MINIMAL COMBINATORIAL MODELS FOR MAPS OF

AN INTERVAL WITH A GIVEN SET OF PERIODS

Louis Block Ethan M. Coven William Geller Kristin Hubner

Abstract. A combinatorial model for a property of continuous self-maps of a compact interval is a self map π of a finite ordered set such that every continuous π-weakly monotone self-map of a compact interval has that property. We identify the minimal combinatorial models for the property “the set of periods is a given set.” Here the word minimal refers to the number of points in the domain of the model. We also identify the minimal permutation models, and in appropriate cases, the minimal combinatorial models for properties involving “horseshoes.”

Introduction

A combinatorial model for a property of continuous self-maps of a compact interval is a self-map π of a finite ordered set such that every continuous π-weakly monotone self-map of a compact interval has the property. Not every dynamical property has a combinatorial model. For example, the property “f has a dense orbit” does not. We also consider permutation models, where we require that π be a permutation.

We consider the following two properties:

• the set of periods of f is a given set of positive integers.

• the set of periods of f is a given set of positive integers and f^{2^{k}} does not have a horseshoe. (Horseshoe is defined in Section 1.)

We show that for every set, other than the set of all powers of 2, which is the set of periods of some continuous self-map of a compact interval, both properties have combinatorial models. For the properties above, we characterize the minimal combinatorial models and the minimal permutation models, where minimal refers

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 37E15; Secondary 37E05.

Some of the results in this paper first appeared in the 1994 Wesleyan University Ph.D. thesis of the fourth author; some were proved in 1998 while the second and third authors were members of MSRI, where research was supported by NSF grant DMS-970155; and some were proved in 1998-99 while the first author was Van Vleck Visiting Professor of Mathematics at Wesleyan University.

to the cardinality of the domain of π, denoted #π. It turns out that either every minimal combinatorial model is a permutation or none are.

Suppose that π : P → P is a self-map of a finite ordered set P = {p_{1} < p_{2} < ⋯ < p_{n}} and f : I → I is a self-map of a compact interval. f is π-weakly monotone iff (here, and throughout the paper, we use iff for if and only if in definitions) there exist x_{1} < x_{2} < ⋯ < x_{n} in I such that I = [x_{1}, x_{n}], f(x_{i}) = x_{j} if π(p_{i}) = p_{j}, and f is weakly (i.e., not necessarily strictly) monotone on every subinterval [x_{i}, x_{i+1}].

We will show, in Theorems 1.7 and 2.3, that for each of the properties that we are considering, whether a continuous, π-weakly monotone map has the property depends only on π, and not on the map.

Let Per(f) denote the set of (least) periods of the points in the domain of f, and let <_{S} (Sharkovskiĭ-less than) be the Sharkovskiĭ order on the positive integers, defined in Section 1. It follows from the Theorem of Sharkovskiĭ, stated in Section 1, that Per(f) is of one of the following:

(1) {t : t ≤_{S} 2^{k}} for some k ≥ 0.

(2) {t : t is a power of 2}.

(3) {t : t ≤_{S} 3 · 2^{k}} for some k ≥ 0.

(4) {t : t ≤_{S} n · 2^{k}} for some k ≥ 0, and some odd n ≥ 5.

We will use the term simple cycle, which we define in Section 1 for cycles of length a power of 2, and in Section 5 for cycles of other lengths. Our usage corresponds to the usage of the term simple in [ALM] and to the usage of the term strongly simple in [BCop].

In Section 1, we define the Markov graph of a self-map of a finite ordered set and prove the following.

Theorem 1.7. Let π be a self-map of a finite ordered set. Then every continuous, π-weakly monotone map has the same set of periods.

In light of Theorem 1.7, we define the set of periods of π, Per(π), to be the set of periods of any continuous, π-weakly monotone map.

Theorem 1.8. Let π be a self-map of a finite ordered set. Then every period of π is the length of a subcycle of π or is the length of a primitive closed walk in the Markov graph of π. Conversely, every such number is a period of π.

Theorem 1.9. The minimal combinatorial models for “Per(f) = {t : t ≤_{S} 2^{k}}” are the simple cycles of length 2^{k}.

We also show that there is no continuous, π-weakly monotone self-map of a compact interval for which the set of periods is the set of all powers of 2 (Theorem 1.4).

In Section 2, we show that if the k-th power of some continuous, π-weakly monotone map has a horseshoe, then so does the k-th power of every continuous, π-weakly monotone map. This can be seen in the Markov graph of π, and we say that the k-th power of the Markov graph of π has a horseshoe. We remind the reader that if f is continuous and π-weakly monotone, then f^{k} need not be π^{k}-weakly monotone. Thus the terminology “π^{k} has a horseshoe” would not be appropriate in this case.

In Section 3, we define reduction- and restriction-minimal, using the concept of block structure [MN]. We prove that minimal combinatorial models for the properties under consideration must be reduction- and restriction-minimal. The following result, proved in Section 4, is a crucial step in characterizing minimal combinatorial models.

Theorem 4.3. Suppose that π is a reduction- and restriction-minimal self-map of a finite ordered set, such that Per(π) is not a subset of the powers of 2, and such that the 2^{k}-th power of the Markov graph of π does not have a horseshoe. Then π has a block structure over a simple cycle of length 2^{k}.

Theorem 5.2. The minimal combinatorial models for “Per(f) = {t : t ≤_{S} 3 · 2^{k}} and f^{2^{k}} does not have a horseshoe” are the simple cycles of length 3 · 2^{k}.

We also give necessary and sufficient conditions for π to be a minimal permutation model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}” (Theorem 5.3). In this case, #π = 3 · 2^{k}, but π need not be a cycle. Finally, we give necessary and sufficient conditions for π to be a minimal combinatorial model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}.” In this case, if k ≥ 1, then #π = 3 · 2^{k−1} + 1 and π is not a permutation.

In Section 6, we prove out last main result.

Theorem 6.1. Suppose that r ≥ 5 is odd. Then the minimal combinatorial models for “Per(f) = {t : t ≤_{S} r · 2^{k}}” are the simple cycles of length r · 2^{k}.

This implies, for example, that if f is continuous, π-weakly monotone, and Per(f) = {t : t ≤_{S} 1, 000, 000}, then #π ≥ 1, 000, 000.

We conclude the paper with a brief discussion of unimodal minimal combinatorial models in Section 7.

An informal way to summarize some of the conclusions of this paper is the following. For the property that the set of periods is a given set, the only way to obtain a minimal combinatorial model which is not a simple cycle is to create an appropriate horseshoe. In particular, this is possible if and only if the Sharkovskiĭ-largest member of the given set is 3 · 2^{k} for some k ≥ 0. The “turbulence stratification” [BCop, p. 34] is relevant here.

1. Periods, subcycles, and closed walks

Let π : P → P be a self-map of a finite ordered set. We will write #π for the cardinality of P.

Definition. Let π : P → P, where P = {p_{1} < p_{2} < ⋯ < p_{n}}. The Markov graph of π, is a directed graph, with n − 1 vertices, V_{1}, V_{2}, …, V_{n−1}, and an arc from V_{i} to V_{j}, written V_{i} → V_{j}, iff either π(p_{i}) ≤ p_{j} and π(p_{i+1}) ≥ p_{j+1}, or π(p_{i}) ≥ p_{j+1} and π(p_{i+1}) ≤ p_{j}.

Definition. Let π : P → P, where P = {p_{1} < p_{2} < ⋯ < p_{n}}, and let f : I → I be a self-map of a compact interval. We say that f is π-weakly monotone iff there is a subset Z_{π} = {z_{1} < z_{2} < ⋯ < z_{n}} of I such that I = [z_{1}, z_{n}], f(z_{i}) = z_{j} if and only if π(p_{i}) = p_{j}, and f is weakly (i.e., not necessarily strictly) monotone on each subinterval [z_{i}, z_{i+1}] of I. We call Z_{π} a π-set, its members π-points, and the intervals [z_{i}, z_{i+1}] π-intervals.

We remind the reader that a continuous, piecewise weakly monotone self-map f : I → I of a compact interval has finitely many turning points and finitely many turning intervals. (A turning point is a point x ∈ I such that either f(x − ϵ), f(x + ϵ) > f(x) for all small ϵ > 0, or f(x−ϵ), f(x+ϵ) < f(x) for all small ϵ > 0. A turning interval is a nondegenerate subinterval, J = [a, b] of I, such that f(J) is one point, and either f(a − ϵ), f(b + ϵ) > f(J) for all small ϵ > 0, or f(a − ϵ), f(b + ϵ) < f(J) for all small ϵ > 0.)

Remark. If f is continuous and π-weakly monotone, then every turning point is a π-point and every turning interval contains a π-point.

Definition. Let π : P → P, where P = {p_{1} < p_{2} < ⋯ < p_{n}}. p_{k} is a turning point of π iff k ≠ 1, n, and either π(p_{k}) < π(p_{k−1}), π(p_{k+1}) or π(p_{k}) > π(p_{k−1}), π(p_{k+1}).

Definition. Let π : P → P, where P = {p_{1} < p_{2} < ⋯ < p_{n}}. The canonical π-linear map is L_{π} : [1, n] → [1, n], where Z_{π} = {1, 2, …, n}, L_{π}(i) = j if π(p_{i}) = p_{j}, and L_{π} is linear on each π-interval [i, i + 1].

Remark. p_{k} is a turning point of π if and only if k is a turning point of L_{π}.

Lemma 1.1. Let π : P → P, where P = {p_{1} < p_{2} < ⋯ < p_{n}}. The following statements are equivalent.

(1) There is an arc in the Markov graph of π from V_{i} to V_{j}.

(2) For some continuous π-weakly monotone map f with π-set Z_{π}, f[z_{i}, z_{i+1}] ⊇ [z_{j}, z_{j+1}].

(3) For every continuous map f with π-set Z_{π}, f[z_{i}, z_{i+1}] ⊇ [z_{j}, z_{j+1}].

(4) For some continuous π-weakly monotone map f with π-set Z_{π}, there exists x ∈ (z_{i}, z_{i+1}) such that f(x) ∈ (z_{j}, z_{j+1}).

(5) For every continuous π-weakly monotone map f with π-set Z_{π}, there exists x ∈ (z_{i}, z_{i+1}) such that f(x) ∈ (z_{j}, z_{j+1}).

Remark. The condition “f[z_{i}, z_{i+1}] ⊇ [z_{j}, z_{j+1}]” is sometimes called “[z_{i}, z_{i+1}] f-covers [z_{j}, z_{j+1}].”

We use exponentiation of maps to denote iterated composition. Thus π^{2} = π ∘π, f^{2} = f ∘ f, etc. For f : I → I, x ∈ I, and n ≥ 1, we say that x is periodic, or f-periodic, of period n iff f^{n}(x) = x, and f^{m}(x) ≠ x for 1 ≤ m < n. We let Per(f) denote the set of n ≥ 1 such that there exists x ∈ I of period n, and call it the set of periods of f.

A closed walk in a directed graph is called primitive iff it is not a shorter closed walk traversed several times. For example, V_{1} → V_{1} → V_{2} → V_{1} is primitive, whereas V_{1} → V_{2} → V_{1} → V_{2} → V_{1} is not.

Let V_{i_{0}} → V_{i_{1}} → ⋯ → V_{i_{t−1}} → V_{i_{0}} be a closed walk of length t in the Markov graph of π, and let f : I → I be continuous and π-weakly monotone, with π-set Z_{π}. A fixed point x of f^{t} follows the walk iff f^{k}(x) ∈ [z_{i_{k}}, z_{i_{k}+1}] for k = 0, 1, …, t − 1. Note that x need not have period t.

Lemma 1.2. Let π : P → P be a self-map of a finite ordered set, and let f : I → I be continuous and π-weakly monotone, with π-set Z_{π}. Suppose that x ∉ Z_{π} is periodic of period n. Then x follows a closed walk of length n which is either primitive, or a primitive closed walk traversed twice.

Proof. Since no point of the orbit of x is in Z_{π}, x follows a unique closed walk by Lemma 1.1. Suppose that the walk is not primitive, say V_{i_{0}} → V_{i_{1}} → ⋯ → V_{i_{t−1}} → V_{i_{0}}, traversed m ≥ 2 times. Then for k = 0, 1, …, t − 1,

{f^{k}(x), f^{k+t}(x), …, f^{k+(m−1)t}(x)} ⊆ [z_{i_{k}}, z_{i_{k}+1}].

Therefore f is weakly monotone on these finite sets, and hence f^{t} is weakly monotone on {x, f^{t}(x), …, f^{(m−1)t}(x)}. But this set is a periodic orbit of f^{t}. Therefore m = 2. □

Lemma 1.3. Let π : P → P be a self-map of a finite ordered set, and let f : I → I be continuous and π-weakly monotone. Suppose that the Markov graph of π contains a primitive closed walk of length n. Then f has a periodic point of period n or n/2.

Proof. Let Z_{π} = {z_{i}} be a π-set, and let V_{i_{0}} → V_{i_{1}} → ⋯ → V_{i_{n−1}} → V_{i_{0}} be a primitive closed walk. By [BCop, Lemma I.4] there is a fixed point x of f^{n} which follows the walk.

Suppose that x ∈ (z_{i_{0}}, z_{i_{0}+1}). Then f^{k}(x) ∈ (z_{i_{k}}, z_{i_{k}+1}) for 0 ≤ k ≤ n − 1. If the period of x were less than n, the walk would not be primitive.

Suppose that x = z_{i_{0}} or z_{i_{0}+1}. Then [z_{i_{1}}, z_{i_{1}+1}] is the unique π-interval with one endpoint f(x) such that there is an arc from V_{i_{0}} to V_{i_{1}}. Similarly, for k = 2, 3, …, n − 1, [z_{i_{k}}, z_{i_{k}+1}] is the unique π-interval with one endpoint f^{k}(x) such that there is an arc from V_{i_{k−1}} to V_{i_{k}}.

Suppose that the period of x is m. If V_{i_{m}} = V_{i_{0}}, then V_{i_{m}+1} = V_{i_{1}}, etc. Since the walk is primitive, m = n. If V_{i_{m}} ≠ V_{i_{0}}, then [z_{i_{m}}, z_{i_{m}+1}] and [z_{i_{0}}, z_{i_{0}+1}] are the distinct π-intervals with common endpoint x. Then V_{i_{2m}} = V_{i_{0}} and m = n/2. □

The Sharkovskiĭ order, <_{S}, on the positive integers is

1 <_{S} 2 <_{S} 2^{2} <_{S} 2^{3} <_{S} ⋯ <_{S} 2^{2} · 7 <_{S} 2^{2} · 5 <_{S} 2^{2} · 3 <_{S} ⋯
⋯ <_{S} 2 · 7 <_{S} 2 · 5 <_{S} 2 · 3 <_{S} ⋯ <_{S} 7 <_{S} 5 <_{S} 3.

Formally, if r and s are odd, then 2^{k}r <_{S} 2^{ℓ}s iff (1) k < ℓ and r = s = 1, or (2) r = 1 and s > 1, or (3) k = ℓ and 1 < s < r, or (4) k > ℓ and r, s > 1.

Sharkovskiĭ’s Theorem ([ALM],[BCop]) states that for every continuous selfmap f of a compact interval, if n is a period of some point in the domain of f and if k <_{S} n, then k is also a period of some point in the domain of f. In symbols, if n ∈ Per(f), then Per(f) ⊇ {k : k ≤_{S} n}. In particular, if the set of periods of f is not the set of all the powers of 2, then it is determined by its Sharkovskiĭ-largest member.

Theorem 1.4. There is no continuous, π-weakly monotone self-map of a compact interval such that the set of periods is the set of all powers of 2.

Proof. Let π : P → P be a self-map of a finite ordered set, and suppose there were such a map f. For every subcycle of π, there is an f-periodic point whose period is the length of that subcycle. Therefore, the length of every subcycle of π is a power of 2. Let 2^{k} ≥ #π. Since f has a periodic point of period 2^{k+1}, by Lemma 1.2 there is a primitive closed walk of length 2^{k} or 2^{k+1} in the Markov graph of π. Since the graph has #π − 1 vertices, this walk must pass through the same vertex twice. Therefore, there are distinct closed walks starting at the same vertex. Going around one of these walks once and around another one twice gives a closed walk of length not a power of 2. The resulting walk is either primitive or it is a primitive closed walk of length not a power of 2, traversed several times. Then, by Lemma 1.3, f has a periodic point of period not a power of 2. □

Definition. f : I → I has a horseshoe iff there exist subintervals J and K of I, with at most one point in common, such that f(J), f(K) ⊇ J ∪ K.

It is well-known, [BCop, Lemma II.3], that if a continuous self-map of a compact interval has a horseshoe, then it has a periodic point of period 3. We remark that a map which has a horseshoe is said to be turbulent in [BCop] and is said to have a 2-horseshoe in [ALM].

Lemma 1.5. Suppose that f is continuous and π-weakly monotone, and that the Sharkovskiĭ-largest period of the periodic points of f is 2. Then π has a subcycle of length 2.

Proof. Suppose that all the subcycles of π have length 1. Let {v, w} be a periodic orbit of period 2. Without loss of generality, v < w. Then both v and w are in the interiors of π-intervals. Let a be the left endpoint of the π-interval containing v, and let d be the right endpoint of the π-interval containing w. If there is at least one π-point between v and w, let b be the right endpoint of the π-interval containing v, and let c be the left endpoint of the π-interval containing w. If not, let b = c be the unique fixed point of f between v and w. Then a < b ≤ c < d, f[a, b] ⊇ [c, d], and f[c, d] ⊇ [a, b]. It follows that f^{k}[a, b] ⊇ [a, b] for all even k, and that for some even k, f^{k}(a) is a fixed point of f .

Write x = f^{k}(a). Then x ≤ a or x ≥ b.

Suppose first that x ≤ a. Since k + 1 is odd, f^{k+1}[a, b] ⊇ [x, d]. Therefore f^{k+1}[a, b] ⊇ [a, b], f^{k+1}[a, b] ⊇ [c, d] and f^{k+1}[c, d] ⊇ [a, b]. Thus [a, b] and [c, d] exhibit a horseshoe for f^{2k+2}. Then 3 ∈ Per(f^{2k+2}) and so 2 is not the Sharkovskiĭ-largest period of f.

Suppose then that x ≥ b. Then there is a point y with a < y < x, such that f^{k}(y) = a. (For if x > b, then there exists y, a < y ≤ b, such that f^{k}(y) = a; then y < x. If x = b, then f^{k}(b) = b, so there exists y < b = x such that f^{k}(y) = a.) But then [a, y] and [y, x] exhibit a horseshoe for f^{k}. As above, 2 is not the Sharkovskiĭ-largest period of f. □

Theorem 1.6. Suppose that π is a self-map of a finite ordered set, and that f is a continuous and π-weakly monotone map. If the Sharkovskiĭ-largest period of f is a power of 2, then π has a subcycle of that length.

Proof. Suppose that π : P → P. We prove by induction on k that if f : I → I is continuous and π-weakly monotone, and if the Sharkovskiĭ-largest period of f is 2^{k}, then π has a subcycle of length 2^{k}.

Suppose that k = 0. Since the length of every subcycle of π is also the period of some periodic orbit of f, it follows that π has no subcycles of length other than 1, and hence has a subcycle of length 1.

The result is true for k = 1 by Lemma 1.5. Suppose that k ≥ 1 and that the result is true for k; we prove it for k + 1. Let Z_{π} be a π-set for f. Define θ : Q → Q as follows. Let Q be the union of Z_{π} and the set of endpoints of the connected components of f^{−1}(Z_{π}), and let θ = f^{2}|_{Q}. Then f^{2} is θ-weakly monotone. We have Per(f) = {1, 2, …, 2^{k+1}} and Per(f^{2}) = {1, 2, …, 2^{k}}. By the inductive hypothesis, θ has a subcycle of length 2^{k}. Because θ(Q) ⊆ Z_{π}, this subcycle is contained in Z_{π}. Hence π^{2} has a subcycle of length 2^{k}. Since k ≥ 1, 2^{k} is even, and so π has a subcycle of length 2^{k+1}. □

Theorem 1.7. Let π be a self-map of a finite ordered set. Then every continuous, π-weakly monotone map has the same set of periods.

Proof. Let f be continuous and π-weakly monotone. By Theorem 1.4, it suffices to show that (1) and (2) hold.

(1) If every subcycle of π and every primitive closed walk in the Markov graph of π have length a power of 2, then the Sharkovskiĭ-largest period of f is the length of the Sharkovskiĭ-longest subcycle of π.

(2) If some subcycle of π or some primitive closed walk in the Markov graph of π has length not a power of 2, then the Sharkovskiĭ-largest period of f is the Sharkovskiĭ-largest of the following two numbers: the Sharkovskiĭ-longest subcycle of π and the length of the Sharkovskiĭ-longest primitive closed walk in the Markov graph of π.

(1) By Lemma 1.2, the Sharkovskiĭ-largest period of f is a power of 2. By Theorem 1.6, the Sharkovskiĭ-largest period of f is the length of the Sharkovskiĭ-longest subcycle of π.

(2) Consider the lengths of the Sharkovskiĭ-longest subcycle of π and of the Sharkovskiĭ-longest primitive closed walk in the Markov graph of π. By Lemma 1.2, the Sharkovskiĭ-largest period of f is Sharkovskiĭ-less than or equal to one of these numbers. By Lemma 1.3, the Sharkovskiĭ-largest period of f is Sharkovskiĭ-greater than or equal to both of them. □

In light of Theorem 1.7, we introduce the the following notation and terminology.

Notation. For π a self-map of a finite ordered set, Per(π), called the set of periods of π, is the set of periods of any (equivalently, every) continuous, π-weakly monotone map.

A result stronger than Theorem 1.7 holds.

Theorem 1.8. Let π be a self-map of a finite ordered set. Then every period of π is the length of a subcycle of π, or is the length of a primitive closed walk in the Markov graph of π. Conversely, every such number is a period of π.

Proof. By Theorem 1.7, Per(π) = Per(L_{π}), where L_{π} is the canonical π-linear map. We show that if n ∈ Per(L_{π}), but no subcycle of π has length n (i.e., no π-point has period n), then there is a primitive closed walk of length n in the Markov graph of π.

Suppose that x is L_{π}-periodic of period n. Then x follows a closed walk V_{i_{0}} → V_{i_{1}} → ⋯ → V_{i_{n−1}} → V_{i_{0}} of length n. By Lemma 1.2, the walk is primitive, or is V_{i_{0}} → V_{i_{1}} → ⋯ → V_{i_{(n/2)−1}} → V_{i_{0}} traversed twice. Suppose the latter holds. There are exactly two points, x and L_{π}^{n/2}(x), in the orbit of x which lie in the π-interval [i_{0}, i_{0} + 1]. L_{π}^{n/2} maps the interval with endpoints x and L_{π}^{n/2}(x) linearly onto itself with slope −1.

