version of 28 May 1992

In this section we consider discrete-time dynamical systems for which the state space S is the real line R or another one-dimensional set such as the interval [0,1] or the circle S¹. The dynamics is specified by some known function [[phi]]1 =: F: S -> S.

As with continuous systems, there is a convenient graphical way of analyzing these problems. The trajectory associated with an initial point xo would be a sequence of points xn = F[[ring]]ⁿ(xo) := [[phi]]n(xo), and could be plotted as a jumble of points on the line. Matters could be made a bit more understandable if the points were connected by little arrows, as if the points were fleas hopping in a cartoon. The alternative web diagram usually conveys more than flea-hop diagrams. Web diagrams are constructed as follows:

Let us first plot y = F(x) in the usual way, and superpose the line y=x, called the first bisectrix. Beginning with xo, mark the point on the line (xo,xo). Then read off the value x1 by moving vertically from this point to the graph of F(x). Now move horizontally from (xo,x1) until we meet the line again. Mark that point, which is (x1,x1).

If we follow this procedure over and over, we plot out the whole trajectory originating with xo as a sequence of points on the line y=x, together with line segments joining the line to the graph of the function. If we were to drop these points onto the x-axis we would of course have the same values xn we would plot by any method, but the graphical method has two advantages:

a) We do not have to make calculations if we are not interested in accuracy.

b) We get some intuition about how properties of F(x) show up in the dynamics it produces.

FIGURE III.1

Equilibria, or fixed points, are the points where the graph of F(x) crosses the line x=y. We see in almost any example that some fixed points are attracting and others are repelling; for instance, in Figure III.1, 0 is a repelling fixed point and the fixed point at positive x is attracting. It is less clear from the graph what goes on at the negative fixed point, but most likely it is repelling. We will call a fixed point xo hyperbolic if F has a continuous derivative near xo and F'(xo) != 1. The critical value is 1 rather than 0 as in [[section]] II, since F here is the flow itself rather than the vector field. This F is analogous to [[phi]]1 ~ exp(tA) from [[section]] II. Since exp(0) = 1, the value 1 in this situation corresponds to an eigenvalue 0 of A as in [[section]] II.

Exercise III.1. Graphically determine the trajectories beginning at several representative points for the following mappings:

a) The dyadic map, S = [0,1):

F(x) = blc{(a(l( 2x, 0 <= x < 1/2), , ,l(2x-1, 1/2 <= x < 1)))

b) The tent map, S = [0,1]:

F(x) = blc{(a(l( 2x, 0 <= x <= 1/2), , ,l(2-2x, 1/2 <= x <= 1)))

The dyadic map can also be regarded as a mapping of the circle: Suppose a circle has a circumference of 1 and some point of the circle is designated as the origin. Then the dyadic map is the map that doubles the coördinate (=angle from 0, divided by 2[[pi]]). When the doubled coördinate is greater than 1, the new point has gone all the way around the circle, and is at a distance 2x-1 from 0. From this point of view, the dyadic map is continuous, because 1 is the same point as 0.

Exercise III.2. Analyze the dynamics of the circular shift, which simply rotates every point on the circle by a fixed angle [[alpha]]. Compare the case where [[alpha]] is a rational multiple of 2[[pi]] with the case where it is an irrational multiple of 2[[pi]]. Show that if [[alpha]]/2[[pi]] is irrational, the iterates of any point come arbitrarily close to every point of the circle. (This was first observed by JACOBI in 1835; see [ARNOLD-AVEZ, 1968, Appendix 1].)

For circle maps there is a choice of length scale. The circle can be regarded as the interval [0,1], with 1 [[congruent]] 0, or as the interval [0,2[[pi]]] with 2[[pi]] [[congruent]] 0, the interval [-[[pi]],[[pi]]] with [[pi]] [[congruent]] -[[pi]], etc. (Here the symbol [[congruent]] denotes equivalence, not approximate equality.) No convention is universal.

Proposition. If xo is a hyperbolic fixed point and |F'(xo)| < 1, then xo is attractive, in the sense that for some interval I containing xo, x[[propersubset]]I => a( ,lim,^{n->[[infinity]]}) F[[ring]]ⁿ(x) = xo.

Proof. Since F' is assumed continuous near xo, there is an interval I on which |F'(x)| <= c < 1 for some c independent of x. Now estimate:

|F(x) - F(xo)| = bbc|(i(x,xo, F'(s) ds)) <= c |x-xo| . (3.1)

A mapping with this property has a unique attractive fixed point, by the well-known contraction-mapping theorem [e.g., KOLMOGOROV and FOMIN, 1970, p. 66]. The proof in this case is as follows: By iterating the estimate (3.1) we find that

|F[[ring]]ⁿ(x) - F[[ring]]ⁿ(xo)| <= cⁿ |x-xo| -> 0 as n -> [[infinity]]. x( )

Conversely, if a hyperbolic fixed point has the property that |F'(xo)| > 1, then for some open interval U containing xo, every point x [[propersubset]] U other than xo has the property that F[[ring]]^m(x) lies outside U for some m. (The number m will depend on x.) Such an equilibrium is said to be unstable, repulsive, or repelling.

We shall have occasion below to compose functions and try to relate the graph of a composition of f and g to the graphs of f and g separately. For a qualitative picture of the graph it helps to begin by thinking where fdeg.g increases and where it decreases; assuming that f and g are smooth, these intervals are separated by the points where the derivative is 0. According to the chain rule, , so we see the derivative is zero whenever either g'(x) = 0 or f'(g(x)) = 0. It thus helps to enumerate the critical points of f and g.

Exercise III.3.

a) Sketch the graphs of the various compositions of the following functions

x², x³- x, sin(x)

b) What symmetry properties of f and g will guarantee that fdeg.g is an even function function? An odd function?

Now let us look at the system analyzed by MAY and FEIGENBAUM, viz.,

Fu(x) = u x(1-x), (3.2)

which is called the quadratic map, or logistic map. (The term logistic describes the shape of the elongated S-shaped curve representing the solution of the continuous version of this growth law, i.e., (1.5). It is something of a misnomer for (3.2).) We shall let S = R, but shall be most interested in the values x in the range from 0 to 1, and assume that u>1. On occasion it will also be convenient to enlarge S to the set of complex numbers, or restrict it to a subset of the unit interval I = [0,1]. Some rough sketches of the action of this map and of its second iterate Fu[[ring]]² on I are shown in the figure:

In all cases shown above, u < 4, and Fu sends the interval [0,1] into itself, and sends other points to negative values, whereupon further iterations propel them towards -[[infinity]]. It is elementary to solve for the fixed points: x = 0 or (u-1)/u, and the corresponding derivatives are u and 2-u, which means that the fixed point 0 is repulsive, while the positive fixed point is attractive when 1 < u < 3, but repulsive when u > 3. As u passes through the value 3, the positive fixed point undergoes a bifurcation. Look now at the graphs of Fu[[ring]]², the second iterate of Fu. For u < 3 it has the same fixed points as Fu, but for u > 3 it has twice as many. When u=3, the graph of Fu[[ring]]² is tangential to the line y=x at x=1-1/u, but for u slightly larger, it cuts across the line in three places, the middle one of which is (u-1)/u. The reason it does this is that the slope of Fu[[ring]]² is greater than 1 at (u-1)/u, so the graph crosses the bisectrix there from below. Near zero the graph lies above the bisectrix, so by continuity it must cross the bisectrix somewhere to the left of (u-1)/u. It must also cross it to the right of (u- 1)/u for similar reasons; Fu(1) = 0 is below the bisectrix at x=1. (A good text on bifurcation theory is [HALE-KOÇAK, 1989] and the standard mathematical treatise on the subject is [CHOW-HALE, 1982]. See also [Ruelle, 1989]) The other two fixed points of Fu[[ring]]² are periodic points for Fu itself.

Definition. A periodic point xo for a mapping F: S -> S is a fixed point for some iterate F[[ring]]ⁿ. The smallest such n for which xo is fixed is known as the minimal period of xo. A periodic point of minimal period n, together with its n-1 distinct iterates, is called an n-cycle.

The minimal period is also referred to, for instance in DEVANEY's book, as the prime period. I shall avoid this confusing terminology, because I don't want people to worry about a point perhaps being able to have period 61 but not 63. There is no relationship between this term and prime numbers. In fact, I shall use the word period by itself if there seems to be no danger of confusion.

Exercise III.4.

Find the periodic points and their periods for the dyadic map, the tent map, and the circle rotation.

Observe that for u only slightly greater than 3, the 2-cycle is attractive, in the sense that the corresponding fixed points of F[[ring]]² are attractive. This should be evident from the graph of F[[ring]]² for u slightly larger than 3, since the curve passes from above to below the bisectrix at these points, meaning that the slope dF[[ring]]²/dx is less than, but almost equal to, 1. Observe that from the chain rule,

f(dF[[ring]]ⁿ(x),dx) = F'(x) F'(F(x)) F'(F[[ring]]²(x)) ... F'(F[[ring]]^n-1(x)),

if we denote xk = F[[ring]]^k(x1), then

f(dF[[ring]]ⁿ(x1),dx) = iPR(k=1,n-1, F'(xk)). (3.3)

Thus the stability of a hyperbolic n-cycle can be determined by taking the product of F'(xk) as xk runs through the n-cycle.

As u is steadily increased, a very curious phenomenon takes place: at some critical value the 2-cycle becomes unstable, and at precisely that critical value of u a stable 4-cycle is born. At a slightly larger value of u the 4-cycle becomes unstable, and a stable 8-cycle is born. This happens over and over, with stable 2ⁿ-cycles going unstable and giving birth to 2ⁿ⁺¹-cycles. Most curiously, the critical values of u come so fast and furious that all possible 2ⁿ-cycles are generated by the time u reaches a finite value u[[infinity]] [[congruent]] 3.5699. This period-doubling cascade turns out not to be special to the example Fu, but to apply to many dynamical systems, especially unimodal maps of the interval, i.e., iterations of uF(x), where F(x) is smooth, equals 0 at 0 and 1, and has a unique maximum at some value between 0 and 1. Indeed, for a large class of unimodal maps uF(x), if the bifurcation values of u are denoted ui, it is found that they conform to a universal scaling:

a(lim,k->[[infinity]]) a(f(uk - uk-1,uk+1 - uk), ) sup8( = d) (3.4)

Exercise III.5. Determine numerically or graphically at what values the period-doubling bifurcations occur, and verify the universal scaling.

Figure III.4 shows the result of a program which draws the bifurcation diagram in a standard way: For each value of u, the map Fu is iterated, with a randomly chosen initial point. A large number of iterates are computed without being plotted, and then another large number of iterates are plotted vertically above the value of u. If the initial value is not on an unstable n-cycle, and there is a stable k-cycle for that value of u, this procedure will be likely to find the stable k-cycle.

The analysis of the motion defined by the quadratic map becomes somewhat complicated for values of u larger than this critical value. It is easiest to begin with what happens for significantly larger u, in particular u > 4. Whenever u > 4, Fu maps some points in the interval I = [0,1] outside this interval, since Fu(1/2) = u/4 > 1. (More precisely, the interval

Ao = b(l(.5-f(r(u²-4u),2u), .5+f(r(u²-4u),2u)))

is mapped to (1,u/4).)

Once a point leaves I, it is easy to see that it becomes negative and moves off to -[[infinity]] during successive iterations. While not every point of I eventually leaves I, witness 0 or any of the infinitely many unstable periodic points, it is very likely that a randomly chosen point of I eventually leaves I and heads for -[[infinity]]. A point not in Ao might be in its preimage A1 := {x: Fu(x) [[propersubset]] Ao}, or in the preimage A2 of A1, etc., in which case it will eventually leave I. A1 consists of a pair of disjoint intervals containing, for example, the preimage of x=.5, i.e., {.5-r(u²-2u)/2u, .5+r(u²-2u)/2u}. A2 consists of four intervals interlacing those of A1, and so forth. We shall refer to these deleted intervals as the holes. If we try to construct the set [[Lambda]] of points that are never sent off to -[[infinity]] by successively deleting the holes An, i.e., [[Lambda]]= I - [[union]]An, , we are reminded very much of the classical middle-thirds CANTOR set, the most familiar fractal. Although the deleted intervals of this invariant set are not located exactly where they are in the classical CANTOR set, it is just like it in other respects.

Definition. A CANTOR set is a closed set C such that

a) C does not contain any open sets (in one dimension, this

means that it does not include any open intervals); and

b) the distance between any point x [[propersubset]] C and C-x is 0, i.e., no

