Twenty-five colours, and the mirrors come back

A colouring of a repeating pattern is a way of painting its copies of the motif so that every symmetry of the pattern either keeps the colours or permutes them consistently. In group terms it is a subgroup: the operations that keep every colour where it is, with as many cosets as there are colours. Five colours, seven colours, and the primes that split counted the colourings of the seventeen plane groups with a prime number of colours from five upward, and found the answer governed by a single fact. No point group has an order divisible by a prime of five or more, so a colouring with that many colours cannot remove any rotation or mirror. It must keep the whole point group and remove translations instead, by keeping a sublattice of index $p$, which is a line through the origin of the plane modulo $p$.

That reduced everything to lines. Every group keeps some line except the square and hexagonal ones, which keep a line only when the line is an eigenline of the rotation modulo $p$: for the quarter turn when $p$ splits in the Gaussian integers, for the third turn when it splits in the Eisenstein integers. And five groups, the ones with a mirror across their rotation, $p4m$, $p4g$, $p3m1$, $p31m$ and $p6m$, can be coloured at no prime at all, because their mirror exchanges the rotation’s two eigenlines and keeps neither.

The essay ended at the next case it could see. At the square of a prime the argument changes in one place. A subgroup of index $p^2$ may meet the lattice in a sublattice that is not a line but the whole plane modulo $p$, the sublattice $pL$, which every group keeps. So the mirror groups ought to come back. The census here confirms that they do, and measures exactly what else changes and what does not.

What changes at a prime squared #

The first half of the argument survives unchanged. A colouring with $p^2$ colours is a subgroup $H$ of index $p^2$. Its point group has index in the full point group dividing the point group’s order, which is prime to $p$, and the total index $p^2$ is the product of that and the translational index, so the point group is kept whole and $H$ meets the lattice $L$ in a sublattice $L'$ of index $p^2$ that the point group keeps.

The second half needs a case distinction. A sublattice of index $p^2$ has quotient $L/L'$ of order $p^2$, and an abelian group of that order is either the plane $(\mathbb{Z}/p)^2$ or the cycle $\mathbb{Z}/p^2$. The quotient is the plane for exactly one sublattice, $pL$, every lattice vector multiplied by $p$, and every one of the seventeen groups keeps it, since a matrix carries $p$ times a lattice vector to $p$ times another. The quotient is a cycle for the other $p^2 + p$ sublattices of index $p^2$, the points of the projective line over $\mathbb{Z}/p^2$. Of how many sublattices of index $p^2$ a plane lattice has, $p^2 + p + 1$, one is the plane and the rest are cycles.

Above each kept sublattice the count of subgroups is the same as at a prime. The extension of the point group by $L/L'$ splits because their orders are coprime, all its complements are conjugate for the same reason, and they number $|L/L'|$ divided by the number of elements of $L/L'$ the point group fixes. So for $pL$ the count is $p^2$ divided by the number of colours, read as vectors modulo $p$, that every operation of the point group leaves alone. That is $p^2$ for any group with a half-turn or a rotation, which fix only the origin; $p$ for the groups with a single mirror direction, which fix a line; and one for $p1$, which fixes everything.

Every group, twenty-five colours #

The census builds every subgroup of index 25 and of index 49 directly, without the argument. It works in the finite group of the pattern’s operations taken modulo $p^2$ times its lattice, a few thousand to thirty thousand elements. It enumerates every sublattice of index $p^2$ in Hermite form and keeps those the point group carries to themselves. Above each, it tries every way of attaching a translation from $L/L'$ to each generating rotation or mirror, closes the result into a group, and keeps it when it has the right size. Nothing in the search assumes that the point group is kept whole; the subgroups it finds simply all turn out to keep it.

The table at the head of this essay is the outcome. All seventeen groups can be coloured with twenty-five colours and with forty-nine. There are 1,449 colourings at twenty-five and 4,197 at forty-nine, against 104 and 172 at five and seven. The five mirror groups, which have none at five or seven, have exactly $p^2$ at the square, 25 and 49, all of them on $pL$. And the split into plane and cycle agrees with the argument group by group: $p1$ has one colouring on $5L$ and thirty on cycles, $pm$ five and twenty-six, $p2$ twenty-five and 750, $p4$ twenty-five and fifty.

The cyclic counts are where the argument predicts them, and it is worth seeing why. A group whose point group is just the identity or the half-turn, $p1$ or $p2$, acts on lattice vectors by the scalars $\pm1$, which keep every sublattice, so all $p^2 + p$ cycles are kept: thirty at twenty-five, fifty-six at forty-nine. Any other point group keeps a cycle only above a line it keeps modulo $p$.

Which cycles a rotation keeps #