We claim that L_{π}^{n/2} maps the π-interval [i_{0}, i_{0} + 1] linearly onto itself with slope −1. Without loss of generality, x < L_{π}^{n/2}(x). Let y ∈ [i_{0}, x] be the point closest to x such that L_{π}^{n/2}(y) is a π-point. Similarly, let w ∈ [L_{π}^{n/2}(x), i_{0} + 1] be the point closest to L_{π}^{n/2}(x) such that L_{π}^{n/2}(w) is a π-point. Since L_{π}^{n/2}[x, L_{π}^{n/2}(x)] contains no π-points, L_{π}^{n/2} maps [y, w] linearly onto [i_{0}, i_{0} + 1] with slope −1. Therefore y = i_{0} and w = i_{0} + 1.

Now i_{0} and i_{0} + 1 are fixed points of L_{π}^{n}, and are in the same L_{π}-orbit. If i_{0} had period m < n, then x would be a fixed point of L_{π}^{m}. Since this is not the case, i_{0} has period n.

To prove the converse, it suffices by Lemma 1.3 and Sharkovskiĭ’s Theorem, to prove that if the Markov graph of π has a primitive closed walk of length 2^{m}, then 2^{m} is a period of π.

Suppose that 2^{m} is the length of a primitive closed walk in the Markov graph of π, but that 2^{m} is not a period of π. Let f be continuous and π-weakly monotone, with π-set Z_{π}. It follows, as in the proof of Lemma 1.3, that there is a π-point z_{k} ≠ max Z_{π} or min Z_{π}, which is periodic of period 2^{m−1}, and there are walks of length 2^{m−1} in the Markov graph of π from V_{k} to V_{k−1} and from V_{k−1} to V_{k}.

There are points a ∈ [z_{k−1}, z_{k}) and d ∈ (z_{k}, z_{k+1}] such that f^{2^{m−1}}(a) = z_{k+1} and f^{2^{m−1}}(d) = z_{k−1}. Then, setting b = c = z_{k} and g = f^{2^{m−1}}, we have a < b ≤ c < d, g(a) ≥ d, g(d) ≤ a, g(b) = b, g(c) = c, and there are no π-points in (a, b). In addition, Per(g) = {1}, and for some even j ≥ 0, g^{j}(a) is both a π-point and a fixed point of g. This leads to a contradiction as in the proof of Lemma 1.5. □

Remark. The proof of Theorem 1.8 shows that if π has no subcycle of length n, then every L_{π}-periodic point of period n follows a primitive closed walk of length n. This is not true for arbitrary continuous, π-weakly monotone maps in place of L_{π}. Let π = ( \begin{matrix}1 & 2 & 5 & 6 \\ 5 & 6 & 2 & 1 \end{matrix} ) and θ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 6 & 4 & 3 & 2 & 1 \end{matrix} ). Then L_{θ} is π-weakly monotone, and x = 3 is a point of L_{θ}-period 2 which does not follow a primitive closed walk of length 2 in the Markov graph of π.

Theorem 1.8 also shows that for every primitive closed walk in the Markov graph of π, there is an L_{π}-periodic point of that period. But there need not be such a point which follows the walk. Consider π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 3 & 2 & 1 \end{matrix} ), and the primitive closed walk V_{2} → V_{3} → V_{2}. Then 2 is a period of π, but no L_{π}-periodic point of period 2 follows this walk.

Definition. Let π : P → P be a cyclic permutation of a finite ordered set, P = {p_{1} < p_{2} < ⋯ < p_{2^{k}}}, of cardinality 2^{k}, k ≥ 0. If k = 0, we say that π is a simple cycle of length 1. If k > 0, set L = {p_{1} < p_{2} < ⋯ < p_{2^{k−1}}} and R = {p_{2^{k−1}+1} < p_{2^{k−1}+2} < ⋯ < p_{2^{k}}}. We say that π is a simple cycle of length 2^{k} iff π(L) = R, π(R) = L, and both π^{2}|_{L} and π^{2}|_{R} are simple cycles of length 2^{k−1}.

Suppose, for example, that π : P → P a simple cycle of length 8, where P = {p_{1} < p_{2} < ⋯ < p_{8}}. It follows from the definition that π{p_{1}, p_{2}, p_{3}, p_{4}} = {p_{5}, p_{6}, p_{7}, p_{8}} and π{p_{5}, p_{6}, p_{7}, p_{8}} = {p_{1}, p_{2}, p_{3}, p_{4}}. Furthermore, π maps each of the sets {p_{1}, p_{2}} and {p_{3}, p_{4}} onto one of the sets {p_{5}, p_{6}} and {p_{7}, p_{8}}, and vice versa. Therefore, there are exactly three primitive closed walks in the Markov graph of π, namely V_{4} → V_{4}, V_{2} → V_{6} → V_{2}, and a walk of length 4 passing through the vertices V_{1}, V_{3}, V_{5}, V_{7}.

Using the same analysis for arbitrary k > 0, we have

Remark. Suppose that π : P → P is a simple cycle of length 2^{k}, k > 0, and let t be a positive integer. Then there is a primitive closed walk of length t in the Markov graph of π if and only if t = 2^{j} for some j < k. In particular, there is no primitive closed walk of length 2^{k} in the Markov graph of π.

Theorem 1.9. For every k ≥ 0, the minimal combinatorial models for “Per(f) = {t : t ≤_{S} 2^{k}}” are the simple cycles of length 2^{k}.

Proof. It suffices to consider only k > 0, and to prove (1) and (2).

(1) Every simple cycle π of length 2^{k} satisfies Per(π) = {t : t ≤_{S} 2^{k}}.

(2) Every minimal combinatorial model for “Per(f) = {t : t ≤_{S} 2^{k}}” is a simple cycle of length 2^{k}.

Statement (1) follows from Theorem 1.8 and the Remark immediately preceding the statement of this theorem. To prove (2), suppose that π is a minimal combinatorial model for “Per(f) = {t : t ≤_{S} 2^{k}}.” Then, by (1), #π ≤ 2^{k}, and so by Theorem 1.6, π is a cycle of length 2^{k}. By [BCop, Theorem VII.24] (see also [B]), if a continuous self-map of a compact interval has a periodic point of period 2^{k} whose orbit is not simple, then it has a periodic point whose period is not a power of 2. It follows that π is a simple cycle of length 2^{k}. □

Definition. Two self-maps of finite ordered sets, π : P → P and θ : Q → Q, are equivalent iff #π = #θ, and π(p_{i}) = p_{j} if and only if θ(q_{i}) = q_{j}.

Remark. Suppose that π : P → P is a self-map of a finite ordered set and that #π = n. Then there is a unique map θ : {1, 2, …, n} → {1, 2, …, n} which is equivalent to π. Observe that the Markov graphs of π and of θ are the same. Moreover, any self-map of a compact interval is π-weakly monotone if and only if it is θ-weakly monotone. So we may assume, when convenient, that P = {1, 2, …, n}. We will do this several times in later sections.

2. Horseshoes

Recall that f : I → I has a horseshoe iff there exist subintervals J and K of I, with at most one point in common, such that f(J), f(K) ⊇ J ∪ K. Recall also that a continuous map with a horseshoe has periodic points of all periods.

Lemma 2.1. Suppose that π : P → P is a self-map of a finite ordered set, and that f : I → I is continuous and π-weakly monotone. Then f has a horseshoe if and only if there exist points p_{i} < p_{j} < p_{k} in P such that π(p_{i}), π(p_{k}) ≤ p_{i} and π(p_{j}) ≥ p_{k}, or π(p_{i}), π(p_{k}) ≥ p_{k} and π(p_{j}) ≤ p_{i}.

Proof. The conditions are clearly sufficient for f to have a horseshoe. For the converse, it suffices to show that one of the conditions holds if f has a horseshoe. Let Z denote the set of π-points of f.

By [BCop, Lemma II.2], we may assume that there exist points a < b < c in I such that

f(a) = f(c) = a and f(b) = c,
f(x) > a for all x, a < x < c,
x < f(x) < c for all x, a < x < b.

Let z_{i} be the largest π-point less than or equal to a, let z_{j} be the smallest π-point greater than or equal to b, and let z_{k} = f(z_{j}). Then z_{i} ≤ a < b ≤ z_{j} < c ≤ z_{k}.

If z_{i} = a, then f(z_{i}) = z_{i}. If z_{i} < a, then it follows from the fact that for small ϵ > 0, f is nondecreasing on [a, a + ϵ] and there are no π-points in (z_{i}, a + ϵ), that f(z_{i}) ≤ z_{i}. Similarly, f(z_{k}) ≤ z_{i}.

It follows that π(p_{i}), π(p_{k}) ≤ p_{i} and π(p_{j}) ≥ p_{k}. □

Lemma 2.2. Suppose that π : P → P is a self-map of a finite ordered set, and that f : I → I is continuous and π-weakly monotone. Let k ≥ 1. Then f^{k} has a horseshoe if and only if there exist π-points, a < b < c of f, such that f^{k}[a, b], f^{k}[b, c] ⊇ [a, c].

Proof. One direction is trivial. Suppose then that f^{k} has a horseshoe. Let Z_{π} denote the set of π-points of f. As in the proof of Theorem 1.6, there is a self-map θ : Q → Q of a finite ordered set, such that f^{k}(Z_{θ}) ⊆ Z_{π} and f^{k} is θ-weakly monotone. By Lemma 2.1, there are points x < y < z in Z_{θ} such that, without loss of generality, f^{k}(x) ≤ x, f^{k}(z) ≤ x and f^{k}(y) ≥ z. Hence f^{k}(x) ≤ x, f^{k}(z) ≤ x and f^{k}(y) ≥ z. In particular, f^{i}(y) ≠ f^{i}(x), f^{i}(z) for 0 ≤ i ≤ k.

Let m be the smallest positive integer such that f^{m}(y) is not between f^{m}(x) and f^{m}(z). Then 1 ≤ m ≤ k. We may assume that f^{m}(y) < f^{m}(x), f^{m}(z).

Let

v = min{f^{m−1}(x), f^{m−1}(z)},
and w = max{f^{m−1}(x), f^{m−1}(z)}.

Then v < f^{m−1}(y) < w and f^{m−1}[x, z] ⊇ [v, w].

Let b be a point in [v, w] at which f attains its minimum value. This minimum is less than f(v) and f(w), so min f[v, w] = f(b), where b is a turning point or in a turning interval. Since every turning interval contains a π-point, we may assume that b is a π-point.

Now let a be the largest π-point less than or equal to v, and let c be the smallest π-point greater than or equal to w. Since f^{k}[v, b], f^{k}[b, w] ⊇ [v, w] and f^{k}(Z_{θ}) ⊆ Z_{π}, it follows that f^{k}[v, b], f^{k}[b, w] ⊇ [a, c]. Thus f^{k}[a, b], f^{k}[b, c] ⊇ [a, c]. □

We now phrase Lemma 2.2 in terms of π and its Markov graph.

Definition. A directed graph, with ordered vertices, and arcs · → ·, has a horseshoe iff there are disjoint, nonempty collections V_{L} and V_{R}, of vertices of the Markov graph of π, such that i < j for every V_{i} ∈ V_{L} and every V_{j} ∈ V_{R}, and such that for every V ∈ V_{L} ∪ V_{R}, there exist V_{i} ∈ V_{L} and V_{j} ∈ V_{R} and arcs from V_{i} to V and from V_{j} to V.

Definition. Let D be a directed graph and let k ≥ 1. The k-th power of D is the directed graph whose vertices are the vertices of D (and with the same order if the vertices of D are ordered), and whose arcs are the paths of length k in D.

Theorem 2.3. Suppose that π : P → P is a self-map of a finite ordered set, and that f : I → I is continuous and π-weakly monotone. Let k ≥ 1. Then f^{k} has a horseshoe if and only if the k-th power of the Markov graph of π has a horseshoe.

