Sarkovsky’s theorem

The previous post explained what is meant by period three implies chaos. This post is a follow-on that looks at Sarkovsky's theorem, which is mostly a generalization of that theorem, but not entirely [1].

First of all, Mr. Sarkovsky is variously known Sharkovsky, Sharkovskii, etc. As with many Slavic names, his name can be anglicized multiple ways. You might use the regular expression Sh?arkovsk(ii|y) in a search.

The theorem in the previous post, by Li and Yorke, says that if a continuous function from a closed interval to itself has a point with period three, it has points with all positive periods. This was published in 1975.

Unbeknownst to Li and Yorke, and everyone else in the West at the time, Sarkovsky had published a more general result in 1964 in a Ukrainian journal. He demonstrated a total order on the positive integers so that the existence of a point with a given period implies the existence of points with all periods further down the sequence. The sequence starts with 3, and every other positive integer is in the sequence somewhere, so period 3 implies the rest.

Sarkivsky showed that period 3 implies period 5, period 5 implies period 7, period 7 implies period 9, etc. If a continuous map of an interval to itself has a point of odd period n > 1, it has points with order given by all odd numbers larger than n. That is, Sarkovsky's order starts out

3 > 5 > 7 > ...

The sequence continues

... 2*3 > 2*5 > 2*7 > ...

then

... 2^2*3 > 2^2*5 > 2^2*7 > ...

then

... 2^3*3 > 2^3*5 > 2^3*7 > ...

and so on for all powers of 2 times odd numbers greater than 1.

The sequence ends with the powers of 2 in reverse order

... 2^3 > 2^2 > 1.

Here's Python code to determine whether period m implies period n, assuming m and n are not equal.

from sympy import factorint# Return whether m comes befor n in Sarkovsky orderdef before(m, n): assert(m != n) if m == 1 or n == 1: return m > n m_factors = factorint(m) n_factors = factorint(n) m_odd = 2 not in m_factors n_odd = 2 not in n_factors m_power_of_2 = len(m_factors) == 1 and not m_odd n_power_of_2 = len(n_factors) == 1 and not n_odd if m_odd: return m < n if n_odd else True if m_power_of_2: return m > n if n_power_of_2 else False # m is even and not a power of 2 if n_odd: return False if n_power_of_2: return True if m_factors[2] < n_factors[2]: return True if m_factors[2] > n_factors[2]: return False return m < n

Next post: Can you swim upstream" in Sarkovsky's order?

[1] There are two parts to the paper of Li and Yorke. First, that period three implies all other periods. This is a very special case of Sarkovsky's theorem. But Li and Yorke also proved that period three implies an uncountable number of non-periodic points, which is not part of Sarkovsky's paper.

The post Sarkovsky's theorem first appeared on John D. Cook.