Penrose tiling

A Penrose tiling.

A Penrose tiling is a nonperiodic tiling generated by an aperiodic set of prototiles named after Sir Roger Penrose, who investigated these sets in the 1970s. Because all tilings obtained with the Penrose tiles are non-periodic, Penrose tilings are considered aperiodic tilings. A Penrose tiling may be constructed so as to exhibit both reflection symmetry and fivefold rotational symmetry, as in the diagram at the right.

A Penrose tiling has many remarkable properties, most notably:

• It is nonperiodic, which means that it lacks any translational symmetry. More informally, a shifted copy will never match the original exactly.
• Any finite region in a tiling appears infinitely many times in that tiling and, in fact, in any other tiling. This property would be trivially true of a tiling with translational symmetry but is non-trivial when applied to the non-periodic Penrose tilings.
• It is a quasicrystal: implemented as a physical structure a Penrose tiling will produce Bragg diffraction; the diffractogram reveals both the underlying fivefold symmetry and the long range order. This order reflects the fact that the tilings are organized, not through translational symmetry, but rather through a process sometimes called "deflation" or "inflation."

Various methods to construct Penrose tilings have been discovered, including matching rules, substitutions, cut and project schemes and coverings.

Background and history

Penrose tilings are among the simplest examples of aperiodic tilings of the plane.^[1] A tiling is a covering of the plane by tiles with no overlaps or gaps; the tiles normally have a finite number of shapes, called prototiles, and a set of prototiles is said to admit a tiling or tile the plane if there is a tiling of the plane using only tiles congruent to these prototiles.^[2] The most familiar tilings (e.g., by squares or triangles) are periodic: a perfect copy of the tiling can be obtained by translating all of the tiles by a fixed distance in a given direction. Such a translation is called a period of the tiling; more informally, this means that the tiling repeats itself. If a tiling has no periods it is said to be nonperiodic. A set of prototiles is said to be aperiodic if it tiles the plane, but every such tiling is nonperiodic; tilings by aperiodic sets of prototiles are called aperiodic tilings.^[3]

The subject of aperiodic tilings received new interest in the 1960's when logician Hao Wang noted connections between problems in geometry—specifically problems about tiling—and certain decision problems.^[4] As an aside, he observed that if the so-called Domino Problem were undecidable, then there would have to exist an aperiodic set of prototiles. At the time, this seemed implausible, so Wang conjectured no such set could exist, and that the Domino Problem should be decidable.

Wang's student Robert Berger disproved this conjecture in his 1964 thesis,^[5] where he exhibited an aperiodic set of 20426 prototiles, and described a reduction of this set to 104 prototiles; the latter reduction did not appear in his published monograph,^[6] but Donald Knuth later detailed a modification of Berger's set requiring only 92 prototiles.^[7][8] A further substantial reduction was obtain by Raphael Robinson, who simplified Berger's techniques in a 1971 paper,^[9] and produced an aperiodic set of just six prototiles.^[10]

The pentagonal Penrose tiling (P1) in black on a colored rhombus tiling (P3) background.^[11]

In a 1974 paper, Roger Penrose also proposed a tiling with six prototiles (tiling P1 below); his tiling forced a hierarchical pentagonal structure.^[12] Penrose acknowledged inspiration from the work of Johannes Kepler: in Harmonices Mundi Kepler explored tilings built around pentagons and it has been shown that his construction can be extended into a Penrose tiling; other traces of these ideas can be found in Dürer's work.^[13]

Penrose subsequently reduced the number of prototiles to two, discovering the kite and dart tiling (tiling P2 below) and the rhombus tiling (tiling P3 below). The rhombus tiling was independently discovered by Robert Ammann in 1976.^[14] Penrose and John H. Conway investigated the properties of Penrose tilings and their findings were publicized by Martin Gardner in his January 1977 "Mathematical Games" column in Scientific American.^[15]

