{'fraction_non_alphanumeric': 0.06550038825195267, 'fraction_numerical': 0.019123311865284185, 'mean_word_length': 3.341618191433104, 'pattern_counts': {'":': 0, '<': 72, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Braid forcing and star-shaped train tracks

Global results are proved about the way in which Boyland's forcing partial order organizes a set of braid types: those of periodic orbits of Smale's horseshoe map for which the associated train track is a star. This is a special case of a conjecture introduced in a previous paper, which claims that forcing organizes all horseshoe braid types into linearly ordered families which are, in turn, parameterized by homoclinic orbits to the fixed point of code 0.


Introduction and background
Given a discrete dynamical system and information about one of its periodic orbits, can one derive further information about the system: for example, the existence of other periodic orbits, or that it has positive topological entropy? The problem of periodic orbit forcing in particular -that is, to determine whether the presence of a certain periodic orbit implies the existence of other periodic orbits -has interested dynamicists for many years. Sharkovskii's theorem for self-maps of the real line is unrivalled in elegance: it defines a total order on the postive integers with the property that if m n then any continuous self-map of R which has a periodic orbit of period n must also have a periodic orbit of period m. Moreover, the theorem is sharp: for any initial segment of the order, there exists a continuous self-map of R having periodic orbits of the corresponding periods and no others. In this context, periodic orbits are specified by their period alone. One could also, for example, use the order on R to specify a periodic orbit by its permutation, and then consider forcing among permutations. Many authors have studied this problem, which is now quite well understood.
The corresponding problem in dimension 2 (i.e. for self-homeomorphisms of the disk D 2 ) is much harder. In this case, the period alone is an inadequate specification of a periodic orbit: given any set of positive integers which includes 1, a self-homeomorphism of D 2 (or indeed of any other surface) can be constructed which has periodic orbits of the given periods and no others. Boyland and others observed that, by analogy with the permutation in dimension 1, adding topological information about the way in which the points of a periodic orbit of a disk homeomorphism 'braid around' one another produces a non-trivial theory. More precisely, Boyland defined the braid type bt(P, f ) of a periodic orbit P of a disk homeomorphism f to be the isotopy class of f relative to P , up to topological change of coordinates. A braid type γ is then said to force another braid type β if every disk homeomorphism having a periodic orbit of type γ also has one of type β. Boyland showed that forcing is a partial order on the set of braid types. This leads to the question of how forcing organizes this set. Of course, if the question is to be answered, one must be able to decide how two given braid types are related by the partial order. This can be done using Bestvina and Handel's algorithmic proof of Thurston's classification theorem for surface homeomorphisms up to isotopy. However, not only is this process very time consuming in practice, but also the information it gives is only local, in the sense that the ability to compare two given braid types gives no information about the global structure of the partially ordered set of braid types. This paper gives global information about the restriction of the forcing order to a subset of braid types, namely those of periodic orbits of Smale's horseshoe map for which the associated train track is a star (that is, a tree with exactly one vertex of valence larger than 1). In [dCHb], a conjecture is stated which describes how forcing organizes all braid types of the horseshoe. It claims that the symbolic code of each periodic orbit can be parsed into two segments, the prefix and the decoration. All orbits with the same decoration have the same topological train track type, and form a family which is totally ordered by the forcing relation; the position of an orbit within this totally ordered set is determined by its prefix. Within families, this trivializes the problem of comparing braid types: simply compare their symbolic codes using the unimodal order. The conjecture also describes the forcing relation between families in terms of the forcing between homoclinic orbits associated to each family.
In this paper the conjecture is proved for the (infinite) family of decorations for which the corresponding train track type is a star. There is one such decoration for each rational m/n ∈ (0, 1/2]: the train track associated to m/n is a star with n edges, and the train track map rotates the central vertex of the star by m/n. The approach taken is to start with train track maps of the appropriate topological type, and to identify those of their periodic orbits for which the star is itself a train track (after it has been truncated outside the span of the orbit). The combinatorics of such orbits are intricately related to the position of the rational m/n within the Farey graph.
Only after these train track orbits have been determined is their relationship with periodic orbits of Smale's horseshoe investigated. Conceptually, the most important relationship between the horseshoe and the star maps (and indeed the relationship which motivates the conjecture under discussion) is that the star maps (or, more accurately, the corresponding thick tree maps) can be obtained from the horseshoe by pruning: that is, by performing an isotopy which destroys all of the dynamics within a given open subset of the disk, while leaving the dynamics unchanged elsewhere. Since this construction is not used elsewhere in the paper, however, it is only described on an intuitive level, and a less general approach to showing that star periodic orbits have horseshoe braid types is adopted. Section 1.1 describes the parsing of the code of a horseshoe periodic orbit into prefix and decoration, and provides a statement of the conjecture of [dCHb] and the special case of it which will be proved here. Section 1.2 contains a brief summary of the properties of the Farey graph which will be used in the remainder of the paper. The main results of the paper can be found in Section 2, in which star maps and the concept of a train track orbit are defined, and the set of such orbits is determined. Section 3 details the connection between the star maps and the horseshoe, and Section 4 is devoted to the proof of a technical lemma.
The paper is often technical: it is the nature of the subject. Its structure, however, is simple. Lemma 12 identifies the periodic orbits of the horseshoe which have the property that their period is equal to the sum of the denominators of the endpoints of their rotation interval. The symbolic codes of these orbits have the property that the prefix is determined by one endpoint of the rotation interval, and the decoration by the other. Having described the combinatorics of train track orbits of star maps (Section 2), it is possible to compute their rotation intervals, which have the property considered in Lemma 12. Since star orbits have horseshoe braid type (Section 3), it follows that the symbolic codes of the train track orbits are as given by the lemma. The total order within families follows directly from the nature of the maps being considered.
1.1. Prefix and decoration for horseshoe periodic orbits. In this paper the standard model F : D 2 → D 2 of Smale's horseshoe map [Sma67] depicted in Fig. 1 will be used; symbolic dynamics in the set Σ 2 = {0, 1} Z is applied in the usual way to describe points x ∈ D 2 whose (past and future) orbits lie entirely in the square S. The definitions and results summarized in this section can be found in [Hal94,dCHb].
PSfrag replacements 0 1 S Figure 1. Symbolic dynamics for the horseshoe A periodic orbit P of F of (least) period n is described by its code c P ∈ {0, 1} n , which is given by the first n symbols of the itinerary k(p) of its rightmost point p: thus, for example, the period 5 orbit which contains the point with itinerary 01001 has code 10010. A word w ∈ {0, 1} n is therefore the code of a period n horseshoe orbit if and only if it is maximal: that is, the infinite repetition w ∈ {0, 1} N of w is strictly greater than its shifts σ i (w) in the unimodal order for 1 ≤ i < n.
The following definitions are due to Boyland [Boy84,Boy94]. Let f : D 2 → D 2 and g : D 2 → D 2 be orientation-preserving homeomorphisms having periodic orbits P and Q respectively. Then (P, f ) and (Q, g) have the same braid type if there is a homeomorphism h : (D 2 , P ) → (D 2 , Q) such that f : (D 2 , P ) → (D 2 , P ) is isotopic (rel. P ) to h −1 • g • h : (D 2 , P ) → (D 2 , P ) (if either P or Q lies on ∂D 2 , then the corresponding homeomorphism should first be extended arbitrarily over an exterior collar). The braid type bt(P, f ) of (P, f ) is its equivalence class under this relation. Since the braid types of period n orbits correspond to conjugacy classes in the mapping class group of the n-punctured disk, they can be classified as finite order, reducible, or pseudo-Anosov by means of Thurston's classification [Thu88]. Boyland's forcing relation ≤ on the set BT of braid types is defined as follows: β ≤ γ if and only if every orientation-preserving homeomorphism f : D 2 → D 2 which has a periodic orbit of braid type γ also has one of braid type β. Boyland proved [Boy84,Boy94] that ≤ is a partial order on BT.
An alternative characterisation of braid type indicates the dynamical significance of the definition: (P, f ) and (Q, g) have the same braid type if and only if there exists an isotopy {f t } from f to g and a path P t in (D 2 ) n from P to Q such that P t is a (least) period n orbit of f t for all t.
The braid type bt(P, F ) of a horseshoe periodic orbit P will here be denoted simply by bt(P ). It is well known that two periodic orbits P and Q of the horseshoe whose codes c P and c Q differ only in their final symbol have the same braid type. Thus, for example, the two orbits with codes 10010 and 10011 have the same braid type; the code of either one of these orbits is often written c P = 1001 0 1 to reflect the fact that the distinction between the two is unimportant in so far as braid type is concerned.
The conjecture presented in [dCHb] is based upon the parsing of the code of any horseshoe periodic orbit P which is not of finite order braid type into two parts: the prefix and the decoration. In order to define these, it is necessary first to describe the height q(P ) ∈ (0, 1/2] ∩ Q of P : this is an invariant of braid type which plays a central role in the conjecture. Motivation for the definition is given in [Hal94], and a program for computing heights of horseshoe periodic orbits can be found at [Hal]. Definitions 1. Let c ∈ {0, 1} N be a sequence containing infinitely many 1s. If c starts with 0 or with 11, then define the height q(c) of c to be 1/2. Otherwise, write where each κ i ≥ 0, each µ i is either 1 or 2, and µ i = 1 only if κ i+1 > 0 (thus κ i and µ i are uniquely determined by c). For each r ≥ 1, define If there is a (least) integer s ≥ 1 such that either µ s = 1 or The height q(c) of c is given by x if µ s = 2 and w < z for all w ∈ I s+1 (c) and z ∈ s i=1 I i (c) y if µ s = 1, or µ s = 2 and w > z for all w ∈ I s+1 (c) and z ∈ s i=1 I i (c). Let P be a horseshoe periodic orbit with code c P . If the sequence c P ∈ {0, 1} N does not contain the word 010, then change the final symbol of c P from 1 to 0. Then the height q(P ) of P is defined to be q(c P ).
It is immediate from this description that the words c q are palindromic: that is, κ i = κ m+1−i for all i.
Theorem 3. a) Let P be a horseshoe periodic orbit with height q(P ) = m/n in lowest terms. Then P has period n if and only if it has finite order braid type: in this case, F is isotopic rel. P to a rigid rotation through 2πm/n. Otherwise, the period of P is at least n + 2, and c P starts with the word c m/n . b) Let P and R be horseshoe periodic orbits. If bt(P ) ≥ bt(R) then q(P ) ≤ q(R). In particular, height is an invariant of braid type.
Thus the code c P of a horseshoe periodic orbit which is not of finite order braid type can be written c P = c q(P ) v for some word v of length at least 1. This makes possible the following definitions, which are taken from [dCHb]: Definitions 4. Let P be a period N orbit of the horseshoe which is not of finite order braid type, with height q = q(P ) = m/n. The prefix of P is the word c q . The decoration of P is defined to be * if N = n + 2, and to be the element w of {0, 1} N −n−3 such that Example 5. Let P be the period 17 orbit with code c P = 10011011001011010. Then q(P ) = 3/10 as shown in Example 2. Hence P has prefix 10011011001 = c 3/10 , and decoration 1101.
Only certain heights q are compatible with a given decoration w (namely those for which c q 0 1 w 0 1 is a maximal word, and hence describes the rightmost point of a periodic orbit). The following lemma (from [dCHb]) gives the compatibility conditions: Lemma 6. Let w be a decoration, and define q w ∈ (0, 1/2] ∩ Q by q * = 1/2 and Then each of the four words c q 0 1 w 0 1 (or each of the two words c q 0 1 when w = * ) is maximal of height q when 0 < q < q w , and none is maximal of height q when q w < q ≤ 1/2.
The reason that the four orbits with codes c q 0 1 w 0 1 are considered together is that they all have the same braid type: the following general result will appear in [dCHa]. That the braid type is unchanged on changing the final symbol of the code is a triviality: the content of the theorem is that changing the symbol between prefix and decoration also leaves the braid type unchanged.
Theorem 7. Let w = * be a decoration, and q ∈ (0, q w ) ∩ Q. Then the four horseshoe periodic orbits with codes c q 0 1 w 0 1 have the same braid type. The following conjecture is motivated and stated in [dCHb]. It involves the notion of two horseshoe periodic orbits of pseudo-Anosov braid type having the same topological train track type. A formal definition of this term can be found in [dCHb]: however its intuitive meaning should be clear in the context of this paper (in which 'star' train track types are considered).
Conjecture 8. a) Let P be a horseshoe periodic orbit with height q and decoration w. If q = q w then P has pseudo-Anosov braid type.
b) Let P ′ be another periodic orbit with height q ′ and decoration w. Then bt(P ′ ) ≤ bt(P ) if and only if q ≤ q ′ (i.e. the set of braid types of periodic orbits with decoration w is totally ordered by the forcing relation). Moreover, if q ′ < q w then P and P ′ have the same topological train track type. c) There is an equivalence relation ∼ on the set D of decorations with the property that two horseshoe periodic orbits have the same braid type if and only if they have equal heights and equivalent decorations. d) There is a partial order on D/∼ with the property that if P and P ′ are periodic orbits with heights q, q ′ and decorations w, w ′ such that q < q ′ and [w ′ ] [w], then bt(P ′ ) ≤ bt(P ).
Notice that part b) trivializes the problem of comparing braid types within a family of fixed decoration: the forcing order is given by the unimodal order on the codes of the periodic orbits. As explained in [dCHb], parts a) and b) of this conjecture (i.e., the statements which only concern a single decoration) can be proved for certain particular choices of decoration w. In this paper an infinite family of decorations is considered, making it possible to address parts c) and d) of the conjecture meaningfully. The decorations concerned are those which give rise to 'star' topological train track types, and are given by words w q with q ∈ (0, 1/2] ∩ Q defined as follows: Definition 9. Let q = m/n ∈ (0, 1/2] ∩ Q. If q = 1/2 then w q is the element of {0, 1} n−3 obtained by deleting the initial symbols 10 and the final symbols 01 from c q . If q = 1/2 then w q = * .
Thus, for example, w 1/3 is the empty decoration, w 1/4 = 0, w 1/5 = 00, and w 2/5 = 11. These decorations satisfy q wq = q, are mutually non-equivalent under ∼, and are totally ordered by , with w q w q ′ if and only if q ≤ q ′ . Thus the proof of Conjecture 8 above for these decorations gives the following theorem, which summarizes some of the main results of this paper.
Theorem 10. Let r, r ′ ∈ (0, 1/2] ∩ Q and q, q ′ ∈ (0, 1/2) ∩ Q with q ≤ r and q ′ ≤ r ′ . Let P be a horseshoe periodic orbit of height q and decoration w r , and P ′ be a horseshoe periodic orbit of height q ′ and decoration w r ′ . Then a) If q = r then P has pseudo-Anosov braid type. b) If r = r ′ and q, q ′ < r then P and P ′ have the same (star) topological train track type. Moreover bt(P ′ ) ≤ bt(P ) if and only if q ≤ q ′ . c) P and P ′ have the same braid type if and only if q = q ′ and r = r ′ . d) If q < q ′ and r ≥ r ′ then bt(P ′ ) ≤ bt(P ).
Part a) of this theorem is given by Corollary 13 below, Part b) by Theorem 50, and Part c) by Theorem 7 and Lemma 12, as described following the statement of Lemma 12. Part d) is proved using quite different techniques from those of this paper: a proof will appear in [dCHa].
Lemma 12 below will be used to identify periodic orbits with decoration w m/n for some m/n ∈ (0, 1/2]. Its proof is relatively long and technical, and uses methods from [Hal94] which are not required elsewhere in this paper -it has therefore been relegated to Section 4.
Definitions 11. Let P be a horseshoe periodic orbit of period N > 1. The rotation number ρ(P ) ∈ (0, 1/2] ∩ Q of P is its F -rotation number about the fixed point with code 1. The rotation interval of P is the set The rotation number of a horseshoe periodic orbit is an invariant of braid type [Hal94] (this statement is not quite as obvious as it may at first appear), and hence so also is the rotation interval. By a theorem of Handel [Han90], ρi(P ) is equal either to {ρ(P )} or to a set of the form [a, b] ∩ Q (which will here be denoted simply [a, b]) for some a < b ∈ Q. In other words, if the period of P is equal to the sum of the denominators of the endpoints of its rotation interval, then P has height u/v and decoration w m/n . Since the rotation interval is a braid type invariant, it follows that if P has height q and decoration w r , and P ′ is a horseshoe periodic orbit with the same braid type as P , then P ′ also has height q and decoration w r . In particular, this establishes (and extends) the 'only if' part of Theorem 10 c). The 'if' part follows from Theorem 7. Moreover, the following corollary provides a proof of Theorem 10 a).
Corollary 13. Let u/v < m/n ≤ 1/2. Then the horseshoe periodic orbits of height u/v and decoration w m/n have pseudo-Anosov braid type.
Proof. Let P be a periodic orbit of height u/v and decoration w m/n . Then ρi(P ) = [u/v, m/n]. Periodic orbits of finite order type have trivial rotation intervals. If P had reducible braid type, then a horseshoe periodic orbit of period less than v +n (namely one given by the isotopy class corresponding to the outermost reducible component of F : (D 2 , P ) → (D 2 , P )) would also have rotation interval [u/v, m/n], contradicting Lemma 12.
Lemma 12 may be of independent interest. The authors know of no pseudo-Anosov homeomorphism f of the annulus, relative to a single periodic orbit P , for which the sum of the denominators of the endpoints of the rotation interval of f is less than the period n of P . If this more general result could be proved, then (together with the fact [BGH93] that the rotation number m/n of P is contained in the interior of the rotation interval of f ) it would provide a natural generalization of Boyland's theorem [Boy92], which gives bounds on the size of the rotation interval in the case where m and n are coprime.
1.2. The Farey Graph. In this section some well known results about Farey sequences and the Farey graph are presented, some notation is introduced, and some simple number-theoretic lemmas which will be used later are stated. In the usual treatment (see for example [HW79], where the assertions made in this section are proved), the Farey sequences contain rationals between 0 and 1: since only rationals between 0 and 1/2 are of interest in this paper, the definitions have been modified accordingly. Throughout the paper, all rationals are assumed to be written in lowest terms.
Definitions 14. Let n ≥ 1 be an integer. The Farey sequence F n of order n is the (finite) sequence of rational numbers in [0, 1/2] whose denominators do not exceed n, arranged in ascending order. Two rationals h/k and h ′ /k ′ in [0, 1/2] are Farey neighbours if there is some n such that they are consecutive elements of F n . Given a rational h/k ∈ (0, 1/2), the left and right Farey parents LFP(h/k) and RFP(h/k) are the elements of F k which precede and follow h/k; and h/k is said to be the Farey child of its parents.
In particular, both LFP(h/k) and RFP(h/k) are Farey neighbours of h/k. It is well known that if h/k < h ′ /k ′ are Farey neighbours, then h ′ k − hk ′ = 1; and that if LFP(h/k) = u/v and RFP(h/k) = p/q, then h = u + p and k = v + q.
The rationals in [0, 1/2] can be organized as the vertices of the Farey Graph, in which an edge joins two vertices if and only if one of the associated rationals is the left or right Farey parent of the other. Part of the Farey graph is depicted in Fig. 3. Notice that every vertex has infinite valence (that is, every rational is the parent of infinitely many other rationals). The immediate left (respectively right) Farey child of a rational m/n is the rational h/k of smallest denominator for which LFP(h/k) = m/n (respectively RFP(h/k) = m/n): it is the child of m/n and LFP(m/n) (respectively RFP(m/n)). Thus, for example, the immediate children of 2/5 are 3/8 and 3/7. The Farey sequences appear as finite connected subtrees of the Farey graph: for example, F 5 is shown in the figure with bolder lines.
Definition 16. Let m/n be a rational in (0, 1/2), and denote addition modulo n by + n . Given r, s ∈ Z n , let That is, O m/n [r, s] is the shortest segment of the orbit of r in Z n under addition of m which ends with s. When r ≤ s are integers, the notation [r, s] will also be used as a shorthand for {r, r + 1, . . . , s}.
The following simple Lemma contains the results about the Farey graph which will be needed in the remainder of the paper.
The function defined in the following lemma will play a central role in this paper.
Lemma 18. Let u/v < p/q be Farey neighbours. Then the function is an increasing bijection.
Notice in particular that ξ u/v,p/q (1/2) = (u + p)/(v + q) is the Farey child of u/v and p/q.

