1
$\begingroup$

I have a cube $X\in \mathbb R^{N\times N\times N}$ such that no matter how the cube is rotated by $90^\circ$ along any of the axes, the result is unchanged. What is the maximum number of distinct entries in the cube if $N$ is odd?

Here is my answer. I am sure that it is less than or equal to the true answer.

Let $n=(N+1)/2$. There exists a subcube of shape $\mathbb R^{n\times n\times n}$ that contains all of the distinct entries. This subcube must be on the corner of the cube, so I can imagine the indices of the entries as being in $\mathbb N_n^3,\mathbb N_n:=1,...,n$.

The claim I am unsure of: the indices of any one of the distinct entries are the same up to a permutation, e.g., the $(1,2,3), (1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$ entries must all be the same. This is sufficient for the cube to be rotation invariant, but it may not be necessary, which would allow for the final answer to be greater.

Assuming that this claim is true, it's enough to just count the number of sets of indices that are equal up to a permutation. That is the same as unordered sampling with replacement, and thus, the number of distinct entries is $\binom{n+3-1}{3} = \binom{n+2}{3}$

Results following @MaartenHavinga:

I attempted to follow Maarten's instructions to generate the $(0,0,0)$ corner of the cube (the first dimension is the row, second is the column, third is the depth, i.e. the "upper left front" part of the cube).

When $n=3$, the results are good:

Group 0: 
 [[0 0 0]]
Group 1: 
 [[0 0 1]
 [0 1 0]
 [1 0 0]]
Group 2: 
 [[0 0 2]
 [0 2 0]
 [2 0 0]]
Group 3: 
 [[0 1 1]
 [1 0 1]
 [1 1 0]]
Group 4: 
 [[0 1 2]
 [0 2 1]
 [1 0 2]
 [1 2 0]
 [2 0 1]
 [2 1 0]]
Group 5: 
 [[0 2 2]
 [2 0 2]
 [2 2 0]]
Group 6: 
 [[1 1 1]]
Group 7: 
 [[1 1 2]
 [1 2 1]
 [2 1 1]]
Group 8: 
 [[1 2 2]
 [2 1 2]
 [2 2 1]]
Group 9: 
 [[2 2 2]]

array([[[ 1.62, -0.61, -0.53],
        [-0.61, -1.07,  0.87],
        [-0.53,  0.87, -2.3 ]],

       [[-0.61, -1.07,  0.87],
        [-1.07,  1.74, -0.76],
        [ 0.87, -0.76,  0.32]],

       [[-0.53,  0.87, -2.3 ],
        [ 0.87, -0.76,  0.32],
        [-2.3 ,  0.32, -0.25]]])

However, when $n=4$, the results are slightly off:

Group 0: 
 [[0 0 0]]
Group 1: 
 [[0 0 1]
 [0 1 0]
 [1 0 0]]
Group 2: 
 [[0 0 2]
 [0 2 0]
 [2 0 0]]
Group 3: 
 [[0 0 3]
 [0 3 0]
 [3 0 0]]
Group 4: 
 [[0 1 1]
 [1 0 1]
 [1 1 0]]
Group 5: 
 [[0 1 2]
 [1 2 0]
 [2 0 1]]
Group 6: 
 [[0 2 1]
 [1 0 2]
 [2 1 0]]
Group 7: 
 [[0 1 3]
 [0 3 1]
 [1 0 3]
 [1 3 0]
 [3 0 1]
 [3 1 0]]
Group 8: 
 [[0 2 2]
 [2 0 2]
 [2 2 0]]
Group 9: 
 [[0 2 3]
 [0 3 2]
 [2 0 3]
 [2 3 0]
 [3 0 2]
 [3 2 0]]
Group 10: 
 [[0 3 3]
 [3 0 3]
 [3 3 0]]
Group 11: 
 [[1 1 1]]
Group 12: 
 [[1 1 2]
 [1 2 1]
 [2 1 1]]
Group 13: 
 [[1 1 3]
 [1 3 1]
 [3 1 1]]
Group 14: 
 [[1 2 2]
 [2 1 2]
 [2 2 1]]
Group 15: 
 [[1 2 3]
 [2 3 1]
 [3 1 2]]
Group 16: 
 [[1 3 2]
 [2 1 3]
 [3 2 1]]
Group 17: 
 [[1 3 3]
 [3 1 3]
 [3 3 1]]
Group 18: 
 [[2 2 2]]
Group 19: 
 [[2 2 3]
 [2 3 2]
 [3 2 2]]
Group 20: 
 [[2 3 3]
 [3 2 3]
 [3 3 2]]
Group 21: 
 [[3 3 3]]

array([[[ 1.62, -0.61, -0.53, -1.07],
        [-0.61,  0.87, -2.3 , -0.76],
        [-0.53,  1.74,  0.32, -0.25],
        [-1.07, -0.76, -0.25,  1.46]],

       [[-0.61,  0.87,  1.74, -0.76],
        [ 0.87, -2.06, -0.32, -0.38],
        [-2.3 , -0.32,  1.13, -1.1 ],
        [-0.76, -0.38, -0.17, -0.88]],

       [[-0.53, -2.3 ,  0.32, -0.25],
        [ 1.74, -0.32,  1.13, -0.17],
        [ 0.32,  1.13,  0.04,  0.58],
        [-0.25, -1.1 ,  0.58, -1.1 ]],

       [[-1.07, -0.76, -0.25,  1.46],
        [-0.76, -0.38, -1.1 , -0.88],
        [-0.25, -0.17,  0.58, -1.1 ],
        [ 1.46, -0.88, -1.1 ,  1.14]]])

I will refer to positions starting from index 1. In the 2nd depth position, the entry in the 3rd row and 4th column (-1.1) is distinct from the entry in the 4th row and 3rd column (-0.17). This is because the indices are (3, 4, 2) and (4, 3, 2) which are an odd permutation.

However, in order for the cube to be rotation invariant to rotations about the row and column axes (i.e., around the entry -0.88 in the second depth dimension), these two entries should be equal.

Results following @MaartenHavinga's corrected answer for n=4:

Group 0: 
 [[0 0 0]]
Group 1: 
 [[0 0 1]
 [0 1 0]
 [1 0 0]]
Group 2: 
 [[0 0 2]
 [0 2 0]
 [2 0 0]]
Group 3: 
 [[0 0 3]
 [0 3 0]
 [3 0 0]]
Group 4: 
 [[0 1 1]
 [1 0 1]
 [1 1 0]]
Group 5: 
 [[0 1 2]
 [1 2 0]
 [2 0 1]]
Group 6: 
 [[0 2 1]
 [1 0 2]
 [2 1 0]]
Group 7: 
 [[0 1 3]
 [0 3 1]
 [1 0 3]
 [1 3 0]
 [3 0 1]
 [3 1 0]]
Group 8: 
 [[0 2 2]
 [2 0 2]
 [2 2 0]]
Group 9: 
 [[0 2 3]
 [0 3 2]
 [2 0 3]
 [2 3 0]
 [3 0 2]
 [3 2 0]]
Group 10: 
 [[0 3 3]
 [3 0 3]
 [3 3 0]]
Group 11: 
 [[1 1 1]]
Group 12: 
 [[1 1 2]
 [1 2 1]
 [2 1 1]]
Group 13: 
 [[1 1 3]
 [1 3 1]
 [3 1 1]]
Group 14: 
 [[1 2 2]
 [2 1 2]
 [2 2 1]]
Group 15: 
 [[1 2 3]
 [1 3 2]
 [2 1 3]
 [2 3 1]
 [3 1 2]
 [3 2 1]]
Group 16: 
 [[1 3 3]
 [3 1 3]
 [3 3 1]]
Group 17: 
 [[2 2 2]]
Group 18: 
 [[2 2 3]
 [2 3 2]
 [3 2 2]]
Group 19: 
 [[2 3 3]
 [3 2 3]
 [3 3 2]]
Group 20: 
 [[3 3 3]]

array([[[ 1.62, -0.61, -0.53, -1.07],
        [-0.61,  0.87, -2.3 , -0.76],
        [-0.53,  1.74,  0.32, -0.25],
        [-1.07, -0.76, -0.25,  1.46]],

       [[-0.61,  0.87,  1.74, -0.76],
        [ 0.87, -2.06, -0.32, -0.38],
        [-2.3 , -0.32,  1.13, -1.1 ],
        [-0.76, -0.38, -1.1 , -0.17]],

       [[-0.53, -2.3 ,  0.32, -0.25],
        [ 1.74, -0.32,  1.13, -1.1 ],
        [ 0.32,  1.13, -0.88,  0.04],
        [-0.25, -1.1 ,  0.04,  0.58]],

       [[-1.07, -0.76, -0.25,  1.46],
        [-0.76, -0.38, -1.1 , -0.17],
        [-0.25, -1.1 ,  0.04,  0.58],
        [ 1.46, -0.17,  0.58, -1.1 ]]])
Improve this question
$\endgroup$
8
  • $\begingroup$ Since SO(3), the group of all rotations in 3D, contains A3 but not S3, the odd permutations are excluded. So there are twice as much 3 different index unique elements. I think you're correct after changing that. $\endgroup$
    – Maarten Havinga
    Commented Nov 30, 2022 at 20:20
  • 1
    $\begingroup$ I don't understand the notation. If $N$ is, say, $5$, then $X$ is a cube in the $125$-dimensional space ${\bf R}^{5\times5\times5}={\bf R}^{125}$. I don't know what it means for $X$ to be a cube in this space. So, maybe you mean a cube in ${\bf R}^3$, measuring five on each side. Then what does "the result is unchanged" mean? What result? Unchanged from what? $\endgroup$
    – Gerry Myerson
    Commented Nov 30, 2022 at 22:54
  • 1
    $\begingroup$ @GerryMyerson Similar to how $\mathbb R^{5\times5}$ is the space of $5\times5$ matrices, $\mathbb R^{5\times5\times5}$ is the space of $5\times5\times5$ tensors. I'm imagining rotating a tensor $X$ by a rotation tensor $R$, similar to a rotation matrix. Then what I mean by unchanged is that $R\cdot X = X$ $\endgroup$
    – Jacob Helwig
    Commented Dec 1, 2022 at 0:23
  • 1
    $\begingroup$ @LSpice Sure, I edited my question $\endgroup$
    – Jacob Helwig
    Commented Dec 1, 2022 at 0:26
  • 1
    $\begingroup$ @MaartenHavinga SO(3) actually does contain S3, inside A5. $\endgroup$
    – Daniel Sebald
    Commented Dec 1, 2022 at 23:47

1 Answer 1

Reset to default
1
$\begingroup$

Since rotations give only even permutations, the 3 distinct index triples $\{a,b,c\}$ with $a \neq b \neq c \neq a$ give twice as much distinct entries as you gave: entries at $(a,b,c)$ and $(b,a,c)$ may be distinct in this case. This adds $n$ choose $3$ distinct entries.

However, for entries $\{a,b,n\}$ a 90 degree rotation can interchange $b$ and $n$ because $N$ is odd and $n=(N+1)/2=1-n$ modulo $N$, which is an odd permutation identifying $\binom{n-1}{2}$ unique entry pairs.

That gives a total of $\binom{n+2}{3} + \binom{n}{3} - \binom{n-1}{2}$ which is $\binom{n+2}{3} + \binom{n-1}{3}$ distinct entries/dimensions in your tensor space. Check for instance for $n=3, N=5$: giving $10$ distinct entries.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think that this is over-counted. In the $n=3$ case, the entries you identified do indeed produce a roto-invariant cube. When $n=4$, though, there are some issues. For example, the $(3,4,2)$ and $(4,3,2)$ entries are permitted to be distinct from one another because these indices are odd permutations with respect to the other. However, I believe that these entries should be the same for roto-invariance. See the example in my edit $\endgroup$
    – Jacob Helwig
    Commented Dec 2, 2022 at 17:34
  • 1
    $\begingroup$ You are right, I will edit my answer $\endgroup$
    – Maarten Havinga
    Commented Dec 3, 2022 at 10:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .