One tile, and no period

Every aperiodic pattern this collection has drawn needs at least two shapes. Penrose’s tiling has two rhombs, the Fibonacci chain has two intervals, the cut-and-project construction has a window that produces two spacings. The obvious question is whether one shape could do it — cover the plane, and cover it only without a repeat — and it was open from 1961, when Wang asked it in a different form, until March 2023.

Both of this site’s essays on the subject mention the answer in a sentence and compute nothing about it. What follows is what those sentences owe.

The grid it lives in #

A tiling problem over the whole plane is a search over a continuum, and the first thing to do with it is to make it discrete. The construction that does so here is old and is already in this collection: divide every hexagon of the hexagonal tiling by joining its centre to its six vertices and its six edge midpoints. Each hexagon falls into six kites, and the result is a tiling by one quadrilateral — the Laves tiling [3.4.6.4], the dual of the semiregular tiling whose vertices are three, four, six and four.

The kite has sides of two lengths, a half and root three over two, and that single fact is why the shape at the top of this page has sides of two lengths. A shape assembled from kites cannot have a boundary made of anything else.

The grid also makes the arithmetic exact. Every corner of every kite is a hexagon centre, a hexagon vertex or an edge midpoint, and all three lie on a sixth of the hexagon lattice — so multiplying every coordinate by six turns the whole subject into integers, and two placements of a tile either coincide or they do not. There is no tolerance anywhere in what follows, which is the condition this collection asks of any claim it is willing to call decided.

What was searched #

A shape made of eight kites is an octakite, and there are not many. Growing them one cell at a time and identifying two whenever a translation and one of the twelve rotations and reflections carries one onto the other gives 1, 2, 4, 10, 27, 85, 262 and then 873 — a list short enough to examine one shape at a time.

The filters applied to it mention aperiodicity nowhere. They are these, in order:

1. Simply connected. A shape with a hole in it is dropped, and the test is that its boundary is one closed loop rather than two. 845 survive.
2. Tiles a small patch. Cover every kite of a one-ring core of hexagons exactly once, with tiles allowed to hang over the edge. 314 survive.
3. Tiles a larger one. The same with a two-ring core. 60 survive.
4. Has no periodic tiling. For every translation lattice of index up to sixteen, ask whether the shape tiles the corresponding torus. 21 survive.
5. Tiles a four-ring core — fifty-six tiles. One survives.

The survivor has thirteen sides, sides of length one half and root three over two with a single side of twice the shorter, and angles that are 90, 120, 240 and 270 degrees. It is the hat, announced by David Smith, Joseph Myers, Craig Kaplan and Chaim Goodman-Strauss in March 2023 — recovered here rather than copied, which matters because a shape traced from a picture is a shape whose properties have to be taken on trust.

The order of the filters is doing a great deal of work and it is worth reading off the numbers. The step that removes most of the candidates is the second — 845 shapes down to 314 — and it is the cheapest test in the list: cover a one-ring core, twelve hexagons’ worth of kites, and give up on anything that cannot. The step that removes the last candidates is the fifth, and it is the most expensive by a wide margin. That ordering is not an accident of how the code was written; it is the only order that makes the search finish, because an exact cover of a four-ring core costs a few hundred times what an exact cover of a one-ring core does and there is no point paying it eight hundred times over.

And no filter mentions the property the shape is famous for. Filter four asks whether a shape tiles a small torus, which is a question about periodic tilings; filters two, three and five ask whether it covers a region, which is a question about tilings of any kind. Aperiodicity is what is left when the two questions are asked together and the answers disagree — tiles a large patch, tiles no small torus — and stating it that way is what makes the search a search rather than a demonstration. Nothing in it knows what it is looking for.

The patch, and how little searching it takes #

The covering search is an exact cover: take the uncovered cell with fewest remaining placements, try each of them, and go back when a cell has none. On most shapes that search thrashes. On this one it barely runs.

Fifty-six tiles cost sixty-six placements — barely more than one decision per tile, and almost no backtracking at all. That number is worth pausing on, because it is the computational shadow of the property the shape is famous for. A tiling that had freedom in it would offer the search many choices at each step and it would have to try them; a tiling that is forced offers one, and the search walks straight through. The hat’s tilings are forced nearly everywhere, and the searching is cheap because there is so little to search.

The same number read the other way is a warning. A cheap search is a search that found a covering, not a typical one and not all of them. Everything measured off this patch — the proportion of reflected tiles, the shapes of the neighbourhoods, the way the two handednesses are distributed — is measured off the first covering the search happened to reach, and a different tie-breaking rule would have reached a different one. That is why the claims made from it below are of the form reflected tiles are present and are a minority of about this size rather than the proportion is this number. The proportion in the plane is a theorem about all tilings; a patch is one tiling, seen once.

