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<x<n.

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.

About these ads

Responses

  1. Very cool. Thanks for sharing that.

  2. wonderful blog. Thanks for sharing.

  3. [...] logistic map with . There is an attracting period 3 orbit. As I explained in my earlier post about Sharkovsky’s Theorem, the existence of a period 3 oribit implies that there are periodic orbits of every period! [...]

  4. [...] Period 3 implies chaos (and Sharkovsky’s theorem) [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 203 other followers

%d bloggers like this: