Unimodal Maps and Kneading Theory

The prototypical example of a unimodal map is the quadratic map:
 
Figure 1 shows , and includes a few iterations of the point . In general, a unimodal map maps an interval I into intself, has a single critical point C in I, and is monotone increasing on the left of C and decreasing on the right. For the quadratic map, I = [0,1] and C=1/2. The key topological property of a unimodal map is that it stretches and folds the interval I into itself.

  
Figure 1: The quadratic map, with . The vertical and horizontal lines show five iterates of the point .

One of the motivating reasons for studying the quadratic map is to understand the diagram shown in Figure 2. A closer view of part of this plot is shown in Figure 3. In each of these plots, a large sequence of increasing values of are generated. For each value of , we set , and iterate the quadratic map 1000 times. We then plot the next 32 values in the iteration versus . These plots provide a rough picture of the asymptotic behavior of the quadratic map. For example, Figure 2 shows that for , there is a stable equilibrium. (Indeed, it is easy to prove that for , is an equilibrium, and it is stable for .) At , the equilibrium becomes unstable, and a stable period 2 orbit is born. As is increased, the period 2 orbit eventually becomes unstable, and a period 4 orbit is born. This sequence of period doubling bifurcations appears to continue as is increased, but there is not sufficient resolution in the figures to see what happens. We can see a stable period 6 orbit at , and a stable period 3 orbit at .

In principle, we could determine all the periodic orbits (and determine their stability) by solving the appropriate formula. For example, period 3 orbits satisfy x = f(f(f(x))). However, these equations quickly become intractable as the period increases. It has also been observed that very similar bifurcation diagrams can be found with other unimodal maps, suggesting that the qualitative structure of the bifurcation diagram is not unique to the quadratic map. It turns out that the phenonema illustrated in the bifurcation diagrams can be elucidated with symbolic dynamics and kneading theory.

  
Figure 2: Bifurcation diagram for the quadratic map, .

  
Figure 3: A closer look at the bifurcation diagram for the quadratic map, .

To set up the symbolic dynamics of this system, we must first define a partition. In general, a partition is the separation of phase space into disjoint regions. For the quadratic map with , I=[0,1]. We define , C=1/2, and . Given , we define by (1). We now define

The symbol sequence or itinerary of the point is the sequence . For example, if and (see Figure 1), then . The quadratic map acts on the sequence as a shift:

where operates on sequences by discarding the left-most symbol, and shifting the rest of the sequence to the left.

We present a brief discussion of kneading theory [6, 7]. (A nice introduction to the theory is given by Devaney [8].) First, we define an ordering on the itineraries which preserves the ordering on the interval. More precisely, if , then x < y, and if x < y, then . Note that for a unimodal map, f is increasing on and decreasing on . After one iteration, the order of points in is maintained, while the order of points in is reversed. That is, if and , and x < y, then f(x) > f(y).

Define the order of the symbols to be 0 < C < 1. Let's compare the symbol sequences and . Clearly, if , then x < y, and if then x > y. If , we compare and . However, we have to take into account that if , then the order of the points has been reversed by the first iteration of the mapping. Therefore, if and , then it must be that x > y (and x < y if ). Now suppose that the first two symbols agree, but, say, . If the first two symbols are 00, then there have been no reversals, so x < y. If the first two symbols are 01 or 10, then there has been one reversal, so x > y. Finally, if the first two symbols are 11, then there have been two reversals, so x < y.

In general, the order is determined by the order of the first pair of symbols that differ in the two sequences. In order to know the correct direction of the inequalities, we must keep track of how many times the order has been reversed. But this is just the number of 1s that appear in the segment of the sequences that agree, because a 1 means that the points are to the right of C, and their order will be reversed by the next iteration. If there are an even number of 1s, then we use the natural order of the first symbols that differ. If there are an odd number of ones, then the order of x and y is the reverse of the order of the first pair of different symbols.

These simple observations on the ordering of symbol sequences lead to some remarkable consequences. An illustration of the power of the kneading theory are the following theorems, which hold for a large class of unimodal maps. We define the kneading sequence K(f) of the unimodal map f to be the itinerary of x=f(C), i.e. K(f) = S(f(C)).

Theorem. Let be a symbol sequence. If K(f) is not periodic, and for all , then there is a point such that .

This means we can construct an arbitrary symbol sequence , and if this sequence precedes the kneading sequence of the map, then there is a point in the interval with symbol sequence . A generalization is the following.

Theorem. Suppose we are given two symbol sequences and , and there is a such that . If there is an such that for all , then there is such that .

These results prove especially useful when we consider periodic orbits. (See, for example, Chapter 1.19 of Devaney [8] for a more detailed introduction.) As we vary , the kneading sequence K(f) changes, and the above results shows that the kneading sequence ``determines'' which periodic orbits exist. It turns out that for the quadratic map, the kneading sequence increases (in the sense of the order defined above) as increases. By combining the kneading theory with an additional property of the quadratic map (namely that is has a negative Schwarzian derivative), we obtain a detailed description of how periodic orbits arise as (and hence the kneading sequence) increases. This theory explains the qualitative features of the bifurcation diagram in Figure 2.