Ninety-six four-colour designs

Four colours, five ways to permute them counted every four-colouring of every plane group. A four-colouring is a pattern whose symmetries permute four colours transitively, and it is determined by the subgroup of symmetries that keep the colour of one chosen motif. That subgroup has index four, and the essay found 281 of them across the seventeen groups. It sorted them by the group of permutations the pattern’s symmetries induce on the colours: 20 cyclic, 77 Klein, 164 square, 8 tetrahedral and 12 fully symmetric.

A count of subgroups is a count of descriptions, not of designs. Seventy-four colourings, forty-six groups made the same point at two colours. The seventy-four index-two subgroups of the seventeen fall into forty-six classes once colourings related by an affine map of the plane are identified, because a map carrying the pattern’s group onto itself carries each colouring to another that looks the same after the map. The four-colour essay ended by asking whether that identification carries to index four without change, and what the number of distinct four-colour designs is.

It carries, with one amendment, and the number is ninety-six. The amendment is conjugation by whole lattice vectors, which the two-colour identification never needed. The same computation run again at two and three colours gives forty-six and twenty-three, so one routine produces the known count at each number of colours.

A subgroup as a set of elements #

The earlier census found each four-colouring as a transitive action of the group on four colours. It searched every assignment of permutations to the group’s presentation generators that satisfies the relations. That describes a colouring by the images of three or four generators, and an affine map of the plane acts on the group, not on a presentation. So the first step is to rebuild each colouring as a set of elements.

Every element of a plane group is a pair: a matrix and a translation. The census works with the translations measured in twelfths of a cell, and reduces them modulo twelve whole cells. At that modulus every index-four subgroup is visible, and nothing smaller would do. The lattice’s translations act on the four colours through an abelian subgroup of the symmetric group on four letters, whose elements have orders dividing four or three. So every translation by twelve cells acts on the colours as the identity, and every index-four subgroup contains the translations by twelve times the lattice. Modulo them a plane group is a finite group of at most 1,728 elements, the point group’s order times 144.

Starting from the identity and multiplying by the generators, with their matrices and translations on one side and their permutations of the colours on the other, the census reaches every element of that finite group together with the permutation it induces. At every step it checks that an element reached two ways gets the same permutation. The subgroup is the set of elements that keep the first colour. That rebuilds all 281 subgroups, as many as the search found for each group.

Maps that carry the group to itself #

An affine map $x \mapsto Ax + a$ carries a plane group onto itself when conjugating every element by it gives another element of the group. Those maps are the ones that describe the same pattern twice, and applied to a colouring they redescribe it without changing it. The census tries every integer matrix $A$ of determinant $\pm 1$ with entries from $-2$ to $2$, and every translation $a$ by twelfths of a cell. It keeps the maps that carry every operation of the group to an operation of the group. Those maps act on the finite group by conjugation, $(M, t) \mapsto (AMA^{-1}, At + a - AMA^{-1}a)$, and so on its subgroups. Two colourings are the same design exactly when some product of such maps carries one subgroup to the other. The designs are therefore the orbits, and the census closes each orbit under repeated application, since the maps it tries are a generating set and not the whole normaliser.

For groups with an oblique lattice the normaliser is infinite. What matters is only its action on the finite group modulo twelve cells, which passes through a finite quotient, and small matrices generate that quotient. That is the plane’s version of what the normaliser only acts modulo two found for space groups. The closure then reaches everything.

Ninety-six #

The picture at the head of this essay is the result. The 281 four-colourings make ninety-six designs. Thirteen are colourings whose four colours are cycled, thirty-nine are Klein, where the colours are permuted in two independent pairs, and thirty-nine are dihedral, with the symmetries of a square acting on the four colours. Two are tetrahedral, both over three-fold groups, and three are fully symmetric.

The reductions differ a great deal from group to group. $p1$’s seven colourings, which are its seven sublattices of index four, fall into two designs. One is the square sublattice of doubled period, the other the six cyclic sublattices, all equivalent under a change of basis. $p2$’s thirty-one colourings fall into three designs. The oblique lattice has so many equivalent bases that a single dihedral design gathers twenty-four of them. At the other extreme, $cm$’s eleven colourings make seven designs. Its normaliser is small and does little identifying.

