Twenty-one vertices, eleven tilings

Ask how many ways there are to cover the plane with regular polygons, all of the same edge length, meeting edge to edge, with every vertex looking the same as every other, and the answer is a small number arrived at twice. It is eleven, and this essay is about the two roads to it, which meet with nothing left over in between.

The first road is arithmetic and it is short. The second is a parity argument about walking round a polygon, and it does almost all of the work — it disposes of ten candidates without drawing a single line.

The equation, and why it has an end #

A regular n-gon has interior angle 180°(n − 2)/n. Polygons meeting at a point with no gap and no overlap fill 360°, so their sizes satisfy

$$\sum_i \left(1 - \frac{2}{n_i}\right) = 2 .$$

That is a Diophantine equation and it is bounded at both ends. Each term is at least 1/3, since the smallest interior angle belongs to the triangle, so at most six polygons meet at a vertex; each term is less than 1, so at least three do. And the largest polygon that can appear is settled by the two smallest companions it could have: a triangle and a heptagon leave (1 − 1/3 − 5/7) = 1 − 2/42 of a turn, which is the forty-two-gon exactly.

So the search is finite and it is a few lines: sizes from 3 upward, non-decreasing, at most six of them, stop when the sum passes 2. It returns seventeen multisets.

Seventeen is not the answer to the question, because a vertex is not a set of polygons — it is a cyclic arrangement of them. Three triangles, a square and another square can be arranged as 3.3.3.4.4 or as 3.3.4.3.4, and those are different objects. Counting arrangements up to rotation and reflection, since a vertex has no preferred first polygon and no preferred sense, the seventeen multisets give twenty-one species.

That distinction is not bookkeeping. The two arrangements of {3, 3, 3, 4, 4} are the elongated triangular tiling and the snub square tiling, they have different wallpaper groups, and later in this collection a check that ignored the difference produced a patch that was locally perfect and globally wrong.

What a species has to survive #

A species is a description of one vertex. Whether a tiling exists with every vertex of that description is a completely different question, and the honest way to ask it is to try to build one and see.

There is a cheaper way, and it works on ten of the twenty-one.

Fix a polygon P in the species — say the heptagon of 3.7.42 — and walk round it. P has seven edges, each shared with one other polygon, and at each of its seven corners the species dictates what flanks it: in 3.7.42 the heptagon always sits between a triangle and a forty-two-gon. So the ring of polygons round the heptagon must alternate: triangle, forty-two-gon, triangle, forty-two-gon, and back to the start after seven places.

Seven is odd, so the ring cannot close. No tiling of the plane can have every vertex of species 3.7.42, and the argument used no coordinates, no angles beyond the ones already in the equation, and no drawing.

Stated generally: the ring of edge-neighbours round a polygon of size n is a closed walk of length n in the graph whose vertices are polygon sizes and whose edges are the flanking pairs the species permits. A bipartite graph has no closed walk of odd length. So whenever n is odd and that little graph is bipartite, the species is refuted.

The machinery here builds that graph — it has at most four vertices — two-colours it, and reports the refutation with the polygon and the pair it would have had to alternate between. Ten of the twenty-one die.

The ten it kills are worth listing, because they fall into two visibly different sorts. Six of them — 3.7.42, 3.8.24, 3.9.18, 3.10.15, 4.5.20 and 5.5.10 — contain a polygon that appears nowhere else in this subject, and their deaths are unsurprising. The other four are 3.3.4.12, 3.4.3.12, 3.3.6.6 and 3.4.4.6, which are made of the ordinary polygons and look entirely plausible. They tile nothing either, and the arguments are worth reading because they differ in shape.

For 3.4.3.12 the pinned polygon is the triangle: whichever of the two triangles in the species is looked at, it is flanked by a square and a twelve-gon, so its three edges would have to alternate between them. For 3.3.6.6 the triangle is flanked by a triangle and a hexagon in one occurrence and by a hexagon and a triangle in the other — the same pair either way — and three is again odd. 3.4.4.6 pins the triangle between a square and a hexagon. 3.3.4.12 is the delicate one: a triangle there is flanked by {12, 3} at one occurrence and by {3, 4} at the other, so the graph is a path on three sizes rather than a single edge, and it is still bipartite, so an odd ring is still impossible.

One qualification, and it is the reason these four look plausible. The argument assumes every vertex of the polygon being walked round is of the species. Drop that — allow a tiling with two or more kinds of vertex — and the walk is no longer constrained, so nothing above rules these four out of tilings that mix vertex types. What is refuted here is precisely what is being counted: tilings in which every vertex is alike.

The other road: build it and see #

The parity argument is a proof of impossibility. It says nothing about whether the surviving eleven are possible, and a classification with a gap between “not refuted” and “constructed” is a classification with a hole in the middle.

So the eleven are built, by a routine that has never heard of parity.

