An aperiodic monotile, visually

I printed a sheet of hats on Saturday morning and cut out forty of them with kitchen scissors, which is not how I expected to spend a weekend at my age. Five of them had to be flipped over, printed side down, because of something I’ll get to. By lunchtime I had a patch about the size of a dinner plate on the dining table, and I’d managed to convince myself, wrongly, three separate times that I’d found a repeating pattern in it.

The shape is from An aperiodic monotile, a paper posted to arXiv on March 20th by David Smith, Joseph Samuel Myers, Craig Kaplan and Chaim Goodman-Strauss. It answers a question that’s been open for about sixty years: is there a single shape that can tile the whole plane, but only in a way that never repeats? People call that an “einstein”, which is a German pun (ein Stein, one stone) and has nothing to do with Albert. The answer is yes, and the shape is called the hat, because it looks a bit like one if you squint, or like a T-shirt if you don’t.

I’ve been reading the paper on and off for three weeks. It’s 89 pages and most of it is beyond me, but the first two sections are written for people like me, and there’s one argument in section 3 that’s short and beautiful and that I could follow with my undergraduate math, so this post is my attempt to draw what I understood.

Tiling, periodic and aperiodic

A tiling is a way of covering the whole infinite plane with copies of some shapes, rotated and moved however you like, with no gaps and no overlaps. Squares tile the plane. So do regular hexagons, and lots of irregular shapes.

A tiling is periodic if you can slide the whole thing some distance in some direction and it lands exactly on itself, like a bathroom floor. Squares obviously tile periodically. But squares can also tile non-periodically: take one row and shift it over by a third of a square, and the rows no longer line up across that line, and no slide maps the whole tiling onto itself. So “can tile without repeating” is easy. The hard question is about shapes that can’t tile any other way. A set of tiles is aperiodic if it tiles the plane, but every single tiling it allows is non-periodic. No matter how you lay them, you can never fall into a repeating pattern.

The history of that question starts in computer science, which I didn’t know. In 1961 Hao Wang was studying square tiles with colored edges, as a way of encoding logic problems, and conjectured that any set of tiles that can tile the plane at all can also tile it periodically. If that were true, there’d be an algorithm to decide whether a set of tiles tiles the plane: keep trying bigger and bigger patches until you either get stuck or find a repeating block. In 1966 Robert Berger showed the conjecture was false by constructing an aperiodic set, and with it that the tiling problem is undecidable, in the same family as the halting problem. Berger’s set had 20,426 tiles.

After that it was a game of getting the number down. Raphael Robinson got it to six in 1971. Roger Penrose got it to two in the 1970s, the famous kites and darts, and the rhombs. And then it stuck at two for nearly fifty years. There have been near misses. Joshua Socolar and Joan Taylor found a single hexagonal tile around 2010 that forces aperiodicity, but only with extra matching rules about which edges can touch, and when you turn those rules into shape you get a tile that’s not connected, a tile made of separate pieces. Whether one ordinary shape, a single connected piece with no rules except “no gaps and no overlaps”, could do it was the open question.

The hat

Here it is. The hat is a polykite: take the tiling of the plane by hexagons, cut each hexagon into six kites by joining its center to the middles of its edges, and glue eight of those kites together.

It has 13 sides. If the kites’ short edges have length 1, the hat’s sides have lengths 1, 2 and √3 (the 2 is two short kite edges in a straight line), and because it’s eight kites with area √3 each, its area is 8√3. I checked that with the shoelace formula on the vertex coordinates, which is how I spent some of Saturday afternoon after the scissors, and it’s also how I drew the diagram.

Smith is a hobbyist, a retired print technician from Yorkshire by the accounts I’ve read, who explores tiling shapes for fun with a program called PolyForm Puzzle Solver. He found the hat last November, couldn’t get it to repeat, couldn’t get it to stop either, and emailed Kaplan, who has software for exactly this. The paper says Kaplan’s software showed that if the hat couldn’t tile the plane, its Heesch number would have to be at least 16, meaning you can surround it with at least 16 complete rings of copies before you get stuck, and Myers’ software showed that if it could tile periodically, the repeating unit would need at least 64 tiles playing different roles in its repeating unit. Either answer would have smashed an existing record by a wide margin, which is when they knew they had something.

Why I flipped five of them

The hat is asymmetric, so it has a mirror image, and you have to use both. In every tiling by hats, some of the tiles are reflected. They’re sparse, they’re spread out fairly evenly, and in the patches the authors computed, each reflected hat is surrounded by the same “shell” of three ordinary ones. That’s where my five flipped tiles out of forty went, although I placed mine by trial and error and I wouldn’t swear my patch was legal at the edges.

