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 😀
Best Answer
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.)