It places a single polygon on a unit edge. Then it repeatedly picks the unfinished vertex nearest the centre, reads off the polygons already round it, finds every way the species could be laid over them, and fills the gap — checking as it goes that no edge acquires a third polygon, that no polygon overlaps one already placed, and that the last polygon in the ring closes it exactly. Exactness is available because the coordinates are exact: every polygon that can appear in a surviving species is a triangle, square, hexagon, octagon or twelve-gon, and the cosines those need are ±1, ±½, ±√2/2 and ±√3/2. So a vertex of any of these tilings is a triple of integers in ℚ(√2) or ℚ(√3), and “the ring closed” is a comparison of integers rather than of floating-point numbers within a tolerance.

The exactness is the part worth pausing on. Every other pattern in this collection has rational coordinates in its lattice basis, which is what lets the detector settle a symmetry by comparing fractions. A tiling by regular polygons does not: truncate a honeycomb so that the twelve-gon’s edges match the triangle’s and the cut falls at 2 − √3 along each edge, and a vertex of 4.8.8 sits at 1/(2 + √2) of a cell. Those numbers are exact and they are not fractions.

What they are is quadratic, and that is enough. A number of the form (p + q√d)/r with p, q and r integers can be added, multiplied and divided exactly — division by the conjugate, since d is not a square — and two such numbers are equal exactly when their reduced triples agree. So the ring closes or it does not, with no tolerance introduced anywhere, and the only cost is that the arithmetic needs one more square root than the seventeen wallpaper groups did.

All eleven build. And when the grower is handed one of the four plausible-looking refuted species — the ones made of ordinary polygons, so the arithmetic is available to it — it fails on every one of them, running out of continuations after a handful of polygons.

Eleven refuted, eleven built, twenty-one accounted for. The two roads meet exactly, and neither was told the other’s answer.

Reading across that plate, the eleven sort themselves by how many polygon sizes each of them uses. Three use one — the regular tilings. Six use two. Two use three, and they are 3.4.6.4 and 4.6.12 — the second of which has twelve vertices in its cell, more than any other member of the eleven.

Three sizes is a ceiling, and it is the angle sum that imposes it rather than the parity argument. Four different sizes at one vertex would have to be at least a triangle, a square, a pentagon and a hexagon, and those four terms alone come to 1/3 + 1/2 + 3/5 + 2/3 = 2.1 — past the two the equation permits, before any fifth polygon has been added. So no multiset among the seventeen has four sizes in it, and the search never had to consider one. What the parity argument then does to the three-size species is severe in the other direction: ten of the twenty-one species use three sizes and only two of them survive, because a species with three sizes has the most constrained ring of all — the polygon being walked round has two different neighbours dictated at every corner, which is exactly the alternation an odd ring cannot close.

One of the eleven is worth naming for a reason that has nothing to do with the count. The trihexagonal tiling, 3.6.3.6, has its vertices at the midpoints of a triangular lattice’s edges — take every edge of the triangular tiling, mark its middle, and the marks are exactly the vertices of the trihexagonal tiling with nothing left over. It is also the only member whose two tile shapes are each surrounded entirely by the other: every triangle has three hexagons round it and every hexagon has six triangles, so the tiling is bipartite in its tiles as well as alternating at its vertices. That pair of facts is why it turns up in this collection under three other names, as a lattice with a coset removed, as the dual of the rhombille, and as the arrangement of the sites in a kagome net.

Three of them are older than the question #

The eleven contain the three regular tilings — triangles, squares, hexagons — which are the ones where every polygon is the same. That there are exactly three is the plane’s version of a fact about the five Platonic solids, and it comes out of the same equation with the inequality pointing the other way.

The other eight are the semiregular or Archimedean tilings. Kepler drew all eleven in Harmonices Mundi in 1619, in a plate that also contains several tilings that are not uniform and a good deal of speculation about the harmony of the spheres. He had the list before anybody had the argument, which is the usual order of events; the parity argument that shows the list is complete is nineteenth- and twentieth-century, and the general classification of tilings by their vertex species belongs to Grünbaum and Shephard’s Tilings and Patterns in 1987.

Kepler’s list was right. What was missing for three hundred years was the reason there is no twelfth.

The species does not always decide the tiling #

Here the classification acquires a subtlety that the neat count hides, and it was met here as a bug rather than as a piece of theory.

Take the elongated triangular tiling, 3.3.3.4.4: rows of squares alternating with rows of triangles. Every vertex reads 3.3.3.4.4. Now slide one row of squares half a step sideways. Every vertex still reads 3.3.3.4.4 — and the tiling is a different tiling. Do that independently at every row and there are uncountably many tilings, all with the same vertex species and only one of them periodic.

The snub square tiling, 3.3.4.3.4, does the same thing less obviously, and the grower here found one of its non-periodic variants before it found the periodic one: a patch that was legal at every vertex, exactly closed at every ring, and out of register with itself four rings out.

