The classification proof, one branch at a time

The number seventeen is quoted far more often than the argument behind it is given, which is a pity, because the argument is finite, elementary and short. It has four moves, and each of them closes off a branch of possibilities completely.

The four moves are: fix the highest rotation order; find which lattices carry it; enumerate the reflection arrangements that lattice permits; and collapse the arrangements that forcing makes identical. Everything else is bookkeeping.

Move one: the rotation order is one of five #

Any wallpaper group has a subgroup of translations that forms a lattice, and every other operation must map that lattice to itself. So the rotations available are the rotations a lattice can carry, and the crystallographic restriction says there are five: orders 1, 2, 3, 4 and 6.

The proof of that is one line. A rotation mapping a lattice to itself is an integer matrix in the lattice basis, so its trace is a whole number; the trace of a rotation by $2\pi/n$ is $2\cos(2\pi/n)$, which lies between $-2$ and $2$; and a whole number in that range is one of five values, each corresponding to exactly one $n$.

So the classification splits into five branches at the first step, indexed by the highest rotation order present. That is what makes the whole thing finite, and it is why the restriction has to come first: without it there are infinitely many branches and nothing to enumerate.

Move two: the order constrains the lattice #

Each rotation order is compatible with only some of the five lattice types, and the compatibility is forced rather than conventional.

A threefold or sixfold rotation requires a hexagonal lattice. Rotating a shortest vector by $120°$ produces another vector of the same length at $120°$, and a lattice containing two equal shortest vectors at $120°$ is hexagonal by definition.

A fourfold rotation requires a square lattice, by the same argument at $90°$.

A twofold rotation requires nothing: every lattice has a half turn, since negating both coordinates is an integer operation that preserves any lattice at all. So the order-two branch has to consider every lattice type, and it is correspondingly the largest.

Order one — no rotation — also allows every lattice, but with no rotation the reflections have little to interact with, and the branch collapses quickly.

This is where the count starts to become explicable. Two of the five branches are constrained to a single lattice each; two are unconstrained and do most of the work. The seventeen are distributed 4 · 5 · 3 · 3 · 2 across the orders 1, 2, 3, 4 and 6, and the largest branch is the one where the lattice was least constrained.

Move three: the reflections, enumerated #

With the rotation order and the lattice fixed, the remaining question is which reflections and glides can be added.

The available mirror directions are fixed by the lattice: a square lattice has two families, along the axes and along the diagonals; a hexagonal lattice has two, along the axes and bisecting them; a rectangular lattice has two perpendicular ones; an oblique lattice has none. So the choice is not “where shall a mirror go” but “which of these two or three families shall be occupied, and by a mirror or by a glide”.

That reduces each branch to a handful of cases. In the fourfold branch: no reflection at all gives p4; the axis family occupied by mirrors gives p4m; the axis family occupied by glides gives p4g. Occupying the diagonal family instead turns out to give nothing new, because the fourfold rotation carries one family to the other whenever both are occupied, and when only one is occupied the choice of which is a choice of axes.

Three cases, three groups, branch closed. The threefold branch gives p3, p3m1 and p31m by the same reasoning with two inequivalent mirror families, and the pair that results is the classification’s most delicate distinction.

Move four: forcing #

The step that makes the count fall well below the number of candidate combinations is the observation that symmetries compose, so the presence of two operations can force a third.

Three forcing rules do nearly all the work, and each is a one-line composition.

Two perpendicular mirrors force a half turn, about their crossing point, because reflecting across two perpendicular lines is a rotation by twice the angle between them.

A mirror and a parallel translation force a glide, because the composite of a reflection with a translation along its own axis is a glide by definition. So a mirror is never alone: it always brings glides on parallel axes half a cell away.

A half turn and a mirror force either a second mirror or a glide, depending on whether the rotation centre lies on the mirror line. This is the rule where placement rather than presence decides the outcome, and it is the source of every awkward pair in the classification.

Applying those rules collapses the candidate list. In the twofold branch on a rectangular lattice the naive count is eight combinations of two mirror families each occupied by a mirror, a glide or nothing; forcing reduces them to pmm, pmg and pgg — three — and the collapse pattern is exactly the frieze case with a second direction added.

