Posted by: Dave Richeson | December 18, 2008

## Sharkovsky’s theorem

In this post I would like to share one of the most surprising, remarkable, and beautiful results in the study of discrete dynamical systems. It relates to an unusual ordering of the positive integers:

$3, 5, 7, 9, \ldots ,2\cdot 3, 2\cdot 5, 2\cdot 7,\ldots , 2^2\cdot 3, 2^2\cdot 5,\ldots , 2^4, 2^3, 2^2, 2, 1.$

First, some definitions. The basic object of study in a discrete dynamical system is the orbit. Let $f$ be a function from $\mathbb{R}$ to $\mathbb{R}$ (think $f(x)=x^2$, $f(x)=\sin x$, $f(x)=e^x$, etc.). A sequence of real numbers $x_0,x_1,x_2,\ldots$ is an orbit (or the orbit of $x_0$) provided $x_{k}=f(x_{k-1})$ for all $k\ge 1$. Another way of saying this is that $x_k=f^k(x_0)$ for all $k\ge 1$ where $f^k=f\circ f\circ \cdots\circ f$ (composition $k$ times). We think of the orbit of $x$ as motion—$x$ hops along the real number line with the new position determined by an application of $f$.

For example, if $f(x)=x^2$, then the orbit of 2 is $2,4,16,256,\ldots$

A fixed point is a real number $x$ such that the orbit of $x$ is constant: $x,x,x,x,\ldots$ Equivalently, it is a point $x$ such that $f(x)=x$.

For example, the function $g(x)=2x(1-x)$ has two fixed points: $x=0$ and $x=\frac{1}{2}$. To see that these are fixed points, observe that $g(0)=0$ and $g(\frac{1}{2})=\frac{1}{2}$. To see that they are the only fixed points, solve $x=2x(1-x)$ for $x.$

A value $x$ is a periodic point of period $n$ if the orbit of $x$ is periodic of period $n$ (called a periodic orbit or a cycle). Equivalently, $f^n(x)=x$, but $f^k(x)\ne x$ for $0.

For example, consider the function

$h(x)=-\frac{3}{2}x^{2}+\frac{11}{2}x-2.$

The value $x=1$ is a point of period 3 for $h$. Why? We see that: $h(1)=2,$ $h(2)=3,$ and $h(3)=1$. So the orbit of 1 is

$1,2,3,1,2,3,1,2,3,\ldots$

Now the motivating question: does the function $h$ have any other periodic points? If so, of what periods?

For very small values of $n$ it may be possible to use algebra to answer this question, but algebra fails quickly (notice that solving $h^k(x)=x$ requires finding the roots of a polynomial of degree $2^k$).

In 1975 James Yorke and his graduate student Tien-Yien Li proved the following remarkable theorem in a paper called “Period Three Implies Chaos” (Amer. Math. Monthly 82, 985-992, 1975). Their theorem implies that $h$ has points of every period!

Theorem [Li-Yorke]. Let $I\subset \mathbb{R}$ be an interval (possibly $I=\mathbb{R}$). If a continuous function $f:I\to I$ has a point of period 3, then it has a point of period $k$ for every $k\ge 1$.

That is, if there is a period-three orbit, then there are orbits of every period—chaos!

This theorem amazed the mathematical community. In fact, Li and Yorke’s paper was responsible for introducing the word “chaos” into the mathematical vocabulary. (Now there are several competing definitions of chaos.)

However, little did they know this result had been proved over a decade before, and as a special case of a truly remarkable theorem.

In 1964, the Ukrainian mathematician Aleksandr Nikolayevich Sharkovsky introduced the following ordering on the positive integers (Sharkovsky, A.N. “Coexistence of cycles of continuous mapping of the line into itself.” Ukrainian Math. J., 16, 61-71, 1964):

$3\prec 5 \prec 7\prec 9\prec\ldots\prec 2\cdot 3\prec 2\cdot 5\prec 2\cdot 7\prec \ldots\prec 2^2\cdot 3\prec 2^2\cdot 5\prec \ldots\prec 2^4\prec 2^3\prec 2^2\prec 2\prec 1.$

First come the odd numbers, then the doubles of the odd numbers, then $2^2$ times each odd number, etc. When all of these values are exhausted, the ordering ends with the powers of 2.

Sharkovsky’s theorem says the following:

Theorem [Sharkovsky]. Let $I\subset \mathbb{R}$ be an interval. If a continuous function $f:I\to I$ has a point of period $n$, then it has a point of period $k$ for every $k$ with $n\prec k$.

Notice that the first term in the Sharkovsky ordering is 3. Thus, if we apply Sharkovsky’s theorem with $n=3$ we get the Li-Yorke theorem. But clearly Sharkovsky’s theorem is much deeper. If there is a point of period 9, there is a point of period 6, if there is a point of period 8, there is a point of period 4, and so on.

Finally, I will add that the theorem cannot be strengthened in any obvious way. Without continuity the theorem fails, and it fails for dynamical systems on spaces other than $\mathbb{R}$. Moreover, there exist dynamical systems containing a periodic point of period $n$ and no periodic point of period $k$ for any $k$ with $k\prec n$.