Proof. Let Z denote the set of π-points of f. Suppose that f^{k} has a horseshoe. By Lemma 2.2, there are π-points points a < b < c such that f^{k}[a, b], f^{k}[b, c] ⊇ [a, c]. Let V_{L} denote the set of vertices V_{i} in the Markov graph of π such that a ≤ z_{i} < z_{i+1} ≤ b, and let V_{R} denote the set of vertices V_{j} in the Markov graph of π such that b ≤ z_{j} < z_{j+1} ≤ c. Then V_{L} and V_{R} are well-defined, and satisfy the conditions of the definition.

Conversely, suppose that V_{L} and V_{R} are as in the definition. Let i and j be least such that V_{i} ∈ V_{L} and V_{j} ∈ V_{R}. Similarly, let i′ and j′ be greatest such that V′_{i} ∈ V_{L} and V′_{j} ∈ V_{R}. Then [z_{i}, z_{i′+1}] and [z_{j}, z_{j′+1}] exhibit a horseshoe for f^{k}. □

3. Reduction- and restriction-minimality

In this section, we introduce an important property of minimal combinatorial models, reduction- and restriction-minimality. Reduction-minimality is defined in terms of an even more important concept, block structure.

Throughout this section, π : P → P = {p_{1} < p_{2} < ⋯ < p_{n}} and θ : Q → Q = {q_{1} < q_{2} < ⋯ < q_{m}} will denote self-maps of finite ordered sets, n = #π and m = #θ.

Definition and Notation. A block of P is a subset B of consecutive members (possibly only one) of P. For blocks B and B′, write B < B′ iff b < b′ for every b ∈ B, b′ ∈ B′.

Definition. A block structure for π is a partition B = {B_{1} < B_{2} < ⋯ < B_{m}} of P into disjoint blocks such that if b and b′ belong to the same block, then so do π(b) and π(b′).

Definition. Let B = {B_{1} < B_{2} < ⋯ < B_{m}} be a block structure for π. The reduction of π corresponding to B is θ : {q_{1} < q_{2} < ⋯ < q_{m}} → {q_{1} < q_{2} < ⋯ < q_{m}}, defined by θ(q_{i}) = q_{j} if π(B_{i}) ⊆ B_{j}.

We will use some graph theory terminology.

Definition. Let D be a graph and let V be a subset of the vertices of D. The subgraph of D induced by V is the graph whose set of vertices is V, and whose set of arcs is the set of arcs in D from vertices in V to vertices in V.

Definition. Let B be a block structure for π. The vertex V_{k} in the Markov graph of π is a gap vertex if p_{k} and p_{k+1} are in different blocks, and a block vertex if they are in the same block.

Lemma 3.1. Suppose that B is a block structure for π, and that θ is the corresponding reduction.

(1) Every closed walk in the Markov graph of π passes through only block vertices or through only gap vertices.

(2) [MN, Theorem 4.1] The Markov graph of θ is isomorphic, via an increasing map of the vertices, to the subgraph of the Markov graph of π induced by the gap vertices.

Proof. (1) follows from the fact that there are no arcs from block vertices to gap vertices. □

Definition. θ : Q → Q is a restriction of π : P → P iff Q ⊆ P and θ = π|_{Q}.

Lemma 3.2. Suppose that θ is a reduction of or a restriction of π.

(1) If π is a permutation, then so is θ.

(2) If the r-th power of the Markov graph of θ has a horseshoe, then so does the r-th power of the Markov graph of π.

Proof. (1) By [MN, Remark 3.2], a reduction of a permutation is a permutation. It is obvious that a restriction of a permutation is a permutation.

(2) If θ is a reduction of π and the r-th power of the Markov graph of θ has a horseshoe, then by Lemma 3.1, so does the r-th power of the Markov graph of π.

Suppose that θ : Q → Q is a restriction of π : P → P, and that the r-th power of the Markov graph of θ has a horseshoe. Let f be continuous, π-weakly monotone, and, without loss of generality, the set of π-points of f is P. Similarly, let g be continuous, θ-weakly monotone, and the set of θ-points of g is Q. Since the r-th power of the Markov graph of θ has a horseshoe, it follows from Theorem 2.3 that g^{r} has a horseshoe. By Lemma 2.2, there are θ-points a < b < c, such that g^{r}[a, b], g^{r}[b, c] ⊇ [a, c]. Since Q ⊆ P, a, b, and c are π-points. But f(J) ⊇ g(J) for every interval J whose endpoints are θ-points, and hence f^{r}(J) ⊇ g^{r}(J) for every such interval. Therefore f^{r}[a, b], f^{r}[b, c] ⊇ [a, c]. By Theorem 2.3, the r-th power of the Markov graph of π has a horseshoe. □

Definition. π is reduction- and restriction-minimal iff there is no proper reduction of π with the same set of periods as π and there is no proper restriction of π with the same set of periods as π.

The following theorem is immediate from Lemma 3.2.

Theorem 3.3. Suppose that π is a minimal combinatorial model or a minimal permutation model for either of the following properties.

(1) Per(f) = {t : t ≤_{S} s}, s ≥ 1.

(2) Per(f) = {t : t ≤_{S} 3 · 2^{k}}, k ≥ 0, and f^{2^{k}} does not have a horseshoe. Then π is reduction- and restriction-minimal.

In the remainder of this section, we establish several properties of reduction- and restriction-minimal maps. These properties will be needed in the next section.

Definition. f : I → I exhibits π iff there exist x_{1} < x_{2} < ⋯ < x_{n} in I such that if π(p_{i}) = p_{j}, then f(x_{i}) = x_{j}.

Remark. Every π-weakly monotone map exhibits π.

Definition. A block B of P is flat iff B contains at least two points, and π is constant on B.

Lemma 3.4. If θ is a reduction of or a restriction of π, then Per(θ) ⊆ Per(π).

Proof. (1) θ is a reduction of π.

By Lemma 3.1, if the Markov graph of θ has a primitive closed walk, then the Markov graph of π has a primitive closed walk of the same length.

Suppose that θ has a subcycle q_{i_{1}} → q_{i_{2}} → ⋯ → q_{i_{k}} → q_{i_{1}} of length k. Let B_{i_{1}}, B_{i_{2}}, …, B_{i_{k}} be the corresponding blocks of π-points. Since the q’s are distinct, these blocks are pairwise disjoint. Let f be continuous and π-weakly monotone, with π-set Z. Define closed intervals J_{i_{1}}, J_{i_{2}}, …, J_{i_{k}} by

J_{i_{1}} = [min{z_{r} ∈ Z : p_{r} ∈ B_{i_{1}}}, max{z_{r} ∈ Z : p_{r} ∈ B_{i_{1}}}], etc.

These intervals are pairwise disjoint, and some may be degenerate. f^{k}(J_{i_{1}}) ⊆ J_{i_{1}}, and f^{j}(J_{i_{1}}) ∩ J_{i_{1}} = ∅ for 1 ≤ j ≤ k − 1. Therefore, k ∈ Per(f) = Per(π).

By Theorem 1.8, Per(θ) ⊆ Per(π).

(2) θ is a restriction of π.

We show that if f is continuous and exhibits θ, then Per(θ) ⊆ Per(f). Then, since θ is a restriction of π, any continuous, π-weakly monotone map exhibits θ. By [MN, Corollary 1.15], there is a continuous, θ-weakly monotone map f_{θ}, such that for every map η of a finite ordered set which has no flat blocks, if f_{θ} exhibits η, then any continuous f which exhibits θ also exhibits η. So let k ∈ Per(θ) = Per(f_{θ}), and let f be a continuous map which exhibits θ. There is a cyclic permutation η of a finite ordered set containing k points which is exhibited by f_{θ}. Since permutations have no flat blocks, f also exhibits η. Thus k ∈ Per(f). □

We now derive the desired properties of reduction- and restriction-minimal maps. Some of these properties hold only for maps whose set of periods does not consist only of powers of 2.

We will show that a reduction- and restriction-minimal map

• has no flat blocks,

• is not a double,

• has no proper cycle of blocks,

• has no monotone cycle of blocks,

• has every point in the orbit of a turning point.

Lemma 3.5. A reduction- and restriction-minimal map has no flat blocks.

Proof. Suppose that π : P → P is reduction- and restriction-minimal, but that π(p_{k}) = π(p_{k+1}). Define a block structure B = {B_{1} < B_{2} < ⋯ < B_{n−1}}, by B_{i} = {p_{i}}, i = 1, 2, …, k−1, B_{k} = {p_{k}, p_{k+1}}, and B_{i} = {p_{i+1}}, i = k+1, k+2, …, n−1. Let m = n − 1 and let θ be the corresponding proper reduction of π.

The Markov graph of θ is isomorphic, via the obvious map, to the subgraph of the Markov graph of π induced by the vertices V_{i}, i ≠ k. Since no subcycles of π pass through both p_{k} and p_{k+1}, and no arcs in the Markov graph of π have initial vertex V_{k}, it follows from Theorem 1.8 that π and θ have the same set of periods.

Therefore, π has no flat blocks. □

Definition. π : P → P is a double of θ : Q → Q iff n = 2m, and π{p_{2i−1}, p_{2i}} = {p_{2j−1}, p_{2j}} if θ(q_{i}) = q_{j}.

Lemma 3.6. A reduction- and restriction-minimal map π such that the set of periods of π does not consist only of powers of 2 is not a double.

Proof. Suppose that π is reduction- and restriction-minimal, and the set of periods of π does not consist only of powers of 2, but that π is a double of θ. Since θ is a proper reduction of π, it suffices, by Lemma 3.4, to show that Per(π) ⊆ Per(θ). To do this, it suffices to show that the Sharkovskiĭ-largest period s of π is also a period of θ. By Theorem 1.8, π has a subcycle of length s, or there is a primitive closed walk of length s in the Markov graph of π.

In the first case, θ has a subcycle of length s or of length s/2. Since s is not a power of 2, s/2 is Sharkovskiĭ-greater than s. So by Sharkovskiĭ’s Theorem, s is a period of θ.

In the second case, if the primitive closed walk passes through only block vertices, then θ has a subcycle of length s. If the subcycle passes through only gap vertices, then by Lemma 3.1(2), the Markov graph of θ contains a primitive closed walk of length s. By Theorem 1.8, s is a period of θ. □

Lemma 3.7. Suppose that π : P → P is reduction- and restriction-minimal, and that {B_{1}, B_{2}, …, B_{k}} is a collection of disjoint blocks, each containing at least two points, such that π(B_{i}) ⊆ B_{i+1}, i = 1, 2, …, k, where B_{k+1} = B_{1}. Then B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{k} = P.

Proof. If there is such a collection of blocks whose union is not all of P, let C be the block structure for π, where the blocks in C are B_{1}, B_{2}, …, B_{k} and the singleton subsets of P ∖ (B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{k}). Let θ be the proper reduction of π determined by C, and let η be the proper restriction of π to B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{k}. We show that Per(π) = Per(θ) or Per(η). To do this, it suffices, by Lemma 3.4, to show that Per(π) ⊆ Per(θ) or Per(π) ⊆ Per(η). As in the proof of Lemma 3.5, we show that the Sharkovskiĭ-largest period s of π is also a period of θ or of η. By Theorem 1.8, π has a subcycle of length s, or there is a primitive closed walk of length s in the Markov graph of π.

Suppose that π has a subcycle of length s. This cycle is either entirely contained in B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{k} or is disjoint from it. In the first case, η has a subcycle of length s; in the second case, θ does.

Suppose that there is a primitive closed walk of length s in the Markov graph of π. There are no arcs from block vertices to gap vertices, and the Markov graph of θ is isomorphic to the subgraph of the Markov graph of π induced by the gap vertices. The subgraph of the Markov graph of π induced by the block vertices is isomorphic to the corresponding induced subgraph of the Markov graph of η. Therefore, the Markov graph of θ or the Markov graph of η contains a primitive closed walk of length s. □

