Aperiodic tiling

In the mathematics of tessellations, a non-periodic tiling is a tiling that does not have any translational symmetry. An aperiodic set of prototiles is a set of tile-types that can tile, but only non-periodically. The tilings produced by one of these sets of prototiles may be called aperiodic tilings.
The Penrose tilings are a well-known example of aperiodic tilings.
In March 2023, four researchers, David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss, announced the proof that the tile discovered by David Smith is an aperiodic monotile, i.e., a solution to the einstein problem, a problem that seeks the existence of any single shape aperiodic tile. In May 2023 the same authors published a chiral aperiodic monotile with similar but stronger constraints.
Aperiodic tilings serve as mathematical models for quasicrystals, physical solids that were discovered in 1982 by Dan Shechtman who subsequently won the Nobel prize in 2011. However, the specific local structure of these materials is still poorly understood.
Several methods for constructing aperiodic tilings are known.

Definition and illustration

Consider a periodic tiling by unit squares. Now cut one square into two rectangles. The tiling obtained in this way is non-periodic: there is no non-zero shift that leaves this tiling fixed. But clearly this example is much less interesting than the Penrose tiling. In order to rule out such boring examples, one defines an aperiodic tiling to be one that does not contain arbitrarily large periodic parts.
A tiling is called aperiodic if its hull contains only non-periodic tilings. The hull of a tiling contains all translates + x of T, together with all tilings that can be approximated by translates of T. Formally this is the closure of the set in the local topology. In the local topology two tilings are -close if they agree in a ball of radius around the origin.
To give an even simpler example than above, consider a one-dimensional tiling T of the line that looks like where a represents an interval of length one, b represents an interval of length two. Thus the tiling T consists of infinitely many copies of a and one copy of b. Now all translates of T are the tilings with one b somewhere and as else. The sequence of tilings where b is centred at converges – in the local topology – to the periodic tiling consisting of as only. Thus T is not an aperiodic tiling, since its hull contains the periodic tiling
For well-behaved tilings holds: if a tiling is non-periodic and repetititve, then it is aperiodic.

History

The first specific occurrence of aperiodic tilings arose in 1961, when logician Hao Wang tried to determine whether the domino problem is decidable – that is, whether there exists an algorithm for deciding if a given finite set of prototiles admits a tiling of the plane. Wang found algorithms to enumerate the tilesets that cannot tile the plane, and the tilesets that tile it periodically; by this he showed that such a decision algorithm exists if every finite set of prototiles that admits a tiling of the plane also admits a periodic tiling. In 1964, Robert Berger found an aperiodic set of prototiles from which he demonstrated that the tiling problem is in fact not decidable. This first such set, used by Berger in his proof of undecidability, required 20,426 Wang tiles. Berger later reduced his set to 104, and Hans Läuchli subsequently found an aperiodic set requiring only 40 Wang tiles. A smaller set, of six aperiodic tiles, was discovered by Raphael M. Robinson in 1971. Roger Penrose discovered three more sets in 1973 and 1974, reducing the number of tiles needed to two, and Robert Ammann discovered several new sets in 1977. The number of tiles required was reduced to one in 2023 by David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss.
The aperiodic Penrose tilings can be generated not only by an aperiodic set of prototiles, but also by a substitution and by a cut-and-project method. After the discovery of quasicrystals aperiodic tilings become studied intensively by physicists and mathematicians. The cut-and-project method of N.G. de Bruijn for Penrose tilings eventually turned out to be an instance of the theory of Meyer sets. Today there is a large amount of literature on aperiodic tilings.
An einstein is an aperiodic tiling that uses only a single shape. The first such tile was discovered in 2010 - Socolar–Taylor tile, which is however not connected into one piece. In 2023 a connected tile was discovered, using a shape termed a "hat".

Constructions

