Sharkovsky ordering

The Sharkovsky ordering describes the coexistence of cycles with different periods for discrete-time dynamical systems given by maps \\( f: I \to I\ ,\\) where \\(I\\) is an interval in the real line \\(\mathbb{R}\ ,\\) and, possibly \\(I=\mathbb{R}\ .\\) One can also say that it provides a forcing relation for the existence of cycles of certain periods due to the presence of a cycle of another period.

The Sharkovsky ordering is the following ordering of natural numbers \\[\tag{1} 1 \prec 2 \prec 2^2 \prec 2^3 \prec \dots \prec ~2^n~ \prec \dots \quad \dots \prec ~7 \cdot 2^n~ \prec ~5 \cdot 2^n~ \prec ~3 \cdot 2^n~ \prec \dots \\]

\\[ ~\qquad \qquad \qquad \qquad~~~\dots \prec ~7 \cdot 2~ \prec ~5 \cdot 2~ \prec ~3 \cdot 2~ \prec \dots \prec ~9~ \prec ~7~ \prec ~5~ \prec ~3~. \\]

## Contents

* 1 Sharkovsky theorem
* 2 Proofs of Sharkovsky theorem
* 3 History
* 4 Generalizations
* 5 References
* 6 See also

## [edit] Sharkovsky theorem

Let \\(f^n\ ,\\) \\(n \ge 1\ ,\\) denote the \\(n\\)-th iterate of \\(f\ ,\\) i.e., \\(f^n = f \circ f^{n-1}\ ,\\) where \\(f^0\\) is the identity map. The point \\(x \in I\\) is a periodic point of (least) period \\(m ~(m \ge 1)\\) for \\(f\ ,\\) if \\(f^m (x) = x\\) and \\(f^n (x) \not= x\\) for any \\(1 \le n < m\ .\\) In this case, the points \\(x, f(x), \ldots, f^{m-1}(x)\\) form a "periodic orbit", usually called a "cycle" of period \\(m\ .\\)

The ordering (1) defines a forcing relation for continuous, one-dimensional maps:

Theorem * (Sharkovsky 1964) If a continuous map of an interval into itself has a cycle of period \\(m\ ,\\) then it has a cycle of any period \\({\tilde m} ~\prec~ m\ .\\) Moreover, for any \\(m\\) there exists a continuous map that has a cycle of period \\(m\\) but does not have cycles of periods \\({\overline m}\ ,\\) \\(m ~\prec~ {\overline m}\ .\\)

This theorem also shows how cycles of different periods can be arranged on \\(I\ .\\) If \\(B\\) is a cycle, let \\(S(B)\\) be the interval \\([\min \\{x \in B\\}, \max \\{x \in B\\}]\ ,\\) referred to as the support of the cycle. If \\(m\\) is the period of the cycle \\(B\\) and \\({\tilde m}\\) is any number such that \\({\tilde m} ~\prec~ m\ ,\\) then the map \\(f\\) also has a cycle \\({\tilde B}\\) of period \\({\tilde m}\\) such that \\(S({\tilde B}) \subset S(B)\ .\\) Indeed, instead of the map \\(f\ ,\\) one can consider a continuous map \\(f_B\\) that coincides with \\(f\\) on \\(S(B)\\) and equals const outside the interval \\(S(B)\ .\\) The theorem remains true for \\(f_B\ ,\\) in particular, \\(f_B\\) has cycles of period \\({\tilde m}\ ,\\) but all cycles of \\(f_B\\) are in \\(S(B)\ .\\)

The ordering (1) can be interpreted in terms of stratification (Block, Coppel 1992). Let \\(C(I,I)\\) denote the set of all continuous maps of \\(I\\) into itself and \\({\mathbb P}_n\\) be the subset of \\(C(I,I)\\) consisting of maps which have cycles of period \\(n\ .\\) According to (1), if \\(m ~\prec~ {\overline m}\\) then \\({\mathbb P}_m \supset {\mathbb P}_{\overline m}\ .\\) Hence, \\({\mathbb P}_1 \supset {\mathbb P}_2 \supset {\mathbb P}_4 \supset ... \supset {\mathbb P}_5 \supset {\mathbb P}_3\ .\\)

Figure 1: The bifurcation diagram for the logistic family of maps \\(x \mapsto \lambda x(1-x), ~x \in [0,1]\ .\\)

The ordering (1) has a property of stability (Block 1981): if \\(f\\) has a cycle of period \\(m\ ,\\) then there exists \\(\varepsilon > 0\\) such that whatever \\({\tilde m} ~\prec~ m\ ,\\) any map \\({\tilde f}\,: \sup_{x \in I} |{\tilde f}(x) - f(x)| < \varepsilon\\) has a cycle of period \\({\tilde m}\ .\\)