points are isolated.

The mathematical jargon for a) is: C is nowhere dense, and for b): C is perfect. It is not hard to verify that [[Lambda]] is a CANTOR set when u > 2 + 5^1/2. It is a CANTOR set assuming only that u>4, but the proof is somewhat more difficult. What is special about u > 2 + 5^1/2 is that |Fu'(x)| > 1 for all x[[propersubset]][[Lambda]].

Definition. The classical middle-thirds CANTOR set is the subset of the unit interval defined as what remains when one deletes the open interval (1/3,2/3), then the open intervals (1/9,2/9) and (7/9,8/9), and so on an infinite number of times, at each stage removing an open interval in the middle third of each of the closed intervals remaining from the previous stage.

In ternary (base-three) arithmetic, the classical CANTOR set consists of all numbers between 0 and 1 inclusive that can be represented using the digits 0 and 2, but not 1. For example, in the ternary system 1/3 can be represented as .1 or as .0xto(2) (the bar indicates that what is under it repeats indefinitely), 2/3 can be represented as .2 or as .1xto(2), 1/2 uniquely as .xto(1), etc. The numbers 1/3 and 2/3 belong to C, but 1/2 does not.

Exercise III.6.

Show that the LEBESGUE measure of the classical CANTOR set is 0 by showing that the lengths of the deleted intervals sum to 1. Is the LEBESGUE measure of the CANTOR set where one deletes (1/5,2/5) and (3/5,4/5) then (1/25,2/25), (3/25,4/25), (11/25,12/25), (13/25,15/25), (21/25,22/25) and (23/25,24/25), etc., always deleting 2 symmetrical fifth-intervals, likewise 0? Show how to construct fat CANTOR sets in the unit interval that have any given positive measure less than 1.