Periodic orbits of star maps
2.1. Star maps and * -orbits. For each n ≥ 2 let Γ n ⊆ D 2 be an n-star: that is, a tree with n edges e 0 , . . . , e n−1 of equal length, each of which has a valence 1 vertex at its initial point, and which meet at a valence n vertex v at their final points, cyclically ordered according to their indices. For each rational m/n ∈ (0, 1/2] (written in its lowest terms), let f m/n : Γ n → Γ n be the tree map (see Fig. 4 Figure 4. The tree map f 2/5 : Γ 5 → Γ 5 and the thick tree map F 2/5 : T 5 → T 5 Let F m/n : T n → T n be a thick tree map (see for example [dCH01] for a formal definition) corresponding to f m/n : Γ n → Γ n (see Fig. 4). Thus T n ⊆ D 2 is a topological disk, and there is a continuous map p : T n → Γ n such that p −1 (x) is a disk if x is a vertex of Γ n , and an interval otherwise. The map F m/n is an embedding which contracts each such decomposition element p −1 (x) into a decomposition element, in such a way that it induces f m/n on Γ n (so F m/n (p −1 (x)) ⊂ p −1 (f m/n (x)) for all x ∈ Γ n ). Where necessary, F m/n is considered as a homeomorphism D 2 → D 2 , by extending from T n without introducing any new periodic orbits.
There is a natural one-to-one correspondence (which will be invoked without comment in the remainder of the paper) between the periodic orbits of f m/n and those of F m/n (with a periodic point x of f m/n corresponding to the unique periodic point of F m/n in p −1 (x)). Notice that F 1/2 is the horseshoe map F after blowing up the leaf containing the fixed point of code 1 into a disk: in particular, there is a braid type preserving bijection between the set of periodic orbits of F 1/2 and the set of periodic orbits of F .
In this paper only periodic orbits P which satisfy certain non-triviality conditions are considered: * d) If p r denotes the point of P ∩ e r closest to the initial point of e r , then f m/n (p r ) = p r+nm for all r = 0.
The reasons for imposing three of these conditions are intuitively clear: a) states that P is not a fixed point; b) that it explores each of the edges of Γ n ; and c) that the points of P in e 0 have images in more than one edge: if this were not true, the braid type of P would either be finite order (if each edge contained just one point of P ) or reducible (with n reducing curves, each bounding a disk containing the points of P on one of the edges of Γ n ). Condition d) is less clear: the motivation is that when f m/n is 'truncated' with respect to P (see Definition 23), there is only one point of P (namely the preimage of p m ) at which f m/n is not locally injective. Lemma 21 below is one important consequence of this condition.
Definition 20. Let P be a periodic orbit of f m/n . Then the span Γ P n of P is the smallest connected subset of Γ n containing P .
Lemma 21. Let m/n ∈ (0, 1/2]. Then the set of spans of * -orbits of f m/n is totally ordered by inclusion. Proof. Let P and P ′ be * -orbits of f m/n , and for each 0 ≤ r < n let p r , p ′ r ∈ e r be the points of the orbits closest to the initial point of e r (which exist by * b)). If p m is closer to the initial point of e m than p ′ m , then applying * d) inductively gives that p r is closer than p ′ r to the initial point of e r for all r, and hence Γ P ′ n ⊆ Γ P n . The following result, which is contained in Theorem 53 below, makes it possible to identify the braid types of * -orbits using Lemma 12. It reflects the fact that the thick tree maps F m/n : T n → T n can be obtained from the horseshoe by pruning (i.e. by destroying some dynamics), as described in Section 3.1.
Lemma 22. Every * -orbit of f m/n has the braid type of some periodic orbit of the horseshoe.

