An Aperiodic Monotile Exists!

Actual aperiodicity news on The Aperiodical!

This is probably the biggest aperiodicity news we’ll ever cover here: David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss have produced a single shape which tiles the plane, and can’t be arranged to have translational symmetry.

And it’s so simple!

The “hat” aperiodic monotile.

Geometers have been looking for a shape with these properties for over 60 years, and until this example was found it wasn’t clear that one would exist at all.

The tile is made of eight kites – the shape you get by cutting a hexagon up through the midpoints of its edges.

In fact, they show that there’s a whole continuous family of aperiodic monotiles, obtained by changing the lengths of the edges in the shape shown above. Here’s an animation by Craig Kaplan showing a continuous transformation through the whole family:

Note that there are three points in the animation where the shape is degenerate (at the start, middle and end) because two adjacent edges become parallel, and those shapes can tile periodically.

The authors have put together a website to accompany their paper proving the shape is an aperiodic monotile. Have a go at reading the paper: it’s really well written, and starts with a detailed introduction describing the problem and its history.

There’s also an interactive tool for producing patches of the tiling. It wasn’t immediately clear to me how it works: you pick which of the basic clusters H, T, P or F you want to start with, and then click “Build supertiles” to apply the substitution process and end up with a bigger patch of tiles.

It’s worth noting that this is just a preprint, so a mistake in the proof might be found, but this announcement is credible: the authors are well-known geometers who have been working on this and similar problems for a long time, and the outline of the proof looks coherent.

The authors call their shape the “einstein hat”, punning on the German “ein” – one, “stein” – stone (or tile). It’s fairly safe to predict that if the “einstein” part sticks, future generations will be confused about whether Albert Einstein was involved. Opinion differs on whether the shape looks more like a hat or a t-shirt.

Hat, t-shirt, trousers?

An explanation of what it’s all about that you can handwave your way through at the dinner table

Think about the 2D plane – an infinite, flat surface. How can you completely cover it up? If you’ve got an infinite supply of tiles, can you arrange them together on the plane so that there are no gaps?

If the tiles can be any shape you like, you can put them down however you like and then fill in any gaps with just the right shape. So it’s more interesting to restrict yourself to a certain, finite, set of different tile shapes.

Tilings of the plane with squares, triangles, and a mix of triangles and hexagons.

You can do this with infinitely many squares of the same size, or with a mix of equilateral triangles and regular hexagons. If all you’ve got is regular pentagons, you can’t do it: no matter how you arrange them, eventually you’ll end up with a gap that’s too small to put a pentagon tile in.

Pentagons don’t tile the plane

The next question is: once you’ve put the tiles down, are there any symmetries? If you just used squares, then you can move every tile one space down and it’ll look exactly the same as it did before.

Tiling with squares has translation symmetry

Is it possible to arrange the tiles so that there’s no translation symmetry – so that each point in the plane looks completely unique? This is called a non-periodic tiling.

If you split up a square into a few rectangles with the same proportions, you can produce a non-periodic tiling of the plane by by arranging them in a different configuration depending on their position on the plane. But you could also arrange them the same way everywhere, so there would be translation symmetry.

The interesting question is: are there any tiles, or sets of tiles, that can cover the plane, but never with translation symmetry – a truly aperiodic tiling?

The answer is yes: most famously, Roger Penrose found a pair of shapes – a kite and a dart, with specific edge lengths, or alternately a pair of rhombi, marked so that they obey certain edge-matching rules – that together tile the plane, but can never produce translation symmetry. Versions of the shapes which encode the matching rules, with chunks removed and added from the correct edges to force the matching (like the ones shared by Edmund Harriss in our Math-Off) constitute true aperiodic tile sets.

Penrose tiling with rhombi. From wikimedia, by Inductiveload, in the public domain.

It’s also possible to tile the plane aperiodically using a single tile, called a monotile – for example, the pinwheel tiling consists entirely of copies of a right-angled triangle with sides of length $1$, $2$ and $\sqrt{5}$ – but this shape could also form a periodic tiling, and in order to force the tiling to be aperiodic, matching rules are needed.

What nobody knew until now was whether there’s a single tile shape that generates only aperiodic tilings, without needing to specify matching rules – an aperiodic monotile.

That’s what Smith, Myers, Kaplan and Goodman-Strauss have found. They’ve proved that it tiles the plane, which is the easy part, and then proved that it must tile aperiodically. They came up with a new technique for proving this – actually, two: they proved it twice, just to be sure.

---

That’s the short version of the story. If your dinner companions are still interested, here’s some more explanation of how the aperiodicity proof works. Maybe pause for a bit, make sure your dinner isn’t getting too cold, and do some finger exercises to prepare for all the handwaving you’re about to do.

---

The authors show that no matter how you put the tiles down, it will always be possible to divide it up so that each tile belongs to one of a set of four clusters – specific arrangements of 1, 2 or 4 tiles – and that the edges on adjacent clusters can only match up in certain ways.

The four clusters of tiles. From An Aperiodic Monotile.

This part of the proof is done with computer assistance: there are lots of cases, and it’s likely you’d make a mistake while trying to draw them out on paper, so instead the authors rely on verifying that the code for their checking program is correct.

They then show that these clusters can themselves always be separated into larger groups called metatiles, which have the same symmetries as the basic tiles. So if the tiling when looked at as a collection of single tiles has translational symmetry, then looking at it as a collection of metatiles must also have that symmetry.

And then they show that the metatile tiling can’t have translational symmetry! So the monotile tiling doesn’t either!

The four metatile shapes.

To show that the metatile tiling is aperiodic, they just do the same trick again, forever: they show that the metatiles form clusters, and after a few steps the clusters from one step look the same as the clusters from the previous step, except bigger. These self-similar shapes are called supertiles. (Good job the proof ends after this step, because they’re running out of words for “bigger than”!)

Once you’ve identified the supertiles, you can perform a substitution to obtain the next step of the clustering process.

A patch of the tiling, with several layers of supertiles superimposed.

Remember that we’ve supposed you’re already looking at a complete tiling of the plane, and you’ve found a patch of adjacent supertiles. Replace each supertile with a certain arrangement of copies of the four possible supertiles, and the bigger patch of tiles you end up with must exactly match the tiling you’ve got, covering more of the plane than the patch you started looking at.

Because there’s no translation symmetry inside the supertiles, then there’s no translation symmetry among the metatiles, and hence the original tiles.

Reactions

The shape is really easy to make. I’ve created a GitHub repository of files representing the shape in various formats, for use in graphic design or 3D printing.

Dan Piker added some Truchet-like markings to the tile to make this nice pattern:

Dave Richeson was quick off the mark to print the tile on his 3D printer:

He’s put his model file on Thingiverse for anyone else who wants to print their own.

Travis Howse skipped a dimension and used his laser cutter to produce a set of tiles:

Adam Goucher has blogged about the paper, noting that the ratio of flipped tiles to unflipped tiles is $\phi^4$.

Dan Anderson has drawn the monotile using Mathigon’s interactive geometry tool, Polypad.

This meme by John May, who admits that it’s terrible, will not help with the einstein/Einstein confusion:

Read the paper

Really, read the paper! It’s very well-written, and deserves a lot of credit for going to extra lengths in the introduction to set the scene and provide the gist of the proof. If you just want to skim it, I suggest reading to the end of section 1.2 (“Outline”), and then the introductory paragraphs of each section after that. The subsections largely deal with the fiddly case-by-case checking that should be verified by somebody, but that needn’t be you.

from Hacker News https://ift.tt/o6pmY8O