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.
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.
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.
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.
Image:subst-haus.png
One may intuitively get an idea how this procedure yields a substitution tiling of the entire
plane. A mathematically rigorous 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, as well as
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
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
as prototiles. A placement of a prototile
is a pair
where
is an
isometry of
. The image
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.
A tile substitution with respect to the prototiles P is a pair
, where
is a
linear map, all of whose
eigenvalues are larger than one in modulus, together with a substitution rule
that maps each
to a tiling of
. The substitution rule
induces a map from any tiling T of a region W to a tiling
of
, defined by
:
Note, that the prototiles can be deduced from the tile substitution. Therefore it is not necessary to include them in the tile substitution
.
[A. Vince, Digit Tiling of Euclidean Space, in: Directions in Mathematical Quasicrystals, eds: M. Baake, R.V. Moody, AMS, 2000]
Every tiling of
, where any finite part of it is congruent to a subset
of some
is called a substitution tiling (for the tile substitution
).
See also
*
Pinwheel tiling
*
Photographic mosaic
References
Further reading
*
External links
*Dirk Frettlöh's and Edmund Harriss'
Encyclopedia of Substitution Tilings
{{Tessellation
Category:Tessellation