Sets of periods for piecewise monotone tree maps

SETS OF PERIODS FOR PIECEWISE MONOTONE TREE MAPS LL. ALSED` A Departament de Matem`atiques, Edifici Cc, Universitat Aut`onoma de Barcelona, 08913 Cerdanyola del Vall`es, Barcelona, Spain On leave at: Departament de Matem`atica Aplicada I, Universitat Polit`ecnica de Catalunya, Diagonal 647, 08028 Barcelona, Spain E-mail: alse[email protected] D. JUHER Departament d’Inform`atica i Matem`atica Aplicada, Universitat de Girona, Llu´ıs Santal´o s/n, 17071 Girona, Spain E-mail: [email protected] P. MUMBR´ U Departament de Matem`atica Aplicada i An`alisi, Universitat de Barcelona, Gran Via 585, 08071 Barcelona, Spain E-mail: [email protected] May 29, 2007 We study the set of periods of tree maps f:T−→ Twhich are monotone between any two consecutive points of a fixed periodic orbit P. This set is characterized in terms of some integers which depend only on the combinatorics of f|Pand the topological structure of T. In particular, a type p≥1 of Pis defined as a generalization of the notion introduced by Baldwin in his characterization of the set of periods of star maps. It follows that there exists a divisor kof the period of Psuch that if the set of periods of fis not finite then it contains either all the multiples of kp or an initial segment of the kp≥Baldwin’s ordering, except for a finite set which is explicitly bounded. Conversely, examples are given where fhas precisely these sets of periods. 1. Introduction In this paper we deal with the problem of determining which are the possible sizes of the periodic orbits that appear by iterating a continuous map defined on a tree. For some particular cases (interval and star), several well known results establish that if a continuous map exhibits a periodic orbit which verifies some combinatorial properties then we can determine a set which is a lower bound of the set of periods of the map. The widely known Sharkovskii’s Theorem (see [Sharkovskii, 1964]) studying the set of periods of any continuous map from an interval of the real line into itself was the first remarkable result in this setting. In order to state it, we introduce the Sharkovskii ordering D(the symbols E,⊳and ⊲ will be understood in the natural way) in the set N∪ {2∞}: 1 2Ll. Alsed`a, D. Juher, P. Mumbr´u 3D5D7D...D2·3D2·5D2·7D...D4·3D 4·5D4·7D...D...D2n·3D2n·5D2n·7D...D 2∞D...D2nD...D16 D8D4D2D1. The Sharkovskii’s theorem states that if an interval map fhas a periodic orbit of period mthen fhas periodic orbits of period kfor each mDk. As a consequence, it can be shown that for each interval map fthere exists some n∈N∪ {2∞}verifying that the set of periods of fis exactly the set of integers ksuch that nDk. Conversely, given any n∈N∪ {2∞}there exists an interval map gwhose set of periods is the set of all integers ksuch that nDk. During the last three decades there have been several attempts to find results similar to that of Sharkovskii for 1-dimensional spaces other than the interval (see for instance [Alsed`a et al., 1989] about maps on Yor [Efremova, 1978], [Block et al., 1980], [Block, 1981] and [Misiurewicz, 1982] about circle maps). More recently, the case of maps defined on trees has been specially treated. In [Baldwin, 1991] the characterization of the set of periods of any continuous map defined on an r-star (a tree with redges and rendpoints) is given in terms of finitely many partial orderings. Let us define the Baldwin partial orderings p≥for all p∈N(the symbols <p,≤pand p>will be understood in the natural way). If p= 1 then p≥is the Sharkovskii ordering. For p > 1 and k, m ∈N∪ {p2∞}, we write mp≥kif one of the following cases holds: (i) k= 1 or k=m (ii) k, m ∈pN∪ {p2∞}and m/p ⊲k/p (iii) k∈pN∪ {p2∞}and m /∈ {1} ∪ pN∪ {p2∞} (iv) k, m /∈ {1}∪pN∪{p2∞}and k=im+jp with i, j ∈N where the arithmetic rule p2∞/p = 2∞is assumed and pNstands for {pn :n∈N}. It is not difficult to see that 2≥also coincides with the Sharkovskii ordering. In Baldwin’s paper, a positive integer is associated to each periodic orbit Pof an r-star map f. This integer is called the type of Pand depends only on the combinatorics of f|P(in Sec. 4 a precise definition is given for a general tree map). Baldwin proves that if fhas a periodic orbit of period m and type pthen fhas periodic orbits of period k for each mp≥k. An initial segment of the ordering p≥is defined to be any set Ssuch that if m∈ S and mp> k then k∈ S. Baldwin proves that the set of periods of any r-star map is a union of finitely many initial segments of the orderings p≥for 1 ≤p≤r. Conversely, given such a union Athere exists an r-star map whose set of periods is A. In what follows, any continuous map from a tree into itself will be called a tree map. The characterization of the set of periods for any tree map f:T−→ Tin terms of some constants which depend on the topological structure of T(such as the amount of vertices or endpoints of T) is yet an open problem. However, there are some partial results in this direction (see, for instance, [Imrich & Kalinowski, 1985a,b], [Alsed`a & Ye, 1995], [Llibre & Misiurewicz, 1993] and [Blokh, 1992]). A natural strategy to obtain this kind of characterization for interval and star maps, that already has been used in the proofs of Sharkovskii and Baldwin theorems, is the following one. Assume that f is an interval map or an r-star map and let Pbe a periodic orbit of f. The first stage of the strategy consists of studying the subset ΛPof periods of f which are forced by the pattern of P. That is, one wants to know which other orbits the map fwill necessarily have, depending only on the combinatorics of f|P. To solve this problem one replaces fby another map gsuch that g|P=f|Pand gis monotone between any two consecutive points of P. It can be seen that such a map is the dynamically simplest model which exhibits an orbit having the pattern of P. This means that each pattern exhibited by gis also exhibited by fand that the set ΛP coincides with the set of periods of g. Therefore, the set ΛPcan be computed just by studying the loops of the Markov graph of g. The last step of the proof consists in considering each orbit Pof f and its associated ΛP. Then one gets the structure of the set of periods of fby obtaining the structure of the (uncountable) union of all sets ΛP. This is done by purely number-theoretical arguments. As it has been said before, an important intermediate step in getting the periodic structure of interval and star maps is the study of the set of periods of these (piecewise monotone) “dynamically simplest models”. Since, in addition, piecewise monotone maps provide all the necessary ex- Sets of periods of piecewise monotone tree maps 3 amples in the “converse part” of the theorems of Sharkovskii and Baldwin, the proofs of these results are strongly based on the study of this class of maps. To study the set of periods of tree maps we have chosen to follow a strategy similar to the one described above (as we shall see, this is a natural strategy also in the case of tree maps). However, it turns out that the straightforward implementation of this strategy to tree maps does not work. Indeed, let f:T−→ Tbe a tree map, let Pbe a periodic orbit of fand let Vdenote the set of vertices of T. Then we want to consider a P-weakly monotone map gwhich is defined to coincide with fon V∪P and is monotone (injective) on the closure of each connected component of T\(V∪P). The problem is that a P-weakly monotone map can have (even infinitely many) periods which are not periods of f, and thus it cannot be our desired “minimal model”. To illustrate this phenomenon consider the following simple example in the case of interval maps. Example 1.1. Let g: [0,1] −→ [0,1] denote the tent map such that the point 1/2 is a periodic point of period 3. That is: g(x) = (µx when x∈[0,1/2], µ(1 −x) when x∈[1/2,1], with µ=1+√5 2. This map has periodic points of all periods. Set p=g(1/2) = 1+√5 4and let f: [0,1] −→ [0,1] be the continuous map such that f(0) = f(1) = 0, f(x) = pfor each x∈[1 −p, p] and fis affine on [0,1−p] and [p, 1]. Clearly, p is a fixed point of fand 1 is the only period of f. Now consider T= [0,1] as a 2-star with vertices V={0,1/2,1}and suppose that we are given the map fwith P={0}. The map gcoincides with fon V∪Pand is monotone (injective) on the closure of each connected component of T\(V∪P) (so, gis P-weakly monotone). However the map g has periodic points of all periods whereas the map fonly has fixed points. The above example tells us that it is not straightforward to extend the notion of “minimal model” (or “P-minimal map”) to the setting of tree maps. However, in [Alsed`a et al., 1997] the authors give a definition of pattern of Pand prove that there always exists a tree SPand a map gP:SP−→ SP exhibiting a periodic orbit Qwith the same pattern as Pand displaying dynamic minimality properties similar to the known ones for the interval case. The crucial point is that the map gPis Q-monotone which means that it is monotone between any two consecutive points of Q(two points a, b of Qare said to be consecutive if there are no other points of Qin the convex hull of {a, b}). We also remark that the tree SP, which may be different from T, is unique up to homeomorphisms and collapse of invariant forests. The map gP, which is the crucial tool in our strategy, is called a P-minimal model. As an example consider the maps fand gdefined in Fig. 1: It turns out that the orbits Pand Qhave the same pattern (even living in two different trees) and that the map gis the minimal model corresponding to this pattern. Observe also that the notion of Qmonotonicity is stronger than the notion of Q-weak monotonicity. To see it, consider the map fdefined in Fig. 1 and observe that there does not exist any P-monotone map ϕ:T−→ Twhich coincides with fon the set P. Such a map ϕwould have to satisfy ϕ([x1, x2]) = [x2, x3] and ϕ([x3, x5]) = [x4, x6]. Thus ϕ(z)∈[x2, x3]∩[x4, x6]; a contradiction. Now we are ready to describe the implementation of the strategy we use to study the set of periods of tree maps: (1) For each periodic orbit Pof fcalculate ΛP, the set of periods of the corresponding Pminimal model gP:SP−→ SPor, if this is not possible, estimate the largest possible subset of ΛP. (2) Prove that the set of periods of the P-minimal model gPis contained in the set of periods of each tree map which exhibits an orbit with the pattern of P. In particular, ΛPis a subset of the set of periods of f. (3) Consider each orbit Pof fand its associated ΛP. Then one can obtain the structure of the set of periods of fby describing the structure of the (uncountable) union of all sets ΛP. The main result of this paper performs step (1) of the above program by means of the study of the Markov graph of gP. Indeed, given any tree map g:S−→ Shaving a periodic orbit Qand such that gis Q-monotone, we use information from the combinatorics of g|Qand the topological structure of Sin order to study the Markov graph of gand compute as large as possible subsets of the set of 4Ll. Alsed`a, D. Juher, P. Mumbr´u 01 01 01 01 01 01 01 01 01 00 00 00 00 11 11 11 11 00 00 00 00 11 11 11 11 0 0 0 0 0 1 1 1 1 1 000111 000 000 000 111 111 111 0000 0000 0000 0000 1111 1111 1111 1111 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 01 01 01 01 01 01 01 y1 y3 y5 y4 v v′ y2 y6 v′′ x1x4 x6 x5 x2 x3 z Fig. 1. Left figure: A tree Tand a map f:T−→ Twhich exhibits an orbit P={x1, x2,...,x6}with f(xi) = xi+1 for 1 ≤i≤5 and f(x6) = x1. This map can be made P-weakly monotone by setting f(z)∈P∪ {z}but it cannot be made P-monotone. Right figure: A tree Sand a map g:S−→ Shaving an orbit Q={y1, y2, . . . , y6}with g(yi) = yi+1 for 1≤i≤5 and g(y6) = y1. If in addition we take g(v) = v′,g(v′) = v′′ and g(v′′) = y5then gcan be made Q-monotone (and thus Q-weakly monotone). periods of g. Moreover, examples are given where the difference between the whole set of periods and these subsets is finite and explicitly bounded. Since in general Tand SPdiffer (unless Tis an interval or a star) it is not easy to carry out steps (2) and (3) of the above program. These two steps will be matter of a forthcoming paper by the same authors. 2. Basic Definitions and Statement of the Main Results Let Xbe a topological space and let f:X−→ X be a map. As usual, f0= Id and fk=f◦f◦· · ·◦f (ktimes) for k∈N. For a finite set Awe will denote its cardinality by |A|. Given a point x∈X we define its orbit, denoted by Orbf(x) (or simply by Orb(x)), to be the set {fk(x) : k= 0,1,2,...}. If |Orb(x)|=n, then fk(x)6=xfor 0 < k < n and fn(x) = x. In this case we say that xis a periodic point of fof period n(or an n-periodic point of f) and that Orbf(x) is a periodic orbit of fof period n(or an n-periodic orbit of f). A point of period 1 is called a fixed point, and the set of fixed points of fwill be denoted by Fix(f). The set of periods of f, denoted by Per(f), is the set of periods of all periodic orbits of f. Given a point x∈X, we say that xis eventually periodic if it is not periodic but fn(x) is periodic for some n > 0. If A⊂Nand m, n ∈N,nA stands for {nk :k∈A}and m+nA stands for {m+nk :k∈A}. Atree is a compact uniquely arcwise connected space which is a point or a union of a finite number of intervals (from now on, by an interval we mean any space homeomorphic to [0,1]). Any continuous map from a tree into itself will be called a tree map. If Tis a tree and x∈T, we define the valence of xto be the number of connected components of T\{x}. Each point of valence 1 will be called an endpoint of Tand the set of such points will be denoted by En(T). Each point of valence different from 2 will be called a vertex of Tand the set of vertices of Twill be denoted by V(T). As usual, the closure of each connected component of T\V(T) will be called an edge of T. Any tree which is a union of r > 1 intervals whose intersection is a unique point xof valence rwill be called an r-star, and xwill be called the central point. If Xis a topological space and f:X−→ Xis a map, we will say that a set A⊂Xis f-invariant if f(A)⊂A. For a set B⊂Xwe will denote by Int(B) and Cl(B) the interior and the closure of B respectively. Let Sbe a tree. Given P⊂Swe will define the convex hull of P, denoted by hPiSor simply by hPi, as the smallest closed connected subset of Scontaining P. When P={x, y}we will write hx, yior [x, y] to denote hPi. The notations (a, b), (a, b] and [a, b) will be understood in the natural way. Let g:S−→ Sbe a tree map. Given a, b ∈S we say that g|[a,b]is monotone if either g([a, b]) is a point or it is an interval and, given two homeomorphisms φ: [0,1] −→ [a, b] and ϕ:g([a, b]) −→ [0,1], then ϕ◦g◦φ: [0,1] −→ [0,1] is monotone (as a real Sets of periods of piecewise monotone tree maps 5 function). If P⊂Sis a finite g-invariant set which contains En(S), we say that gis P-monotone if g([a, b]) = [g(a), g(b)] and g|[a,b]is monotone whenever [a, b]∩P={a, b}. In this case we will say that the triplet (S, P, g) is a monotone model. If in addition Pcontains a unique periodic orbit and this orbit consists of a fixed point, then we will say that (S, P, g) is a trivial model. Observe that if (S, P, g) is a trivial monotone model and Pconsists of a fixed point then Sreduces to the unique point of Psince En(S)⊂P. Remark 2.1. If (S, P, g) is a monotone model, it is shown in Proposition 4.2 of [Alsed`a et al., 1997] that the image of each vertex zis uniquely determined and is either a vertex or belongs to P. In fact, if a, b, c ∈Pin such a way that z∈[a, b]∩[a, c]∩[b, c] and h{a, b, c}iS\Pis connected, then it can be easily seen that g(z) is the only point contained in g([a, b]) ∩g([a, c]) ∩g([b, c]). Let (S, P, g) be a monotone model and let Q= P∪V(T). Observe that each connected component of T\Qis an interval. By Remark 2.1, Qis g-invariant. It is not difficult to see that gis monotone on each connected component of T\Q. In this situation, we can consider the usual notion of the Markov graph of g, whose vertices are closures of connected components of T\Qand there is an arrow from Kto Lif and only if g(K)⊃L. It is folk knowledge that there is a certain correspondence between periodic orbits of gand loops of its Markov graph (see Sec. 3). Now we informally sketch the strategy that we use in this paper in order to calculate the set of periods of a monotone model. Let (S, P, g) be a non-trivial monotone model such that Pis a periodic orbit of g. The basic tool we use to obtain periodic points of gis the existence of a special kind of loops in the Markov graph of g, which we call external loops (see Sec. 4). The set of external loops in the Markov graph of gwhich in addition verify certain technical properties will be denoted by ˜ E(S, P, g). If ˜ E(S, P, g)6=∅then Per(g) is directly calculable (see Lemma 4.6 and Theorem 4.7). If ˜ E(S, P, g) = ∅then we proceed as follows. Set (S1, P1, g1) = (S, P, g). We prove that there exist p1∈Nand a monotone model (S2, P2, g2) such that S2⊂S1,g2=gp1 1|S2and Per(g1)⊃p1Per(g2). Such a monotone model is called a partial p1reduction of (S1, P1, g1). If we are able to compute Per(g2), then the estimation p1Per(g2) for the set of periods of g1is optimal, since we know examples verifying Per(g1) = p1Per(g2). So the problem of estimating Per(g1) is reduced to compute Per(g2). If ˜ E(S2, P2, g2) = ∅, we can iterate this procedure. In Sec. 6 it is shown that we can proceed in this way as many times as necessary in order to obtain a finite sequence of monotone models {(Si, Pi, gi)}m i=1 such that: (i) (S1, P1, g1) = (S, P, g). (ii) (Si+1, Pi+1, gi+1) is a pi-partial reduction of (Si, Pi, gi) for 1 ≤i < m. (iii) Picontains a unique periodic orbit Pi◦and |P◦ i|=pi|P◦ i+1|for 1 ≤i < m. Moreover, Pi◦⊂Pi+1 Piwhen pi= 1. (iv) ˜ E(Si, Pi, gi) = ∅for 1 ≤i < m. (v) Either (Sm, Pm, gm) is a trivial model or it verifies ˜ E(Sm, Pm, gm)6=∅. Since Per(gi)⊃ {1} ∪ piPer(gi+1), we can easily get that Per(g)⊃ {1, p1, p1p2,...,p1p2···pm−1} ∪ p1p2···pm−1Per(gm). Furthermore, since P= P1=P◦ 1, we have that |P|=p1p2···pm−1|P◦ m|. We remark that such a sequence of partial reductions of (S, P, g) is not unique. By means of the above construction, a complete reduction of (S, P, g) is defined to be the pair {R, K}where K={1, p1, p1p2,...,p1p2···pm−1} and R= (Sm, Pm, gm). Note that if ˜ E(S, P, g)6=∅ then m= 1 and thus Kreduces to {1}. The model Rwill be called a completely reduced model of (S, P, g). It satisfies: (i) gm=gmax K|Sm. (ii) Pmcontains a unique periodic orbit Pm◦and |P|=|Pm◦| · max K. (iii) Per(g)⊃K∪(max K)·Per(gm). Since there exist many sequences of partial reductions, a complete reduction of (S, P, g) is not uniquely determined. By (iii), the study of the set of periods of a monotone model can be reduced to the study of the set of periods of its completely reduced models. This is the strategy we use in this paper and it gives rise to our main result. In order to state it, we need to introduce some more notation. Let R= (S, P, g) be a non-trivial completely reduced model of a given monotone model (S, P, g). 6Ll. Alsed`a, D. Juher, P. Mumbr´u We will prove that Per(g) depends on three nonnegative constants (besides |P◦|, of course). These constants can be directly calculated from the combinatorics induced by gon the g-invariant set P∪ V(S). Since these numbers strongly depend on the topological structure of the tree Sand the behavior of gon P, we denote them by n(R), p(R) and q(R) in order to stress their dependence from the model. The constant n(R) is the minimum integer nsuch that gn(P) = P◦. On the other hand, p(R) is called a type of the model, and essentially is a generalization of the notion of type of a periodic orbit introduced in [Baldwin, 1991] for star maps. Finally q(R) will be called the rotation index of the model. The precise definition of these constants is given in Sec. 4. Next we introduce a notation to deal with a special type of initial segments of the p≥orderings. If p∈Nand r∈N∪ {p2∞}, we define Sp(r) = {k∈N:rp≥k}. Note that if r∈pNthen Sp(r) = {1} ∪ p{k∈N:r/p Dk}and if r /∈pN then Sp(r) = {1, r}∪{ri+pj :i≥0, j ≥1}. Given p, r ∈N, we define S∗ p(r) = Sp(r) if r /∈pN Sp(3p) if r∈pN Observe that if r∈pNthen S∗ p(r) = pN∪ {1} ⊃ Sp(r). Remark 2.2. Let k, p, r be natural numbers. Then we have that {1}∪kS∗ p(r) = {k}∪S∗ kp(kr). Indeed, if r /∈pNthen {1} ∪ kS∗ p(r) = {1} ∪ k({1, r} ∪ {ri + pj :i≥0, j ≥1}) = {1, k, kr} ∪ {kri +kpj :i≥ 0, j ≥1}={k}∪S∗ kp(kr). On the other hand, when r∈pNwe get {1} ∪ kS∗ p(r) = {1} ∪ k(pN∪ {1}) = {1, k} ∪ kpN={k} ∪ S∗ kp(kr). From now on, we take {1,2,...,n}as the representatives of the classes of Z/nZ. Now we are ready to state the main results of this paper. Theorem A. Let (S, P, g)be a monotone model such that Pis a periodic orbit of g. If Pconsists of a fixed point of gthen Per(g) = {1}. Otherwise, there exist complete reductions of (S, P, g). For any complete reduction {R, K}of (S, P, g), we have that Per(g)⊃K. If, in addition, Ris non-trivial and we denote p(R),q(R),n(R)and max Kby p,q,n and krespectively, then Per(g)⊃K∪ S∗ kp(|P|+lkp)\ {2kp, 3kp, . . . , λkp} for some 0≤λp ≤|P| k+p+q+n+ 1 and some 0≤l≤|P| k+q+ 1. Furthermore, if n= 0 then lp ≤p+q−(qmod p). The periods computed in the proof of Theorem A correspond to periodic orbits which do not intersect the set V(S) of vertices of S. We additionally prove (see Corollary 6.8) that Per(g) contains a finite set Vwhose elements divide the least common multiple of the periods of all periodic orbits contained in V(S). Remark 2.3. When |P| ∈ kpNthe upper bound for lin Theorem A is irrelevant, since S∗ kp(|P|+lkp) = kpNfor any l. On the other hand, when |P|/∈kpN the upper bound for lcontrols how far S∗ kp(|P|+lkp) is from S∗ kp(|P|). Indeed, it is easy to check that S∗ kp(|P|)\ S∗ kp(|P|+lkp) = {i|P|+jkp : 1 ≤i < kp, 1≤j≤il}. Sometimes a continuous self–map of a compact space is called chaotic if it has positive topological entropy (see [Denker et al., 1976] for a definition). Then it can be derived from Theorem E of [Llibre & Misiurewicz, 1993] and Theorem A that if Ris a non-trivial model then gis chaotic. And conversely, it is not difficult to see that if gis not chaotic then Per(g) must be finite (this is true only for monotone models). Thus the monotone models with a trivial (respectively non-trivial) completely reduced model correspond to zero entropy (resp. chaotic) maps. We must stress the fact that there are some known results which describe the set of periods of some kinds of tree maps except for a finite set of periods (see for instance [Blokh, 1991] and [Alsed`a & Ye, 1995]). Nevertheless, nothing is said usually about this finite set. Theorem A states that the set of periods of a (chaotic) monotone model contains a set Cwhich is S∗ kp(|P|) except for an explicitly bounded finite set of periods. In fact, from Remark 2.3 it follows that S∗ kp(|P|)\ C is exactly {2kp, 3kp, . . . , λkp}if |P| ∈ kpNand {2kp, 3kp, . . . , λkp} ∪ {i|P|+jkp : 1 ≤i < kp, 1≤ j≤il}otherwise. Thus the difference between Cand S∗ kp(|P|) depends on the constants λand Sets of periods of piecewise monotone tree maps 7 l, which depend on combinatorial data extracted from the model by means of the constants qand n. The smaller qand nare, the bigger (and closer to S∗ kp(|P|)) Cis. A natural question arises: how accurate is the estimation of Per(g) given by Theorem A in relation to Sharkovskii and Baldwin theorems when S is an interval or a star? Given r∈N, let us write Sh(r) for the initial segment of Sharkovskii’s ordering starting at r. That is, Sh(r) = {s∈N:rDs}. Suppose that Sis an interval and |P|=t·2s with todd and s > 1. Assume in addition that P has no division (see for instance [Li et al., 1982]). Then from the proof of Theorem A one gets that (S, P, g) admits a complete reduction {R, K}with R= (S, P, g), K={1},q=n=l= 0 and p∈ {1,2}. If p= 1 then Theorem A states that Per(g)⊃N\ {2,3,...,λ}. When p= 2, we get Per(g)⊃2N\ {4,6,...,2λ}. In both cases, these sets contain infinitely many periods which are not in Sh(t·2s). Theorem A can provide more information than Sharkovskii’s theorem, since in our result other combinatorial features of the orbit P, besides its period, are taken into account. This goes in the direction of the main result of [Li et al., 1982], Baldwin’s theorem and other several results in the same spirit (see [Misiurewicz & Nitecki, 1991] or [Alsed`a & Ye, 1995]). Assume that Sis an interval and Pis a primary orbit (see [Baldwin, 1987] or [Alsed`a et al., 1989]) of period t·2swith todd and s≥0. Then Per(g) = Sh(t·2s), and it is not difficult to see that (S, P, g) admits a complete reduction {R, K}such that K= {1,2,22,...,2s}and Ris a trivial model if and only if t= 1. If Ris trivial then Theorem A states that Per(g)⊃K={1,2,22,...,2s}= Sh(2s). On the other hand, when Ris not trivial from the proof of Theorem A one gets that q=n=l= 0, k= 2s, p= 2 and λ=t−1 2. Hence Theorem A states that Per(g)⊃K∪ S∗ 2s+1 (t·2s)\ {2·2s+1,3·2s+1,...,t−1 2·2s+1} ={1,2,22,...,2s} ∪ {t·2s} ∪ 2s{ti + 2j, i ≥0, j ≥1} \ {2·2s+1,3·2s+1,...,t−1 2·2s+1}. It is not difficult to show that this set is exactly Sh(t·2s)\ {2·2s+1,3·2s+1,...,t−1 2·2s+1}. A similar calculus can be done when Sis an rstar (with r≥3) and Pis a primary orbit. Some of these computations are shown in Table 1. When |P|/∈rNthen gis the (|P|, r)-spiral map (see [Baldwin, 1991]). Thus, when Sis an interval or a star, in some cases Theorem A misses out the subset of periods {2kp, 3kp, . . . , λkp}. Nevertheless, in these cases it can be shown that gkp exhibits a horseshoe. Then it easily follows that Per(g)⊃kpN. In particular, Per(g)⊃ {2kp, 3kp, . . . , λkp}. The existence of this horseshoe is due to the (geometric) fact that there are no vertices of Sbetween consecutive points of P. For a general tree map it is not true that gkp has a horseshoe, and thus Per(g) does not necessarily contain kpN. Also the following natural question arises: do there exist monotone models whose set of periods contains exactly the periods of Theorem A and no other? Before answering this question, we must give the range of possible values of the constants p,q,n and kin Theorem A. We have that p≥1, q≥0 and n∈ {0,1,2}. Set r=|P|/k. In Corollary 8.2 we show that the values of pand qare bounded in terms of r. In particular, when n= 0 we have that p≤r−1, q+ 4 ≤rwhen p= 1 and 2p+q+ 1 ≤rwhen q > 0. (1) The answer to the above question is given by the following converse of Theorem A: Theorem B. Let K⊂Nbe a set of the form {1, k1, k2,...,km}such that k1>1and kistrictly divides ki+1 for 1≤i < m. Set k=km. Then: (a) There exists a monotone model (R, B, h)such that |B|=kand Per(h) = K. (b) Given any r > 1,p≥1and q≥0verifying (1), there exists a monotone model (S, P, g) and a complete reduction {(S, P, g), K}of (S, P, g)such that |P◦|=r,p(S, P , g) = p, q(S, P, g) = q,n(S, P , g) = 0 and Per(g) = K∪ C, where Cis a set such that S∗ kp(|P|+lkp)\ {2kp, 3kp, . . . , λkp} ⊂ C ⊂ S∗ kp(|P|) with lp =p+q−(qmod p)and λp being the largest multiple of psmaller than r+p+q+1. 8Ll. Alsed`a, D. Juher, P. Mumbr´u Table 1. Some examples of sets of periods given by Theorem A and Theorems of Sharkovskii and Baldwin. Model Complete reduction Sharkovskii’s or Baldwin’s Theorem Theorem A Sinterval, |P|=t·2s, todd, s > 1, no division R= (S, P, g), K={1}, q=n=l= 0, p∈ {1,2} Sh(t·2s)pN\ {2p, 3p, . . . , λp} S r-star, |P|=r·2s, Pprimary Rtrivial, K={1, r, 2r, 22r, . . . , 2sr}Sr(r·2s)Sr(r·2s) S r-star, |P|=rt ·2s, t > 1 odd, Pprimary Rnon-trivial, K={1, r, 2r, 22r, . . . , 2sr}, q=n=l= 0, p= 2, k= 2sr,λ=t−1 2 Sr(rt ·2s)Sr(rt ·2s)\r· {2·2s+1, 3·2s+1,...,t−1 2·2s+1} S r-star, |P|=s /∈rN, (s, r)-spiral map Rnon-trivial, K={1},q=n=l= 0, p=r,λ=s−(smod r) r Sr(s)Sr(s)\ {2r, 3r,...,s−(smod r)} In order to simplify the proof of Theorem B, we have considered only models for which n= 0. In fact, according to Theorem A, if one looks for a characterization of Per(g) up to a finite set then the values of qand nare irrelevant. This paper is organized as follows. In Sec. 3 we introduce the usual f-covering tools which relate the periodic orbits of a map and the loops of its associated Markov graph. In Sec. 4 we define a particular class of monotone models, which we call y-expansive, and we compute periodic orbits associated to the loops of the Markov graph of yexpansive models. In Sec. 5 we use the notion of a canonical model introduced in [Alsed`a et al., 1997]. From each monotone model (S, P, g) we construct a canonical model (S′, P ′, g′) and find a relation between Per(g) and Per(g′). Moreover, we prove that every canonical model is, in particular, y-expansive. This allows us to use the results of Sec. 4 for canonical models. In Sec. 7 we prove Theorem A for a monotone model (S, P, g). The complexity of the arguments of the proof depends strongly on the combinatorics of the g-invariant set P∪V(S) around a fixed point yof g. This combinatorics is studied in Sec. 6, where we define the notion of a twist model around a fixed point and we remark that if (S, P, g) is not a twist model around ythen the theorems of Sec. 4 can be directly used. The sets of periods of the twist models are studied in Sec. 6. In Sec. 8 we prove the inequalities (1). Finally Sec. 9 is devoted to prove Theorem B. 3. Markov Graphs and Periodic Orbits Let Tbe a tree and let Q⊂Tbe a finite set containing V(T). An interval of Twill be called Q-basic if it is the closure of a connected component of T\Q. Given f:T−→ Tand K, L ⊂T, we will say that K f-covers Lif f(K)⊃L. We will use the notation K→L(or Kf →Lif we want to specify the map) to denote that K f-covers L. In this setting, it makes sense to consider the (Markov) f-graph of Q, whose vertices are Q-basic intervals and, if I, J are Q-basic intervals, there is an arrow I→Jif Sets of periods of piecewise monotone tree maps 9 and only if I f-covers J. The results of this section are well known for interval and star maps and extend straightforwardly to the case of tree maps. However, we include some proofs for completeness. Lemma 3.1. Let f:T−→ Tbe a tree map. Assume that fis Q-monotone for a set Qcontaining V(T). Let K⊂Tbe a connected union of Q-basic intervals. Then for each Q-basic interval J⊂f(K) there exists a Q-basic interval I⊂Ksuch that I f-covers J. Proof. Note that Int(J)∩V(T) = ∅because Jis a Q-basic interval and V(T)⊂Q. Since fis continuous and Tis a tree, it follows that there exists an interval I′⊂Ksuch that f(I′) = J. Furthermore, since fis Q-monotone we can assume Int(I′)∩V(T) = ∅. Thus the lemma follows by taking a Q-basic interval Isuch that I′⊂I⊂K. Let f:T−→ Tbe a Q-monotone tree map, where Qis a set which contains V(T). There is a certain correspondence between periodic points of fand loops in the f-graph of Q. We will use the usual notions (see Chapter 1 of [Alsed`a et al., 2000] or [Block et al., 1980]): the concatenation of two loops αand βwill be denoted by αβ, and αn= αα . . . α (ntimes) will be called an n-repetition of α. A loop will be called elementary if it cannot be formed by concatenating two loops. A loop α is simple if it is not an n-repetition of any other loop with n≥2. The length of a loop αwill be denoted by |α|. If J0→J1→... →Jn−1→J0 is a loop αin the f-graph of Qand x∈Fix(fn) we say that xand αare associated if fi(x)∈Ji for 0 ≤i < n. In this case we also will say that Orb(x) and αare associated. We note that when xand αare associated the period of xcan be a strict divisor of |α|. As usual, to every arrow I→ Jin the f-graph of Qwe associate a sign which is +1 if f|Iis non-decreasing and -1 if it is nonincreasing. Then we say that the loop J0→J1→ ... →Jn−1→J0is positive if the product of the signs of the arrows J0→J1, J1→J2,...,Jn−1→ J0is +1 and negative if it is -1. Lemma 3.2. Let f:T−→ Tbe a tree map. Assume that fis Q-monotone for a set Qcontaining V(T). If Pis a periodic orbit of fsuch that P∩Q=∅, then there exists a loop αin the f-graph of Qsuch that Pand αare associated. Proof. Let x∈P. For each 0 ≤i < |P|, there exists a unique Q-basic interval Jisuch that fi(x)∈ Int(Ji). Since fis Q-monotone and V(T)⊂Q, it follows that Jif-covers Ji+1 for 0 ≤i < |P|−1 and J|P|−1f-covers J0. The next result follows easily from the ideas of Lemma 1.4 of [Block et al., 1980]. See also Lemma 2.1 of [Alsed`a et al., 2001]. Lemma 3.3. Let f:T−→ Tbe a tree map. Assume that fis Q-monotone for a set Qcontaining V(T). Let αbe a loop J0→J1→...→Jn−1→J0 in the f-graph of Q. Then there exist closed intervals Ki⊂Jifor 0≤i < n such that f(Ki) = Ki+1 for 0≤i < n −1and f(Kn−1) = J0. Moreover, there exists x∈Fix(fn)such that fi(x)∈Kifor 0≤i < n. In particular, xand αare associated. Remark 3.4. With the notation of Lemma 3.3, it is not difficult to see that fnis monotone on K0, and the loop is positive (respectively negative) if and only if fn|K0is non-decreasing (respectively nonincreasing). Under the hypotheses of Lemma 3.3, there exists a periodic point xassociated to α. Therefore, the loops of the f-graph of Qare useful to obtain periodic orbits of the map f. When doing this, the basic problem is to determine the exact period of the periodic point that one gets. The following result imposes some conditions on αin order to assure that the period of xcoincides with the length of α. Lemma 3.5. Let f:T−→ Tbe a tree map. Assume that fis Q-monotone for a set Qcontaining V(T). Let αbe a simple loop [a, b]→J1→J2→ ... →Jn−1→[a, b]in the f-graph of Q. Let xbe the periodic point given by Lemma 3.3. If x∈(a, b) then the period of xis n. This happens, in particular, when any of the following statements holds: (a) aand bare not fixed points of fn. (b) αis negative. Proof. We use the notation of Lemma 3.3. A standard argument (see for instance the first part of the 16 Ll. Alsed`a, D. Juher, P. Mumbr´u Remark 6.2. Let (T, A, f) be an orbital y-expansive model. By definition, Adoes not contain fixed points and thus y /∈A. Furthermore, since (T, A, f) is a monotone model, En(T)⊂A. Therefore, y /∈En(T) and it follows that n⋆≥2. On the other hand, from the fact that (T, A, f) is orbital we have that n⋆is either n◦or n◦+1, and n⋆=n◦+1 if and only if there exists a residual branch. In summary, we have: (i) n⋆≥2. (ii) n⋆∈ {n◦, n◦+ 1}, and there exists a residual branch if and only if n⋆=n◦+ 1. The next lemma establishes some properties of the type of Aywhen (T, A, f) is a twist model around y. Lemma 6.3. Let (T, A, f)be a y-expansive orbital model which is twist around y. Then Ayhas a unique type and it coincides with n◦. Proof. Assume that X(Ay) contains two different periodic orbits of ΦAyof periods pand q. Then, since (T, A, f) is twist around y, there exist two subsets Z={Z1, Z2,...,Zp}and W= {W1, W2,...,Wq}of the set of y-branches such that Z ∩ W =∅,f(Zi)⊂Zi+1 mod pfor i= 1,2,...,p and f(Wi)⊂Wi+1 mod qfor i= 1,2,...,q. Furthermore, by the definition of the y-branches we have that Zi∩Wj=∅for 1 ≤i≤pand 1 ≤j≤q. Let z∈A∩Zp. Then fi(z)∈Zimod pfor every i≥0. Since (T, A, f) is orbital, there is a k≥0 such that fk(z)∈A◦. Consequently, A◦⊂ Z1∪Z2∪...∪Zp. But analogously, by taking some w∈A∩Wq, we get that A◦⊂W1∪W2∪...∪Wq, a contradiction. Let Pbe the the unique periodic orbit of ΦAy and let p=|P|. Then p≤n⋆. By Remark 6.2, n⋆∈ {n◦, n◦+ 1}. Now we claim that p≤n◦. Indeed, assume that p=n⋆=n◦+ 1. Then there is one residual branch Sand the unique point zof X(Ay)∩ Sbelongs to P. By Remark 6.2, p≥2. Therefore, there exists another y-branch S′such that if z′is the only point of X(Ay)∩S′then ΦAy(z′) = z. In other words, f(z′)∈S. Therefore, since (T, A, f) is twist around y,f(S′)⊂S. In particular, f(A◦∩S′)⊂S, in contradiction with the fact that Sis the residual branch. This proves the claim. To prove n◦=pwe must see that n◦≤p. It is enough to show that, given a y-branch Ssuch that S∩A◦6=∅, then z∈Pwhere zis the unique point of X(Ay)∩S. On the contrary, since Pis the unique periodic orbit of ΦAy, Φi Ay(z)6=zfor all i > 0. Since (T, A, f) is twist around y, it follows that fi(S)∩S=∅for all i > 0. Take z′∈A◦∩S. Then f|A◦|(z′) = z′∈S, a contradiction. Proposition 6.4. Let (T, A, f)be an n-orbital canonical model which is twist around a fixed point yand let pbe the type of Ay. Then there exist a y-branch Sand a finite set B⊂Ssuch that the following properties hold for g=fp|S: (a) (S, B, g)is a canonical model. (b) Bcontains a unique periodic orbit of g. Furthermore, B◦=A◦∩Sand |B◦|=|A◦|/p. (c) If |B◦|>1then (S, B, g)is (n+ 1)-orbital if n∈ {0,1}and n-orbital if n≥2. (d) Per(f)⊃p·Per(g). (e) If p= 1 then A◦⊂B A. Proof. By Lemma 6.3 and Remark 6.2 we have p= n◦,n⋆≥2 and n⋆∈ {n◦, n◦+ 1}. Since |En(T)\ A◦| ≤ 1 and n⋆≥2, we can choose Sto be a ybranch such that En(T)∩S⊂A◦. Without loss of generality, we can assume that S=Z1. In order to prove (d) it is enough to see that each k-periodic point of gis a kp-periodic point of f. This is a direct consequence of the fact that (T, A, f) is twist around yand the definitions of g and S. Now we prove the other statements when p= n◦= 1. In this case, there are two y-branches: S and the residual one. Moreover, A◦⊂S. Since (T, A, f) is twist around y,f(S)⊂S. We take B= A∩S. Thus A◦is the only periodic orbit contained in B, and (b) and (e) hold. Since En(T)∩S⊂ A◦, the only endpoint of Swhich possibly does not belong to A◦is x1. Hence |En(S)\A◦| ≤ 1. It is obvious that (S, B, g) is n-orbital and thus (c) is satisfied. Finally, it is not difficult to prove that (S, B, g) is a canonical model. Thus (a) holds and we are done in this case. Now we consider the case p=n◦≥2. Observe that the set f−p(A)∩Sis not necessarily finite, but the A-monotonicity of fimplies that it has finitely many connected components, each of them being either a point or a subtree on which fpis constant. Note that A∩S⊂f−p(A)∩S. Then we construct Sets of periods of piecewise monotone tree maps 17 the set Bby taking all the points of A∩Sand all vertices V(K) for each connected component Kof f−p(A)∩S. Thus Bis finite and A∩S⊂B. Since A◦is a periodic orbit and (T, A, f) is twist around y, we get that |A◦∩Zi|=|A◦|/p for i∈ {1,2,...,p}. Moreover, g(S)⊂S,A◦∩Sis a periodic orbit of gof period |A◦|/p and B⊂f−p(A∩ S)∩S=g−1(A∩S). Thus g(B)⊂A∩S⊂B and hence Bis g-invariant. On the other hand, A◦∩Sis the only periodic orbit of gcontained in B. Therefore, B◦=A◦∩Sand (b) holds. Next we prove (c). Assume that |B◦|>1. Since En(T)∩S⊂A◦, the only element of En(S) which possibly does not belong to B◦is x1, and so we have that |En(S)\B◦| ≤ 1. To finish the proof of (c) we claim that for each x∈B,gn+1(x)∈B◦ if n∈ {0,1}and gn(x)∈B◦if n≥2. To prove the claim, set n=pq +rwith q≥0 and 0 ≤r < p. Since x∈B,fp(x)∈A∩S. Therefore, since S=Z1 and (T, A, f) is n-orbital and twist, we have that fn(fp(x)) = fn+p(x) = f(q+1)p+r(x)∈A◦∩Zr+1. Hence, for i≥0 we have fn+p+i(x)∈A◦∩Zr+1+imod p.(2) When n= 0 we have r= 0, and by taking i= 0 in (2) we get that g(x) = fp(x)∈A◦∩Z1=B◦. If n= 1, since p > 1 we have q= 0 and r= 1. Then, by taking i=p−1 in (2) we get that g2(x) = f2p(x)∈A◦∩Z1=B◦. Finally, when n≥2 we take i=pn −n−p. Since p≥2 and n≥2, it follows that i≥0. Then from (2) we obtain that gn(x) = fpn(x)∈A◦∩Zr+1+(pn−pq−r−p) mod p= A◦∩Z1=B◦. This ends the proof of the claim, and hence (c) follows. Finally we must prove (a), i.e. that (S, B, g) is a canonical model. First we will show that g is B-monotone. Let [x, z] be an interval such that [x, z]∩B={x, z}. Since g=fp, we must see that fp([x, z]) = [fp(x), fp(z)] and fp|[x,z]is monotone. From the definition of B, we have that either [x, z] is contained in a connected component of f−p(A)∩S and thus fp([x, z]) reduces to a point of A, or (x, z)∩f−p(A) = ∅. In the first case it is obvious that fp([x, z]) = [fp(x), fp(z)] and fp|[x,z]is monotone. Now assume that (x, z)∩f−p(A) = ∅. Since Ais f-invariant, (x, z)∩f−i(A) = ∅for 0 ≤i < p. Since (x, z)∩A=∅and En(T)⊂A, there exists a minimal interval in T(with respect to the inclusion relation) containing [x, z] whose endpoints belong to A. Since fis A-monotone we have that f|[x,z]is monotone. In particular, f([x, z]) = [f(x), f(z)]. Moreover, (f(x), f(z)) ∩A=∅, since otherwise (x, z)∩f−1(A)6=∅, a contradiction. In the same way, it can be proved inductively that fi|[x,z]is monotone for each 1 < i ≤p. Therefore, gis Bmonotone. In order to complete the proof we must show that there are no g-identifiable vertices. On the contrary, assume that there exist v1, v2∈V(S)\B that are g-identifiable. Since the only possible point of V(S)\V(T) is the unique point of X(Ay)∩S, which belongs to B, we have that v1, v2∈V(T). We consider two cases. In the first case we assume that [gi(v1), gi(v2)]∩ B=∅for i≥0. In other words, [fip(v1), fip(v2)] ∩ B=∅for i≥0. Moreover, since gis B-monotone, we have [gi(v1), gi(v2)] = gi([v1, v2]) for i≥0. Since (T, A, f) is a canonical model, v1and v2are not fidentifiable. Therefore, there exists j≥1 (which we take as small as possible) such that [fj(v1), fj(v2)]∩ A6=∅and fj(v1)6=fj(v2). Since fis A-monotone, [fj(v1), fj(v2)] = fj([v1, v2]). Take k∈Nsuch that kp > j. Since Ais f-invariant, fkp([v1, v2])∩A6=∅. Then ∅ 6=A∩gk([v1, v2]) = A∩[gk(v1), gk(v2)] ⊂ B∩[gk(v1), gk(v2)], a contradiction. This ends the proof of the proposition in this case. Secondly, assume that there is a j≥1 such that [gi(v1), gi(v2)] ∩B=∅for 0 ≤i < j and gj(v1) = gj(v2)∈B. In other words, [fip(v1), fip(v2)] ∩B= ∅for 0 ≤i < j and fjp(v1) = fjp(v2)∈B. Moreover, since gis B-monotone, we have that [fip(v1), fip(v2)] = fip([v1, v2]) for 0 ≤i≤j. In particular, fjp([v1, v2]) = {fjp(v1)}={fjp(v2)}.(3) Since [fjp−p(v1), fjp−p(v2)] ∩B=∅, from the definition of Bit follows that [fjp−p(v1), fjp−p(v2)] does not intersect any connected component of f−p(A)∩S. Thus fjp(v1) = fjp(v2)∈B\A. (4) Since (T, A, f) is a canonical model, v1and v2 are not f-identifiable. Therefore, there exists some k≥1 (which we take as small as possible) such that [fk(v1), fk(v2)] ∩A6=∅and fk(v1)6= fk(v2). From (4) it follows that k < jp. Since fis A-monotone, [fk(v1), fk(v2)] = fk([v1, v2]). Then, since [fk(v1), fk(v2)] ∩A6=∅, we have that 18 Ll. Alsed`a, D. Juher, P. Mumbr´u ∅ 6=fjp−k([fk(v1), fk(v2)]) ∩A=fjp([v1, v2]) ∩A. Therefore, (4) and (3) are in contradiction to each other. To compute the set of periods of a canonical model we will use a subclass of the external loops whose length satisfies certain properties. Now we establish a notation for this kind of loops. Let (T, A, f) be a a y-expansive n-orbital model. Let pbe a type of Ayand let qbe a rotation index associated to p. Then we define ˜ E(T, A, f) = {β∈ E(T, A, f) : |β| ∈ pN, |β| ≤ |A◦|+p+q+n+ 1}. Proposition 6.5. Let (T, A, f)be an n-orbital canonical model which is non-twist around a fixed point y. Let pbe a type of Ayand let qbe a rotation index of (T, A, f)associated to p. Then at least one of the following statements hold: (a) There exist a tree S⊂Tand a finite set B⊂ Ssuch that A◦⊂B Aand (S, B, f|S)is an n-orbital canonical model; (b) ˜ E(T, A, f)6=∅. In particular, (b) holds if En(T)⊂A◦ Proof. Let Wbe the set of points z∈Aythat satisfy the following two properties: (i) There exists N∈ {1,2,...,p}such that z∈ ZNbut f(z)/∈ZN+1 mod p; (ii) There exist z′∈Ay\ {z}and w∈A◦such that z′wand zf(z′). A sufficient condition for (ii) is the following property: (ii’) There exists z′′ ∈A◦such that zz′′. To see it, take w=z′as the unique point of f−1(z′′)∩A◦when {z} 6=f−1(z′′)∩A◦, and take w=z′as the unique point of f−1(z)∩A◦otherwise. We start by claiming that if En(T)⊂A◦then W6=∅. To prove the claim assume that W=∅. Since in this case (ii’) holds for every z∈Ay, we see that (i) does not hold for any z∈Z(Ay). Thus f(Ay∩Zi)⊂Zi+1 mod pfor i= 1,2,...,p. Then, by the Ay-monotonicity of f, we have f(Zi)⊂ Zi+1 mod pfor i= 1,2,...,p. Since A◦is a periodic orbit and En(T)⊂A◦, we easily get that n⋆=n◦=p. Therefore f(Zi)∩Z⋆=∅for i= 1,2,...,n⋆and so (T, A, f) is twist around y, in contradiction with the hypotheses. This proves the claim. To prove the proposition we consider two cases. First we assume that W6=∅and we prove that (b) holds. In the proof of this case, the subindexes will be considered modulo p. Let k∈ {1,2,...,p} be such that q=qk. By the A-monotonicity of f and the definition of q,f([y, fi−1(xk)]) = [y, fi(xk)] for 1 ≤i≤qand [y, fq(xk)] ∩A6=∅. We have fq(xk)∈Zk+q. This is obvious if q= 0 and it follows from Lemma 4.4 if q > 0. Let a∈[y, fq(xk)] ∩A. Take z∈Wand let N∈ {1,2,...,p},w∈A◦and z′∈Ay\{z}be such that z∈ZN,f(z)/∈ZN+1,z′wand zf(z′). Since (T, A, f) is n-orbital and w∈A◦, there exists s≤n+|A◦| − 1 such that fs(a) = w. Thus z′ fs(a). If fi([y, fq(xk)]) ⊂[y, xk+q+i]∪Zk+q+i(5) is satisfied for each 0 ≤i≤s+ 1, then we have that z′∈fs([y, fq(xk)]), z∈fs+1([y, fq(xk)]), ZN=Zk+q+s+1 and f(z)/∈Zk+q+s+2. Summarizing, there exists a minimum non-negative integer t≤s+ 1 ≤n+|A◦|such that (5) holds for each 0≤i≤tand ft([y, fq(xk)]) contains a point u whose image does not belong to Zk+q+t+1. Since f(xk+q+t)∈Zk+q+t+1, there exists a Aybasic interval L= [b, c]⊂[xk+q+t, u] such that f(b)∈Zk+q+t+1 and f(c)/∈Zk+q+t+1. Then L f-covers [y, xk+q+t+1] = Ik+q+t+1. By using q+t times Lemma 3.1 by backwards induction we obtain the following loop βin the f-graph of Ay: Ik→J1→J2→. . . →Jq+t−1→L →Ik+q+t+1 →Ik+q+t+2 →...→Ik where Jiis a Ay-basic interval contained in fi(Ik) for each 1 ≤i≤q+t−1. Since Lis not a typical interval, βis an external loop, and |β|=q+t+ 1 + p−(q+t+ 1 mod p)∈pN. Observe that |β| ≤ q+t+ 1 + p≤q+n+|A◦|+ 1 + p. Hence, (b) holds when W6=∅and, in particular, when En(T)⊂A◦. From now on we assume that W=∅. From the above claim, En(T)6⊂ A◦and thus |En(T)\A◦|= 1. Hence, there is a unique y-branch containing some endpoint which does not belong to A◦. By Remark 6.2, n⋆≥2 and n⋆∈ {n◦, n◦+ 1}. We also recall that the y-branches are labeled in such a way Sets of periods of piecewise monotone tree maps 19 that f(xi)∈Zi+1 mod pfor i= 1,2,...,p. We shall consider the following cases: Case 1. p= 1. Assume that Z1∩A◦6=∅. Each z∈Z1∩A◦ verifies (ii’) and, since W=∅, it does not verify (i). In consequence, A◦⊂Z1and n◦= 1. Since n⋆∈ {n◦, n◦+ 1}and n⋆≥2, it follows that n⋆= 2. Therefore Z2is the residual branch and En(T)∩Z1⊂A◦. In particular, each point in Z1 verifies (ii’). Since W=∅, no point in Z1∩Ay verifies (i) and thus f(Z1∩Ay)⊂Z1. Since fis Ay-monotone, it follows that f(Z1)⊂Z1. We set S=Z1and B=A∩S. Then B A. It is not difficult to prove that (S, B, f|S) is an n-orbital canonical model. Therefore (a) holds and we are done in this case. Now suppose that Z1∩A◦=∅. Then, from the fact that (T, A, f) is n-orbital, it follows that fr(x1)/∈Z1for some r≤n(which we take as small as possible). By the definition of type, f(x1)∈Z1and hence I1f-covers [x1, f(x1)]. Also [fi−1(x1), fi(x1)] f-covers [fi(x1), fi+1(x1)] for 1 ≤ i≤r−2 and [fr−2(x1), fr−1(x1)] f-covers I1⊂ [fr−1(x1), fr(x1)]. By using Lemma 3.1 by backwards induction, as above we obtain a loop in the f-graph of Ayof length r≤n. Since [x1, f(x1)] does not contain typical intervals, this loop is external. Hence (b) holds in this case. Case 2. p > 1and n⋆=n◦+ 1. In this case there is a residual branch Zifor some i∈ {1,2,...,n⋆}. We claim that i > p. Indeed, if i≤p then, since p > 1, it follows that i−1 (mod p)6=i. Hence, Zi−1 mod pis not residual. Since |En(T)\ A◦|= 1, it follows that Zi−1 mod p∩En(T)⊂A◦. Thus each point in Ay∩Zi−1 mod pverifies (ii’) from the definition of W. On the other hand, each point z∈A◦∩Zi−1 mod p⊂Ay∩Zi−1 mod pverifies f(z)/∈ Zimod p. That is, it verifies (i). This implies W6= ∅, a contradiction. This proves the claim. From above, it follows that En(T)∩Zi⊂A◦ for i= 1,2,...,p. Therefore, each z∈Ay∩Zi satisfies (ii’) from the definition of Wand, since W=∅, these points do not satisfy (i). Consequently, f(Ay∩Zi)⊂Zi+1 mod p,n◦=pand Zn⋆=Zn◦+1 is the residual branch. By the Aymonotonicity, f(Zi)⊂Zi+1 mod pand f([y, xi]) ⊂ [y, xi+1 mod p]∪Zi+1 mod pfor i= 1,2,...,p. Thus, if we define S=hA◦iT=T\(Zn⋆∪(y, xn⋆]), then f(S)⊂S. Finally, if we define B=A∩S then B Aand it is not difficult to prove that (S, B, f|S) is an n-orbital canonical model. Hence (a) holds and we are done. Case 3. p > 1and n⋆=n◦. In this case, A◦∩Zi6=∅for each 1 ≤i≤n⋆. We claim that, for some N∈ {1,2,...,p}, there exists a∈Ay∩ZNsuch that f(a)/∈ZN+1 mod p. Indeed, when p=n⋆the claim follows since (T, A, f) is nontwist around y. To end the proof of the claim we assume that p < n⋆and f(Ay∩Zi)⊂Zi+1 mod p for i= 1,2,...,p. Then A◦⊂Z1∪Z2∪...∪Zp and Zn⋆∩A◦=∅, a contradiction. Thus the claim follows. Since asatisfies (i) from the definition of W and W=∅we have: {x∈A◦:xa}=∅.(6) Therefore, since |En(T)\A◦|= 1, the unique point ein En(T)\A◦must satisfy ae, [a, e]∩ V(T) = {e}and [a, e]∩A◦=∅. Since ZN∩A◦6=∅, there exists v∈(V(T)∪A◦)∩ZNsuch that v≺a and (v, e)∩(V(T)∪A◦) = ∅.(7) Since y /∈ZN, we get that x∈(v, e)∩Ayimplies x∈A\A◦. Let zbe the minimum (with respect to the ≺ordering) of the points of (v, a]∩Aysuch that f(z)/∈ZN+1 mod p(this point exists since f(a)/∈ ZN+1 mod p). We have xNv≺zaeand f(v, z)∩Ay⊂ZN+1 mod p.(8) Set R=T\(v, e]. Observe that R=hA◦iT⊃ ZN+1 mod p. Clearly, for each point z′∈Rthere exists w∈En(T)∩A◦such that z′w. Consequently, if there exists z′∈R∩Aysuch that f(z′)∈[z, e] (that is, zf(z′)), it follows that zverifies (i) and (ii) from the definition of W; a contradiction since W=∅. Therefore, f(R∩Ay)∩[z, e] = ∅.(9) Furthermore, if the image of some x∈R∩Ay belongs to (v, z), then by (8) we have that f2(x)∈ R∩Ayand hence f2(x)/∈[z, e]. This fact, together 20 Ll. Alsed`a, D. Juher, P. Mumbr´u with (9), gives us that fi(R∩Ay)∩[z, e] = ∅for all i≥0. Since fis Ay-monotone, it follows that fi(R)∩[z, e] = ∅for i≥0.(10) We define S= Cl( S i≥0 fi(R)). Since f(R)⊃R,S is connected. That is, Sis a subtree of T. Clearly, f(S)⊂Sand R⊂S. Moreover, by (10), S⊂ T\(z, e]. Thus there exists v′∈En(S) such that vv′zand S=T\(v′, e]. From the definition of Sand from the Ay-monotonicity of fwe deduce immediately that v′∈Ay(in fact, S=f|Ay|(R)). Hence, v′∈A\A◦. We define B=A∩S. Observe that A◦⊂B A, since at least edoes not belong to B. Clearly, f(B)⊂B. Moreover, it is not difficult to show that (S, B, f|S) is a canonical model. This model is n-orbital, since A◦is the unique periodic orbit contained in B, and En(S)\ {v′} ⊂ A◦. In the rest of this section, we use recursively the above theorem to study the set of periods of a canonical model. To do it, we introduce the following notions. Let (T, A, f) be a canonical model and let p∈ N. We say that a canonical model (T′, A′, f′) is a partial p-reduction of (T, A, f) if T′⊂T,f′=fp|T′ and Per(f)⊃pPer(f′). Let (T, A, f) be a 2-orbital canonical model. A sequence {(Ti, Ai, fi), yi, pi}m i=1 will be called a sequence of partial reductions of (T, A, f) if and only if: (i) (T1, A1, f1) = (T, A, f) (ii) (Ti, Ai, fi) is a yi-expansive 2-orbital canonical model for 1 ≤i < m. (iii) (Ti+1, Ai+1, fi+1) is a partial pi-reduction of (Ti, Ai, fi) for 1 ≤i < m. (iv) |Ai◦|=pi|Ai+1◦|for 1 ≤i < m. Moreover, Ai◦⊂Ai+1 Aiwhen pi= 1. (v) ˜ E(Ti, Ai, fi) = ∅for 1 ≤i < m. (vi) (Tm, Am, fm) is a canonical model such that Amcontains a unique periodic orbit and either (vi.1) |Am◦|= 1 and thus (Tm, Am, fm) is a trivial model or (vi.2) (Tm, Am, fm) is a ym-expansive 2-orbital canonical model, pmis a type of Aym mand ˜ E(Tm, Am, fm)6=∅. Observe that if m= 1 then, by (i) and (vi.2), (T, A, f) is a y1-expansive 2-orbital model, p1is a type of Ay1and ˜ E(T, A, f)6=∅. Remark 6.6. Given a sequence of partial reductions {(Ti, Ai, fi), yi, pi}m i=1 of (T, A, f), from (iv) it follows that |A|=p1p2···pm−1|A◦ m|. Moreover, since Per(fi)⊃piPer(fi+1)∪ {1}for 1 ≤i < m, it follows that Per(f)⊃ {1, p1, p1p2,...,p1p2···pm−1} ∪p1p2. . . pm−1Per(fm). The next theorem and corollary are the main results of this section. Theorem 6.7. Each 2-orbital canonical model admits a sequence of partial reductions. Proof. Let (T, A, f) be a 2-orbital canonical model. During this proof, we will use the notation from the definition of a sequence of partial reductions. In particular, the roman numerals (i–vi) refer to the properties of that definition. We formally denote {(Ti, Ai, fi), yi, pi}k i=1 by Skfor any k≥0 (note that S0=∅). We start by setting (T1, A1, f1) = (T, A, f). Therefore (T1, A1, f1) is a 2-orbital canonical model. Moreover, (i–v) hold (with 1 instead of m). Now we proceed by induction on k. Let k≥1 and assume that we have constructed a sequence Sk−1and a canonical model (Tk, Ak, fk) such that: (a) Akcontains a unique periodic orbit of fkand (Tk, Ak, fk) is 2-orbital if |Ak◦|>1. (b) (i–v) hold (with kinstead of m). Observe that if, in addition, there exist ykand pk such that (vi) holds (with kinstead of m) then Sk is a sequence of partial reductions. Now we must define ykand pkand then decide whether Skis a sequence of partial reductions (in this case we stop by setting m=k) or we construct a canonical model (Tk+1, Ak+1, fk+1) such that Sk and (Tk+1, Ak+1, fk+1) verify (a) and (b) (with k+1 instead of k). Assume that |Ak◦|= 1. We set pk= 1 and define ykto be the unique element of Ak◦. Then Sk verifies (vi.1) and thus Skis a sequence of partial reductions. In this case we are done by setting m= k. Assume that |Ak◦|>1. Then (Tk, Ak, fk) is 2- Sets of periods of piecewise monotone tree maps 21 orbital since (a) holds. By Proposition 5.4, there exists yk∈Fix(fk) such that (Tk, Ak, fk) is ykexpansive. Let pbe a type of Ayk k. If ˜ E(Tk, Ak, fk)6=∅then we define pk=pand (vi.2) holds (with kinstead of m). Hence Skis a sequence of partial reductions and we are done by setting m=k. From now on we assume that ˜ E(Tk, Ak, fk) = ∅. Since |Ak◦|>1, (Tk, Ak, fk) does not verify neither (vi.1) nor (vi.2) and Skis not a sequence of partial reductions. In order to iterate the argument we will define a model (Tk+1, Ak+1, fk+1) such that Sk and (Tk+1, Ak+1, fk+1) verify (a) and (b) with k+1 instead of k. We consider two cases. Case 1. (Tk, Ak, fk)is twist around yk. We define pk=p. By Proposition 6.4, there exists a yk-branch Tk+1 and a finite set Ak+1 ⊂ Tk+1 such that if we define fk+1 = (fk)pk|Tk+1 then (Tk+1, Ak+1, fk+1) is a canonical model and Per(fk)⊃pkPer(fk+1). Hence, (Tk+1, Ak+1, fk+1) is a partial pk-reduction of (Tk, Ak, fk). Furthermore, Ak+1 contains a unique periodic orbit and (Tk+1, Ak+1, fk+1) is 2-orbital if |Ak+1◦|>1. Finally, |Ak◦|=pk|Ak+1◦|and if pk= 1 then Ak◦⊂Ak+1 Ak.(11) Summarizing, we have constructed a canonical model (Tk+1, Ak+1, fk+1) in such a way that Skand (Tk+1, Ak+1, fk+1) verify (a) and (b) (with k+ 1 instead of k). Case 2. (Tk, Ak, fk)is non-twist around yk. Since ˜ E(Tk, Ak, fk) = ∅, by Proposition 6.5 there exists a tree Tk+1 ⊂Tkand a finite set Ak+1 ⊂ Tk+1 such that (Tk+1, Ak+1, fk|Tk+1 ) is a 2-orbital canonical model and Ak◦⊂Ak+1 Ak.(12) We set pk= 1 and fk+1 =fk|Tk+1 . Thus Per(fk)⊃ pkPer(fk+1) and (Tk+1, Ak+1, fk+1) is a partial pkreduction of (Tk, Ak, fk). As above, we have constructed a canonical model (Tk+1, Ak+1, fk+1) such that Skand (Tk+1, Ak+1, fk+1) verify (a) and (b) (with k+ 1 instead of k). Finally we must prove that this iterative construction stops after a finite number of steps. This is a direct consequence of (11), (12) and the finiteness of A1. Next we will use the notion of a sequence of partial reductions to estimate the set of periods of a canonical model. A serious drawback of this notion is that it is only defined for canonical models, whereas we are interested in studying the set of periods of the more general monotone models. However, by means of Theorem 5.3, for each monotone model (S, P, g) we can construct a canonical model (T, A, f) associated to it (see page 15). Then we can use a sequence of partial reductions to get an estimation of Per(f), which differs from Per(g) only in finitely many periods. This motivates the following definition. Let (S, P, g) be a monotone model such that Pis a periodic orbit which does not consist of a fixed point. A pair {R, K}, where Ris a canonical model and K⊂N, is said to be a complete reduction of (S, P, g) if there exists a sequence of partial reductions {(Ti, Ai, fi), yi, pi}m i=1 such that K= {1, p1, p1p2,...,p1p2· · · pm−1},R= (Tm, Am, fm) and (T1, A1, f1) is a canonical model associated to (S, P, g). When Ris non-trivial, we define the three non-negative numbers which play the central role in the characterization of Per(g) given by Theorem A. In this case, p(R) will denote the type pmof Aym m, q(R) will denote a rotation index of Rassociated to the type pm, and n(R) will denote the least nsuch that Ris n-orbital. Observe that n(R)∈ {0,1,2} since Ris 2-orbital. From this definition and Theorem 6.7 we obtain the following corollary. Corollary 6.8. Let (S, P, g)be a monotone model such that Pis a periodic orbit with |P|>1. Then (S, P, g)admits a complete reduction. Given a complete reduction {(S, P, g), K}of (S, P, g), there exists a (possibly empty) finite set Vsuch that Per(g)⊃ V ∪ K∪(max K) Per(g) and each element of Vdivides the least common multiple of the periods of all periodic orbits of g contained in V(S). Moreover, |P|= (max K)|P◦|. Proof. Since (S, P, g) is 0-orbital, by Theorem 5.3 there exists a 0-orbital (and thus 2-orbital) canonical model (T, A, f) associated to (S, P, g). By Theorem 6.7, (T, A, f) admits a sequence of partial re- 22 Ll. Alsed`a, D. Juher, P. Mumbr´u ductions {(Ti, Ai, fi), yi, pi}m i=1. In consequence, {(Tm, Am, fm),{1, p1, p1p2,...,p1p2···pm−1} } = {(S, P, g), K }is a complete reduction of (S, P, g). Since (T, A, f) and (S, P, g) are associated, A is a periodic orbit of f,|A|=|P|and there exists a (possibly empty) finite set Vverifying the prescribed properties and such that Per(g) = Per(f)∪ V. By Remark 6.6, Per(f)⊃K∪(max K) Per(g) and |A|= (max K)|P◦|. 7. Proof of Theorem A The main results used in the proof of Theorem A are: Corollary 6.8, which allows us to work with a complete reduction instead of the original model, and both Lemma 4.6 and Theorem 4.7 which are used to calculate the set of periods of the reduced model. Proof of Theorem A. By the definition of a monotone model, En(S)⊂P. Therefore, Sreduces to a point when Pconsists of a fixed point, and in this case the theorem follows obviously. Assume that |P|>1. The fact that there exist complete reductions of (S, P, g) follows from Corollary 6.8. Moreover, given a complete reduction {R, K}, we have Per(g)⊃K. If Ris trivial, we are done. Assume that Ris non-trivial and set R= (S, P, g). By the definition of a complete reduction we have ˜ E(R)6=∅. Thus there exists β∈ E(R) such that |β| ∈ pNand |β| ≤ |P◦|+p+q+n+1. We define λ=|β|/p. Since βis external, by Lemma 4.6 we get Per(g)⊃ {λpi +pj :i, j ≥1}. Moreover, by Lemma 4.2, p∈Per(g). Consequently, from Corollary 6.8 we have Per(g)⊃K∪ {kp} ∪ {λkpi +kpj :i, j ≥1} =K∪kpN\ {2kp, 3kp, . . . , λkp},(13) and |P|=k|P◦|. Hence, when |P◦| ∈ pNit follows that for each l≥0 (see Remark 2.3) we have |P|+ lkp =k(|P◦|+lp)∈kpNand therefore S∗ kp(|P|+ lkp) = Skp(3kp) = {1} ∪ kpN. Hence, from (13) we have Per(g)⊃K∪ S∗ kp(|P|+lkp)\ {2kp, 3kp, . . . , λkp} and the theorem follows in this case. Assume now that |P◦|/∈pN. By Theorem 4.7 we have Per(g)⊃ {(|P◦|+lp)i+pj :i, j ≥1}for some 0 ≤l≤ |P◦|+q+n−1. Then, l≤ |P|/k+q+1 because n∈ {0,1,2}. Furthermore, if n= 0 then, again by Theorem 4.7, lp ≤p+q−(qmod p). Thus, from Corollary 6.8 it follows that Per(g)⊃ {(|P|+lkp)i+kpj :i, j ≥1}.(14) Since |P|+lkp =|P◦|k+lkp /∈kpN\ {1}, we have S∗ kp(|P|+lkp) = Skp(|P|+lkp) ={1,|P|+lkp} ∪ {(|P|+lkp)i+kpj :i≥0, j ≥1} ={1} ∪ kpN∪ {(|P|+lkp)i+kpj :i, j ≥1}. Hence, from (13) and (14) we have Per(g)⊃K∪ S∗ kp(|P|+lkp)\ {2kp, 3kp, . . . , λkp}. 8. Upper bounds for the type and the rotation index This section is devoted to prove the inequalities (1), from Sec. 2. In the proof of Proposition 8.1 we use Lemma 4.4. Proposition 8.1. Let (T, A, f)be a y-expansive norbital model such that E(T, A, f)6=∅. Let pbe a type of Ayand let qbe a rotation index of (T, A, f) associated to p. Then: (a) p≤ |A◦|+ 1. (b) If q > 0then 2p+q−2≤ |A◦|. If, in addition, n= 0 then: (c) p≤ |A| − 1. (d) If p= 1 then q+ 4 ≤ |A|. (e) If q > 0then 2p+q+ 1 ≤ |A|. Proof. Until the end of the proof, the subindexes will be considered modulo p. Since pis a type of Ay we have p≤ | En(T)|and, since (T, A, f) is orbital, there is at most 1 endpoint which does not belong to A◦. Therefore, |En(T)| ≤ |A◦|+ 1,(15) which proves (a). If n= 0 then A=A◦. Moreover, if En(T) = Athen from the fact that (T, A, f) is a canonical model and the unicity of canonical Sets of periods of piecewise monotone tree maps 23 models (see Theorem B of [Alsed`a et al., 1997]) we get that Tis a |A|-star whose central point is y and f([y, x]) = [y, f(x)] for each x∈A. Then E(T, A, f) = ∅, a contradiction. Consequently, En(T) Aand |En(T)| ≤ |A| − 1 when n= 0,(16) which proves (c). Next we prove (b). By assumption we have q > 0. So, xi∈V(T) for 1 ≤i≤pand, hence, for each 1 ≤i≤pthere are at least 2 points of X(A) in Zi(we recall that Zistands for Z(Ay)i). Therefore, X(A)∩ p [ i=1 Zi≥2p. (17) Let k∈ {1,2,...,p}be such that q=qkand set Q={fi(xk)}q−1 i=0 . Clearly Q⊂V(T)\A. By Lemma 4.4, fi(xk)∈Zk+ifor 0 ≤i≤q−1. Moreover, since (T, A, f) is y-expansive we have that Q does not contain periodic orbits and thus |Q|=q. We claim that Q∩ {xi}p i=1 ={xk}. Indeed, assume that fj(xk)∈ {xi}p i=1 for some 1 ≤j≤q− 1. Then fj(xk) = xk+j. Since Qdoes not contain periodic orbits, xk+j6=xkand then we easily get that qk+j=qk−j, in contradiction with the fact that qk=q= min{q1, q2,...,qp}. Thus the claim follows. Given v∈Q\{xk}, we have that v∈V(T)∩Zi for some 1 ≤i≤p,v6=xiand [xi, v]∩A=∅. Since v∈V(T), there exists some point w∈X(A)∩Zi with v≺wwhich has not been taken into account in (17). Therefore, X(A)∩ p [ i=1 Zi≥2p+q−1 when q > 0.(18) Since |En(T)| ≥ |X(A)|, (b) follows from (15) and (18). To prove (d), assume that p= 1. Let a∈ X(A)∩Z1. Then f(a)6=asince (T, A, f) is orbital. Since x1≺f(x1) and x1belongs to the (A∪ {y})- basic interval [y, a], the (A∪ {y})-monotonicity of fimplies that f(a)∈Z1. By Remark 6.2, there is at least one y-branch different from Z1. Therefore, since En(T)⊂Athere exists b∈X(A)\Z1. Now we claim that f(b)/∈Z1. Indeed, if f(b)∈Z1then the A-monotonicity of fand the fact that (a, b)∩A=∅imply that f([a, b]) ⊂Z1, in contradiction with the fact that y∈[a, b] and hence y∈f([a, b]). Thus the claim follows. Observe that f(b)6=bsince (T, A, f) is orbital. Also, by the previous claim, f(b)/∈ {a, f(a)}, and thus a,b,f(a) and f(b) are 4 different points contained in A. In consequence, |A| ≥ 4. Then, (d) holds when q= 0. When q > 0 we have q=q1since p= 1. So, by Lemma 4.4, fi(x1)∈(V(T)∩Z1)\A for 0 ≤i < q. Let Sbe the closure of the connected component of Z1\X(A) which contains x1. Then Sis a tree whose endpoints are the elements of X(A)∩Z1. From the definition of qit follows that, for 0 < i < q,fi(x1) are vertices of Swhich are not endpoints of S. Since any tree with nvertices has at least n+ 2 endpoints, we get |En(S)| ≥ q+ 1. As we noticed above, f(a)∈Z1and f(a)6=afor any a∈X(A)∩Z1. Thus |A∩Z1|>|X(A)∩Z1| and, hence, |A∩Z1| ≥ q+2. Therefore, taking into account band f(b), which are in Abut not in Z1, we have |A| ≥ q+ 4 and (d) holds. To end the proof of the proposition we must show that (e) holds. So we assume that n= 0, that is, Ais a periodic orbit. By (d), it is enough to consider the case p > 1. Since |En(T)| ≥ |X(A)|, from (16) and (18) it follows that |A| ≥ 2p+q. So, we must show that |A| 6= 2p+q. In the rest of the proof we assume that |A|= 2p+q(and q > 0 and p > 1) and we will arrive to a contradiction. If A=X(A), as in the proof of (c) we get that fis a rigid rotation of a |A|-star and since E(T, A, f)6=∅we get that X(A) A. From (18) we have 2p+q−1≤X(A)∩ p [ i=1 Zi≤ |X(A)|<|A|= 2p+q. Hence, there is exactly one point win A\X(A) and |X(A)∩ ∪p i=1Zi|= 2p+q−1. Now we claim that n⋆=p. Indeed, assume that there exists some y-branch Wdifferent from Z1, Z2,...,Zp. Since En(T)⊂A, we have W∩ A6=∅. Since |X(A)∩ ∪p i=1Zi|= 2p+q−1 and |A|= 2p+q, it follows that W∩A={w}. Thus w∈X(A), a contradiction. So the claim follows. Let j∈ {1,2, . . . , p}be such that w∈Zj. We have that Zj∩Ais the disjoint union of {w}and Zj∩X(A), while Zi∩A=Zi∩X(A) when i6=j. Since q > 0, xi/∈X(A) for 1 ≤i≤p. For each point z∈X(A)∩Zi, we have that [y, z] is a (A∪ {y})-basic interval containing xi. Therefore, 24 Ll. Alsed`a, D. Juher, P. Mumbr´u since f(xi)∈Zi+1 and fis (A∪{y})-monotone, we get f(X(A)∩Zi)⊂Zi+1 for 1 ≤i≤p. Moreover, f(X(A)∩Zi) = X(A)∩Zi+1 when i6≡ jand i6≡ j+ 1 (mod p). We set Ni=|X(A)∩Zi|for 1 ≤i≤p. Since X(A)⊂Aand Ais a periodic orbit, it follows that Ni+1 =Niwhen i6≡ jand i6≡ j+ 1 (mod p). Consequently, we have Nj−1=Nj−2=...=Nj+2 =Nj+1.(19) If f(w)∈Zj+1 then (T, A, f) is twist around y and, by Remark 6.1, E(T, A, f) = ∅, a contradiction. Therefore, f(w)/∈Zj+1. Then X(A)∩Zj+1 = f(X(A)∩Zj) and it follows that Nj+1 =Nj. Thus from (19) we get that Nj−1=Nj. On the other hand, since Ais a periodic orbit, there exists a unique point w′∈A∩Zj−1=X(A)∩Zj−1such that f(w′) = w. Since w∈Zj\X(A), we get Nj=Nj−1−1, a contradiction. The following result states that the inequalities (1) hold for complete reductions of monotone models. Corollary 8.2. Let (S, P, g)be a monotone model such that Pis a periodic orbit of gwith |P|>1. Let {R, K}be a complete reduction of (S, P, g)such that Ris non-trivial and n(R) = 0. Then p≤r−1, q+ 4 ≤rwhen p= 1 and 2p+q+ 1 ≤rwhen q > 0, where we denote p(R),q(R),n(R)and |P| max Kby p, q,nand rrespectively. Proof. Set (T, A, f) = R. Since n= 0, we have A◦=A. By Corollary 6.8, |A|=r. Since Ris nontrivial, by the definition of a complete reduction we have that Ris a y-expansive 0-orbital model for some y∈Fix(f), pis a type of Ay,qis a rotation index of Rassociated to pand ˜ E(R)6=∅. In particular, E(R)6=∅. Therefore Rverifies the hypotheses of Proposition 8.1 and the corollary follows. 9. Some Examples. Proof of Theorem B This section is devoted to prove Theorem B. In fact, we prove the following stronger result from which Theorem B can be obviously derived. Since any tree can be imbedded in R2, in what follows we will consider each tree endowed with the topology induced by the topology of R2. Theorem 9.1. Let K⊂Nbe a set of the form {1, k1, k2,...,km}such that k1>1and kistrictly divides ki+1 for 1≤i < m. Set k=km. Then: (a) There exists a canonical model (R, B, h)such that |B|=kand Per(h) = K. (b) Given any r > 1,p≥1and q≥0verifying p≤r−1, q+ 4 ≤rwhen p= 1 and 2p+q+ 1 ≤rwhen q > 0, there exists a canonical model (S, P, g)and a complete reduction {(S, P, g), K}of (S, P, g) with |P◦|=r,p(S, P, g) = p,q(S, P , g) = q, n(S, P, g) = 0 and Per(g) = K∪ C, where C is a set such that S∗ kp(|P|+lkp)\ {2kp, 3kp, . . . , λkp} ⊂ C ⊂ S∗ kp(|P|) with lp =p+q−(qmod p)and λp being the largest multiple of psmaller than r+p+q+1. In order to prove Theorem 9.1 we will use the following two technical results. For Proposition 9.2 see Fig. 3, which shows an example of the construction made in that proposition. Proposition 9.2. Let (T, A, f)be a canonical model such that Ais a periodic orbit and let s≥2 be an integer. Then there exists a canonical model (T′, A′, f′)such that: (a) There exists y∈Fix(f′)such that sis a type of A′yaround yand (T′, A′, f′)is y-expansive and twist around y. (b) A′is a periodic orbit with |A′|=s|A|. (c) (T, A, f)is a partial s-reduction of (T′, A′, f′). (d) Per(f′) = {1} ∪ s·Per(f). Proof. Set t=|A∪V(T)|and Q1=A∪V(T) = {v1 1, v1 2,...,v1 t}in such a way that v1 1∈En(T) and A={v1 i}|A| i=1. Next we will construct T′by attaching one copy of Tto each endpoint of an s-star. For each 2 ≤i≤swe consider a tree Ti, a finite set Qi={vi 1, vi 2,...,vi t} ⊂ Tiand a homeomorphism hi:Ti−→ Tsuch that hi(vi j) = v1 jfor each 1 ≤j≤t. We also set T1=Tand h1= Id|T1. Sets of periods of piecewise monotone tree maps 25 a2a3a1 a4y a′ 2 a′ 1a′ 3 a′ 4 a′ 7 a′ 8 a′ 5 a′ 9 a′ 6 (T′, A′, f′) a′ 10 a′ 11 a′ 12 (T, A, f) Fig. 3. An example of the construction made in Proposition 9.2, with |A|= 4 and s= 3. We assume f(ai) = ai+1 mod 4 and f′(a′ i) = a′ i+1 mod 12. Now we define T′to be a tree which consists of the union of Tifor 1 ≤i≤sand an s-star Rsuch that En(R) = {v1 1, v2 1,...,vs 1}. Thus T′consists of an sstar with one copy of Tattached to each endpoint. Let ybe the central point of R. Now we are going to define the map f′. First we define it on each Ti. We set f′|Ti=h−1 i+1 ◦hifor each 1 ≤i < s and f′|Ts=f◦hs. Note that f′is a homeomorphism between Tiand Ti+1 and f′(vi 1) = vi+1 1for each 1 ≤i < s. Moreover, f′(vs 1) = f(v1 1)∈ A∩T1. Now we define f′on R\En(R). We set f′(y) = yand take f′to be an affine homeomorphism between [y, vi 1] and [y, f(vi 1)] for each 1 ≤i≤s. Finally set A′=∪s i=1{vi 1, vi 2,...,vi |A|}. Since f′|Tiis a homeomorphism for each 1 ≤i < s and fis A-monotone, we easily get that (T′, A′, f′) is a monotone model. Moreover, since (T, A, f) is canonical, there are no f-identifiable vertices in T. Then there are no f′-identifiable vertices in T′and (T′, A′, f′) is a canonical model. Now we prove (a). Set Q={y}∪s i=1Qi. Clearly A′y=Qand for 1 ≤i≤swe have Z(Q)i=Tiand x(Q)i=zi. Since f′(x(Q)i) = x(Q)i+1 for 1 ≤i < sand f′(x(Q)s)∈Z(Q)1, it follows that sis a type of A′y. Moreover, f′(Z(Q)i)⊂Z(Q)i+1 mod sfor 1≤i≤sand so (S′, P′, g′) is twist around y. Since there are no vertices of T′in Z⋆(A′)\{y}, obviously (T′, A′, f′) is y-expansive and (a) holds. To prove the rest of the statements first we consider the case |A|= 1. Then Treduces to the unique point of A, that is v1 1. Moreover, T′coincides with Rand A′={v1 1, v2 1,...,vs 1}. Therefore f′is a rigid rotation of an s-star and (b), (c) and (d) follows obviously in this case. Now we assume that |A|>1. We claim that f′s(z) = f(z) for each z∈T . (20) Indeed, take z∈T. We have that f′s−1(z) = h−1 s◦ hs−1◦h−1 s−1◦hs−2◦...◦h2◦h−1 2◦h1(z). Since h1= Id, we get f′s−1(z) = h−1 s(z)∈Ts. Therefore f′s(z) = f′(f′s−1(z)) = f(hs(h−1 s(z))) = f(z) and the claim follows. Now we prove (b) and (c). Let x∈Tbe an n-periodic point of f. Since f′i(x)∈Ti+1 for 1 ≤ i < s, from (20) it follows that {f′i(x)}sn i=0 is an snperiodic orbit of f′. In particular, (b) holds. Thus we have {1} ∪ sPer(f)⊂Per(f′). This inclusion, together with (20) and the fact that T⊂T′, proves that (T, A, f) is a partial s-reduction of (T′, A′, f′) and (c) holds. Finally we prove (d). It is enough to show that Per(f′)⊂ {1} ∪ sPer(f). Let Pbe an n-periodic orbit of f′with n > 1. The definition of f′on R implies that yis a repelling fixed point of f′son each edge of R. It follows that the unique periodic orbit of f′on Ris {y}. Therefore, P⊂T′\R. Moreover, since (T′, A′, f′) is twist we have that n=rs for some r≥1 and there exists x∈P∩Tsuch that f′i(x)∈Ti+1 mod sfor all 1 ≤i≤rs. From (20) we get that {f′is(x)}r−1 i=0 is an r-periodic orbit of f. Thus n∈sPer(f). By convention, a tree Twill be a 1-star if T 32 Ll. Alsed`a, D. Juher, P. Mumbr´u grant number 1999SGR-00349 and the third author by CIRIT grant number 2000SGR-00027. References Alsed`a, Ll., Guaschi, J., Los, J., Ma˜nosas, F., Mumbr´u, P. [1997] “Canonical representatives for patterns of tree maps”, Topology 36, 1123– 1153. Alsed`a, Ll., Juher, D., Mumbr´u, P. [2001] “A note on the periodic orbits and topological entropy of graph maps”, Proc. Amer. Math. Soc. 129, no. 10, 2941–2946. Alsed`a, Ll., Llibre, J., Misiurewicz, M. [1989] “Periodic orbits of maps of Y”, Trans. Amer. Math. Soc. 313, 475–538. Alsed`a, Ll., Llibre, J., Misiurewicz, M. [2000] Combinatorial dynamics and entropy in dimension one, Advanced Series in Nonlinear Dynamics 5, World Scientific, second edition. Alsed`a, Ll., Ye, X. [1995] “No division and the set of periods for tree maps”, Ergod. Th. & Dynam. Sys. 15, 221–237. Baldwin, S. [1987] “Generalizations of a theorem of Sharkovskii on orbits of continuous real-valued functions”, Discrete Math. 67, 111–127. Baldwin, S. [1991] “An extension of Sharkovskii’s Theorem to the n-od”, Ergod. Th. & Dynam. Sys. 11, 249–271. Block, L. [1981] “Periods of periodic points of maps of the circle which have a fixed point”, Proc. Amer. Math. Soc. 82, 481–486. Block, L., Guckenheimer, J., Misiurewicz, M., Young, L.S. [1980] “Periodic points and topological entropy of one-dimensional maps”, Global theory of dynamical systems, pp. 18–34, SLNM 819, Springer, Berlin. Blokh, A.M [1991] “On some properties of graph maps: spectral decomposition, Misiurewicz conjecture and abstract sets of periods”, preprint, Max Planck Institut f¨ur Mathematik, Bonn. Blokh, A.M [1992] “Periods implying almost all periods for tree maps”, Nonlinearity 5, 1375–1382. Denker, M., Grillenberger, C., Sigmund, K. [1976] Ergodic theory on compact spaces, SLNM 527, Springer, Berlin. Efremova, L.S. [1978] “Periodic orbits and a degree of a continuous map of a circle” (in Russian), Diff. and Integr. Equations (Gor’kii) 2, 109–115. Imrich, W., Kalinowski, R. [1985 a] “Periodic points of small periods of continuous mappings of trees”, Ann. Discrete Math. 27, 443–446. Imrich, W., Kalinowski, R. [1985 b] “Periodic points of continuous mappings of trees”, Ann. Discrete Math. 27, 447–460. Li, T.-Y., Misiurewicz, M., Pianigiani, G., Yorke, J.A [1982] “No division implies chaos”, Trans. Amer. Math. Soc. 273 191–199. Llibre, J., Misiurewicz, M. [1993] “Horseshoes, entropy and periods for graph maps”, Topology 32, 649–664. Misiurewicz, M [1982] “Periodic points of maps of degree one of a circle”, Ergod. Th. & Dynam. Sys. 2, 221–227. Misiurewicz, M., Nitecki, Z. [1991] “Combinatorial patterns for maps of the interval”, Mem. Amer. Math. Soc. 94, no. 456 Sharkovskii, A.N. [1964] “Co–existence of the cycles of a continuous mapping of the line into itself” (in russian), Ukrain. Math. Zh. 16 (1), 61–71. English translation in Proceedings of the Conference “Thirty Years after Sharkovskii’s Theorem: New Perspectives” (Murcia, 1994), Internat. J. Bifur. Chaos Appl. Sci. Engrg. 5(1995), 1263– 1273.