Wang's conjecture states that if a set of tiles can tile the plane, then they can always be arranged to do so periodically (Wang 1961). The conjecture
was refuted when Berger (1966) showed that an aperiodic set of tiles existed. Berger
used
tiles, but the number has subsequently been greatly reduced.
Culik (1996) reduced the number of colored square tiles to 13. Jeandel and Rao (2015) subsequently found an 11-tile 4-color set, illustrated above, and proved through exhaustive search that it is minimal in the sense that no Wang set with either fewer than 11 tiles or fewer than 4 colors is aperiodic.
For non-square tiles, the problem becomes much more complicated due to the Penrose tiles (2 tiles), the Robertson tiling (6 tiles), and various Ammann tilings (2-5
tiles).
The longstanding open problem of finding an aperiodic
monotile was solved by Smith et al. (2023).
Adler, A. and Holroyd, F. C. "Some Results on One-Dimensional Tilings." Geom. Dedicata10, 49-58, 1981.Berger,
R. "The Undecidability of the Domino Problem." Mem. Amer. Math. Soc.
No.66, 1-72, 1966.Culik, K. II "An Aperiodic Set of
13 Wang Tiles." Disc. Math.160, 245-251, 1996.Dutch,
S. "Aperiodic Tilings." May 29, 2003. http://www.uwgb.edu/dutchs/symmetry/aperiod.htm.Grünbaum,
B. and Shephard, G. C. Tilings
and Patterns. New York: W. H. Freeman, 1986.Hanf, W. "Nonrecursive
Tilings of the Plane. I." J. Symbolic Logic39, 283-285, 1974.Jeandel,
E. and Rao, M. "An Aperiodic Set of 11 Wang Tiles." 25 Jun 2015. https://arxiv.org/abs/1506.06492.Kari,
J. "A Small Aperiodic Set of Wang Tiles." Disc. Math.160,
259-264, 1996.Mozes, S. "Tilings, Substitution Systems, and Dynamical
Systems Generated by Them." J. Analyse Math.53, 139-186, 1989.Myers,
D. "Nonrecursive Tilings of the Plane. II." J. Symbolic Logic39,
286-294, 1974.Radin, C. Miles
of Tiles. Providence, RI: Amer. Math. Soc., pp. 6-8, 1999.Robinson,
R. M. "Undecidability and Nonperiodicity for Tilings of the Plane."
Invent. Math.12, 177-209, 1971.Smith, D.; Myers, J. S.;
Kaplan, C. S.; and Goodman-Strauss, C. "An Aperiodic Monotile." 20
Mar 2023. https://arxiv.org/abs/2303.10798.Smith,
T. "Penrose Tilings and Wang Tilings." http://www.innerx.net/personal/tsmith/pwtile.html.Wang,
H. "Proving Theorems by Pattern Recognition. II." Bell Systems Tech.
J.40, 1-41, 1961.
tiles, but the number has subsequently been greatly reduced.