There are a few constructions of aperiodic tilings known. Some constructions are based on infinite families of aperiodic sets of tiles. The tilings which have been found so far are mostly constructed in a few ways, primarily by forcing some sort of non-periodic hierarchical structure. Despite this, the undecidability of the domino problem ensures that there must be infinitely many distinct principles of construction, and that in fact, there exist aperiodic sets of tiles for which there can be no proof of their aperiodicity.
However, there are three principles of construction that have been predominantly used for finite sets of prototiles up until 2023:

matching rules,
substitution and expansion rules and
the cut-and-project method.

For some tilings only one of the constructions is known to yield that tiling. Others can be constructed by all three classical methods, e.g. the Penrose tilings.
Goodman-Straus proved that all tilings generated by substitution rules and satisfying a technical condition can be generated through matching rules. The technical condition is mild and usually satisfied in practice. The tiles are required to admit a set of hereditary edges such that the substitution tiling is sibling-edge-to-edge.

Aperiodic hierarchical tilings through matching

For a tiling congruent copies of the prototiles need to pave all of the Euclidean plane without overlaps and without leaving uncovered pieces. Therefore the boundaries of the tiles forming a tiling need to match geometrically. This is generally true for all tilings, aperiodic and periodic ones. Sometimes these geometric matching condition is enough to force a tile set to be aperiodic, this is e.g. the case for Robinsion's tilings discussed below.
Sometimes additional matching rules are required to hold. These usually involve colors or markings that have to match over several tiles across boundaries. Wang tiles usually require such additional rules.
In some cases it has been possible to replace matching rules by geometric matching conditions altogether by modifying the prototiles at their boundary. The
Penrose tiling originally consists of four prototiles together with some matching rules. One of the four tiles is a pentagon. One can replace this pentagon prototile by three distinct pentagonal shapes that have additional protrusions and indentations at the boundary making three distinct tiles. Together with the three other prototiles with suitably adapted boundaries one gets a set of six prototiles that essentially create the same aperiodic tilings as the original four tiles, but for the six tiles no additional matching rules are necessary, the geometric matching condition suffice.
Also note that Robinsion's protiles below come equipped with markings to make it easier to visually recognize the structure, but these markings do not put more matching rules on the tiles as are already in place through the geometric boundaries.
To date, there is not a formal definition describing when a tiling has a hierarchical structure; nonetheless, it is clear that substitution tilings have them, as do the tilings of Berger, Knuth, Läuchli, Robinson and Ammann. As with the term "aperiodic tiling" itself, the term "aperiodic hierarchical tiling" is a convenient shorthand, meaning something along the lines of "a set of tiles admitting only non-periodic tilings with a hierarchical structure".
For aperiodic tilings, whether additional matching rules are involved or not, the matching conditions forces some hierarchical structure on the tilings that in turn make period structures impossible.
Each of these sets of tiles, in any tiling they admit, forces a particular hierarchical structure.. No tiling admitted by such a set of tiles can be periodic, simply because no single translation can leave the entire hierarchical structure invariant. Consider Robinson's 1971 tiles:
Image:Robinson tiles.svg|center|thumbnail|200px|The Robinson Tiles
Any tiling by these tiles can only exhibit a hierarchy of square lattices: the centre of any orange square is also a corner of a larger orange square, ad infinitum. Any translation must be smaller than some size of square, and so cannot leave any such tiling invariant.
Image:Robinson tiling.jpg|center|thumbnail|300px|A portion of tiling by the Robinson tiles
Robinson proves these tiles must form this structure inductively; in effect, the tiles must form blocks which themselves fit together as larger versions of the original tiles, and so on.
This idea – of finding sets of tiles that can only admit hierarchical structures – has been used in the construction of most known aperiodic sets of tiles to date.
However, the tiling produced in this way is not unique, not even up to isometries of the Euclidean group, e.g. translations and rotations. A complete tiling of the plane constructed from Robinsion's tiles may or may not have faults going off to infinity in up to four arms and there are additional choices that allow for the encoding of infinite words from Σ^ω for an alphabet Σ of up to four letters. In summary there are uncountably many different tilings unrelated by Euclidean isometries, all of them necessarily nonperiodic, that can arise from the Robinsion's tiles.