Every wall names a generator

A fundamental domain is a piece of the plane that meets each orbit exactly once. Its copies under the group therefore tile the plane, and — this is the part usually treated as bookkeeping — the copies are in one-to-one correspondence with the elements of the group. One element, one copy; and the copy corresponding to the identity is the domain itself.

That correspondence turns an algebraic question into a geometric one, and Poincaré’s theorem is the answer.

The elements that carry the home copy onto a copy sharing a wall with it generate the whole group.

Why it is true #

The proof is one sentence and it is entirely geometric.

Take any element g. Its copy is somewhere in the plane. Walk to it from the home copy, stepping from one copy to an adjacent one at each stage — which is possible because the tiling is connected. Each step crosses a wall and therefore corresponds to a wall element. The product of the wall elements along the walk is g.

That is all. The theorem is the connectedness of a tiling, and everything algebraic about it comes for free.

What makes it worth stating is what it replaces. Without it, “which elements generate this group” is a question answered by trying things: pick a set, close it up, see whether everything appears. With it, the answer is read off a picture, and the picture is the one a reader was going to draw anyway.

What is computed here, and on what #

The domain used in this collection is not the polygon a textbook draws. It is a set of cells on a grid — the lexicographically first point of each orbit, taken over a grid of twelfths — with the partition asserted in both directions before it is handed back, so that no cell is claimed twice and none is missed.

That choice is visible in every count below and it has to be said plainly. A pixelated domain has more walls than a polygon would, because its boundary is a staircase; some of those walls separate copies that a polygonal domain would have met only at a corner; and the number of walls is therefore a property of this domain rather than of the group. Every table says walls of this domain.

What does not depend on the pixels is the thing being tested. The set of elements reached across walls either generates the group or it does not, and that is decided by closing the set up.

Closing the set up, and the condition that is easy to miss #

Testing whether a set of elements generates a wallpaper group has a trap in it, and the trap is the reason the test here has two conditions rather than one.

The obvious test is: close the set up and see whether every coset of the translation subgroup is reached. That is necessary and it is not sufficient. A set can reach every coset and generate only a sublattice of the translations — which would mean the group it generates has the right point group and the wrong lattice, an index-two subgroup that looks complete by every count the obvious test makes.

So the check has two parts: every coset reached, and the translations generated being the whole of ℤ² rather than a sublattice. The second is the voltage-lattice test again, in its third appearance in these essays.

The case that makes it concrete is the simplest group there is. p1 has one coset — itself — so every non-empty set of its elements reaches every coset there is. Its walls are the two lattice translations; take one of them and the coset test passes perfectly while the group generated is a line’s worth of translations rather than a plane’s.

The walls are closed under inverses, and getting that right cost something #

A wall is crossed in both directions. If the home copy touches g’s copy then g’s copy touches the home one, and applying g⁻¹ to both says g⁻¹ is a wall element too. So the set of wall elements must be closed under inverses, always, and that is a property nothing in the construction imposes — which makes it a good check on whether the construction is right.

It failed twice, and both failures were informative.

The first was a stabiliser. A pixel of a pixelated domain can sit on a mirror or at a rotation centre, in which case several elements carry the domain’s representative to the same neighbouring pixel. Taking the first match found made the wall set fail inverse-closure on six of the seventeen. The neighbouring pixel genuinely belongs to several copies at once, and all of them are wall elements.

The second was the adjacency itself. Which pixels count as sharing a wall has to be invariant under the group, or the wall set is not a wall set: a symmetry would carry a wall to something that is not one. On a square or rectangular cell the four steps to left, right, up and down are invariant, because every linear part permutes them. On a hexagonal cell they are not — the three-fold rotation sends the step (0, 1) to (−1, −1), which is no step at all — and the invariant neighbourhood is six steps rather than four. Using four put p31m, p6 and p6m out of inverse-closure, which is impossible for a real wall set and was the arithmetic saying so.

Both are the same lesson in different clothes: a discretisation must respect the symmetry of the thing it is discretising, or it introduces asymmetries of its own that look like results.

And the six-neighbour rule has a consequence in the drawing that is worth naming, because it is the kind of thing a picture quietly loses. Four of the six steps carry one pixel across an edge of the grid, and the drawing marks those as heavy segments along that edge. The other two — the step (1, 1) and its inverse — carry it across a corner: two rhombic pixels related by (1, 1) share a single point of the grid and no edge at all. Thirty-four of p3’s ninety-four wall segments are of that kind, and twenty-eight of p31m’s seventy-four. They are drawn as short ticks laid across the shared corner rather than as edges, because that is what they are; a wall that is a point is still a wall, and the element reached across it is still in the generating set.

What a wall is, when the domain is made of pixels #

