version of 3 June 1992

There is a remarkable way to understand the qualitative features of the mapping
Fu(x) = ux(1-x) for large u by using the dynamics to encode itself. Suppose
that u > 2+r(5), so that |Fu'| > 1 on the invariant set [[Lambda]], and
imagine that we watch the iterates xn = Fu[[ring]]^{n}(x0) of some
point x0, but make only the crudest of measurements, *viz.*, we write down
L or R according as xn lies to the left or the right of the principle gap Ao =
b(l(.5-f(r(u^{2}-4u),2u), .5+f(r(u^{2}-4u),2u))). The result
is an infinite string of letters known as the **itinerary** of x0. For
example, the itinerary of 1 is Rxto(L) and the itinerary of .5 -
f(r(u^{2}-4u),2u) is LRxto(L). (The bar indicates that L repeats
indefinitely.) We denote the itinerary of a point x by S(x), and call this
function S:[[Lambda]] -> [[Sigma]]2 the **itinerary map**, where
[[Sigma]]2 denotes the set of all infinite sequences of two symbols (R's and
L's).

It is clear that the itinerary is defined for any point x0 of [[Lambda]]. Not quite as clear is that every conceivable itinerary is the actual itinerary of a point of [[Lambda]], so that [[Lambda]] and [[Sigma]]2 are in one-to-one correspondence. This can be seen as follows. Let

IL = bbc[(l(0, .5-f(r(u^{2}-4u),2u)) ) and IR =
bbc[(l(.5+f(r(u^{2}-4u),2u), 1)),

and consider the points of [[Lambda]] corresponding to the first n terms in a putative itinerary s0s1.... These are the points of the set

Jn := ISdo5(s0)[[intersection]] Fu[[ring]]^{-1}(
ISdo5(s1))[[intersection]]...Fu[[ring]]^{-n}( ISdo5(sn)),

where Fu[[ring]]^{-k}(...)^{ }denotes the inverse image under
Fu[[ring]]^{k}. Each Jn is a nonempty closed set, and
Jn [[propersuperset]] Jn+1, so there is at least one point in J :=
a( ,[[intersection]],^{n<[[infinity]]})Jn.

To see that there is exactly one point in J we must show that any two points of [[Lambda]] have different itineraries. When we argued that [[Lambda]] was a CANTOR set in [[section]]III, we saw that as long as the iterates xn and yn of two distinct points x0 and y0 lie on the same side of the central gap for all n, the interval [xn,yn] is stretched by at least a factor c>1 during each iteration of Fu. It follows that

|xn+1 - yn+1| >= c |xn - yn| >= ... >= c^{n+1} |x0 - y0| .
(5.1)

Since the distance between any two points of [[Lambda]] can never be larger than one, there would be a contradiction for n sufficiently large.

We can define a natural distance function on [[Sigma]]2, with which the
functions S and S^{-1} will turn out to be continuous, i.e., S is a
homeomorphism between [[Lambda]] and [[Sigma]]2. The distance between two
elements s = s0s1s2... and t = t0t1t2...of [[Sigma]]2 is
defined by

dist(s,t) = isu(k:sk != tk,, 2^{-k}) . (5.2)

**Warning**. It is tempting to think of L and R as binary digits 0 and 1
and put a period in front of the sequences s and t to interpret them as binary
numbers between 0 and 1. Notice, however, that with the metric (= distance
function) (5.2), the distance between Rxto(L) and Lxto(R)is 2, which is the
maximum possible, whereas in binary .1xto(0) and .0xto(1)are the same number.

The metric on [[Lambda]] is the usual distance |x-y|; it is equipped with the relative topology as a subset of R.

**Exercise** V.1. Verify that [[Sigma]]2 is a **metric space** with this
metric, i.e., show that

a) dist(s,t) >= 0 for all s,t;

b) dist(s,t) = 0 if and only if s = t;

c) dist(s,t) = dist(t,s) for all s,t; and

d) dist(s,t) <= dist(s,u) + dist(u,t) for all s,t,u. (The **triangle
inequality**.)

The metric dist(s,t) gives us a natural sense of convergence for [[Sigma]]2, which is complete, i.e., all CAUCHY sequences of elements of [[Sigma]]2 converge.

**Exercise** V.2. Show that a sequence s^{(j)} of elements of
[[Sigma]]2 converges to a limit s [[propersubset]] [[Sigma]]2 if and only if
for each N there exists J such that whenever j >= J, then

