An aperiodic set of 11 Wang tiles
This page is a companion to the article with the same title I wrote with Michael Rao (Jeandel and Rao 2021).
The Aperiodic set
Consider the following set of 11 tiles:
Consider a tiling of the plane by copy of the 11 tiles, without rotations, s.t. colors match on adjacent tiles.
Here is a tiling of a 10x10 square (this webpage is too small to show a tiling of the whole plane)
Our result states that the tileset is aperiodic, which means: a) such a tiling exist b) no such tiling is periodic.
Furthermore, we showed in the same article that this tileset is minimal: No tileset with 10 tiles or less is aperiodic. We also show that a variant of this tileset (replacing the white color by yellow) has the same properties and is also minimal in terms of colors: it has 4 horizontal and vertical colors, and it was known that no tileset with only 3 horizontal and vertical colors is aperiodic.
The proof
People interested in these questions might be interested in how you prove this tileset is indeed aperiodic and minimal. I will give here some short ideas.
Minimality in the number of tiles
This tileset was found by enumerating all sets of \(n\) tiles, with \(n \leq 11\), and prove that all tilesets with at most 10 tiles are not aperiodic. This part was done independently by Michael and me. The techniques I will explain here are the techniques that I used personally.
There are a few problems here
- There are a lot of sets of 10 Wang tiles. It is hard to count exactly how many there are (a tentative number is \(10^{40} \simeq 2^{130}\)). It is important to break symmetries as much as possible. I also used a theorem (Jeandel and Rolin 2012) that said that an aperiodic tileset with \(n\) tiles uses at most \(n-2\) colors.
- Aperiodicity is an undecidable problem. There is no algorithm to test whether a set of tiles is aperiodic. The best we can do is fix some integer \(N\) big enough and test if (a) it tiles a square of size \(N \times N\) (b) it doesn’t tile periodically a square of size at most \(N \times N\). If the tileset does not satisfy (a) and (b), it is not aperiodic. If it satifies (a) and (b), we don’t know.
An important idea is to use the representation of Wang tiles by transducers. To a Wang tile one can associate a transition in a transducers, from the west color to the east color, reading the south color and outputting the north color, as illustrated below.
The set of Wang tiles is able to tile an entire row iff there is a loop in the transducer. It is able to tile \(N\) rows iff there is a loop in the transducers \(T^N\) obtained by composing the transducer \(T\) with itself \(N\) times. There exists a tiling of vertical period \(N\) iff there exists a loop in the restriction of the transducer \(T^N\) to the transitions where input color=output color. This coding of Wang tiles by transducers enables us to use formal language theory (for instance automatata minimization) to study Wang tiles.
Using considerable computational resources, it is possible to generate all tilesets with 10 tiles or less and prove that there are not aperiodic, by using the transducer technique with a small value of \(N\). Typically \(N=128\) is enough: A set of 10 Wang tiles either does not tile an horizontal/vertical strip of width 128, or it does it periodically. Except for one example.
A hard example to analyze
Our program(s) failed to prove that the following example is not aperiodic:
It is not surprising that the program failed to work in all cases, because the problem is undecidable in general. Where we are lucky is that we were able to understand this particular example. It is a tileset that follows a construction by Jarkko Kari (Kari 1996). From this, it was easy to prove that it does not tile periodically, but we had to work to prove that it actually does not tile the plane (it does however tile a square of size 200x200).
An aperiodic set of 11 tiles
While enumerating all tilesets with 10 or 11 tiles, we found a few tilesets with 11 tiles for which we had no proof they are aperiodic (more accurately Michael did. My program did not scale up to \(n=11\)). One of them stood up amongst them because it seemed easier to analyze, it is the tileset presented earlier.
It remained to prove that it is aperiodic. It is hard to give a sketch of the proof because it is intricate. The main idea is to show that it has some kind of self-similar structure.
- From the set of 11 tiles, we were able to extract two sets of 14 tiles each that we call \(T_{-1}\) and \(T_0\) with the property that any tiling of the plane by the set of 11 tiles can be seen as a tiling by the 28 tiles, where each row is either in \(T_0\) or in \(T_{-1}\).
- From the definition of \(T_0\) and \(T_{-1}\) we were able to define by induction a family of transducers \(T_n\) that looks closely similar with the property that:
- \(T_{n+3} = T_{n+1} T_n T_{n+1}\)
- \(T_n\) has a loop (from which it follows that there is a tiling)
- Any tiling with \(T_n, T_{n+1}, T_{n+2}\) can be rewritten as a tiling by \(T_{n+1}, T_{n+2}, T_{n+3}\) (from which nonperiodicity follows).
This sketch of proof might remain incomprehensible, the proof is indeed quite technical.
By analyzing carefully our set of tiles, Sebastien Labbé (Labbé 2021) provided a new proof that the tileset tiles the plane. The proof is “constructive” in the sense that it is easy to give a program that computes a square of size \(n \times m\) in time roughly linear in \(nm\).
This is also explained in some details in his blog
Resources
- wallpaper_1920x1080 A tiling of a rectangle of size 96x54 for a wallpaper of size 1920x1080.
- wallpaper2_1920x1080 A tiling of a rectangle of size 48x27 for a wallpaper of size 1920x1080.
- wallpaper_2560x1440 A tiling of a rectangle of size 128x72 for a wallpaper of size 2560x1440.
- wallpaper2_2560x1440 A tiling of a rectangle of size 64x36 for a wallpaper of size 2560x1440.
- 100 A square of size 100x100, as a text file. It uses the characters 0,1,2..,9,A for the 11 tiles in the order provided above.
- 1000 A square of size 1000x1000, as a text file.
- 10000 A square of size 10000x10000, as a text file (compressed)
All of these were generated with a rust file, available at this link. To generate a rectangle of size \(N\times M\), just call partition N M. This code uses float64, and its accuracy has been tested for squares of size 10000x10000. It uses the method of Sebastien Labbé to generate the tilings.