A Remarkable Property of Real-Valued Functions on Intervals of the Real Line

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 let $f:I\to\mathbb{R}$ be a continuous function su. 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, let $f:I\to\mathbb{R}$ be 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, 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) 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) 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. 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.

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 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 period $m, 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, in increasing order; then, all the doubles of the odd numbers, in increasing order; then, all the quadruples of the odd numbers, 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.