The following important corollary of the theorem relates to bifurcation theory: if the map \\(f\\) depends on a parameter, the ordering (1) also gives a universal ordering for the birth of cycles of new periods when this parameter varies. For example, the bifurcation diagram for the logistic family of maps \\[\tag{2} x \mapsto \lambda x(1-x) \;, \\]

shown in Figure 1, displays the birth of attracting cycles whose periods are ordered according to (1), when \\(\lambda\\) increases from 2.9 up to 4. At first, there is an attracting cycle of period 1 (fixed point), at \\(\lambda = 3\\) an attracting cycle of period 2 is created, later period \\(2^2\ ,\\) period \\(2^3\\) cycles, etc. appear; a period 3 cycle first appears when \\(\lambda = 1 + 2 \sqrt 2 \approx 3.83\ .\\) If \\(\lambda_{n}\\) denotes the parameter value corresponding to the birth of the first cycle of period \\(2^{n}\ ,\\) then, as noticed by Feigenbaum, Coullet, and Tresser, \\[ \delta_{n} = (\lambda_{n}-\lambda_{n-1})/(\lambda_{n+1}-\lambda_{n}) \rightarrow \delta = 4.66920... \qquad {\rm as}~~~ n \rightarrow \infty, \\] that is, the rate of appearance of cycles of double periods is characterized by the number \\(\delta\\) which is often called the Feigenbaum constant. It turns out that not only the sequence of bifurcations, defined by (1), but also the rate of bifurcations, defined by the constant \\(\delta\ ,\\) are "universal" in the sense that they are valid for the whole class of differentiable maps (and not only the logistic family).

There are maps having only cycles of periods \\(2^n, ~n=0,1,2,...\ ;\\) an example is the logistic map (2) with \\(\lambda = \lambda^* = \lim_{n \to \infty} \lambda_{n} \approx 3.57\ ,\\) which is the limit of maps having cycles of periods \\(2^n,~n < \infty,\\) only ( Figure 1). Maps of this kind are called maps of the type \\(2^\infty\ ;\\) the first example of such a (non-smooth) map was probably given by Sharkovsky (1965). Sometimes the ordering (1) of natural numbers is supplemented with the symbol \\(2^\infty\ ,\\) inserted after all numbers of the form \\(2^n\\) and before the numbers \\(\not= 2^n\ .\\)

## [edit] Proofs of Sharkovsky theorem

The proof of the theorem is based on the intermediate value theorem and actually uses only the fact that if \\(f\\) is a continuous map and \\(J\\) is an interval such that \\(f(J) \supset J\\) then on \\(J\\) there exists a fixed point of the map \\(f\ .\\)

Since the end of 1970's, there have been published many papers with various proofs of the theorem or its parts, as well as proofs of the theorem for special classes of maps. All these can be divided into three directions:

1. Improvement of the original proof (see, for example, Du 2004, Du 2007).
2. Proofs using the graph of admissible transitions (see below).
3. Proofs using kneading theory (for unimodal maps, i.e., maps with unique extremum point).

The most transparent and elegant proof of the theorem is probably the one based on the transition graph.

To every cycle \\(B\\) there are

* a cyclic permutation \\(\pi(B)\ ,\\)
* a transition matrix \\(\mu(B)\\) and/or
* a directed graph of admissible transitions \\(G(B)\ .\\)