Lemma 3.8. Suppose that π : P → P is reduction- and restriction-minimal, and that the set of periods of π does not consist only of powers of 2. Then there is no collection {B_{1}, B_{2}, …, B_{k}} of disjoint blocks, each containing at least two points, such that π maps B_{i} monotonically onto B_{i+1}, i = 1, 2, …, k, where B_{k+1} = B_{1}.

Proof. If there is such a collection, then by Lemma 3.7, B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{k} = P. Also, π maps the union of the endpoints of the blocks onto itself. Let θ be the restriction of π to this set. By Lemma 3.6, π is not a double, so θ is a proper restriction of π. We show that Per(θ) = Per(π).

By Lemma 3.4, Per(θ) ⊆ Per(π). To show the opposite containment, let s be the Sharkovskiĭ-largest period of π. We show that s is a period of θ.

First suppose that s = k or 2k. Then, as in the proof of Lemma 3.4, k ∈ Per(θ), and since s is not a power of 2, 2k is Sharkovskiĭ-less than or equal to k, and hence 2k ∈ Per(θ).

Next suppose that s ≠ k or 2k. Since every subcycle of π has length k or 2k, by Theorem 1.8, the Markov graph of π has a primitive closed walk of length s. Every primitive closed walk which passes through only block vertices has length k or 2k. Therefore, this walk passes through only gap vertices. Since θ and π have block structures with a common reduction, by Lemma 3.1, the subgraphs of the Markov graphs of θ and of π induced by the respective gap vertices are isomorphic. Therefore, the Markov graph of θ has a primitive closed walk of length s. By Theorem 1.8, s ∈ Per(θ). □

Recall that L_{π} : [1, n] → [1, n] is the canonical π-linear map. In [BCov], an interval J with endpoints in P is called periodic iff there is a positive integer t such that L_{π}^{t} is the identity on J. It follows from [BCov, Lemmas 2.3 and 2.4] that {p_{i}, p_{i+1}, …, p_{i+k}} is in a monotone cycle of blocks if and only if [i, i + k] is a periodic interval.

Recall that p_{k} is a turning point of π iff k ≠ 1, n, and either π(p_{k−1}), π(p_{k+1}) < π(p_{k}) or π(p_{k−1}), π(p_{k+1}) > π(p_{k}).

Lemma 3.9. Suppose that π : P → P is reduction- and restriction-minimal, and that the set of periods of π does not consist only of powers of 2. Then every point in P is in the orbit of a turning point of π.

Proof. Let θ be the restriction of π to Q, where Q is the set of points in P, each of which is in the orbit of at least one of the following.

• the largest point in P

• the smallest point in P

• a turning point of π

• an endpoint of a maximal flat block

• an endpoint of a block in a maximal monotone cycle of blocks. By [BCov, Theorem 2.6], L_{θ} and L_{π} are topologically conjugate; in particular they have the same set of periods. But then by Theorem 1.7, Per(θ) = Per(π). Since π is reductionand restriction-minimal, θ = π.

Since π has no flat blocks and no monotone cycles of blocks, it suffices to show that the smallest and largest points in P, say p and p′, are in the orbits of turning points of π. If π^{−1}(p) ⊆ {p}, π^{−1}(p′) ⊆ {p′}, or π^{−1}{p, p′} ⊆ {p, p′}, then there is a restriction of π with the same set of periods as π. If none of these conditions hold, then p and p′ are in the orbits of turning points of π. □

4. Block structure over a simple cycle

Recall that f : I → I has a horseshoe iff there are nondegenerate closed subintervals, J and K of I, with at most one point in common, such that f(J), f(K) ⊇ J∩K. It is clear that if f has a horseshoe, then so does any power of f.

Lemma 4.1. Suppose f : I → I is continuous and that there is no nondegenerate, closed subinterval J ≠ I of I, such that f(J) ⊆ J.

(1) If f has more than one fixed point, then f has a horseshoe.

(2) If some fixed point of f has more than one preimage, then f^{2} has a horseshoe.

Proof. Without loss of generality I = [0, 1].

(1) It suffices to find a < b < c in [0, 1], such that f(a) = f(c) = a and f(b) = c (or f(a) = f(c) = c and f(b) = a).

The set of non–fixed points of f is open and dense in [0, 1]. Since f has more than one fixed point, there is a connected component C of that set such that both endpoints a < a′ are fixed points. Without loss of generality f(x) > x for every x, a < x < a′. Then a′ ≠ 1. (Otherwise let J = [a + ϵ, 1].)

Let c > a′ be least such that f(c) = a. (If no such c exists, again let J = [a+ϵ, 1].) There exists b, a < b < c, such that f(b) = c. (If no such b exists, let J = [a, c − ϵ].)

(2) We may assume that f has exactly one fixed point a, for otherwise by (1), f has a horseshoe and then so does f^{2}. Since f is onto, a ≠ 0, 1. Suppose that f(c) = a, where without loss of generality, c > a.

Let u = min{f(x) : a < x < c}. Then u < a. (If not, let J = [a, c].) There exists b′, u ≤ b′ < a, such that f(b′) = c. (If not, let J = f[u, c].) There exists b, a < b < c, such that f(b) = b′. Then f^{2}(a) = f^{2}(c) = a and f^{2}(b) = c. □

Recall that if #π = n, then L_{π} : [1, n] → [1, n] is the canonical π-linear map.

Lemma 4.2. Suppose that π : P → P is reduction- and restriction-minimal, #π = n, and the set of periods of π does not consist only of powers of 2. If there is a nondegenerate, closed interval J ⊆ [1, n], and a positive integer t, such that J, L_{π}(J), …, L_{π}^{t−1}(J) are pairwise disjoint and L_{π}^{t}(J) ⊆ J, then J ∪ L_{π}(J) ∪ ⋯ ∪ L_{π}^{t−1}(J) ⊇ {1, 2, …, n}.

Proof. Without loss of generality, P = {1, 2, …, n}. Since π has no flat blocks, the slope of L_{π} on any π-interval [i, i + 1] has absolute value at least 1. Let J be an interval satisfying the conditions of the lemma.

Suppose first that J ∩ P = ∅. Then, for i = 0, 1, …, t − 1, L_{π}^{i}(J) ∩ P = ∅. Therefore, L_{π}^{t} is linear on J. Since L_{π}^{t}(J) ⊆ J and the slope of L_{π}^{t} on J has absolute value at least 1, L_{π}^{t} maps J linearly onto J. Therefore L_{π}^{2t} is the identity on J, and so J is contained in a periodic (in the sense of [BCov] - see Section 3) interval whose endpoints belong to P. This contradicts Lemma 3.8. Therefore J ∩ P ≠ ∅.

Next, suppose that J ∩ P contains exactly one point, say d. Since π has no flat blocks, each L_{π}^{i}(J) ∩ P contains exactly one point. Define a subinterval K of J = [a, b], as follows. If d = a or b, let K = J. Suppose that a < d < b. At least one of the following holds.

(1) L_{π}^{t}[a, d] ⊆ [a, d].

(2) L_{π}^{t}[d, b] ⊆ [d, b].

(3) L_{π}^{t}[a, d] ⊆ [d, b] and L_{π}^{t}[d, b] ⊆ [a, d].

If (1) holds, set K = [a, d]; otherwise set K = [d, b]. Then L_{π}^{2t}(K) ⊆ K, and for each i = 0, 1, …, 2t − 1, L_{π}^{i}(K) is contained in a unique π-interval. As above, this leads to a condradiction of Lemma 3.8.

Therefore J ∩ P contains at least two points. For each i = 1, 2, …, t, let B′_{i} = L_{π}^{i−1}(J)∩P. Each B′_{i} is a block containing at least two points, and π(B′_{i}) ⊆ B′_{i+1} for i = 1, 2, …, t, where B′_{t+1} = B′_{1}. It follows from Lemma 3.7 that B′_{1}∪B′_{2}∪⋯∪B′_{t} = P. Therefore J ∪ L_{π}(J) ∪ ⋯ ∪ L_{π}^{t−1}(J) ⊇ P. □

Remark. A cycle which is a double (defined in Section 3) of a simple cycle of length 2^{k} (defined in Section 1) is a simple cycle of length 2^{k+1}.

Theorem 4.3. Let k ≥ 0. Suppose that π : P → P is a reduction- and restrictionminimal self-map of a finite ordered set, such that the set of periods of π does not consist only of powers of 2, and such that the 2^{k}-th power of the Markov graph of π does not have a horseshoe. Then π has a block structure over a simple cycle of length 2^{k}.

Proof. We prove, by induction on j, that for every j = 0, 1, …, k, π has a block structure over a simple cycle of length 2^{j}.

There is nothing to prove for j = 0. Suppose then that 0 ≤ j ≤ k −1, and that π has a block structure over a simple cycle θ of length 2^{j}. Let B′′_{1}, B′′_{2}, …, B′′_{2^{j}} be the blocks of this block structure, labelled so that π(B′′_{i}) ⊆ B′′_{i+1} for i = 1, 2, …, 2^{j}, where B′′_{2^{j}+1} = B′′_{1}. Since π has no flat blocks and the set of periods of π does not consist only of powers of 2, each block contains at least two points of P.

Suppose that #π = n. Without loss of generality, P = {1, 2, …, n}. Let L_{π} : [1, n] → [1, n] be the canonical π-linear map. For i = 1, 2, …, 2^{j}, let J_{i} be the convex hull, in [1, n], of the block B′′_{i}, where B′′_{i} is as in the preceding paragraph, and let g_{i} = L_{π}^{2^{j}}|_{J_{i}}. Then g_{i} maps J_{i} to itself. Since j ≤ k − 1, g_{i}^{2} does not have a horseshoe.

Now, fix i, 1 ≤ i ≤ 2^{j}. We claim that there is no nondegenerate, proper, closed subinterval J of J_{i} such that g_{i}(J) ⊆ J. Suppose that J is such an interval. Then the intervals J, L_{π}(J), …, L_{π}^{2^{j}−1}(J) are pairwise disjoint. So, by Lemma 4.2, J ∪ L_{π}(J) ∪ ⋯ ∪ L_{π}^{2^{j}−1}(J) ⊇ P. Since the endpoints of J_{i} are in P, it follows that J = J_{i}. This establishes the claim.

By Lemma 4.1, g_{i} has a unique fixed point w_{i}, and w_{i} is its own g_{i}-preimage. We claim that every L_{π}-periodic point not in J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{2^{j}} has period a

power of 2. If not, then by Lemma 1.2, the Markov graph of π has a primitive closed walk of length not a power of 2 which passes through only gap vertices. By Lemma 3.1, the Markov graph of θ has a a primitive closed walk of length not a power of 2. This contradicts the Remark immediately preceding Theorem 1.9.

Since L_{π} has a periodic point of period not a power of 2, g_{i} has a periodic orbit Q with more than one point. There exist adjacent points y < z in Q, such that g_{i}(y) > y and g_{i}(z) < z. Therefore y < w_{i} < z, g_{i}(y) > w_{i}, and g_{i}(z) < w_{i}. Since w_{i} is its own g_{i}-preimage, it follows that (∗) g_{i}(x) > w_{i} for every x ∈ J_{i} such that x < w_{i}, and g_{i}(x) < w_{i} for every x ∈ J_{i} such that x > w_{i}.

Now, {w_{1}, w_{2}, …, w_{2^{j}}} is a periodic orbit of L_{π}. It follows from (∗) that if x_{1} ∈ J_{1} and L_{π}(x_{1}) = w_{2}, then x_{1} = w_{1}. Therefore we have (∗∗) L_{π}^{−1}(w_{1}) ∩ J_{2^{j}} = {w_{2^{j}}}, and for i ≠ 1, L_{π}^{−1}(w_{i}) ∩ J_{i−1} = {w_{i−1}}.