This has turned into the main argument about the result, in the comments I’ve read anyway. If you’re cutting tiles out of paper, flipping one over is free. If you think of the tiles as physical objects with a top and bottom, a floor tile with a glaze say, then the hat needs two kinds of tile and you’re back to a set of two, and some people have said it doesn’t count. The authors’ position, and the usual definition in the field, is that reflections are allowed, since a reflected hat is congruent to the original. I agree with them, but I do think it leaves an obvious next question, which is whether there’s a shape that’s aperiodic using only rotations and slides, with no mirror images at all. As far as I can tell that’s still open, and I’d guess a lot of people are looking right now.

How they proved it

There are two proofs in the paper, and they’re very different.

The first one found, which is the second in the paper, is the classical kind. They show that in any tiling, the hats group themselves into clusters of four types, which they then simplify to four outlines called metatiles, named H, T, P and F after their rough shapes. Then they show that the metatiles can only fit together as parts of slightly bigger copies of the same four shapes, called supertiles, and those can only fit together as parts of bigger ones again, and so on forever. A tiling with that kind of unique hierarchy can’t be periodic, because sliding it would have to preserve a structure that has no repeating unit at any scale. Each level is bigger than the last by a factor of φ², the golden ratio squared, which surprised the authors too, since nothing about a grid of hexagons and kites suggests five-fold anything. Part of this proof is a computer-checked case analysis, done twice by two of the authors in independent implementations.

The second proof is the one I could follow, and it starts from something odd. The hat has two kinds of edges, the ones of length 1 and 2 (multiples of the short kite edge), and the ones of length √3. They point out that you can change those two lengths independently and you still get a closed 13-sided shape. Call it Tile(a, b), where a replaces 1 and b replaces √3. The hat is Tile(1, √3). Here’s what the family looks like:

Smith actually found the turtle, Tile(√3, 1), separately and sent it to the others as a second candidate, and the family was how they discovered the two were related. The paper proves that every Tile(a, b) except the three marked “periodic” above tiles the plane in essentially the same way as the hat. The two ends of the family are where the proof comes from. Tile(0, 1) is a shape made of four equilateral triangles and Tile(1, 0) is made of eight. Both live on the ordinary triangular grid, and both tile periodically, nothing special.

The argument goes like this. Suppose you had a periodic tiling by hats. Because the family members all fit together the same way, you could shrink one kind of edge to zero in that tiling and get a tiling by the four-triangle shape, or shrink the other kind and get a tiling by the eight-triangle shape, and both would be periodic too, with the same pattern of repeats. Their lattices of repeats would then have to be related by a similarity, a rotation and a scaling, and since one tile has twice the area of the other, the scale factor would have to be √2. And they show that no similarity between lattices on the triangular grid can scale by √2. So there’s no periodic hat tiling. Add the separate construction showing the hat tiles at all, and it’s aperiodic.

The paper’s version is more careful than that, and I’m leaving out the steps that make the “you could shrink the edges” part legitimate. But the last step I could check myself, and I think this is why it works. On the triangular grid, with spacing 1, the squared length of any vector from one grid point to another is m² + mn + n² for some integers m and n. Those are the norms of the Eisenstein integers, which I last thought about in a number theory class in college, and there’s a classical fact about which numbers you can write that way: exactly the ones where every prime that leaves a remainder of 2 when divided by 3 appears an even number of times. 2 is such a prime. So if v is a grid vector with squared length N, scaling it by √2 gives squared length 2N, and the power of 2 in N and in 2N can’t both be even. One of them isn’t a grid vector. No √2 similarity can map grid vectors to grid vectors. I was very pleased with myself for about ten minutes until I realized this is probably the first thing anyone in the field would think of.

Why it’s a big deal

Honestly, mostly because it was open for so long and the answer is so simple. You can explain the hat to a ten-year-old, and the shape was found by someone playing with shapes. A lot of the mathematicians on my Twitter seem equal parts delighted and annoyed that nobody found it in the 1970s. The kites and hexagons were all there.

There might be applications. Penrose tilings turned out to be a good model for quasicrystals, the materials Dan Shechtman found in 1982 that have ordered, non-repeating atomic structures, which won him the 2011 Nobel Prize in chemistry. A single tile that forces aperiodicity seems like it ought to say something about materials that could form that way from one kind of building block, but I’m not a materials scientist and I’ve seen no one claim that yet, so treat it as a guess.

The part I like best, as a programmer, is Berger. One big reason anyone cared about aperiodic tiles in the first place was that Wang’s conjecture would have made tiling decidable, and an aperiodic set is the scaffolding Berger used to encode a running computation in floor tiles. Getting from 20,426 tiles to one doesn’t change anything about decidability, which was settled in 1966. What I’d like to know, and haven’t seen anyone say, is whether you could do Berger’s trick with copies of a single shape, a computer made entirely of hats.