Coloring the faces of a hypercube

I will restate the 3-D version of the problem. In how many ways can you color a regular cube with 2 colors up to a rotational isometry. The answer is of course a special case of Burnsides Lemma which can be used to show that the number of distinct face permutations is $\frac{1}{24}(N^6 + 3N^4 + 12N^3 + 8N^2)$ where $N$ is the number of colors used, $2$ in this case, which gives us an answer of $10$ distinct permutations.

My question is how can you expand this to a tesseract, and then more generally, to any hypercube. The rotational isometries of a cube are somewhat simple to comprehend, but the rotational isometries o hypercube are difficult to grasp (even after an hour of playing with the 4d rubiks cube app)

My initial thought was to consider the expansion of a tesseract as 8 interconnected cubelets. For the two color case each one of these cubelets has 10 distinct states. Which gives us $10^8$ non-distinct permutations of the hypercube. Or more generally, this reduces to how many distinct ways one can color a 8 faced 3-dimensional figure using 10 colors. So the complicated question of 4-dimensional isometries reduces to 3 dimensional rotational isometries of a octahedron.

But I'm a physicist so what the hell do I know :D

Solution 1:

First let's state the special case of Burnside's lemma that is relevant here.

Lemma: Let $G$ be a finite group acting on a finite set $X$. The number of ways to color the elements of $X$ with $z$ different colors, up to the action of $G$, is

$$\frac{1}{|G|} \sum_{g \in G} z^{c(g)}$$

where $c(g)$ is the number of cycles in the cycle decomposition of $g$ acting on $X$. (Proof.)

Here $X$ is the set of faces of a hypercube. In $n$ dimensions there are $2n$ such faces. $G$ is the subgroup of index $2$ in the hyperoctahedral group with determinant $1$, also known as the Coxeter group $D_n$. So our job now is to count, for each $k$, the number of elements of $D_n$ with $k$ cycles in the action on $X$.

Now, note that to analyze the action of $D_n$ on the faces it suffices to analyze the action of $D_n$ on the midpoints of the faces. But these are precisely the $2n$ points $(0, 0, ... \pm 1, ..., 0, 0)$, so writing the elements of $D_n$ as signed permutation matrices is very well-suited to analyzing their action on these points; in particular, it suffices to figure out the answer for a single signed cycle. But this turns out to be very simple: there are either one or two cycles depending on whether the product of the signs is $-1$ or $+1$.

(It might be helpful here to play with a specific example. Consider $\left[ \begin{array}{cc} 0 & 1 & 0 \\ 0 & 0 & -1 \\ -1 & 0 & 0 \end{array} \right]$ acting on the six points $(\pm 1, 0, 0), (0, \pm 1, 0), (0, 0, \pm 1)$ to get a feel for what's going on in the general case.)

From here I think it's easiest to work with generating functions because the combinatorics get a little messy. Begin with the identity

$$\sum_{m \ge 0} Z(S_n) t^n = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right)$$

where $Z(S_n)$ is the cycle index polynomial for the action of $S_n$ on $\{ 1, 2, ... n \}$. Each $z_i$ is the term that controls cycles of length $i$. We want to modify this generating function so that it tells us how the cycles in $D_n$ work. There are $2^i$ signed cycles of length $i$ which come in two flavors: half of them have positive sign product (two unsigned cycles) and half of them have negative sign product (one unsigned cycle), so to keep track of the total number of unsigned cycles we should replace $z_i$ with $2^{i-1} z^2 + 2^{i-1} z$. We also have to keep in mind that the determinant of a signed cycle is its sign product multiplied by $(-1)^{i+1}$, and we only want permutations with determinant $1$. So the generating function we want is

$$\sum_{n \ge 0} f_n(z) \frac{t^n}{n!} = \frac{1}{2} \left( \exp \left( \sum_{i \ge 1} \frac{2^{i-1} z^2 + 2^{i-1} z) t^i}{i} \right) + \exp \left( \sum_{i \ge 1} (-1)^{i+1} \frac{2^{i-1} z^2 - 2^{i-1} z) t^i}{i} \right) \right)$$

where $f_n(z) = \sum_{g \in D_n} z^{c(g)}$. After some simplification the above becomes

$$\sum_{n \ge 0} \frac{1}{|D_n|} f_n(z) t^n = \frac{1}{(1 - t)^{(z^2+z)/2}} + (1+t)^{(z^2-z)/2}.$$

Substituting $z = 2$ gives, at last, the answer

$$\sum_{n \ge 0} \frac{1}{|D_n|} f_n(2) t^n = \frac{1}{(1 - t)^3} + 1 + t.$$

In other words, for $n \ge 2$ we simply have $\frac{1}{|D_n|} f_n(2) = {n+2 \choose 2}$. This is such a simple answer that there should be a direct proof of it. I'll keep working on it. (There is a rather straightforward proof of the corresponding result with "hypercube" replaced by "simplex," so my guess is something along those lines is possible here.)

Solution 2:

Once someone else has done the hard work and come up with the answer, as Qiaochu has done, then it's easy to prove it on an ad hoc basis as this interloper (me) will do.

Consider an $n$-cube with faces coloured red and blue. Consider a set of $n$ balls. Colour the $j$-th ball red, blue or green according to the colours of the $j$-th pair of faces in the cube, that is if they both have the same colour give the ball that colour, else if they have different colours colour the ball green. Now a symmetry operation on the cube will shuffle the balls so the number of each colour of balls will be the same. Conversely given the $n$ coloured balls there will be various coloured cubes giving rise to the colour distribution of the balls, but these will all be equivalent under the full symmetry group of the cube. However for $n\ge 2$ each $2$-coloured cube has a non-rotational symmetry, so any two coloured cubes giving rise to the same colour distribution of balls are related by a rotation. Hence the number of $2$-coloured $n$-cubes up rotation is the same as the number of triples $(r,b,g)$ of nonnegative integers adding to $n$ and there are ${n+2\choose 2}$ of these.

One can repeat this with $k$-colours for the cube. This time one needs ${k+1\choose 2}$ colours for the balls, and the argument ensuring that rotations and the full symmetry group give the same answer requires $n>{k\choose 2}$ (why?).

Added (30/9/2010) One can get the general result using these considerations. For $n>{k\choose 2}$ one gets $${n+(k^2+k)/2-1\choose (k^2+k)/2-1}$$ colourings up to rotations. For $n\le {k\choose 2}$ there are $k$-colourings having no improper (determinant $-1$) symmetries. But any such colouring has no nontrivial symmetries at all. If two opposite faces have the same colour, one can reflect through a hyperplane parallel to them. So assume that no colour is opposite itself. Then if two pairs of opposite faces have the same two colours between them, one can reflect in a plane $x_i=x_j$or $x_i=-x_j$. Hence in these "special" colourings each pair of opposite faces has a distinct pair of distinct colours. Up to symmetry there are $${(k^2-k)/2\choose n}$$ of these special colourings. So for $n\le{k\choose 2}$ there are $${(k^2-k)/2\choose n}+{n+(k^2+k)/2-1\choose (k^2+k)/2-1}$$ up to rotational symmetries.