Five colours, seven colours, and the primes that split

Ninety-six four-colour designs finished the count that the colour essays had been building towards. The seventeen plane groups have 281 four-colourings, the colours are permuted by five different groups, and the colourings make ninety-six designs once two descriptions of one pattern are identified. Each step up in the number of colours had been harder than the last. Two colours gave seventy-four colourings and forty-six designs, three gave eighty-two and twenty-three, and four needed a new way of identifying descriptions before its count would come out right.

Five colours look as though they should be worse again. The symmetric group on five letters has 120 elements, against twenty-four on four, and five different groups can permute five things transitively, among them the alternating and symmetric groups on all five. In fact five colours are much simpler. The seventeen groups have 104 five-colourings, the colours are permuted in only three ways, and the colourings make fourteen designs. Ten of the seventeen groups have any. And the simplicity is not special to five. From five upwards every prime number of colours behaves the same way, and which groups can be coloured is decided by a question about the prime itself: whether it is a sum of two squares, and whether it leaves remainder one on division by three.

A number of colours the point group cannot see #

A colouring of a pattern with $n$ colours, in the sense of these essays, is one in which every symmetry of the pattern permutes the colours and some symmetry carries any colour to any other. It is determined by the subgroup $H$ of symmetries that keep the colour of one chosen motif, and that subgroup has index $n$ in the plane group $G$. Counting colourings is counting subgroups of index $n$.

The index of $H$ splits into two factors. One is how much of the point group $H$ loses, the index of its point group $P_H$ in $P$. The other is how much of the lattice it loses, the index of its translations in the lattice $L$:

$$[G : H] = [P : P_H]\,[L : L \cap H].$$

When the index is a prime $p$, one factor is $p$ and the other is one. The point groups of the seventeen have orders 1, 2, 3, 4, 6, 8 and 12, and a prime of five or more divides none of them. So at a prime $p \ge 5$ the subgroup keeps the whole point group, and it loses exactly a sublattice of index $p$. Every rotation and every mirror direction of the pattern survives in $H$, displaced perhaps, and only the translations are thinned.

That is the whole difference from two, three and four colours. At two colours a mirror can swap the colours while every translation keeps them, which is how a chessboard differs from a grid of identical squares. At three colours a third turn can cycle them, and ten of the seventeen have no three-colouring at all because a half turn cannot; dropping the demand that the colours be cycled changes that answer completely. Those colourings come from the point-group factor, and they are most of what made the small counts rich. From five colours on that factor is gone.

The sublattice $L' = L \cap H$ has to be kept by every rotation and mirror of the point group, because $H$ contains an operation with each of those linear parts and conjugation by an element of $H$ keeps $H$’s own translations. And it contains $pL$, as every sublattice of index $p$ does. So $L'$ is a line through the origin in the lattice read modulo $p$, a plane over the field of $p$ elements with $p + 1$ lines in it, which is why the lattice has $p + 1$ sublattices of index $p$, as counting the ways to thin a lattice found from the divisor sum, and the line has to be one the point group keeps.

Which lines a rotation keeps #

The question is now about two-by-two integer matrices read modulo a prime. A matrix keeps a line exactly when the line is spanned by an eigenvector, so the lines the point group keeps are its common eigenlines over the field of $p$ elements.

For $p1$ and $p2$ every line is kept, since the only matrices are the identity and its negative. Those two groups have $p + 1$ invariant sublattices at every prime. For the rectangular and centred groups the mirrors have eigenvalues $1$ and $-1$, and a mirror keeps exactly its two eigenlines, along the mirror and across it. Every one of $pm$, $pg$, $cm$, $pmm$, $pmg$, $pgg$ and $cmm$ therefore has two invariant sublattices of index $p$ at every prime $p \ge 5$.

