How few operations make a pattern

Every pattern on this site is drawn the same way: a motif, a group, and the orbit of the first under the second. The group is handed to the drawing loop as a finite list of operations modulo the lattice, which is a convenient fiction — the group itself is infinite, since it contains every lattice translation and there are infinitely many of those.

So a fair question, which none of the essays here has asked: how few operations does it take to build the whole thing?

The interest is not in the number itself but in how it is decided. Asking whether a set of operations generates an infinite group is a question with no obvious stopping rule: multiplying elements together produces more elements, and never producing anything new is not the same as never being able to.

And “how few” is two questions rather than one, which is worth separating before any of the machinery arrives. There is the number a proof can establish from below — the abelianisation cannot be generated by fewer elements than it has invariant factors, and that bound is inherited by the group above it — and there is the number a search finds from above, by trying every set of a given size and failing. When the two meet, the answer is settled and no better argument can exist. When they do not, what is reported is the search’s answer, and the search’s guarantee is only that the pool it looked in was exhausted. Fourteen of the seventeen have the two numbers meeting; three do not, and those three are where the rest of this essay’s caution goes.

Two halves, and only one of them is easy #

A subgroup of a plane group is settled by two facts about it, and separating them is what makes the question tractable.

Which point operations it reaches. Ignore the translation parts and close the matrices up. That is a finite computation over a set of at most twelve matrices, and it either reaches every matrix of the point group or it does not.

Which translations it contains. This is the hard half, and it is where an unwary answer goes wrong. A set of operations may reach every point operation of the group and still generate only a sublattice of the translations — half the lattice, or a third of it — in which case what it generates is a genuinely smaller group that looks correct from every angle except the one that counts.

The rotation on its own is the standing warning. Its matrices close up to the whole point group of p3; the group it generates is finite; and no amount of examining the matrices reveals the difference, because the difference is in the translations, which the matrices do not carry.

Schreier’s lemma, which removes the search #

The translations a set generates can be computed exactly, with no search over words and no cap. The tool is a lemma of Schreier’s from 1927, and it is the single piece of machinery this essay rests on.

Let the set generate a subgroup, and let that subgroup map onto some set of point operations, with the translations as the kernel. Choose one element of the subgroup for each point operation reached — a transversal, obtained here by closing the generators up and keeping the first element found with each matrix. Then the kernel is generated by

the transversal element for g, times a generator s, times the inverse of the transversal element for whatever point operation g s reaches,

taken over every g in the transversal and every generator s. Each of those products has trivial linear part by construction, so each is a pure translation, and there are finitely many of them: the number of point operations reached, times the number of generators.

So the translation subgroup is the lattice spanned by an explicit finite list of vectors. Computing which lattice that is takes a Hermite normal form over the integers — the same reduction the sublattice essays use to count sublattices of a given index — and comparing it with the group’s own lattice is then an integer determinant. The subgroup is the whole group when the point operations are all of them and that determinant is one.

Nothing is approximated and nothing is capped. The alternative — multiply things together and watch for new translations to stop appearing — has no stopping rule at all, and would have been wrong in exactly the cases that matter.

A floor, a ceiling, and where they meet #

With generation decidable, the fewest generators is a search: try every set of one operation, then every set of two, and stop at the first size that works. The pool is the group’s operations within one cell of the origin, which is enough because an operation further out is a nearby one composed with a translation.

A search alone gives an upper bound. What makes the answer exact is a lower bound that owes nothing to the search.

The abelianisation is that lower bound. Making a group abelian cannot make it harder to generate: the images of a generating set generate the quotient. So a group needs at least as many generators as its abelianisation does, and a finitely generated abelian group needs exactly as many as it has invariant factors. That number is read off a Smith normal form and it is not a guess.

Fourteen of the seventeen meet their floor, which settles those fourteen exactly: no set of that size minus one can exist, and a set of that size does. The three that do not — p3m1, p31m and p6, each of which abelianises to a cyclic group and so has a floor of one — need more than the abelian argument can see, and the gap is itself informative.

p2, and why two half-turns are not enough #

