1.4. CONTRUCTING INTERESTING TILINGS 11
Definition. If σ is a primitive substitution on an alphabet {a1, . . . , ak},
we call a bi-infinite word σ-admissible if each finite sub-word can be found
in
σn(a1)
for some n ≥ 0.
In such cases, let L = (L1, . . . , Lk) be a left-eigenvector of the substitu-
tion matrix corresponding to λP
F
, and consider tiles with labels a1, . . . , ak
and lengths L1, . . . , Lk.
Exercise 1.3. Show that the length of the patch corresponding to
σn(aj
)
is λP
n
F
Lj .
Exercise 1.4. Show that, as n → ∞, the fraction of letters of type ai
in
σn(aj
) approaches Ri/
∑
k
Rk, and in particular is independent of j.
Definition. Given a substitution σ, the sequence space Sσ is the set
of all bi-infinite σ-admissible words and the tiling space Ωσ consists of all
tilings by the tiles (a1, . . . , ak) such that the corresponding sequence of letters
(a1, . . . , ak) forms a σ-admissible word. The substitution σ acts on Sσ by
replacing each letter with a word. It acts on Ωσ by first stretching the tiling
by a factor of λP
F
about the origin, and then replacing each stretched tile of
type aj with tiles corresponding to the word σ(aj ).
Exercise 1.5. Show that for any integer k 0 and any substitution σ,
Ωσ = Ωσk
Definition. A patch of a tiling corresponding to
σn(ai)
is called a su-
pertile of level n (or order n) and type i. Ωσ is the set of tilings with the
property that every patch is found inside a supertile of some order.
Theorem 1.3. [Mos, Sol] If σ is a primitive substitution and Ωσ con-
tains at least one non-periodic tiling, then every tiling in Ωσ is non-periodic
and σ : Ωσ → Ωσ is a homeomorphism.
In particular, if T ∈ Ωσ, then there is a unique way to group the tiles of
T into supertiles of order 1, such that the pattern of supertiles looks like a
scaled-up version of a tiling in Ωσ.
Examples.
(1) Thue-Morse sequences have an alphabet of two letters, a and b, with
the substitution σ(a) = ab, σ(b) = ba. Note that
σ2(a)
= abba be-
gins with a and
σ2(b)
= baab ends with b. Let w = b.a, with the
dot indicating the location of the origin.
σ2(w)
= baab.abba con-
tains w in the center. Likewise,
σ4(w)
contains
σ2(w),
and gener-
ally
σn+2(w)
contains
σn(w).
Taking limits we find a sequence u =
. . . abbaabbabaab.abbabaabbaababba . . . with
σ2(u)
= u. We can make a
tiling T out of u by thinking of each letter as a tile of length 1.
Exercise 1.6. Consider the patch bbaababbabaababbaabbaba of a
Thue-Morse tiling. Group the tiles into supertiles of level 1, 2, etc., as
far as you can go. Note that near the edges, a supertile may only be
partially in the patch.
