A tiling of the whole plane, decided on one tile's edge

A shape either tiles the plane or it does not, and no algorithm decides which. That result is about sets of tiles rather than single ones, and the single-tile question is not known to be undecidable — but nor is it known to be decidable, and after sixty years of people looking, the honest position is that nobody has a procedure.

What exists instead is a sufficient condition, and its shape is remarkable. It reads the tile’s boundary, which is a closed path of a few dozen unit steps, and nothing else about the tile: not its area, not its symmetry, not what it looks like. When the condition holds, the shape tiles — and the condition hands over the group that does it.

The condition is Conway’s criterion, from around 1975, and it is stated in one sentence. Cut the boundary into six consecutive arcs A B C D E F such that D is the arc A traversed backwards — so D is a translate of A — and each of B, C, E, F is carried onto itself by the half turn about its own midpoint. Any of the four may be empty. If that cut exists, the tile tiles the plane.

What the two conditions say about a curve #

The two halves of the criterion are two different statements about arcs, and both are easier to see on the boundary word than in words.

D is A backwards. An arc traversed backwards is the same curve with every step turned round, so requiring D to equal A read that way is requiring the two arcs to be the same piece of curve at two places on the boundary, related by a translation. That translation is the one that will carry the tile onto a neighbour.

B is its own half turn. Rotating a path by half a turn about its own midpoint swaps its two ends and reverses the direction of travel. Do both and every step comes out as it went in — so the condition is that the arc’s word is a palindrome in its step letters, and nothing more exotic. A single edge is a palindrome of one letter, which is why so many shapes satisfy the criterion with three of the four arcs a single step long.

That is a local condition in the strictest sense. It is a statement about a bounded curve, checkable in a time that depends on the boundary’s length and not at all on the plane. What it forces is global: a covering of an unbounded surface, exactly once, for ever.

The group the cut names #

The reason the criterion works is that the cut is not a certificate of a tiling — it is a construction of one. The five arcs it distinguishes give five motions:

• the translation t taking A to D;
• the half turns about the midpoints of B, C, E and F.

Those generate a group, and the orbit of the tile under that group is the tiling. Every plane group they can generate is p1, p2 or a group containing one of them, so the tiling is by translations and half turns and never by anything else — which is a strong statement about what kind of tiling a boundary condition can force.

This site never draws a pattern by hand, and a tiling is a pattern. So the figure above is built the way every wallpaper plate here is built: the group is closed up, the tile’s orbit is generated, and the result is checked — cell by cell, over a stated window, with the counts of single, double and empty coverage printed underneath. A criterion that promises a tiling and cannot produce one is a criterion nobody should believe, and the difference costs a few lines of code.

Three tiles, three cuts #

The criterion is easiest to trust after watching it work on shapes whose tilings are already familiar.

Its boundary is twelve steps long and the cut uses all six arcs, which is less common than it sounds. Most certified polyominoes leave one or two of B, C, E and F empty and get by with a translation and a couple of pivots; the L-tromino above manages on five arcs. The Y needs the whole apparatus, and it needs it precisely because it has no symmetry of its own to do any of the work.

Sixteen copies cover the eighty-one cells of that window exactly once each: nothing doubled, nothing bare. The count is the only reason to believe the picture. A plate of interlocking shapes is persuasive at a glance, and a tiling that fails does so at one cell in a hundred rather than everywhere at once, which is exactly the failure a glance is worst at.

The U’s boundary is twelve steps, like the Y’s, and it too uses all six arcs. What differs is where the arcs fall: the notch pulls two of the pivot points down into the concavity, which is the last place somebody fitting tiles by hand would think to look for them. The word does not know it is looking at a notch, and that indifference is the whole reason a boundary condition is cheaper than a search.

How many shapes it settles #

A sufficient condition is worth exactly as much as the fraction of cases it settles, and that fraction can be measured. Every polyomino of up to eight cells — five hundred and thirty-three of them, counted by growing shapes one cell at a time — is put through three separate questions.

The second column deserves its own sentence, because it is the one that is exhaustive rather than sufficient. An isohedral tiling — one whose symmetry group carries any tile to any other — has a translation lattice, a point group of order at most eight (the grid of cells admits no other), and one orbit of tiles. So one cell of the translation lattice holds at most eight tiles, and its area is at most eight times the tile’s. Every candidate lattice, point group and set of translation parts inside that bound is finite in number, so the search over them terminates and its negative answer means something. No isohedral tiling exists here is a result, not a failure to find one.

The gap, measured #

Set the criterion’s column against the exhaustive one and the difference is the criterion’s own limitation, in numbers.