The clearest case is the group whose every operation is a half-turn or a translation.

Where the product is works out the composition of two half-turns exactly: about centres p and q, the product is a translation by twice the vector from one to the other. So a pair of half-turns generates translations along one direction only — the line joining the two centres — and everything it makes lies on that line. It reaches every point operation of p2, since a half-turn and the identity are all there is, and it reaches a rank-one subgroup of the translations. It is not p2, and the failure is invisible in the matrices.

A third centre off that line supplies the second direction, and three is enough. Three is also the floor, since p2 abelianises to three factors of two, so p2 needs exactly three half-turns and the number is proved from both sides.

The same argument in a group with more rotation gives a smaller answer. Two four-fold rotations, one at a cell corner and one at the cell centre, generate p4 outright: their product is a translation, and this time a single pair supplies both directions because the four-fold turns one into the other.

The pair, once more, differing in a new way #

p3m1 and p31m have now been separated three ways on this site: by where their mirrors sit, by their abelianisations, and now by this.

Two operations for one, three for the other, and the reason is a fact about products rather than about positions: p31m contains an operation whose square is a lattice translation, and p3m1 does not. Its abelianisation is cyclic, so the floor for p3m1 is one — the floor is as unhelpful here as it can be, and the search does all of the work.

That is worth noticing as a limitation rather than glossing over. Three of the seventeen have a floor of one and need two or three, so for those the number reported is the search’s, and the search’s guarantee is that the pool was exhausted at each smaller size rather than that no such set can exist anywhere. The pool being the right pool is the next section.

What could be wrong, and what was checked #

The pool could be too narrow. Every candidate is a coset representative shifted by a lattice vector within one cell of the origin. If some group needed a generator further out, the search would report a number too large. So the whole census is run again over a pool five times the size — shifts up to two cells — and no group generates more cheaply in it. That does not prove no pool ever helps; it is the check that was available, and the result is stated as what it is.

The claim could be about words rather than operations. “Generated by two” here means two elements of the group, not two letters of a presentation with relations. The presentation of p6m has four letters and the group has two generators, and both statements are true of different objects.

The lattice half could be silently skipped. This is the failure that the refusals are aimed at: a three-fold rotation is offered as a generating set for p3, and the machinery must refuse it — not because the matrices are wrong, which they are not, but because the translations are missing. It does refuse, reporting that the subgroup contains no lattice at all.

The number this site has been using instead #

There is a smaller number that looks like this one and is not, and it has been in every figure in this collection from the beginning.

The drawing loop works with a group modulo its lattice: translations are reduced into one cell, the quotient is finite, and the closure that produces it starts from a very short list. p1 starts from nothing at all, p2 from a single half-turn, p6m from a six-fold rotation and one reflection. Those lists generate the quotient, and reducing modulo the lattice is what makes the closure terminate — it is the reason the orbit of a motif is a finite set of points rather than an unbounded one.

One half-turn generates p2 modulo the lattice, and three operations generate p2. Both are true, and they are statements about different groups. The quotient has order two and needs one generator; the group is infinite, contains a rank-two lattice, and needs three. Anyone reading the site’s own generator lists as minimal generating sets for the plane groups would be reading a table about the quotient.

Where the two numbers coincide is itself readable. p6m needs two either way, because a six-fold rotation and a glide reach the lattice on their own; p1 needs none for the quotient and two for the group, which is the largest gap possible and says only that p1 is its lattice. The gap is exactly the number of lattice directions the point operations fail to manufacture, and manufacturing them is what a glide or a second rotation centre does.

This is the same distinction the site draws elsewhere between a group and its quotients: a subgroup that keeps every translation and one that keeps only some of them are different kinds of descent, and a count that does not say which group it is counting is not a count.

Where the exactness stops #

The generation test is exact. Integer matrices, integer vectors scaled to twelfths of a cell, and a Hermite normal form. There is no tolerance and no iteration limit inside it.

The minimality is exact where floor and ceiling meet, and is a search result where they do not. Fourteen groups are in the first case and three in the second, and the table says which.