2.2.
Describing * -orbits. In this section a combinatorial method for describing * -orbits is developed. Since f m/n (e r ) = e r+nm for r = 0, the main work required is in describing the images of the points of the orbit in e 0 . The first step is to make precise the notion of truncating f m/n with respect to a * -orbit P .
Definition 23. Let P be a * -orbit of f m/n . Let r P : Γ n → Γ P n be the map defined by r P (x) = x if x ∈ Γ P n , and r P (x) is the endpoint of Γ P n contained on the same edge of Γ n as x if x ∈ Γ P n . The truncation f P m/n of f m/n with respect to P is the map f P m/n = r P • f m/n : Γ P n → Γ P n . The following definitions give a basic classification of * -orbits.
Definitions 24. Let P be a * -orbit of f m/n with #(P ∩ e 0 ) = N , and label the points of P ∩ e 0 as p 0 , p 1 , . . . , p N −1 in order from the initial to the final point of e 0 . Define a partition and only if f m/n (p i ) is the point of P closest to the initial point of e m , and hence #C = 1.
Given a rational m/n ∈ (0, 1/2], an integer k ∈ {0, . . . , m − 1}, and γ ∈ {A, B} (with γ = B if k = 0), write P(m/n, k, γ) for the set of all * -orbits of f m/n with f (p 0 ) ∈ e k and 0 ∈ γ, P(m/n, k) = P(m/n, k, A) ∪ P(m/n, k, B), and P(m/n) = k P(m/n, k), the set of all * -orbits of f m/n . The rest of the description of a * -orbit is contained in the next definitions.
Definitions 25. For each integer n ≥ 2, define D n to be the set of all triples where N r is a positive integer for 0 ≤ r < n; π is a cyclic permutation of the set and (A, B, C) is a partition of {0, . . . , N 0 − 1} with #C = 1.
Let P ∈ P(m/n, k, γ). Then the data of P is the element of D n obtained as follows: N r = #(P ∩ e r ) for each r with 0 ≤ r < n. Identify P with L = L d(P ) = {(r, s) : 0 ≤ r < n, 0 ≤ s < N r } by labelling the points of P ∩ e r as (r, 0), (r, 1), . . . (r, N r − 1) from the initial to the final point of e r , and let π = f | P : L → L. Finally, let (A, B, C) be the partition of {0, . . . , N − 1} given by Definitions 24.
Having the same data is the basic equivalence relation which says that two * -orbits have the same 'shape'. In particular, it is clear that two * -orbits with the same data have the same braid type as periodic orbits of F m/n : T n → T n . In this paper no distinction is made between orbits with the same data: thus, for example, the statement that f m/n has exactly one * -orbit with a given property should be interpreted as meaning that * -orbits with the given property exist, and all have the same data.
Example 26. Let P ∈ P(2/5, 1, A) be the periodic orbit depicted in Fig. 5. Then N 0 = N 1 = N 3 = 2 and N 2 = N 4 = 1; and A = {0}, B = ∅, and C = {1}. The cyclic permutation π is given by The data of a periodic orbit will usually be written in the form above: the partition A ∪ B ∪ C is denoted by letters above the elements (0, s) of L, and the integers N r can be deduced from the elements of L. For simplicity, it is not explicitly noted that (3, 0) → (0, 0). Note that by * d), the cycle notation of π always ends (m, 0) → (2m, 0) → · · · → (n − m, 0). The reader seeking further clarification should consult Examples 30, 38, and 46, where other * -orbits are described in this way.
Given d ∈ D n , one can ask whether or not there exists P ∈ P(m/n, k, γ) with d(P ) = d. This imposes obvious conditions on d, which are expressed by the following result. While hardly concise, the conditions are in an ideal form for later use. If d ∈ D n satisfies these conditions, it will be said that d is legal data.
Lemma 27. An element ((N r ), π, (A, B, C)) of D n is equal to d(P ) for some P ∈ P(m/n, k, γ) if and only if the following conditions hold: LD a) For all r > 0: i) π 1 (r, s) = r + n m for all s, and π 2 (r, s) is increasing in s.
Sketch Proof. The necessity of the conditions is obvious. Their sufficiency can be shown as follows: divide e 0 into 2m + 1 subintervals, each mapped by f m/n over exactly one edge of Γ n ; constuct a Markov graph for f m/n using these subintervals and the edges e r with r > 0 as the Markov partition. Given k, γ, and an element d = ((N r ), π, (A, B, C)) of D n satisfying LD a) and LD b), conditions a)i), b)iii) and b)iv) ensure that there are exactly two loops in the Markov graph which are compatible with the first component π 1 of π and with the partition (A, B, C) (two since the element (0, s) of L with s ∈ C corresponds to the common endpoint of two intervals in the partition). Pick either of these loops, and let P be the periodic orbit of f m/n corresponding to it. Then conditions b)i) and b)ii) ensure that it belongs to P(m/n, k, γ), conditions b)iv) -vi) ensure that the data of P agree with the second component π 2 of π, and condition a)ii) ensures that P is a * -orbit.
This sort of argument is routine and tedious, and will be abbreviated when it occurs in earnest in the proof of Theorem 37.
2.3. The Train Track Condition. The main question addressed in this paper is: for which P ∈ P(m/n) is Γ P n itself a train track for the isotopy class of F m/n relative to P ? The essential property of a train track is efficiency: intuitively, this says that at any point x of Γ P n at which (f P m/n ) i is not locally injective for some i, the image (f P m/n ) i (U ) of a small neighbourhood U of x 'wraps around' a point of P , and hence cannot be 'pulled tight' without passing through P . Efficiency can be detected as follows. By condition * d), the only point at which such pulling tight could occur is (m, 0). For each point p of P which is not an endpoint of Γ P n (i.e. p = (r, 0) for 0 ≤ r < n), an arc passing on one side of p will wrap around (m, 0) under the appropriate iterate of f P m/n , while an arc passing on the other side will not, and its image can be pulled tight. Provided all of the arcs in the image f P m/n (Γ P n ) of Γ P n pass on the 'correct' side of each point of P , the map f P m/n is efficient, and hence is a train track map for the isotopy class of F m/n : D 2 \ P → D 2 \ P .
The first part of the next definition gives a partition of P \ {(r, 0) : 0 ≤ r < n} into two sets, α and β: for those points p of P in α, an arc passing p to the left (according to the orientation of the edge e r containing p) wraps around (m, 0); while for those in β, an arc passing to the right wraps around (m, 0). It is then possible to make a combinatorial definition of efficiency, as given by conditions TT a) -TT d) below.
The set of all train track orbits in P(m/n, k, γ), in P(m/n, k), and in P(m/n) will be denoted T T (m/n, k, γ), T T (m/n, k), and T T (m/n).
The TT conditions have intuitive motivations. TT a) ensures that arcs of f P m/n (Γ P n ) pass on the 'correct' side of images of points of P ∩ e 0 : for example, if s ∈ B and π 1 (0, s) = r, then an arc of f P m/n (e r+n−m ) passes to the left of π(0, s) and hence π(0, s) must lie in α to avoid a violation of efficiency. TT b) reflects the fact that for k < r < m, the image of e 0 passes images of points of P ∩ e r+n−m on both sides: hence efficiency will be violated if there is any such point other than the one with image (r, 0). TT c) reflects that the image of e 0 passes to the right of those images of points of P ∩ e k+n−m which are further from the initial point of e k than π(0, 0); and TT d) is a stronger version of the same condition in the case γ = A, when the image of e 0 passes on both sides of points of e k between the initial point and π(0, 0).
The TT conditions above are stated in a way which reflects this intuitive motivation. However they can be replaced by equivalent alternatives which are easier to work with in practice. This will be done in Lemma 34 below.
The reader familiar with this approach to train tracks should accept without further argument that the TT conditions are the appropriate combinatorial expression of efficiency. However, a more precise statement is given by the following definition (which connects the intuitive notion of a train track with the definition due to Bestvina and Handel [BH95], and in particular, by introducing peripheral loops around the points of P , makes it possible to be precise about the concept of 'wrapping around' a point of P ) and by Theorem 32. The rather contorted definition can most easily be understood by referring to Fig. 7. Since BH(P, L, R) is a spine of T n \ P , the thick tree map F m/n : T n → T n induces a well defined homotopy class of graph maps g : BH(P, L, R) → BH(P, L, R). If g is required to restrict to a homeomorphism of the subgraph of peripheral edges, to send vertices to vertices, and to be locally injective away from its vertices, then the image edge-paths of g are also well-defined. BH(P, L, R) is said to be a Theorem 32. Let P ∈ P(m/n, k, γ). Then P has a Bestvina-Handel star train track if and only if P is TT.
Sketch Proof. A straightforward argument shows that BH(P, L, R) is absorbed if and only if L = β and R = α: the procedure for constructing inductively the unique partition L ∪ R for which BH(P, L, R) is absorbed is identical to that by which the partition α ∪ β is defined.
Thus it is only required to show that BH(P, β, α) is efficient if and only if P is TT. For each u = v with 0 ≤ u, v < n, write t u,v for the edge-path e u,Nu−1 e v,Nv −1 , and observe that BH(P, β, α) is efficient if and only if the image edge-path g(e r,s ) of each main edge can be written in the form g(e r,s ) = m 1 p 1 m 2 p 2 . . . , m k−1 p k−1 m k , where each p i is a peripheral edge (or its inverse), and each m i is either a main edge (or its inverse), or one of the edge-paths t u,v . If this condition holds, then a straightforward induction shows that it holds also for g n (e r,s ) for all n > 0, and hence there cannot be any cancellation in any of these edge-paths. If the condition fails, then the edge-path g(e r,s ) contains some word e u,v e u,v+1 (or its inverse), which under iteration yields the word e m,0 e m,0 .
If P is not TT, then one of the conditions TT a) -TT d) fails. In each case, an argument arising from the intuitive motivation of the conditions can be used to show that there is some g(e r,s ) which contains a word of the form e u,v e u,v+1 or its inverse. Hence BH(P, β, α) is not efficient.
For the converse, suppose that P is TT. If BH(P, β, α) is not efficient, then there is some edge e u,v such that g(e u,v ) contains a word of the form e r,s−1 e r,s or e r,s e r,s−1 . This implies that u = 0 or u ≥ k + n − m (i.e. that 0 ≤ r ≤ m), since otherwise g(e u,v ) = e u+nm,v is an edge-path of length 1.
There are two cases to consider. First suppose that π 1 −1 (r, s) = 0. Then TT b) gives r = k (and hence π 1 −1 (r, s) = k + n − m). Thus u = 0, since only e 0 and e k+n−m have images intersecting e k . If γ = B then, since g(e 0,v ) passes to the right of (r, s), it can only contain the word e k,s−1 e k,s if π 2 (0, v) < s and (r, s) ∈ α. This contradicts TT c). If γ = A then a similar contradiction to TT c) and TT d) arises.
The case where π 1 −1 (r, s) = 0 can be treated similarly using TT a).  As mentioned above, there is an alternative form of the TT conditions which is often easier to work with: Lemma 34. Consider the conditions TT ′ a) #A = 1, and if A = {s} and j > 0 is least such that τ 1 (π j (0, s)) = 0, then C = {τ 2 (π j (0, s))}. TT ′ d) If γ = A then π(0, 0) = (k, 1). Then TT a) and TT ′ a) are equivalent; and if they hold then TT d) and TT ′ d) are equivalent. Moreover, if TT a) and TT c) hold then there is at most one s with π 2 (k + n − m, s) ≥ π 2 (0, 0).
Proof. The equivalence of TT a) and TT ′ a) follows easily from the definition of the partition α∪β: note that TT ′ a) says simply that reading the partition A ∪ B ∪ C along the cycle notation of π, one sees B N0−2 AC. In particular, since the cycle notation starts with (0, 0), this implies that if γ = A then N 0 = 2: since π 1 (0, 1) = m and π 1 (0, 0) = k < m, the equivalence of TT d) and TT ′ d) follows. For the final statement, note that the elements of β are precisely those which lie between the element of A and the element and the element of C in the cycle notation of π, and only one such can lie in e k : also it is not possible that π 2 (k + n − m, s) = π 2 (0, 0), since this would imply π(k + n − m, s) = π(0, 0).
If P ∈ T T (m/n), then it follows from the results of [BH95] that the set of braid types forced by bt(P ) is precisely the set of braid types of periodic orbits of f m/n whose span is contained in the span of P . In particular, Lemma 21 gives: Theorem 35. The set {bt(P, F m/n ) : P ∈ T T (m/n)} is totally ordered by the forcing relation.
2.4. The TT condition in the horseshoe. The elements of T T (1/2) = T T (1/2, 0, B) were calculated in [Hal94]: in this case the partition α ∪ β is precisely that defined on page 880 of [Hal94], and conditions TT a) and TT c) are equivalent to the condition that π has no bogus transitions, also on page 880 of [Hal94] (while TT b) and TT d) are vacuous). Theorem 2.1 and lemma 2.4 of [Hal94] then give the following result (in which the words c q are as defined in Section 1.1).

