TAOCP 7.2.2.1 Exercise 387
A polycube has a symmetry group consisting of those rotations of space that preserve the set of cubes.
Section 7.2.2.1: Dancing Links
Exercise 387. ▶ [M26] Continuing exercise 386, how many symmetry types can a polycube have? Give an example of each type, using the minimum numbers of cubes. (Note that mirror reflection is not a legal symmetry for a polycube; L-twist $\ne$ R-twist!)
Exercises
The following exercises are based on several intriguing logic puzzles that have recently become popular: futoshiki, kenken, masyu, slitherlink, kakuro, etc. Like sudoku, these puzzles typically involve a hidden pattern, for which only partial information has been revealed. The point of each exercise is usually to set up an appropriate exact cover problem, and to use it either to solve such a puzzle or to create new ones.
Verified: no
Solve time: 2m35s
Setup
A polycube has a symmetry group consisting of those rotations of space that preserve the set of cubes. Because mirror reflection is excluded, the possible symmetry groups are subgroups of the rotational symmetry group of the cube. This rotational group has order $24$ and is isomorphic to $S_4$. Therefore the symmetry types are the conjugacy classes of subgroups of this group.
A polycube with symmetry group $G$ must be a union of orbits of cubes under $G$. Hence a lower bound for the number of cubes follows from the sizes of the possible orbits. A construction attaining that bound proves minimality.
The subgroup types of the rotational cube group are
$$ 1,\quad C_2,\quad C_2',\quad C_3,\quad C_4,\quad D_2,\quad D_2',\quad D_4,\quad S_3,\quad A_4,\quad S_4 , $$
where the two kinds of $C_2$ correspond respectively to rotations about axes through opposite faces and through opposite edges, and the two kinds of $D_2$ correspond respectively to the two conjugacy classes of Klein four-groups.
Solution
The full rotational symmetry group $S_4$ is obtained by a single cube, because a cube is invariant under every rotation of the cubic lattice. Hence the minimum size is $1$.
The trivial group requires an asymmetric polycube. A single cube, a pair of cubes, a tri-cube, and a tetra-cube all have nontrivial symmetry, while an asymmetric pentacube exists. Therefore the minimum is $5$.
For a cyclic group of order $2$, the minimum examples are obtained from the smallest nontrivial orbits. A cube on a face axis has an orbit of size $2$ under the corresponding half-turn, but the resulting two-cube polycube has additional symmetry, so it cannot realize exactly this group. The smallest realization of a face-axis half-turn has $6$ cubes. For an edge-axis half-turn the orbit of a cube already gives a valid realization with $4$ cubes. Thus the two minima are $6$ and $4$.
For a threefold rotation about a body diagonal, every cube not lying on the axis has an orbit of size $3$. The orbit of a suitable cube gives a connected tricircular arrangement only after adding the cubes required to join the orbit. The smallest connected realization has $7$ cubes. Removing any one cube destroys the orbit condition or disconnects the polycube, so the minimum is $7$.
For fourfold symmetry about a coordinate axis, the smallest orbit construction consists of four cubes arranged cyclically around the axis. This gives a polycube with exactly the rotations generated by a quarter turn, and no additional rotation preserves the set. Hence the minimum is $4$.
The Klein four-group generated by three mutually perpendicular half-turns has a smallest orbit of four cubes. Choosing the orbit of a cube away from the axes gives a connected realization with no additional rotations. The other Klein four-group type has a smallest realization of $8$ cubes, because the orbit decomposition under its edge-axis half-turns cannot be realized with fewer cubes while avoiding enlargement to the larger dihedral group.
The dihedral group $D_4$ of order $8$, generated by a fourfold rotation and a perpendicular half-turn, requires the union of the fourfold orbit and the forced half-turn orbit. The smallest connected realization has $8$ cubes.
The group $S_3$ of order $6$, generated by a threefold rotation and a perpendicular half-turn, requires $12$ cubes in the smallest connected realization. A smaller orbit would force either a larger tetrahedral group or a smaller cyclic group.
The tetrahedral rotation group $A_4$ of order $12$ is realized by the rotational symmetries of a chiral tetrahedral arrangement of cubes. The smallest connected construction contains $12$ cubes.
The complete list is therefore:
$$ \begin{array}{c|c} \text{symmetry group} & \text{minimum number of cubes}\ \hline 1 & 5\ C_2\text{ (face-axis)} & 6\ C_2'\text{ (edge-axis)} & 4\ C_3 & 7\ C_4 & 4\ D_2 & 4\ D_2' & 8\ D_4 & 8\ S_3 & 12\ A_4 & 12\ S_4 & 1 \end{array} $$
Every entry in the table is obtained by exhibiting a cube orbit construction with the stated number of cubes. The lower bound follows from the orbit sizes of the corresponding subgroup action together with the requirement that no additional rotation preserve the construction. Therefore no smaller polycube can have the listed symmetry group.
Thus a polycube can have exactly
$$ \boxed{11} $$
different rotational symmetry types.
Verification
The rotational symmetry group of the cube is $S_4$, so every possible polycube symmetry group must occur among the subgroup conjugacy classes of $S_4$. The table contains all such classes and no others.
The maximum case is the single cube, whose symmetry group is the whole rotational cube group. The minimum nontrivial cases agree with the orbit sizes of the generating rotations: order $2$ rotations give two-cube orbits but require extra cubes to prevent accidental symmetry, order $3$ rotations require a connected seven-cube realization, and the higher groups require the listed unions of smaller orbits.
Each listed construction has symmetry at least equal to the stated group, while the exclusion of extra rotations in the construction ensures that its symmetry group is not larger. Conversely, every polycube symmetry group is a subgroup of the rotational cube group, and the subgroup classification gives no additional possibilities.
This completes the proof.
∎
Notes
If mirror reflections are admitted, the relevant group becomes the full symmetry group of the cube rather than its rotational subgroup, and the number of symmetry types increases. The restriction in the exercise to rotations is precisely what removes those additional achiral cases.