HOME

TheInfoList



OR:

An aperiodic tiling is a non-periodic tiling with the additional property that it does not contain arbitrarily large periodic regions or patches. A set of tile-types (or prototiles) is
aperiodic A periodic function is a function that repeats its values at regular intervals. For example, the trigonometric functions, which repeat at intervals of 2\pi radians, are periodic functions. Periodic functions are used throughout science to desc ...
if copies of these tiles can form only non- periodic tilings. The
Penrose tiling A Penrose tiling is an example of an aperiodic tiling. Here, a ''tiling'' is a covering of the plane by non-overlapping polygons or other shapes, and ''aperiodic'' means that shifting any tiling with these shapes by any finite distance, without ...
s are the best-known examples of aperiodic tilings. 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 (it looks like infinite
graph paper Graph paper, coordinate paper, grid paper, or squared paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting graphs of functions or experimental data and drawing curves ...
). 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 Hull may refer to: Structures * Chassis, of an armored fighting vehicle * Fuselage, of an aircraft * Hull (botany), the outer covering of seeds * Hull (watercraft), the body or frame of a ship * Submarine hull Mathematics * Affine hull, in affi ...
of a tiling T \subset \R^d contains all translates ''T+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 (resp. the corresponding metric) two tilings are \varepsilon-close if they agree in a ball of radius 1/\varepsilon around the origin (possibly after shifting one of the tilings by an amount less than \varepsilon). 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'' (with centre 0, say). Now all translates of ''T'' are the tilings with one ''b'' somewhere and ''a''s else. The sequence of tilings where ''b'' is centred at 1,2,4, \ldots,2^n,\ldots converges – in the local topology – to the periodic tiling consisting of ''a''s only. Thus ''T'' is not an aperiodic tiling, since its hull contains the periodic tiling For well-behaved tilings (e.g. substitution tilings with finitely many local patterns) holds: if a tiling is non-periodic and repetitive (i.e. each patch occurs in a
uniformly dense Uniform distribution may refer to: * Continuous uniform distribution * Discrete uniform distribution * Uniform distribution (ecology) * Equidistributed sequence See also * * Homogeneous distribution In mathematics, a homogeneous distribution ...
way throughout the tiling), 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.Grünbaum and Shephard, section 11.1. An even smaller set of six aperiodic tiles (based on Wang tiles) was discovered by Raphael M. Robinson in 1971.
Roger Penrose Sir Roger Penrose (born 8 August 1931) is an English mathematician, mathematical physicist, philosopher of science and Nobel Laureate in Physics. He is Emeritus Rouse Ball Professor of Mathematics in the University of Oxford, an emeritus f ...
discovered three more sets in 1973 and 1974, reducing the number of tiles needed to two, and
Robert Ammann Robert Ammann (October 1, 1946 – May, 1994) was an amateur mathematician who made several significant and groundbreaking contributions to the theory of quasicrystals and aperiodic tilings. Ammann attended Brandeis University, but generally did ...
discovered several new sets in 1977. The aperiodic Penrose tilings can be generated not only by an aperiodic set of prototiles, but also by a
substitution Substitution may refer to: Arts and media *Chord substitution, in music, swapping one chord for a related one within a chord progression *Substitution (poetry), a variation in poetic scansion * "Substitution" (song), a 2009 song by Silversun Pic ...
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 set In mathematics, a Meyer set or almost lattice is a set relatively dense ''X'' of points in the Euclidean plane or a higher-dimensional Euclidean space such that its Minkowski difference with itself is uniformly discrete. Meyer sets have several e ...
s. Today there is a large amount of literature on aperiodic tilings.


Constructions

There are a few constructions of aperiodic tilings known. Some constructions are based on infinite families of aperiodic sets of tiles. Those constructions which have been found 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.


Aperiodic hierarchical tilings

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 and Robinson. 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". 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; this is described below). 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: 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. 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.


Substitutions

