The orbit is the pattern

Here is a way of making a wallpaper pattern that involves no design decisions at all. Put a mark somewhere. Apply every operation of a group to it, and keep every image that results. Stop when applying another operation produces nothing new.

What comes out is a pattern with exactly that group’s symmetry, and the process is mechanical from beginning to end.

The set of images of a point under a group is called its orbit, and the claim of this essay is that the orbit is not a way of making patterns among others. It is what a pattern is.

Why the reframing pays #

Taking it literally changes what can be checked.

A pattern that was drawn has a caption asserting its symmetry, and the assertion rests on the author’s judgement. A pattern that was generated has no caption problem at the point of generation — it has the group’s symmetry because it was made by applying the group — but it acquires a subtler one, which the rest of this essay is about.

More importantly, generation makes the reverse direction available. A drawn pattern can only be examined; a generated pattern can be examined and compared against what it was supposed to be. That comparison is the round trip on which every figure on this site rests, and it is worth spelling out in full:

1. Generate. Apply the group’s operations to a motif until the orbit closes.
2. Forget the group. Hand the bare point set to a detector that enumerates every operation the lattice permits and keeps the ones that map the set to itself.
3. Compare, in both directions. The detected set must equal the generating set exactly.

Step two is the one that carries the weight. The detector is not told what it is looking for. It runs the same search whatever pattern it is given.

What the detector actually does #

The search is finite, which is the fortunate structural fact this subject rests on.

An operation is a matrix and a translation. In coordinates chosen along the pattern’s own repeat vectors, the matrix has whole-number entries, and the requirement that it preserve lengths and map the lattice onto itself limits it to the handful of integer matrices in the lattice’s holohedry — two for an oblique lattice, four for rectangular, eight for square, twelve for hexagonal. So the matrix is drawn from a list of at most twelve candidates.

The translation is then determined rather than searched. Pick any point $p$ in the pattern and any point $q$; if the operation with matrix $M$ maps $p$ to $q$ then its translation must be $q - Mp$, and there is nothing left to guess. Every candidate operation is therefore of the form “matrix from a list of twelve, translation from a list of pairs of pattern points”, and each is checked by applying it and comparing sets.

That is the whole detector. It is exhaustive by construction, it involves no tolerance, and it terminates.

Two details make it exact rather than merely careful. The first is the choice of coordinates: expressed along the pattern’s own repeat vectors, a threefold rotation is a matrix of whole numbers, whereas in ordinary page coordinates it involves $\sqrt{3}/2$ and every subsequent comparison would need a threshold. The second is that the translations are rationals with small denominators — halves, thirds, quarters — so comparing two operations is comparing two lists of exact fractions. Nothing in the pipeline ever asks whether two numbers are close.

The motif is a choice, and not an innocent one #

Now the subtlety. Applying a group faithfully does not guarantee a picture of that group.

If the motif has symmetry of its own, or sits at a position where some of the group’s operations leave it alone, the orbit can turn out to have more symmetry than the group used to make it. The generation was correct. The picture is nonetheless of a different group, and the caption is wrong.

The cleanest case is a single dot. Its orbit under p3 acquires three mirror lines and a pair of glide axes it was never given, so the pattern is p31m and the caption says p3. Its orbit under p1 always acquires an inversion centre — the midpoint between the dot and its own lattice translate is one — so a lone dot can never illustrate the group with no symmetry at all.

The remedy is an asymmetric motif, and this site uses three points in no particular arrangement. That fixes all seventeen. It is the algebraic version of the comma that every nineteenth-century ornament plate draws instead of a dot.

Stabilisers, and where the count goes #

There is a tidy piece of arithmetic underneath the hazard, and knowing it removes the mystery.

The stabiliser of a point is the set of operations that leave that point exactly where it is. For a point in a general position the stabiliser is trivial — only the identity fixes it — and the orbit then has as many members as the group has operations. For a point sitting on a rotation centre, the stabiliser contains that rotation, and the orbit is correspondingly shorter.

The relation is exact: the size of the orbit times the size of the stabiliser equals the size of the group. So a point at a fourfold centre in p4 has an orbit of one rather than four, because its stabiliser has four members. That is why special positions are dangerous: the orbit collapses, the collapsed set has additional coincidences, and the coincidences show up as symmetry that was never asked for.

Crystallographers call the general-position orbit the general position and the collapsed ones special positions, and every entry in the International Tables lists them explicitly for exactly this reason. The tables were doing this bookkeeping a century before anybody could automate it.

The fundamental domain #

If the orbit is the pattern, then most of a drawn pattern is redundant. The non-redundant part has a name.

A fundamental domain is a region containing exactly one point of each orbit — a patch of the plane such that applying the group’s operations to it tiles the whole plane, with no overlaps and no gaps. For p1 it is the unit cell. For p2 it is half a cell, since the half turn accounts for the rest. For p6m it is a twelfth of a cell, a small triangle with a $30°$–$60°$–$90°$ shape.

The practical consequence is that designing a p6m wallpaper means designing that triangle. Everything else is forced. Escher understood this perfectly well without the vocabulary: his notebooks contain the fundamental domains, worked out by hand, with the rest of the plane filled in mechanically afterwards.

Crystallographers use the term asymmetric unit for the same idea, and a structure determination reports the contents of the asymmetric unit rather than of the whole cell. A protein structure listing three thousand atoms in a cell containing twelve thousand is not being economical with the truth; it is reporting the only part that is not implied.