What “no period” here means, exactly #

The fourth filter deserves its own statement, because a claim about periodicity is where a bounded search is easiest to over-read.

A tiling of the plane invariant under a lattice of translations descends to a tiling of the torus obtained by dividing the plane by that lattice. So asking whether a shape has a periodic tiling with a given translation lattice is a finite question: tile the torus, or run the search to exhaustion and find that it cannot be done. That is a decision, not a failed attempt.

Index sixteen is not an arbitrary stopping point and it is also not a large one. A translation lattice of index n gives a torus of six n kites, which holds three quarters of n hats — so the rows that exist are the indices at which that comes out whole, and the largest of them is a repeat of twelve tiles on ninety-six kites. Doubling the bound multiplies the work by much more than two, since both the number of lattices and the size of each torus grow with it, so the bound is where the arithmetic stopped rather than where the interest did. Every lattice up to it is run to exhaustion, which is the part that matters: none of these rows is a search that gave up.

Sixteen is the bound, and the bound travels with the claim. What has been established is that the hat has no periodic tiling whose translation lattice has index sixteen or less — twenty-four, forty-eight, seventy-two and ninety-six kites, three to twelve tiles per repeat. What has not been established is that it has no periodic tiling at all, which is a theorem with two published proofs and is not the kind of thing a search produces. Nothing decides whether a set of tiles tiles the plane is the essay about that gap, and its rule holds here without amendment: the bound is never an answer.

The shapes that nearly made it #

Seventeen octakites cleared every filter except the last. Each of them tiles a two-ring core and has no small periodic tiling — every property the hat has, at the resolution the earlier filters see — and each of them fails at four rings, where the exact cover runs to exhaustion and returns nothing.

Those seventeen are the reason to distrust a small patch, and the distrust generalises well past this search. A shape can be surrounded by copies of itself once, and twice, and tile nothing; Heesch numbers exist precisely because local success is not global success. Every one of the seventeen is a small counterexample to an argument nobody would otherwise think to check.

Three further shapes are neither refused nor accepted. The covering search is given a step limit, and on three of the twenty-one it was still running when the limit arrived. They are reported as undecided at this bound rather than assigned to either column, which is the same discipline the periodicity filter is under: a search that ran out of room has said nothing, and a table that quietly turned it into a no would be a table with one wrong row and no way of knowing which.

The reflection, which is not a convenience of the drawing #

Eight of the fifty-six tiles in the patch above are reflected. That is not the search preferring variety: the copies of the hat that tile the plane come in both handednesses, in a proportion, and without the reflected ones there is no tiling at all past a very small region.

That is the property the next rung of this ladder is about, and it is also the one that troubled the result when it appeared: a shape and its mirror image are the same shape to a mathematician and are two different objects to anyone cutting them out of a sheet. The tile that needs no reflection takes up what happened next.

The proportions are measurable here, roughly. In the tilings of the whole plane the ratio of unreflected to reflected hats is the fourth power of the golden ratio, about 6.854 — a published value, and a number with the same flavour as the ratio of long to short tiles in every quasicrystal this site has drawn.

What the family says #

The hat is one member of a family, and the family is what turns a curiosity into a construction. Keep the thirteen turns and let the two side lengths vary: every member closes, because the turns sum to a full circle whatever the lengths are.

The two ends of that family are ordinary shapes that tile periodically. Everything strictly between them is not, and the argument that establishes it is combinatorial rather than metric: the tilings of any two members correspond, tile for tile, so a periodic tiling of one would give a periodic tiling of all. That is quoted here, not computed — the deformation argument is the substance of the 2023 paper and it is not what a covering search sees.

Why this was hard, and why it looked easy afterwards #

The shape is small. Eight kites, thirteen sides, and a search over 873 candidates that a laptop finishes in a couple of minutes. The obvious question is why sixty years passed.

Part of the answer is that nobody knew where to look. A monotile could have had a hundred sides or lived on no grid at all; the space of candidate shapes is not a list, and the polykites are a list only because somebody guessed that the answer might be a polyform on the kite grid. Smith found the hat by hand, cutting shapes out and pushing them about, and the computation came afterwards, to check what the paper cutting had suggested.