The gap is thirty-two shapes out of five hundred and thirty-three, and it is worth reading that number in both directions. Thirty-two is small: the criterion settles four hundred and seventy of the five hundred and two shapes that tile isohedrally, so a boundary test of one sentence gets ninety-four per cent of the way to an exhaustive search. Thirty-two is also not zero, and every one of them is a shape that visibly tiles while the criterion declines to say so — which is what a sufficient condition looks like from the inside, and why the column headed criterion can never be the column headed tiles.

The reason for the gap is the reason the criterion is simple. Its five motions can only generate a group whose rotations are half turns. A tile whose tilings all use a four-fold or a three-fold rotation is outside its reach by construction, however obviously it tiles. Widening the criterion to cover those means adding more cut patterns — and the full list of boundary conditions for isohedral tilings, worked out by Keating and Vince and by Myers, runs to nine of them rather than one. That is the price of necessity.

What a boundary cannot see #

Two facts about the census are worth separating, because they are the shape of every honest report of this kind.

Some shapes have no boundary word at all. A polyomino with a hole has two boundary curves, and one that touches itself at a corner has a curve that visits a point twice. Neither can be cut into six consecutive arcs, because “consecutive” presumes a single simple closed curve. Seven of the five hundred and thirty-three are like that. They are counted in the census and refused a criterion, rather than being quietly given the outer curve and treated as though the inner one were not there.

One shape tiles the plane and has no isohedral tiling at all. It is the eight-cell shape in the next essay, and it is the reason the third column of the census exceeds the second by exactly one.

Who stated it, and why it was never published #

John Conway stated the criterion in conversation in the early 1970s and never wrote it down. It reached print through others — Doris Schattschneider’s 1980 account is the one usually cited, and Marjorie Rice, an amateur working from Scientific American, had been using something very like it to find new pentagons that tile. That provenance is not a curiosity. A criterion whose whole content is cut the boundary into six arcs is the kind of thing that is more useful to hand somebody than to publish, and its history is a record of people passing it round because it made a hard search tractable.

What made it tractable is worth stating precisely. Before the criterion, checking whether a proposed tile tiled meant trying to build a patch and seeing whether it closed up — a search with no bound on it, where failure meant not yet. After it, a large class of cases became a finite test on a string of a few dozen letters. The gap between those two situations is the difference between a hobby and a programme, and Rice found four new tiling pentagons inside it.

The criterion also says how the tiling goes together, which a mere existence result would not. The translation from A to D is the offset at which the tile meets its own translate; the four half turns are where neighbours pivot. Anybody who has fitted a jigsaw by trial knows the two moves; what the criterion adds is that those two are enough, and that whether they suffice is decided before any fitting is done.

How many tilings, and how few #

A shape the criterion certifies has at least one tiling. It usually has more than one, and the census’s second column quietly counts something narrower than it appears to.

The exhaustive search finds isohedral tilings — those whose group carries any tile to any other. A shape may tile in ways that are not isohedral as well, and most do: shift one row of a brick wall and the tiling is still a tiling, and no longer has a group acting transitively on its bricks. Such tilings are not counted anywhere in the table, because they are not finite objects to enumerate: a brick wall has a continuum of them, indexed by how far each row is shifted.

That is worth keeping straight, because it is the distinction this whole family of results turns on. Tiles the plane is one question. Tiles the plane in a way a group describes is another, and only the second is a finite search. The criterion answers the second and thereby settles the first, which is the only direction the implication runs.

Where this sits among the tiling results #

The criterion belongs to a family of statements this collection has met before, and the family is worth naming.

Which convex polygons tile is a classification: every triangle, every quadrilateral, three families of hexagons, fifteen kinds of pentagon and nothing with seven sides or more. That is a complete answer to a restricted question.

Every quadrilateral tiles the plane — convex or not, and with no condition on its angles — and the proof of that is Conway’s criterion with A and D empty and all four of B, C, E and F single edges. A single edge is a palindrome of one letter, so the four palindrome conditions are satisfied by the shape merely having four sides, and the two empty arcs cost nothing because the criterion allows them to be empty. The four half turns about the edge midpoints generate p2, and the quadrilateral’s orbit under p2 is the tiling. So the classical theorem about quadrilaterals is not an analogue of the boundary criterion; it is the criterion’s most degenerate case, and it is where the half turns in the criterion came from in the first place.

Whether a set of tiles covers the plane is undecidable, and what is available there is two half-searches that between them leave a residue nothing settles. The criterion here is the opposite kind of object: not a search that might not terminate but a test that always terminates and sometimes declines to answer. Both are honest responses to a hard question and they fail in different directions.