The colour groups are spread over the plane groups in a pattern that follows from what each colour group needs. The thirteen cyclic designs, where a symmetry cycles all four colours, come from only seven groups: $p1$, $pm$, $pg$, $cm$, $pgg$, $p4$ and $p4g$. A cyclic colouring needs a quotient of the group of order four that is cyclic, and the groups with a two-fold rotation acting as $-1$ on the lattice rarely have one. $p4$ and $p4g$ have it through the quarter-turn itself, which cycles four colours. The Klein designs, thirty-nine of them, come from every group except $p3$, $p3m1$, $p31m$ and $p6$, with a single one from $p6m$. A Klein colouring is a pair of independent two-colourings, so it needs a group with at least two, and the three-fold groups have almost none. The dihedral designs, also thirty-nine, belong to $p2$ and the rectangular and square groups, where a pair of perpendicular mirrors or a quarter-turn can act on four colours as the symmetries of a square act on its corners.

The tetrahedral and fully symmetric designs are the rarest and the most rigid. Each of the three-fold and six-fold groups has exactly one. $p3$ and $p6$ have a tetrahedral design and $p3m1$, $p31m$ and $p6m$ a fully symmetric one. All five are the same construction. The hexagonal lattice reduced modulo two has four cosets, a plane over the field of two elements, and the three-fold rotation permutes three of them while fixing the fourth. Colouring each point of the pattern by the coset of its cell’s position gives four colours. The three-fold rotations permute them as the rotations of a tetrahedron, and mirrors, where the group has them, add the reflections. That is why a three-fold group’s only four-colouring with a non-abelian colour group is this one. It is the lattice modulo two made visible, and the colour group is the affine group of that plane over two elements.

The picture sets each group’s designs side by side as blocks, each as wide as the number of colourings it gathers. $pmm$’s sixty-seven colourings make thirteen designs. The largest gathers sixteen dihedral colourings, related by the maps $pmm$’s normaliser contains, among them translations by half a cell and the exchange of the two axes. $p4m$’s thirty-one make thirteen, in orbits of one, two and four. What the blocks show is that the multiplicity of a count of subgroups is almost entirely a count of ways to describe one pattern. The ratio of colourings to designs runs from about one and a half for $cm$ and $p4g$ to ten for $p2$.

Why some groups compress more than others #

How many colourings a design gathers is the size of an orbit, and orbits are large where the normaliser is large. That is the same arithmetic that makes one crystal sixteen coordinate lists: a large normaliser means many descriptions of one object. $p2$ compresses most because its normaliser is the largest. Its point group, the half-turn, commutes with every integer matrix, so every change of basis of the oblique lattice carries $p2$ to itself, and so do the translations by half a cell. That normaliser is infinite, and on the thirty-one colourings it acts through a finite quotient large enough to leave only three orbits. $p1$ is the same story with the half-turns removed. At the other end, $cm$ and $p4g$ have small normalisers. Their mirrors and glides pin the axes, and only a few maps keep the pattern’s group, so most of their colourings stand alone as designs.

The identification is also blind to the metric, and that is a feature of affine equivalence worth stating. A $pmm$ pattern on a rectangle and one on a square have the same group as far as the classification is concerned, since an affine map stretches one into the other. Their four-colour designs are therefore the same designs, although the square pattern has additional rigid symmetries a coloured version might or might not keep. Counting the designs of $pmm$ patterns that happen to be square is a different question, about colourings of $p4m$ that break the quarter-turn, and it is answered by $p4m$’s own row.

Two and three colours by the same route #

A new routine is worth trusting only if it reproduces what is already known, and this one can be run at other indices without change. At index two the seventeen groups have seventy-four subgroups, and the routine finds forty-six designs. That is the number seventy-four colourings, forty-six groups reached by a different computation, on homomorphisms to the group of two elements. At index three there are eighty-two subgroups, and the routine finds twenty-three designs. The square groups $p4$, $p4m$ and $p4g$ have none, as three colours, and why most cannot have them explained, and the half-turn groups that do have them permute the colours only as a half-turn allows. Forty-six, twenty-three and ninety-six are the counts of two-, three- and four-colour plane groups given in the classical tables of coloured plane patterns. The routine meets all three.

A neighbouring cell is the same pattern #

The two-colour identification used maps whose translations were at most half a cell. At four colours that is not enough, and the census found out how.