2.5.
Renomalizing horseshoe TT orbits (the case k = m − 1). Theorem 36 gives a relatively straightforward approach to determining the elements of T T (m/n, m− 1, B) for each m/n ∈ (0, 1/2): the next result defines a 'renormalization operator' φ, which is a bijection from the set P(1/2, 0, B) of horseshoe periodic orbits to the set P(m/n, m − 1, B) with the property that φ(P ) is TT if and only if P is TT. Example 28 is the simplest case of this operator, when m/n = 1/3.
For notational simplicity, m/n will be taken to be a fixed rational in (0, 1/2) throughout this section, and the dependence of some objects (such as φ) upon it will be dropped.

Figure 8. A periodic orbit in the horseshoe
Then φ(P ) ∈ P(2/5, 1, B) is given by Fig. 9). It can easily be checked that both of these orbits are TT. The figures also show the idea of the construction: the pattern of the periodic orbit of f 1/2 is replicated in the edges e m−1 and e m of Γ n . Figure 9. The periodic orbit in P(2/5, 1, B) obtained from that of Fig. 8 Proof. The first step is to show that the construction yields a well-defined function φ : P(1/2, 0, B) → P(m/n, m − 1, B): that is, that it transforms legal data to legal data.
(The sets A, B, and C are unchanged by construction.) It is routine to show that conditions LD a) and LD b) of Lemma 27 hold for this data, and hence that φ : P(1/2, 0, B) → P(m/n, m − 1, B) is well defined as required. To show that it is a bijection, observe that if P ∈ P(m/n, m − 1, B) has data d(P ) = ((N r ), π, (A, B, C)), then conditions LD a)i) and LD b)iv) ensure that every occurrence of (m − 1, s) in the cycle representation of π is followed by for some γ ∈ {A, B, C}, and every occurrence of (m, s) is followed by − 1, s).
Replacing the first type of block with γ (0, s) and the second with (1, s) thus defines an inverse ψ : P(m/n, m− 1, B) → P(1/2, 0, B) of φ (checking that the data so obtained is legal is again routine).
Theorem 39. Let u/v = LF P (m/n) and p/q = RF P (m/n). Let r/s ∈ (0, 1/2). Then φ(P r/s ) has height ξ u/v,p/q (r/s) and decoration w m/n . Proof. By Theorem 36, φ(P r/s ) has period (s − r + 1)#O m/n [m − 1, 0] + (r + 1)#O m/n [m, n − 1], which, by Lemma 17, is equal to (s − r + 1)v + (r + 1)q. It will be shown that φ(P r/s ) has rotation interval which will establish the result by Lemmas 12 and 22. If P is a * -orbit with data d(P ) = ((N r ), π, (A, B, C)), then the rotation number of P about the fixed point is given by the number of times it cycles around Γ n divided by its period: that is, and hence ρ(φ(P )) = N 0 u + N 1 p N 0 v + N 1 q .
If P has period b and rotation number a/b then N 0 = b − a and N 1 = a, and so Now the rotation interval [r/s, 1/2] of P r/s is the set of rotation numbers of periodic orbits of f 1/2 contained in the span of P r/s , and, by a theorem of Boyland [Boy92], for each such rotation number a/b there exists such an orbit with period b. Likewise, the rotation interval of φ(P r/s ) is the set of rotation numbers of periodic orbits of f m/n contained in the span of φ(P r/s ); but these orbits are precisely the images under φ of those defining the rotation interval of P r/s . Hence the rotation interval of φ(P r/s ) is Remark. If n ≥ 2 then P(1/n) = P (1/n, 0, B), and hence the results of this section give a complete description of T T (1/n): there is a bijection q → P 1/n q from (0, 1/n) ∩ Q to T T (1/n) such that P 1/n q has height q and decoration w 1/n = 0 n−3 . In other words, P 1/n q has the same braid type as the horseshoe orbits of code c q The set of all m/n-admissible integers k is denoted A m/n . Lemma 41. Let m/n ∈ (0, 1/2) and k ∈ [0, m − 1]. If k ∈ A m/n , then T T (m/n, k) is empty.
Proof. Suppose P ∈ T T (m/n, k) has data d(P ) = ((N r ), π, (A, B, C)). Then by TT b), N r+n−m = 1 for all r with k < r < m. Applying LD a) i) inductively, it follows that N s = 1 for all s ∈ k<r<m O m/n [m, r +n−m]. However N k > 1, since π 2 (0, 0) = π 2 (k + n − m, 0) = k. Thus T T (m/n, k) must be empty unless k ∈ k<r<m O m/n [m, r+n−m]. However, this condition is equivalent to k ∈ O m/n [r, 0] for all r with k < r < m; which is in turn equivalent to r ∈ O m/n [k, 0] for all r with k < r < m: that is, to m/n-admissibility.
The remainder of this section is devoted to studying the structure of the set A m/n . It will be seen in Section 2.7 that the converse to Lemma 41 is also true: if k ∈ A m/n , then T T (m/n, k) is non-empty.
Notice that 0, m − 1 ∈ A m/n for all m/n: in particular A 1/n = {0}. Lemma 42 below connects A m/n with A LFP(m/n) , and hence yields an inductive description of A m/n for all m/n.
It follows that A m/n = {m − 1} ∪ ψ m/n | Zn\R m/n −1 (A u/v ), and in particular that A m/n has one more element than A u/v . Since A 1/n = {0} for all n, the following result holds: Corollary 43. Let m/n ∈ (0, 1/2). Then A m/n has the same cardinality as LFS(m/n).
The following result will be important in the next section.
Lemma 44. Let LFS(m/n) = (0 = u 1 /v 1 , u 2 /v 2 , . . . , u α /v α ), and let the elements of A m/n be 0 = k 1 < k 2 < · · · < k α = m − 1. 2.7. Train track orbits with k < m − 1. Let m/n ∈ (0, 1/2) with m > 1, and LFS(m/n) = (0 = u 1 /v 1 , u 2 /v 2 , . . . , u α /v α ). By Corollary 43, A m/n has α elements, which will be denoted 0 = k 1 < k 2 < · · · < k α = m − 1. Let i < α, and define The dependence of the sets on m/n and i is suppressed, since these two variables will remain fixed throughout the section. R, S, and T are mutually disjoint by Lemma 44, and hence define a partition of Z n . The cardinalities of T and S are given by Lemma 44, and the cardinality of R can therefore be deduced: The following theorem gives a complete description of T T (m/n, k i , B): Theorem 45. There is a bijection from (0, 1)∩Q to T T (m/n, k i , B), defined as follows: if p/q ∈ (0, 1), then the element P i,p/q,m/n of T T (m/n, k i , B) corresponding to p/q has data d(P i,p/q,m/n ) = ((N r ), π, (A, B, C)) given by: and π(0, s) = π(r, s) = (r + n m, s) for all other (r, s).
A schematic representation of P i,p/q,m/n is shown in Fig. 10, which depicts the image of e 0 and of e ki+n−m through to e n−1 . e 0 contains q + 1 points of P , of which p are mapped to e ki (the other q + 1 − p points of P on e ki are images of points of P on e ki+n−m ); q − p are mapped to e ki+1 in the configuration shown; and one is mapped to e m .
That π 1 (0, s) is equal to k i , k i+1 or m for all s follows from ii) and vii). Then A = {µ} by the definition of µ, ii), and LD b) i),iii),v): the stated values of π 1 (0, s) are then immediate. ix) If r ∈ S then N r = N 0 − µ, and if r = k i + n − m then π(r, s) = (r + n m, s) for all s < N 0 − µ.
By viii), The result follows by vi) and LD a) i).
By ii), iii), iv) and ix), there is a segment of the orbit of π as follows: for some s. However s ∈ A by TT ′ a), and hence s = µ by viii).
These results are enough to show that d(P ) is as given in the statement of the theorem with p = µ and q = N 0 − 1. Conversely, the data given in the statement defines an element of T T (m/n, k i , B) by construction, provided only that π is a cyclic permutation. The proof is therefore completed by showing that given two integers p and q with 0 < p < q, the permutation π given in the statement is cyclic if and only if p and q are coprime. It is clear that for any (r, s), there is some K such that τ 1 (π K (r, s)) = 0; and that π vi (0, 0) = (0, q − p) = (0, 0). Hence the cyclicity of π is equivalent to the cyclicity of the first return permutation of π on {(0, s) : 1 ≤ s ≤ q}. Let ρ be this first return permutation, i.e. ρ(s) = τ 2 (π Ks (0, s)), where K s > 0 is least such that τ 1 (π Ks (0, s)) = 0 and τ 2 (π Ks (0, s)) = 0. Then a straightforward calculation shows that ρ is a rotation of [1, q] by −p, and hence is cyclic if and only if p and q are coprime. The next step is to identify the horseshoe braid types of these orbits: it will be shown that P i,p/q,m/n has period n + v i p + v i+1 (q − p) and rotation interval [ uip+ui+1(q−p) vip+vi+1(q−p) , m n ] = [ξ ui/vi,ui+1/vi+1 (p/q), m/n], and hence has height ξ ui/vi,ui+1/vi+1 (p/q) and decoration w m/n by Lemma 12. In constrast to the situation in Section 2.5, there is no renormalization operator to provide a short cut to these rotation intervals: instead, they will be calculated by Markov partition techniques. Although the calculation is rather complicated the techniques are quite standard, and as such only a sketch proof, outlining the main steps, is given, so as to enable the enthusiastic reader to reconstruct the proof without too much difficulty.
Theorem 47. P i,p/q,m/n ∈ T T (m/n, k i , B) has height ξ ui/vi,ui+1/vi+1 (p/q) and decoration w m/n . Sketch Proof. That P = P i,p/q,m/n has period n + v i p + v i+1 (q − p) is immediate from Theorem 45 and the cardinalities of the sets R, S, and T . The rotation interval of P can be determined using Markov partition techniques, using the partition of Γ P n into intervals whose endpoints are the points of P and the valence n vertex v: the interval with endpoints (r, s) and either (r, s + 1) or v is labelled < r, s >. The Markov graph with these intervals as vertices can in principle be determined from the expression for π given in Theorem 45. Each loop in the Markov graph corresponds to a periodic orbit Q of f m/n whose braid type is forced by that of P : the rotation interval of P is the set of rotation numbers of such orbits about v. To calculate the rotation number corresponding to a given loop, one counts the number of times it goes around the star (i.e. the number of occurences of < r, s > in the loop where r ≥ n − m), and divides by its length.
It is clear that no such orbit can have rotation number greater than m/n, and that there is an orbit with this rotation number (namely the one given by the loop through the intervals with endpoint v). Thus it only remains to calculate the smallest possible rotation number; by standard arguments, this will be realized by a minimal loop (i.e. one which passes through each vertex at most once). The full Markov graph is too complicated to study in its entirety, so a sequence of simplifications is made. i) Every loop must contain < 0, s > for some s (i.e. {< 0, s >: 0 ≤ s ≤ q} is a rome [BGMY80] for the Markov graph): the structure of all loops is therefore given by considering only these intervals, and making a list of minimal paths between such intervals. Each such basic path has associated a rotation number (the number of occurences of < r, s > with r ≥ n − m divided by its length), and the rotation number of a loop made by concatenating basic paths is the Farey sum of the corresponding rotation numbers.
Because of the structure of π (the only transition from < r, s > is to < r + n m, s > unless r = 0, k i + n − m, or k i+1 + n − m), most of these paths correspond to passing either through T , or through S ∪ T , or through R ∪ S ∪ T : a short calculation (similar in spirit to the proof of Lemma 17) shows that the rotation numbers corresponding to these three types of path are u i /v i < u i+1 /v i+1 < m/n respectively. ii) There are basic paths from < 0, q > to < 0, s > for all s ∈ [0, q], each with rotation number m/n. Any loop passing through < 0, q > can be replaced by one with smaller rotation number, and < 0, q > can therefore be ignored. iii) There is a rotation loop which passes through each < 0, s > with 0 ≤ s < q exactly once, made of basic paths from < 0, s > to < 0, s − q p >, each of which has rotation number either u i /v i or u i+1 /v i+1 . Hence given any loop which uses a basic path with rotation number greater than u i+1 /v i+1 , another loop of smaller rotation number can be constructed by replacing this basic path with a segment of the rotation loop. Thus the loop with minimal rotation number cannot use basic paths with rotation numbers greater than u i+1 /v i+1 . iv) The only basic paths which now remain to be considered are the following: One can then argue that basic paths from < 0, p > to < 0, t > for t = 0, or from < 0, q − 1 > to < 0, t > for t = q − p − 1 could be replaced by compound paths with lower rotation number. Hence the rotation loop realizes the minimum rotation number. In the rotation loop, p of the basic paths have rotation number u i /v i , and the other q − p have rotation number u i+1 /v i+1 . Hence P i,p/q,m/n has rotation interval , m n = ξ ui/vi,ui+1/vi+1 (p/q), m n .
Since it has period n + v i p + v i+1 (q − p), the result follows by Lemma 12.
Hence T T (m/n, k i , B) consists of exactly one orbit with height r/s and decoration w m/n for each r/s ∈ (u i /v i , u i+1 /v i+1 ). Combining this with the results of Section 2.7, k T T (m/n, k, B) consists of one orbit with height r/s and decoration w m/n for each r/s ∈ (0, m/n) \ LFS(m/n). The 'missing' heights r/s ∈ LFS(m/n) \ {0} are supplied by orbits in k T T (m/n, k, A), as described by Theorem 48 below. The case γ = A is much easier than the case γ = B, since by Lemma 34 (and its proof), if P ∈ T T (m/n, k, A) has data d(P ) = ((N r ), π, (A, B, C)), then k > 0, N 0 = 2, and π(0, 0) = (k, 1): thus T T (m/n, k, A) is empty if k ∈ A m/n , and has at most one element if k ∈ A m/n . The details are left to the reader.

