## Period Three Implies Chaos

tags: Dynamics

Suppose $$I = [0,1]$$ and $$f: I \to I$$ is a continuous function.

Definition 1. $$f$$ has a period-$$m \ge 1$$ point if there exists $$x \in I$$ such that $$f^m(x) = x$$ but $$f^i(x) \ne x$$ for $$1 \le i < m.$$ If $$m=1,$$ then we say $$f$$ has a fixed point.

Suppose $$m < n,$$ then a natural question to ask is whether having a period-$$m$$ point implies having a period-$$n$$ point or vice-versa. In the simple case where $$m=1$$ and $$n=2,$$ it is obvious that having a fixed point does not guarantee having a period-$$2$$ point: Let $$f(x) = x$$ then every point is a fixed point. On the other hand, the intermediate value theorem (IVT) gives us the other implication:

IVT. Suppose $$g:[a,b] \to {\mathbb R}$$ is continuous and, without loss of generality, $$g(a) \le g(b)$$ then for every $$r \in [g(a), g(b)]$$ there exists $$c \in [a,b]$$ such that $$g(c) = b.$$

The topological form of this theorem states that continuous functions preserve connectedness.

Theorem 2. period-$$2$$ point $$\Rightarrow$$ fixed point.

Proof: Let $$a$$ be a period-$$2$$ point and $$b=f(a) \ne a.$$ Then $$f(b) = f^2(a)=a \ne b$$ and $$f^2(b) = f(a) = b.$$ So $$b$$ is a period-$$2$$ point as well. In fact, $$f$$ swaps $$a$$ and $$b.$$ Assume without loss of generality that $$a < b$$ and let $$g(x) = x - f(x)$$ be defined on $$[a, b] \subset I.$$ Then $$g(a) = a - b < 0$$ and $$g(b) = b - a > 0.$$ By IVT, there exists $$c \in [a,b]$$ such that $$g(c) = 0.$$ So $$f(c) = c$$ and $$f$$ has a fixed point.$$~\Box$$

And if you let $$f(x) = 1 - x,$$ then all points except $$x = 0.5$$ are period-$$2$$ points while $$x = 0.5$$ is the fixed-point guaranteed by the theorem. Evidently, the existence of period-$$2$$ points does not imply the existence of period-$$m$$ points, for $$m > 2.$$

So in a similar vein, one might ask whether the existence of a period-$$3$$ point implies

• the existence of a fixed point.
• the existence of a period-$$2$$ point
• the existence of a period-$$m$$ point for $$m > 3$$

Tien-Yien Li and James Yorke published a paper in 1954 that suprisingly answered “yes” to all the implications.

Li-Yorke, '75. period-3 point $$\Rightarrow$$ period-$$m,$$ for all $$m \ge 1.$$

To be fair, they proved much more than what I just stated but I'll just stick to this for now cause I want to highlight their elegant use of IVT. So something very interesting happens at $$m=3$$ and you might wonder how to go about proving such a general theorem. The proof will still rely on IVT but we'll have to be clever on the type of sets/functions we apply it to. We'll need two lemmas:

Lemma 4. Suppose $$g:[a,b] \to {\mathbb R}$$ is continuous and $$[c,d] \subset g([a,b]),$$ then there exists $$[a', b'] \subset [a,b]$$ such that $$g([a',b']) = [c,d]$$

Proof: Since $$g$$ is continuous, the pre-image of $$(c,d)$$ must be open in $$[a,b],$$ hence a disjoint union of open intervals. Let $$(a',b') \subset g^{-1}((c,d))$$ be one of these intervals. By continuity, $$g([a', b' ]) = [ c, d ]. $~\Box$$ Lemma 5. Suppose $$f: I \to I,$$ $$I_0 = [a_0,b_0] \subset g(I_0).$$ Then there exists closed intervals $$I_n \subset I_0$$ such that $$g(I_n) = I_{n-1},$$ for all positive integers $$n.$$ In particular, $$g^n(I_n) = I_0$$ for all positive integers $$n$$ Proof by induction: When $$n=1,$$ the statement holds by the lemma 4. Assume that $$I_n \subset I_0$$ and $$g(I_n) = I_{n-1}$$ for some $$n \ge 1,$$ then let $$[c,d] = I_n \subset I_0 \subseteq g(I_0),$$ then by lemma 4, there exists $$I_{n+1} = [a_{n+1}, b_{n+1}] \subset I_0$$ such that $$g(I_{n+1}) = I_n.$~\Box$$