The rotations are where the prime starts to matter. A quarter turn has characteristic polynomial $x^2 + 1$, and it has an eigenvector modulo $p$ exactly when $-1$ is a square modulo $p$. Fermat’s theorem on primes, the one that decides which sublattices stay square, says that happens exactly when $p$ leaves remainder one on division by four, equivalently when $p$ is a sum of two squares. Five is $2^2 + 1^2$, and the picture shows the quarter turn keeping two lines modulo five while moving the other four in pairs. Seven is not a sum of two squares, and modulo seven the quarter turn keeps no line at all. Its four orbits are pairs. The two kept lines modulo five are the two square sublattices of index five, spanned by $(2, 1)$ and $(-1, 2)$ and by its mirror image, which are the Gaussian integers divisible by $2 + i$ and by $2 - i$. The five-colourings of a pattern with quarter turns are colourings by cosets of those sublattices, and at seven, eleven and nineteen colours there are none.

A third turn has characteristic polynomial $x^2 + x + 1$, whose roots modulo $p$ are the primitive cube roots of one, and they exist exactly when $p$ leaves remainder one on division by three. A sixth turn is the negative of a third turn and keeps the same lines. So $p3$ and $p6$ have invariant sublattices of index $p$ at 7, 13 and 19 and not at 5, 11 or 17. The kept lines are the hexagonal sublattices of index $p$, multiples of one of the two Eisenstein primes into which $p$ splits, $7 = (3 + \omega)(3 + \bar\omega)$ with $\omega$ a primitive cube root of one.

Mirrors undo all of it for the five groups that combine them with these rotations. A mirror exchanges the two eigenlines of a quarter turn or a third turn, because it conjugates the rotation into its inverse and so swaps eigenvalues $\lambda$ and $1/\lambda$. Neither line is kept by both. $p4m$, $p4g$, $p3m1$, $p31m$ and $p6m$ have no colouring with any prime number of colours from five upwards. Their rotation subgroups have such colourings when the prime splits, and the mirror takes every one of them away.

The colours are permuted by multiplying #

Once the sublattice is chosen, the colouring is a choice of where each operation of the point group sits relative to it. The group $G/L'$ is built from the point group and the cyclic group $L/L'$ of order $p$, and because $p$ shares no factor with the point group’s order, the theorem of Schur and Zassenhaus says it splits and that its subgroups complementary to $L/L'$ are all conjugate. So there is exactly one colouring per invariant line when the point group acts trivially on $L/L'$, and then $H$ is normal and the colours are simply cycled by translations. There are $p$ colourings per line when it acts non-trivially, one for each position of the motif that the rotations are centred on.

Number the colours by the elements of $L/L'$, which is the integers modulo $p$. A translation adds a constant to every colour. A rotation about the centre of a colour-0 motif fixes colour 0 and acts on $L/L'$ by its eigenvalue on the quotient, so it multiplies every colour by a fixed number $a$. Every colour group at a prime $p \ge 5$ is a group of maps $c \mapsto ac + b$, with $b$ any colour and $a$ running through a cyclic group whose order $m$ is the order of the point group’s action on $L/L'$. That order is one, two, three, four or six, so the colour group has $p$, $2p$, $3p$, $4p$ or $6p$ elements. The figure shows the multipliers: a quarter turn multiplies five colours by 3, cycling 1, 3, 4 and 2 and keeping 0; a third turn multiplies seven colours by 2, in two cycles of three; a sixth turn multiplies them by 3, a single cycle of six; a half turn multiplies by $-1$ and exchanges colours in pairs.

One consequence can be stated without the algebra. In a pattern coloured with a prime number of colours from five up, every rotation either keeps all the colours or keeps exactly one of them, since a map $c \mapsto ac + b$ with $a \ne 1$ has exactly one fixed point. A rotation that kept two colours and moved the rest, which is perfectly possible with four colours, cannot occur.

This is also why the large permutation groups never appear. Galois showed that a transitive group of prime degree that is built up from cyclic pieces is a group of maps $c \mapsto ac + b$, and Burnside that every other transitive group of prime degree moves pairs of points onto any pairs. A plane group is built up from cyclic pieces, so its colour groups can only be the first kind. At five colours that leaves the cyclic group of order five, the dihedral group of order ten and the group of order twenty, three of the five transitive groups on five points. The alternating and symmetric groups, sixty and 120 elements, are out of reach of any plane pattern.