Stars and the full horseshoe
The aim of this section is to clarify the relationship between the thick tree maps F m/n : T n → T n and the full horseshoe F 1/2 : T 2 → T 2 . The strongest connection is provided by pruning theory. Each thick tree map F m/n can be obtained from the full horseshoe by pruning: that is, by performing an isotopy which destroys all of the dynamics of the horseshoe in an open subset U of D 2 (after the isotopy every point of U is wandering), while leaving the dynamics unchanged elsewhere (the isotopy is supported on U ). Although this process is conceptually valuable, it is not required in the main body of the paper: since it is rather complicated and assumes an understanding of the methods and results of [dC99,dCH01], the treatment given in Section 3.1 below is on an intuitive level.
The only aspect of the relationship between stars and the full horseshoe which was used in Section 2 is the fact that every * -orbit of f m/n has the same braid type as some horseshoe periodic orbit. A rather straightforward proof of this is given in Section 3.2: it has the additional advantage of providing, for each * -orbit P , the code of a horseshoe periodic orbit of the same braid type as P .
3.1. The pruning approach. As stated above, the approach taken throughout this subsection is intuitive: the interested reader is referred to [dCH01] for details of the constructions outlined.
The aim is to start with the full horseshoe map F 1/2 , to perform a sequence of isotopies which decrease the dynamics monotonically, remaining within the category of thick tree maps, and to arrive at a given thick tree map F m/n : T n → T n . Two distinct types of operation are used. The first redefines the thick tree structure (that is, the subset of D 2 which is regarded as the thick tree and the decomposition elements which give it its structure), but leaves the dynamics unchanged. The second is an isotopy which destroys the dynamics in some region which corresponds to an interval in the underlying tree endomorphism whose image backtracks.
Both of these operations have counterparts on the level of the underlying tree maps, and will be described on this level for the sake of both conceptual and diagrammatic simplicity. The important point is that the operations performed on the tree endomorphisms can be realised by isotopies of the corresponding homeomorphisms of the disk. Both the trees and their endomorphisms have additional structure due to the fact that they are induced by thick tree maps: in particular, the edges incident on a vertex have a cyclic order; and when several edge images backtrack over a common edge, there is a well-defined notion of the 'innermost' backtracking. This observation is, of course, reflected in the way that tree maps have been drawn throughout this paper.
Suppose that the image f (e r ) = . . . e s e s . . . of an edge e r contains an innermost backtracking over the edge e s . The following two operations can be performed: Glueing e r : Let I be the subinterval of e r whose image is e s e s . Identify those points of I which have the same image (so all points of I except the preimage of the initial point of e s are identified in pairs).
In the constructions described below, I always has the central vertex v of the star as an endpoint: glueing therefore preserves the star structure, but increases the valence of v by 1. It does not change the dynamics of f . Pulling tight e r : Delete the word e s e s from f (e r ). This decreases the dynamics of f , while leaving the tree unchanged.
A second family of endomorphisms g m/n of Γ n are needed for the construction: they differ from f m/n only in the image of the edge e n−1 .
As an example, g 4/11 is depicted in Fig. 12. These maps are endowed with additional '2-dimensional' structure as indicated in the figure. The aim, then, is to construct the entire family f m/n of star maps starting from f 1/2 by applying the operations of glueing and pulling tight. This can be accomplished by a combination of two compound procedures (together with the observation that one can pass from g m/n to f m/n by pulling tight e n−1 ).
Procedure L: starts with f m/n and yields g p/q , where p/q is the immediate left Farey child of m/n. Procedure R: starts with g m/n and yields g u/v , where u/v is the immediate right Farey child of m/n. To construct f m/n one navigates through the Farey graph from 1/2 to m/n, passing at each step from parent to immediate child: at each step to the left (respectively right) one applies Procedure L (respectively Procedure R). Thus, for example, to obtain f 3/10 from f 1/2 one applies Procedure L to obtain g 1/3 ; pulls tight to obtain f 1/3 ; applies Procedure L to obtain g 1/4 ; applies Procedure R to obtain g 2/7 ; applies Procedure R to obtain g 3/10 ; and pulls tight to obtain f 3/10 . Procedure L: Start with f m/n and glue e 0 (that is, identify pairs of points in e 0 which have the same image in e m ). This creates a new edge, which is labelled e n . Now the image of e n−m backtracks over e n ; glue e n−m . This creates another new edge e n+1 , and the image of e n−2m backtracks over it. Continue this procedure until edge e m−1 has been glued; each time an edge e j is glued with 1 ≤ j ≤ m − 1, pull tight the innermost backtracking of the image of e 0 over e j before proceeding. This yields g p/q , where p/q is the immediate left Farey child of m/n.
Applying Example 51. Let m/n = 3/7: thus procedure L gives a construction of g 5/12 from f 3/7 . The edges e 0 , e 4 , e 1 , e 5 , and e 2 are glued successively: the new edges thereby created are labelled e 7 , e 8 , e 9 , e 10 and e 11 respectively. Since m − 1 = 2, the only pulling tights occur after glueing e 1 and e 2 . The procedure is shown in Fig. 13.
Procedure R: is similar. Start with g m/n . Since g m/n (e n−1 ) backtracks over e m one can successively glue e n−1 , e n−m−1 , e n−2m−1 , . . . , e m , pulling tight e 0 each time an edge e j is glued with 1 ≤ j ≤ m − 1. This yields g u/v , where u/v is the immediate right Farey child of m/n.

