Four colours, five ways to permute them

A two-coloured pattern whose symmetries either keep the colours or swap them has one way of permuting its colours, the swap. Three colours, and why most patterns cannot have them moved to three and found that the colours can then be cycled or, as what a half-turn does to three colours showed, permuted by the whole symmetric group. The difference decided which of the seventeen plane groups could be three-coloured at all. Ten can be coloured cyclically in no way, and only the three four-fold groups refuse three colours altogether.

Four is the first number of colours with real variety in how they can be permuted. A group of motions acting transitively on four colours induces one of five permutation groups on them: the cyclic group of order four, the Klein four-group, the dihedral group of order eight that a square’s symmetries form, the rotation group of a tetrahedron and the full symmetric group. The first essay on three colours named the choice between the first two as the point where colour symmetry stops being one question. This essay makes the count, for every plane group and every one of the five.

A colouring is a subgroup of index four #

The object being counted needs a definition that does not depend on a picture. Take a pattern with symmetry group $G$ and colour its motifs in four colours so that every symmetry carries each colour class onto a colour class, and the colour classes are permuted transitively. The motifs of the colour carried by the motif at the origin are an orbit of a subgroup $H$, the operations that keep that colour, and $H$ has index four. Conversely a subgroup of index four colours the pattern by its four cosets. So the four-colourings of a pattern are its subgroups of index four. The group the colours are permuted by is the image of $G$ acting on those four cosets.

How many subgroups of index three counted subgroups of small index by counting the ways a group can act on a few points. A homomorphism from a presented group to the permutations of four points is a choice of permutation for each of the group’s generating operations that satisfies every relator, a finite search over the letters and relations of a group in four letters. Each subgroup of index four comes from exactly six transitive actions, one for each relabelling of the three colours other than the first. That essay reported the index-four totals: sixty-seven for $pmm$, five for $p6m$, four for each of $p3$, $p3m1$, $p31m$ and $p6$. Here each action is also asked what group its images generate.

The picture at the head of this essay is the census, 281 four-colourings across the seventeen groups. Its most striking feature is a wall between two halves. The twelve groups without a three-fold rotation use only the cyclic, Klein and dihedral groups. The five with one use only the tetrahedral groups $A_4$ and $S_4$, apart from a single Klein colouring of $p6m$. No group reaches across. The rest of this essay explains the three columns that can be predicted without the search, and then the wall.

Klein colourings are pairs of two-colourings #

A colouring whose colours are permuted by the Klein group is normal, since the Klein group acts on four points regularly, and the quotient $G/H$ is the Klein group itself, two independent swaps. Such a colouring is therefore two two-colourings laid over each other. Give each motif a pair of bits, the first from one two-colouring and the second from another, and the four pairs are the four colours. The Klein colourings of a group correspond exactly to pairs of independent two-colourings, counted up to the ways of choosing the pair.

That is a count with a closed form. The two-colourings of a group are the non-zero vectors of a space over the field of two elements, and the essay on three colours found that its dimension $r$ is read off the number of index-two subgroups, $2^r - 1$. A Klein colouring is a two-dimensional subspace of that space, and the number of those is

$$\binom{r}{2}_{\!2} = \frac{(2^r - 1)(2^r - 2)}{6} .$$

Every group lands on the curve. The groups with three two-colourings, a space of dimension two, have exactly one Klein colouring: $p1$, $pg$, $cm$, $pgg$, $p4$, $p4g$ and $p6m$. Those with seven two-colourings, dimension three, have seven: $p2$, $pm$, $pmg$, $cmm$ and $p4m$. $pmm$, with fifteen two-colourings and dimension four, the most of any plane group, has thirty-five. The groups with at most one two-colouring have none. The search found these numbers without being told the formula, and the formula predicts them without the search, so the agreement is a test of both.

For $p1$ the single Klein colouring is the one a reader would draw first. Colour each lattice point by the parity of its two coordinates. The subgroup is the lattice with every vector doubled. $p1$’s subgroups of index four are its sublattices of index four, and how many sublattices counts those as the sum of the divisors of four, seven. The quotient of a lattice by a sublattice of index four is either cyclic of order four or two independent swaps. A sublattice with the second quotient contains twice every vector, so it contains the doubled lattice, and having the same index it is the doubled lattice. That leaves six cyclic ones, which is what the next column reports.

Cyclic colourings need a factor of order four #

A cyclic four-colouring is also normal, with $G/H$ the cyclic group of order four, so it is a surjection of $G$ onto that group taken up to the group’s two automorphisms. A homomorphism to an abelian group factors through the abelianisation, the largest abelian quotient of $G$, and the number of surjections can be read off its invariant factors. A free factor $\mathbb{Z}$ contributes four homomorphisms to the cyclic group of order four, a factor $\mathbb{Z}_d$ contributes $\gcd(d, 4)$, and the non-surjective ones are those landing in the subgroup of order two.