Colour, and the choice not to use it #

One decision has been silently in force since the first figure, and it changes the answer, so it deserves stating.

Everything here treats a pattern as a set of points, uncoloured. A chessboard, on that convention, has a fourfold rotation about the centre of any square and also about any corner, because the squares are indistinguishable. Restore the colours and the corner rotation fails: it sends black to white.

Colour symmetry is a real extension rather than a complication to be avoided. Requiring operations either to preserve the colouring or to swap the colours consistently gives the two-colour groups, of which there are forty-six in the plane. Requiring consistency across more colours gives more still. The subject is genuinely beautiful and it is a different subject, with its own notation and its own classification.

The second colour used throughout this site is therefore not a colouring in that technical sense. It records handedness, which is a property of the operation that produced a copy rather than a property assigned to the copy independently. A reader who takes the two colours as a two-colour pattern will get the wrong answer, and this paragraph exists so that nobody does.

Growing rather than drawing, in practice #

Every figure on this site is generated. What that means concretely is worth describing, because it changes what a figure can be wrong about.

A generator is a function. It takes parameters — which group, how many cells, what to overlay — and returns the drawing. There is no saved artwork anywhere and no step at which a person positions anything. Ask for p31m at three cells and the code applies the group’s six operations to the motif, tiles the resulting cell across the range, locates the symmetry elements from the operations’ own matrices, and marks them in the International Tables symbols.

The figure therefore cannot disagree with its own caption about which operations are present, because the caption’s group is the same object the drawing was made from. What it can be wrong about is everything else: a label in the wrong place, an element mark drawn at the right coordinates but visually attached to the wrong feature, a canvas too small for its contents. Those failures are caught by looking, and looking is still part of the process.

What generation costs #

Growing patterns instead of drawing them has a price, and it is paid at build time rather than by the reader.

The detector’s search is quadratic in the number of points, because the translation of each candidate operation is fixed by a pair of points and every pair must be considered. For a motif of three points under a group of twelve operations that is a set of thirty-six points and about thirteen hundred pairs, each checked against twelve candidate matrices — trivial. For the plate showing all seventeen groups at once it is done seventeen times over, and for the figure that tries a dot at 121 positions across the cell it is done 121 times more.

None of that is expensive yet. It will be. The remedy, when the site is large enough to need one, is to cache orbits by group and motif rather than to make the detector faster, since the same handful of orbits recur across hundreds of figures.

The reason for mentioning arithmetic cost at all is that it constrains what the method can be used for. A check that runs at build time can be exhaustive because it runs once; a check that had to run in a reader’s browser could not be. Every verification claim on this site is a build-time claim, and nothing is recomputed when a page is opened.

Three things generation does not buy #

Being clear about the limits is more useful than being enthusiastic about the method.

It does not decide aperiodic patterns. A Penrose tiling has no lattice, so the integer machinery has nothing to work with: there are no repeat vectors to use as coordinates and no finite holohedry to search. Aperiodic figures on this site are constructed by inflation and their properties are measured rather than proved.

It does not go to three dimensions. Everything here is planar. The space groups are the same argument with screw axes added and considerably more bookkeeping, and no essay here may imply the code went there.

It does not make a figure clear. A verified pattern with an unreadable label is a bad figure that happens to be correct. Verification and communication are separate problems, and only one of them is automatable.

What the round trip caught first #

The method’s first catch was the site’s own default motif, which is a pleasing kind of evidence.

The intention had been to draw the motif as a single dot, on the grounds that dots are unambiguous and cheap. The round trip refused eleven of the seventeen groups outright. Investigating why produced the numbers now quoted in the essay on the comma: for pm, pg and cm every one of 121 dot positions tried gives a pattern more symmetric than the group; for p3 it is 85 of 121; for p6m only 2, which is a genuine surprise and has a good explanation.

Nobody would have caught that by looking. The pictures were entirely plausible, and the wrong ones were prettier.

Who did this before there were computers #

Generating a pattern from a group by hand is laborious but perfectly possible, and the practice is much older than the algebra.

Islamic geometric ornament from the tenth century onwards is constructed rather than drawn: a master pattern of construction lines is laid out, the fundamental unit is developed within it, and the repeat is mechanical. The girih tiles used in Persian architecture from the thirteenth century are literally a generating set, and the craftsmen who used them were manipulating a group without a name for it.

The Alhambra is the famous case, and it is famous for a slightly wrong reason. It is often said to contain all seventeen groups; careful surveys find between thirteen and sixteen depending on what counts as a distinct pattern and whether colour is ignored. That the number is close to seventeen without being seventeen is more interesting than the myth: it says the craftsmen explored the space thoroughly by construction, and stopped short of the cases that are hardest to reach by construction — which are, unsurprisingly, the ones with essential glides.

Where the ladder goes next #

The orbit needs somewhere to live, and that somewhere is the lattice: the set of translations the pattern already has, which every other operation must respect. The lattice underneath takes that up, and five lattices and no others enumerates the possibilities.

The other direction is the hazard this essay kept running into. The motif must be a comma is about accidental symmetry, why it is invisible, and what the numbers actually are.

What the pictures here cannot show. An orbit is infinite and every figure shows a few cells of it. More seriously, no picture can display the absence of a symmetry — the claim that p3 has no mirrors is a claim about a completed search, and a drawing can only ever fail to show one.