Table of Contents
Aperiodic Tiles
In the 1960s the concept of an “aperiodic tiling” became an important mathematical concept. Wang studied the Tiling Problem – whether, given a set of prototiles (the unique tiles that are used and repeated within the tiling) P there is a process for deciding whether or not P admits a tiling. This led him to conjecture in 1961 that aperiodic tilings don’t exist [2].
An aperiodic tile set is a set of tiles that can be combined to tile the infinite plane but such that no such tiling has translational symmetry. That means that no row or column in an infinite tiling can be repeated. This does not, however, mean that a finite tiling cannot be periodic.
Different tilings have different rules, for instance in some tile sets prototiles can be rotated or reflected, in others they can’t. Some tilings simply require that the physical shapes of the tiles fit together without gaps, others have rules dictating which tiles can be placed adjacent to each other.
Wang conjectured that aperiodic tilings don’t exist. He also introduced Wang tiles, or domino tiles as he called them.
Wang Tiles
Wang tiles are square tiles. Each edge has a label or property, often referred to as a “colour”. The tiles are arranged in a grid but any tile edge colour must match that of the tile to which it is adjacent. The Wang prototiles cannot be reflected or rotated. Wang tiles are often displayed divided into 4 triangles – those made by each edge with the tile centre. Each triangle is coloured according to the relevant external edge.
Right top: A tiling using the Kari tile set and traditional Wang rendering.
Note that although the Kari tile set is aperiodic, this example of a finite tiling shows repetition. Lines 13-19 are replicated.
Right bottom: The Kari prototiles.
The Race to Find Ever Smaller Aperiodic Tile Sets
In 1975 Hans Läuchli [2] discovered a set of 40 aperiodic Wang tiles. At the time this was the smallest set of aperiodic tiles known. A few years later a set of 16 aperiodic Wang tiles, due to Ammann [2], were found.
The first set of aperiodic tiles were discovered by Berger, a student of Wang, who found a set of a set of 20426 Wang tiles, thus proving Wang’s conjecture incorrect. He later managed to reduce this to 104 tiles.
For some years after this the main sucesses were with other tiles other than Wang tiles. Ammann and Roger Penrose found aperiodic sets of 2 tiles[2]. In both these cases it is permissable to rotate and reflect the tiles, something that is prohibited with Wang tiles.
Further progress on Wang tiles wasn’t made until 1996 when Kari [4] and Culik [1] came up with aperiodic tile sets of 14 and 13 . In 2021 Jeandel and Rao [3] discovered a set of 12 and proved no smaller aperiodic set of Wang tiles existed.
In the 2020’s a single aperiodic tile was discoverd, the “hat” monotile. This can be rotated or reflected in a tiling. Subsequently an aperiodic chiral monotile (one that cannot be reflected) has been found[]. But the smallest set of aperiodic Wang tiles remains at 12, Jeandel and Rao proved this to be the smallest set possible.
How I use Wang Tiles
My program WARP came about when I wrote my dissertation on Aperiodic Wang Tiles for my Maths master’s. I wanted to be able to generate the tilings, but also to investigate more interesting ways of rendering some of the tiles to help illustrate the logic behind the proof of aperiodicity.
Since completing the masters I have developed WARP in two directions:
(1) Continuing to play with the aperiodic tile sets and alternative renderings:
Läuchli defined a set of prototiles that show the hierarchical structure on which the proof of aperiodicity is based, but I have still played with alternative renderings.
Kari and Culik’s tiles – I believe an alternative rendering greatly aids visualisation of the proof of aperiodicity.
(2) Using the matching rules of Wang tiles to define sets of (non-aperiodic) prototiles. Here the edge matching is used to force some rules and structure into renderings, although I use other techniques too to generate output as in this work aesthetics is more important than any mathematics beyond pure geometry. Many decisions are made with random input. I am also using other shaped Wang tiles such as hexagons. I have a library of tiles that render in different ways and work together to produce emergent shapes and forms. This is currently the main focus of my algorithmic work.
References
[1] Culik, K. (1996) An aperiodic set of 13 Wang tiles, Discrete mathematics,
160(1), pp. 245–251. Available at:
https://doi.org/10.1016/S0012-365X(96)00118-5.
[2]Grünbaum & Shephard (1987) ‘Wang Tiles’, in Grünbaum & Shephard
Tilings and Patterns, Freeman, New York pp 583-608
[3] Jeandel, E. and Rao, M. (2021) An aperiodic set of 11 Wang tiles, Advances
in Combinatorics (Online) [Preprint]. Available at:
https://doi.org/10.19086/aic.18614.
[4] Kari, J. (1996) A small aperiodic set of Wang tiles, Discrete mathematics,
160(1), pp. 259–264. Available at:
https://doi.org/10.1016/0012-365X(95)00120-L.
