One-dimensional Maps

A map is a function whose range is contained in its domain, which allows it to be iterated. One-dimensional real-valued maps are one of the simplest kinds of dynamical systems, but their dynamics turn out to be surprisingly complicated.

As a quick example of dynamics of a 1-D map, take a calculator and pick a number $x_0$. Compute $\cos(x_0)$. Take that number, $x_1 = \cos(x_0)$, and compute its cosine, $x_2 = \cos(\cos(x))$. Keep iterating until you see what happens to this sequence of numbers. In this case, the dynamics are quite simple.

We will denote iterates of a function $f$ by superscripts, so that $f^2(x) = f(f(x))$, $f^3(x) = f(f(f(x)))$, et cetera. Note that this conflicts with some other conventions in math, in particular with trigonometric functions such as cosine. In this text, $\cos^2(x)$ always means $\cos(\cos(x))$, not $\cos(x)^2$.

Basic definitions for maps

The simplest dynamical structures of maps are periodic points. A point $x$ is periodic with period $k$ if $f^k(x) = x$. We say that $x$ is a period-$k$ point if $k$ is the smallest positive integer for which $f^k(x) = x$.

An important special case of periodic points is when $k=1$, so that $f(x) = x$. These are called fixed points of the map $f$.

The (forward) orbit of a point $x$ under a map $f$ is the set of all forward iterates, $\{x,f(x),f^2(x), f^3(x), \ldots \}$. If $f$ is invertible (a pretty rare case in dynamics) then we can also speak of the backwards orbit, which would be the set of reverse iterates $\{x,f^{-1}(x),f^{-2}(x), f^{-3}(x), \ldots \}$. Even more generally, some people use the term grand orbit of $x$ to refer to the set

in which $m$ and $n$ are integers. We will mostly focus on the forward orbits.

Recall that a function $f$ with domain $D$ and range $R$ is said to be surjective, or equivalently onto, if for every point $y \in R$ there is an $x \in D$ such that $f(x) = y$. A function $f$ is injective, or one-to-one, if distinct inputs give distinct outputs, i.e. if $x_1 \neq x_2$ implies that $f(x_1) \neq f(x_2)$.

If a map $f$ is not one-to-one it can have eventually periodic points; a point $x$ is eventually periodic with period $k$ if there are integers $m$ and $n=m+k$ such that $f^n(x) = f^m(x)$. For example, the map $f=x^2$ has the eventually periodic point $-1$, since $f(-1) = f^2(-1) = 1$.

Stability of fixed points and periodic points

There are many definitions of stability in dynamical systems, and it is important to be aware of their differences.

A fixed point $x$ of a map $f$ is asymptotically stable if there exists a neighborhood $N$ of $x$ such that if $y \in N,$ then $\displaystyle \lim_{i \rightarrow \infty} f^i(y) = x$. The stable set of $x$, $W^s(x)$, is the set of all points in the domain of $f$ which have $x$ as their limit under iteration by $f$.

A weaker form of stability is Lyaponuv stability. A fixed point $x$ is Lyaponuv stable if given any neighborhood $N$ of $x$, there is a neighborhood $D$ of $x$ such that if $x \in D$ then the orbit of $x$ is contained in $N$.

For differentiable maps, a fixed point $x$ is asymptotically stable if $|f'(x)| < 1$. A fixed point $x$ is called hyperbolic if $|f'(x)| \neq 1$.

For periodic points we can use the chain rule to see the relationship between the derivatives of $f$ and the stability of the orbit. Suppose that $x_0$ is on a period-$k$ orbit, and let $x_i = f^i(x_0)$. For points near $x_0$ we consider the stability of the $k$th iterate map $f^k$, for which $x_0$ is a fixed point. From the chain rule, its derivative is

If we start at a different point on the orbit, i.e. some $x_i$ for $i>0$, we get the same factors in the derivative, so the values $(f^k)'(x_i)$ are all equal. If $|(f^k)'(x_i)| < 1$, then the orbit will be asymptotically stable.