Although the classical CANTOR set strikes one as small in the sense of LEBESGUE measure, it is not small when considered as a set. Suppose that we were to represent C in the ternary system, but put on astigmatic glasses that make 2's look like 1's while leaving 0's recognizable. We might easily think we were looking at the set of all numbers of the unit interval, represented in the binary system. In other words, there is a one-to-one correspondence between C and the unit interval, which is an uncountable set. There are just as many points as if we hadn't deleted any.

To prove that [[Lambda]] for the map Fu is a CANTOR set, first note that [[Lambda]] is closed, since its complement [[union]]An is open (unions of open sets are open).

To prove a), observe that Fu"(x) = -2u < 0, so Fu' is a decreasing function. If u > 2 + 5^1/2, then at the left end point of Ao, .5-r(u²-4u)/2u, we find that Fu'(x) = u-2ux = r(u²-4u) > 1. Since Fu is symmetric about x=.5, this means that |Fu'(x)| >= c > 1 on all of [[Lambda]]. Now suppose that [[Lambda]] contained an interval (x0, y0). Since [[Lambda]] is closed, it would contain the closed interval [x0, y0], and from the definition of [[Lambda]] and the continuity of Fu, it also contains the intervals [xk, yk] for all k. Consider iterating Fu n times, where n is so large that cⁿ |x0-y0| > 1. By the chain rule, |dF[[ring]]ⁿ/dx| >= cⁿ on [[Lambda]], so the mean- value theorem would imply that |xn - yn| = |F[[ring]]ⁿ(x0)-F[[ring]]ⁿ(y0)| >= cⁿ|x0 - y0| > 1, which contradicts the fact that [[Lambda]] is mapped into itself.

We will verify b) when discussing symbolic dynamics in [[section]]V.

x( )

Exercise III.7.Find the invariant set [[Lambda]] for the stretched tent map,

One curious property of CANTOR sets is that they have nonintegral dimension. It was a realization of HAUSDORFF that the dimension of a regular geometric figure could be determined by a scaling relation in the way the set can be covered up with small sets. A simplified version of his notion of dimension is known as the box-counting dimension (also fractal dimension, limit capacity, and various other terms). Suppose that a set S is a subset of Rⁿ and we cover it as efficiently as possible by boxes of side [[epsilon]]. We could equally well use spheres or any other regular figures. If S is regular and n-dimensional, it will take us roughly (volume of S)/[[epsilon]]ⁿ such boxes. If S is regular and one-dimensional, i.e., a smooth curve, it will take us roughly (length of S)/[[epsilon]] boxes, and for intermediate dimensionality k we will require roughly constant/[[epsilon]]^k boxes for some integer k. The constant will be the k-dimensional volume of S, and the dimensionality can be read off from the covering procedure by taking the logarithm of the number of boxes and letting [[epsilon]]->0. Coverings for irregular figures may have the same sort of scaling law, but with nonintegral k.