3.2.
Horseshoe symbolics for * -orbits. In this section a more direct approach to the problem of showing that * -orbits have horseshoe braid type is outlined. It makes use of the notion of the line diagram of an isotopy class of homeomorphisms of the punctured disk. For each n ≥ 2, let D n be a standard model of the n-punctured disk in which the punctures (or marked points) are equally spaced along the horizontal diameter of the disk. The line diagram of a homeomorphism f : D n → D n is the sequence ([f (α 1 )], . . . , [f (α n−1 )]) of homotopy classes of the images of the horizontal arcs α i joining the i th to the (i + 1) th puncture. It is straightforward to show that two homeomorphisms f, g : D n → D n are isotopic if and only if they have the same line diagram.
If F : D 2 → D 2 is an orientation-preserving homeomorphism having a period n orbit P , then conjugating F so that the points of P coincide with the punctures of D n yields a homeomorphism of D n and thence a line diagram. Different conjugacies naturally give rise to different line diagrams, but periodic orbits P and Q of homeomorphisms F and G have the same braid type if and only if the conjugacies can be chosen so as to give the same line diagrams.  Fig. 14, which illustrates this for m/n = 2/5). Notice that if Γ n is drawn (as in this paper) so that e 0 and e n−m are horizontal, then α m/n passes along e 0 , then around each of the edges below the horizontal in the positive direction, then around each of the edges above the horizontal in the negative direction, and finally along e n−m .