The essay has been using the word wall as though it were obvious, and on a polygonal domain it is: a wall is an edge of the polygon, and the pairing that identifies it with another edge is the group element. On a pixelated domain the word needs a definition, and the definition is what the computation actually uses.

A wall is a pair of adjacent grid cells, one inside the domain and one outside it. The outside cell belongs to some copy; the element carrying the home copy to that one is the wall’s element. Two different pairs of cells can name the same element — a long straight stretch of boundary facing the same neighbour does exactly that — so the number of distinct elements is smaller than the number of adjacent pairs, and it is the elements that are counted.

The identification of which copy an outside cell belongs to is done through the domain itself: reduce the cell into the home cell of the lattice, ask the domain which of its own cells represents that orbit, and then find the operations carrying the representative to the cell in question. The lattice part is kept rather than reduced away, which is the step that keeps the translations in the generating set instead of collapsing them to the identity.

None of that is geometry. It is a lookup in a table the fundamental-domain construction already built, and it is exact, because the grid points are rationals and the operations act on them by integer matrices and rational translations.

The copies are a Cayley graph #

Now put the two halves together, which is the point of the essay.

The copies of the domain are the elements. Two copies are joined when they share a wall, and sharing a wall means differing by a wall element. So the graph of copies, joined across walls, is the Cayley graph of the group against the wall elements — not similar to it, the same graph, because the vertices are the same set and the edges are the same relation.

The consistency check is immediate: the number of copies touching the home copy must equal the number of distinct wall elements, and the first shell of the Cayley graph must be that number. It is, on all seventeen.

That identification is what makes the growth of a group a geometric quantity. Counting the elements of word length at most R against the wall generators is counting the copies of the domain reachable in R steps — which is a count of a growing patch of a tiling, and grows like its area.

What the wall count is measuring #

The wall counts in the table run from four to seventeen across the seventeen groups, and it is worth asking what makes one group’s domain have more walls than another’s, since the number is not the group’s.

Two things. The shape of the domain, which on a grid is a staircase and whose length depends on how the domain’s boundary lies relative to the grid directions; and the order of the group, since a larger group has a smaller domain and a smaller domain has proportionally more boundary. p6m’s domain is nineteen cells out of a hundred and forty-four and touches sixteen distinct neighbours; p1’s is the whole cell and touches four.

Four, not two, and the difference is the point of counting elements rather than directions. p1’s domain is the whole cell and it has two pairs of opposite sides. The element crossing the right-hand side is the translation along a; the element crossing the left-hand side is its inverse, which is a different element of the group. A wall set that listed the two translations and stopped would not be closed under inverses, and closure under inverses is the property that caught both of the bugs described above. So the smallest wall count in the table is four rather than two.

And the counts are not all even, which is the same rule read the other way. Closure under inverses pairs the wall elements up — except where an element is its own inverse, which is what a mirror and a half-turn are. Those contribute one each rather than two, so a group with an odd number of self-inverse wall elements has an odd wall count: cm and p4 come in at seven and p31m at seventeen, while p1, p2, pgg and pmm are even. The parity is a fact about how many of the wall crossings are reflections and half-turns, and it is worth noticing because a count that came out even everywhere would mean the self-inverse elements had been counted twice.

So the wall count is roughly a perimeter-to-area ratio, and a group with many operations has a domain that is nearly all boundary. That is the same trade the asymmetric unit makes in three dimensions, where a high-symmetry space group’s asymmetric unit is a sliver with a great deal of surface.

None of that is a fact about generation. Every one of these sets generates, whatever its size, and the redundancy grows with the wall count rather than the generating power.

What the walls do not settle #

They are not a minimal generating set. Two operations suffice for many of the seventeen, and no wall set here is that small. A wall set is usually redundant, and on the pixelated domains used here it always is: dropping any single element still leaves a generating set on every one of the seventeen. That is a fact about staircase boundaries — a polygonal domain has fewer walls and its wall set can be minimal — and it is the reason how few operations make a pattern is a separate question with a separate answer.

They depend on the domain. Choose a different fundamental domain and the walls change, the wall elements change, and the Cayley graph changes with them. What does not change is that they generate.

They say nothing about relations. Poincaré’s theorem in its full form also produces the relations — from the cycles of copies round a vertex of the tiling — and that half cannot be computed from this domain. A pixelated domain’s vertices are pixel corners rather than the tiling’s own, so the cycles it produces are artefacts of the grid, and reporting them as the group’s relations would be reporting the grid. The relations a polygon dictates builds the domain exactly instead — as the Dirichlet cell of a point with trivial stabiliser, which is a convex polygon with corners the group put there — and takes the cycles round those, giving a presentation of each of the seventeen that coset enumeration then confirms.

Reading generators off a picture, and why that is unusual #