s^{(j)}k = sk for all k = 0, 1, ..., N.

**Theorem**. *The itinerary map is a homeomorphism between*
[[Lambda]] *and* [[Sigma]]2.

**Proof**. We have already seen that S is bijective, so it remains to show
that S and S^{-1} are continuous. The key to the proof is to observe
there are finite constants c and C such that 1 <= c <= |Fu'(x)| <= C
for all x[[propersubset]] [[Lambda]]. Suppose that x0,y0 [[propersubset]]
[[Lambda]] with |x0-y0| <= d, and denote the iterates (xk,yk). Recall that
|xk-yk| <= C^{k}d. Since the width of the central gap is
w = 2f(r(u2-4u),2u), it requires at least ln(w/d)/lnC iterates before
the itineraries of x0 and y0 can differ. In other words,

dist(S(x0),S(y0)) <= 2sup10(1 - f(ln(w/d),ln C)).

As d -> 0, the distance goes to 0, so S is continuous. The proof that
S^{-1 }is continuous is similar, using the constant c as in (5.1).

x( )

The advantage of the homeomorphism is that we have the option of understanding
the dynamical system Fu, [[Lambda]] by studying instead the action s ->
S(Fu(S^{-1})) on [[Sigma]]2. But this action, denoted [[sigma]], is
extremely simple:

[[sigma]](s0s1s2...) = s1s2s3.... (5.3)

The itinerary of Fu(x) is the same as that of x except that it begins one
time-step later. The dynamical system [[sigma]],[[Sigma]]2 is known as the
**BERNOULLI shift**. With the itinerary map, any statement we can make
about the shift can be translated into a statement about Fu on [[Lambda]]. For
example, the N cycles of the BERNOULLI shift correspond to the possible
repeating sequences of N symbols R and L. We can easily count them as in
Section III, making sure not to include the fixed points or the M-cycles for
the divisors M of N.

**Corollary**. The nonwandering set [[Lambda]] for the quadratic mapping Fu
is a CANTOR set.

**Proof**. In [[section]]III we saw that [[Lambda]] is closed and nowhere
dense. The fact that no points are isolated follows from the homeomorphism
between [[Lambda]] and [[Sigma]]2 since no point of [[Sigma]]2 is isolated.

x( )

**Exercise** V.3. Show that [[Lambda]] is topologically transitive. Do
this by writing down an infinite sequence of symbols R and L which contains
every possible finite sequence, and apply S^{-1}.

This way of understanding the dynamical system Fu, [[Lambda]], known as
**symbolic dynamics**, also applies to many other models. The relationship
between Fu, [[Lambda]] and [[sigma]],[[Sigma]]2,

S(Fu(x)) = [[sigma]](S(x)),

or, using the composition sign,

S[[ring]]Fu = [[sigma]][[ring]]S,

is known as **topological conjugacy**, or **isomorphism**. Observe that
a simple example of a topological conjugacy

S[[ring]][[phi]]t = [[psi]]t[[ring]]S, (5.4)

of flows [[phi]]t and [[psi]]t is furnished by a flow itself, since (5.4) is valid for [[phi]]t = [[psi]]t and S = [[phi]]T.

In the general situation there may be any number of symbols, and they may be indexed with negative as well as positive integers:

... s-3s-2s-1s0s1s2s3....

This will occur when the shift is topologically conjugate to an invertible
mapping. Furthermore, there may be restrictions on which sequences occur. For
example, there may be four symbols, N,E,S,W, but it may never happen that S
never follows N. A shift of a sequence where S never follows N will still be a
sequence with this restriction, and so it still defines a self-contained
symbolic dynamics. There may also be equivalences. For instance, the
sequences of symbols 0 and 1 can be identified with the binary numbers between
0 and 1 with the proviso that .s0...sn1xto(0) is regarded as the same number
as .s0...sn0xto(1). A shift on the space of sequences of a finite number of
symbols with possible restrictions allowing the dynamics to be self-contained,
is known as a **subshift of finite type**.

**Exercise** V.4. Investigate the symbolic dynamics for the dyadic map,
F(x) = 2x mod 1, S = [0,1). (Use binary numbers.) Do the same for
the tent map.

**Exercise** V.5. Consider the dynamics given by the mapping