The count is of unordered sets, not of ordered ones, and it says nothing about which sets work — many do. The figures show the first set the search finds in a pool deliberately ordered tidiest-first, so that the reported answer is stated at the origin rather than a cell away. A different ordering would give a different set of the same size.

Nothing here extends to three dimensions as written. The Schreier construction does, and so does the abelian floor; the pool of candidates does not, since a space group’s operations within one cell of the origin is a much larger set and the search would need to be cleverer than exhaustive.

Who found it, and when #

Otto Schreier published the lemma in 1927, in the paper that also gave the subgroup theorem for free groups he shares with Nielsen. The lemma is one paragraph and it is the reason subgroups of finitely presented groups are computable at all: it turns “what does this subgroup contain” from an unbounded search into a finite list.

Nielsen’s 1921 theorem that a subgroup of a free group is free is the other half of the same story, and the combination — Nielsen–Schreier — is the foundation of the rewriting methods that produce presentations of subgroups.

Coxeter and Moser tabulate generators alongside relations for the seventeen plane groups, and a reader comparing will find the same counts. As with the presentations themselves, the agreement is reassuring and is not what makes the numbers here trustworthy: the floor comes from an invariant and the ceiling from an exhaustive search, and both are computed here.

The three-half-turns fact is older than any of it. That a pattern with nothing but two-fold centres is built from three of them is the kind of observation that appears in nineteenth-century ornament treatises as a rule of thumb about how to lay out a repeat, long before there was a language in which to say why three and not two.

The bound Schreier’s lemma also carries #

The lemma is used here to compute the translations a set generates. It also carries an inequality, and the inequality relates the two numbers this essay is about in a way worth having.

Schreier’s index formula says that a subgroup of index n in a group generated by d elements is generated by at most n(d − 1) + 1 elements. It is not an estimate — it is the length of the list the lemma produces, one entry per transversal element and generator, with the trivial ones removed.

Apply it to a plane group. The translations are a subgroup of index |P|, the order of the point group, and they are ℤ² — so they need exactly two generators. If the whole group is generated by d elements, the formula gives

$$2 \le |P|\,(d - 1) + 1,$$

which for d = 1 reads 2 ≤ 1 and is false. So no plane group is generated by a single element, whatever its point group — a fact this essay’s floor gets from the abelianisation and which arrives here from a completely different direction.

For d = 2 the inequality is satisfied by every point group of order two or more, so it forbids nothing further. That is the honest limit of the bound: it separates one generator from two and says nothing above that, which is why the exhaustive search is still doing the work. A bound that rules out one case is still a bound, and it is worth noticing that the two arguments — a rank over the integers modulo nothing, and a count of Schreier generators — agree on the one case they both reach.

Generators are not a presentation #

There is a second number in the neighbourhood, it is the one a reader who has met group presentations will assume is meant, and the two are worth separating because they behave differently.

The minimum number of generators is what this essay computes: how few elements of the group suffice, with no constraint on how they relate. The minimum number of relations is a separate quantity, and a group generated by few elements may need many relations to pin it down.

The difference between the two is called the deficiency, and it is not a formality: a group can have a presentation with two generators and three relations, or with three generators and four, and which is smaller depends on the group. A group in four letters gives a presentation of each plane group with generators chosen for legibility rather than for minimality, and the counts there are not the counts here.

For a plane group both quantities are finite and both are computable, which is unusual — a general finitely presented group has neither computable. What makes them computable is what makes everything else in this ladder computable: a normal subgroup of translations that is ℤ², with a finite quotient, and integer arithmetic all the way down.

Where this ladder goes #

Three rungs have now taken a plane group apart without drawing it: its presentation derived from its operations and checked by an enumeration that never met a matrix, its abelianisation separating a pair that no picture can separate, and its generating number bounded from both directions.

What each of them has in common is that the answer survives every convention this site has ever had to choose — the cell, the origin, the axes, the symbol. That is the whole reason for leaving the plane behind for three essays, and it is also the reason to come back: none of these computations can draw a pattern, and the picture is still what the argument is for.