Cobweb diagrams

It can be very helpful to visualize the iterates of a one-dimensional map $f$, and one way to do this is with a cobweb plot. Start with the graph of $f$ on an interval of interest, and the graph of the identity function $x$. Next we add an initial point $(x_0, f(x_0))$. From this point, draw a horizontal line to the diagonal $(f(x_0), f(x_0))$. From that point, draw a vertical line to $(f(x_0), f(f(x_0)))$. Repeating this process gives a cobweb plot for $f$.

The logistic map family

The logistic map family consists of the quadratic maps of the form

We will mostly consider the parameter $\lambda \in [0,4]$, since then $f_\lambda$ maps the unit interval $[0,1]$ into itself.

Change the slider to see how the orbit changes in the cobweb diagram for the logistic map family $x_{i+1} = \lambda x (1-x)$, as $\lambda$ changes:

The logistic map is one of the simplest families of maps that possesses very rich and interesting behavior under iteration, so we will use it to introduce many general concepts.

There is a always a fixed point of $f_\lambda$ at $0$. Since the fixed point equation $f_\lambda(x) = x$ is quadratic:

$$ f_\lambda(x) - x = -\lambda x^2 + (\lambda-1) x = 0 $$ there is a second fixed point at $x = \frac{\lambda-1}{\lambda}$, which is distinct from $0$ if $\lambda \neq 1$.

Critical points

Recall that a critical point of a differentiable function $f$ is a point $x$ in the domain such that $f'(x) = 0$. The value $f(x)$ at a critical point is called a critical value. The critical points are extremely important for understanding the dynamics of a function, particularly in the 1-D and complex cases.

A critical point is called degenerate if $f''(x) = 0$.

The logistic map has only one critical point, at $x=1/2$. We will use this fact later when we look at the Schwartzian operator. Since $f_\lambda'' = -\lambda$, the critical point for the logistic map is always nondegenerate for nonzero $\lambda$.

Bifurcations

A bifurcation in a family of maps is a change in the number or stability of periodic orbits caused by a small change in one of the parameters of the family.

Bifurcations in higher dimensions can be very complex, and their study forms an entire specialty area of mathematics research. In one dimension, there are only a few types of common bifurcations, and we can learn a lot about them just by looking at the logistic family.

Lets look at the first few bifurcations in the logistic map family as we increase $\lambda$ from $0$.

$\lambda \in (0,1]$

Recall that the logistic map $f_{\lambda}$ has two fixed points at $x_0 = 0$ and $x_1 = \frac{\lambda - 1}{\lambda}$. Since $f' = \lambda (1 - 2 x)$, the derivatives at the fixed points are $\lambda$ and $2 - \lambda$ respectively. For $\lambda \in (0,1)$, this means that $|f'(0)| < 1$, and $|f'(x_1)| > 1$, so $0$ is an attracting (stable) fixed point and $x_1$ is repelling (unstable). Note that we usually think of the logistic map with domain $[0,1]$, and $x_1 < 0$ is outside of that interval in this case.

When $\lambda=1$, the two fixed points have coalesced, and since $f_1'(0) = 1$ it is not immediately obvious what the stability is. Initial points less than $0$ will become more negative and diverge to $-\infty$, while points greater than $0$ will approach $0$ under the iteration. This is sometimes called a 'semi-stable' point, a particular type of one-dimensional instability.

$\lambda \in (1,3)$

For $\lambda \in (1,3)$ the second fixed point becomes attracting, since $|f'(x_1)| < 1$. It in fact the basin of attraction is the whole interior $(0,1)$, although that takes more work to prove.

When $\lambda=2$, the fixed point $x_1$ is also the critical point of $f_2$. When this occurs the fixed point is said to be super-attracting, since close enough iterates converge to it very quickly.

