Substitution tiling

Substitution tiling

A tile substitution is a useful 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.

Introduction

A tile substitution is described by a set of prototiles (tile shapes) T_1,T_2,..., T_m, an expanding map Q and a dissection rule showing how to dissect the expanded prototiles Q T_i to form copies of some prototiles T_j. Intuitively, higher and higher iterations of tile substitution produce a tiling of the plane called a substitution tiling. Some substitution tilings are periodic, defined as having translational symmetry. Among the nonperiodic substitution tilings are some aperiodic tilings, those whose prototiles cannot be rearranged to form a periodic tiling (usually if one requires in addition some matching rules).

A simple example that produces a periodic tiling has only one prototile, namely a square:

By iterating this tile substitution, larger and larger regions of the plane are covered with a square grid. A more sophisticated example with two prototiles is shown below, with the two steps of blowing up and dissecting are merged into one step in the figure.

One may intuitively get an idea how this procedure yields a substitution tiling of the entire plane. A mathematically proper definition is given below. Substitution tilings are notably useful as ways of defining aperiodic tilings, which are objects of interest in many fields of mathematics, including automata theory,combinatorics, discrete geometry, dynamical systems, group theory, harmonic analysis and number theory, not to mention the impact which were induced by those tilings in crystallography and chemistry. In particular, the celebrated Penrose tiling is an example of an aperiodic substitution tiling.

History

In 1973 and 1974, Roger Penrose discovered a family of aperiodic tilings, now called Penrose tilings. The first description was given in terms of 'matching rules' treating the prototiles as jigsaw puzzle pieces. The proof that copies of these prototiles can be put together to form a tiling of the plane, but cannot do so periodically, uses a construction that can be cast as a substitution tiling of the prototiles. In 1977 Robert Ammann discovered a number of sets of aperiodic prototiles, i.e., prototiles with matching rules forcing nonperiodic tilings; in particular, he rediscovered Penrose's first example. This work gave an impact to scientists working in crystallography, eventually leading to the discovery of quasicrystals. In turn, the interest in quasicrystals led to the discovery of several well-ordered aperiodic tilings. Many of them can be easily described as substitution tilings.

Mathematical definition

We will consider regions in {mathbb R}^d that are well-behaved, in the sense that a region is a nonempty compact subset that is the closure of its interior.

We take a set of regions old{P} = { T_1, T_2,..., T_m } as prototiles. A placement of a prototile T_i is a pair ( T_i, varphi ) where varphiis an isometry of {mathbb R}^d. The image varphi(T_i) is called the placement's region. A tiling T is a set of prototile placements whose regions have pairwise disjoint interiors. We say that the tiling T is a tiling of W where W is the union of the regions of the placements in T.

A tile substitution is often loosely defined in the literature. A precise definition is as follows [D. Frettlöh, Duality of Model Sets Generated by Substitutions, Romanian J. of Pure and Applied Math. 50, 2005] .

A tile substitution with respect to the prototiles P is a pair (Q, sigma), where Q: {mathbb R}^d o {mathbb R}^d is a linear map, all of whose eigenvalues are larger than one in modulus, together with a substitution rule sigma that maps each T_i to a tiling of Q T_i. The tile substitution sigma induces a map from any tiling T of a region W to a tiling sigma(old{T}) of Q_sigma(old{W}), defined by: sigma(old{T}) = igcup_{(T_i,varphi) in old{T { ( T_j, Q circ varphi circ Q^{-1} circ ho ) : (T_j, ho) in sigma(T_i) } .

Note, that the prototiles can be deduced from the tile substitution. Therefore it is not necessary to include them in the tile substitution (Q,sigma) [A. Vince, Digit Tiling of Euclidean Space, in: Directions in Mathematical Quasicrystals, eds: M. Baake, R.V. Moody, AMS, 2000] .

Every tiling of {mathbb R}^d, where any finite part of it is congruent to a subsetof some sigma^k(T_i) is called a substitution tiling (for the tile substitution (Q, sigma)).

References

External links

# Dirk Frettlöh's and Edmund Harriss's [http://tilings.math.uni-bielefeld.de/tilings/index Encyclopedia of Substitution Tilings]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Aperiodic tiling — are an aperiodic set of tiles, since they admit only non periodic tilings of the plane:] 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… …   Wikipedia

  • Penrose tiling — A Penrose tiling is a nonperiodic tiling generated by an aperiodic set of prototiles named after Roger Penrose, who investigated these sets in the 1970s.Because all tilings obtained with the Penrose tiles are non periodic, Penrose tilings are… …   Wikipedia

  • Quaquaversal tiling — The quaquaveral tiling is an nonperiodic three dimensional substitution tiling of space proposed by John Conway and Charles Radin. The basic solid tiles are half prisms arranged in a pattern which relies essentially on their previous construct,… …   Wikipedia

  • Ammann–Beenker tiling — In geometry, an Ammann–Beenker tiling is a nonperiodic tiling generated by an aperiodic set of prototiles named after Robert Ammann, who first discovered the tilings in the 1970s, and after F. P. M. Beenker who discovered them independently and… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Quasicrystal — Atomic model of an aluminum palladium manganese (Al Pd Mn) quasicrystal surface. Similar to Fig. 6 in Ref.[1] A quasiperiodic crystal, or, in short, quasicrystal, is a structure that is ordered but not periodic. A quasicrystalline pattern can… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Wang tile — Wang tiles (or Wang dominoes), first proposed by mathematician Hao Wang in 1961, are a class of formal systems. They are modelled visually by equal sized squares with a color on each edge which can be arranged side by side (on a regular square… …   Wikipedia

  • MicroRNA — The stem loop secondary structure of a pre microRNA from Brassica oleracea. A microRNA (abbreviated miRNA) is a short ribonucleic acid (RNA) molecule found in eukaryotic cells. A microRNA molecule has very few nucleotides (an average of 22)… …   Wikipedia

  • Liste De Fractales Par Dimension De Hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”