It also follows from (∗) that none of the points w_{i} are turning points of L_{π}. Since J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{t} contains all the turning points of L_{π}, it follows from (∗∗) that none of the points w_{i} is in the orbit of a turning point of L_{π}. Then, by Lemma 3.9, none of the points w_{i} is in P. This, together with (∗) and the remark immediately preceding the statement of this theorem, implies that π has a block structure over a simple cycle of length 2^{j+1}. □

5. Sharkovskiĭ-largest period 3 · 2^{k}

This section contains the most surprizing, and technically most difficult to prove, results — the characterizations of the minimal combinatorial models and the minimal permutation models for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}.” It is the only case for which the minimal combinatorial models and the minimal permutation models are not the same.

Definition. Let π : P → P be a cyclic permutation of a finite ordered set of cardinality m · 2^{k}, where m > 1 is odd. π is a simple cycle iff

(1) π has a block structure over a simple cycle of length 2^{k}.

(2) π is monotone on all blocks but one.

(3) For each block B, letting p be the central point of B and θ = π^{2^{k}}|_{B}, either

θ^{m−1}(p) < θ^{m−3}(p) < ⋯ < θ^{2}(p) < p < θ(p) < ⋯ < θ^{m−4}(p) < θ^{m−2}(p)

or

θ^{m−1}(p) > θ^{m−3}(p) > ⋯ > θ^{2}(p) > p > θ(p) > ⋯ > θ^{m−4}(p) > θ^{m−2}(p).

Lemma 5.1. Let π : P → P be a reduction- and restriction-minimal map of a finite ordered set, such that Per(π) = {t : t ≤_{S} 3 · 2^{k}}, and such that the 2^{k}-th power of the Markov graph of π does not have a horseshoe. If #π ≤ 3 · 2^{k}, then π is a simple cycle of length 3 · 2^{k}.

Proof. Without loss of generality, P = {1, 2, …, n}. By Theorem 4.3, π has a block structure over a simple cycle of length 2^{k}. Let B_{1}, B_{2}, …, B_{2^{k}} be the blocks of this structure, labelled so that π(B_{i}) ⊆ B_{i+1} for i = 1, 2, …, 2^{k}, where B_{2^{k}+1} = B_{1}. Let C_{i} = [min B_{i}, max B_{i}] be the convex hull of B_{i} (in [1, n]). Since the set of periods of π does not consist only of powers of 2, at least one block contains more than one point. Since π has no flat blocks, every block contains at least two points. If every block contained exactly two points, then, by Theorem 1.8, every period of π would be a power of 2. Therefore, one of the blocks contains at least three points.

If one of the blocks contained exactly two points, then some block B_{i} contains more than two points, while B_{i+1} contains exactly two points. Now let L_{π} : [1, n] → [1, n] be the canonical π-linear map. Since π has no flat blocks, there are nonoverlapping subintervals J′ and J′′ of C_{i}, such that L_{π}(J′) = L_{π}(J′′) = C_{i+1}. But then L_{π}^{2^{k}} has a horseshoe. Therefore each block contains at least three points, hence exactly three points, and #π = 3 · 2^{k}.

Let J be the set of π-intervals contained in C_{1}∪C_{2}∪⋯∪C_{2^{k}}, i.e., J = {[j, j+1] : V_{j} is a block vertex}. Note that each C_{i} contains exactly two intervals in J. If, for each interval J in J, L_{π}(J) contains only one interval in J, then every L_{π}^{2^{k}}|_{C_{i}} is monotone. This contradicts the fact that some L_{π}^{2^{k}}|_{C_{i}} has a periodic point of period 3. Therefore, there is at least one interval J_{0} in J such that L_{π}(J_{0}) contains two intervals in J.

By relabelling, we may assume that J_{0} ⊆ C_{2^{k}}. Let I_{2^{k},1} = J_{0}, and let I_{2^{k},2} be the other interval in J which is a subset of C_{2^{k}}. Then L_{π}(I_{2^{k},1}) = C_{1}. Now, it follows from Lemma 3.7 that L_{π}(C_{i}) = C_{i+1} for i = 1, 2, …, 2^{k} − 1. In particular, L_{π}^{2^{k}}(I_{2^{k},1}) = C_{2^{k}}. Since L_{π}^{2^{k}} does not have a horseshoe, L_{π}(I_{2^{k},2}) is a proper subset of C_{1}. Denote the intervals in J which are contained in C_{1} by I_{1,1} and I_{1,2}, where L_{π}(I_{2^{k},2}) = I_{1,2}. Similarly, for i = 2, 3, …, 2^{k} − 1, denote the two members of J which are contained in C_{i} by I_{i,1} and I_{i,2}, where L_{π}(I_{i−1,2}) = I_{i,2}.

Since L_{π}^{2^{k}} has a point of period 3, we must have L_{π}(I_{2^{k}−1,2}) ⊇ I_{2^{k},1}. If L_{π}(I_{2^{k}−1,2}) ⊇ I_{2^{k},2} as well, then the intervals I_{2^{k},1} and I_{2^{k},2} would exhibit a horseshoe for L_{π}^{2^{k}}. Thus L_{π}(I_{2^{k}−1,2}) = I_{2^{k},1}.

If L_{π}(I_{1,1}) ⊇ I_{2,2}, then the intervals I_{1,1} and I_{1,2} would exhibit a horeshoe for L_{π}^{2^{k}}. Thus L_{π}(I_{1,1}) = I_{2,1}. Similarly L_{π}(I_{i,1}) = I_{i+1,1} for i = 2, 3, …, 2^{k} − 2 and L_{π}(I_{2^{k}−1,1}) = I_{2^{k},2}.

We have determined all the arcs emanating from block vertices in the Markov graph of π. In particular, π maps B_{i} monotonically onto B_{i+1} for i = 1, 2, …, 2^{k}−1. Furthermore, if x is the point in B_{1} which is an endpoint of I_{1,1}, but not an endpoint of I_{1,2}; if y is the common endpoint of I_{1,1} and I_{1,2}; and if z is the point in B_{1} which is an endpoint of I_{1,2}, but not an endpoint of I_{1,1}, then it is easy to check that π^{2^{k}}(x) = y, π^{2^{k}}(y) = z, and π^{2^{k}}(z) = x. Therefore π is a simple cycle. □

Theorem 5.2. The minimal combinatorial models for “Per(f) = {t : t ≤_{S} 3 · 2^{k}} and f^{2^{k}} does not have a horseshoe” are the simple cycles of length 3 · 2^{k}.

Proof. First suppose that π : P → P is a simple cycle of length 3 · 2^{k}. Then π has a block structure over a simple cycle θ of length 2^{k}. Since the length of any primitive closed walk in the Markov graph of θ is a power of 2, it follows from Lemma 3.1(2) that the length of any primitive closed walk in the Markov graph of π which passes through only gap vertices is also a power of 2. On the other hand, any primitive closed walk in the Markov graph of π which passes only through block vertices has length a multiple of 2^{k}. The Markov graph of π has a primitive closed walk of length 3 · 2^{k}, and 3 · 2^{k} is the Sharkovskiĭ-largest multiple of 2^{k}. By Theorem 1.8, the Sharkovskiĭ-largest period of π is 3 · 2^{k}.

Let f be continuous and π-weakly monotone. The monotonicity condition on π implies that the 2^{k}-th power of the Markov graph of π does not have a horseshoe. By Theorem 2.3, neither does f^{2^{k}}. Therefore π is a combinatorial model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}} and f^{2^{k}} does not have a horseshoe.”

To complete the proof, suppose that π : P → P is a minimal combinatorial model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}} and f^{2^{k}} does not have a horseshoe.” Then, by the first part of the proof, #π ≤ 3 · 2^{k}, and by Theorem 3.3, π is reduction- and restriction-minimal. So, by Lemma 5.1, π is a simple cycle of length 3 · 2^{k}. □

Theorem 5.3. The minimal permutation models for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}” are the permutations of cardinality 3 · 2^{k} which satisfy (1) and (2).

(1) π has a block structure over a simple cycle of length 2^{k}, with each block having exactly three points.

(2) For any pair of adjacent points, p_{j} and p_{j+1}, in the same block, π^{i}(p_{j}) and π^{i}(p_{j+1}) are not adjacent points for some i, 1 ≤ i ≤ 2^{k+1}.

Proof. First, suppose that π : P → P is a permutation which satisfies (1) and (2). There is a block B = {p_{j}, p_{j+1}, p_{j+2}} such that the restriction of π to B is not monotone. Consider V_{j} and V_{j+1}, the two block vertices associated with B in the Markov graph of π. Without loss of generality, there are arcs from V_{j} to two distinct block vertices. Since π maps blocks onto blocks, it follows that there are walks of length 2^{k} from V_{j} to V_{j} and from V_{j} to V_{j+1}.

It follows from (2) that there is a closed walk of length 2^{k} from V_{j+1} to V_{j}. By following, in succession, the walks from V_{j} to V_{j}, from V_{j} to V_{j+1}, and from V_{j+1} to V_{j}, we obtain a primitive closed walk of length 3 · 2^{k}. By Theorem 1.8, 3 · 2^{k} ∈ Per(π).

On the other hand, it follows from (1) that the length of any subcycle of π is a multiple of 2^{k}. Now suppose that W is a primitive closed walk. By Lemma 3.1(1), W passes through only block vertices or through only gap vertices. In the first case, the length of W is a multiple of 2^{k}. In the second case, it follows from Lemma 3.1(2) and the remark immediately preceding Theorem 1.9, that the length of W is 2^{j} for some j < k. Therefore, the length of W is Sharkovskiĭ-less than or equal to 3 · 2^{k}. Thus, by Theorem 1.8, 3 · 2^{k} is the Sharkovskiĭ-largest period of π, and so π is a permutation model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}.”

To complete the proof, suppose that π : P → P is a minimal permutation model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}.” For notational convenience, we may assume that P = {1, 2, …, n}, and consider the canonical π-linear map L_{π} : [1, n] → [1, n]. We may also assume that k ≥ 1, as the case k = 0 is straightforward.

By Theorem 3.3, π is reduction- and restriction-minimal. Since 3·2^{k−1} ∉ Per(π), the 2^{k−1}-st power of the Markov graph of π does not have a horseshoe. Hence, by Theorem 4.3, π has a block structure over a simple cycle of length 2^{k−1}.

As in the proof of Theorem 4.3, let B be one of the blocks, and let C = [min B, max B] be its convex hull. Since π maps blocks onto blocks, L_{π} maps convex hulls of blocks onto convex hulls of blocks. Set g = L_{π}^{2^{k−1}}|_{C}. Then g maps C onto itself. We will show that (∗) holds.

(∗) There is a point z ∈ C, z ∉ B, such that g(p) > z for every p ∈ B with p < z, and g(p) < z for every p ∈ B with p > z.

As in the proof of Theorem 4.3, g has no proper, nondegenerate, invariant subinterval. Since g does not have a horseshoe, by Lemma 4.1, it has a unique fixed point, call it z. Since g maps C onto itself, z is not an endpoint of C.

We first claim that z is not a turning point of g. Note that, since π is reductionand restriction-minimal, L_{π} and hence g have no flat intervals. If z is a turning point of g, let Q be B union the set of endpoints of maximal monotone pieces of g. Let a be the largest point in Q less than z, and let b be the smallest point in Q greater than z. Then, since g maps endpoints of maximal monotone pieces of g into B, g(a), g(b) ∈ B. Since the turning point z is the unique fixed point of g, either g(a) < a or g(b) > b. Without loss of generality, assume the former. Then g(x) < x for all x ∈ C such that x ≤ a. But g(a) < a, so g^{2}(a) < g(a). Continuing, we have ⋯ < g^{3}(a) < g^{2}(a) < g(a), which contradicts the fact that g(a) is g-periodic. Therefore z is not a turning point of g, and hence not a turning point of L_{π}.