The largest branch, run in full #

The twofold branch is the one worth doing completely, because it is the biggest — five of the seventeen — and because everything awkward in the classification appears in it.

Every lattice carries a half turn, so the branch has to consider all five lattice types. On an oblique lattice there are no mirror directions at all, so the only group is p2: a half turn and nothing else.

On a rectangular lattice there are two perpendicular mirror directions, and each may carry a mirror, a glide, or nothing. Nine combinations, before forcing:

• Neither occupied gives p2 again, on a lattice more special than it needs. Not a new group.
• Both mirrors gives pmm — and the half turn comes free, forced by the two perpendicular mirrors, which is why pmm’s symbol names two mirrors and its cell holds four operations.
• One mirror, one glide gives pmg. The half turn is again forced, and the glide’s axis runs perpendicular to the mirror’s.
• Both glides gives pgg, a group with reflection-reversing symmetry and no mirror line anywhere.
• One direction occupied, the other empty is not consistent once the half turn is present: the half turn carries the occupied family onto itself and generates an operation in the other direction. So these cases collapse into the three above.

Three groups from a rectangular lattice, then. On a rhombic lattice the two mirror directions run along the diagonals, and the analogous enumeration gives cmm — a single group, because the centring translation relates the cases that were distinct on the rectangular lattice.

Finally, a square lattice carries a half turn but a pattern whose highest rotation is a half turn cannot use the square lattice’s extra symmetry, so nothing new appears. Total: p2, pmm, pmg, pgg, cmm. Five.

Two features of that walk are worth naming because they recur.

The forced half turn. In pmm, pmg and pgg the rotation was never specified: it appeared as a consequence of two reflections. A classification that treated rotations and reflections as independent would count these branches several times over.

The lattice doing the collapsing. On the rhombic lattice, cases that were distinct on the rectangular one merge, because the centring translation supplies a motion carrying one to the other. That is the same mechanism as the glide that is and is not there, and it is the reason the branch has four groups on two lattices rather than six on one.

What the computation contributes, and what it cannot #

This site generates all seventeen and round-trips each: the pattern is built from the group’s operations, the group is forgotten, and a detector rediscovers the symmetries from the bare point set. Being precise about what that establishes is the whole point of doing it.

It establishes the lower bound. Seventeen groups were specified, seventeen patterns produced, and each pattern’s detected symmetry matches its own generating set exactly. Since no two of the seventeen operation sets are equal, no two are the same group. So there are at least seventeen, machine-checked, with no appeal to a table.

It does not establish the upper bound. No amount of exhibiting shows that an eighteenth is impossible. That is a claim about every conceivable pattern, and only the case analysis above reaches it.

There is a useful middle ground the computation does occupy. Every step of the case analysis is a claim about a specific group or pair of groups — that p4g’s glides cannot be removed by moving the origin, that p3m1 and p31m are not related by any change of basis, that the fourfold rotation carries one mirror family to the other — and each of those is decidable and is checked here. So the computer verifies the argument’s individual steps while the structure of the argument, the part that makes it exhaustive, stays in the prose.

That division is honest and it generalises. A figure can confirm every step of a proof and never confirm the proof, because the exhaustiveness is a property of the enumeration rather than of any case in it.

Where the exactness stops #

Two boundaries, and both are about what “the same group” means.

The classification counts groups up to affine equivalence: two patterns have the same group when some invertible linear map plus translation carries one group of operations onto the other. Under that relation there are seventeen. Under a stricter relation — up to rigid motion, without stretching — there are more, because a rectangular pattern and a differently proportioned rectangular pattern are not related by any rigid motion. The seventeen is a count of types, and the type is defined by the equivalence chosen.

The second boundary is the one that matters for what is on the rest of this site. The classification is a statement about patterns with a lattice of translations. A pattern without one is not an eighteenth case; it is outside the domain of the theorem, in the same way that a Penrose tiling is neither one of the seventeen nor a counterexample to their being seventeen.