A cyclic sublattice of index $p^2$ reduces modulo $p$ to a line, the sublattice of index $p$ containing it, and each line has exactly $p$ cycles above it. A rotation that keeps a cycle keeps the line beneath it, so the cycles a group keeps lie above the lines it kept at the prime. The converse needs a small calculation. Above a line the quarter turn keeps, the cycles kept are the eigenvectors of the quarter turn modulo $p^2$ that reduce to the eigenvector modulo $p$. The quarter turn’s eigenvalues modulo 5 are 2 and 3, the square roots of $-1$, and each lifts to exactly one square root of $-1$ modulo 25, namely 7 and 18, because the derivative of $x^2 + 1$ at a root is $2x$, which is not zero modulo 5. So each kept line carries exactly one kept cycle, and the figure shows which.

The consequence is that the cyclic colourings are the prime colourings lifted. Each line the prime used carries one cycle at the square, the complements above it are counted the same way, and the colour group on a cycle is the same shape as on the line: the affine maps $c \mapsto ac + b$ of $\mathbb{Z}/p^2$ rather than of $\mathbb{Z}/p$, with the multiplier $a$ in a group of order one, two, three, four or six. Everything the prime colourings did, the cyclic ones do again, one digit further out. The new behaviour is all on the plane.

The plane of colours #

On $pL$ a colour is a coset of $pL$ in the lattice, which is a vector modulo $p$: the colours form a plane, $(\mathbb{Z}/p)^2$, with twenty-five points at five and forty-nine at seven. Translations move the colours by adding that vector, and a rotation or mirror of the pattern moves them by applying its matrix modulo $p$. So the group permuting the colours is an affine group of the colour plane: translations of the plane, with the point group acting linearly.

That is the structure the prime colourings could not have. With $p$ colours the colours formed a line, $\mathbb{Z}/p$, and a linear map of a line is multiplication by a number, so the point group reached the colours only through a homomorphism to the multiplicative group modulo $p$, which is cyclic. A mirror and a rotation together form a non-abelian group, and a non-abelian group cannot act faithfully on a line by multiplication. That is the obstruction the earlier essay found, in different words: the mirror exchanges the rotation’s eigenlines, and with only a line of colours there is nowhere for the exchange to happen. A plane has room. The quarter turn and the mirrors of $p4m$ act on $(\mathbb{Z}/5)^2$ as the dihedral group of order eight acts on any plane, and the colour group is that group with the plane’s twenty-five translations, of order two hundred.

The figure shows the quarter turn acting on the two colour planes, and the difference between them is the Gaussian arithmetic again. A line through the origin of $(\mathbb{Z}/p)^2$ spanned by $(a, b)$ is kept by the quarter turn exactly when $(a, b)$ and $(-b, a)$ are proportional, which is when $a^2 + b^2 \equiv 0$ modulo $p$: the colour lies on the norm form’s zero set. Modulo 5 that happens on two lines, because $5 = (2+i)(2-i)$ splits and $-1$ has square roots; those two lines are the two prime ideals above five, and they are what the cyclic colourings of $p4$ sit over. Modulo 7 it happens nowhere, because seven stays prime in the Gaussian integers, and the plane of colours is the field of forty-nine elements, $\mathbb{Z}[i]/7$, with the quarter turn acting as multiplication by $i$. The census shows the consequence: $p4$ has seventy-five colourings with twenty-five colours, fifty of them on cycles, and forty-nine with forty-nine colours, every one on $7L$.

The colour groups #

The census computes each colour group directly, as the pattern’s group modulo the largest normal subgroup inside the colouring subgroup, and the figure lists them. On $pL$ every one has order $p^2$ times the order of the point group: twenty-five for $p1$, fifty for $p2$, $pm$, $pg$ and $cm$, a hundred for the rectangular and $p4$ groups, seventy-five, a hundred and fifty and three hundred for the hexagonal ones, two hundred for $p4m$ and $p4g$. At forty-nine the same formula holds with forty-nine in place of twenty-five.

The formula needs the point group to act faithfully on the colour plane: no rotation or mirror may act on $(\mathbb{Z}/p)^2$ as the identity. That is a fact about integer matrices that the census of finite groups proved in another context: a finite group of integer matrices survives reduction modulo three, and modulo any odd prime, with no two of its elements colliding. It fails modulo two, where the inversion $-1$ becomes the identity, which is part of why four colours produced a zoo of colour groups that no odd prime reproduces.

The colour groups at a prime were at most $p$ times six. At the square they reach $p^2$ times twelve for $p6m$, six hundred at twenty-five, and they are no longer metacyclic: the colour group of $p4m$ on $5L$ contains the dihedral group of order eight acting on a plane, which no affine group of a line contains. The mirror groups come back with colour groups that could not exist at a prime.