For $\lambda > 2$, the slope of $f$ at $x_1$ is negative, which results in a flip-flopping of the iterates near $x_1$ from one side to another (see picture below).

First period doubling at $\lambda=3$

An important type of bifurcation occurs at $\lambda=3$. The slope of $f$ decreases to $-1$, and for $\lambda > 3$ the fixed point at $x_0$ becomes unstable.

We can examine how this results in the creation of a stable period-2 orbit by studying the period-2 equation $f^2(x) = x$, or $f^2(x) - x = 0$:

This equation must contain the two fixed points at $0$ and $1 - \frac{1}{\lambda}$, so we can factor it:

The first quadratic factor contains the true period-2 points. Using the quadratic formula we can write them explicitly as

These points are real if the discriminant $(\lambda+1)(\lambda-3)$ is non-negative, which occurs for $\lambda \in (-\infty,1]$ and $\lambda \in [3,\infty)$. When $\lambda=3$, the points coincide with the fixed point, but for $\lambda>3$ they are distinct. We can compute their stability from the derivative of the second iterate map,

which evaluated at the period-2 orbit is

This quantity is less than 1 in absolute value for $\lambda \in (3, 1+\sqrt{6})$. At $\lambda = 1+\sqrt{6} \approx 3.45$, the period-2 orbit becomes unstable. In fact it undergoes a period doubling bifurcation that results in a stable period-4 orbit. We could study this in the same way as above, but if you do you will see that the polynomials grow in complexity very quickly. For example, to study the period-16 orbits we would need to analyze polynomials of degree $2^{16} = 65536$. Clearly it would be better if there were some other tools available, and there are. One of them is the Schwartzian derivative.

The Schwartzian

For one-dimensional maps there is an interesting quantity, called the Schwartzian derivative (or just the Schwartzian), that has been helpful in proving some dynamical properties. The Schwartzian derivative of a map $f$ is defined as:

One of the properties of the Schwartzian that is useful in dynamical systems is that it satisfies a kind of chain rule under composition of maps:

The following theorem about the Schwartzian derivative was used to prove a number of results about 1D maps:

Theorem (Singer): If $f : \mathbb{R} \rightarrow \mathbb{R}$ has $S(f) < 0$, then the stable set of every attracting orbit for $f$ either contains a critical point of $f$ or is unbounded.

Corollary: Suppose $f : \mathbb{R} \rightarrow \mathbb{R}$ has $S(f) < 0$. If $f$ has $n$ critical points, then $f$ admits at most $n + 2$ attracting orbits.

For the purposes of Singer's theorem, we can consider the Schwartzian to be negative if it is negative for all points where $f'(x) \neq 0$.

The logistic map has Schwartzian $-\frac{6}{{\left(2 \, x - 1\right)}^{2}}$, so it is negative in the interval $[0,1]$. The result of Singer can be refined for this case to show that there is at most one attracting orbit of the logistic map.

A key property of the Schwartzian is that it is invariant under linear fractional transformations (also called Moebius transformations) of the form

because $S(M) = 0$.

Another interesting property of the Schwartzian can be used to study ODES: if $y'' + py' + q y = 0$ has solutions $y_1$, $y_2$, then $f = y_1/y_2$ satisfies

Now if $p=0$ and $w = f''/f'$ then $w$ satisfies the Riccati equation

The Sharkovs'kyi ordering

In the late 1960s an amazing theorem on 1D maps was proven by the Ukrainian mathematician Oleksandr Sharkovs'kyi. If $f$ is a continuous map on an interval $I$, Sharkovs'kyi proved that if $f$ has periodic orbits of certain periods then it must have periodic orbits with other periods. The structure of the implied periods follows a single ordering, called the Sharkovsky ordering, in which:

The existence of a periodic orbit with period $k$ implies the existence of periodic orbits with periods $k'$ where $k'$ is any integer below $k$ in the Sharkovs'kyi ordering. The most striking consequence of this theorem is that if a continuous map of an interval has a period-3 orbit, then it must have periodic orbits with all integer periods.

