Aperiodic tiling

are an aperiodic set of tiles, since they admit only "non-periodic" tilings of the plane:]

---

right| thumb| 200px">
Any of the infinitely many tilings by the Penrose tiles is non-periodic. More informally, many refer to the 'Penrose tilings' as being 'aperiodic tilings', but this is not well-defined mathematically.

The informal term aperiodic tiling loosely refers to an aperiodic set of tiles and the tilings which such sets admit. Properly speaking, aperiodicity is a property of the set of tiles themselves; a given tiling is simply "non-periodic" or "periodic". Further confusing the matter is that a given aperiodic set of tiles typically admits infinitely many distinct tilings.

A given set of tiles, in the Euclidean plane or some other geometric setting, "admits a tiling" if non-overlapping copies of the tiles in the set can be fitted together to cover the entire space. A given set of tiles might admit periodic tilings, tilings that remain invariant after being shifted by a translation. (For example, a lattice of square tiles is periodic.) It is not difficult to design a set of tiles that admits non-periodic tilings as well (For example, randomly arranged tilings using a 2×2 square and 2×1 rectangle will typically be non-periodic.) An aperiodic set of tiles however, admits "only" non-periodic tilings, an altogether more subtle phenomenon.cite book | last = Senechal | first = Marjorie | authorlink = Marjorie Senechal | year = 1995 (corrected paperback edition, 1996) | title = Quasicrystals and geometry | publisher = Cambridge University Press | id = ISBN 0-521-57541-9] cite book | last = Grünbaum | first = Branko | authorlink = Branko Grünbaum | coauthors = Geoffrey C. Shephard | year = 1986 | title = Tilings and Patterns | publisher = W.H. Freeman & Company | id = ISBN 0-7167-1194-X]

The various Penrose tiles [cite journal | last = Gardner | first = Martin | authorlink = Martin Gardner | year = 1977 | month = January | title = Mathematical Games | journal = Scientific American | volume = 236 | pages = 111–119] [cite book | last = Gardner | first = Martin | authorlink = Martin Gardner | year = 1988 | title = Penrose Tiles to Trapdoor Ciphers | publisher = W H Freeman & Co | id = ISBN 0-7167-1987-8] are best known examples of an aperiodic set of tiles.

Only few methods for constructing aperiodic tilings are known, such as forcing the emergence of a non-periodic hierarchical structure. This is perhaps natural: the underlying undecidability of the Domino problem implies that there exist aperiodic sets of tiles for which there can be no proof they are aperiodic.

Physical materials, quasicrystals, with the apparent structure of the Penrose tilings were discovered by Dan Shechtman" et al." in 1984;cite journal| last = Schechtman|first = D.|last2 = Blech|first2 = I.|last3 = Gratias|first3 = D.|last4 = Cahn|first4 = J.W.|title = Metallic Phase with long-range orientational order and no translational symmetry| journal = Phys. Rev. Letters| volume = 53|year = 1984| pages = 1951–1953|doi = 10.1103/PhysRevLett.53.1951] however the specific local structure of these materials is still poorly understood.

History

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

The specific question of aperiodic tiling first arose in 1961, when logician Hao Wang tried to determine whether the Domino Problem is decidable: i.e. whether there exists an algorithm for deciding if a given finite set of prototiles admits a tiling of the plane. Wang showed that such an 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, [cite journal | last=Berger | first=Robert | year=1966 | title=The undecidability of the domino problem | journal=Memoirs of the American Mathematical Society | issue=66 | pages=1–72] it followed that there must exist an aperiodic set of prototiles. The first such set, presented by Berger and used in his proof of undecidability, consisted of 20,426 Wang tiles. Berger reduced his set to size 104, and Hans Läuchli found an aperiodic set of 40 Wang tiles. [Grünbaum and Shephard, section 11.1.] The set of 13 tiles given in the illustration is an aperiodic set published by Karel Culik, II, in 1996.

The fact that Wang's procedure cannot theoretically work for arbitrary large tile sets does not render it useless for practical purposes.