There is a third thing worth saying because it is a live confusion. The seventeen classify the symmetry group, not the appearance. Infinitely many patterns share each group, and two patterns in the same class can look nothing alike. A classification into seventeen is not a claim that there are seventeen kinds of wallpaper.

The generalisation, and the sizes it produces #

The same four moves run in three dimensions and give two hundred and thirty, and the growth in the count comes from three places.

The restriction gives the same five orders, which is not obvious and is worth checking. The lattices grow from five to fourteen, because centring has more options in space. And a new kind of operation appears: the screw axis, a rotation combined with a translation along its own axis, which has no two-dimensional counterpart and which multiplies the non-symmorphic possibilities.

The counts in higher dimensions are known and were computed rather than derived: 4783 in four dimensions, 222 018 in five, 28 927 915 in six. Bieberbach proved in 1911 that the number is finite in every dimension — the answer to the eighteenth of Hilbert’s problems — but the proof gives no bound worth having, and every count past three has come from a computer search.

That progression is a good calibration of what “elementary case analysis” is worth. In two dimensions it is a pleasant afternoon. In three it took three people working independently and produced two conflicting answers before they were reconciled. In four it is a computation.

The count as a piece of arithmetic #

There is a second proof, and it is short enough to be worth putting beside the case analysis, because it replaces the enumeration with a calculation.

Fold the plane up along the group’s own symmetries. What remains is a small surface with marked points — an orbifold — and every wallpaper group gives a different one. Each feature of that surface carries a cost: a cone point of order $n$ costs $(n-1)/n$, a mirror boundary costs $1$, a corner where two mirrors meet at order $n$ costs $(n-1)/2n$, and a handle costs $2$. The theorem is that the costs of a wallpaper group’s orbifold sum to exactly $2$.

So the classification becomes: list every way of making $2$ out of those pieces. It is a small arithmetic problem, it terminates quickly, and it produces seventeen answers. The same calculation with a sum below $2$ gives the finite groups and with a sum above $2$ gives the hyperbolic ones, of which there are infinitely many — so the argument classifies all three cases at once and explains why only the middle one is finite.

That proof is Conway’s, and it is a genuinely different route rather than a rearrangement of the first: no lattice appears in it, no forcing rule is invoked, and the crystallographic restriction comes out as a consequence rather than going in as a hypothesis. The notation it produces is the shortest of the three in use.

Two proofs of one theorem, with almost nothing in common, is the strongest kind of evidence available for a result of this shape — and it is the same methodological principle this site applies to its figures, where a pattern’s group is asserted directly from the point set and again, independently, from what the point set scatters.

Who did it, and who nearly did #

Fedorov derived the seventeen in 1891, as part of a much larger project that also gave the two hundred and thirty space groups. Pólya rediscovered them in 1924 and, more consequentially, drew them: his plates travelled to the Netherlands, where M. C. Escher — who had no mathematics at all — used them as a working manual for the rest of his career.

The story that the Alhambra contains all seventeen is repeated constantly and is not settled. Different surveys of the same building disagree with each other, chiefly because they disagree about how much of a pattern must be present before its group can be assigned, and the question is less about mathematics than about what counts as evidence.

The earlier near-miss is instructive. Camille Jordan enumerated the groups of motions of the plane in 1869 and missed several cases; Sohncke corrected part of it in 1874 and missed others. Both were working without the forcing rules stated explicitly, which is exactly the step that keeps the count from being larger than it should be — and the error in both directions is the same error, of treating the available operations as independent switches.

Where the ladder goes next #

The result being proved is the seventeen themselves, and the rehearsal that makes the argument legible is the seven friezes, where sixteen candidates collapse to seven by the same three rules.

The notation that makes the branches nameable is Hermann–Mauguin, and the one that makes the distinctness obvious is orbifold notation, whose own proof of the seventeen is a piece of arithmetic rather than a case analysis.

The step up is three dimensions, where the same argument gives two hundred and thirty.

What the pictures here cannot show. Every figure on this page shows patterns that exist. The theorem is about patterns that do not, and no drawing exhibits an absence. A reader who finds the seventeen convincing after looking at the plate has been convinced by the prose, and the plate’s real job is to confirm that each of the seventeen it names is genuinely different from the others.