12 1. BASIC NOTIONS

Exercise 1.7. Show that for the Thue-Morse substitution, Ωσ =

ΩT .

(2) The Fibonacci substitution is σ(a) = b, σ(b) = ab. The substitution

matrix is

(

0 1

1 1

)

, whose Perron-Frobenius eigenvalue equals the golden

mean τ = (1 +

√

5)/2. The corresponding left- and right-eigenvectors

are L = (1, τ ) and R =

(

1

τ

)

. As with the Thue-Morse sequence, there

is a fixed point of

σ2

built from the seed b.a. To get a tiling, we take

the a-tile to have length 1 and the b-tile to have length τ . On average,

there are τ b-tiles for every a-tile. This shows that there are no periodic

tilings in Ωσ, since the ratio of a to b-tiles in a periodic tiling would

have to be rational.

(3) The period-doubling substitution has σ(a) = bb, σ(b) = ab. The matrix

is

(

0 1

2 1

)

, with λP

F

= 2, L = (1, 1) and R =

(

1

2

)

. Once again, a fixed

point of

σ2

can be built from the seed b.a

There is a map from the Thue-Morse tiling space to the period-

doubling tiling space. If a Thue-Morse tile is preceded by a tile of the

same type, replace it with a period-doubling a tile. If it is preceded by

a tile of the opposite type, replace it with a period-doubling b tile.

Exercise 1.8. Let ΩT

M

and ΩP

D

denote the Thue-Morse and period-

doubling substitution tiling spaces, respectively, and let f : ΩT

M

→ ΩP

D

be

as above. Show that f intertwines the two substitutions. That is, σP

D

◦ f =

f ◦ σT

M

. Use this fact to show that f is a 2:1 cover of ΩP

D

by ΩT

M

.

A brief digression into history. Substitution sequences were studied at

length long before aperiodic tilings became fashionable. Thue invented the

Thue-Morse sequence in the late 1800s, and Morse reinvented it in the 1930s

to prove properties of geodesics on Riemann surfaces. Traditionally, the

central object of study wasn’t the space of sequences, but rather a particular

sequence that was fixed by some power of the substitution. The sequence

space could then be recovered from this fixed point by taking its orbit under

a shift map, and then taking the completion of that orbit in a metric that

is similar to our tiling metric.

Substitution tilings in higher dimensions. A substitution in one

dimension is combinatorial — replace each letter with a word. In higher di-

mensions, we must also consider the geometry of the tiles. Given a stretching

factor λ 1, a substitution is an operation that

(1) Stretches each tile by a linear factor λ, and

(2) Replaces each stretched tile by a cluster of (ordinary-sized) tiles, as in

Figure 1.10. As before, these clusters are called supertiles (of order 1).

The substitution matrix is as before, and Mij gives the number of i-tiles

in a substituted j-tile. The left-eigenvector L = (L1, . . . , Lk) specifies their

volumes of the different tile types, but has no information about their shapes.