The census, and two checks on it #

The argument predicts every count. The search does not use the argument. For each group and each prime it works in the finite group $G/pL$, with translations held as integers in twelfths of a cell modulo $12p$. It finds every line of the lattice modulo $p$ that the whole group keeps, and over each line every subgroup of index $p$, by choosing a translate of each point-group generating operation and closing. The one fact it borrows is that a subgroup of index $p$ meets the lattice in index $p$, and that is checked independently at five colours.

The picture at the head of this essay is the table. $p1$ has $p + 1$ colourings, one for each sublattice of index $p$, all by translations alone. $p2$ has $p(p + 1)$, with the half turn multiplying colours by $-1$ and the colour group dihedral. $pm$, $pg$ and $cm$ have $p + 1$ each: one colouring on the sublattice the mirror acts trivially across, which is normal and cyclic, and $p$ on the other, which are dihedral. The four groups with two mirror directions have $2p$ each, all dihedral. $p4$ has $2p$ when $p$ is a sum of two squares, with colour group of order $4p$, and $p3$ and $p6$ have $2p$ each when $p$ leaves remainder one on division by three, with colour groups of order $3p$ and $6p$. The totals are 104 at five colours, 172 at seven, 268 at eleven and 420 at thirteen, where for the first time every rotation subgroup has colourings at once.

The first check is the count at five colours by a method that shares nothing with the argument. Four colours, five ways to permute them found its colourings as transitive actions on four points: every assignment of permutations to a group’s presentation generators that satisfies its relations and moves every colour to every other. Run on five points, the same search tries up to $120^4$ assignments for each group and finds 104 subgroups of index five, group by group the counts in the table, with the same number of normal ones. The permutation search knows nothing of lattices, eigenvectors or remainders. At seven colours it would have to try up to $5040^4$ assignments, and the search in $G/pL$ replaces it.

The second check is the argument itself, which the search was not given and which it reproduces for all seventeen groups at all four primes, colour group by colour group.

Five colours on a square pattern #

The figure draws one of $p4$’s ten five-colourings. Each square of a square pattern gets the colour $x + 3y$ modulo five. The squares of colour 0 form a square lattice of index five, spanned by $(2, 1)$ and $(-1, 2)$, tilted against the pattern at the angle whose tangent is one half, and the other colours are its four translates. A quarter turn about the centre of a colour-0 square sends $(x, y)$ to $(-y, x)$, and $-y + 3x$ is three times $x + 3y$ modulo five, so the turn multiplies every colour by 3 and keeps colour 0. The shading pairs the colours that a half turn exchanges, 1 with 4 and 2 with 3, because a half turn multiplies by $-1$. The same pattern with seven colours is impossible: there is no way to paint the squares of a square pattern in seven colours so that every quarter turn permutes them, because seven is not a sum of two squares and no tilted square sublattice of index seven exists.

Fourteen designs, and a rule for every prime #

A count of subgroups counts descriptions, and the earlier essays identified two colourings when an affine map carrying the pattern’s group to itself carries one to the other, the maps that describe the same pattern twice. The same routine, run modulo $p$ times the lattice, gives the designs.

The designs follow from the lines. $p1$’s $p + 1$ colourings are one design, because changes of basis of the lattice permute the lines of the lattice modulo $p$ transitively. $p2$’s are also one, since the same changes of basis move the lines, and conjugating by translations of the lattice moves the $p$ colourings over each line into one another. $pm$, $pg$ and $cm$ have two designs each, the normal one and the dihedral one, which no map can exchange because one has a mirror that keeps every colour and the other does not. $pmm$, $pgg$ and $cmm$ have one each, since exchanging the two axes carries one mirror’s line to the other’s. $pmg$ has two, because its glides run in one direction only and the axes cannot be exchanged. That is thirteen, at every prime. $p4$ adds one when $p$ is a sum of two squares, since a mirror in its normaliser exchanges its two square sublattices, a map outside the group that still carries it to itself, of the kind the normaliser is not a function of the group studies. $p3$ and $p6$ add one each when $p$ leaves remainder one on division by three.