In 1981 De Bruijn explained a method to construct Penrose tilings^[16] from five families of parallel lines as well as a "cut and project method", in which Penrose tilings are obtained as two-dimensional projections from a five-dimensional cubic structure. In this approach the Penrose tiling is considered as a set of points, its vertices, while its tiles are just the geometrical shapes defined by connecting edges.

The Penrose tilings

A tiling constructed from Penrose's original (P1) set of six prototiles.

Attempts to tile the plane with regular pentagons necessarily leave gaps. Penrose's first tiling (P1) fixes this problem by filling the gap with other shapes.^[17] He later found two more sets of aperiodic tiles, one consisting of tiles known as a 'kite' and a 'dart' (P2) and a second set consisting of two rhombuses (P3).^[18]

The original Penrose tiling (P1)

Penrose's first tiling uses pentagons and three other shapes: a star, a boat and a diamond, as shown on the left. In addition to the tiles, Penrose stated rules, usually called matching rules, that specify how tiles must be attached to one another; these rules are needed to ensure that the tilings are nonperiodic. As there are three distinct sets of matching rules for pentagonal tiles, it is common to consider the set as having three different pentagonal tiles, shown in different colors in the illustration. This leads to a set of six tiles: a thin rhombus or 'diamond', a five pointed star, a 'boat' (roughly 3/5 of a star) and three pentagons.^[8]

Kite and dart tiling (P2)

The quadrilaterals called the 'Kite' and 'Dart' can also be used to form a Penrose tiling.^[19]

Kite and Dart tiles

• The Kite is a quadrilateral whose four corners have angles of 72, 72, 72, and 144 degrees. The Kite may be bisected along its axis of symmetry to form a pair of acute Robinson triangles.
• The Dart is a non-convex quadrilateral whose four interior angles are 36, 72, 36, and 216 degrees. The Dart may be bisected along its axis of symmetry to form a pair of obtuse Robinson triangles.

The green and the red arcs in the tiles constrain the placement of tiles: When two tiles share an edge in a tiling, the patterns must match at these edges. For example, the concave vertex of a Dart cannot be filled with a single Kite to create a rhombus, but must be filled with a pair of Kites; this prevents the tiles being used to tile the plane periodically.^[20]

Rhombus tiling (P3)

The Penrose rhombuses are a pair of rhombuses with equal sides but different angles.

• The thin rhombus t has four corners with angles of 36, 144, 36, and 144 degrees. The t rhombus may be bisected along its short diagonal to form a pair of acute Robinson triangles.
• The thick rhombus T has angles of 72, 108, 72, and 108 degrees. The T rhombus may be bisected along its long diagonal to form a pair of obtuse Robinson triangles.

Two kinds of matching rules for Penrose rhombuses.

There are 54 cyclically ordered combinations of such angles that add up to 360 degrees at a vertex, but the rules of the tiling allow only 7 of these combinations to appear. Ordinary rhombus-shaped tiles can be used to tile the plane periodically, so restrictions must be made on how tiles can be assembled. The simplest rule, prohibiting two tiles to be put together to form a single parallelogram, is insufficient to ensure aperiodicity.^[21] Instead, rules are made that distinguish sides of the tiles and require that only particular sides can be put together with each other. An example of appropriate matching rules is shown in the upper part of the diagram to the right. Tiles must be assembled so that the curves across their edges match in color and position. An equivalent condition is that tiles must be assembled so that the bumps on their edges fit together. The same rules can be specified with other formulations.

There are arbitrarily large finite patches with tenfold symmetry and at most one center point of global tenfold symmetry where ten mirror lines cross. As the tiling is aperiodic, there is no translational symmetry—the pattern cannot be shifted to match itself over the entire plane. However, any bounded region, no matter how large, will be repeated an infinite number of times within the tiling. Therefore, a finite patch cannot differentiate between the uncountably many Penrose tilings, nor even determine which position within the tiling is being shown.^[22]