The two routes agree in every row, and the seven groups that have any split into two kinds. $p1$, $pm$, $pg$ and $cm$ have a free factor in their abelianisation, a translation that survives the quotient, and a translation can cycle four colours like a stripe pattern of period four. $p1$ has six such stripes, one for each sublattice of index four with a cyclic quotient. $pgg$, $p4$ and $p4g$ have no free factor, but each has a factor $\mathbb{Z}_4$. In $p4$ it is the four-fold rotation. In $pgg$ it is a glide, whose square is a translation that the abelianisation does not kill. Every other group’s abelianisation is made of copies of $\mathbb{Z}_2$, or of odd factors, and cannot map onto a cyclic group of order four.

The square, from half-turns #

The largest column in the census is the dihedral one: 164 colourings whose colours are permuted as the four vertices of a square. None of these is normal. The subgroup of the colour at the origin is not the subgroup of the colour opposite it, and the dihedral group of order eight acting on four points has a stabiliser of order two that is not normal.

The obvious guess is that permuting four colours like the corners of a square needs a pattern with a square’s rotation. $p2$ has only half-turns, and it has twenty-four such colourings. The drawing shows how one of them arises. One translation leaves every colour where it is. The other cycles all four, a quarter turn of the square, performed by an operation of infinite order in the pattern that happens to have order four on the colours. The half-turn swaps two colours and fixes the other two, which is what a reflection across a square’s diagonal does to its corners. A quarter turn and a diagonal reflection generate the square’s whole group of eight, although no operation of $p2$ has order four. A colour group need not look like the pattern’s point group, and here it is larger than the point group in every sense that matters.

The dihedral colourings have a structure the definition does not show. The operations keeping one colour form a subgroup $H$, and in the square’s group the stabiliser of a corner is a single reflection. That reflection lies in a Klein subgroup of index two, the diagonal reflections and the half-turn. So $H$ sits inside a subgroup $K$ of index two in $G$, and has index two in $K$. Every dihedral colouring is a two-colouring of a two-colouring, a subgroup that is normal in the half it halves and not normal in the whole. That is the non-normal case the two ways down could not reach at index two, where every subgroup is normal.

The dihedral colourings are also where the count grows fastest with the number of mirrors. $pmm$ has thirty-two, $p2$, $cmm$ and $p4m$ twenty-four each. Each dihedral colouring is a two-colouring of a two-colouring. It halves the group, and then halves the half by a subgroup that is not normal in the whole, so a group rich in index-two subgroups is rich in these.

The wall, and the lattice modulo two #

The five groups with a three-fold rotation colour differently. $p3$ and $p6$ have four colourings each, all with colour group $A_4$, the rotation group of a tetrahedron. $p3m1$ and $p31m$ have four each, all with colour group $S_4$, the tetrahedron’s full symmetry group. $p6m$ has four of $S_4$ and its one Klein colouring. None has a cyclic or dihedral colouring, and no group without a three-fold rotation has a tetrahedral one. The second half is immediate, since $A_4$ and $S_4$ contain elements of order three and a pattern needs an operation whose image has order three. The first half needs a construction.

The construction is the one $p1$’s Klein colouring already used: colour each lattice point by its coordinates reduced modulo two. The four colours are the four cosets of the doubled lattice, and they form a plane over the field of two elements, four points in which every line has two. A translation adds its own vector modulo two and permutes the colours as the Klein group. A point operation acts on the four cosets through its integer matrix reduced modulo two, and it fixes the colour of the point it is centred on.

In the hexagonal lattice a three-fold rotation fixes the colour of its centre and cycles the other three. Translations and that rotation together generate the maps $x \mapsto Rx + t$ of the four-point plane, with $R$ one of the rotation’s three powers reduced modulo two, and that group has twelve elements. Twelve permutations of four things containing the Klein group and a three-cycle is $A_4$. The four colours are the vertices of a tetrahedron, and the three-fold rotation is a turn about the axis through one of them. The search found exactly this: $p3$’s four colourings are the four ways of choosing which lattice points count as the origin’s colour, one per coset.

The subgroup keeping one colour has a simple description. It contains every rotation of $p3$ about a point of that colour, and every translation by a doubled vector, and nothing else. It is $p3$ again on a lattice of index four. So every tetrahedral colouring keeps the whole point group and gives up translations, in the two ways down a purely klassengleiche descent, in which the colours are carried entirely by where a point sits in the lattice. $p6m$’s one Klein colouring is the opposite kind. Its subgroup is $p3$ on the same lattice, keeping every translation and giving up three quarters of the point group, and its two bits of colour are the two independent ways a hexagonal pattern can reverse, by a mirror and by a half-turn.

