Aperiodic set of prototiles

Last updated
.mw-parser-output .hidden-begin{box-sizing:border-box;width:100%;padding:5px;border:none;font-size:95%}.mw-parser-output .hidden-title{font-weight:bold;line-height:1.6;text-align:left}.mw-parser-output .hidden-content{text-align:left}@media all and (max-width:500px){.mw-parser-output .hidden-begin{width:auto!important;clear:none!important;float:none!important}}
Click "show" for description.
A periodic tiling with a fundamental unit (triangle) and a primitive cell (hexagon) highlighted. A tiling of the entire plane can be generated by fitting copies of these triangular patches together. To do this, the basic triangle must be rotated 60 degrees to fit edge-to-edge to a neighboring triangle. Thus a triangular tiling of fundamental units is generated that is mutually locally derivable from the tiling by the colored tiles. The other figure drawn onto the tiling, the white hexagon, represents a primitive cell of the tiling. Copies of the corresponding patch of coloured tiles can be translated to form an infinite tiling of the plane. It is not necessary to rotate this patch to achieve this. Fund un prim cell.svg
Click "show" for description.
A periodic tiling with a fundamental unit (triangle) and a primitive cell (hexagon) highlighted. A tiling of the entire plane can be generated by fitting copies of these triangular patches together. To do this, the basic triangle must be rotated 60 degrees to fit edge-to-edge to a neighboring triangle. Thus a triangular tiling of fundamental units is generated that is mutually locally derivable from the tiling by the colored tiles. The other figure drawn onto the tiling, the white hexagon, represents a primitive cell of the tiling. Copies of the corresponding patch of coloured tiles can be translated to form an infinite tiling of the plane. It is not necessary to rotate this patch to achieve this.
The Penrose tiles are an aperiodic set of tiles, since they admit only non-periodic tilings of the plane (see next image). Penrose Rhombi BR.svg
The Penrose tiles are an aperiodic set of tiles, since they admit only non-periodic tilings of the plane (see next image).
All of the infinitely many tilings by the Penrose tiles are aperiodic. That is, the Penrose tiles are an aperiodic set of prototiles. Penrose tiling.svg
All of the infinitely many tilings by the Penrose tiles are aperiodic. That is, the Penrose tiles are an aperiodic set of prototiles.

A set of prototiles is aperiodic if copies of the prototiles can be assembled to create tilings, such that all possible tessellation patterns are non-periodic. The aperiodicity referred to is a property of the particular set of prototiles; the various resulting tilings themselves are just non-periodic.

Contents

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 — that is, 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 as periodic tilings. (For example, randomly arranged tilings using a 2×2 square and 2×1 rectangle are typically non-periodic.)

However, an aperiodic set of tiles can only produce non-periodic tilings. [1] [2] Infinitely many distinct tilings may be obtained from a single aperiodic set of tiles. [3]

The best-known examples of an aperiodic set of tiles are the various Penrose tiles. [4] [5] The known aperiodic sets of prototiles are seen on the list of aperiodic sets of tiles. The underlying undecidability of the domino problem implies that there exists no systematic procedure for deciding whether a given set of tiles can tile the plane.

History

Polygons are plane figures bounded by straight line segments. Regular polygons have all sides of equal length as well as all angles of equal measure. As early as AD 325, Pappus of Alexandria knew that only 3 types of regular polygons (the square, equilateral triangle, and hexagon) can fit perfectly together in repeating tessellations on a Euclidean plane. Within that plane, every triangle, irrespective of regularity, will tessellate. In contrast, regular pentagons do not tessellate. However, irregular pentagons, with different sides and angles can tessellate. There are 15 irregular convex pentagons that tile the plane. [6]

Polyhedra are the three dimensional correlates of polygons. They are built from flat faces and straight edges and have sharp corner turns at the vertices. Although a cube is the only regular polyhedron that admits of tessellation, many non-regular 3-dimensional shapes can tessellate, such as the truncated octahedron.

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 in 1928, but sets of aperiodic tiles have been considered as a natural extension. [7] The specific question of aperiodic sets of tiles 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.

