Substitution Tiling - Introduction

Introduction

A tile substitution is described by a set of prototiles (tile shapes), an expanding map and a dissection rule showing how to dissect the expanded prototiles to form copies of some prototiles . 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.