The rhombuses may be cut in half to form a pair of triangles, called Robinson triangles, which can be used to produce the Penrose tilings as a substitution tiling. The Robinson triangles are the isosceles 36º-36º-108º and 72º-72º-36º triangles. Each of these triangles has edges in the ratio of (1+√5):2, the golden ratio φ.^[23]

Constructions and properties

Deflation

A substitution method known as deflation, the steps of which are described below, will produce a kite and dart (P2) Penrose tiling.^[24][25] Starting with a finite tiling called the axiom, deflation proceeds with a sequence of steps called generations. The axiom can be as simple as a single tile. In one generation of deflation, each tile is replaced with one or more new tiles that exactly cover the area of the original tile. The new tiles are scaled-down versions of the original tiles. The substitution rules guarantee that the new tiles are arranged according to the matching rules.^[25] Repeated generations of deflation produce a tiling of the original axiom shape with smaller and smaller tiles. Given sufficiently many generations, the tiling will contain a scaled-down version of the axiom that does not touch the boundary of the tiling. The axiom can then be surrounded by full-size tiles corresponding to tiles that appear in the scaled-down version. This extended tiling can be used as a new axiom, producing larger and larger extended tilings and ultimately covers the entire plane.

An example: three generations of four axioms

This is an example of successive generations of deflation starting from different axioms. In the case of the 'Sun' and 'Star', the scaled-down interior version of the axiom appears in generation 2. The 'Sun' also appears in the interior of its generation 3.

Name	Generation 0 (or axiom)	Generation 1	Generation 2	Generation 3
Kite (half)
Dart (half)
Sun
Star

Golden ratio features

Length ratios in Penrose tiles.

Several properties and features of the Penrose tiling involve the golden ratio φ. This is a consequence of the local fivefold rotational symmetry of the tiling and the fact that the ratio of chord lengths to side lengths in a regular pentagon is φ. The ratio of the lengths of long sides to short sides in the isosceles Robinson triangles is φ:1. As a result, the ratio of the lengths of long sides to short sides in the kite and dart tiles, the ratio of the areas of the kite and dart tiles, the ratio of the lengths of sides to short diagonal in the thin rhombus and the ratio of lengths of long diagonal to sides in the thick rhombus are all φ:1.^[23][26]

The deflation construction decomposes a kite into two kites and a dart, and decomposes a dart into a kite and a dart. The number of kites and darts in the nth iteration of the construction is determined by the nth power of the substitution matrix:

where F_n is the nth Fibonacci number. The ratio of numbers of kites to darts in any sufficiently large P2 Penrose tiling pattern therefore tends to φ.^[27] A similar result holds for the ratio of the number of thick rhombuses to thin rhombuses in the P3 Penrose tiling.^[28]

Related tilings and topics

Decagonal coverings and quasicrystals

Gummelt's decagon (left) with the decomposition into kites and darts indicated by dashed lines; the thicker darker lines bound an inscribed ace and thick rhombus; possible overlaps (right) are by one or two red aces.^[29]

In 1996, German mathematician Petra Gummelt demonstrated that a covering (so called to distinguish it from a non-overlapping tiling) equivalent to the Penrose tiling can be constructed using a single decagonal tile if two kinds of overlapping regions are allowed.^[30] The decagonal tile is decorated with colored patches and the covering rule only allows overlaps compatible with the coloring. A suitable decomposition of the decagonal tile into kites and darts transforms such a covering into a Penrose (P2) tiling. Similarly, a P3 tiling can be obtained by inscribing a thick rhombus into each decagon; the remaining space is filled by thin rhombuses.

These coverings have been considered as a realistic model for the growth of quasicrystals: the overlapping decagons are 'quasi-unit cells' analogous to the unit cells from which crystals are constructed, and the matching rules maximize the density of certain atomic clusters.^[31][29]

Other tilings and Islamic art