The reduction modulo two also says why $p6$ adds nothing to $p3$, which is the second refused claim below. $p6$ has a half-turn that $p3$ lacks, and a half-turn’s matrix is $-I$, which is the identity modulo two. It acts on the four colours as nothing at all, and $p6$’s six point operations reduce to $p3$’s three. $p6$’s colour group is the same $A_4$. A reflection is different. In the hexagonal lattice a mirror reduces modulo two to a matrix that swaps two of the three non-zero cosets, a transposition. It doubles the affine group to twenty-four elements, all of $S_4$, the group of every map $x \mapsto Rx + t$ with $R$ any invertible two-by-two matrix over the field of two elements. That is the isomorphism between $S_4$ and the affine group of the four-point plane, and $p3m1$ and $p31m$ realise it with a mirror. For the four-fold groups the same reduction leaves two operations, the identity and the exchange of the two axes, and with the translations they generate a group of order eight. That is the dihedral group again: the parity colouring of a four-fold pattern is one of its square colourings, not a Klein one.

This is the connection the census hides. Nothing about the hexagonal lattice looks tetrahedral. Its point groups are the symmetries of a hexagon, and the tetrahedron’s twelve rotations include rotations of order three about four different axes, where a plane pattern has rotations about one. The tetrahedron appears only after reduction modulo two, where the hexagon’s six-fold rotation loses its half-turn and becomes a three-cycle of three cosets, and the four cosets become four vertices. Five solids from one inequality derives the tetrahedron’s group from a sphere. Here the same group turns up as the colour group of a flat pattern, by arithmetic.

Two groups the colourings cannot tell apart #

A census this fine might be expected to identify each group by its row, and it does not. $cm$, $pgg$, $p4$ and $p4g$ share one row exactly: two cyclic colourings, one Klein, eight dihedral, eleven in all. $p2$, $cmm$ and $p4m$ share another. Rows can coincide for reasons that are no mystery. The Klein and cyclic columns depend only on the abelianisation, and $pgg$, $p4$ and $p4g$ all abelianise to $\mathbb{Z}_2 \oplus \mathbb{Z}_4$.

$p4$ and $p4g$ go further than sharing a row. They have three subgroups of index two each, none of index three, and eleven of index four, falling into seven conjugacy classes with three normal in both. Every count made so far, of two, three and four colours and of subgroups at every index up to four, fails to separate them. They are nonetheless different groups. The seventeen are pairwise non-isomorphic as abstract groups, which is Bieberbach’s theorem at work in the plane, and the seventeen are seventeen for that reason. Counting colourings measures a group through its small quotients, and two groups can agree on every small quotient and differ in how the quotients fit together. $p4g$ has glides where $p4$ has none, and no census of four colours sees a glide as such.

What the census counts, and what it does not #

Colourings are counted as subgroups of a fixed pattern. Two colourings that differ by a change of origin, or by an operation of the lattice’s affine normaliser, count as two here, as the 74 two-colourings did before seventy-four colourings became forty-six groups. The number of four-colour designs, identified up to the normaliser, is smaller and has not been computed. For the tetrahedral colourings the identification is easy to state: $p3$’s four colourings are carried to one another by translations, so they are one design.

The colour groups are abstract permutation groups. Two colourings with colour group $D_4$ can differ in which elements of the pattern’s group act as which symmetries of the square, and the census does not separate them. A finer classification would record the whole homomorphism, as the census of three-colourings by $S_3$ did.

Four is the last small case this method reaches by brute force. The search tries every assignment of permutations to the generating operations, at most $24^4$ tuples for a group with four of them. At five colours there are five transitive groups again, and at six there are sixteen, and the search grows as the sixth power of 720. The census is exact for four colours, and a larger count would need a different method.

Who counted them #

Colour symmetry began with two colours, in Heesch’s work around 1930 and Shubnikov’s on antisymmetry of 1951, and the forty-six two-colour plane groups were known by the 1950s. Colourings with more colours were classified in the 1960s and after, first as the colour groups of patterns in which every symmetry permutes the colours, and then with explicit counts for each number of colours. The four-colour plane groups sorted by the group acting on the colours are recorded in that literature. This census recomputes the subgroup count from presentations and sorts it, and does not reproduce the design count the literature gives.

What the census has to refuse #

The tests that carry the most weight are the three independent routes. The Klein counts are checked against the planes of the space of two-colourings, the cyclic counts against the abelianisation’s invariant factors, and the tetrahedral counts against the affine groups computed from matrices modulo two. None of the three shares code with the permutation search, and each agrees with it in every row. The first refused claim fails in $p2$, which has twenty-four square colourings and nothing of order four. The second fails because $-1$ is $1$ modulo two.

Still open: the designs, and where the tetrahedron goes in space #

The census counts colourings of a fixed pattern, and designs are fewer. Identifying colourings under the affine normaliser, as the two-colour census was reduced from seventy-four to forty-six, would give the number of distinct four-colour plane patterns for each colour group. The identification is already computed for index two, and the question is whether it carries to index four without change.

The reduction modulo two has a three-dimensional form that is more striking. A cubic lattice reduced modulo two has eight cosets, a three-dimensional space over the field of two elements. Its affine group has 1,344 elements, and a cubic space group’s three-fold rotations act on it. Which of those groups act on the eight colours as a group that is not already visible in the point group is the same calculation one dimension up, and it has not been made here.