Similarly no point in the L_{π}-orbit of z is a turning point of L_{π}. Since π is a permutation, z is not in the orbit of a turning point of L_{π}. Then by Lemma 3.9, z ∉ P.

Let p ∈ B. Then p is L_{π}-periodic and hence g-periodic. Since p ≠ z, and Per(g) contains no odd number other than 1, it follows from [ALM, Lemma 2.1.6] that there exists z′ = z′(p) ∈ C, z′ not in the g-orbit of p, such that g(p) > z′ if p < z′, and g(p) < z′ if p > z′. Clearly z′ may be chosen to be a fixed point of g. Therefore we may choose z′(p) = z for all p ∈ B and (∗) is estabished.

It follows from (∗) and the remark immediately preceding Theorem 4.3 that π has a block structure over a simple cycle of length 2^{k}. Since π is a permutation, the blocks all have the same number of points. If this number were one or two, then by Theorem 1.8, the Sharkovskiĭ-largest period of π would be 2^{k} or 2^{k+1}. Since this is not the case, every block contains three points, i.e., (1) holds.

Finally, we show that (2) holds. Proceeding by contradiction, suppose that there is a pair of adjacent points, p_{j} and p_{j+1}, in the same block, such that for every i, 1 ≤ i ≤ 2^{k+1}, π^{i}(p_{j}) and π^{i}(p_{j+1}) are adjacent points. Without loss of generality, we may assume that the block which contains p_{j} and p_{j+1} is {p_{j}, p_{j+1}, p_{j+2}}. It follows from Lemma 3.7 that {π^{2^{k}}(p_{j}), π^{2^{k}}(p_{j+1})} = {p_{j+1}, p_{j+2}}, and hence that {π^{2^{k}}(p_{j+1}), π^{2^{k}}(p_{j+2})} = {p_{j}, p_{j+1}}. Therefore, π is monotone on every block, π^{2^{k}}(p_{j}) = p_{j+2}, π^{2^{k}}(p_{j+1}) = p_{j+1}, and π^{2^{k}}(p_{j+2}) = p_{j}. Then, by Theorem 1.8, the Sharkovskiĭ-largest period of π is 2^{k+1}. This is a contradiction, and so (2) holds. □

It follows from Theorem 5.3 that every cyclic permutation which satisfies (1) is a minimal permutation model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}.” On the other hand, there are non-cyclic minimal permutation models. For example, the permutation ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 4 & 6 & 2 & 3 & 1 \end{matrix} ) is a minimal permutation model for “Per(f) = \{t : t ≤_{S} 6\}.”

Theorem 5.4. The minimal combinatorial models for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}, k ≥ 1” are the self-maps π of finite ordered sets of cardinality 3 · 2^{k−1} + 1 which satisfy (1), (2), (3), and (4).

(1) π has a block structure over a simple cycle of length 2^{k−1}.

(2) There is a block B with four points, and every other block has three points.

(3) π is strictly monotone on every block other than B.

(4) π^{2^{k−1}}|_{B} is equivalent to ( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 3 & 1 \end{matrix} ) or ( \begin{matrix}1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 2 \end{matrix} ).

Proof. First, suppose that π : P → P, #π = 3 · 2^{k−1} + 1, and π satisfies (1), (2), (3), and (4). Let P = {p_{1} < p_{2} < ⋯ < p_{3·2^{k−1}+1}}, and let the exceptional block be B = {p_{m}, p_{m+1}, p_{m+2}, p_{m+3}}. Let V_{m}, V_{m+1}, V_{m+2} be the corresponding block vertices in the Markov graph of π.

Number the blocks B_{1} = B, and the remaining blocks B_{2}, B_{3}, …, B_{2^{k−1}}, so that π(B_{i}) ⊆ B_{i+1}, where B_{2^{k−1}+1} = B_{1}. Without loss of generality, π^{2^{k−1}}|_{B_{1}} is equivalent to ( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 3 & 1 \end{matrix} ). Then it follows from (3) that the endpoints of B_{2} are π(p_{m+3}) and π(p_{m+1}), and that π(p_{m}) = π(p_{m+2}) is the midpoint of B_{2}. Moreover, π maps the endpoints of B_{2^{k−1}} onto {p_{m}, p_{m+3}}, and maps the midpoint of B_{2^{k−1}} to p_{m+2}.

It follows that in the Markov graph of π there are walks of length 2^{k−1} from V_{m} to V_{m+2}, from V_{m+1} to V_{m+2}, from V_{m+2} to V_{m}, and from V_{m+2} to V_{m+1}, and no other walks of length 2^{k−1} between these vertices. Since by (1), every primitive closed walk which passes through only gap vertices has length a power of 2, it follows that the Sharkovskiĭ-largest length of a primitive closed walk is 3 · 2^{k}. As the only subcycle of π has length 2^{k−1}, it follows from Theorem 1.8 that Per(π) = {t : t ≤_{S} 3 · 2^{k}}.

To complete the proof, suppose that π : P → P is a minimal combinatorial model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}, k ≥ 1.” By Theorem 3.3, π is reduction- and restriction-minimal. Also, since 3 · 2^{k−1} ∉ Per(π), the 2^{k−1}-st power of the Markov graph of π does not have a horseshoe. Hence, by Theorem 4.3, (1) holds.

To show that (2), (3), and (4) hold, first consider the case k ≥ 2. By Lemma 3.5, π has no flat blocks. In particular, each block has at least two points. Suppose that some block has exactly two points, and let V denote the corresponding block vertex in the Markov graph of π. At least one block has more than two points, otherwise Per(π) would consist only of powers of 2. It follows from Lemma 3.7 that there are two distinct primitive closed walks of length 2^{k−1} from V to itself. By Theorem 1.8, 3 · 2^{k−1} ∈ Per(π). Since this is a contradiction, each block contains at least three points.

By the first part of the proof, #π ≤ 3 · 2^{k−1} + 1. Since k ≥ 2, there is a block B with exactly three points. Let V′ and V′′ be the corresponding block vertices in the Markov graph of π. It follows from Lemma 3.7 that there are walks of length 2^{k−1} from V′ to V′′, and from V′′ to V′. Since 3·2^{k−1} ∉ Per(π), it follows from Theorem 1.8 that

(∗) there are no closed walks of length 2^{k−1} from V′ to itself, or from V′′ to itself.

In light of (∗), and the fact that π has no flat blocks, we see that π cannot map the midpoint of B to an endpoint of another block. From this, and Lemma 3.7, we have

(∗∗) π|_{B} is strictly monotonic and maps the endpoints of B to the endpoints of another block.

Since 3·2^{k} ∈ Per(π), it follows from (∗∗) and Theorem 1.8 that at least one block has more than three points. On the other hand, since π is a minimal combinatorial model, it follows from the first part of the proof that #π ≤ 3·2^{k−1}+1. Hence, there is exactly one block with four points, i.e., (2) holds. Since (3) follows from (∗∗), it remains to prove (4).

Number the blocks B_{1}, B_{2}, …, B_{2^{k−1}}, so that B_{1} has four points, and π(B_{i}) ⊆ B_{i+1}, where B_{2^{k−1}+1} = B_{1}. It follows from (∗) and Lemma 3.7 that π maps adjacent points of B_{1} to adjacent points of B_{2}. So π maps one endpoint of B_{1} to an endpoint of B_{2}, and the other endpoint of B_{1} to the midpoint of B_{2}. Write B_{1} = {a < b < c < d}. We may assume that π(d) is an endpoint of B_{2}. Write B_{2} = {u, v, w}, where w = π(d), and u is the other endpoint of B_{2}. Then, using Lemma 3.7, we have π(a) = π(c) = v, and π(b) = u. Write B_{2^{k−1}} = {x, y, z}, where π^{2^{k−1}−2}(u) = x, π^{2^{k−1}−2}(v) = y, and π^{2^{k−1}−2}(w) = z. By (∗∗), π{x, z} = {a, d}. If π(x) = a and hence π(z) = d, we obtain a contradiction to Lemma 3.7. Therefore, π(x) = d and π(z) = a.

Suppose that π(y) = b. If V is the block vertex corresponding to the adjacent points x and y in B_{2^{k−1}}, there is a closed walk of length 2^{k−1} from V to itself. This contradicts (∗). Hence π(y) = c. Therefore π^{2^{k−1}}(a) = c, π^{2^{k−1}}(b) = d, π^{2^{k−1}}(c) = c, and π^{2^{k−1}}(d) = a, i.e., (4) holds.

Finally, we consider the case k = 1. It suffices to show only that (4) holds, i.e., that π|_{B} is equivalent to ( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 3 & 1 \end{matrix} ) or ( \begin{matrix}1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 2 \end{matrix} ). Since π is a minimal combinatorial model, it follows from the first part of the proof that #π ≤ 4. On the other hand, it is easy to see, using Theorem 1.8, that there are no combinatorial models for “Per(f) = {t : t ≤_{S} 6}” with fewer than four points. Therefore #π = 4. Write P = {p_{1} < p_{2} < p_{3} < p_{4}}. By Theorem 5.3, π is not a permutation, and by Lemma 3.7, p_{1} and p_{4} are in the image of π. So we may assume that p_{2} is not in the image of π. Now, by Lemma 3.5, π has no flat blocks. So, if the image of π were {p_{1}, p_{4}}, the Markov graph of π would have a horseshoe, implying that 3 ∈ Per(π). Therefore, the image of π is {p_{1}, p_{3}, p_{4}}.

We claim that π(p_{1}) ≠ p_{1}. If π(p_{1}) = p_{1}, then π(p_{2}) is either p_{3} or p_{4}. First, suppose that π(p_{2}) = p_{3}. Since p_{1} is in the orbit of a turning point of π, either π(p_{3}) = p_{1}, or π(p_{3}) = p_{4} and π(p_{4}) = p_{1}. In either case, there is a primitive closed walk of length 3 in the Markov graph of π. This is a contradiction. By a similar argument, π(p_{2}) = p_{4} leads to a contradiction. Therefore π(p_{1}) ≠ p_{1}, i.e., π(p_{1}) = p_{3} or p_{4}. Arguments similar to the ones above show that π(p_{1}) ≠ p_{4}. Therefore, π(p_{1}) = p_{3}.

Now, if π(p_{2}) = p_{1}, then V_{1} → V_{1} → V_{2} → V_{1} is a primitive closed walk of length 3, where V_{1} is the block vertex corresponding to {p_{1}, p_{2}}, and V_{2} is the block vertex corresponding to {p_{2}, p_{3}}. Therefore, π(p_{2}) = p_{4}. It follows similarly that π(p_{3}) = p_{3} and π(p_{4}) = p_{1}. □

Remark. The minimal combinatorial models for “Per(f) = {t : t ≤_{S} 3}” are the self-maps of finite ordered sets which are equivalent to one of the following: ( \begin{matrix}1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix} ),

( \begin{matrix}1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} ), ( \begin{matrix}1 & 2 & 3 \\ 1 & 3 & 1 \end{matrix} ), ( \begin{matrix}1 & 2 & 3 \\ 3 & 1 & 3 \end{matrix} ).

6. Sharkovskiĭ-largest period r · 2^{k}, r ≥ 5

In this section, we prove our last main result, Theorem 6.1, the characterization of the minimal combinatorial models for “Per(f) = {t : t ≤_{S} r · 2^{k}}”, r odd, r ≥ 5. The proof is entirely in terms of the Markov graph.

Theorem 6.1. Suppose that r ≥ 5 is odd. Then the minimal combinatorial models for “Per(f) = {t : t ≤_{S} r · 2^{k}}” are the simple cycles of length r · 2^{k}.