Definition. Let S be a compact subset of Rⁿ, and define N([[epsilon]]) to be the infimum over all possible configurations of the number of boxes of side [[epsilon]] required to cover S. Then

dimK(S) = a(___,lim,[[epsilon]]->0) f(ln(N([[epsilon]])),|ln([[epsilon]])|).

A fractal is a set with a nonintegral dimension.

I believe that K stands for KOLMOGOROV (Kolmogocentsrov). The notation a(___,lim,[[epsilon]]->0) is the same as a( ,lim sup,[[epsilon]]->0), i.e., the largest of all limiting values of a function.

Since the classical CANTOR set can be covered with 2ⁿ intervals (= 1-dimensional boxes) of length [[epsilon]]=3^{- n}, N([[epsilon]]) = 2^{|ln[[epsilon]]|/ln3} for these values of [[epsilon]], and hence dimK(C) = ln2/ln3. For entertaining and useful discussion of fractals, we refer to [BARNSLEY, 1988], [FALCONER, 1965], and [MANDELBROT, 1983]. Iterative procedures are very likely to generate fractal geometrical structure, and in this sense the quadratic mapping is a typical dynamical system. The Georgia Tech School of Mathematics offers a separate course on fractal geometry in which this idea is explored in more depth than is possible in these notes.

Exercise III.8. Find the box-counting dimensions of the middle-fifths CANTOR set and the fat CANTOR sets of Exercise III.6.

The box-counting dimension is a great thing for calculations, but it suffers from some mathematical disadvantages, as realized already by HAUSDORFF. For this reason the HAUSDORFF dimension dimH(S) is defined in terms of coverings of variable size, but having a maximal diameter of [[epsilon]]. We will not go into details about fractal geometry in these notes, since the Georgia Tech School of Mathematics offers a separate course in fractal geometry. Exercise III.9, however, shows that some sets that by rights should have dimension zero are overestimated by dimK. The general fact is that dimH(S) <= dimK(S).

Exercise III.9. Let S be the subset of [0,1] consisting of the points 0 and 1/n, n = 1, 2, 3.... Show that dimK(S) > 0.

Exercise III.10. Read the books by BARNSLEY, FALCONER, and MANDELBROT and speculate about their personalities.

Let us return now to the quadratic mapping. We can consider the action of Fu on [[Lambda]] as an interesting dynamical system in its own right, regarding [[Lambda]] as one state space and the rest of the real numbers as a second, independent state space. As a by-product of the proof given above we see that the dynamical system on [[Lambda]] exhibits sensitive dependence on initial conditions, in the sense that initially nearby points become widely separated.

The dynamical system on [[Lambda]] for u sufficiently large is generally considered chaotic, a term that is so fashionable that there are many different ideas about what it means. Both fractal structures and sensitive dependence of initial conditions are certainly among the signs of chaos, but neither one by itself convincingly describes all that we intuitively understand by chaos. For example, iterations of the function sinh(x) on R⁺ exhibit exponential divergence of trajectories and hence sensitive dependence on initial conditions, but of a rather regular sort. It is also possible to cook up dynamical systems with fractal structures, but which do not exhibit sensitive dependence [GREBOGI et al., 1984]. Various notions of chaotic dynamics will appear recurrently in these notes.

Let us return to the quadratic mapping briefly, and crank the parameter u back down to 4, so that no points of the interval are mapped outside it. In this case as x increases from 0 to 1, F4(x) increases from 0 to 1 and then falls back to zero. It is fairly easy to see that the graph of F4[[ring]]^k will consist of 2^{k- 1} identical humps, in each of which the function rises continuously from 0 to 1 and falls back. The graph thus cuts across the first bisectrix 2^k times, so F4[[ring]]^k has 2^k fixed points. Two of these are obviously the fixed points of F4 itself. How many of the rest belong to k-cycles depends on the factorization of k into prime factors. For example, there are 2³ = 8 fixed points of F4[[ring]]³, 2 of which are fixed points of F4. The other 6 correspond to 2 3-cycles, since 3 is prime. On the other hand, consider the 2⁴ = 16 fixed points of F4[[ring]]⁴. 2 of these are the fixed points of F4 as before, and 2² -2 = 2 of them are a 2-cycle (the -2 is because we have already counted the 2 fixed points of F4). This leaves 16-4 = 12 corresponding to 3 4-cycles.

