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<d$ , otherwise the statement is trivial. Let $u\in{I}$ be the largest such that $f(u)=c$ . Two cases are possible.

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$ .
$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 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<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, 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.

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

Theory Lunch

Institute of Cybernetics, Tallinn

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply