What a half-turn does to three colours

Three colours, and why most patterns cannot have them counts the three-colourings of the plane groups and finds twenty-six of them, in seven groups, with ten of the seventeen admitting none. The argument for the ten is one line: a half-turn has order two, a cyclic permutation of three colours has order three, and two does not divide three — so a half-turn must preserve every colour, and a group containing one has no three-colouring.

That argument is correct and it contains a word doing more work than it looks: cyclically.

A three-colouring is an assignment of colours such that every operation of the group permutes them consistently — a homomorphism into the symmetric group on three letters. The cyclic case is the one where the image lands inside the three-cycles. It need not. S₃ also contains transpositions, and a transposition has order two, which is exactly the order a half-turn needs.

A half-turn can permute three colours: it swaps two of them and fixes the third.

What changes when the word is dropped #

Enumerating homomorphisms into the whole of S₃, rather than onto ℤ₃, is the same computation with a larger target. A colouring must still use all three colours, which means the image has to be transitive on them, and the transitive subgroups of S₃ are two: the three-cycles, and S₃ itself. So the enumeration allows both and sorts the results afterwards.

The quotient it runs over changes too. A homomorphism into a group whose order divides six kills the translations by three, so the finite group to search is G/3Λ — nine translation classes rather than the four the two-colour count uses.

One hundred and sixty-four colourings, and twenty-five designs. Of the seventeen groups, only p4, p4m and p4g admit none at all.

So the ten groups that “cannot have three colours” have three colourings each or more; what they cannot have is a cyclic one. pmm has twelve. p2 has twenty-four. In every one of them the half-turn is doing exactly what the first rung says it cannot: permuting the colours, by swapping two.

The cyclic count comes out the same #

A count that revises an earlier one has to reproduce it, and this one does.

Filtering the hundred and sixty-four by whether the image is cyclic gives twenty-six, in seven groups — p1, pm, pg, cm, p3, p31m and p6. Those are the numbers and the groups the first rung obtains, and the two computations share no step: that one enumerates subgroups of index three with cyclic quotient, this one enumerates homomorphisms into a symmetric group and filters afterwards by what the image turned out to be.

That agreement is worth more than a check on the code. It says the two ways of describing a colour symmetry — as a subgroup of the colour-preserving operations, or as a homomorphism to the colour permutations — really are the same description, and it locates exactly where the earlier count was narrower: not in its arithmetic, in its target group.

Which groups refuse, and why it is the same line twice #

Three groups admit no three-colouring, and they are the four-fold ones.

A four-fold rotation has order four, so its image is a permutation whose order divides four. The symmetric group on three letters has elements of order one, two and three and none of order four, so the rotation goes to something of order one or two. What that generates, together with the rest, cannot be transitive on three letters — and a colouring whose image is not transitive is not using all three colours.

Set beside the two-colour case, the symmetry is exact. p3 has no two-colouring because a three-fold rotation must map to an element of order dividing three in S₂, and S₂ has none but the identity. p4 has no three-colouring because a four-fold rotation must map to an element of order dividing four in S₃, and the ones available are too small.

Both refusals are the same sentence with the numbers exchanged, and neither group is exceptional in any other way. It is a coincidence of small numbers rather than a fact about those patterns — which is why the two lists of refusing groups are disjoint and why nothing about p3 predicts anything about p4.

It is worth noticing what does not refuse. p6 and p6m contain a six-fold rotation, whose order does not divide anything in S₃ either — six is not the order of any element there, since the largest is three. But six-fold rotations are not fatal, because a rotation of order six may map to an element of order two or three and still leave the image transitive: the six-fold goes to a transposition or a three-cycle, and what the rest of the group supplies finishes the job. The four-fold groups fail where the six-fold ones do not, and the difference is that four has no useful divisor in S₃ while six has two. An order that fails to divide is not the obstruction; an image with nowhere to go is, and the two coincide only when the rotation is the group’s whole supply of non-translations.

Colourings against designs #

A homomorphism is a description and not a pattern, and the gap between the two counts is the same one seventy-four colourings, forty-six groups is about.

Two homomorphisms give the same coloured design when a change of description carries one to the other, and with three colours there are two kinds of change rather than one. A normaliser element moves the origin or the axes — that is the change the two-colour count already quotients by. And relabelling the colours conjugates every permutation in the image, which is a change with no counterpart at two colours: swapping the two colours of a two-colouring leaves its homomorphism onto ℤ₂ exactly as it was, while renaming three colours genuinely produces a different homomorphism describing the same picture.

The orbits are large. p2’s twenty-four colourings are one design; p3m1’s twenty-four are three. That the collapse is so severe is the point: a count of homomorphisms measures the description and a count of orbits measures the pattern, and at three colours the ratio between them is six or eight rather than the two-colour case’s typical two or four — because the colour relabelling alone contributes a factor of up to six.

What the colouring does to the lattice #

There is a second thing a colouring can do besides permuting colours, and the earlier rung splits its twenty-six by it: a colouring either leaves every translation’s colour alone, in which case the coloured pattern repeats on the same lattice as the uncoloured one, or it does not, in which case its lattice is three times larger and the picture has a cell nobody drew.

Over the whole hundred and sixty-four, twenty-two keep the lattice and a hundred and forty-two enlarge it. The split is far more lopsided than at two colours, and the reason is arithmetic rather than aesthetic: keeping the lattice means the whole colour permutation has to be carried by the point group, and a point group of order two has very little to give a target of order six.

p2 shows it at its starkest. All twenty-four of its three-colourings enlarge the lattice, because the only non-translation p2 has is the half-turn, and a half-turn alone generates a group of order two which cannot be transitive on three colours. Something in the translations has to move the colours, so the coloured cell is three times the plain one. A three-coloured p2 pattern is always a pattern whose colours repeat on a bigger cell than its shapes do, and that is forced rather than chosen.

p6m is the opposite case and is the informative one. Six of its twelve colourings keep the lattice — its point group is of order twelve and has plenty to spare — and six do not, so the same group offers both kinds. A reader looking at a three-coloured hexagonal design cannot tell from the shapes which kind it is, and the difference is exactly whether the colours repeat on the cell or on three of them.

That split is the same distinction the two ways down draws for subgroups in general: a subgroup either thins the lattice or reduces the point group, and a colour subgroup is a subgroup like any other. What is new here is the proportion, and it is a fact about the target rather than about the plane — going to a larger colour group makes it harder for a point group to carry the whole permutation, so more of the work falls to the translations.

Why the transitive subgroups are the thing to enumerate #

One decision in the computation is worth defending, because getting it wrong is the easiest way to produce a number that means nothing.

A colouring must use all its colours. If it did not — if a “three-colouring” gave every copy of the motif one of two colours and never the third — it would be a two-colouring with a spare crayon, and counting it would double-count things the two-colour census already has. The condition that makes a homomorphism a genuine k-colouring is that its image is transitive on the k colours, which is exactly the condition that every colour is reachable from every other by some operation of the group.

At two colours that condition is invisible, because the only non-trivial subgroup of S₂ is S₂ and any surjection is transitive. At three it does real work: S₃ has a subgroup of order two, generated by a transposition, and a homomorphism onto that fixes one colour and swaps the other two — which is a two-colouring of two-thirds of the pattern and not a three-colouring at all. Those are discarded here, and there are many of them.

So “three-colouring” is not “homomorphism to S₃” but “homomorphism to S₃ with transitive image”, and the two differ by a large factor. The transitive subgroups of S₃ are the three-cycles and S₃ itself; the intransitive ones are the trivial subgroup and the three copies of S₂. It is the sort of condition that is obvious once written and easy to omit, and omitting it is how a colour census comes out with a number nobody else can reproduce.

At larger k the same condition is what keeps the problem interesting: the transitive subgroups of S₄ are five up to conjugacy, of S₅ five, and each kind of image gives a genuinely different kind of colouring. The classification of colourings is really a classification of transitive group actions, and the plane groups are only the source of the homomorphisms.

What a number like twenty-five is worth #

A count of coloured groups is meaningless without its equivalence, and this is the essay’s one methodological point.