However, a smaller aperiodic set, of six non-Wang tiles, was discovered by Raphael M. Robinson in 1971. [cite journal | last=Robinson | first=Raphael M. | year=1971 | title=Undecidability and Nonperiodicity for Tilings of the Plane | journal=Inventiones Mathematicae | volume=12 | pages=177–209 | doi=10.1007/BF01418780] 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. [cite journal | last=Radin | first=Charles | year=1995 | title=Aperiodic tilings in higher dimensions | journal=Proceedings of the American Mathematical Society | volume=123 | issue=11 | pages=3543–3548 | url=http://links.jstor.org/sici?sici=0002-9939(199511)123%3A11%3C3543%3AATIHD%3E2.0.CO%3B2-O | format=fee required | doi=10.2307/2161105] 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". [cite web | url=http://comp.uark.edu/~strauss/papers/survey.pdf | title=Open Questions in Tiling | accessdate=2007-03-24 | last=Goodman-Strauss | first=Chaim | date=2000-01-10 | format=PDF]

In 1996 Petra Gummelt showed that a single marked decagonal tile with two kinds of overlapping allowed can force aperiodicity; [cite journal | last=Gummelt | first=Petra | year=1996 | title=Penrose Tilings as Coverings of Congruent Decagons | journal=Geometriae Dedicata | volume=62 | issue=1 | pages=1–17 | doi=10.1007/BF00239998] this overlapping goes beyond the normal notion of "tiling". The existence of an aperiodic protoset consisting of just one tile in the Euclidean plane, with no overlapping allowed, or of a strongly aperiodic protoset consisting of just one tile in any dimension, is an unsolved problem.

Constructions

There are remarkably few constructions of aperiodic sets of tiles known, even forty years after Berger's groundbreaking construction (Some constructions, such as that given in cite journal | last=Goodman-Strauss | first=Chaim | year=1998 | title=Matching rules and substitution tilings | journal=Annals of Mathematics | volume=147 | issue=1 | pages=181–223 | url=http://comp.uark.edu/~strauss/papers/index.html | doi=10.2307/120988 ] , are of infinite families of aperiodic sets of tiles).Moreover, those that have been found are generally constructed only a very 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!

It is worth noting that there can be no aperiodic set of tiles in one dimension: it is a simple exercise to show that any set of tiles in the line either cannot be used to form a complete tiling, or can be used to form a periodic tiling. Aperiodicity requires, somehow, two or more dimensions.

Aperiodic hierarchical tilings

To date, there is not a formal definition describing when a tiling has a hierarchical structure; nonetheless, it is clear substitution tilings have them, as do the tilings of Berger, Knuth, Läuchli and Robinson. As is the case 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".

Each of these sets of tiles, in any tiling they admit, forces a particular hierarchical structure. (In many later examples, this structure can be described as a substitution tiling system, described momentarily.) 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:

Any tiling by these tiles can only exhibit a hierarchy of square lattices: each orange square is at the 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.

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.

ubstitutions

Substitution tiling systems provide a rich source of hierarchical non-periodic structures; however the substituted tiles themselves are not typically aperiodic. A set of tiles that forces an substitution structure to emerge is said to enforce the substitution structure. For example, the chair tiles shown below admit a substitution, and a portion of a substitution tiling is shown at right below. These substitution tilings are necessarily non-periodic, in precisely the same manner as described above, but the chair tile itself is not aperiodic-- it is easy to find periodic tilings by unmarked chair tiles.

However, the tiles shown below, somehow, force the chair substitution structure to emerge, and so are themselves aperiodic. cite journal| last = Goodman-Strauss|first = Chaim| title = A small aperiodic set of planar tiles| journal = European J. Combinatorics| year = 1999| volume = 20| pages = 375–384| doi = 10.1006/eujc.1998.0281]

The Penrose tiles, and shortly thereafter Amman's several different sets of tiles, were the first example based on explicitly forcing a substition tiling structure to emerge. Joshua Socolar [cite journal| last = Socolar|first = J.E.S.|title = Simple octagonal and dodecagonal quasicrystals| journal = Phys. Rev. A| volume = 39| year = 1989| pages = 10519–51] , Roger Penrose [cite journal| last = Penrose|first = R.|title = Remarks on Tiling: details of a1+ε+ε²-aperiodic set|journal= The mathematics long rangeaperiodic order, NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci. |volume = 489 |year = 1997| pages = 467–497] , Ludwig Danzer [cite journal| last = Nischke|first =K.-P.| last2 = Danzer|first2 = L.|title = A construction of inflation rules based on "n"-fold symmetry| journal = Disc. and Comp. Geom.|volume = 15|year = 1996|pages = 221–236|doi = 10.1007/BF02717732] , and Chaim Goodman-Strauss have found several subsequent sets. Shahar Mozes gave the first general construction, showing that every product of one-dimensional substitution systems can be enforced by matching rules.cite journal|last = Mozes|first = S.| title = Tilings, substitution systems and dynamicalsystems generated by them|journal = J. D'Analyse Math.|volume = 53|year = 1989|pages =139–186]
Charles Radin found rules enforcing the Conway-pinwheel substitution tiling system. [cite journal| last = Radin|first = Charles| title = The pinwheel tilings of the plane|journal = Annals of Mathematics |volume = 139| year = 1994| pages = 661–702| doi = 10.2307/2118575] In 1998, Goodman-Strauss showed that local matching rules can be found to force any substitution tiling structure, subject to some mild conditions.