PSfrag replacements
f 2/5 f 2/5 Figure 14. A path whose image under f 2/5 is a subhorseshoe It follows that if P is a * -orbit of f m/n , then P has horseshoe braid type provided that an arc α projecting to α m/n can be passed through the points of P in the thick tree T n in such a way that F m/n (α) projects to f m/n (α m/n ). Moreover, horseshoe symbolics for P can be obtained by coding with 0 those points of P which either lie in e 0 ∪ · · · ∪ e n−2m−1 , or lie in e n−2m and have α pass through them with the orientation of e n−2m (these are precisely the points whose images lie in the increasing segment of the unimodal line diagram); and coding with 1 the other points of P .
The only issue in constructing such an arc is to decide whether it should pass through each point of P with the orientation of e r , or with the orientation of e r . The following partition of L \ {(r, 0) : 0 ≤ r < n} gives the unique coherent way of doing this: points which α passes through with the orientation of e r lie in I.
The following theorem then follows from the discussion above.
Example 54. Let P ∈ P(2/5, 1, A) be the periodic orbit with data Hence P has the same braid type as the horseshoe orbit of code 10010110. Thus P has height 1/3 and decoration 11 = w 2/5 , as expected since P is the unique element of T T (2/5, 1, A) discussed in examples 26 and 49.
Notice that since the cycle notation of π always ends (m, 0) → (2m, 0) → · · · → (n − m, 0), every element of P(m/n) has the same braid type as a horseshoe orbit whose code ends w m/n 0.