A variant of the Penrose tiling which is not a quasicrystal

The three variants (P1–P3) of the Penrose tiling are equivalent in the sense of being mutually locally derivable,^[11] but there also exist related inequivalent tilings, such as the hexagon-boat-star and Mikulla–Roth tilings. For instance if the matching rules for the rhombus tiling are reduced to a specific restriction on the angles permitted at each vertex, a binary tiling is obtained.^[32] Its underlying symmetry is also fivefold but it is not a quasicrystal. It can be obtained either by decorating the rhombuses of the original tiling with smaller ones, or by substitution rules, but not by de Bruijn's cut-and-project method.^[33]

The aesthetic value of tilings has long been appreciated and remains a source of interest in them; here the visual appearance (rather than the formal defining properties) of Penrose tilings has attracted attention. The similarity with some decorative patterns used in the Middle East has been noted^[34] and Lu and Steinhardt have presented evidence that a Penrose tiling underlies some examples of medieval Islamic art.^[35]

Drop City artist Clark Richert used Penrose rhombuses in artwork in 1970. Art historian Martin Kemp has observed that Albrecht Dürer has sketched similar motifs of a rhombus tiling.^[36] The Penrose tilling pattern could be used to generate importance sampling samplers with blue noise properties at a high performance.^[37]

See also

• Zellige
• Aperiodic tiling
• Girih tiles
• Pinwheel tiling
• Quaquaversal tiling

Notes

References

Primary sources

• Berger, R. (1966), The undecidability of the domino problem, Memoirs of the American Mathematical Society, 66 .
• de Bruijn, N. G. (1981), "Algebraic theory of Penrose's nonperiodic tilings of the plane, I, II" (PDF), Indagationes mathematicae 43 (1): 39–66, http://alexandria.tue.nl/repository/freearticles/597566.pdf .
• Gummelt, Petra (1996), "Penrose tilings as coverings of congruent decagons", Geometriae Dedicata 62 (1), doi:10.1007/BF00239998 .
• Penrose, Roger (1974), "Role of aesthetics in pure and applied research", Bulletin of the Institute of Mathematics and its Applications 10: 266ff .
• Penrose, Roger, "Set of tiles for covering a surface", US 4133152, published 1976-06-24, issued 1979-01-09.
• Robinson, R.M. (1971), "Undecidability and nonperiodicity of tilings in the plane", Inventiones Mathematicae 12: 177–190 .
• Schechtman, D.; Blech, I.; Gratias, D.; Cahn, J.W. (1984), "Metallic Phase with long-range orientational order and no translational symmetry", Physical Review Letters 53: 1951–1953, doi:10.1103/PhysRevLett.53.1951 
• Wang, H. (1961), "Proving theorems by pattern recognition II", Bell Systems Technical Journal 40: 1–42 .

Secondary sources

• Austin, David (2005a), "Penrose Tiles Talk Across Miles", Feature Column (Providence: American Mathematical Society), http://www.ams.org/featurecolumn/archive/penrose.html .
• Austin, David (2005b), "Penrose Tilings Tied up in Ribbons", Feature Column (Providence: American Mathematical Society), http://www.ams.org/featurecolumn/archive/ribbons.html .
• Gardner, Martin (1997), Penrose Tiles to Trapdoor Ciphers, Cambridge University Press, ISBN 978-0883855218 . (First published by W. H. Freeman, New York (1989), ISBN 978-0716719861.)
  • Chapter 1 (pp. 1–18) is a reprint of Gardner, Martin (January 1977), "Extraordinary nonperiodic tiling that enriches the theory of tiles", Scientific American 236: 110–121 .