These Wang tiles yield only non-periodic tilings of the plane, and so are aperiodic. Wang tiles.svg
These Wang tiles yield only non-periodic tilings of the plane, and so are aperiodic.

Hence, when in 1966 Robert Berger found an aperiodic set of prototiles this demonstrated that the tiling problem is in fact not decidable. [8] (Thus Wang's procedures do not work on all tile sets, although that does not render them useless for practical purposes.) 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. [9] 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. [10] 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. The question of whether an aperiodic set exists with only a single prototile is known as the einstein problem.

Constructions

There are few constructions of aperiodic tilings known, even forty years after Berger's groundbreaking construction. Some constructions are of infinite families of aperiodic sets of tiles. [11] [12] Those constructions that have been found are mostly constructed in one of 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.

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 of prototiles requires two or more dimensions.[ citation needed ]

Related Research Articles

<span class="mw-page-title-main">Prototile</span> Basic shape(s) used in a tessellation

In mathematics, a prototile is one of the shapes of a tile in a tessellation.

<span class="mw-page-title-main">Wang tile</span> Square tiles with a color on each edge

Wang tiles, first proposed by mathematician, logician, and philosopher Hao Wang in 1961, is a class of formal systems. They are modeled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.

<span class="mw-page-title-main">Kite (geometry)</span> Quadrilateral symmetric across a diagonal

In Euclidean geometry, a kite is a quadrilateral with reflection symmetry across a diagonal. Because of this symmetry, a kite has two equal angles and two pairs of adjacent equal-length sides. Kites are also known as deltoids, but the word deltoid may also refer to a deltoid curve, an unrelated geometric object sometimes studied in connection with quadrilaterals. A kite may also be called a dart, particularly if it is not convex.

<span class="mw-page-title-main">Tessellation</span> Tiling of a plane in mathematics

A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called tiles, with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of geometries.

<span class="mw-page-title-main">Aperiodic tiling</span> Form of plane tiling without repeats at scale

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 is aperiodic if copies of these tiles can form only non-periodic tilings.

<span class="mw-page-title-main">Euclidean tilings by convex regular polygons</span> Subdivision of the plane into polygons that are all regular

Euclidean plane tilings by convex regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in his Harmonices Mundi.

<span class="mw-page-title-main">Heesch's problem</span> On surrounding polygons by layers of copies

In geometry, the Heesch number of a shape is the maximum number of layers of copies of the same shape that can surround it with no overlaps and no gaps. Heesch's problem is the problem of determining the set of numbers that can be Heesch numbers. Both are named for geometer Heinrich Heesch, who found a tile with Heesch number 1 and proposed the more general problem.

<span class="mw-page-title-main">Hexagonal tiling</span> Regular tiling of a two-dimensional space

In geometry, the hexagonal tiling or hexagonal tessellation is a regular tiling of the Euclidean plane, in which exactly three hexagons meet at each vertex. It has Schläfli symbol of {6,3} or t{3,6} .

<span class="mw-page-title-main">Elongated triangular tiling</span>

In geometry, the elongated triangular tiling is a semiregular tiling of the Euclidean plane. There are three triangles and two squares on each vertex. It is named as a triangular tiling elongated by rows of squares, and given Schläfli symbol {3,6}:e.

<span class="mw-page-title-main">Pentagonal tiling</span> A tiling of the plane by pentagons

In geometry, a pentagonal tiling is a tiling of the plane where each individual piece is in the shape of a pentagon.

In geometry, a tile substitution is a method for constructing highly ordered tilings. Most importantly, some tile substitutions generate aperiodic tilings, which are tilings whose prototiles do not admit any tiling with translational symmetry. The most famous of these are the Penrose tilings. Substitution tilings are special cases of finite subdivision rules, which do not require the tiles to be geometrically rigid.

Geometry is a branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. Geometry is one of the oldest mathematical sciences.

In geometry, a uniform tiling is a tessellation of the plane by regular polygon faces with the restriction of being vertex-transitive.

<span class="mw-page-title-main">Ammann–Beenker tiling</span> Non-periodic tiling of the plane

In geometry, an Ammann–Beenker tiling is a nonperiodic tiling which can be generated either by an aperiodic set of prototiles as done by Robert Ammann in the 1970s, or by the cut-and-project method as done independently by F. P. M. Beenker. They are one of the five sets of tilings discovered by Ammann and described in Tilings and patterns.

<span class="mw-page-title-main">Penrose tiling</span> Non-periodic tiling of the plane

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 a tiling is aperiodic if it does not contain arbitrarily large periodic regions or patches. However, despite their lack of translational symmetry, Penrose tilings may have both reflection symmetry and fivefold rotational symmetry. Penrose tilings are named after mathematician and physicist Roger Penrose, who investigated them in the 1970s.

<span class="mw-page-title-main">Pythagorean tiling</span> Tiling by squares of two sizes

A Pythagorean tiling or two squares tessellation is a tiling of a Euclidean plane by squares of two different sizes, in which each square touches four squares of the other size on its four sides. Many proofs of the Pythagorean theorem are based on it, explaining its name. It is commonly used as a pattern for floor tiles. When used for this, it is also known as a hopscotch pattern or pinwheel pattern, but it should not be confused with the mathematical pinwheel tiling, an unrelated pattern.

<span class="mw-page-title-main">Conway criterion</span> Rule from the theory of the tiling of the plane

In the mathematical theory of tessellations, the Conway criterion, named for the English mathematician John Horton Conway, is a sufficient rule for when a prototile will tile the plane. It consists of the following requirements: The tile must be a closed topological disk with six consecutive points A, B, C, D, E, and F on the boundary such that:

<span class="mw-page-title-main">Einstein problem</span> Question about single-shape aperiodic tiling

In plane geometry, the einstein problem asks about the existence of a single prototile that by itself forms an aperiodic set of prototiles; that is, a shape that can tessellate space but only in a nonperiodic way. Such a shape is called an einstein, a word play on ein Stein, German for "one stone".

<span class="mw-page-title-main">Binary tiling</span> Tiling of the hyperbolic plane

In geometry, a binary tiling is a tiling of the hyperbolic plane, resembling a quadtree over the Poincaré half-plane model of the hyperbolic plane. The tiles are congruent, each adjoining five others. They may be convex pentagons, or non-convex shapes with four sides, alternatingly line segments and horocyclic arcs, meeting at four right angles.

References

  1. Senechal, Marjorie (1996) [1995]. Quasicrystals and geometry (corrected paperback ed.). Cambridge University Press. ISBN   978-0-521-57541-6.
  2. Grünbaum, Branko; Geoffrey C. Shephard (1986). Tilings and Patterns. W.H. Freeman & Company. ISBN   978-0-7167-1194-0.
  3. A set of aperiodic prototiles can always form uncountably many different tilings, even up to isometry, as proven by Nikolaï Dolbilin in his 1995 paper The Countability of a Tiling Family and the Periodicity of a Tiling
  4. Gardner, Martin (January 1977). "Mathematical Games". Scientific American. 236 (5): 111–119. Bibcode:1977SciAm.236e.128G. doi:10.1038/scientificamerican0577-128.
  5. Gardner, Martin (1988). Penrose Tiles to Trapdoor Ciphers . W H Freeman & Co. ISBN   978-0-7167-1987-8.
  6. "Pentagon Tiling Proof Solves Century-Old Math Problem". 11 July 2017.
  7. Senechal, pp 22–24.
  8. Berger, Robert (1966). "The undecidability of the domino problem". Memoirs of the American Mathematical Society (66): 1–72.
  9. Grünbaum and Shephard, section 11.1.
  10. Robinson, Raphael M. (1971). "Undecidability and Nonperiodicity for Tilings of the Plane". Inventiones Mathematicae . 12 (3): 177–209. Bibcode:1971InMat..12..177R. doi:10.1007/BF01418780. S2CID   14259496.
  11. Goodman-Strauss, Chaim (1998). "Matching rules and substitution tilings". Annals of Mathematics . 147 (1): 181–223. CiteSeerX   10.1.1.173.8436 . doi:10.2307/120988. JSTOR   120988.
  12. Mozes, Shahar (1989). "Tilings, substitution systems and dynamical systems generated by them". Journal d'Analyse Mathématique . 53 (1): 139–186. doi:10.1007/BF02793412. S2CID   121775031.