Suppose we are given a continuous function f:[0,1][0,1]f: [0, 1] \to [0, 1]. For example, the graph of ff may look like this:

\begin{tikzpicture} 
    \draw (0, 0) rectangle (5, 5);
    \node [left] at (0, 0) {$(0, 0)$};
    \node [right] at (5, 0) {$(1, 0)$};
    \node [left] at (0, 5) {$(0, 1)$};
    \node [right] at (5, 5) {$(1, 1)$};

    \draw [blue, semithick] (0, 0) parabola bend (2.5, 2.25) (5, 0);
  \end{tikzpicture}

One interesting thing to do is to randomly pick a point x[0,1]x \in [0, 1], keep applying ff, and see where we end up. We can visualize this process via a cobweb diagram, drawn as follows:

\begin{tikzpicture} 
    \draw (0, 0) rectangle (5, 5);
    \node [left] at (0, 0) {$(0, 0)$};
    \node [right] at (5, 0) {$(1, 0)$};
    \node [left] at (0, 5) {$(0, 1)$};
    \node [right] at (5, 5) {$(1, 1)$};

    \draw [blue, semithick] (0, 0) parabola bend (2.5, 2.25) (5, 0);

    \draw [dashed] (0, 0) -- (5, 5);

    \draw [red] (1.0, 0) node [below, black] {$x_0$}
    -- (1.0, 1.44) -- (1.44, 1.44)
    -- (1.44, 1.845) -- (1.845, 1.845)
    -- (1.845, 2.095) -- (2.095, 2.095)
    -- (2.095, 2.19) -- (2.19, 2.19)
    -- (2.19, 2.215) -- (2.215, 2.215);

    \node [fill, circle, inner sep=0, minimum size=3] at (2.215, 2.215) {};
    \node [above] at (2.215, 2.215) {$x_*$};
  \end{tikzpicture}

We see that we converge towards the point xx_*. In particular, if we start at xx_*, we stay there all the time — xx_* is a fixed point.

Some choices of ff give more complicated behaviour. For example, in the following diagram

\begin{tikzpicture} 
    \draw (0, 0) rectangle (5, 5);
    \node [left] at (0, 0) {$(0, 0)$};
    \node [right] at (5, 0) {$(1, 0)$};
    \node [left] at (0, 5) {$(0, 1)$};
    \node [right] at (5, 5) {$(1, 1)$};

    \draw [blue, semithick] (0, 0) parabola bend (2.5, 4) (5, 0);

    \draw [dashed] (0, 0) -- (5, 5);

    \draw [red] (0.75, 0) node [below, black] {$x_0$}
    -- (0.75, 2.04) -- (2.04, 2.04)
    -- (2.04, 3.865) -- (3.865, 3.865)
    -- (3.865, 2.81) -- (2.81, 2.81)
    -- (2.81, 3.94) -- (3.94, 3.94)
    -- (3.94, 2.675) -- (2.675, 2.675)
    -- (2.675, 3.98) -- (3.98, 3.98)
    -- (3.98, 2.6) -- (2.6, 2.6)
    -- (2.6, 3.995) -- (3.995, 3.995)
    -- (3.995, 2.57) -- (2.57, 2.57)
    -- (2.57, 3.995) -- (3.995, 3.995)
    -- (3.995, 2.57) -- (2.57, 2.57)
    -- (2.57, 3.995) -- (3.995, 3.995)
    -- (3.995, 2.57) -- (2.57, 2.57)
    -- (2.57, 3.995) -- (3.995, 3.995)
    -- (3.995, 2.57) -- (2.57, 2.57)
    -- (2.57, 3.995) -- (3.995, 3.995)
    -- (3.995, 2.57) -- (2.57, 2.57);

    \node [fill, circle, inner sep=0, minimum size=3] at (2.57, 3.995) {};
    \node [above] at (2.57, 3.995) {$x_1$};
    \node [fill, circle, inner sep=0, minimum size=3] at (3.995, 2.57) {};
    \node [below] at (3.995, 2.57) {$x_2$};
  \end{tikzpicture}

we see that in the limit, the point oscillates between x1x_1 and x2x_2. In this case, x1x_1 and x2x_2 are 22-periodic points. Perhaps if we want to care about the limiting behaviour, we should understand these periodic points.

Definition

Let f:[0,1][0,1]f: [0, 1] \to [0, 1] be a function. A point x[0,1]x \in [0, 1] is nn-periodic if fn(x)=xf^ n(x) = x and fk(x)xf^ k(x) \neq x for 0<k<n0 < k < n.

For example, for the following choice of ff, we have a 33-periodic point:

\begin{tikzpicture} 
    \draw (0, 0) rectangle (5, 5);
    \node [left] at (0, 0) {$(0, 0)$};
    \node [right] at (5, 0) {$(1, 0)$};
    \node [left] at (0, 5) {$(0, 1)$};
    \node [right] at (5, 5) {$(1, 1)$};
    \draw [dashed] (0, 0) -- (5, 5);

    \node [fill, circle, inner sep=0, minimum size=3] at (1.2, 2) {};
    \node [fill, circle, inner sep=0, minimum size=3] at (2, 3.5) {};
    \node [fill, circle, inner sep=0, minimum size=3] at (3.5, 1.2) {};

    \draw [red] (1.2, 1.2) -- (1.2, 2) -- (2, 2) -- (2, 3.5) -- (3.5, 3.5) -- (3.5, 1.2) -- (1.2, 1.2);

    \draw [blue, semithick] plot [smooth] coordinates { (0, 3) (1.2, 2) (2.52, 4.2) (3.5, 1.2) (5, 0)};
  \end{tikzpicture}

We are now ready to state the desired theorem.

Theorem

Let f:[0,1][0,1]f: [0, 1] \to [0, 1] be a continuous function. If ff has a 33-periodic point, then ff has an nn-periodic point for all nn.

Let's try to understand this. A good start might be to find a fixed point, i.e. a 11-periodic point. We can achieve this using the intermediate value theorem. From now on, we fix a single continuous function ff.

Lemma

Let I[0,1]I \subseteq [0, 1] be a (closed) subinterval. If f(I)If(I) \supseteq I, then II contains a fixed point.

Proof
Write I=[a,b]I = [a, b]. Then since f(I)If(I) \supseteq I, we in particular have a,bf(I)a, b \in f(I). So we can find a,bI=[a,b]a', b' \in I = [a, b] such that f(a)=af(a') = a and f(b)=bf(b') = b. Then we have f(a)a=aa0f(a') - a' = a - a' \leq 0 and f(b)b=bb0f(b') - b' = b - b' \geq 0. Since xf(x)xx \mapsto f(x) - x is continuous, we can find some cc such that f(c)c=0f( c ) - c= 0, ie. cc is a fixed point.

So we just need to find an interval II such that f(I)If(I) \supseteq I. We suppose the three points in the 33-periodic orbit are x0<x1<x2x_0 < x_1 < x_2. We may wlog assume that f(x0)=x1f(x_0) = x_1, f(x1)=x2f(x_1) = x_2 and f(x2)=x0f(x_2) = x_0.

\begin{tikzpicture} 
    \begin{scope}[node distance=0.5cm]
      \node [fill, circle, inner sep=0, minimum size=3] at (0, 0) {};
      \node [fill, circle, inner sep=0, minimum size=3] at (2, 0) {};
      \node [fill, circle, inner sep=0, minimum size=3] at (4, 0) {};

      \node [circle, inner sep=0, minimum size=8] (a) at (0, 0) {};
      \node [circle, inner sep=0, minimum size=8] (b) at (2, 0) {};
      \node [circle, inner sep=0, minimum size=8] (c) at (4, 0) {};

      \node [above] at (0, 0) {$x_0$};
      \node [above] at (2, 0) {$x_1$};
      \node [above] at (4, 0) {$x_2$};

      \draw (a) edge [bend left, ->] (b);
      \draw (b) edge [bend left, ->] (c);
      \draw (c) edge [bend left, ->] (a);
    \end{scope}
  \end{tikzpicture}

Then f([x1,x2])f([x_1, x_2]) is a closed subinterval containing x0x_0 and x2x_2. So it in particular contains [x1,x2][x_1, x_2]. So we have found a fixed point.

How about periodic points of larger period? If we want to find an nn-periodic point, we might try to look for fixed points of fnf^ n. This is in some sense a good strategy, but it is not good enough. If we are given a fixed point fnf^ n, we know it has period at most nn. Perhaps it is secretly a fixed point of ff. So we need to be a bit more delicate than that.

We first introduce a convenient notation:

Notation

If I,J[0,1]I, J \subseteq [0, 1] are subintervals, we write IJI \to J if f(I)Jf(I) \supseteq J.

We have seen that if III \to I, then II contains a fixed point of ff. The following is the desired strengthening of the lemma.

Theorem

If I0I1I2In1I0I_0 \to I_1 \to I_2 \to \cdots \to I_{n-1} \to I_0, then there exists an xI0x \in I_0 such that fk(x)Ikf^ k(x) \in I_ k for k=1,,n1k = 1, \ldots , n-1 and fn(x)=xf^ n(x) = x.

This is trivial if we don't require fk(x)Ikf^ k(x) \in I_ k, since fn(I)If^ n(I) \supseteq I, and we can apply the lemma. The (slightly) hard part is getting the points to lie in the IkI_ k.