There is a third kind of tiling question worth holding up beside those two, because it shows how cheaply finiteness can be bought. Require every vertex of a tiling by regular polygons to look like every other and an infinite question collapses into an equation in a handful of integers, whose solutions are a list of eleven. That is finiteness obtained by assuming a symmetry: the assumption does the work, and what is enumerated afterwards is a consequence of it rather than a fact about tiles. Conway’s criterion is trying to do without the assumption. It reads one tile’s boundary and says nothing whatever about what the tiling looks like at a vertex, which is why its answer is a sufficient condition rather than a list.

What the criterion is really doing #

Underneath the arcs there is one idea. A tiling is a global object. What the criterion supplies is a local certificate: a finite amount of information, read off a bounded piece of the plane, that forces the global object into existence.

Certificates of that kind are not always available. Matching rules on a Penrose tiling are local conditions too, and what they force is a covering with no period anywhere — so a local rule can compel a global structure without compelling a repeating one. And a set of Wang tiles carries local rules whose global consequence no procedure extracts at all.

Between those, Conway’s criterion is the comfortable case: local information, global consequence, and a construction rather than an existence proof. The uncomfortable case is next.

What a shape is, for this purpose #

One definition has been used throughout without being stated, and stating it explains what the criterion is doing.

For the criterion, a shape is its boundary word and nothing else. Two shapes with the same boundary word are the same input; a shape with a hole has no such word and is refused; a shape whose boundary touches itself at a corner is refused for the same reason. That is a much narrower object than a tile, and its narrowness is the point — a condition on a narrow object is cheap to test.

What the narrowing throws away is the area. The criterion never asks how large the tile is, and it never needs to: a tiling of the plane by translations and half turns has one tile per fundamental domain of the group, and the group the cut produces has a fundamental domain of the tile’s own area by construction. The area takes care of itself, which is why an argument that never mentions it can still produce a covering that fits exactly.

The complete boundary criterion, of which Conway’s is one case #

Conway’s criterion cuts the boundary into six arcs with two relations. That is one arrangement among a finite list, and the list is what turns a sufficient condition into a complete one.

An isohedral tiling identifies each edge of a tile with an edge of a neighbour, by a motion of the tiling’s group. Which motions can appear, and in which patterns round the boundary, is a finite classification — Heesch worked it out, and it comes to twenty-eight types for a tile in the plane, each specifying how many arcs the boundary is cut into and which motion relates which pair.

Conway’s criterion is one of those types, or rather a family of them: the six-arc cut with a translation and four half-turns. The shapes it misses are shapes whose isohedral tilings use one of the other arrangements — a boundary cut into four arcs, say, or one relating arcs by a glide rather than a half turn.

So the exhaustive column of the census is not doing something of a different kind from the criterion. It is running the same test twenty-eight times, once per arrangement, instead of once. The criterion’s virtue is that its one arrangement covers most shapes and is short enough to check by eye; the exhaustive test’s virtue is that its list is complete, so a negative answer is a proof and not a failure to find.

That distinction is the same one this collection keeps drawing between a sufficient condition and a classification, and it is worth noticing that here the gap between them is a factor of twenty-eight rather than a difference of principle.

What the test costs #

A criterion checkable in a time depending only on the boundary is a strong claim, and the exhaustive version is nearly as strong, which is not obvious.

Deciding whether a polyomino tiles the plane isohedrally is a search over cuts of its boundary word, and a boundary of n steps has on the order of n choices per cut point. Running the twenty-eight arrangements over all placements of their cut points is polynomial in n — a few powers of it, depending on how carefully the arrangements are organised — and algorithms doing it in low degree are known.

That puts the isohedral question in an entirely different class from the general one. Whether a shape tiles the plane at all is not known to be decidable; whether it tiles isohedrally is decidable in polynomial time from the boundary alone, with no search of the plane anywhere. The whole difficulty of the general question lives in the tilings that are not isohedral, which is why the eight-cell shape of the next rung matters more than its size suggests.

And it is why the census on this page has three columns rather than two. The first is a cheap sufficient test, the second an exhaustive decidable one, and the third — whether the shape tiles at all — is a question no column can be filled in for in general.

Where the ladder goes next #

The census above has one shape in the third column that is not in the second, and it is the whole of the next rung: a tile that covers the plane and never with one orbit. Congruence of the tiles turns out not to imply transitivity of the group, and Hilbert asked whether that could happen before anybody had an example.

The other direction is the one this essay has been circling. A criterion that always terminates and sometimes declines is a good bargain when the alternative is a search that may not terminate at all — and how many rings of copies a shape that tiles nothing will still accept measures exactly how much local success a global impossibility permits.