Aperiodic Tiling - History

History

The second part of Hilbert's eighteenth problem asked for a single polyhedron tiling Euclidean 3-space, such that no tiling by it is isohedral (an anisohedral tile). The problem as stated was solved by Karl Reinhardt (mathematician) in 1928, but aperiodic tilings have been considered as a natural extension.

The specific question of aperiodic tiling first 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.

Hence, when in 1966 Robert Berger demonstrated that the tiling problem is in fact not decidable, it followed logically that there must exist an aperiodic set of prototiles. (Thus Wang's procedures do not work on all tile sets, although does not render them useless for practical purposes.) The first such set, presented by Berger and used 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. The set of 13 tiles given in the illustration on the right is an aperiodic set published by Karel Culik, II, in 1996.

However, a smaller aperiodic set, of six non-Wang 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.

In 1988, Peter Schmitt discovered a single aperiodic prototile in 3-dimensional Euclidean space. While no tiling by this prototile admits a translation as a symmetry, it has tilings with a screw symmetry, the combination of a translation and a rotation through an irrational multiple of π. This was subsequently extended by John Horton Conway and Ludwig Danzer to a convex aperiodic prototile, the Schmitt–Conway–Danzer tile. Because of the screw axis symmetry, this resulted in a reevaluation of the requirements for periodicity. Chaim Goodman-Strauss suggested that a protoset be considered strongly aperiodic if it admits no tiling with an infinite cyclic group of symmetries, and that other aperiodic protosets (such as the SCD tile) be called weakly aperiodic.

In 1996 Petra Gummelt showed that a single-marked decagonal tile, with two kinds of overlapping allowed, can force aperiodicity; this overlapping goes beyond the normal notion of tiling. An aperiodic protoset consisting of just one tile in the Euclidean plane, with no overlapping allowed, was proposed in early 2010 by Joshua Socolar; this example requires either matching conditions relating tiles that do not touch, or a disconnected but unmarked tile. The existence of a strongly aperiodic protoset consisting of just one tile in a higher dimension, or of a single simply connected tile in two dimensions without matching conditions, is an unsolved problem.