Thirty-one designs #

Two colourings that differ only in the origin, the axes or the scale of the description are the same design. The earlier essays made this precise as orbits under the affine normaliser, the changes of description that carry a group to itself, and counted ninety-six designs at four colours and fourteen at five.

At the square the designs separate cleanly into two kinds. On $pL$ the complements of any one group are all conjugate, so every colouring of a group on $pL$ is the same design described from a different origin, and each of the seventeen groups contributes exactly one. On cycles the designs number exactly what the prime gave: fourteen at twenty-five, fifteen at forty-nine. The census finds thirty-one and thirty-two, and the rule is the prime’s rule with seventeen added: thirteen, plus one when $p \equiv 1 \pmod 4$, plus two when $p \equiv 1 \pmod 3$, plus seventeen.

The match of the cyclic designs with the prime ones is not automatic. A design is an orbit of colourings under changes of description, and a change of description acts on cycles modulo $p^2$ rather than on lines modulo $p$, so it could in principle split one prime design into several at the square, or merge two. It does neither at twenty-five or forty-nine, consistent with each cycle lying over its line in exactly one way, which is the lifting argument above. That consistency is checked, not assumed: the census orbits the subgroups themselves.

What the census does not say #

Two squares only. The census runs at twenty-five and forty-nine; the argument covers every prime square from twenty-five up, and the design rule at 121 or 169 is a prediction, which the argument makes for the same reason it made the prime’s rule: every step uses only that $p$ is odd and prime to the point group’s order. The search at 121 would take hours rather than minutes, and has not been run.

Not $p^3$, and the reason is a proof. At $p^3$ colours a sublattice has quotient $\mathbb{Z}/p^3$ or $\mathbb{Z}/p^2 \times \mathbb{Z}/p$, and both lie over a line: the first reduces to one, and the second is $p$ times a sublattice of index $p$. A mirror group keeps no line modulo $p$, so it keeps neither. More generally its point group acts on the plane modulo $p$ with no invariant line, irreducibly, and a sublattice it keeps must then be either the whole lattice or inside $pL$; dividing by $p$ and repeating, the only sublattices of $p$-power index the five mirror groups keep are $p^k L$, at the even powers $p^{2k}$. They can be coloured with 25 and 625 colours and never with 5, 125 or 3,125. The census checks the lattice half of that at 125 and 625, where the mirror groups keep nothing and $25L$ respectively. Composite numbers of colours mixing two primes, thirty-five say, split into a colouring at each prime by the Chinese remainder theorem when the primes avoid the point group’s order, which is why ninety-six four-colour designs, at a prime that divides it, was the hard case and these are not.

What the pictures cannot show is a coloured pattern with twenty-five colours. A drawing would need twenty-five distinguishable inks and a motif repeated over at least a five-by-five block of cells, and the eye cannot verify from it that a mirror permutes the colours affinely. The figures draw the colour plane instead, where the action is legible, and the census decides every claim from the subgroups.

Who worked out the pieces #

Colour symmetry was developed by Shubnikov and Belov in the 1950s and classified for the plane by Wieting in 1982, whose tables count colour plane groups by number of colours; two colours, and a symmetry that swaps them is where the subject begins here. That colourings with a number of colours prime to the point group’s order are governed by invariant sublattices and their complements is standard group theory, Schur and Zassenhaus’s theorem on coprime extensions. The splitting of primes in the Gaussian integers is Fermat’s theorem on sums of two squares, the arithmetic the sublattices that stay square used for the lattice itself. What the census adds is the count at the two smallest prime squares, the return of the mirror groups through $pL$ with colour groups no prime allows, and the design rule with its seventeen.

What the census must refuse #

The refused claim is the natural extrapolation from the primes: that a group with no colouring at $p$ has none at $p^2$ either, as though the obstruction were a property of the group. It is a property of the line. The mirror groups’ obstruction at a prime is that a non-abelian point group cannot act on a line of colours by multiplication; at twenty-five colours there is a plane of colours available, and $p6m$, with none at five, has twenty-five.

Still open: nine colours, where three divides the point group #

Everything above rests on $p$ being prime to the point group’s order, which is what forces the point group to be kept whole and makes every complement conjugate. At nine colours neither holds for the groups with a three-fold axis. A colouring may then remove a three-fold rotation as well as translations, as three colours found at index three, and above a kept sublattice the extension need not split, so a colouring can carry a glide or screw-like translation the parent’s operations did not have. The plane $3L$ still exists and every group still keeps it, so the hexagonal mirror groups have nine-colourings on it; whether they have others, through subgroups that drop a rotation, and how the count of designs departs from thirteen plus one plus two plus seventeen at a prime that divides the point group, is the census here run at nine with the coprime shortcuts removed. It has not been run.