So the number of designs with a prime number $p \ge 5$ of colours is thirteen, plus one when $p \equiv 1 \pmod 4$, plus two when $p \equiv 1 \pmod 3$. That is fourteen at five colours, fifteen at seven, thirteen at eleven, sixteen at thirteen, fourteen at seventeen and fifteen at nineteen. Those are the counts of colour plane groups of those indices in the classical tables, compiled by Wieting and by Grünbaum and Shephard: 14, 15, 13, 16, 14 and 15. The rule reproduces every prime entry from the one argument, and the census reproduces it group by group.

Read against the sequence, the rule also says why the small cases looked so different. The table runs 46, 23, 96, 14, 90, 15 for two to seven colours, and the composite numbers and the primes two and three are large because the point group can absorb part of the index. At a prime it cannot, and the count drops to a number between thirteen and sixteen and stays there for ever.

What the census does not say #

Prime numbers only. At six colours the index can split as two from the point group and three from the lattice, or the other way round, and the classical count of ninety is made of both. At twenty-five colours the lattice can lose an index-25 sublattice that is not a line modulo five, and the colour group can be larger than any $c \mapsto ac + b$. Neither is computed here.

Unlabelled colours, affine equivalence. As in the earlier essays a colouring is its subgroup, so renaming the colours changes nothing, and two colourings related by any affine map carrying the group to itself, including stretches and shears, are one design. Counted up to rigid motions only, there would be more.

The lines are about the lattice, not the motif. A colouring is a partition of the pattern’s motifs, and the figures draw it on squares. A pattern whose motif sits on a rotation centre has fewer motifs per cell than the general position, and the same subgroup colours it with the same rule. Nothing here depends on the motif’s shape, which is the sense in which the count is a count of colour groups and not of pictures.

The mirror groups have no prime colourings from five up, and that is not an artefact of the definition. It is tempting to read it as “colourings that break the mirrors were not counted”. They were: a subgroup that dropped the mirrors would lose a factor of two from the point group, and its index would be even. At a prime index every colouring keeps every mirror direction, and the mirrors leave no line to colour by.

Who worked out the pieces #

Fermat stated in 1640 that an odd prime is a sum of two squares exactly when it leaves remainder one on division by four, and Euler proved it. That the solvable transitive groups of prime degree are groups of maps $c \mapsto ac + b$ is a theorem in Galois’s memoir of 1831, and Burnside proved early in the twentieth century that every other transitive group of prime degree is doubly transitive. The splitting of a group whose normal subgroup and quotient have coprime orders is the Schur–Zassenhaus theorem. Colour groups of the plane with many colours were tabulated by Wieting in 1982, and the counts by index appear in Grünbaum and Shephard’s Tilings and Patterns. The census here derives the prime entries rather than quoting them.

What the census must refuse #

The first refusal is the one a reader is most likely to make. $p4$ has ten five-colourings and $p4m$ contains $p4$, so it looks as though $p4m$ should have some. It has none, and the search confirms it at every prime, because a subgroup of $p4m$ of prime index must keep the mirrors, and the mirrors exchange the only two lines a quarter turn keeps. The second refusal is Galois’s theorem made concrete. Over all four primes and all seventeen groups no colour group has more than $6p$ elements.

Still open: a prime squared #

The argument used one fact about the prime, that it divides no point-group order, and one structure, the lines of a plane over a field. At $p^2$ colours the second gives way. A subgroup of index 25 can meet the lattice in $5L$ itself, which is not a line but the whole plane modulo five, and then the colours are the 25 points of that plane and the colour group can include the point group acting on it by matrices, not just by multiplication. The square groups would then have colourings at every prime, through $pL$, and not only when the prime splits. Whether the count of designs at $p^2$ follows a rule as clean as thirteen plus one plus two, and whether the mirror groups, absent at every prime, return at its square, is the computation the table’s composite entries point to next.