Today the 17 October 2019 I discussed a very remarkable fixed point theorem discovered by the Ukrainian mathematician Oleksandr Micholayovych Sharkovsky.

We recall that a periodic point of period n\geq1 for a function f:X\to{X} is a point x_n such that f^n(x_n)=x_n. With this definition, a periodic point of period n is also periodic of period m for every m which is a multiple of n. If f^n(x_n)=x_n but f^k(x_n)\neq{x_n} for every k from 1 to n-1, we say that n is the least period of x_n.

Theorem 1. (Sharkovsky’s “little” theorem) Let I\subseteq\mathbb{R} be an interval and f:I\to\mathbb{R} a continuous function. If f has a point of least period 3, then it has points of arbitrary least period; in particular, it has a fixed point.

Note that no hypothesis is made on I being open or closed, bounded or unbounded.

Our proof of Sharkovsky’s “little” theorem follows the one given in (Sternberg, 2010), and could even be given in a Calculus 1 course: the most advanced result will be the intermediate value theorem.

Lemma 1. Let I=[a,b] be a compact interval of the real line and f:I\to\mathbb{R} a continuous function. Suppose that for some compact interval J it is I\subseteq{J}\subseteq{f(I)}. Then f has a fixed point in J.

Proof. Let m and M be the minimum and the maximum of f in I, respectively. As I\subseteq{f(I)}, it is m\leq{a} and M\geq{b}. Choose u,v\in{I} such that f(u)=m and f(v)=M. Then g(x)=f(x)-x is nonpositive at x=u and nonnegative at x=v. By the intermediate value theorem applied to g, f must have a fixed point in the closed and bounded interval (possibly reduced to a single point) delimited by u and v, which is a subset of J. \Box

Lemma 2. In the hypotheses of Lemma 1, let K be a closed and bounded interval contained in f(I). Then there exists a closed and bounded subinterval J of I such that f(J)=K.

Proof. Let K=[c,d]. We may suppose c<d, otherwise the statement is trivial. Let u\in{I} be the largest such that f(u)=c. Two cases are possible.

  1. There exists x\in(u,b] such that f(x)=d. Let v be the smallest such x, and let J=[u,v]. Then surely f(J)\supset{K}, but if for some x\in(u,v) we had either f(x)<c or f(x)>d, then by the intermediate value theorem, for some y\in(u,v) we would also have either f(y)=c or f(y)=d, against our choice of u and v.
  2. f(x)<d for every x\in(u,b]. Let then w be the largest x\in[a,u] such that f(x)=d, and let J=[w,u]. Then f(J)=K for reasons similar to those of the previous point.

\Box

Proof of Sharkovsky’s “little” theorem. Let a,b,c,\in\mathbb{R} be such that f(a)=b, f(b)=c, and f(c)=a. Up to cycling between these three values and replacing f(x) with -f(-x), we may suppose a<b<c. Fix a positive integer n: we will prove that there exists x_{n}\in{I} such that f^n(x_{n})=x and f^i(x_{n})\neq{x_{n}} for every i<n.

Let L=[a,b] and R=[b,c] be the “left” and “right” side of the closed and bounded interval [a,c]: then R\subseteq{f(L)} and L\cup{R}\subseteq{f(R)} by the intermediate value theorem. In particular, R\subseteq{f(R)}, and Lemma 1 immediately tells us that f has a fixed point x_{1} in R. Also, L\subseteq{f(R)}\subseteq{f^2(L)}, so f also has a point of period 2 in L, again by Lemma 1: call it x_{2}. This point x_{2} cannot be a fixed point, because then it would also belong to R as L\subseteq{f(R)}, but L\cap{R}=\{b\} which has period 3. As we can obviously take x_{3}=b, we only need to consider the case n\geq4.

By Lemma 2, there exists a closed and bounded subinterval A_1 of R such that f(A_1)=R. In turn, as A_1\subseteq{R}, there also exists a closed and bounded subinterval A_2 of A_1 such that f(A_2)=A_1, again by Lemma 2: but then, f^2(A_2)=f(A_1)=R. By iterating the procedure, we find a sequence of closed and bounded intervals A_i such that, for every i\geq1, A_{i+1}\subseteq{A_i} and f^i(A_i)=R.

We stop at i=n-2 and recall that R\subseteq{f(L)}: we are still in the situation of Lemma 2, with A_{n-2} in the role of K. So we choose A_{n-1} as a closed and bounded subinterval not of A_{n-2}, but of L, such that f(A_{n-1})=A_{n-2}. In turn, as L\subseteq{f(R)}, there exists a closed and bounded subinterval A_n of R such that f(A_n)=A_{n-1}. Following the chain of inclusions we obtain f^n(A_n)=R. By Lemma 1, f^n has a fixed point x_n in A_n, which is a periodic point of period n for f.

Can the least period of x_n for f be smaller than n? No, it cannot, for the following reason. If x_{n} has least period m\leq{n}, then so has y=f(x_{n}), and in addition n is divisible by m. But f(x_n)\in{L} while f^i(x_n)\in{R} for every i\in[2:n]. Consequently, if x_{n} has least period m<n, then y\in{L}\cap{R}=\{b\}. But this is impossible, because f^{2}(y)=f^{3}(x_{n})\in{R} by construction as n\geq4, while f^{2}(b)=a\not\in{R}. \Box

Theorem 1 is a special case of a much more general, and complex, result also due to Sharkovsky. Before stating it, we need to define a special ordering on positive integers.

Definition. The Sharkovsky ordering \rhd between positive integers is defined as follows:

  • Identify the number n=2^k\cdot{m}, with m odd integer, with the pair (k,m).
  • Sort the pairs with m>1 in lexicographic order.

    That is: first, list all the odd numbers larger than 1, in increasing order; then, all the doubles of the odd numbers larger than 1, in increasing order; then, all the quadruples of the odd numbers larger than 1, in increasing order; and so on.

    For example, 17\rhd243 and 4095\rhd6

  • Set (k,m)\rhd(h,1) for every m>1 and k,h\geq0.

    That is: the powers of 2 follow, in the Sharkovskii ordering, any number which has an odd factor.

    For example, 17000000000000\rhd2.

  • Sort the pairs of the form (k,1)—i.e., the powers of 2—in reverse order.

The set of positive integer with the Sharkowsky ordering has then the form:

3\rhd5\rhd7\rhd\ldots\rhd6\rhd10\rhd14\rhd\ldots\rhd12\rhd20\rhd28\rhd\ldots\rhd8\rhd4\rhd2\rhd1

Note that \rhd is a total ordering.

Theorem 2. (Sharkovsky’s “great” theorem) Let I be an interval on the real line and let f:\mathbb{R}\to\mathbb{R} be a continuous function.

  1. If f has a point of least period m, and m\rhd{n}, then f has a point of least period n. In particular, if f has a periodic point, then it has a fixed point.
  2. For every m\geq1 integer it is possible to choose I and f so that f has a point of minimum period m and no points of minimum period k for any k\rhd{m}. In particular, there are functions whose only periodic points are fixed.

Bibliography:

  • Keith Burns and Boris Hasselblatt. The Sharkovsky theorem: A natural direct proof. The American Mathematical Monthly 118(3) (2011), 229–244. doi:10.4169/amer.math.monthly.118.03.229
  • Robert L. Devaney, An Introduction to Chaotic Dynamical Systems, Second Edition, Westview Press 2003.
  • Shlomo Sternberg, Dynamical Systems, Dover 2010.