Proof of Li-Yorke: Suppose $$a \in I$$ is a period-$$3$$ point. Let $$b = f(a) \neq a$$ and $$c = f(b)\neq a,b,$$ then $$f(c) = f^3(a) = a$$ and $$a, b, c$$ are all period-$$3$$ points. Without loss of generality, we have either $$a < b < c$$ or $$c < b < a.$$ In both cases, by IVT, $$[b, c] \subset f([a,b])$$ and $$[a,c] \subset f([b,c]).$$ Again by IVT, $$f$$ has a fixed point in $$[b,c].$$

Fix a positive integer $$m > 1$$ and let $$I_0 = [b,c],$$ then, by lemma 5, there exists closed intervals $$I_n \subset [b,c]$$ such that $$f(I_n) = I_{n-1},$$ for all $$n \ge 1.$$ Since $$I_{m-2} \subset [b,c] \subset f([a,b]),$$ by lemma 4, there exists $$[a',b'] \subset [a,b]$$ such that $$f([a', b']) = I_{m-2}.$$ So \begin{aligned} ~[a', b'] \subset [a,b] &\subset [a,c] \\ &\subset f([b,c]) \\ &= f^{m-1}(I_{m-2}) \\ &= f^{m}([a',b']) \end{aligned} By IVT, $$f^m$$ has a fixed point $$x_0 \in [a',b'].$$ Since $$f^i([a',b']) = f^{i-1}(I_{m-2}) = I_{m-i-1} \subset [b,c]$$ is disjoint from $$[a', b']$$ for $$i< m,$$ then $$f^i(x_0) \neq x_0$$ for $$i < m.$$ Therefore $$x_0$$ is a period-$$m$$ point.$$~\Box$$

The crucial step in the proof was recognition that $$f$$ acted on the set $${ a,b,c }$$ by cyclic rotation. This simplicity is lost when look at period-$$m$$ points with $$m > 3.$$ So it seems sort of hopeless to use the same argument to say which period-$$n$$ points are guaranteed when period-$$m$$ points exists, $$m > 3.$$ Li & Yorke did not address this question in the paper.

Surprisingly, Oleksandr Sharkovsky, a Ukranian mathematician had answered it completely back in $$1964$$ but the theorem had gone largely unnoticed outside of Eastern Europe. I will now state the full theorem but save proof for another time:

Definition 2. The positive integers have admit the following ordering: $3 \prec 5 \prec 7 \prec \cdots \prec 2\cdot3 \prec 2\cdot 5 \prec 2 \cdot 7 \prec \cdots \prec 2^2 \cdot 3 \prec 2^2 \cdot 5 \prec \cdots \prec 2^3 \prec 2^2 \prec 2 \prec 1$ This is known as Sharkovsky's ordering.

Sharkovsky, '64. If $$m \prec n$$ in Sharkovsky's ordering, then $\textrm{period-}m \Rightarrow \textrm{period-}n$ and the converse is true.

To fully apperciate this theorem, let $$\succ$$ be a (new) relation on the positive integers such that $$m \succ n$$ if (and only if) period-$$m$$ implies period-$$n.$$ Then we have only proven that:

• $$2 \succ 1$$
• $$1 \nsucc m$$ for $$m > 1$$
• $$2 \nsucc m$$ for $$m > 2$$
• $$3 \succ m$$ for $$m \ge 1$$

$$\succ$$ is obviously transitive and reflexive, but we have yet to prove the relation is antisymmetric and total. I will however one thing for you to prove:

Exercise 1. $$5 \nsucc 3 ,$$ that is, period-$$5$$ $$\not\Rightarrow$$ period-$$3$$

Hint: Let $$f:I \to I$$ be define as $$f(0)=\frac{1}{2},$$ $$f(\frac{1}{4})=1,$$ $$f(\frac{1}{2}) = \frac{3}{4},$$ $$f(\frac{3}{4})=\frac{1}{5}$$, $$f(1)=0$$ and $$f$$ is linear in between the points $$0, \frac{1}{4}, \frac{1}{2}, \frac{3}{4}, 1.$$ Prove that $$f$$ has no period-$$3$$ point.

References

Li, T. Y. and Yorke, J. A. “Period Three Implies Chaos” The American Mathematical Monthly 82.10 (1975): 985-992. Web.