The other part is that the search above proves nothing. It says the hat tiles patches of the size it was asked for and that it has no small periodic tiling, and both statements would be equally true of a shape that tiled the plane periodically with a repeat of a thousand cells. What was actually needed was a hierarchical argument — showing that any tiling by hats organises itself into clusters that behave like hats at a larger scale, indefinitely — and that argument is the paper. This collection has the same shape of argument already, in inflation: a tiling that reproduces itself at a larger scale cannot have a smallest period, because a period would have to survive every inflation and periods do not shrink.

Where the exactness stops #

Three things here are computed and one is not, and the difference is worth stating plainly.

Computed: that the shape is the unique octakite passing the filters; that it covers cores of one, two and four rings with every cell covered exactly once; that it has no periodic tiling at any of the translation lattices of index up to sixteen; that unreflected copies cover one ring and cannot cover two; and the proportion of reflected tiles in each patch drawn.

Not computed, and quoted: that the hat admits tilings of the plane, and that every one of them is non-periodic. Neither follows from a bounded search, and this collection’s own account of undecidability is the reason to say so loudly rather than in a footnote. The hierarchical proof, and the second proof by deformation into the family above, are due to Smith, Myers, Kaplan and Goodman-Strauss.

The gap between those two lists is exactly the gap the seventeen near misses live in, which is the best argument for keeping it visible.

Who found it, and when #

Wang posed the question in 1961 in terms of edge-coloured squares and conjectured that no aperiodic set existed. Berger refuted the conjecture in 1966 with a set of over twenty thousand tiles, and the count fell for decades: Robinson to six, Penrose to two in 1974. Two stood for nearly fifty years.

David Smith, a retired printing technician, found the hat in November 2022 by cutting shapes from card. Joseph Myers, Craig Kaplan and Chaim Goodman-Strauss joined him, and the announcement came in March 2023 with two independent proofs. Within two months the same four announced the spectre, which settles the question the next rung is about.

What the proof of aperiodicity actually does #

The search on this page ends where the interesting claim begins, and it is worth saying what the quoted half consists of, because it is not a bigger search.

Two independent proofs were given. The first is hierarchical: groups of hats are shown to combine into a small set of larger clusters, those clusters combine into larger ones by the same rule, and the substitution continues without limit. A tiling admitting such a hierarchy cannot be periodic, because a period would have to survive every level of it and the clusters grow without bound. That is the same shape of argument the Penrose tilings use, and it is the one a reader of matching rules and forcing will recognise.

The second is the one that came out of the family. The hat sits in a continuous family Tile(a, b) of combinatorially identical shapes, and the two ends of that family — where one of the two edge lengths goes to zero — are ordinary shapes that tile periodically, in two different ways. Any tiling by the hat can be deformed into a tiling by each end member, so a periodic hat tiling would produce periodic tilings of both ends with a common combinatorial structure; and those two structures are incompatible. The contradiction is combinatorial and needs no hierarchy at all.

Neither proof is a computation over patches, and that is the point of separating them from the search above. A search establishes that a shape covers a bounded region and that nothing small repeats; it cannot establish a statement about every tiling of the whole plane, and the seventeen near misses are the standing demonstration of how convincing a bounded search can be while proving nothing.

The near misses that came before it #

The question had been narrowed for decades, and the partial results are worth naming because each of them shows what “one tile” was doing.

The Socolar–Taylor tile of 2010 is a single hexagonal shape with decorations on it, and the decorations force aperiodicity — but the matching rules are between tiles that do not touch, so realising them geometrically means turning the tile into a disconnected shape. A disconnected tile is a tile in a technical sense and not in the sense the question was asked in, and the result was universally reported as a step rather than an answer.

Aperiodic pairs kept falling in number — Penrose’s two shapes, and several other pairs found since — and each reduction sharpened the question without touching it, because two is not one and no argument bridged the gap.

And nothing forbade one. No theorem said a single aperiodic tile was impossible; the question was open in the strict sense, and the general expectation was simply that if one existed somebody would have found it. That expectation is why the answer’s shape was a surprise twice over: the tile is small, made of eight kites of a grid anybody could have searched, and reachable by a search of the kind run above. It was found by cutting card.

Where the ladder goes next #

Sideways, to the two-shape results this one supersedes without diminishing: matching rules and what actually forces aperiodicity is the argument that a decoration, not a shape, was doing the work in the Penrose case — which is exactly what the hat does not need.

Upwards, to the reflection. The tile that needs no reflection measures how badly the hat needs its mirror image, and what a shape has to look like to do without one.

And outwards, to the question underneath all of it. Nothing in this essay decides whether a given shape tiles the plane, because nothing does. What a search can do is produce a candidate and bound what it has failed to find, and saying which of the two has happened is the whole of the method.