It is worth stepping back to notice how odd this result is as a piece of mathematics.

Generating sets are normally found by searching. To show that a set generates a group, one closes it up and checks; to find a small generating set, one tries subsets. That is what how few operations make a pattern does, and the search is unavoidable there because the question is about minimality, which is a global property.

Poincaré’s theorem supplies a generating set with no search at all. Look at the domain, list its neighbours, done — and the guarantee that the list works comes from a topological fact about the tiling rather than from any computation on the group. That is a rare shape of argument: a geometric property of a picture certifying an algebraic property of an abstract object, with the certification requiring no calculation.

The check performed here is therefore not a proof of the theorem, which needs none. It is a check on the implementation — that the wall elements were read off correctly — and it is worth having because the two bugs described above both produced wall sets that looked entirely reasonable and were wrong.

Where the theorem lives #

Poincaré proved the general version in the 1880s, for groups acting on the hyperbolic plane, and it is one of the foundational results of that subject: given a polygon and a rule pairing its sides, the theorem says when the pairings generate a discrete group with that polygon as fundamental domain, and what its presentation is. The Euclidean case is the easy corner of it.

The reason it matters more in hyperbolic geometry than here is that hyperbolic groups are not classified — there is no list of seventeen to look things up in — so a theorem that manufactures a group from a polygon is the main way of getting hold of them at all. In the plane it is a convenience; there it is a construction method.

One check that is not a formality #

The tests reported above all pass, and a set of tests that all pass is exactly the situation in which nobody looks again. So one of them is deliberately arranged to have teeth.

The claim the walls generate is worth something only if it is possible for a set of elements not to generate — otherwise it is a statement about the machinery’s willingness to say yes. The p1 case supplies the counterexample: a single wall element, reaching every coset, generating a rank-one subgroup, and refused. Without it the generation test would be a test that had never rejected anything, which this collection treats as no test at all.

The same discipline governs the inverse-closure check, which is the one that found both bugs. It is not a check that anything ought to pass by construction — the construction never imposes it — so a failure there is evidence rather than noise, and it was evidence twice.

Where this goes #

The identification with the Cayley graph is what the growth essay needs and is the reason these two rungs were written together: one counts words and the other says where the words come from.

The wider connection is to the essays on crystal nets. A fundamental domain is a piece of geometry; its copies form a graph; the graph is a crystal net; and everything the net ladder establishes about coordination sequences and quasi-polynomial growth applies to it. The generators of a wallpaper group and the neighbours of an atom turn out to be counted by one procedure.

The corners give the relations #

The theorem quoted here is half of Poincaré’s, and the other half answers a question the first half raises immediately: knowing that the wall elements generate the group says nothing about how many different words in them give the same element.

Walk around a vertex of the tiling. The copies of the domain meeting at that corner form a cycle: cross a wall into the next copy, then the next, until the walk arrives back at the copy it started from. The composite of the elements crossed is an operation carrying the home copy to itself, so it is the identity — or, if the vertex sits at a rotation centre, a rotation whose order is how many copies meet there.

Each vertex therefore supplies one relation. The word spelled out by its cycle equals the identity, or equals a rotation of the stated order, and nothing else needs to be imposed.

That is a presentation. Generators from the walls, relations from the corners, and Poincaré’s theorem says the list is complete — any two words denoting the same element can be transformed into one another using only those relations. So the group is not merely generated by the picture; it is described by it, up to isomorphism, with no algebra performed at all.

The two halves fail differently if the domain is wrong. A region that is not a fundamental domain can still have wall elements that generate, by accident. It will not give a correct presentation, because the vertex cycles will not close.

Where the theorem is actually used #

The plane case is a demonstration, and it is worth saying what the theorem is for, because it was not proved to re-derive facts about wallpaper.

It runs in the other direction. Start with a polygon and a rule pairing its sides. Poincaré’s theorem gives conditions — on the angles at each vertex cycle, and on the pairings being consistent — under which the group generated by those pairings is discrete, and the polygon is a fundamental domain for it.

Discreteness is the hard part. A set of isometries generated by a few elements can easily have images accumulating somewhere, in which case there is no pattern, no tiling and no fundamental domain. Checking discreteness directly means examining infinitely many products; the theorem replaces that with a finite check on angles.

Which is how hyperbolic groups are built. The plane admits seventeen groups and they are all known, so nothing needs constructing. The hyperbolic plane admits infinitely many, and the standard way to produce one with prescribed properties — a surface of a given genus, a tiling by polygons of a given shape — is to draw the polygon, pair its sides, check the angle conditions, and let the theorem supply the group.

The plane case is then the sanity check. A theorem that constructs discrete groups had better return the seventeen when handed the seventeen, and the walls counted here are that test run on the one classification where the answer is already known.