Corollary. Suppose that r ≥ 5 is odd. Then the minimal permutation models for “Per(f) = {t : t ≤_{S} r · 2^{k}}” are the simple cycles of length r · 2^{k}.

Proof of Theorem. Suppose first that π : P → P is a simple cycle of length r · 2^{k}. Then, by the

following [ALM, Corollary 2.11.2], Per(π) = {t : t ≤_{S} r · 2^{k}}. So to prove the theorem, it suffices to show that if π : P → P is a minimal combinatorial model for Per(f) = {t : t ≤_{S} r · 2^{k}}, then π is a simple cycle of length r · 2^{k}.

Suppose then that π : P → P is a minimal combinatorial model for Per(f) = {t : t ≤_{S} r · 2^{k}}. It follows from the preceding paragraph that #π ≤ r · 2^{k}. By Theorem 3.3, π is reduction- and restriction-minimal. Since 3 · 2^{k} is not a period of π, and since a continuous self-map of a compact interval which has a horseshoe must have a periodic point of period 3, it follows from Theorem 2.3 that the 2^{k}-th power of the Markov graph of π does not have a horseshoe. Hence, by Theorem 4.3, π has a block structure over a simple cycle of length 2^{k}.

By Theorem 1.8, either π is a cycle of length r · 2^{k}, or there is a primitive closed walk of length r · 2^{k} in the Markov graph of π. In the first case, it follows from [BCop, Theorem VII.11] that π is a simple cycle of length r · 2^{k}. Hence we may assume that there is a primitive closed walk W of length r · 2^{k} in the Markov graph of π.

In light of Theorem 1.8, we have the following:

(∗) There is no primitive closed walk of length s · 2^{k}, 1 < s < r, in the Markov graph of π.

We claim that every block in the block structure contains exactly r points. To prove the claim, it suffices to show that if a block B has at most r points, then it has exactly r points. Let D_{B} be the subgraph of the 2^{k}-th power of the Markov graph of π induced by the block vertices associated with the block B.

As in the proof of Theorem 5.3, the walk W passes through only block vertices. So, from W we obtain a closed walk W_{B} of length r in D_{B}.

If W_{B} contained only one vertex, then the 2^{k}-th power of the Markov graph of π would have a horseshoe. So W_{B} contains at least two vertices. On the other hand, since there are at most r − 1 vertices in D_{B}, W_{B} passes through some vertex twice. It follows that W_{B} is the concatentation of two shorter closed walks, one of which has odd length. However, it follows from (∗) that if s is odd and 1 < s < r, then in D_{B}, there is no closed walk of length s which passes through two distinct vertices. Thus W_{B} is the concatenation of a closed walk of length one and a closed walk of length r − 1, i.e., W_{B} is of the form

J_{1} → J_{1} → J_{2} → ⋯ → J_{r−1} → J_{1}.

It now follows that J_{1}, J_{2}, …, J_{r−1} are distinct — otherwise there would be a closed walk of odd length s, 1 < s < r, in D_{B} passing through two distinct vertices. In particular, there are at least r − 1 distinct vertices in D_{B}. Hence B contains at least r points, and the claim is proved.

It follows from the preceding paragraph and (∗) that the blocks may be numbered B_{1}, B_{2}, …, B_{2^{k}}, where π(B_{i}) ⊆ B_{i+1} and B_{2^{k}+1} = B_{1}, in such a way that the closed walk W has the form

J_{1,1} → J_{2,1} → ⋯ → J_{2^{k},1} →
J_{1,1} → J_{2,1} → ⋯ → J_{2^{k},1} →
J_{1,2} → J_{2,2} → ⋯ → J_{2^{k},2} →
⋯ → ⋯
J_{1,r−2} → J_{2,r−2} → ⋯ → J_{2^{k},r−2} →
J_{1,r−1} → J_{2,r−1} → ⋯ → J_{2^{k},r−1} → J_{1,1},

where for each i = 1, 2, …, 2^{k}, the distinct block vertices associated with the block B_{i} are J_{i,1}, J_{i,2}, …, J_{i,r−1}.

Recall that, if P = {p_{1} < p_{2} < ⋯ < p_{r·2^{k}}}, then the vertices V_{i} of the Markov graph of π are labelled so that V_{i} → V_{j} if and only if either π(p_{i}) ≤ p_{j} and π(p_{i+1}) ≥ p_{j+1}, or π(p_{i}) ≥ p_{j+1} and π(p_{i+1}) ≤ p_{j}.

Using (∗), we have that arcs in W are the only arcs in the Markov graph of π emanating from J_{1,1}, J_{2,1}, …, J_{2^{k},1}. In particular, {J_{1,1}, J_{1,2}} = {V_{i}, V_{i+1}} for some i. We may assume that J_{1,1} = V_{i} and J_{1,2} = V_{i+1}. It follows that π^{2^{k}}{p_{i}, p_{i+1}} = {p_{i}, p_{i+2}}.

We claim that π^{2^{k}}(p_{i}) = p_{i+2} and π^{2^{k}}(p_{i+1}) = p_{i}. Suppose not, i.e., π^{2^{k}}(p_{i}) = p_{i} and π^{2^{k}}(p_{i+1}) = p_{i+2}. Then π^{2^{k}}(p_{i+2}) > p_{i}, otherwise the 2^{k}-th power of the Markov graph of π would have a horseshoe. Since there is a walk of length 2^{k} in the Markov graph of π from J_{1,2} to J_{1,3}, but no such walk from J_{1,2} to J_{1,4}, J_{1,5}, … or J_{1,r−1}, we have J_{1,3} = V_{i+2} and π^{2^{k}}(p_{i+2}) = p_{i+3}. In the same way, it follows that B_{1} = {p_{i}, p_{i+1}, …, p_{i+r−1}}, J_{1,s} = V_{i+s−1} for s = 1, 2, …, r−1, and π^{2^{k}}(p_{j}) = p_{j+1} for j = i, i + 1, …, i + r − 2. Since π^{2^{k}}(p_{i+r−2}) = p_{i+r−1} and there is a walk of length 2^{k} from J_{1,r−1} = V_{i+r−2} to J_{1,1} = V_{i}, it follows that there are walks of length 2^{k} from J_{1,r−1} to each of the vertices J_{1,1}, J_{1,2}, …, J_{1,r−1}. In particular, there is a primitive closed walk of length 3 · 2^{k} in the Markov graph of π. This establishes our claim that π^{2^{k}}(p_{i}) = p_{i+2} and π^{2^{k}}(p_{i+1}) = p_{i}.

We claim next that if k ≠ 0, then the arc J_{1,2} → J_{2,2} is the only arc in the Markov graph of π emanating from J_{1,2}. If there were an arc from J_{1,2} to J_{2,1}, then the 2^{k}-th power of the Markov graph of π would have a horseshoe. If there were an arc from J_{1,2} to any of the vertices J_{2,3}, J_{2,3}, …, J_{2,r−1}, it would contradict (∗). Similarly, there is only one arc emanating from each of the vertices J_{2,2}, J_{3,2}, …, J_{2^{k}−1,2}.

Now, each of the maps π, π^{2}, …, π^{2^{k}−1} is monotone on {p_{i}, p_{i+1}, p_{i+2}}, π^{2^{k}}(p_{i}) = p_{i+2}, and π^{2^{k}}(p_{i+1}) = p_{i}. By (∗), there cannot be a closed walk of length 2^{k} from J_{1,2} to any of the vertices J_{1,1}, J_{1,4}, J_{1,5}, …, J_{1,r−1}, so we must have π^{2^{k}}(p_{i+2}) = p_{i−1}.

Similarly, we see that π is monotone on every block except B_{2^{k}}, p_{i+1} is the central point of B_{1}, and if θ = π^{2^{k}}|_{B_{1}}, then

θ^{r−2}(p_{i+1}) < θ^{r−4}(p_{i+1}) < ⋯ < θ^{3}(p_{i+1}) < θ(p_{i+1}) <

< p_{i+1} < θ^{2}(p_{i+1}) < ⋯ < θ^{r−3}(p_{i+1}) < θ^{r−1}(p_{i+1}).

Finally, since there is a walk of length 2^{k} from J_{1,r−1} to J_{1,1}, but by (∗), no such walk from J_{1,r−1} to J_{1,2}, we must have θ^{r}(p_{i+1}) = p_{i+1}.

Therefore, π is a simple cycle of length r · 2^{k}. □

7. Unimodal minimal combinatorial models

Recall that a self-map π of a finite ordered set {p_{1} < p_{2} < ⋯ < p_{n}} is unimodal iff for some m, 1 ≤ m ≤ n, π is (not necessarily strictly) increasing on {1, 2, …, m} and (not necessarily strictly) decreasing on {m, m+1, …, n}. Note that unimodality is a property of the equivalence class of π (see the definition in Section 1), and that π is unimodal if and only if every π-weakly monotone map is unimodal.

For all the properties considered in this paper, except “Per(f) = {t : t ≤_{S} 3·2^{k}},” k ≥ 1, the minimal combinatorial models are the simple cycles of the appropriate length. It is well-known that there is a unique unimodal simple cycle of every length. Using Theorem 5.4, it can be checked that there is a unique unimodal minimal combinatorial model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}},” k ≥ 1.

These may be constructed inductively, as follows. Let π_{1} = ( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 3 & 1 \end{matrix} ). Assume that k ≥ 1, and that π_{k} is the unique unimodal minimal combinatorial model for “Per(f) = {t : t ≤_{S} 3 · 2^{k}}.” Let θ_{k+1} be the “unimodal S̆tefan square root” of π_{k}. (See [BkhC] for how to take unimodal square roots of unimodal self-maps of finite ordered sets.) Then #θ_{k+1} = 3 · 2^{k} + 2, the turning point of θ_{k+1} is pre-periodic, but not periodic, and it has a unique pre-image under θ_{k+1}. The pre-image has no pre-images. Restricting θ_{k+1} to its domain with the pre-image deleted produces a unimodal map π_{k+1} with #π_{k+1} = 3 · 2^{k} + 1 and Per(π_{k+1}) = {t : t ≤_{S} 3 · 2^{k+1}}. By Theorem 5.4, π_{k+1} is a minimal combinatorial model.

References

[ALM] Ll. Alsedà, J. Llibre, and M. Misiurewicz, Combinatorial dynamics and entropy in dimension one, World Scientific, River Edge NJ, 1993.

[B] L. Block, Simple periodic orbits of mappings of the interval, Trans. Amer. Math. Soc. 254 (1979), 391–398.

[BCop] L. S. Block and W. A. Coppel, Dynamics in one dimension, Lecture Notes in Math., vol. 1513, Springer-Verlag, Berlin and New York, 1992.

[BCov] L. Block and E. M. Coven, Topological conjugacy and transitivity for a class of piecewise monotone maps of the interval, Trans. Amer. Math. Soc. 300 (1987), 297–306.

[BkhC] A. M. Blokh and E. M. Coven, Sharkovskiĭ type of cycles, Bull. London Math. Soc. 28 (1996), 417–424.

[MN] M. Misiurewicz and Z. Nitecki, Combinatorial patterns for maps of the interval, Mem. Amer. Math. Soc. 94 (1991), no. 456.

Louis Block, Deparment of Mathematics, University of Florida, Gainseville, FL 32611-8105

E-mail address: block@math.ufl.edu

Ethan M. Coven, Deparment of Mathematics, Wesleyan University, Middletown, CT 06459-0128

E-mail address: ecoven@wesleyan.edu

William Geller, Department of Mathematics, IUPUI, Indianapolis, IN 46202-3216

E-mail address: wgeller@math.iupui.edu

Kristin Hubner, Deparment of Mathematics, Wesleyan University, Middletown CT 06459-0128

Current address: Innosoft International Inc., 1050 Lakes Drive, West Covina CA 91790

E-mail address: kristin.hubner@sun.com