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.