Substitution tiling systems provide a rich source of aperiodic tilings. A set of tiles that forces a 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 force the chair substitution structure to emerge, and so are themselves aperiodic. The Penrose tiles, and shortly thereafter Amman's several different sets of tiles, were the first example based on explicitly forcing a substitution tiling structure to emerge.
Joshua Socolar Joshua () or Yehoshua ( ''Yəhōšuaʿ'', Tiberian: ''Yŏhōšuaʿ,'' lit. 'Yahweh is salvation') ''Yēšūaʿ''; syr, ܝܫܘܥ ܒܪ ܢܘܢ ''Yəšūʿ bar Nōn''; el, Ἰησοῦς, ar , يُوشَعُ ٱبْنُ نُونٍ '' Yūšaʿ ...
,
Roger Penrose Sir Roger Penrose (born 8 August 1931) is an English mathematician, mathematical physicist, philosopher of science and Nobel Laureate in Physics. He is Emeritus Rouse Ball Professor of Mathematics in the University of Oxford, an emeritus f ...
,
Ludwig Danzer Ludwig Danzer (15 November 1927 – 3 December 2011) was a German geometer working in discrete geometry. He was a student of Hanfried Lenz, starting his career in 1960 with a thesis about "Lagerungsprobleme". Danzer's name is popularized in the ...
, and Chaim Goodman-Strauss have found several subsequent sets.
Shahar Mozes Shahar Mozes (שחר מוזס) is an Israeli mathematician. Mozes received in 1991, his doctorate from the Hebrew University of Jerusalem with thesis ''Actions of Cartan subgroups'' under the supervision of Hillel Fürstenberg. (doctoral disserta ...
gave the first general construction, showing that every product of one-dimensional substitution systems can be enforced by matching rules.
Charles Radin Charles Lewis Radin is an American mathematician, known for his work on aperiodic tilings and in particular for defining the pinwheel tiling and, with John Horton Conway, the quaquaversal tiling. Education and career Radin did his undergraduate st ...
found rules enforcing the Conway-pinwheel substitution tiling system. In 1998, Goodman-Strauss showed that local matching rules can be found to force any substitution tiling structure, subject to some mild conditions.


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 De Bruijn is a Dutch surname meaning "the brown". Notable people with the surname include: * (1887–1968), Dutch politician * Brian de Bruijn (b. 1954), Dutch-Canadian ice hockey player * Chantal de Bruijn (b. 1976), Dutch field hockey defender ...
. There is yet no complete (algebraic) characterization of cut and project tilings that can be enforced by matching rules, although numerous necessary or sufficient conditions are known.


Other techniques

Only a few different kinds of constructions have been found. Notably, Jarkko Kari gave an aperiodic set of Wang tiles based on multiplications by 2 or 2/3 of real numbers encoded by lines of tiles (the encoding is related to Sturmian sequences made as the differences of consecutive elements of Beatty sequences), with the aperiodicity mainly relying on the fact that 2n/3m is never equal to 1 for any positive integers n and m. This method was later adapted by Goodman-Strauss to give a strongly aperiodic set of tiles in the hyperbolic plane.
Shahar Mozes Shahar Mozes (שחר מוזס) is an Israeli mathematician. Mozes received in 1991, his doctorate from the Hebrew University of Jerusalem with thesis ''Actions of Cartan subgroups'' under the supervision of Hillel Fürstenberg. (doctoral disserta ...
has found many alternative constructions of aperiodic sets of tiles, some in more exotic settings; for example in semi-simple
Lie group In mathematics, a Lie group (pronounced ) is a group that is also a differentiable manifold. A manifold is a space that locally resembles Euclidean space, whereas groups define the abstract concept of a binary operation along with the addi ...
s. Block and Weinberger used homological methods to construct aperiodic sets of tiles for all non- amenable manifolds. Joshua Socolar also gave another way to enforce aperiodicity, in terms of ''alternating condition''. This generally leads to much smaller tile sets than the one derived from substitutions.


Physics

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 an unambiguous fivefold symmetry – so it had to be a crystalline substance with icosahedral symmetry. In 1975
Robert Ammann Robert Ammann (October 1, 1946 – May, 1994) was an amateur mathematician who made several significant and groundbreaking contributions to the theory of quasicrystals and aperiodic tilings. Ammann attended Brandeis University, but generally did ...
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. Faraday waves have been observed to form large patches of aperiodic patterns. The physics of this discovery has revived the interest in incommensurate structures and frequencies suggesting to link aperiodic tilings with interference phenomena.


Confusion regarding terminology

The term ''aperiodic'' has been used in a wide variety of ways in the mathematical literature on tilings (and in other mathematical fields as well, such as dynamical systems or graph theory, with altogether different meanings). With respect to tilings the term aperiodic was sometimes used synonymously with the term non-periodic. A ''non-periodic'' tiling is simply one that is not fixed by any non-trivial translation. Sometimes the term described – implicitly or explicitly – a tiling generated by an aperiodic set of prototiles. Frequently the term aperiodic was just used vaguely to describe the structures under consideration, referring to physical aperiodic solids, namely quasicrystals, or to something non-periodic with some kind of global order. The use of the word "tiling" is problematic as well, despite its straightforward definition. There is no single
Penrose tiling A Penrose tiling is an example of an aperiodic tiling. Here, a ''tiling'' is a covering of the plane by non-overlapping polygons or other shapes, and ''aperiodic'' means that shifting any tiling with these shapes by any finite distance, without ...
, for example: the Penrose rhombs admit infinitely many tilings (which cannot be distinguished locally). A common solution is to try to use the terms carefully in technical writing, but recognize the widespread use of the informal terms.


See also

* Girih tiles *
List of aperiodic sets of tiles In geometry, a tiling is a partition of the plane (or any other geometric setting) into closed sets (called ''tiles''), without gaps or overlaps (other than the boundaries of the tiles). A tiling is considered periodic if there exist translation ...
* Quasicrystal *
Zellige ''Zellij'' ( ar, الزليج, translit=zillīj; also spelled zillij or zellige) is a style of mosaic tilework made from individually hand-chiseled tile pieces. The pieces were typically of different colours and fitted together to form various ...


References


External links


The Geometry JunkyardThe Infinite Pattern That Never Repeats
{{Tessellation