• Godrèche, C; Lançon, F. (1992), "A simple example of a non-Pisot tiling with five-fold symmetry", Journal de Physique I 2: 207–220, doi:10.1051/jp1:1992134, http://www.edpsciences.org/10.1051/jp1:1992134 .
• Grünbaum, Branko; Shephard, G. C. (1987), Tilings and Patterns, New York: W. H. Freeman, ISBN 978-716711933 .
• Kemp, Martin (2005), "Science in culture: A trick of the tiles", Nature 436: 332, doi:10.1038/436332a .
• Lançon, Frédéric; Billard, Luc (1988), "Two-dimensional system with a quasi-crystalline ground state", Journal de Physique 4: 249–256, doi:10.1051/jphys:01988004902024900, http://inac.cea.fr/sp2m/L_Sim/Publications/1988/Lancon-Billard-1988-binary_tilings.pdf .
• Lord, E.A.; Ranganathan, S. (2001), "The Gummelt decagon as a 'quasi unit cell'", Acta Crystallographica A57: 531–539, doi:10.1107/S0108767301007504, http://materials.iisc.ernet.in/~lord/webfiles/actagum.pdf 
• Lu, Peter J.; Steinhardt, Paul J. (2007), "Decagonal and Quasi-crystalline Tilings in Medieval Islamic Architecture", Science 315: 1106–1110, doi:10.1126/science.1135491, PMID 17322056, http://www.physics.harvard.edu/~plu/publications/Science_315_1106_2007.pdf .
• Luck, R. (2000), "Dürer-Kepler-Penrose: the development of pentagonal tilings", Materials Science and Engineering 294 (6): 263–267 .
• Ostromoukhov, Victor; Donohue, Charles; Jodoin, Pierre-Marc (2004), "Fast Hierarchical Importance Sampling with Blue Noise Properties", ACM Transactions on Graphics (ACM Press) 23 (3): 488–495, http://www.iro.umontreal.ca/~ostrom/ImportanceSampling/ .
• Makovicky, E. (1992), "800-year-old pentagonal tiling from Maragha, Iran, and the new varieties of aperiodic tiling it inspired", in I. Hargittai, Fivefold Symmetry, Singapore–London: World Scientific, pp. 67–86 .
• Senechal, Marjorie (1996), Quasicrystals and geometry, Cambridge University Press, ISBN 978-0521575416 .
• Steinhardt, Paul J.; Jeong, Hyeong-Chai (1996), "A simpler approach to Penrose tiling with implications for quasicrystal formation", Nature 382 (01 August): 431–433, doi:10.1038/382431a0, http://www.nature.com/nature/journal/v382/n6590/abs/382431a0.html .
• Zaslavskiĭ, G.M.; Sagdeev, Roal'd Z.; Usikov, D.A.; Chernikov, A.A. (1988), "Minimal chaos, stochastic web and structures of quasicrystal symmetry", Soviet Physics Uspekhi 31: 887–915, doi:10.1070/PU1988v031n10ABEH005632 .

External links

Wikimedia Commons has media related to: Penrose tilings

There are many internet resources related to Penrose tilings; the following is a selection.

• Weisstein, Eric W., "Penrose Tiles" from MathWorld.
• John Savard, "Penrose Tilings", quadibloc.com, http://www.quadibloc.com/math/pen01.htm, retrieved 2009-11-28. 
• Eric Hwang, "Penrose Tiling", intendo.net, http://intendo.net/penrose/info.html, retrieved 2009-11-28. 
• E. Harriss and D. Frettlöh, "Penrose Rhomb", Tilings Encyclopedia, Department of Mathematics, University of Bielefeld, http://tilings.math.uni-bielefeld.de/substitution_rules/penrose_rhomb, retrieved 2009-11-28. 
• Kevin Brown, "On de Bruijn Grids and Tilings", mathpages.com, http://www.mathpages.com/home/kmath621/kmath621.htm, retrieved 2009-11-28. 
• David Eppstein, "Penrose Tiles", The Geometry Junkyard, www.ics.uci.edu/~eppstein, http://www.ics.uci.edu/~eppstein/junkyard/penrose.html, retrieved 2009-11-28.  This has a list of additional resources.