Substitution tiling

From Wikipedia, the free encyclopedia

A tile-substitution is a simple way to generate highly ordered tilings without any translational symmetry, in other words: aperiodic tilings. The most famous examples are certainly the Penrose tilings.

1 Introduction
2 History
3 Mathematical definition
4 External links

[edit] Introduction

A simple way to generate a large number of interesting tilings, both periodic tilings and aperiodic tilings (aka nonperiodic tilings), is via a tile-substitution. A tile-substitution is described by a set of building blocks (prototiles) $T 1, T 2,..., T m$ , an expanding map $\varphi$ and a rule how to dissect each 'blown up' prototile $\varphi T_i$ into copies of some prototiles $T j$ . Here is a simple example with only one prototile, namely a square:

By iterating the tile-substitution larger and larger regions of the plane are covered. In the last example, one obtains just a square grid. Here is a more sophisticated example with two prototiles (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. Those tilings, in particular the ones without any translational symmetry, are objects of interest in many fields of mathematics, for instance 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 a substitution tiling.

[edit] History

In 1973 and 1974, Roger Penrose discovered a family of nonperiodic tilings, see Penrose tiling. The first description was given in terms of 'matching rules', i.e., the tiles were shaped like jigsaws. They can be put together to a tiling covering the whole plane without gaps. But none of these tilings possesses a translational symmetry, i.e., they are nonperiodic. The proof that these tilings are in fact nonperiodic uses the fact that they are essentially substitution tilings. 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 hype about quasicrystals lead to the discovery of several well-ordered nonperiodic tilings. Many of them can be easily described as substitution tilings.

[edit] Mathematical definition

Let $T 1, T 2,..., T m$ be nonempty compact subsets in ${\mathbb R}^d$ such that each $T i$ is the closure of its interior. Let $Q$ be an expanding linear map (i.e., all eigenvalues of Q are larger than one in modulus). Furthermore, let $Q T_i = \bigcup_{1 \le j \le m} T_j + x_{ijk}$ such that the elements in the union on the right hand side do not overlap, i.e., their interiors are pairwise disjoint (where the $t i j k$ are appropriate translation vectors). Let T be the set of all sets of copies of the prototiles $T i$ . Then, $σ:$ T $\to$ T, $\sigma(\{ T_{i(k)} + t_k \, | \, k \in K \} = \{ T_j + x_{ijk} + Q t_k \, | \, k \in K \}$ maps any set (finite or infinite) of copies of the prototiles to a larger one.

Even if this sounds technical, this definition just describes what was shown in the introduction above (and makes it precise): Applying $σ$ to a single tile blows it up and dissects it into other tiles. Moreover, $σ k$ describes exactly k iterations of the tile-substitution.

Now, given a tile-substitution $σ$ , a tiling T consisting of copies of the prototiles $T 1, T 2,..., T m$ is called substitution tiling (for the tile substitution $σ$ ), if each finite pattern in T is a copy of some pattern in $σ k (T i)$ (for some k,i).