Euler, Erdős

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.