This argument makes it easy to count the k-cycles, and to see that F4 has cycles of all periods. It is more tedious to find them.

Exercise III.11. Count the 6-cycles for the quadratic mapping F4.  

Answer: (2⁶ -2³ -2² + 2)/6 = 9. Explain this calculation.

Also count the k-cycles for Fu with u>4, various k.

Exercise III.12. Count and find the 4-cycles for the tent map.

There is a very interesting theorem due to A.N. SHARKOVSKII [Ùarkocentsvskii[[sterling]],  1964] concerning the k-cycles of one-dimensional mappings. The SHARKOVSKII ordering of the positive integers is defined as follows: Begin with 3, then count through the odd numbers 2k+1, k = 1, 2, ..., i.e., 3,5,7,9,.... After these come all numbers of the form 2(2k+1), k = 1, 2, ..., then 2²(2k+1), 2³(2k+1), etc. After running through all powers of 2 times (2k+1), the ordering continues in descending order through the powers of 2 alone. Thus we have:

3,5,7,...,6,10,14,...12,20,...,2⁵,2⁴,2³,2,1. (3.5)

While this ordering consists of many infinite subsequences, it includes all the integers, and it is perfectly well-defined to say that one integer is prior to or latter to another (in other words, whether it stands to the left or right of the other).

Theorem. Let F be a continuous mapping from R to R. If F has a k-cycle, then it has an l-cycle for every l latter to k in the SHARKOVSKII ordering. In particular, if there is a 3-cycle, there are cycles of all periods.

The important point in the proof of SHARKOVSKII's theorem is the observation that if an interval I is continuously mapped by a function F onto a larger interval containing I, then there must be a fixed point for F in I. This is a simple consequence of the intermediate value theorem of elementary calculus. Now suppose that there is a 3-cycle x1->x2->x3. These points can be ordered in various ways, but let us suppose x1<x2<x3. The other possibilities work similarly. Considering now how the intervals I1 = [x1,x2], and I2 = [x2,x3] are mapped, we see that F(I1)[[propersuperset]]I2 and F(I2)[[propersuperset]]I2[[union]]I1. From the observation about the intermediate value theorem it is easy to see that there must be cycles of period 1 (look at F(I2)) and 2 (look at F[[ring]]²(I1)). Now let n be any integer greater than 3. Let A1 := I2, A2 be any connected part of A1[[intersection]]F^-1(A1) - there has to be at least one interval in this set, but conceivably there are many. Similarly, for any larger k let Ak be any connected part of Ak-1[[intersection]]F^-1(Ak-1). This is a sequence of nested intervals, i.e., for each k, Ak[[propersuperset]]Ak+1, and from the construction, AkÌF[[ring]]^k(Ak) and F[[ring]]^k(Ak)[[propersuperset]]I2[[propersuperset]]Ak. This implies that Ak contains a point of period k for F, but for all we know the minimal period is 1 or some other number less than k. To establish that there is a point with any minimal period n, we modify the construction as follows: Let Bn-1 be any connected part of I1[[intersection]]F^-1(An-2) - for the n-1st inverse image we jump over to I1 rather than I2. Finally, let Bn be any connected part of I2[[intersection]]F^-1(Bn-1). Bn is an interval within I2 such that F[[ring]]ⁿ(Bn)[[propersuperset]]I2[[propersuperset]]Bn, and therefore there is a fixed point of Bn for F[[ring]]ⁿ, but because of the one detour to I1, the minimal period of this point cannot be less than n.

This shows that the existence of a point of period three implies the existence of points of all periods. To get the full SHARKOVSKII ordering, it is necessary to go through a more elaborate argument of this kind and account for more possible orderings. More details of the proof, following ideas of BLOCK et al., are reproduced in [DEVANEY, 1987].