So “eleven” is a count of something narrower than “tilings whose vertices all read the same”. It is a count of uniform tilings — the ones whose symmetry group is transitive on vertices, so that the vertices are alike not merely in what surrounds them but in the group’s own sense of alike. That is the condition the machinery here checks: the group is detected from the point set, one vertex’s orbit under it is computed, and the orbit has to be every vertex of the cell.

The distinction is exactly the one this collection makes between a pattern’s local rules and its global order, and it is the same distinction that makes Penrose tilings interesting: there, local rules force a non-periodic tiling. Here, local rules fail to force anything.

The definition the eleven are a count of #

The essay’s subtlety — that a species can be realised by more than one tiling — is resolved by a definition, and stating it says exactly what the eleven count.

A tiling is uniform when its symmetry group acts transitively on its vertices: every vertex can be carried to every other by an operation of the tiling’s own group. That is stronger than every vertex having the same species, because it asks for a motion carrying one to another rather than only for the two to look alike locally.

The eleven are the uniform tilings. The non-periodic variants of 3.3.4.3.4 have the right species everywhere and a symmetry group that does not reach from one vertex to another, so they fail the definition — and they are not counterexamples to the count but objects the count was never about.

That is the same move this collection makes whenever a local description and a global one come apart. Local rules do not force a global order; a species is a local rule; and asking for a group to act transitively is asking for something global. The species enumeration produces candidates and the transitivity condition selects among them, exactly as the parity argument refutes among them.

It also says what the grower found. A routine placing polygons to satisfy the species at every vertex is implementing the local condition and nothing else, so finding a non-uniform tiling is the correct behaviour of a correct program answering the question it was actually asked.

Relaxing the condition, and the counts that follow #

Once transitivity is the criterion, the obvious generalisation is to allow more than one orbit, and the resulting counts are known and are worth knowing.

A tiling is k-uniform when its vertices fall into k orbits under its symmetry group — so uniform means k = 1. Relaxing to two gives twenty tilings; to three, sixty-one; and the enumerations have been carried further by computer, with the counts growing steadily rather than exploding.

Every one of them is still built from regular polygons meeting edge to edge, so the Diophantine equation of this essay still bounds what can happen at a vertex — the seventeen multisets and twenty-one species are the alphabet for all of them. What changes is how many different letters one tiling may use.

That gives the eleven a place in a sequence rather than a status as a complete answer. They are the tilings a group can act on with one orbit, and the classification continues upward with no obvious end — which is the ordinary situation for a condition relaxed by a parameter, and worth noticing because the count of eleven is so often quoted as though it closed the subject.

What the round trip checked, and how #

Nothing above rests on a picture being convincing. Four things are checked every time these figures are drawn, and a figure whose check fails does not appear at all.

Polygons that do not fill a turn are not a species. Three triangles come to 180°, and the enumeration must not contain them.

A species the parity argument refutes must also defeat the grower, for each of the four whose polygons the grower can construct. It does, and the two routes share no code.

The same polygons in the wrong cyclic order must not pass as this one. 3.3.4.3.4 and 3.3.3.4.4 hold the same five polygons and both fill a turn. A grower that checks only the angle sum will finish a vertex of the first as the second and never notice. This one compares the cyclic sequence, and the check exists because its absence produced exactly the failure described above — a legal-looking patch with eight vertices in a cell that holds four.

Move a vertex and the group must go. Displacing one vertex of 3.6.3.6 by a seventh of a cell takes its twelve operations to two.

Where the exactness stops #

Three boundaries, and they matter because this subject is full of near-misses.

Edge to edge is an assumption, not a theorem. Every tiling here has each edge shared by exactly two polygons along its whole length. Drop that and squares of one size can meet squares of another halfway along, the angle equation no longer describes a vertex, and the count is not eleven — it is not finite in any useful sense. The brick wall is the smallest counterexample and it is a tiling by squares that is not in the list.

“Every vertex alike” was strengthened silently and then unsilently. The count is of uniform tilings, in the group-theoretic sense above. Counting tilings whose vertices all read the same species is a different and much larger question, and for two of the eleven the answer is uncountable.

Nothing here says anything about tilings by irregular tiles. The moment the polygons are allowed to be merely convex, the classification collapses: every triangle tiles, every quadrilateral tiles, and the question of which pentagons tile was open until 2017. Regularity is not a mild simplifying assumption; it is the entire reason there is a finite list.

The generalisation, and where it goes badly #

The same equation with the sum less than 2 describes polygons meeting on a sphere, and gives the five Platonic solids and the thirteen Archimedean solids. With the sum greater than 2 it describes the hyperbolic plane, where the answers are infinite in number — {3, 7} and {7, 3} and everything past them — and where the tilings this collection meets as bad orbifolds live.

The plane is the boundary case, and boundary cases are where the finite lists are.

Where the ladder goes next #

The eleven are built. What has not been asked yet is what symmetry each of them has — the vertex set of a uniform tiling is a plane pattern like any other, and this collection’s detector can be handed it and asked which of the seventeen it is. The answer is smaller than eleven and the reason is worth an essay of its own.