Sharkovs'kyi Example

To illustrate the idea behind Sharkovs'kyi's theorem we will consider the specific example of the map $f(x) = \frac{-3 x^2}{2} + \frac{5 x}{2} + 1$, which has a period-3 orbit of $f(0) = 1$, $f(1) = 2$, and $f(2) = 0$. A cobweb plot of this orbit is shown below.

Suppose we want to find a period-5 orbit for this map, which must exist by Sharkovs'kyi's theorem. We can construct this orbit by first finding an interval in $I_1 = [1,2]$ that after four iterations covers the interval $[0,2]$, and then finding its preimage in $I_0 = [0,1]$.

Using the quadratic formula we can find the preimages of the interval points that we need:

From these values we can see that the interval

in $I_1$ is the preimage of $A_1$ where $f(A_0) = A_1 = [\frac{4}{3}, \frac{5 + \sqrt{17}}{6}]$. Similarly $f(A_1) = A_2 = [\frac{4}{3},\frac{5}{3}]$, and $f(A_2) = A_3 = [1, \frac{5}{3}]$ and $f(A_3) = A_4 = [1,2] = I_1$. Then since $f^{5}(A_0) = f(I_1) = [0,2]$, $A_0$ is contained in the image of $f^{5}$ and there must be a fixed point of $f^{5}$ in $A_0$. Because $A_0 \subset I_0$ and the other $A_i$ are subsets of $I_1$, the resulting orbit must have minimal period 5.

This orbit, along with the interval $A_0$, is shown in the cobweb plot below.

Topological conjugacy

Sometimes we can use a homeomorphism as a change of coordinates to make the analysis of a map much simpler. We define two maps $f$ and $g$ to be topologically conjugate if there exists a homeomorphism $h$ such that $h \circ f = g \circ h$. This definition works in any dimension, but its quite hard to find useful conjugacies, at least explicitly, in higher dimensions.

Topologically conjugate maps have essentially the same dynamics, since many properties such as periodic points are preserved. For example if $x$ is a period-$k$ point of a map $f$, then if $g$ is topologically conjugate to $f$, $y = g(x)$ is a period-$k$ point of $g$:

The Tent Map

The tent map $T:[0,1] \rightarrow [0,1]$ is a piecewise-linear map defined by

An interesting example of a conjugacy has been found for the logistic map with parameter $\lambda=4$, i.e. $f_4 = 4 x (1 - x)$, and the tent map. The function $h = (\sin{\frac{\pi x}{2}})^2$ provides the conjugacy, since $T \circ h = (\sin{\pi x})^2 = h \circ f_4$.

Sensitive dependence on initial conditions

One of the key ingredients to chaotic dynamics is sensitive dependence on initial conditions. This is a kind of instability, in which iterates of arbitrarily close points diverge from one another, at least for a while. More precisely, we say that a map $f$ has sensitive dependence on initial conditions at a point $x_0$ if for any neighborhood $N$ of $x_0$ there is a distance $d>0$ such that $|f^k(x) - f^k(x_0)| > d$ for some point $x \in N$ and some positive integer $k$.

Once again the logistic map can provide a relatively simple example of this concept. If $\lambda > 4$, then $f_{\lambda}$ sends some of the interval $[0,1]$ outside itself. One option is if we restrict the map to the subset $V$ of $[0,1]$ that is invariant under $f$. This invariant subset has a fractal structure that is a deformation of one of the most famous fractals, the Cantor (or Smith-Volterra-Cantor) set. In order for a point to have an infinite orbit that is contained in $[0,1]$, it must avoid the middle part of the interval for which $f>1$. The preimage of this interval consists of two intervals, and their preimages consist of four intervals, and so on, so to get the invariant set we must remove an infinite number of intervals from $[0,1]$.

If $\lambda > 2 + \sqrt{5}$, then the slope of $f$ is always larger than 1 on the invariant set. This means that every neighborhood of every point in $V$ is expanding.