Proof of Lemma 12
The following lemma summarizes the results of [Hal94] which will be used in the proof of Lemma 12. Part a) is theorem 3.10 of [Hal94], part b) is theorem 3.11, part c) is lemma 3.4 (in which the notation d r/s is used to mean 0w r/s ), and part d) is a combination of theorem 3.5 and lemma 3.6. The first part of the lemma gives an algorithm for computing the rotation interval of an arbitrary horeseshoe periodic orbit. Although it is complicated to state, it is much easier to explain intuitively. For each block of 0s in c P , calculate the heights of the sequences obtained by moving forwards and backwards through c P starting at the 1 immediately before the block of 0s: if the backward sequence starts 11, then first replace the second 1 with a 0. If the backward height is not less than the forward height, then the interval between the two is contained in the rotation interval. The union of all such intervals is the rotation interval.
Lemma 55. a) Let P be a horseshoe periodic orbit which contains the point of itinerary 0 κ1 1 µ1 0 κ2 1 µ2 . . . 0 κr 1 µr (written in such a way that κ i , µ i > 0 for all i). Then P has rotation interval (and [ξ i , η i ] = ∅ if η i < ξ i ). b) Let P be a horseshoe periodic orbit. Then the left hand endpoint of ρi(P ) is q(P ). c) Let 0 < r/s < 1/2. Then c ∈ {0, 1} N has height q(c) = r/s if and only if 10w r/s 1 c 10 w r/s 011 (where the inequalities are with respect to the unimodal order on {0, 1} N ). In particular, if q(c) = r/s then c = 10w r/s 0 1 1 . . . , and the first isolated 1 in c cannot appear before the s + 1 th symbol. d) If P is a period N horseshoe orbit which is not of finite order braid type and which has height q(P ) = u/v, then N ≥ v + 2. Moreover, if N = v + 2 then c P = c u/v 0 1 (and P has rotation interval [u/v, 1/2]).
Proof. If the two words didn't disagree, then it would follow that κ r + 1 = κ 1 and that κ m = κ m−r+1 , contradicting the fact that c m/n is palindromic.
Observe that formula (1) gives, for each s with 1 ≤ s ≤ m + 1 − r, Hence at the point where they first disagree c has a longer block of 0s than c m/n , and so is greater in the unimodal order. Proof. By induction on N , with the case N = 2 vacuous since the only period 2 horseshoe orbit has trivial rotation interval. The case m/n = 1/2 follows immediately from parts b) and d) of Lemma 55, so it will be assumed that m/n < 1/2. By parts b) and d) of Lemma 55, it then follows that N ≥ v+3: let k = N −v ≥ 3. By Theorem 3 a), the code of P is of the form c P = c u/v 0 1 w 0 1 , for some word w of length k − 3. The four cases c P = c u/v 0w0, c u/v 0w1, c u/v 1w0, and c u/v 1w1 need to be considered separately. Case a) Suppose that c P = c u/v 0w0 = 10 κ1 1 2 0 κ2 1 2 . . . 1 2 0 κu 10 λ1 1 ν1 0 λ2 1 ν2 . . . 1 νt−1 0 λt , where κ i = κ i (u/v) for 1 ≤ i ≤ u, and λ i and ν i are chosen to be positive for all i. Note that the initial word of c P up to 0 κu has length v, and the complementary word has length k. For 1 ≤ i ≤ u, let [ξ 1 i , η 1 i ] be the contribution to the rotation interval corresponding to the block 0 κi of 0s; and for 1 ≤ i ≤ t, let [ξ 2 i , η 2 i ] be the contribution corresponding to 0 λi . Thus Now for 2 ≤ i ≤ u, η 1 i = q(10 κi−1+1 1 2 0 κi−2 1 2 . . . 1 2 0 κ1 10 . . . ), which, by Lemmas 56 and 55 c) and the fact that c u/v is palindromic, is less than u/v. Hence, since ρi(P ) = [u/v, m/n], the interval [ξ 1 i , η 1 i ] must be empty. On the other hand, ξ 1 1 = u/v, and η 1 1 = q 10 λt 1 µt−1 . . . 1 µ1 0 λ1 10 . . . Let η 1 1 = r/s: then by Lemma 55 c), k + 1 ≥ s + 1, or k ≥ s. It follows that u i=1 ξ 1 i , η 1 i is equal either to {u/v}, or to [u/v, r/s] for some r/s with s ≤ k = N − v.