How many non isomorphic $n \times n \times n$ binary tensors under the action of the octahedral symmetry group of the cube are there?

93 Views Asked by At

I think combinatorics meets group theory in this one... both of which I'm not very good at yet.

The $2$D version of this problem is a lot simpler to work with. The pattern of how many non-isomorphic $n \times n$ matrices under the action of the dihedral symmetry group of the square goes $1, 2, 6, 102, 8548,...$ which is sequence $A054247$ in the OEIS. $1$ being the $n = 0$ cases, $2$ being the $n = 1$, and $6$ being the $n = 2$ case and so on. Meaning there are only $6$ ways of arranging a $2 \times 2$ grid of $1$s and $0$s such that they are unique through all possible rotations of a square.

However, I tried to search for the $3$D version of this sequence and couldn't find any mention of it anywhere.

In the $3$D case, $n=1$ is trivial and is equal to $2$, and I solved $n=2$ by manually enumerating through all possible rotations using a physical model to help me visualize the problem. There are $2^8 = 256$ possible binary $2 \times 2 \times 2$ tensors. These $256$ can be further broken down with pascals triangle to help organize the types of a tensor into categories of how many $1$s are in the tensor. $1, 8, 28, 56, 70, 56, 28, 8, 1$. Then I found corresponding non-isomorphic ways of arranging those $1$s of $1, 1, 3, 3, 7, 3, 3, 1, 1$. Which is a total of $23$ different ways. So $n=2$ case is $23$.

So I have $1, 2, 23, ...$

However, now I'm stuck because the $n=3$ case has $2^{27} = 134,217,728$ possible tensors. So it's impossible for me to enumerate through to solve it. I only know so far of course there is $1$ way of having a $3 \times 3 \times 3$ tensor with no $1$s, and in the case of one $1$, there are $27$ possible tensors, which break down into $4$ different non-isomorphic arrangements. For two $1$s, there are $351$ possible tensors. I can't brute force my way through this problem anymore.

Through looking at the $2$D case, for large $n$, the number of possible matrices / the number of non-isomorphic ways converges to $8$ (which is the number of symmetries of the square). So for my ballpark figure of how many non-isomorphic binary $3 \times 3 \times 3$ tensors there are is $134217728/24$ = approximately $5.6$ million.

How would you go about getting an exact figure for this, and then $n=4$ case, etc? Is there any clever group theory stuff I should be using to solve this, or is it just one of those computational problems? Sorry for the terrible formatting, or if this is a silly question, it's just something that's been on my mind a lot lately.

1

There are 1 best solutions below

0
On BEST ANSWER

Here we present rotational symmetries to help with the OEIS search and produce further activity on the question. We compute the cycle index call it $Z(Q_n).$ This will depend on whether $n$ is even or odd. When we speak of vertices, edges and faces this refers to the main cube formed by the constituent cubes that hold the values of the tensor.

The first term is the identity, giving for $n$ odd

$$a_1^{n^3}$$

and for $n$ even

$$b_1^{n^3}$$

The next is rotations by $120$ and $240$ degrees about one of four diagonals connecting opposite vertices, giving for $n$ odd (the rotation fixes the constituent cubes on the diagonal)

$$8 a_1^n a_3^{(n^3-n)/3}$$

and for $n$ even

$$8 b_1^n b_3^{(n^3-n)/3}.$$

There are rotations by $90$ and $270$ degrees about three axes connecting the midpoints of opposite faces. We get for $n$ odd

$$6 a_1^n a_4^{(n^3-n)/4}$$

and for $n$ even

$$6 b_4^{n^3/4}.$$

There are rotations by $180$ degrees about three axes connecting the midpoints of opposite faces. We get for $n$ odd

$$3 a_1^n a_2^{(n^3-n)/2}$$

and for $n$ even

$$3 b_2^{n^3/2}.$$

Finally we have rotations by $180$ degrees about four axes connecting the midpoints of opposite edges. We get for $n$ odd

$$6 a_1^n a_2^{(n^3-n)/2}$$

and for $n$ even

$$6 b_2^{n^3/2}.$$

Therefore with $n$ odd the cycle index is

$$Z(Q_n) = \frac{1}{24} \left(a_1^{n^3} + 8a_1^n a_3^{(n^3-n)/3} + 6 a_1^n a_4^{(n^3-n)/4} + 9 a_1^n a_2^{(n^3-n)/2} \right)$$

and with $n$ even it is

$$Z(Q_n) = \frac{1}{24} \left(b_1^{n^3} + 8b_1^n b_3^{(n^3-n)/3} + 6 b_4^{n^3/4} + 9 b_2^{n^3/2} \right).$$

With two colors setting the variables to $2$ by Burnside this gives the sequence

$$2, 23, 5605504, 768614338020786176, \\ 1772303994379887844373479205703254016, \\ 4388012152856549445746584486819723041078276071004502223505850368, \ldots$$

which points us to OEIS A334616, which says "number of 2-colorings of an n X n X n grid, up to rotational symmetry" so we have the right cycle index. Unfortunately there is no link to the data for the full octahedral symmetry, so this calculation is left to the MSE reader. On the other hand OP says for $n=2$ the answer is $23$ so maybe OP does in fact refer to rotational symmetry.

Remark. OP mentions $24$ symmetries so it looks like the above will do.