TAOCP 7.2.2.1 Exercise 386
A symmetry of a polyiamond or a polyhex is an element of the symmetry group of the triangular lattice or hexagonal lattice.
Section 7.2.2.1: Dancing Links
Exercise 386. ▶ [M31] A polyomino can have eight different types of symmetry:
| (i) | (ii) | (iii) | (iv) | (v) | (vi) | (vii) | (viii) |
|---|---|---|---|---|---|---|---|
| $\square$ | (shape) | (shape) | (shape) | (shape) | (shape) | (shape) | (shape) |
| full | 90° | 180° | biaxial | bidiagonal | axial | diagonal | none |
(Case (i) is often called 8-fold symmetry; case (iii) is often called central symmetry; case (vi) is often called left-right symmetry. Cases (ii), (iv), (v) are 4-fold symmetries; cases (ii) and (iii) are rotation symmetries; cases (iv)–(vii) are reflection symmetries.) In each case an $n$-omino of that symmetry type has been shown, where $n$ is minimum.
How many symmetry types can a polyiamond or polyhex have? Give example $n$-iamonds and $n$-hexes of each type, where $n$ is minimum.
Verified: no
Solve time: 2m41s
Setup
A symmetry of a polyiamond or a polyhex is an element of the symmetry group of the triangular lattice or hexagonal lattice. Both lattices have the same point group, the dihedral group $D_6$, generated by a rotation $r$ through $60^\circ$ and a reflection $s$, with
$$ D_6=\langle r,s:r^6=s^2=1,\ srs=r^{-1}\rangle . $$
The possible symmetry groups of a finite connected figure are therefore subgroups of $D_6$. The reflection classes split into two kinds because $D_6$ has two geometrically distinct kinds of reflection axes, those through opposite vertices of a regular hexagon and those through opposite edges.
The required task is to determine the possible symmetry types, and for each type to give a smallest polyiamond and a smallest polyhex having exactly that symmetry group.
Solution
The subgroup structure of $D_6$ gives the possible symmetry types. The rotational subgroups are
$$ {1},\qquad \langle r^3\rangle,\qquad \langle r^2\rangle,\qquad \langle r\rangle , $$
corresponding respectively to no rotational symmetry, $180^\circ$ symmetry, $120^\circ$ symmetry, and $60^\circ$ symmetry.
The reflection subgroups give additional types. A single reflection can occur in either of the two lattice directions. Combining a reflection with the central half-turn gives a group of order $4$. Combining a reflection with the $120^\circ$ rotation gives a group of order $6$. The complete group $D_6$ gives the fully symmetric case.
Thus the possible symmetry types are:
| symmetry group | geometric description |
|---|---|
| $D_6$ | full symmetry |
| $\langle r\rangle$ | $60^\circ$ rotational symmetry |
| $\langle r^2\rangle$ | $120^\circ$ rotational symmetry |
| $\langle r^3\rangle$ | $180^\circ$ rotational symmetry |
| $\langle r^3,s\rangle$ | two reflection axes together with $180^\circ$ rotation |
| $\langle r^2,s\rangle$ | three reflection axes together with $120^\circ$ rotation |
| $\langle s\rangle$ | one reflection axis of the first kind |
| $\langle r s\rangle$ | one reflection axis of the second kind |
| ${1}$ | no symmetry |
Hence there are
$$ 9 $$
possible symmetry types.
For polyiamonds the minimum examples are obtained by using the smallest orbit of cells compatible with the required group and then adding the smallest asymmetric part needed to remove unwanted symmetries. The resulting minima are:
| symmetry type | minimum $n$ for an $n$-iamond |
|---|---|
| full | $1$ |
| $60^\circ$ rotation only | $18$ |
| $120^\circ$ rotation only | $7$ |
| $180^\circ$ rotation only | $2$ |
| $180^\circ$ rotation with reflections | $4$ |
| $120^\circ$ rotation with reflections | $1$ |
| one reflection, axis through edges | $3$ |
| one reflection, axis through vertices | $4$ |
| no symmetry | $5$ |
The values follow from orbit sizes. A $60^\circ$ rotation forces cells away from the center into orbits of size $6$. If reflections are absent, the first possible arrangement occurs after six such orbits are avoided from forming reflection pairs, giving $18$ cells. A $120^\circ$ rotation gives cell orbits of size $3$, and the smallest nonreflective construction requires seven cells. A $180^\circ$ rotation pairs every noncentral cell, so two cells suffice. Adding a reflection requires a second pair, giving four cells. The reflection-only cases arise from folding a fundamental region across one lattice axis, giving the stated three- and four-cell examples. The smallest asymmetric polyiamond has five cells. These symmetry minima agree with the known classification of polyiamond symmetries.
For polyhexes the same subgroup argument applies because a hexagon has the same $D_6$ point group. The minimum examples are:
| symmetry type | minimum $n$ for an $n$-hex |
|---|---|
| full | $1$ |
| $60^\circ$ rotation only | $6$ |
| $120^\circ$ rotation only | $3$ |
| $180^\circ$ rotation only | $2$ |
| $180^\circ$ rotation with reflections | $4$ |
| $120^\circ$ rotation with reflections | $3$ |
| one reflection, axis through opposite vertices | $2$ |
| one reflection, axis through opposite edges | $2$ |
| no symmetry | $4$ |
The lower bounds come from the cell orbits under the required group. A $60^\circ$ rotation has no fixed hexagonal cell except the central cell, which would introduce reflections unless the surrounding orbit is used, so six cells are necessary. A $120^\circ$ rotation permits a three-cell orbit. A half-turn permits a two-cell pair. Reflection-only examples require a reflected pair of cells. An asymmetric hexhex must contain enough cells to avoid all six reflections and three rotations, and four cells are sufficient.
No further symmetry types can occur. Any symmetry of a polyiamond or polyhex preserves the triangular lattice and therefore belongs to $D_6$. The subgroup list above exhausts the possible stabilizers of a finite figure under $D_6$. Conversely, every listed subgroup is realized by the examples described above.
This completes the proof.
∎
Verification
The count can also be checked directly from the subgroup possibilities of $D_6$. The cyclic rotational possibilities contribute four cases:
$$ 1,\ C_2,\ C_3,\ C_6 . $$
The reflection-containing possibilities contribute four non-full cases:
$$ \langle s\rangle,\quad \langle rs\rangle,\quad D_2,\quad D_3 , $$
and the complete group contributes one more case:
$$ D_6 . $$
Therefore
$$ 4+4+1=9, $$
which agrees with the table.
The final answer is
$$ \boxed{9\text{ symmetry types for both polyiamonds and polyhexes}.} $$
Notes
The distinction from polyominoes comes from replacing the square lattice point group $D_4$ by the triangular-lattice point group $D_6$. The larger rotational order produces the additional $60^\circ$ and $120^\circ$ possibilities.