The first run of the census used only maps with translations less than a whole cell and found 101 designs. Five too many, in $cm$, $p31m$, $p6$ and $p6m$. The missing identification is conjugation by a lattice translation. That translation is itself an element of the group, and conjugating by it changes an element’s translation by $\lambda - M\lambda$, a whole lattice vector. Modulo one cell that is nothing. Modulo twelve cells, where the census keeps its subgroups, it is a different element, and it can carry a subgroup to a different subgroup. But the colouring is the same pattern, the one the first subgroup describes, read from a motif in the next cell. Adding the two basis translations to the generating maps merges the five pairs. At index two the problem never arises, because every index-two subgroup contains twice the lattice and conjugation by a lattice vector moves nothing modulo two cells.

A colouring’s subgroup depends on which motif is chosen to anchor it, and choosing a motif one cell over is not a new design.

$p6$ shows the effect most clearly. Its four colourings are the four cosets of the doubled lattice just described, each subgroup keeping one coset’s colour. The rotations and the translations by fractions of a cell all fix the origin’s cell modulo two, so they keep the coset containing the origin where it is, and they permute the other three. Without lattice conjugation the census therefore found two designs, one subgroup alone and three together. But the coset containing the origin has no special status in the pattern. It is simply the colour of the motif chosen as reference. A translation by one cell carries the origin into another coset and the reference colour with it, and with that conjugation included the four subgroups are one design, as they must be. $cm$ lost two designs the same way, and $p31m$ and $p6m$ one each.

The two-colour count was protected from this by its modulus, and the four-colour count must be protected on purpose.

What the census does and does not say #

The designs are counted up to affine maps. Two colourings are the same design here when an affine map of the plane carries one to the other, which can stretch and shear as well as move rigidly. That is the equivalence under which the classical counts are made. A count up to rigid motions only, distinguishing a colouring from its sheared image when the lattice allows a shear, would give more.

The colours are unlabelled. A colouring is identified with its subgroup, which forgets which colour is which. Two colourings that differ by renaming the colours are one design.

The normaliser is searched, not derived. The maps with entries up to two and translations by twelfths generate everything needed. Evidence of that is that the counts at two and three colours come out at the known values and that every orbit is closed under the maps found. A missing generator could only split a design into two, never merge two, so the count of ninety-six cannot be too small for want of a map.

No design is drawn. Every figure here is a count or a table, and none shows a coloured pattern. A drawing of each of the ninety-six would need a motif and a choice of colours for every coset, and it would show one description of each design while suggesting that the description is the design. The subgroups are exact objects, and the census identifies them exactly. What a reader cannot get from the tables is how different two designs over the same group look, and for that the earlier essays’ drawings of single colourings are the better guide. Two colours, and a symmetry that swaps them shows how much a colouring can change the look of a pattern whose group is unchanged.

Who worked out the pieces #

Two-colour plane patterns were enumerated by H. J. Woods in the 1930s, in a study of textile design, and again by Belov’s school in the 1950s as the black-and-white groups of crystallography. Colour groups with more colours followed through the 1960s and 1970s. The counts for three, four and more colours were tabulated in Thomas Wieting’s The Mathematical Theory of Chromatic Plane Ornaments of 1982, which is where forty-six, twenty-three and ninety-six appear side by side. Describing a colouring as a subgroup of the pattern’s group, and colourings up to equivalence as its orbits under the normaliser, is the standard reduction of colour symmetry to group theory.

What the census must refuse #

The second test carries the essay. A routine that reproduced ninety-six by accident would be unlikely also to reproduce forty-six and twenty-three, which it reaches by the same code at different indices. The refusal records the first run’s mistake as a test. Without conjugation by lattice vectors the count must come out higher, and it does, at 101.

Still open: the colourings of space #

The same construction runs in space, where four colours, five ways to permute them pointed at the cubic lattice reduced modulo two. Its eight cosets form a three-dimensional space over two elements, and the affine group of that space has 1,344 elements. The space groups’ index-four and index-eight subgroups, modulo twelve times their lattices, are finite objects of the same kind as here. The finite groups are larger, up to eighty-three thousand elements for the cubic groups, and the normaliser search would need three-by-three matrices. The construction would give the number of four-colour designs of each space group, sorted by colour group as the plane’s ninety-six are sorted here. It has not been computed.