Twenty-five is the number of orbits under: the affine normaliser of the group, searched over integer matrices with entries up to a stated width and translations on a stated grid; together with the six relabellings of the colours. Change any of those and the number changes. Count homomorphisms instead and it is a hundred and sixty-four. Count only the cyclic ones and it is twenty-six as colourings and nine as designs. Restrict the normaliser to isometries rather than affine maps and it would be larger again.

None of those is wrong. They are answers to different questions, and a number quoted without saying which question it answers cannot be compared with another number quoted the same way. That is precisely what the seventy-four against forty-six taught at two colours, arriving here with more room to go wrong because there are more equivalences in play.

Where this sits among the collection’s other counts #

Three counts of coloured plane groups now exist here and it is worth saying plainly what each one answers, because they are easy to mistake for competing answers to one question.

Two colours and a swap counts two-colourings as homomorphisms onto ℤ₂: seventy-four, with p3 the only refusal. Seventy-four colourings, forty-six groups reduces those by the affine normaliser to forty-six designs. Three colours, and why most patterns cannot have them counts cyclic three-colourings as index-three subgroups: twenty-six, in seven groups. This essay counts three-colourings without the cyclic restriction: a hundred and sixty-four, twenty-five designs, three refusals.

They agree wherever they overlap, and the overlap is checked rather than assumed — the twenty-six is recomputed here from a different definition and comes out the same, in the same seven groups.

What none of them counts is the number of coloured patterns a designer could draw. A colour group is a symmetry, and a pattern realising it needs a motif placed where the colouring is consistent — the hazard two-colours-and-a-swap records, where a motif sitting on a colour-changing mirror would have to be two colours at once. So every count here is an upper bound on designs and a description of symmetries.

There is one further count in the collection that looks related and is not. Every colour count at once enumerates the ways of distributing colours over the sites of a structure — a combinatorial question about compositions, with no requirement that any symmetry permute the colours at all. That is colouring in the ordinary sense; this is colour symmetry, where the permutation is part of the group. The two share a word and nothing else, which is the kind of collision the claim registry exists to keep apart within a single collection as well as between sites.

Set against the ordinary subgroup counts the picture is tidier still. A colour symmetry is a subgroup with a labelled quotient, so a colour census is a subgroup census read with extra structure — which is why how many subgroups of index three is the same computation with the labels thrown away, and why its numbers are the ones the cyclic column of this one reproduces.

What this does not do #

It is three colours, not k. The same machinery runs at any k — the quotient becomes G/kΛ and the target the symmetric group on k letters — and the search grows quickly, since the number of assignments is the number of permutations to the power of the number of generators. Four colours would need 24⁴ assignments for the larger groups and a smarter enumeration than a sweep.

And the four-colour question is left open rather than answered. The pattern the two refusals make — p3 at two colours, the four-fold groups at three — invites the guess that each k has its own short list of refusers, decided by which rotation orders fail to find room in S_k. Four colours would be the case to test it on, since S₄ has elements of order four and the four-fold groups would stop refusing; whether some other group starts is not computed here and the guess is stated as a guess.

And it says nothing about whether a colouring can be drawn. Two colours and a swap records the hazard: a colouring is inconsistent as a picture when a point’s stabiliser contains an operation that changes its colour, so a motif in the wrong place makes the colouring undrawable without anything in the arithmetic objecting. That check is not run here, and the count above is a count of colour symmetries rather than of patterns somebody could paint.

The one thing to carry #

“A symmetry of order two cannot permute three colours” is true of cyclic permutations and false in general, and the difference is the whole content of this rung. A half-turn permutes three colours by fixing one and swapping the other two, which is a perfectly ordinary symmetry of a perfectly ordinary pattern — the sort of thing a tiler does without thinking about it.

What that suggests more widely is worth a sentence. A restriction derived from an order argument is only as strong as the group the orders were compared in, and it is easy to fix that group by habit rather than by the question. The first rung fixed it at ℤ₃ because a three-colouring sounds like a cyclic thing; the answer changed by a factor of six when the assumption was written down and looked at.