by Jonathan Kujawa
In March David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss announced that they discovered an “Ein Stein”. The choice of name can only be described as a tour-de-force of PR: Ein Stein translates as One Stone but also evokes a certain physicist. The Ein Stein got wide play in the media, including here at 3QD. Unfortunately, the same authors’ discovery of the “Spectre” tile two weeks ago seems to have gone under the radar. Since it is even more interesting, I thought we should take the time to talk about it.
First off, what is this all about? This research is in the area of geometry about tilings of the plane. If you have a collection of tiles of various shapes and sizes along with a set of rules about how they can be placed, then a successful tiling of the plane with those tiles and rules is exactly what you think: you cover the entire plane going to infinity in all directions using only those tiles and following those rules [1].
Sometimes this is easy. If you have a rectangular tile with no rules restricting you, you see successful tilings all around you in the brickwork. If you use a rectangle with no rules, there are infinitely many different tilings.
Sometimes tiling the plane is impossible. If you have only a circular tile, then there is no way to tile the plane without leaving gaps. Sometimes it is the rules which cause a problem. If you have a triangular tile, but the rule says you aren’t allowed to rotate the tile, then there is a triangular tiling (here on the right), but it’s forbidden by the rule [2].
One common way of enforcing rules is to color the tiles and make requirements on where colors can be placed relative to each other. We discussed these sorts of tilings ages ago here at 3QD.
What are the Ein Stein and Spectre tiles all about? They are for aperiodic tilings of the plane. A tiling is periodic if it repeats itself over and over as you move along in some direction. Periodic tilings are common. After all, brickwork designs are periodic. What is less common is a tiling that does not repeat. These are aperiodic tilings. It is medium-hard to have a collection of tiles that allow you to tile the plane in an aperiodic way.
The hardest of all is a collection of tiles and rules that can be used for aperiodic tilings and only aperiodic tilings. An early example of this is the work of Robert Berger in 1961, where he gave a collection of 20,426 colored tiles and showed they tile the plane, but only aperiodically. It’s not very practical to work with 20,000+ tiles and various people worked to reduce the number. Famously, in the 1970s, Roger Penrose found a set of two tiles that does the job. They can be used to tile the plane in various ways, but none of those tilings will be periodic.
And then we were stuck. For fifty years, folks wondered if there was a single tile that only allowed aperiodic tilings of the plane. In March, Smith and company announced their Ein Stein. But it was a bit of a cheat. It was a single tile, but you were allowed to flip it over. So it was really two tiles in one [3].
It remained a question if we could come up with a true single tile that only allowed aperiodic tilings. We now have one. It’s the “Spectre” tile. Here is a tiling with the Spectre tile I borrowed from Craig Kaplan’s website:
In fact, the right half is a tiling with the Spectre tile. The left half is a different tile they call Tile(1,1). Tile(1,1) has the property that if you forbid flipping the tile, then Tile(1,1) only creates aperiodic tilings. But if you allow the tile to be flipped, then you can create a periodic tiling. The rules of the game are important!
How did they come up with the Spectre tile? Let’s go back to the Ein Stein. It turns out that there is not just one Ein Stein. There are billions and billions of them! You can start with one Ein Stein and adjust two side lengths to make a new tile. For each pair of side lengths, say a and b, you make a tile they call Tile(a,b). The original Ein Stein is Tile(1,√3). But every choice of a and b makes a new Ein Stein. Well, not quite. Tile(0,1) and Tile(1,0) are periodic. Tile(1,1) is the same Tile(1,1) mentioned above: it is aperiodic only if you forbid flipping.
Smith and his coconspirators realized that they could put some wiggles in the sides of Tile(1,1) to prevent you from fitting together a tile and its flipped version. This is the Spectre. Ayliean made a great short video explaining how the Spectre came about. By blocking you from flipping, the Spectre becomes a true aperiodic tile. You can tile the plane with the Spectre, but no matter how you lay down the tiles, the tiling you make will be aperiodic.
Why bother? First, as always in research, humans can’t help but be curious if something can be done. There is also a certain artistic appeal to aperiodic tilings. They are a pleasing blend of regularity and change. There are patterns, but those patterns never quite repeat. I know mathematicians who used the Penrose tiles when remodeling their kitchens or bathrooms. An aperiodic tiling using Pinwheel tiles decorates the outside of the Federation Square Building in Melbourne, Australia:
Aperiodic tilings are also relevant to the study of quasicrystals.
One of the original motivations may be the most interesting. We talked in the past here at 3QD about how questions about computation can be studied using Turing machines and that Turing machines can be encoded in a business card and in other exotic ways.
An important question is if a particular computation will actually ever be completed. That is, if a particular Turing machine will halt. As we talked about last year at 3QD, solving the Riemann hypothesis is the same as determining if a certain Turing machine halts.
Berger’s result was an answer to a conjecture made by his PhD advisor, Hao Wang, that if one uses what we now call Wang tiles to tile the plane, then they tile periodically. Wang showed that this conjecture would imply the existence of an algorithm for determining if a given collection of Wang tiles can be used to tile the entire plane. Berger’s result showed these conjectures to be false. Since it is known that there is no algorithm for determining if a Turing machine will halt, then Berger’s result means there can be no algorithm for determining if Wang tiles are able to tile the plane.
Even though they didn’t know it, the famous tile artists of the Alhambra Palace were doing theoretical computer science!
[1] Where you have an infinite supply of each tile, of course.
[2] See here for a discussion of the possible tilings of the plane by triangles.
[3] They should have called it the “eineinhalb stein.”
[4] Image borrowed from here.