Symbolic dynamics

A powerful tool in dynamical systems is to find some sort of conjugacy (possibly only covering part of the system of interest) to a simpler symbolic dynamic system, in particular to what is often called a subshift of finite type. We will briefly explain what this is here, and it will also come up later in studying higher dimensional dynamics. Then we will give some examples of its use in 1D dynamics such as the logistic map.

The simplest symbolic dynamical system is the full shift on bi-infinite sequences (indexed by the integers) from some fixed finite alphabet $\mathcal{A}$. The dynamical system is given by the shift map $\sigma$, which as its name implies simply shifts the indices of the sequence - i.e. if $s$ is a bi-infinite sequence, then the $j$th entry of $\sigma(s)$ is the $(j+1)$th entry of $s$.

There are many variations on this idea; one of the most common is to use one-sided sequences, indexed by non-negative integers, so that

Usually the alphabet used consists of integers, and in those cases a metric of the form

$$ d(s,t) = \sum_{0}^{\infty} \frac{|s_i - t_i|}{|\mathcal{A}|^i} $$ can be used (the above formula is for 1-sided sequence spaces).

Symbolic dynamics for the logistic map

We can connect the dynamics of a map such as the logistic map with symbolic dynamics through an itinerary map.

The Sawtooth and Doubling maps

Another interesting and relatively simple map that is connected to the previous ideas is the sawtooth map defined on $[0,1)$ by

We can define an itinerary map $p(x)$ for $x \in [0,1)$ by assigning the $j$th entry of the output sequence to be $0$ if $f^j(x) \in [0,1/2)$, or $1$ if $f^j(x) \in [1/2,1)$. This itinerary map gives one choice of binary expansion for the number $x$.

Somewhat surprisingly, the sawtooth map is conjugate to the tent map $T$, with the conjugating function being $T$ itself: $T(T(x)) = S(T(x))$. This can be verified by checking both compositions on the intervals $[0,1/4]$, $[1/4,1/2)$, $[1/2,3/4]$, and $[3/4,1]$:

Although the sawtooth map is not continuous on $[0,1)$, it can be thought of as a continuous function on the circle if we identify the point $0$ with the point $1$. One way to model this map is to consider the circle as the unit circle in the complex plane. Points on the complex unit circle can be written as $e^{i 2 \pi t}$, and then the squaring map $z^2$ will simply double the angular coordinate $t$ when restricted to the circle:

We put the $2 \pi$ factor in the exponent to make it easier to relate this map to the sawtooth map.

Maps of the circle arise naturally in many applications. The topological differences between the circle and the real line mean that circle maps form their own area of study within one-dimensional dynamics, and generalize to higher dimensions in distinct ways.

Circle Maps

Circle maps are an important group of 1-dimensional maps, in which the domain and range are a circle (usually taken to be the unit circle), $S^1$. It is convenient to represent points on the circle in complex form, as $e^{i \theta}$ for some real angle $\theta$. The simplest circle maps are rotations, $R_{\phi}$, which increase the angle $\theta$ by a fixed constant $\phi$. Below is a picture of the orbit of $\theta=0$ under the rotation with $\phi = \frac{13 \pi}{20}$. For this $\phi$, after 40 iterations every point will return to itself, so every point of the circle is on a periodic orbit with period 40.

If the rotation is not a rational multiple of $\pi$, then there are no periodic orbits, because $\pi$ is irrational . In this case, every orbit is dense on the circle (see if you can prove that!). The image below shows the first 300 points of an orbit with rotation angle $\phi = \pi/g$ where $g$ is the golden ratio $g = \frac{1 + \sqrt{5}}{2}$.

This result on the density of orbits for irrational rotations is one of the main inspirations for the notion of topological transitivity. A map is topologically transitive if there is a point with a dense orbit. A stronger condition is that a map is minimal if the orbit of every point is dense.

