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(u2-4u),2u), .5+f(r(u2-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(u2-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(u2-4u),2u)) ) and IR = bbc[(l(.5+f(r(u2-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| >= ... >= cn+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| <= Ckd. 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 Ì Rn with a hyperbolic fixed point z having a transverse homoclinic point p. That is, p [[propersubset]] Ws(z) [[intersection]] Wu(z), and the manifolds Ws(z) and Wu(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 Es and the unstable set Eu, for which
v [[propersubset]] Es implies ||DF[[ring]]k(x) v|| <= C [[nu]]k||v||, and
(5.5)
v [[propersubset]] Eu 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.