Each one of these is convenient in different situations, and each one provides a lot of information about dynamical systems as a whole. If cycle \\(B\\) consists of points \\(b_1 < b_2 < ... < b_m\\) and \\(f(b_i) = b _{s_i}, ~1 \leq s_i \leq m, ~i = 1, ..., m\ ,\\) then \\[ \pi = \left( \begin{array}{cccc} 1&2&...&m \\\ s_1&s_2&...&s_m \end{array}\right). \\] On the intervals \\(\Im_i = [b_i,b_{i+1}], ~i = 1,...,m-1\ ,\\) the map \\(f\\) being continuous has the property \\[ f(\Im_i) \supset \left\\{\begin{array}{ccc} \Im_{s_i} \cup ...\cup \Im_{s_{i+1}-1}, &\mbox{if}& s_i < s_{i+1}, \\\ \Im_{s_{i+1}} \cup ...\cup \Im_{s_{i}-1}, &\mbox{if}& s_i > s_{i+1}. \end{array}\right. \\] In addition, if \\(f(\Im_i) \supset\Im_s\ ,\\) then the interval \\(\Im_i\\) is said to cover (\\(f\\)-cover) the interval \\(\Im_{s}\ .\\)

To each cycle \\(B\\) we obtain the matrix of admissible transitions (points of intervals \\(\Im_i\\)) \\(\mu(B) = \\{\mu_{is}\\}\ ,\\) where \\[ \mu_{is} = \left\\{\begin{array}{ccc} 0, &\mbox{if}& f(\Im_i)\not \supset\Im_s, \\\ 1, &\mbox{if}& f(\Im_i) \supset\Im_s, \end{array}\right. \\] and the directed graph of transitions with vertices \\(\Im_1,..., \Im_{m-1}\\) and directed edges defined by the rule: an edge connects \\(\Im_i\\) and \\(\Im_s\\) if \\(f(\Im_i) \supset\Im_s\ .\\) It is convenient to write \\(\Im_i \to \Im_s\\) when \\(f(\Im_i)\supset\Im_s\\) (i.e., \\(\Im_i\\) \\(f\\)-covers \\(\Im_s\\)).

The map in Fig.2 has a cycle of period 3, that consists of the points \\(b_1, b_2, b_3\ .\\) For this cycle, \\(\pi = \left( \begin{array}{ccc} 1&2&3 \\\ 2&3&1 \end{array}\right)\\) and \\(f(\Im_1) \supset \Im_2, f(\Im_2)\supset\Im_1 \cup \Im_2\ ,\\) so that the transition matrix has the form \\(\left( \begin{array}{cc} 0&1 \\\ 1&1 \end{array}\right)\ ,\\) and the graph of admissible transitions is as in Fig.2

Figure 2: Map having a cycle of period 3 (left) and the graph of admissible transitions responding to this cycle (right).

By analyzing the matrix or the graph of transitions, one can show the existence of cycles of various periods of the map. For example, if we use the alphabet consisting of the symbols \\(a_1,a_2, ...,a_{m-1}\ ,\\) then to each symbolic sequence \\(a_{r_1}, a_{r_2}, ...,a_{r_j},a_{r_{j+1}}, ..., 1\leq r_j\leq m-1\ ,\\) admissible by the matrix of transitions (i.e., \\(\mu _{r_jr_{j+1}} = 1\\) for \\(j = 1, 2, ...\\)), there corresponds at least one orbit going through the intervals \\(\Im_1, \Im_2, ..., \Im_{m-1}\\) in the order \\(\Im_{r_1} \to \Im_{r_2} \to ... \to \Im_{r_j} \to \Im_{r_{j+1}} \to....\\) (for any \\(j > 1\ ,\\) the set \\(\Im_{r_1 r_2 ... r_j} = f^{-1} (f^{-1} ... (f^{-1} \Im_{r_j} \cap \Im_{r_{j-1}}) \cap ... \cap \Im_{r_{2}}) \cap \Im_{r_{1}}\\) is not empty and hence each point \\(x \in \Im_{r_1 r_2 ... r_j}\\) gives rise to an orbit that visits sequentially the intervals \\(\Im_{r_1}, \Im_{r_2}, ..., \Im_{r_j}\\)). In addition, if the symbolic sequence is periodic with the least period \\(n\ ,\\) then the system has at least one cycle of period \\(n\\) (going through the intervals \\(\Im_1, \Im_2, ..., \Im_{m-1}\\) in this particular order).

For the map having a cycle of period 3 (Fig.2), the periodic sequence of transitions \\(\Im_{1} \to \Im_{2} \to \Im_{2} \to ... \to \Im_{2} \to \Im_{1}\\) of any length is admissible, hence such a map has a cycle of any period. However, the proof of the theorem in general case requests more significant efforts and it makes sense to refer, for example, to (Block, Coppel 1992, Alseda et al. 2000). The first proofs of such kind were given by Straffin (1978), Block et al. (1980), Ho and Morris (1981), and Burkart (1982).

To prove the second part of the theorem, we need only to find a map having a cycle of period \\(m\\) and not having cycles of periods \\({\tilde m}\ ,\\) \\(m ~\prec~ {\tilde m}\ .\\) To do this, we can use the map \\(g\,: x \mapsto 4x(1-x)\ ,\\) which is known to have cycles of all periods. For any value of \\(m\ ,\\) the map has a finite number of cycles of period \\(m\\) (not exceeding \\(2^m\,/\,m\\)). Out of all the cycles of period \\(m\\) let us choose the cycle \\(B_m\\) whose support \\(S(B_m)\ ,\\) i.e., the interval \\([\min \\{x \in B_m \\}, \max \\{x \in B_m \\}]\ ,\\) is of the smallest length (if there are a few cycles like this one, take any of them). Then the continuous map \\[ g_{(m)}\,: x \mapsto \left\\{\begin{array}{ccc} g(x), & x \in S(B_m), \\\ const, & x \notin S(B_m), \end{array}\right. \\] has a cycle of period \\(m\\) (namely, the cycle \\(B_m\\)) and does not have cycles of period \\({\tilde m}\ ,\\) \\(m ~\prec~ {\tilde m}\ .\\)

## [edit] History

The fact that \\(1 ~\prec~ 2\\) is merely a consequence of the intermediate value theorem in classical analysis. Even Henri Poincare used this fact to prove that a second-order ordinary differential equation has an equilibrium point in a region of the phase plane, that is bounded by a closed curve – periodic orbit of the equation.

The next step in the description of the coexistence of cycles was the proof that \\(2 ~\prec~ m\\) when \\(m>2\ .\\) From works (Leibenzon 1953, Coppel 1955, Myshkis, Lepin 1957), devoted to conditions of convergence for function sequences of the form \\(f^n(x), n=0,1,2,..., x\in I\ ,\\) it was at once evident that if a map does not have cycles of period 2, then it does not have cycles of greater periods. In (Sharkovsky 1961) it was proven that if a map has a cycle of period \\(\neq 2^{l}, l=0,1,2,...\ ,\\) then it has cycles of periods \\(2^{i}, i=0,1,2,...\ .\\)

Sharkovsky Theorem and its complete proof was published in 1964 in Ukranian Mathematical Journal (Sharkovsky 1964) in Russian (the article itself was submitted to the journal in March of 1962); the second assertion of the theorem was given in the article in the form of examples. An English translation of the paper was published in 1995 in the International Journal of Bifurcation and Chaos (Sharkovsky 1964). However, as early as 1977, the complete presentation of Sharkovsky’s (1964) results (including the fact that between any two points of a cycle there exists at least one point of a cycle of smaller period) was published in English in (Stefan 1977).

When the Sharkovsky Theorem was first published, it was reasonable to "put 3 at the head". Now, in the mathematical literature, one can find both versions, the "forward" ordering, i.e., in the form (1), and the "reverse" ordering, which begins with 3 and ends with 1. The forward ordering (1) is likely to be preferred, since it more closely resembles the standard ordering of natural numbers and since it characterizes the evolution of systems in the direction from simple to complex (at least with respect to the set of existing cycles), and not the reverse: from complex to simple.

The author was trying to popularize these results as far back as in 1960s. He made presentations on V.V.Nemitsky's seminar in Moscow State University in 1963-1964; at about the same time he described these results to L.V.Keldysh in the Steklov Mathematical Institute in Moscow.

On the 4th International Conference on Nonlinear Oscillations (Prague 1967), the author reported his results concerning the coexistence of periodic solutions for the difference equation \\(x(n+1)=f(x(n))\ .\\) However, the organizers of the conference included only the abstract of the report into the proceedings of the conference, published in 1968 (Sharkovsky 1968). The abstract could be considered as the first publication of the ordering (1) in English (!), not counting the shorter English-language abstract in (Sharkovsky 1964). Ya. Kurzweil, one of the greatest Czech mathematicians, later tried to justify the decision of the organizers pointing out that they, being for the most part mechanicians, did not understand how much this "simple" difference equation would be pertinent to the theory of oscillations.

Widespread interest (not only among mathematicians but among experts in various fields of natural science as well) in one-dimensional dynamical systems, in particular, in the coexistence of cycles have been spurred by the article of Li and Yorke (1975).

The history of studies relevant to the theorem on the coexistence of cycles is described in sufficient detail in (Alseda et al. 2000, Misiurewicz 1997).

## [edit] Generalizations

The ordering (1) has been attracting attention of many mathematicians. Not only have they suggested new versions of the proof, but also they investigated the possibility of extending the results to more complex structures (beyond cycles), to wider classes of maps (discontinuous, multi-valued, random, and so on), to different types of phase spaces (one-dimensional: circle, stars, graphs, so-called hereditary decomposable chainable continua, or even multi-dimensional and infinite-dimensional, but for a special class of maps, such as triangular, cyclic, and so on). These studies led to the appearance of a new section in the Mathematics Subject Classification of AMS, namely, the section "37E15 – Combinatorial Dynamics", in 2000.

Thus of the questions regarding possible extensions and generalizations of Sharkovsky Theorem, the first is: For which classes of maps and topological spaces do theorems similar to the one above hold?

One example of this question is a generalization to non-continuous interval maps. Recently Szuca (2003) proved that the ordering (1) holds even for (non-continuous) maps whose graphs are connected \\(G_\delta\\) sets (of the plane). Andres with colleagues (2002) suggested a multivalued version of the theorem. Kluenger (2001), Andres (2008) considered possibilities to extend the theorem on random maps.

There have also been fairly complete studies of circle maps, i.e., continuous maps of a circle to itself. The rigid rotation \\(x\rightarrow x+\alpha \mod 1\ ,\\) a classic circle map, lacks cycles of any periods when the rotation angle \\(\alpha\\) is irrational; for rational \\(\alpha=p/q\ ,\\) it has cycles of period \\(q\\) only. However, if a circle map is assumed to have cycles of different periods, then the problem of coexistence of cycles becomes worthy of attention (Efremova, Rakhmankulov 1980, Block et al. 1980, Alseda et al. 2000).

The interval and circle are one-dimensional manifolds, which could be treated as simplest connected graphs. There are theorems on coexistence of cycles of different periods for continuous maps of graphs of various types. There the ordering of periods is distinct from (1); moreover, it depends on the type of graph, see, for example, (Alseda et al. 2000, Misiurewicz 2001). This brings up the question: For which topological spaces does the ordering (1) hold? Among these spaces are, for instance, so-called "hereditary decomposable chainable continua" (Schirmer 1985, Ingram 1988, Minc, Transue 1989, Alcaraz, Sanchis 2003).

The ordering (1) is a "one-dimensional phenomenon". For any subset of the natural numbers that contains 1, there exists a continuous (analytical) map of the plane into itself, which has this subset as the set of periods of its cycles (Lisovyk 1985).

On the other hand, even in \\(R^n\\) there is a class of maps for which the ordering (1) holds; these are so-called "triangular" maps (or skewed products of one-dimensional maps) (Kloeden 1979): \\[ x_1 \mapsto f_1(x_1)~~~~~~~~~~~~~ \\] \\[ x_2 \mapsto f_2(x_1, x_2)~~~~~~~~~ \\] \\[ \ldots \\] \\[ x_n \mapsto f_n(x_1, x_2, ... , x_n). \\] Another example of special classes of continuous maps is so-called the cyclic map \\[ x_1 ~~\mapsto ~~f_1(x_2)~ \\] \\[ \ldots \\] \\[ x_{n-1} ~\mapsto ~~f_{n-1}(x_n) \\] \\[ x_n ~~\mapsto ~~f_n(x_1).~ \\] For such a map the coexistence of periods can be described too (Balibrea, Linero 2001) but in a form different from (1).

Of course, these multidimensional maps are close to one-dimensional ones in one sense or another. In (Zgliczynski 1999) is considered "direct" multidimensional but small perturbations of one-dimensional maps.

Finally, there are even infinite-dimensional dynamical systems in which the (co)existence of periodic orbits is controlled by the ordering (1). First of all, among these are dynamical systems generated by (scalar) difference equations \\(x(t+1) = f(x(t))\\) with continuous time (\\(t \in {\mathbb R}^+\\)) and also by boundary value problems reducible to such difference equations (Sharkovsky, Sivak 1994, Sharkovsky 1995, Sharkovsky et al. 2006).

The second question relevant to the generalization and extension of Sharkovsky's Theorem is the question of the coexistence of structures other than cycles, i.e., invariant sets consisting of more than one orbit (cycle) or even of infinity of orbits. An example of such a structure is a minimal set different from a cycle; in the case of the real line, these minimal sets are Cantor sets.

One can introduce the notion of period for minimal sets. The period is the least natural \\(m\\) (if it exists) such that a minimal set is portioned into \\(m\\) non-overlapping sets minimal with respect to the map \\(f^m\ ,\\) which therefore make a cycle (of sets) of period \\(m\\) with respect to the map \\(f\ .\\) The least \\(m\\) does not exist when the minimal set turns to be infinitely divisible (as the one appearing after the infinite sequence of period-doubling bifurcations). The order of coexistence for Cantor minimal sets of special types is described in (Ye 1992).

Notice that the order of coexistence for homoclinic trajectories is also similar to the ordering (1) (Fedorenko, Sharkovsky 1982).

An additional question relates to the means for describing the coexistence of cycles or sets. So far we have used the notion of period, which is characterized by a natural number. But maps can have many cycles of some fixed period \\(m\ .\\) For example, the map \\(x\rightarrow 4x(1-x)\\) has \\((2^{m}-2)/m\\) cycles of period \\(m\\) with \\(m\\) being any prime number. Hence, it makes sense to use sometimes a characteristic of a cycle more precise than just its period. In the case of the real line, we can pay attention to the relative position of cycle points on the line and hence use the cyclic permutations \\(\pi\\) mentioned above. As a result, there arises a problem of coexistence (or forcing) of cycles of different types, i.e., cyclic permutations corresponding to these cycles.

Let "\\(\hookleftarrow\\)" be the order relation defined as\\[\pi \hookleftarrow \pi'\\] if and only if every continuous map of an interval, that has a cycle of type \\(\pi'\ ,\\) also has a cycle of the type \\(\pi\ .\\) The set of all cyclic permutations with this order relation is not a linearly ordered set because the order "\\(\hookleftarrow\\)" is only a partial order (Fedorenko 1986, Baldwin 1987). For example, there are only three cyclic permutations of length 4 (and three inverse to them) \\[\pi_1 = \left( \begin{array}{cccc} 1&2&3&4\\\ 3&4&2&1 \end{array}\right)\ ,\\]  \\(\pi_2 = \left( \begin{array}{cccc} 1&2&3&4\\\ 2&3&4&1 \end{array}\right)\ ,\\)  and  \\(\pi_3 = \left( \begin{array}{cccc} 1&2&3&4\\\ 3&1&4&2 \end{array}\right)\ ,\\) and it is easy to check that \\(\pi_1 \hookleftarrow \pi_2\\) and \\(\pi_1 \hookleftarrow \pi_3\ ,\\) but \\(\pi_2, \pi_3\\) are noncomparable. Besides, the permutation \\(\pi_3\\) cannot be realized by unimodal maps. However, the order relation \\(\hookleftarrow\\) is linear on the set of cyclic permutations generated by unimodal maps. This result can be obtained, e.g., as a corollary of the linear ordering for the codes of trajectories, which used in kneading theory (Sharkovsky et al. 1997).

Notice that among various cyclic permutations of length \\(m\\) one can select so-called minimal permutations corresponding to the cycles of period \\(m\\) that are the first to appear via bifurcations (or equivalently, to the cycles of period \\(m\\) that do not cause the existence of cycles of other types but of the same period). These cycles are sometimes called minimal.

Minimal permutations of length \\(m\\) have the following form (Sharkovsky 1964, Stefan 1977) :

* When \\(m=2k+1\\)

\\[\pi_{2k+1} = \left( \begin{array}{cccccccccccc} 1&2&...&i&...&k+1&k+2&...&j&...&2k+1\\\ k+1&2k+1&...&2k+3-i&...&k+2&k&...&2k+2-j&...&1 \end{array}\right), \ :\\] and the corresponding inverse permutations;

* When \\(m=2k\ ,\\) these are permutations \\(\pi\\) for which the following inductive property holds: The sets \\(N_1 = \\{1,2,...,k\\}\\) and \\(N_2 = \\{k+1,k+2,...,2k\\}\\) are invariant with respect to \\(\pi^{2}\\) (i.e., if \\(i \in N_s\\) then also \\(\pi^2 (i) \in N_s, ~s=1,2\\)), and the restriction \\(\pi^{2}\\) on \\(N_1\\) is the minimal permutation.

If \\(\pi\\) is a minimal permutation and \\(b_1 < b_2 < ... < b_m\\) are some points on the real line, then the continuous piece-wise linear map \\(f_{\pi} :[b_1,b _{m}]\rightarrow[b _{1},b _{m}]\\) such that \\(f_{\pi}(b_i) = b _{\pi(i)}, ~i = 1, ..., m\ ,\\) and \\(f_{\pi}\\) is linear on \\([b _{i},b _{i+1}], ~i = 1, ..., m-1\ ,\\) has a cycle of period \\(m\\) (formed by the points \\(b_1,b_2, ..., b_m\\)) and does not have cycles of periods \\({\tilde m}\ ,\\) \\(m ~\prec~ {\tilde m}\ .\\)

Besides the classification of cycles with respect to periods and types, there is another classification that uses so-called rotation numbers for cycles – certain rational numbers. A variant of such a classification is the following: if \\(b_1 < b_2 < ... < b_{m}\\) are points of a cycle \\(B\\) of period \\(m\\) and exactly \\(p\\) of them are such that \\(f(b)<b\ ,\\) then the number \\(p/m\\) is referred to as the rotation number of the cycle \\(B\ .\\) Articles (Blokh, Misiurewicz 1997, Bobok, Kuchta 1998) describe the coexistence of cycles of interval map with different rotation numbers.

## [edit] References

Alcaraz, D., Sanchis, M. [2003] : A note on Sharkovskii's theorem in connected linearly ordered spaces, Intern. J. Bifurcation and Chaos 13, 1665-1671.

Alseda, L., Llibre, J., Misiurewicz, M. [2000] : "Combinatorial dynamics and entropy in dimension one", Second edition, Advanced Series in Nonlinear Dynamics, vol. 5, World Scientific, River Edge, NJ.

Andres, J. [2008] : Randomization of Sharkovskii-type theorems, Proc. Amer. Math. Soc. 136, 1385-1395.

Andres, J., Fiser, J., Juttner, L. [2002] : On a multivalued version of the Sharkovskii theorem and its application to differential inclusions, Set-Valued Anal. 10, 1-14.

Baldwin, S. [1987] : Generalizations of a theorem of Sharkovskii on orbits of continuous real-valued functions, Discrete Mathematics, 67, 111-127.

Balibrea, F., Linero, A. [2001] : Periodic structure of \\(\sigma\\)-permutation maps, Aequationes Math. 62, 265-279.

Block, L. [1981] : Stability of periodic orbits in the theorem of Sharkovskii, Proc. Amer. Math. Soc. 81, 333-336.

Block, L., Coppel, W.A. [1992] : "Dynamics in one dimension", Lecture Notes in Mathematics, Vol. 1513, Springer-Verlag, Berlin.

Block, L., Guckenheimer, J., Misiurewicz, M., and Young, L.-S. [1980] : Periodic points and topological entropy of one-dimensional maps, in "Global Theory of Dynamical Systems", Lecture Notes in Math., no. 819, Springer-Verlag, Berlin, pp. 18-34.

Blokh, A., Misiurewicz, M. [1997] : New order for periodic orbits of interval maps, Ergod. Th. Dynam. Sys. 17, no. 3, 565-574.

Bobok, J., Kuchta, M. [1998] : X-minimal patterns and a generalization of Sharkovskiı’s theorem, Fund. Math. 156, no. 1, 33-66.

Burkart, U. [1982] : Interval mapping graphs and periodic points of continuous functions, J. Combin. Theory Ser. B 32, 57-68.

Coppel, W.A. [1955] : The solution of equations by iteration, Proc. Cambridge Philos. Soc. 51, 41-43.

Du, B.-S. [2004] : A simple proof of Sharkovsky's theorem, Amer. Math. Monthly 111, 595-599.

Du, B.-S. [2007] : A simple proof of Sharkovsky's theorem revisited, Amer. Math. Monthly 114, 152-155.

Efremova, L.S., Rakhmankulov, R.G. [1980] : Theorems on the coexistence of periodic orbits of endomorphisms of the circle (in Russian), Differential and integral equations (Gor'kov. Gos. Univ., Gorki), No. 4, 116-118.

Fedorenko, V.V. [1986] : Partially ordered set of types of periodic trajectories of one-dimensional dynamical systems (in Russian), Dynamical systems and differential-difference equations (Russian), Akad. Nauk Ukrain. SSR, Inst. Mat., Kiev, 90-97.

Fedorenko, V.V., Sharkovsky, A.N. [1982] : Stability of a dynamical system's property of having a homoclinic trajectory (in Russian), Oscillation and stability of solutions of functional-differential equations (Russian), Akad. Nauk Ukrain. SSR, Inst. Mat., Kiev, 111-113.

Ingram, W.T. [1988] : Concerning periodic points in mappings of continua, Proc. Amer. Math. Soc. 104, 643-649.

Kloeden, P.E. [1979] : On Sharkovsky's cycle coexistence ordering, Bull. Austral. Math. Soc. 20, 171-177.

Kluenger, M. [2001] : Periodicity and Sharkovsky's theorem for random dynamical systems, Stochastics and Dynamics 1, No. 3, 299-338.

Leibenzon, Z.L. [1953] : Investigation of certain properties of a continuous point transformation of an interval onto itself which have application  in the theory of nonlinear oscillations (in Russian), Akad. Nauk SSSR, Prikl. Mat. Meh. 17, 351-360.

Li, T.-Y., Yorke, J.A. [1975] : Period three implies chaos, Amer. Math. Monthly 82, 985-992.

Lisovyk, L.P. [1985] : Construction of analitical transformation of Euclid space for arbitrary given system of periods (in Ukrainian), Dopovidi AN Ukrains'koi RSR, Ser. A, no.6, 10-13.

Minc P., Transue W.R.R. [1989] : Sharkovskii's theorem for hereditarily decomposable chainable continua, Trans. Amer. Math. Soc. 315, 173-188.

Misiurewicz, M. [1997] : Remarks on Sharkovsky's theorem, Amer. Math. Monthly 104, 846-847.

Misiurewicz, M. [2001] : Combinatorial Dynamics, http://www.math.iupui.edu/~mmisiure/publlist.html

Myshkis, A.D., Lepin, A.Ya. [1957] : Existence of an invariant set, consisting of two points, for certain continuos maps of an interval into itself (in Russian), Uchen. Zap. Belorus. Univ., Ser. Fiz.-Mat. 32, 29-32.

Schirmer, H. [1985] : A topologist's view of Sharkovskii's theorem, Houston Journ. Math. 11, 385-395.

Sharkovsky, A.N. [1961] : The reducibility of a continuous function of a real variable and the structure of the fixed points of the corresponding iteration process (in Russian), Dokl. Akad. Nauk SSSR 139, no.5, 1067–1070.

Sharkovsky, A.N. [1964] : Coexistence of cycles of continuous mapping of the line into itself. Ukrainian Math. J., 16, 61-71 [in Russian]; [1995] : Intern. J. Bifurcation and Chaos 5, no. 5, 1263-1273.

Sharkovsky, A.N. [1965] : On cycles and the structure of a continuous mapping, Ukrainian Math. J. 17, 1965, no. 3, 104-111 [in Russian].

Sharkovsky, A.N. [1968] : On the periodic solutions of a class of finite differences equations, in "Proceedings of the Fourth conference on nonlinear oscillations" (Prague, Sept. 5-9, 1967), Academia, CSAV, Prague, 1968, p.249.

Sharkovsky, A.N. [1995] : Universal Phenomena in some Infinite-Dimensional Dynamical Systems, Int. J. Bifurcation and Chaos 5 (5), 1419-1425, and in "Thirty years after Sharkovskii's theorem: New perspectives" (Proc. Conf.), World Scientific, 157-164.

Sharkovsky, A.N., Kolyada, S.F., Sivak, A.G., and Fedorenko, V.V. [1997] : "Dynamics of one-dimensional maps", Translated from the 1989 Russian original by A. Sivak, P. Malyshev and D. Malyshev and revised by the authors, Mathematics and its Applications, vol. 407, Kluwer Academic Publishers Group, Dordrecht.

Sharkovsky, A.N., Romanenko, E.Yu., and Fedorenko, V.V. [2006] :  One-dimensional bifurcations in some infinite-dimensional dynamical systems and ideal turbulence, Regular and Chaotic Dynamics 11 (2), 319-328.

Sharkovsky, A.N., Sivak, A.G. [1994] : Universal Phenomena in Solution Bifurcations of Some Boundary Value Problems, Nonlinear Mathematical Physics 1 (2), 147-157.

Stefan, P. [1977] : A theorem of Sharkovskii on the existence of periodic orbits of continuous endomorphisms of the real line, Comm. Math. Phys. 54, no. 3, 237-248.

Straffin, P.D., Jr. [1978] : Periodic points of continuous functions, Math. Mag. 51, 99-105.

Szuca, P. [2003] : Sharkovskii's theorem holds for some discontinuous functions, Fund. Math. 179, no. 1, 27-41.

Ye, X.D. [1992] : D-function of a minimal set and an extension of Sharkovskii's theorem to minimal sets, Ergod. Th. & Dynam. Sys. 12, 365-376.

Zgliczynski, P. [1999] : Sharkovskii's theorem for multidimensional perturbations of one-dimensional maps, Ergod. Th. & Dynam. Systems 19, no. 6, 1655-1684; Sharkovskii theorem for multidimensional perturbations of one-dimensional maps. II, Topol. Methods Nonlinear Anal. 14, no. 1, 169-182.

Internal references

* John Guckenheimer (2007) Bifurcation. Scholarpedia, 2(6):1517.

* Ian Gladwell (2008) Boundary value problem. Scholarpedia, 3(1):2853.

* Michał Misiurewicz (2007) Combinatorial dynamics. Scholarpedia, 2(10):3228.

* James Meiss (2007) Dynamical systems. Scholarpedia, 2(2):1629.

* Eugene M. Izhikevich (2007) Equilibrium. Scholarpedia, 2(10):2014.

* Jeff Moehlis, Kresimir Josic, Eric T. Shea-Brown (2006) Periodic orbit. Scholarpedia, 1(7):1358.

* Philip Holmes and Eric T. Shea-Brown (2006) Stability. Scholarpedia, 1(10):1838.

* David H. Terman and Eugene M. Izhikevich (2008) State space. Scholarpedia, 3(3):1924.

## [edit] See also

Combinatorial Dynamics, Iterated Maps, Kneading Theory, Period Doubling, Unimodal Maps