Substitution tiling

In geometry, a tile substitution is a method for constructing highly ordered

, which do not require the tiles to be geometrically rigid.

Introduction

A tile substitution is described by a set of prototiles (tile shapes) ${\displaystyle T_{1},T_{2},\dots ,T_{m}}$, an expanding map ${\displaystyle Q}$ and a dissection rule showing how to dissect the expanded prototiles ${\displaystyle QT_{i}}$ to form copies of some prototiles ${\displaystyle 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. Every substitution tiling (up to mild conditions) can be "enforced by matching rules"—that is, there exist a set of marked tiles that can only form exactly the substitution tilings generated by the system. The tilings by these marked tiles are necessarily aperiodic.^[1][2]

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 merged into one step.

One may intuitively get an idea how this procedure yields a substitution tiling of the entire

is an example of an aperiodic substitution tiling.

History

In 1973 and 1974,

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 ${\displaystyle {\mathbb {R} }^{d}}$ that are

.

We take a set of regions ${\displaystyle \mathbf {P} =\{T_{1},T_{2},\dots ,T_{m}\}}$ as prototiles. A placement of a prototile ${\displaystyle T_{i}}$ is a pair ${\displaystyle (T_{i},\varphi )}$ where ${\displaystyle \varphi }$is an isometry of ${\displaystyle {\mathbb {R} }^{d}}$. The image ${\displaystyle \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.^[3]

A tile substitution with respect to the prototiles P is a pair ${\displaystyle (Q,\sigma )}$, where ${\displaystyle Q:{\mathbb {R} }^{d}\to {\mathbb {R} }^{d}}$ is a

are larger than one in modulus, together with a substitution rule ${\displaystyle \sigma }$ that maps each ${\displaystyle T_{i}}$ to a tiling of ${\displaystyle QT_{i}}$. The substitution rule ${\displaystyle \sigma }$ induces a map from any tiling T of a region W to a tiling ${\displaystyle \sigma (\mathbf {T} )}$ of ${\displaystyle Q_{\sigma }(\mathbf {W} )}$, defined by

${\displaystyle \sigma (\mathbf {T} )=\bigcup _{(T_{i},\varphi )\in \mathbf {T} }\{(T_{j},Q\circ \varphi \circ Q^{-1}\circ \rho ):(T_{j},\rho )\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 ${\displaystyle (Q,\sigma )}$.^[4]

Every tiling of ${\displaystyle {\mathbb {R} }^{d}}$, where any finite part of it is congruent to a subset of some ${\displaystyle \sigma ^{k}(T_{i})}$ is called a substitution tiling (for the tile substitution ${\displaystyle (Q,\sigma )}$).

See also

• Pinwheel tiling
• Photographic mosaic

References

Further reading

• Pytheas Fogg, N. (2002).
  Zbl 1014.11015
  .

External links

• Dirk Frettlöh's and Edmund Harriss's Encyclopedia of Substitution Tilings