Exercises

• • For what values of $k \in \mathbb{R}$ does the map $f : \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x) = kx^4 - x$ have nonzero fixed points?

  • How does the stability of the fixed points depend on $k$?

• Sketch a cobweb diagram for four iterations of the function $f(x) = 2 x^2 - 1$, starting at $x_0 = 2/3$.

• Let $S(x) = ( 10 x \ \text{ mod } \ 1)$ be a map of the unit interval (for example $S(0.34) = 0.4$, and $S(10.912) = 0.12$).

  • What are the fixed points of $S(x)$ (on the unit interval)?

  • What is a point in $[0,1]$ that is not eventually periodic under the map $S$ (i.e. find an $x$ such that $S^n(x)$ is not periodic for any natural number $n$).

• Suppose that a continuous function $f$ maps an interval $[a,b]$ into itself, and that there is a period-2 point of $f$. Sketch a picture that suggests why there must be a fixed point of $f$.

• If $f$ is a continuous decreasing function $f:[a,b] \rightarrow \mathbb{R}$, prove that it cannot have a period-3 orbit.

• For the Newton's method map $x_{n+1} = x_n - \frac{p(x_n)}{p'(x_{n})}$ for the polynomial

  $$p(x) = 16 \, x^{3} - 36 \, x^{2} + 4 \, x - 9$$

  characterize the orbits of (a) $x_0 = 2$ and (b) $x_0 = 4/5$ (e.g. are they periodic or eventually periodic).

• Find a linear conjugacy $h(x) = Ax + B$ between $f(x) = 4 x (1-x)$ and a function $g(x) = x^2 + c$ (so $h(f(x)) = g(h(x))$ for some value of $c$), with $A \neq 0$, or explain why no such function exists.

• For the tent-like map $T: [0,1] \rightarrow [0,1]$ defined as

  $$T(x) = \left \{ \begin{array}{l} 3 x \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ if } x \le 1/3 \\ 3(1-x)/2 \ \ \ \text{ if } x > 1/3 \end{array} \right .$$

  • sketch the graphs of $T(x)$, $T^2(x)$ and $T^3(x)$.

  • Find the number of fixed points, period-2 points, and period-3 points of $T$, along with their stability (i.e. are they sources, sinks, or neither?).

• Prove that the Schwartzian derivative

  $$S(f) = \frac{f'''}{f'} - \frac{3}{2} \left ( \frac{f''}{f'} \right )^2$$

  of the quadratic map $f(z) = z^2 + c$ (treating $c$ as a constant) is negative wherever it is defined.

• Prove that the only periodic orbits of the map $f(x) = 16 x (1-x)/5$ have periods 1,2, and 4.

• For the piecewise linear map $f:[0,1] \rightarrow [0,1]$ defined as

  $$f(x) = \left \{ \begin{array}{ll} 1/2 + x & \text{ if } x < 1/4 \\ x - 1/4 & \text{ if } x \in [1/4,3/4) \\ 1 - x & \text{ if } x \ge 3/4 \end{array} \right .$$

  (a) Draw the transition graph for the intervals $A = (0,1/4)$, $B = (1/4,1/2)$, $C = (1/2,3/4)$, $D = (3/4,1)$.

  (b) What does Sharkovsky's theorem guarantee for the periodic orbits of this map?

• A point $(x,y)$ in the unit square $[0,1] \times [0,1]$ can be encoded as a sequence of symbols $a_0 a_1 a_2 a_3 \ldots$, in which $0.a_0a_2a_4\ldots$ is the binary representation of $x$ and $0.a_1a_3a_5\ldots$ is the binary representation of $y$. What is the Euclidean distance between two points with symbol sequences $a_0 a_1 a_2 a_3 \ldots$ and $b_0 b_1 b_2 b_3 \ldots$ ?

License

This work (text, mathematical images, and javascript applets) is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Biographical images are from Wikipedia and have their own (similar) licenses.