Proof

Note that if I,J[0,1]I, J \subseteq [0, 1] are closed subintervals with f(I)Jf(I) \supseteq J, then f1(J)f^{-1}(J) is a disjoint union of closed intervals contained in II, each of which has image JJ. By picking one of these, we get a subinterval KIK \subseteq I such that f(K)=Jf(K) = J.

Now if I0I1I2In1I0I_0 \to I_1 \to I_2 \to \cdots \to I_{n - 1} \to I_0, then we can find some Jn1In1J_{n - 1} \subseteq I_{n-1} such that f(Jn1)=I0f(J_{n-1}) = I_0. We still have f(In2)Jn1f(I_{n-2}) \supseteq J_{n-1}, so we have a sequence

I0I1I2In2Jn1I0. I_0 \to I_1 \to I_2 \to \cdots \to I_{n-2} \to J_{n-1} \to I_0.

We can now replace In2I_{n-2} with a Jn2J_{n-2} as above, and keep going on to obtain a new sequence

J0J1J2Jn2Jn1I0. J_0 \to J_1 \to J_2 \to \cdots \to J_{n-2} \to J_{n-1} \to I_0.

such that JkIkJ_ k \subseteq I_ k, and f(Jk)=Jk+1f(J_ k) = J_{k+1} for all kk. Then since fn(J0)=I0J0f^ n(J_0) = I_0 \supseteq J_0, it follows that we can find some xJ0x \in J_0 such that fn(x)=xf^ n(x) = x. By assumption, fk(x)JkIkf^ k(x) \in J_ k \subseteq I_ k. So we are done.

We are essentially done with the proof. We set I1=[x0,x1]I_1 = [x_0, x_1] and I2=[x1,x2]I_2 = [x_1, x_2]. Then we have I2I2I_2 \to I_2, I1I2I_1 \to I_2 and I2I1I_2 \to I_1. If we feel like drawing diagrams, we can draw it as

\begin{tikzpicture} 
    \node (a) at (0, 0) {$I_1$};
    \node (b) at (2, 0) {$I_2$};

    \draw (a) edge [bend left, ->] (b);
    \draw (b) edge [bend left, ->] (a);

    \draw (b) edge [loop right, ->, looseness=20] (b);
  \end{tikzpicture}

Now we have a sequence of the form

I1I2I2I2I1 I_1 \to I_2 \to I_2 \to \cdots \to I_2 \to I_1

for any number of copies of I2I_2. So for each nn, we get some xI1x \in I_1 such that fn(x)=xf^ n(x) = x, and crucially, fk(x)I2f^ k(x) \in I_2 for all 0<k<n0 < k < n. To see that xx is actually of period nn, we need to check that fk(x)̸=xf^ k(x) \not= x for 0<k<n0 < k < n. To do so, we simply have to note that I1I2={x1}I_1 \cap I_2 = \{ x_1\} . Thus if fk(x)=xf^ k(x) = x for some kk, then xx must be x1x_1. We can check manually that x1x_1 does not satisfy the required property, since f2(x1)=x0̸I2f^2(x_1) = x_0 \not\in I_2. This concludes the proof.

This result is a special case of a more general theorem called Sharkovskii's theorem. The statement is as follows:

Theorem

Define an ordering on the naturals by

3572325272232252272322211 \begin{array}{cccccccc} 3 & \rhd & 5 & \rhd & 7 & \rhd & \cdots & \rhd \\ 2\cdot 3 & \rhd & 2 \cdot 5 & \rhd & 2 \cdot 7 & \rhd & \cdots & \rhd \\ 2^2\cdot 3 & \rhd & 2^2 \cdot 5 & \rhd & 2^2 \cdot 7 & \rhd & \cdots & \rhd \\ \vdots & & \vdots & & \vdots & & \cdots & \rhd \\ 2^3 & \rhd & 2^2 & \rhd & 2^1 & \rhd & 1 \end{array}

Then if f:[0,1][0,1]f: [0, 1] \to [0, 1] has an nn-periodic point and nmn \rhd m, then there is an mm-periodic point.

One way to prove this is to use adapt the above strategy with some clever choices of the intervals involved.

As a concluding remark, recall that we led ourselves into looking at periodic points when we tried to understand the limiting behaviour as we keep iterating ff. In the first two examples, the fixed point and the 22-periodic points were stable, namely if we start somewhere near the periodic points and keep applying ff, the point converges towards the fixed point or cycle. In general, there is no reason to believe that the periodic points given by our theorem will be stable. This makes it slightly less interesting — there is no way we can "naturally" discover these periodic points as we did at the beginning. We must have started at exactly the periodic point to discover the periodicity.