Muqarnas, the Arabic/Islamic space-enclosing system, appear to be non-periodic while lending themselves to aperiodic forms. Consider examples at the image gallery: [http://www.ensightful.com/spatial/gallery/muq-gallery.html]

Cut-and-project method

Non-periodic tilings can also be obtained by projection of higher-dimensional structures into spaces with lower dimensionality and under some circumstances there can be tiles that enforce this non-periodic structure and so are aperiodic. The Penrose tiles are the first and most famous example of this, as first noted in the pioneering work of de Bruijn [ N. G. de Bruijn, Nederl. Akad. Wetensch. Indag. Math. 43, 39-52, 53-66 (1981). Algebraic theory of Penrose's nonperiodic tilings of the plane, I, II ] . In 1995, Thang T.Q. Le gave necessary and sufficient conditions under which the tilings produced by the cut and project method can be enforced by matching rules. [cite journal | last = Le|first = T.T.Q.| title = Local rules for quasiperiodic tilings| journal = The mathematics long rangeaperiodic order, NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci. |volume = 489 |year = 1997| pages = 331–366]

Other techniques

Only a few different kinds of construction have been found: Notably, Jarkko Kari gave an aperiodic set of Wang tiles based on Sturmian sequences [cite journal | last = Kari| first = Jarkko| title = A small aperiodic set of Wang tiles| journal = Discrete Mathematics| volume = 160| year = 1996| pages = 259–264| doi = 10.1016/0012-365X(95)00120-L ] , which was later adapted by Goodman-Strauss to give a strongly aperiodic set of tiles in the hyperbolic plane [cite journal| last=Goodman-Strauss| first = Chaim | year = 2005| title = A strongly aperiodic set of tiles in the hyperbolic plane| journal = Inventiones Mathematicae| volume = 159 | pages = 119–132| doi = 10.1007/s00222-004-0384-1 ]
Shahar Mozes has found many alternative constructions of aperiodic sets of tiles, some in more exotic settings; for example in semi-simple Lie Groups [cite journal|last = Mozes| first = Shahar|title = Aperiodic tilings
journal = Inventiones Mathematicae | year = 1997| volume = 128 | pages = 603–611|doi = 10.1007/s002220050153 ]

In Islamic architecture the geometric space-enclosing system known as [http://en.wikipedia.org/wiki/Muqarnas muqarnas] appears to be aperiodic. Numerous computer rendered examples can be seen [http://www.ensightful.com/ here] .

Physics of aperiodic tilings

Aperiodic tilings were considered as mathematical artefacts until 1984, when physicist Dan Shechtman announced the discovery of a phase of an aluminium-manganese alloy which produced a sharp diffractogram with a unambiguous fivefold symmetry, so it had to be a crystalline substance with icosahedral symmetry. In 1975 Robert Ammann had already extended the Penrose construction to a three dimensional icosahedral equivalent. In such cases the term 'tiling' is taken to mean 'filling the space'. Photonic devices are currently built as aperiodical sequences of different layers, being thus aperiodic in one direction and periodic in the other two. Quasicrystal structures of Cd-Te appear to consist of atomic layers in which the atoms are arranged in a planar aperiodic pattern. Sometimes an energetical minimum or a maximum of entropy occur for such aperiodic structures. Steinhardt has shown that Gummelt's overlapping decagons allow the application of an extremal principle and thus provide the link between the mathematics of aperiodic tiling and the structure of quasicrystals [cite web | url=http://wwwphy.princeton.edu/~steinh/quasi/ | title=A New Paradigmfor the Structure of Quasicrystals | accessdate=2007-03-26 | last=Steinhardt | first=Paul J.] . Faraday waves have been observed to form large patches of aperiodic patterns [ W. S. Edwards and S. Fauve, Parametrically excited quasicrystalline surface waves, Phys. Rev. E 47, (1993)R788 - R791 ] . The physics of this discovery has revived the interest in incommensurate structures and frequencies suggesting to link aperiodic tilings with interference phenomena [ Levy J-C. S., Mercier D., Stable quasicrystals, Acta Phys. Superficium 8(2006)115] . .

Confusion regarding terminology

The terms "non-periodic", "quasiperiodic" and "aperiodic" have been used in a wide variety of ways in a wide variety of fields, leading to considerable confusion. Moreover, the word "tiling" itself is quite problematic.

In the context of 'Aperiodic tiling', a "non-periodic" tiling is simply one with no period, as discussed above, and "aperiodicity" is a property of tiles: a set of tiles is aperiodic if and only if it admits only non-periodic tilings. There is no mathematical concept of "aperiodic tiling" per se. Quasiperiodic tilings, generally, mean those obtained by the cut-and-project method; however William Thurston's influential lecture notes [Citation | last =Thurston
first =William
title =Groups, tilings and finite stateautomata: Summer 1989 AMS colloquim lectures, GCG 1, Geometry Center ] used the term to mean repetitive tilings. The Penrose tiles themselves are a source of much of the confusion, for the tilings they admit are quasiperiodic, in both senses, and non-periodic, and they themselves are aperiodic.

Moreover the terms aperiodic and non-periodic are in fact synonymous in other fields, such as dynamical systems; and there is much literature on tilings in which, inappropriately, the distinction is not made. It is important to note however, that the core results of the field simply are not meaningful without this careful delineation.

The word "tiling" is problematic as well, despite its straightforward definition. There is no single Penrose tiling, for example: the Penrose rhombs admit infinitely many tilings (which cannot be distinguished locally) and even established figures in the field refer to "aperiodic tiling", knowing full well that this is not technically defined. A common solution is to try to use the terms carefully in technical writing, but recognize the widespread use of the informal terms.

References

External links

* [http://www.ics.uci.edu/~eppstein/junkyard/tiling.html The Geometry Junkyard]
* [http://www.uwgb.edu/dutchs/symmetry/aperiod.htm Aperiodic Tilings]