F(x) = blc{(a(l(3x, -[[infinity]] < x <= 1/2), ,l(3-3x, 1/2 <= x < [[infinity]]))).

Find the maximal nonwandering set [[Lambda]] for this transformation, and discuss the symbolic dynamics

SMALE was able to show that a large class of dynamical systems, which, loosely, involve stretching, squeezing, and bending, contain a subset with a symbolic dynamics. The SMALE-BIRKHOFF homoclinic theorem states:

**Theorem**. *Let * F *be a diffeomorphism on * S Ì
R^{n} *with a hyperbolic fixed point *z *having a transverse
homoclinic point *p*. That is, *p [[propersubset]] W^{s}(z)
[[intersection]] W^{u}(z), *and* *the manifolds
*W^{s}(z) *and * W^{u}(z) *intersect at a nonzero
angle at *p*. Then *F *has a hyperbolic invariant set*
[[Lambda]],* and *F,[[Lambda]] *is topologically conjugate to a
subshift of finite type.*

** **

In the context of an iterated mapping, a fixed point z is said to be
hyperbolic if the linearization of F at z, i.e., the matrix DF(z), has no
eigenvalues [[nu]] with |[[nu]]| = 1. A set is hyperbolic if at each point x
the tangent space decomposes into two subspaces, the stable set E^{s}
and the unstable set E^{u}, for which

v [[propersubset]] E^{s} implies ||DF[[ring]]^{k}(x) v|| <=
C [[nu]]^{k}||v||, and

(5.5)

v [[propersubset]] E^{u} implies
||D(F^{-1})[[ring]]^{k}(x) v|| <= C
[[nu]]^{k}||v||,

with C > 0 and 0 < [[nu]] < 1. Section VI of these notes will introduce the LYAPUNOV exponents with a condition that is similar to (5.5) ([[lambda]]v will be analogous to ln [[nu]]) but slightly more general. For future reference, if a system has a full set of LYAPUNOV exponents, then it is hyperbolic if none of the [[lambda]]v are 0.

Instead of proving this theorem, let us look at examples. The proof of the
theorem involves showing that there must exist a structure analogous to the
**horseshoe map**. The horseshoe map is a map on a planar region S which
has a special action on a stadium-shaped subregion, consisting of a rectangle
ABCD and two semicircular caps. The stadium is first squeezed in the direction
transverse to the caps. Then the squeezed rectangle is stretched in the
direction of the line between the goals, but the caps are shrunk in this
direction. We now have the outline of a pencil with erasers at both ends.
This figure is then bent into a horseshoe and placed within the original
stadium as shown below.

** Figure V.1**

The horseshoe intersects the stadium in two columns, CL and CR. Let us seek an
invariant set within these columns in the spirit of the invariant set of the
quadratic mapping within the two basic intervals, by constructing the
intersection of CL and CR with all of their inverse images. The inverse image
of CL consists of a horizontal band cutting across CL and CR, and likewise for
the inverse image of CR. The intersection is thus a pair of horizontal bands
in each column. The inverse image of this set is a pair of horizontal bands
within each previous horizontal band. If we continue taking inverse images, we
are left with a vertical CANTOR set within each column with the same general
structure as the classical middle-thirds CANTOR set. This construction is thus
analogous to the situation for the quadratic mapping, including such features,
for instance, as the fact that the orientation of the points mapped to the
right column is reversed from those mapped to the left column. One difference,
however, is that the horseshoe map is uniquely invertible on its range (and can
be arranged to be invertible on S). If we want to construct a set invariant
under both forward and reverse iteration, we need to look at inverse images of
the columns under F^{-1}, i.e., forward images under F. Now, the
forward image of any vertical line in one of the columns is a pair of columns,
one in CL and one in CR. If we argue as before, we construct a pair of
horizontal CANTOR sets within CL and CR. The invariant set [[Lambda]] for both
directions is therefore a product of CANTOR sets: both the x-
coördinate
and the y-
coördinate
of a point in [[Lambda]] must belong to the appropriate CANTOR set. The
symbolic dynamics for this dynamical system is bilateral: s0 = R or L
according to which column z = (x,y) [[propersubset]] [[Lambda]] belongs to.
Under forward iteration we observe which column F[[ring]]^{k}(z) lands
in and write down sk = L or R accordingly. In addition, under reverse
iteration we write down L or R according as F^{-k}(z) =
(F^{-1})[[ring]]^{k} belongs to the lower (L) or upper (R)
horizontal band. The action of F is topologically conjugate to the leftward
shift on the bilateral sequences of L's and R's. Further details about this
construction can be found in the references [e.g., DEVANEY, 1986;
GUCKENHEIMER-HOLMES, 1983; Wiggins, 1990].

**Figure V.2**

**Exercise** V.6. Analyze the symbolic dynamics for the baker's
transformation.

Not every interesting example of symbolic dynamics is of finite type. Any
number x0 between 0 and 1 can be represented as a **continued fraction**
with positive integer coefficients:

__ 1 __

x0 = a1 +
__ 1 &nbs; __
(5.6)

a2 +
__ 1 __p>
a3 +
__ 1 __

a4 + .....

unless x0 = 0, in which case we may agree to define all ak = [[infinity]] by
convention, and consider [[infinity]] an integer. This represents an
association between x and a sequence {ak} of an infinite number of possible
symbols, *viz.*, the positive integers and [[infinity]]. To see that the
continued-fraction representation is unique, observe that if 0 < x0 < 1,
we can always write

f(1,x0) = a1 + frac b(f(1,x0)),

where a1 = int b(f(1,x0)) >= 1. Letting x1 = frac b(f(1,x0)), we can repeat this procedure unless x1 = 0, and define a2 = int b(f(1,x1)), a3 = int b(f(1,x2)), etc. If b(f(1,xk)) is an integer we set ak+1 = ak+2 = ... = [[infinity]]. In this case x0 is a rational number, and we say that the continued fraction terminates, since the usual practice is not to write the [[infinity]]'s. The construction amounts to iterating the mapping on [0,1) given by F(0) = 0, and otherwise

F(x) = frac(1/x) = 1/x mod 1 (in the interval [0,1)), (5.7)

and the sequence of integers specifying the continued fraction is obtained by following the itinerary of x0 under this mapping, where by itinerary we mean that we look to see which interval of the form (1/(k+1), 1/k] contains xn, and down sn = k. (This mapping is the same as in Exercise IV.11.) The symbol space consists of all positive numbers and [[infinity]], and any sequence can occur, with the restriction that the only number that can follow [[infinity]] is [[infinity]].

**Exercise** V.7. Analyze the symbolic dynamics for the mapping (5.7).
Discuss periodic points and points with dense trajectories.

A theorem of LEGENDRE states that the eventually periodic points are the algebraic numbers of degree two, i.e., roots of quadratic expressions with integer coefficients.

It is possible to form a symbolic dynamics for toral automorphisms like the cat map, but the procedure is more involved, and generally results in a subshift of finite type rather than a simple system like ([[sigma]],[[Sigma]]2). For definiteness let us stay with the cap map (4.2). We know that the unstable and stable manifolds are straight lines leaving the origin with slopes f(1,2)b(1+/- r(5)), but that these lines get folded into an infinite number of parallel line segments because the cat map lives on the torus. Because the cat map is continuous, we see that the image of any rectangle the sides of which lie on pieces of the stable and unstable manifolds is again a rectangle with sides on those manifolds. The new rectangle will be stretched in the unstable direction and squeezed in the stable direction, and it may wrap around the torus.

With a little thought, we find that the torus itself can be written as the
union of only three rectangles, as in the figure, where they are labeled Boxes
1, 2, and 3. This decomposition, known as a **MARKOV partition**, is not
unique, and moreover it is not clear how to apportion the unstable and stable
manifolds among the boxes, but that is a set of measure zero that we will
ignore in this discussion. Some more details on this point are to be found in
[DEVANEY, 1989, [[section]]2.4], where a similar example is analyzed. These
boxes can play the rôle of IR and IL for the quadratic mapping, and we
can write down an itinerary map in terms of the three symbols 1,2,3. Since the
cat map is invertible, we also follow the backwards itinerary of a point, and
associate with it a doubly infinite sequence of symbols 1,2,3, on which the
dynamics is equivalent to a shift. One complication, however, is that Box 1
may be followed by Box 1 or Box 3 but not Box 2, and Box 2 may be followed by
Box 1 or Box 2 but not by Box 3. These restrictions on [[Sigma]]3 define a
subset which is invariant under the shift [[sigma]], so the dynamics is
equivalent to a subshift.

**Exercise** V.8. Show that the itinerary map is actually a topological
conjugacy.