## Wednesday, May 18, 2016

### Triangular numbers, a 3D cube, and the octahedral group

For some computational geometry project, I had to understand the orbits of the action of the octahedral group on a 3D cube, and like so many times with math, I did it the hard way only to find out later that a simple observation would have saved me the effort. Well, some of the effort.

#### tl;dr

Upon counting the orbits of the cells of a 3D cube under the octahedral group action, I found out the result is a sum of triangular numbers, which has a very intuitive geometric reason.

#### The gory details

The octahedral group can be thought of as the group of symmetries obtained by applying a series of 90-degree rotations and/or face-parallel reflections to a cube. Another way of thinking about it is this: if the cube is centered at the origin, applying an element of the group to the cube is equivalent to shuffling the coordinates and/or multiplying some of the coordinates by $-1$. Since there are 6 permutations of the coordinates, and 8 choices as to which coordinates to multiply by $-1$, the number of elements in the group is 48.

For simplicity, let's assume that the 3D cube is actually a discrete object, comprised of $n^3$ cells for some even value of $n$ (having an odd $n$ doesn't change the outcome by a lot, but is a bit different). The group action breaks the cube into orbits, for example, the corner cells form a single orbit of size 8. Note that the group elements can be also thought of as $3\times 3$ matrices, all of whose determinents are $1$ or $-1$ (the latter if the element induces a reflection), and the action thus preserves norms. To put it plainly, the distance of a cell from the cube's center is an invariant of the group action. This observation means that we can think of the cube as comprised of $\frac n 2$ nested hollow cubes of dimensions $n\times n \times n, (n-2)\times(n-2)\times(n-2), ... 4\times 4\times 4, 2\times 2\times 2$, sort of like a matryoshka doll of 3D cubes.
 Image credit: Wikipedia

It suffices to understand how the group acts only on one of these hollow cubes, so let's examine only the largest one - the $n\times n\times n$ hollow cube.

#### Classifying orbits

Suppose the cells are indexed w.r.t. the center of cube, so each cell is indexed by some $i, j, k\in \{-\frac n 2,..., \frac n 2\}\setminus \{0\}$ such that at least one of $i, j, k$ is $\pm \frac n 2$. We omit zero because $n$ is even and no cell is the center cell of the cube.
Observe that using this notation, together with thinking of the group elements as permuting coordinates and/or pointwise multiplying them by $-1$, makes it evident that, up to a permutation, there are only 4 cases, or types of orbits:
Case 1: $\frac n 2 = |i| \neq |j|, |i|\neq |k|, |j| \neq |k|$, choosing such indices defines an orbit of size 48, since no permutation of the coordinates or multiplication of them by $-1$ leaves the indices as they were.
Case 2: $i = |j| = |\frac n 2|, |j|\neq |k|$, these are all the cells that lie on the edges of the hollow cube. A cell with such indices is invariant under elements switching $i$ and $j$, so its orbit's size is 24. To be precise, in the case where $j = -i = \pm \frac n 2$, swapping $i$ and $j$ is just like pointwise multiplying both by $-1$, so the orbit is obtained simply by moving $k$ around and pointwise multiplication by $-1$, and indeed the orbit size is 24.
Case 3: $|i| = |j|, |j| < |k| = \frac n 2$, these are all the cells that lie on the diagonals that run along the face of the hollow cube. For the same arguments as Case 2 - the orbit size here is 24.
Case 4: $|i| = |j| = |k| = \frac n 2$, these are the corner cells. The difference between two corners is only the sign of the coordinates, so the size of such an orbit is 8.

#### Counting orbits

It is now left to understand how many orbits there are for each case. We choose a representative for each orbit - $(i, j, k)$, and count those.
Case 1: The choice is of some unordered pair of elements from $\{1,2,...,\frac n 2 - 1\}$. The pair is unordered since the group action puts $(i,j,k)$ in the same orbit as $(j,i,k)$, and we omit the negatives since they are obtained via the pointwise multiplication by $-1$. The number of ways to choose such a pair is therefore $\frac 1 2 (\frac n 2 - 1)(\frac n 2 - 2)$.
Case 2: Since $|j|$ and $|i|$ must be equal to $\frac n 2$, the only choice here is of $1\leq k < \frac n 2$ (negative values of $k$ are obtained via the pointwise multiplication by $-1$ of the group action). So clearly there are $\frac n 2 - 1$ of those.
Case 3: Like Case 2, the only choice here is of $1 \leq |i| < \frac n 2$, which in turn determins $|j|$. So there are $\frac n 2 - 1$ such orbits.
Case 4: This is the corners' orbit, so there is exactly one for a hollow cube.

Putting it together, a hollow 3D cube of dimension $n$ has $\frac 1 2 (\frac n 2 - 1)(\frac n 2 - 2) + 2 \cdot (\frac n 2 - 1) + 1 = \frac 1 8 (n^2 + 2n)$.
Since the full 3D cube, with an even dimension $s$, is comprised of $\frac s 2$ such hollow cubes, the number of orbits is: $\frac 1 8 \sum _{n=1} ^{\frac s 2} ((2n)^2 + 2(2n))$, which surprisingly gives us a sum of triangular numbers $\sum_{n=1} ^{\frac s 2} \frac {n(n+1)} 2$, which has a nice closed form $\frac {\frac s 2 \cdot (\frac s 2 + 1) \cdot (\frac s 2 + 2)} 6$.

#### Why triangular numbers?

This is a satisfyingly clean formula to ed up with, after a tedious computation, and as one would expect, it is so for a reason:
As noted in the previous paragraph, the result is a sum of triangular numbers, which are called thus because they also represent the number of blocks you'd use to construct a triangle where the bottom row has $n$ blocks, the next row has $n-1$ blocks and so on.
The image below shows one representative of each orbit in the outer layer of an $8\times 8 \times 8$ cube. The Case 1 representatives are red, Case 2 - orange, Case 3 - yellow, and Case 4 - green.

And indeed these representatives form a triangle, and the sum of triangles really represents (sort of) a pyramid that goes from the outer layer of the cube inward, the colorful part of the image below being its base.