8.2 Shifts of ¬nite type.

For example, let M be any positive integer and suppose that we map XF ‚ AZ

into (AM )Z as follows: A “letter” in AM is an M -tuplet of letters of A. De¬ne

the map φ : XF ’ (AM )Z by letting φ(x)i = [xi , xi+M ]. For example, if M = 5

and we write the 5-tuplets as column vectors, the element x is mapped to

« « « «

x’1 x0 x1 x2

¬ x0 · ¬ x1 · ¬ x2 · ¬ x3 ·

¬ ·¬ ·¬ ·¬ ·

. . . , ¬ x1 · , ¬ x2 · , ¬ x3 · , ¬ x4 · , dots.

¬ ·¬ ·¬ ·¬ ·

x2 x3 x4 x5

x3 x4 x5 x6

This map is clearly a sliding code, hence continuous, and commutes with shift

hence is a homomorphism. On the other hand it is clearly bijective since we can

recover x from its image by reading the top row. Hence it is a conjugacy of X

onto its image. Call this image X M .

We say that X is of ¬nite type if we can choose a ¬nite set F of forbidden

words so that X = XF .

8.2.1 One step shifts.

If w is a forbidden word for X, then any word which contains w as a substring

is also forbidden. If M + 1 denotes the largest length of a word in F, we may

enlarge all the remaining words by adding all su¬xes and pre¬xes to get words

of length M . Hence, with no loss of generality, we may assume that all the words

of F have length M . So F ‚ AM . Such a shift is called an M -step shift. But if

we pass from X to X M +1 , the elements of (A)M+∞ are now the alphabet. So

excluding the elements of F means that we have replaced the alphabet AM +1

by the smaller alphabet E, the complement of F in AM+∞ . Thus X M +1 ‚ E Z .

The condition that an element of B Z actually belong to X is easy to describe:

An M + 1-tuplet yi can be followed by an M + 1-tuplet yi+1 if and only if the

last M entries in yi coincide with the ¬rst M entries in yi+1 . All words w = yy

which do not satisfy this condition are excluded. but all these words have length

two. We have proved that the study of shifts of ¬nite type is the same as the

study of one step shifts.

8.2.2 Graphs.

We can rephrase the above argument in the language of graphs. For any shift

and any positive integer K X we let WK (X) denote the set of all admissible

words of length K. Suppose that X is an M -step shift. Let us set

V := WM (X),

and de¬ne

E = WM +1 (X)

141

8.2. SHIFTS OF FINITE TYPE.

as before. De¬ne maps

i : E ’ V, t:E ’V

to be

i(a0 a1 · · · aM ) = a0 a1 · · · aM ’1 t(a0 a1 · · · aM ) = a1 · · · aM .

Then a sequence u = · · · u1 u0 u1 u2 · · · ∈ E Z , where ui ∈ E lies in X M +1 if and

only if

t(uj ) = i(uj + 1) (8.2)

for all j.

So let us de¬ne a directed multigraph (DMG for short) G to consist of a

pair of sets (V, E) (called the set of vertices and the set of edges) together with

a pair of maps

i : E ’ V, t : E ’ V.

We may think the edges as joining one vertex to another, the edge e going from

i(e) (the initial vertex) to t(e) the terminal vertex. The edges are “oriented” in

the sense each has an initial and a terminal point. We use the phrase multigraph

since nothing prevents several edges from joining the same pair of vertices. Also

we allow for the possibility that i(e) = t(e), i.e. for “loops”.

Starting from any DMG G, we de¬ne YG ‚ E Z to consist of those sequences

for which (8.2) holds. This is clearly a step one shift.

We have proved that any shift of ¬nite type is conjugate to YG for some

DMG G.

8.2.3 The adjacency matrix

suppose we are given V. Up to renaming the edges which merely changes the

description of the alphabet, E, we know G once we know how many edges go

from i to j for every pair of elements i, j ∈ V. This is a non-negative integer,

and the matrix

A = A(G) = (aij )

is called the adjacency matrix of G. All possible information about G, and

hence about YG is encoded in the matrix A. Our immediate job will be to

extract some examples of very useful properties of YG from algebraic or analytic

properties of A. In any event, we have reduced the study of ¬nite shifts to the

study of square matrices with non-negative integer entries.

8.2.4 The number of ¬xed points.

For any dynamical system, (M, F ) let pn (F ) denote the number (possibly in¬-

nite) of ¬xed points of F n . These are also called periodic points of period n.

We shall show that if A is the adjacency matrix of the DMG G, and (YG , σY )

is the associated shift, then

pn (σY ) = tr An . (8.3)

142 CHAPTER 8. SYMBOLIC DYNAMICS.

To see this, observe that for any vertices i and j, aij denotes the number of

edges joining i to j. Squaring the matrix A, the ij component of A2 is

aik akj

k

which is precisely the number of words (or paths) of length two which start at

i and end at j. By induction, the number of paths of length n which join i to

j is the ij component of An . Hence the ii component of An is the number of

paths of length n which start and end at i. Summing over all vertices, we see

that tr An is the number of all cycles of length n. But if c is a cycle of length n,

then the in¬nite sequence y = · · · ccccc · · · is periodic with period n under the

shift. Conversely, if y is periodic of period n, then c = [y0 , yn’1 ] is a cycle of

length n with y = · · · ccccc · · · . Thus pn (σY ) = the number of cycles of length

n = tr An . QED

8.2.5 The zeta function.

Let (M, F ) be a dynamical system for which pn (F ) < ∞ for all n. A convenient

bookkeeping device for storing all the numbers pn (F ) is the zeta function

tn

ζF (t) := exp pn (F ) .

n

n

Let x be a periodic point (of some period) and let m = m(x) be the minimum

period of x. Let γ = γ(x) = {x, F x, . . . , F m’1 x} be the orbit of x under F

and all its powers. So m = m(γ) = m(x) is the number of elements of γ. The

number of elements of period n which correspond to elements of γ is m if m|n

and zero otherwise. If we denote this number by pn (F, γ) then

«

tn tmj

exp pn (F, γ) = exp mj =

n mj

n j

«

m

t j 1

= exp (’ log(1 ’ tm )) =

exp .

1 ’ tm

j

j

Now

pn (F ) = pn (F, γ)

γ

since a point of period n must belong to some periodic orbit. Since the expo-

nential of a sum is the product of the exponentials we conclude that

1

ζF (t) = .

1 ’ tm(γ)

γ