Reducible braids and Garside theory

arXiv:1008.0238v1 [math.GT] 2 Aug 2010 Reducible braids and Garside theory Juan Gonz´alez-Meneses∗Bert Wiest August 2, 2010 Abstract We show that reducible braids which are, in a Garside-theoretical sense, as simple as possible within their conjugacy class, are also as simple as possible in a geometric sense. More precisely, if a braid belongs to a certain subset of its conjugacy class which we call the stabilized set of sliding circuits, and if it is reducible, then its reducibility is geometrically obvious: it has a round or almost round reducing curve. Moreover, for any given braid, an element of its stabilized set of sliding circuits can be found using the well-known cyclic sliding operation. This leads to a polynomial time algorithm for deciding the NielsenThurston type of any braid, modulo one well-known conjecture on the speed of convergence of the cyclic sliding operation. 1 Introduction There are currently two known approaches to the problem of determining algorithmically the Nielsen-Thurston type of a given braid, i.e. deciding whether it is reducible, periodic, or pseudoAnosov [12, 7, 11]. Since periodicity of braids is fast and easy to detect [19], the main difficulty is to determine whether a given braid is reducible. One approach is due to Bestvina and Handel [2], and uses the theory of train tracks (see also [22]). The algorithmic complexity of the Bestvina-Handel algorithm is still mysterious – this is particularly regrettable since it seems to be fast in practice, at least generically. The second approach, which was initiated by Benardete, Guti´errez and Nitecki [1], and developed by Lee and Lee [20], uses the Garside structure, as exposed in [9], on the braid group. Indeed, it is shown in [1] that round reduction curves are preserved by cycling and decycling. As a consequence, if a given braid x∈Bnis reducible, then there is at least one element of its super summit set [9] which has a round reduction curve, and whose reducibility is thus easy to to detect. The drawback of this approach is that the algorithm has to compute the complete super summit set of x, and this is is very slow [15]. In order to have any hope of obtaining a polynomial time algorithm from the second approach, we would need to replace the super summit set of xwith another set satisfying the following properties: (1) It is an invariant of the conjugacy class of x, (2) an element in this subset can be computed efficiently, and (3) for every element in this subset, the reducibility or irreducibility can be detected rapidly. Super summit sets satisfy the first two properties, but not the third. In the special case of the four-strand braid group, the super summit set can actually do the job [6]. In the general case of the braid group Bn(with n∈N), the ultra summit set defined in [15] can do ∗Partially supported under Australian Research Council’s Discovery Projects funding scheme (project number DP1094072), the Spansih Projects MTM2007-66929, P09-FQM-5112 and FEDER. 1 the job, but only under certain conditions. It is shown in [20] that if a braid is reducible and the external component is simpler (from the Garside theoretical point of view) than the whole braid, then one can rapidly detect reducibility of any given element in its ultra summit set, as every element in this set has a round reduction curve. Hence, under this hypothesis, the ultra summit set satisfies (1) and (3) above. It is a well-known conjecture [3] that it also satisfies (2). The aim of the present paper is to construct a subset of any conjugacy class which satisfies (1) and (3) above, and is conjectured to also satisfy (2), just like Lee and Lee’s subset [20], but without their technical hypothesis. In particular, we prove the existence of a polynomial time algorithm for deciding the reducibility or irreducibility of a given braid, modulo a well-known conjecture (Conjecture 3.5), again concerning (2) above, which we leave open. Where Benardete, Guti´errez and Nitecki talk about round curves, we have to admit a somewhat larger family of reducing curves which we call almost round curves. Also, the subset of the conjugacy class for which our result holds is neither the super summit set nor the ultra summit set, but a slightly more complicated class, which we call the mtimes stabilised set of sliding circuits, denoted SC[m](x), where mis a positive integer. We will show that one can conjugate a given element xof Bnto an element in SC[m](x), by applying iteratively a special kind of conjugation called cyclic sliding. This iterated cyclic sliding procedure is a Garside-theoretic tool which simplifies (from an algebraic point of view) the braid within its conjugacy class, and which has already been used to solve the conjugacy problem in braid groups and Garside groups [16, 17]. Further, we will show the following result (where ∆ denotes the half twist of all strands, so that ||∆|| =n(n−1)/2): Theorem 3.4 Let x∈Bnbe a non-periodic, reducible braid. There is some m⩽||∆||3− ||∆||2 such that every element y∈SC[m](x)admits an essential reduction curve which is either round or almost round. Theorem 3.4 is telling us that cyclic sliding not only simplifies braids from the algebraic, but also from the geometric point of view, since the reduction curves, which can be terribly tangled in x, become either round or almost round after iterative applications of cyclic slidings. Moreover, we prove that it can be efficiently checked whether there are round or almost round curves which are preserved by a braid ylike in the statement of Theorem 3.4. More precisely, invariant round curves can be efficiently detected by [1]. For almost round curves the situation is not the same: as the number of such curves grows exponentially with respect to the number of strands, it is not a good idea to try to check them one by one. To bypass this difficulty, we show the following particular case: Theorem 2.9 There is an algorithm which decides whether a given positive braid xof length ℓ with nstrands preserves an almost-round curve whose interior strands do not cross. Moreover, this algorithm takes time O(ℓ·n4). Notice that Theorem 2.9 cannot immediately be applied to detect the reduction curves promised by Theorem 3.4, for two reasons: firstly, none of these curves are necessarily x-invariant (they may be permuted by x), and secondly, even if they were, there would be no guarantee that their interior strands do not cross. Moreover, xis not necessarily positive (although this can be easily achieved just by multiplying xby a suitable power of ∆2). There is, however, a situation which can be reduced to the cases that can be checked using Theorem 2.9. This is the situation where the given braid is rigid [3]. Theorem 5.16. Let β∈Bnbe a non-periodic, reducible braid which is rigid. Then there is some positive integer k⩽nsuch that one of the following conditions holds: 2 1. βkpreserves a round essential curve, or 2. inf(βk)and sup(βk)are even, and either ∆−inf(βk)βkor β−k∆sup(βk)is a positive braid which preserves an almost round essential reduction curve whose corresponding interior strands do not cross. In particular, some essential reduction curve for βis either round or almost round. The power k⩽nin the above statement is needed to pass from invariant families of curves to invariant curves, which is what is detected in Theorem 2.9, and also to assure that inf(βk) and sup(βk) are even. We then see that if the braid βunder study is rigid and admits essential reduction curves, we can find them in one of the following two ways: If one these curves is round, we can apply the well known algorithm in [4]. Otherwise, we will find them by applying Theorem 2.9 to ∆−inf(βk)βk(where inf(βk) is even) and to β−k∆sup(βk)(where sup(βk) is even) for k= 1,...,n/2, as these braids have the same essential reduction curves as β. The next aim is to construct, for any given y∈SC[N](x), a rigid braid whose reducing curves are also reducing curves of y. This serves two purposes at once: it allows us to use Theorem 2.9 to search for reducing curves in polynomial time, and it also gives the key to proving Theorem 3.4. In order to do so, we will, for every braid y∈SC[N](x), define its preferred conjugator P(y), which commutes with y. We will prove: Lemma 5.15. Let x∈Bnbe a non-periodic, reducible braid. Let N=||∆||3− ||∆||2. For every element y∈SC[N](x)there is some m⩽Nsuch that either ymis rigid, or P(ym)is rigid, admits essential reduction curves, and all its essential reduction curves are essential reduction curves of y. From the above results, we obtain the following algorithm to determine whether a given element of Bnis periodic, reducible or pseudo-Anosov: Algorithm 1. To determine the geometric type of a braid. Input: x∈Bn. 1. If xn−1or xnis a power of ∆, return ‘xis periodic’ and stop. 2. Compute an element y∈SC[N], where N=||∆||3− ||∆||2. 3. If ypreserves a family of round curves, return ‘xis reducible, non-periodic’ and stop. 4. For m= 1,...,N do the following: If either ymis rigid or P(ym) is rigid, apply the algorithm in Theorem 2.9 to the braids mentioned in Theorem 5.16(2), with β=ymor β=P(ym), respectively. If an almost round reduction curve is found, return ‘xis reducible, non-periodic’ and stop. 5. Return ‘xis pseudo-Anosov’. The computational complexity of each step of this algorithm is bounded by a polynomial in the length and the number of strands of x, with one exception: the second step of this algorithm (conjugating xto y∈SC[N](x)) is not currently known to be doable in polynomial time, but it is conjectured to be so (c.f. Conjecture 3.5). The plan of the paper is as follows. In Section 2 we introduce the basic notions of reducible braids and reduction curves, including the proof of Theorem 2.9, and of Theorem 3.4 in the case where the interior braid is trivial. In Section 3 we switch to the algebraic viewpoint, explaining the notion of cyclic sliding and sliding circuits, and introducing the set SC[m](x). Exploring the relation between sliding circuits and the powers of a braid, in Section 4, we show how to compute one element in SC[m](x) for every xand m. We then proceed to study, in Section 5, the relation between the reduction curves, on the geometric side, and the sets of sliding circuits, on 3 the algebraic side. At the end of this section, we show that Theorem 3.4 holds in general if it holds for the special case of rigid braids. Section 6 treats the case of reducible rigid braids, finishing the proof of Theorem 3.4 by showing that if a rigid, reducible braid has some interior braid which is pseudo-Anosov, then its corresponding reduction curve is round. Acknowledgements: We wish to thank Volker Gebhardt for many useful discussions on this and related problems. 2 Round and almost round reduction curves 2.1 Definitions and notations 2.1.1 Canonical reduction system and complexity of curves Let Bnbe the braid group on nstrands, where we fix as base points the set Pn={1,...,n} ∈ C. Every element x∈Bncan be seen as an automorphism of Dn=D2\Pn, where D2denotes the disk in Cwith diameter [0, n + 1]. Therefore xinduces an action on the isotopy classes of 1-manifolds in Dn. We will consider the action of braids on isotopy classes of simple curves from the right. That is, we will denote the isotopy class of a simple curve Cby [C], and we will write [C]x, meaning the isotopy class of the curve obtained from Cafter applying xconsidered as an automorphism of the n-times punctured disk. By abuse of vocabulary, we shall often say “curves” when we really mean “isotopy classes of curves”. However, we shall carefully distinguish the notations Cand [C]. A simple closed curve Cin D2\Pnis said to be non-degenerate if it encloses more than one and less than npoints of Pn, and it is said to be round if it is homotopic to a geometric circle. It is clear that non-degeneracy and roundness are properties which depend only on the isotopy class of a curve, so we can naturally say that some isotopy class [C] is non-degenerate, or is round. A braid x∈Bnis said to be reducible if [C](xm)= [C], for some positive integer mand some non-degenerate curve C. Such a curve Cis said to be a reduction curve for x. We say that a reduction curve C is essential if every other reduction curve for xcan be isotoped to have empty intersection with C[5]. The set of isotopy classes of essential reduction curves of a braid xis called the canonical reduction system of x, and is denoted CRS(x). It is well known that CRS(x) = ∅if and only if xis either periodic or pseudo-Anosov [5]. In other words, CRS(x)6=∅if and only if xis reducible and nonperiodic. Since it is very easy to determine whether a given braid x∈Bnis periodic (it suffices to check if either xn−1or xnis equal to a power of the half twist ∆), the question of determining the geometric type of a braid reduces to the study of its canonical reduction system. We will then be interested in reducible, non-periodic braids, and in their essential reduction curves. We will say that a non-degenerate simple curve Cin D2\Pnis almost round if there exists a simple element s(a permutation braid) such that [C]sis round. This is equivalent to saying that Ccan be isotoped in D2\Pnto a curve whose projection to the real line has exactly one local maximum and one local minimum. There is an alternative characterization of almost round curves which will also allow us to introduce a notion of complexity of a simple closed curve in the punctured disc. Notice that a curve [C] can always be transformed into a round curve by a suitable automorphism of the punctured disc, that is, by a suitable braid y. Since the full twist ∆2preserves any given curve, it follows that ∆2kβalso transforms [C] into a round curve, for every integer k. Hence we can assume that yis a positive braid, as every braid becomes positive after multiplication by a sufficiently high power of ∆2. It 4 is shown in [20] that given a family Fof mutually disjoint simple closed curves in D2\Pn, there is a unique positive braid y∈Bnsuch that [F]yis a family of round curves, and such that y has minimal length among all positive braids satisfying this property (actually yis a prefix of any other positive braid satisfying this property). This braid yis called the minimal standardizer of F. If Fconsists of a single curve C, we will call ythe minimal standardizer of C. Now recall that the simple braids (or permutation braids) are those positive braids for which every pair of strands cross at most once, and that ℓ(x), the canonical length of a braid x, is the minimal number of simple factors into which xcan be decomposed, not counting factors equal to the half twist ∆ – see also Section 3. Alternatively, the canonical length ℓ(x) is the number of factors different from ∆ in the left normal form of x. Definition 2.1. Given a simple closed curve Cin the punctured disc, we define the complexity of Cto be the canonical length of the minimal standardizer of C. In other words, the complexity of Cis the smallest possible canonical length of a positive braid sending [C] to a round curve. Notice that this definition could be equivalently expressed the other way around: the complexity of Cis the smallest possible canonical length of a positive braid sending a round curve to [C]. The curves of complexity 0 are the round curves, and the curves of complexity 1 are those which become round by the action of a simple element: these are precisely the almost round, not round curves. 2.1.2 Decomposition of a braid along a family of curves Reduction curves allow us to decompose a braid into simpler braids. In fact, several procedures for specifying such a decomposition are conceivable, but we shall use the procedure given in [18], which we briefly explain now. Let x∈Bn, and let Fbe a family of disjoint simple closed curves in D2\Pn. Let ybe the minimal standardizer of F, and let bx=y−1xy =: xyand b F=Fy. Notice that if xpreserves [F], then bx preserves [ b F] = [F]y, which is a family of round curves. However, even if xdoes not preserve [F], it can still happen that bxsends [ b F] = [F]yto a family of round curves (not necessarily [ b F] itself). In this case we can define for every curve C ∈ F ∪ {∂(D2)}, a braid β[C∈F], called the component of xassociated to Cin F, as follows. For every subset I⊂ {1, . . . n}, we can define the subbraid (bx)Ito be the braid on #(I) strands obtained from bxby keeping only those strands which start at I. Notice that this yields a welldefined element of B#(I), even if the strands starting at Ido not end at I– we just require the strands of (bx)Ito cross in the same way as the strands in bxstarting at I, for details see [18]. Now given a curve C ∈ F ∪ {∂(D2)}, let XCbe the only connected component of D2\F which is enclosed by C, and such that C ⊂ XC. Then define DC=XC∪ C, which is homeomorphic to a punctured disc. Notice that DC\DCis a family of points and curves, namely the outermost curves enclosed by C, and the points which are enclosed by Cbut not enclosed by the mentioned curves. Similarly, we let Xb Cbe the only connected component of D2\b Fwhich is enclosed by b C, and such that b C ⊂ Xb C. Then define Db C=Xb C∪b C. This is a closed round disk with some points and some closed round disks removed from its interior. Also, Db C\Db Cis a family of points and round curves. Definition 2.2. [18] Let x∈Bnand let Fbe a family of disjoint simple closed curves in D2\Pn, whose minimal standardizer is y. Let bx=y−1xy, and suppose that bxsends [b F] = [F]yto a family of round curves. Let C ∈ F ∪ {∂(D2)}. Let I⊂ {1,...,n}consist of the indices of 5 •those punctures that appear in Db C\Db C, and •for each curve in Db C\Db C, exactly one puncture chosen arbitrarily among the punctures enclosed by that curve. Then we define x[C∈F], the component of xassociated to Cin F, as the subbraid (bx)I. If F= CRS(x), the mentioned component is just denoted xC. We remark that x∂(D2)is usually called the external braid associated to x, and is denoted xext. 2.2 Canonical reduction curves of reducible, positive braids with trivial interior braids are either round or almost round The aim of this section is to prove the following result: Proposition 2.3. If Cis an essential reduction curve for a positive braid x, with [C]x= [C], and the strands of xenclosed by Cdo not cross each other, then Cis either round or almost round. In order to show this result, it suffices to prove that such a curve Ccannot be of complexity two, i.e., it cannot be the result of a round curve after the action of a braid of canonical length two, without being round or almost round. Our first aim is to understand what a curve of complexity two looks like (for detailed discussion of more general questions see [24]). We shall first study smooth arcs α:I→D2in the disk D2 defined on the unit interval I= [0,1]; we shall restrict our attention to smooth arcs αwhich start and end in puncture points, which may also traverse some puncture points, but whose tangent direction is horizontal and pointing to the right, at every puncture point. For brevity, we shall call them arcs traversing some puncture points horizontally. When studying diffeotopy classes of such arcs, we shall always mean diffeotopies through families of arcs which are all supposed to traverse the puncture points horizontally. We shall say that a simple closed curve or an arc traversing some puncture points horizontally is reduced if it has the minimal possible number of intersections with the horizontal line, and also the minimal possible number of vertical tangencies in its diffeotopy class. The action of the braid group on the set of diffeotopy classes of arcs traversing some puncture points horizontally, specifically of a braid xon an arc α, is defined as follows: xinduces a puncture dance, which in turn can be extended to a diffeotopy of αin such a way that at every moment the intersection of the arc with the punctures is horizontal. At the end of the dance we obtain a new arc traversing some puncture points horizontally, which is well-defined up to diffeotopy. This is αx. For an arc αtraversing some puncture points horizontally, we define the tangent direction function tα:I→R/2Zas the angle of the tangent direction of αagainst the horizontal, divided by −π. In particular, if the arc goes straight to the right in α(t), then tα(t) = 0 + 2Z, if it goes straight down then tα(t) = 1 2+ 2Z, and if it goes to the left then tα(t) = 1 + 2Z. For every arc traversing some puncture points horizontally, we have a unique lifting of the function tαto a function e tα:I→Rwith e tα(0) = 0. Finally, if r:R→Zdenotes the rounding function, which sends every real number to the nearest integer (rounding down n+1 2), then we define the function τα:I→Z, t 7→ r◦e tα(t) which one might call the rounded lifted tangent direction function. 6 Notice that, if αis an arc such that ταtakes the value 0 in a neighbourhood of the points where the arc traverses a puncture, then the same is true for its image αxunder the action of any braid. In order to be able to characterize reduction curves of complexity zero, one, and two, we give now a detailed description of the puncture dance associated to a positive permutation braid. In a first step, the punctures make a small vertical movement, with the puncture in position k∈Z moving to position k−k·ǫ·i∈C, for some small ǫ > 0. In a second step, the punctures make a horizontal movement, permuting their R-coordinates. In a third step, the punctures make again a small vertical movement, lining them back up on the real line. Now, reduction curves Cof complexity zero can be characterized as curves enclosing an arc which lies entirely in the real line, and which traverses all the punctures in the interior of C. Notice that Ccan be seen as the boundary of a regular neighborhood of this arc. Suppose now that a curve Chas complexity one. Then it is obtained from a round curve C0by the action of a simple braid s. We can assume that the punctures enclosed by C0(which are consecutive) do not cross in s, as those crossings could be removed from swithout modifying its action on C0. Hence, from the above description of positive permutation braids, we see that reduction curves Cof complexity one can be characterized as follows: there exists a smooth arc α disjoint from C, traversing all the punctures in the interior component of D2\C horizontally such that ταis the constant function 0. (We are going to say such an arc is almost horizontal.) The action by a positive permutation braid transforms an arc αwith τα≡0 into an arc α′which, after reduction, has the following property: by an isotopy of D2that moves the npuncture points only in the vertical direction up or down, α′can be transformed into an arc whose imaginary coordinate is monotonically decreasing. Therefore, reduction curves Cof complexity two can be characterized as follows: there exists a smooth arc α′disjoint from Cbut traversing horizontally all the punctures in the interior component of D2\C, such that τα′only takes the values 0 and 1 (for a more detailed proof see [24]). One important property is that if a braid xpreserves a curve Cof complexity 2, and the strands inside Cdo not cross in x, then the mentioned arc is invariant by x: Lemma 2.4. Let x∈Bnand let Cbe a curve such that [C]x= [C]. Suppose that the strands enclosed by Cdo not cross in x. Let αby an arc traversing horizontally some punctures enclosed by C. Then αx=α. Proof. Let C0be a round curve and let y∈Bnbe such that [C]y= [C0]. Consider the braid z=y−1xy, and the arc αy. Notice that [C0]z= [C0]y−1xy = [C]xy = [C]y= [C0]. Hence z preserves the round curve C0. Moreover, as the punctures enclosed by Cdo not cross in y, we can find a representative of zin which the punctures enclosed by C0do not cross. This implies that zcan be represented by a homeomorphism of the punctured disc whose restriction to the component enclosed by C0is trivial. As αyis a curve enclosed by C0, one has (αy)z=αyand then αx= (αyz)y−1= (αy)y−1=α, as we wanted to show. We saw above that a curve Cof complexity 2 admit a smooth arc α′disjoint from Cbut traversing horizontally all the punctures in the interior component of D2\C, such that τα′only takes the values 0 and 1. If xis a braid preserving Cin which the strands enclosed by Cdo not cross, the above lemma shows that the smooth arc α′is preserved by x. We shall call such an arc a descending invariant arc. Notice that Cis the boundary of a regular neighborhood of α′. Lemma 2.5. If xis a positive braid, if αis an arc traversing horizontally some puncture points, and if αxis its reduced image under the action of x, then max t∈Iταx(t)⩾max t∈Iτα(t)and min t∈Iταx(t)⩾min t∈Iτα(t) 7 Proof. It suffices to prove this result for x=σi, a single Artin generator. It is an easy observation that for every t0in I, we have tασi(t0) = tα(t0) or tασi(t0) = tα(t0) + 1. Some examples are given in Figure 1. 0 2 3 33 3 3 43 0 1 0 −1 0 1 1 0 0 11 σiσiσi σiσiσi Figure 1: The labels, which represent the values of the function tα, can grow under the action by a generator σi, but never go down. Lemma 2.6. If [C]is an x-invariant closed curve of complexity two, where xis a positive braid, and the strands of xenclosed by Cdo not cross, then for any prefix x′of xthe curve [C]x′is of complexity two. Proof. Let αbe a descending invariant arc associated to C. By Lemma 2.4 we know that αx=α. Now, the image of ταis equal to {0,1}, so the same holds for the image of ταx. Thus Lemma 2.5 implies that for any prefix x′of xone has 1 = max t∈Iταx(t)⩾max t∈Iταx′(t)⩾max t∈Iτα(t) = 1 and 0 = min t∈Iταx(t)⩾min t∈Iταx′(t)⩾min t∈Iτα(t) = 0. Hence the image of ταx′is also equal to {0,1}. Therefore [C]x′has complexity two. Let us introduce some more notation. We shall suppose that αis a descending invariant arc of some positive braid x. We suppose also that α′⊂αis a sub-arc whose two extremities lie in two interior punctures. We say an exterior puncture is left-blocked by α′if there is no smooth path starting at this puncture point, terminating on the boundary of the disk, disjoint from the arc α′, and whose tangent direction has always a negative real coordinate. A right-blocked puncture is defined symmetrically. We define interior punctures to be both left and right blocked. We shall call the two interior punctures at the two ends of the arc α′the extremal (interior) punctures of α′. The proof of Proposition 2.3 will be completed by proving that there are no blocked exterior punctures at all, meaning that the curve Cis of complexity 1. First we obtain two partial results: Lemma 2.7. Let Cbe an essential reduction curve for a positive braid x. Suppose that α′is a sub-arc of a descending invariant arc of x. Then there cannot be any exterior punctures which are left-blocked by α′and to the left of both extremal punctures of α′. Similarly, there cannot be a right-blocked exterior puncture to the right of both extremal punctures. Proof. We shall prove the first sentence, the proof of the second one is very similar. Moreover, we shall suppose that the starting point of the arc α′(which in the picture is “higher” than the end point) is to the left of the terminal point, see Figure 2(a). The proof of the other case (where the starting point of the arc α′is to the right of the end point, Figure 2(b)) is similar, one simply has to consider the positive braid rev(x), which is the image of xunder the anti-isomorphism rev : Bn→Bnwhich sends σito itself for every i= 1,...,n−1 (that is, rev(x) is equal to x written backwards). We shall argue by contradiction: let us suppose that there is some left-blocked puncture which is to the left of the left extremal interior puncture (see Figure 2(a)). We observe that the corresponding 8 strands cannot cross in the braid x– indeed, if we think of the braid xas a dance of the punctures, then during this dance the left-blocked puncture cannot move under the left extremal interior puncture, for this would require a negative crossing, and it cannot move over it, for this would turn the curve α′into a curve α′′ which possesses some points where the function tα′′ takes the value 2. Thus the set of punctures which are left-blocked by α′and which lie to the left of both endpoints of α′is stable during the whole dance. 01 1 0 0 1 right extremal puncture of α′ left of both endpoints of α′ (a) α′ α not left-blocked by α′ (b) α α′ right-blocked puncture to the right of both extremal punctures of α′ left-blocked puncture to the Figure 2: (a) The starting point of α′(the bold line segment) is to the left of the end point. (b) Vice versa. Now the vertical line through the left extremal interior puncture, together with the arc α′, cuts the disk into a number of connected components, at least one of which contains some left-blocked punctures to the left of the left extremal puncture. Let Ξ be the union of all the components containing left-blocked punctures. Let Ψ be the union of Ξ with an initial segment of α′long enough to touch all the connected components of Ξ, but not all of α′. (So Ψ looks in general like some pearls on a thread, see Figure 3(a).) Let N(Ψ) be a regular neighbourhood of Ψ. We observe that N(Ψ) is preserved by the action of x, and so is its boundary, which we shall call C′. Moreover, C′intersects the canonical reduction curve C(which, we recall, was the boundary of a regular neighbourhood of α) twice. This contradicts the definition of a canonical reduction curve. (a)(a) (b) α′ α′ Figure 3: Constructing invariant curves which intersect the curve c: (a) In the case where there is a left blocked puncture to the left of both extremal punctures, and (b) in the other case. Lemma 2.8. Let Cbe an essential reduction curve for a positive braid x. Suppose that α′is a sub-arc of a descending invariant arc αof x. Also suppose that α′does not traverse any interior punctures (except its two endpoints). Then there cannot be any exterior punctures blocked by α′. Proof. Again, we shall assume that the starting point of α′is to the left of the end point, with the other case being similar. Lemma 2.7 together with the hypothesis that α′does not traverse any interior puncture imply that any blocked punctures would have to lie between the left and the right extremity of α′. Supposing, for a contradiction, that such blocked punctures exist, then there must be a pair of them, with a right-blocked puncture above a left-blocked one (see Figure 3(b)). Let us now look at the braid x, considered as a dance of the punctures. 9 Corollary 4.5. Given x∈Bnwritten as a product of ℓsimple elements and its inverses, and given m > 0, there is an algorithm that computes an element in SC[m](x)in time O(Sℓn log n), where S= m X i=1 i Tn,iℓ. Proof. The algorithm computes P(xi [i−1]) and conjugates x[i−1] by this element (obtaining x[i]), for i= 1,...,m. We start with xwritten as a product of ℓsimple elements and its inverses, and compute its left normal form, which takes time O(ℓ2nlog n) [10]. Now we apply iterated cyclic sliding to x until the first repetition, which is x[1]. At each step, we have to compute the preferred prefix of an element α, and conjugate αby it. Notice that a preferred prefix is the greatest common divisor of two permutation braids: if α= ∆pα1···αris in left normal form and r > 0, then p(α) = τ−p(α1)∧∂(αr). If the left normal form of αis known, the computation of τ−p(α1) and ∂(αr) takes time O(n) [10], and computing their gcd takes time O(nlog n) [10]. Now α is an iterated cyclic sliding of x, where cyclic sliding never increases the canonical length of an element [16]. Hence the canonical length of αis at most ℓ. The algorithm takes αin left normal form, and computes the left normal form of its conjugate by p(α). As p(α) is a simple element, and αhas canonical length at most ℓ, this last step takes time O(ℓn log n) [10]. Thus computing p(α), conjugating αby it, and calculating the left normal form of the result takes time O(ℓn log n). This is repeated Tn,ℓ times, so x[1] is computed in time O(Tn,ℓ ℓn log n). In the following steps of the algorithm, one has x[i−1] and xi−1 [i−1] written in left normal form (the case of the previous paragraph is i= 1). Notice that the canonical length of xi−1 [i−1] is at most (i−1)ℓ. The algorithm then computes the left normal form of xi [i−1]. This computation, obtained from the product of the left normal forms of x[i−1] and xi−1 [i−1], takes time O((i−1)ℓ2nlog n). Now the algorithm computes iterated cyclic slidings of xi [i−1] until the first repetition. More precisely, the algorithm starts with α=x[i−1], and at each step it computes the preferred prefix p(αi), and conjugates both αand αiby this prefix. The conjugate of αis set as the new value of α, and the loop is repeated. The loop ends at the first repetition of αi. The complexity of this computation is the same as that of the previous paragraph, but applied to a braid of canonical length iℓ, instead of ℓ. Hence, the computation of x[i]and xi [i]from x[i−1] and xi−1 [i−1] takes time O(Tn,iℓ iℓn log n). Adding up the complexities of each loop, we obtain that the whole algorithm takes time O(ℓ2nlog n) + O(Sℓn log n). As ℓ < Tn,ℓ ⩽S, the result follows. We remark that if Conjecture 3.5 holds, that is, if Tn,ℓ is a polynomial in nand ℓ, then the complexity of the algorithm in Corollary 4.5 is polynomial in n,ℓand m. As we shall only need to compute one element in SC[m](x) for m⩽||∆||3=n3(n−1)3/8 (see Theorem 3.4), the complexity in this case will be polynomial in nand ℓ, always provided Conjecture 3.5 holds. 5 Sliding circuits and reduction curves 5.1 Sliding circuits and round curves In this section we shall investigate the properties of the elements belonging to SC[m](x), with respect to their canonical reduction systems. The simplest case occurs when this reduction system is made of round curves. The following result assures the existence of these examples Theorem 5.1. [1] (see also [20]) Let x∈Bnbe a positive braid whose left normal form is x1···xr. If [C]is a round curve such that [C]xis also round, then [C]x1···xiis round for i= 1,...,r. 16 In other words, if the roundness of a curve is preserved by a braid x, then it is preserved by each factor in the left normal form of x. Since ∆±1preserves the roundness of every curve, the above result can be applied to every braid, not necessarily positive. This is used in [1] to show that, if a braid preserves a round curve, its cycling and its decycling also preserve round curves. This immediately implies that for every reducible braid x, there is some element in its super summit set SSS(x) which preserves a round curve [1]. Clearly, one can replace SSS(x) by USS(x) in the previous statement. Even better, one can replace it by SC(x), as we will now see, but the proof of this fact is slightly different: we need to show the following result, concerning invariant families of round curves. Proposition 5.2. Let x∈Bn, and let Fbe a family round curves such that [F]x= [F]. Then [F]p(x)is also a family of round curves. Hence, if xpreserves a family of round curves, then so does s(x). Proof. We can assume r > 0. Let ∆px1···xrbe the left normal form of x. By Theorem 5.1 applied to each particular curve of F, one has that [F]∆px1is a family of round curves, and since ∆px1=τ−p(x1)∆p, it follows that the curves of [F]τ−p(x1)are round. Let F2be a family of curves such that [F2] = [F]τ−p(x1). In the same way, Theorem 5.1 tells us that the curves of [F]∆px1···xr−1 are round. Let F1be such that [F1] = [F]∆px1···xr−1. Notice that [F1]xr= [F](∆px1···xr−1)xr= [F]x= [F]. We then have [F1]xrτ−p(x1)= [F2], where F1and F2are families of round curves. Now, by definition, the left normal form of xrτ−p(x1) is equal to y1y2, where y1=xrp(x). By Theorem 5.1 again, we obtain that the curves of [F1]y1are round. But [F1]y1= [F1]xrp(x)= [F]p(x), hence [F]p(x)is a family of round curves, as we wanted to show. Corollary 5.3. For every reducible braid x∈Bnand every m > 0, there is some y∈SC[m](x) such that CRS(y)consists of round curves. Moreover, all elements in the sliding circuit of y satisfy the same property. Proof. The canonical reduction system CRS(x) is a family of disjoint simple curves on the punctured disc. Hence some orientable automorphism of the punctured disc relative to the boundary, will send it to a collection of (possibly nested) round curves. This automorphism corresponds to a braid γ∈Bn. In other words, there is some γ∈Bnsuch that [CRS(x)]γconsists of round curves. It is well known that [CRS(x)]γ= [CRS(xγ)], hence z=xγis a conjugate of xwhose canonical reduction system consists of round curves. Now recall that z[m], which is the conjugate of zby P(z)P((z[1])2)P((z[2])3)···P((z[m−1])m), belongs to SC[m](z) = SC[m](x). We will show that all the curves in CRS(z[m]) are round circles by induction on m. We know that this is true for m= 0 since z[0] =z, so we assume CRS(z[m−1]) consists of round curves for some m > 0. In order to compute z[m], we conjugate z[m−1] by P((z[m−1])m). Recall that the canonical reduction system of an element coincides with the canonical reduction system of each nonzero power, hence CRS((z[m−1])m) consists of round curves. Applying iterated cyclic sliding to (z[m−1])muntil the first repetition, that is, conjugating it by P((z[m−1])m), one obtains (z[m])m. By Proposition 5.2, all curves in CRS((z[m−1])m) keep their roundness after each application of s. Hence all curves in CRS((z[m])m) = CRS(z[m]) are round, as we wanted to show. We have then shown that there is some y∈SC[m](x) all of whose reduction curves are round. By Proposition 5.2 again, the same happens for every element obtained by applying iterated cyclic sliding to y, that is, for every element in the sliding circuit of y. Notice that the above proof does not provide an algorithm to find y, since we do not know a 17 priori which is the braid γthat conjugates xto z. Nevertheless, since SC[m](x) is a finite set, one can compute the whole SC[m](x) and check for each element whether it preserves some family of round curves. In this way one can find a reduction curve for y, and then for x. The computation of the whole set SC[m](x), starting from a single element, parallels the usual constructions given in [9, 3, 16], so we will skip it here. For our purposes, it suffices to know that there is one element yin SC[m](x) all of whose essential curves are round. Such elements have a particularly nice behavior with respect to normal forms, as it is shown in [20] and [18]. Lemma 5.4. (see for instance [20]) Let y∈Bn, and let Fbe a family of round curves such that Fyis also round. Suppose that yis a positive braid, and let y1···yrbe its left normal form, where some of the initial factors may be equal to ∆. Let C ∈ F ∪ ∂(D). For i= 1,...,r, denote [Ci] = [C]y1···yi−1and [Fi] = [F]y1···yi−1. Then the left normal form of y[C∈F ]is precisely y1[C1∈F1]y2[C2∈F2]···yr[Cr∈Fr]. In this normal form, some of the initial factors could be half twists, and some of the final factors could be trivial. Lemma 5.5. Let x, y ∈Bnbe braids, let Fbe a family of round curves, and let [C]∈[F]∪∂(D). Suppose that Fxand Fyare round. Then Fx∧yis also round, and (x∧y)[C∈F ]=x[C∈F]∧y[C∈F ]. Proof. The first sentence is shown be Lee and Lee [20], and the second one in [18]. Lemma 5.6. [18] Let y∈Bn, and let Fbe a family of round curves such that Fyis also round. Let C ∈ F ∪ ∂(D). Then ι(y)preserves the roundness of [F], and ι(y)[C∈F]is either a half twist or equal to ι(y[C∈F ]). Proposition 5.7. [18] Let y∈Bn, and let Fbe a family of round curves such that [F]y= [F]. Consider the preferred prefix p(y), and let C ∈ F ∪ ∂(D). Then p(y)[C∈F]is either a half twist, or equal to p(y[C∈F ]), or to ι(y[C∈F]), or to ι(y−1 [C∈F]). 5.2 Rigidity, sliding circuits and preferred conjugators The key ingredient for showing the main theorem will be the properties of the preferred conjugator P(y) of a braid ywhich preserves a family of round curves. In fact, we won’t be able to gain sufficient control over P(y), and we have to study the preferred conjugator P(yk) for some suitable power ykof yinstead. The need of taking powers to obtain a better behavior of the preferred conjugator is the reason why we have to work with the set SC[m](x), rather than simply the set of sliding circuits SC(x). The property we will require for a power of y∈SC(x) involves the notion of rigidity introduced in [3], which measures how the left normal form of an element varies when taking its square. More precisely, if x= ∆px1···xris in left normal form with r > 0, one could expect that the left normal form of x2is ∆2pτp(x1)···τp(xr)x1···xr, but in general this is not the case. We say that the rigidity of xis R(x) = k/r if kis the biggest integer in {0,1,...,r}such that the first 2|p|+kfactors in the left normal form of x2are ∆2pτp(x1)···τp(xk). The two extreme cases are R(x) = 0, in which all factors in the left normal form of xare modified when considering x2, and R(x) = 1, in which no factor is modified, and the left normal form of x2is the expected one we saw above. In this latter case we say that xis rigid. We will be interested in the case in which R(x)>0 and R(x−1)>0. This kind of elements are characterized by the following result. Lemma 5.8. [3, Lemmas 3.4, 3.5 and Corollary 3.6] Let x∈Bnwith ℓ(x)>0. The following conditions are equivalent: 1. R(x)>0. 18 2. inf(x2) = 2 inf(x)and ι(x2) = ι(x). 3. inf(xm) = minf(x)and ι(xm) = ι(x)for every m > 0. The following conditions are also equivalent: 1. R(x−1)>0. 2. sup(x2) = 2 sup(x)and ϕ(x2) = ϕ(x). 3. sup(xm) = msup(x)and ϕ(xm) = ϕ(x)for every m > 0. These equalities of infima, suprema, initial and final factors yield a good behavior of the preferred conjugators, as we shall see. Moreover, this condition is preserved by cyclic sliding, if the element is in its super summit set: Lemma 5.9. Let x∈Bnand y∈SSS(x)with ℓ(y)>0. Then R(s(y)) ⩾R(y)and R(s(y)−1)⩾ R(y−1). Proof. Let r=ℓ(y)>0. Since y∈SSS(x) one has s(y)∈SSS(x), hence ℓ(s(y)) = r. Notice that the property R(y)⩾k/r can be rewritten as y2∧∆2p+k= (y∧∆p+k)∆p. One can apply to this equality the transport map based at y[16]. This map sends yto s(y), ∆ to itself, and preserves products and greatest common divisors. Hence one obtains s(y)2∧∆2p+k= (s(y)∧∆p+k)∆p, which is equivalent to R(s(y)) ⩾k/r. Hence R(y)⩾k/r implies R(s(y)) ⩾k/r for every k∈ {0,...,r}, so one has R(s(y)) ⩾R(y). Replacing yby y−1, which is also in its super summit set, one has R(s(y−1)) ⩾R(y−1). The result follows as s(y−1) = s(y)−1(see the argument that follows Definition 3.1). The elements in a sliding circuit that fulfill the required rigidity conditions also satisfy the following important property: their preferred conjugator is rigid. Proposition 5.10. Let x∈Bnand y∈SC(x)with ℓ(y)>0. If R(y)>0and R(y−1)>0, then the product p(y)p(s(y)) is left-weighted, and P(y)is rigid. Proof. Let us first prove that p(y)p(s(y)) is left-weighted. Consider the biggest element α4p(s(y)) such that p(y)αis simple. Let ∆py1···yrbe the left normal form of y. Notice that p(s(y)) 4 ι(s(y)) 4s(y)∆−p=p(y)−1yp(y)∆−p. Hence p(y)p(s(y)) 4yp(y)∆−p4y2∆−2p. Since ysatisfies the required rigidity conditions, Lemma 5.8 tells us that inf(y2) = 2p, hence the initial factor of y2∆−2pis precisely ι(y2), which is equal to ι(y), again by Lemma 5.8. Since we are assuming that p(y)αis a simple prefix of p(y)p(s(y)), it follows that p(y)α4ι(y2) = ι(y). In the same way, as p(y−1) = ι(y−1)∧ι(y) = p(y) one has p(s(y−1)) = p(s(y)−1) = p(s(y)), we can apply the above argument to y−1and it follows that p(y)α4ι(y−1). Therefore p(y)α4ι(y)∧ι(y−1) = p(y), so α= 1, and the first half of the proposition is proven. Now, if the hypotheses of Proposition 5.10 are satisfied by y, then by Lemma 5.9 they are also satisfied by sk(y) for every k > 0. So not only the product p(y)p(s(y)) is left-weighted as written, but also p(si(y)) p(si+1(y)) is left-weighted for every i > 0. Thus the left normal form of P(y) is precisely p(y)p(y(1))···p(y(N−1)), where Nis the length of the sliding circuit of y. Moreover, as y(N)=y, the product p(y(N−1))p(y) is also left-weighted, hence the left normal form of P(y)2is p(y)p(y(1))···p(y(N−1))p(y)p(y(1))···p(y(N−1)), which means that P(y) is rigid. Once we have seen that if R(y)>0 and R(y−1)>0 then P(y) is rigid, we are interested in finding elements which satisfy these rigidity conditions, so we can gain sufficient control over their preferred conjugator. In the next result,we will see that if N=||∆||3− ||∆||2, every element in SC[N](x) has a power which satisfies the required rigidity conditions. 19 Proposition 5.11. Let x∈Bn, and let N=||∆||3− ||∆||2. Given y∈SC[N](x), there is an integer mwith 0< m < N such that R(ym)>0and R(y−m)>0. Proof. In [21] it is shown that for every x∈Bnthere exists some k⩽||∆||2such that every element in SSS(xk) is periodically geodesic. That is, for every z∈SSS(xk) one has inf(zt) = t·inf(z) and sup(zt) = t·sup(z) for all t > 0. In particular, since y∈SC[N](x) and k < N, one has yk∈SC(xk)⊂SSS(xk), so ykis periodically geodesic. This means that inf(ykt) = t·inf(yk) and sup(ykt) = t·sup(yk) for all t > 0. Once ykis known to be periodically geodesic, one has a chain ι(yk)4ι(y2k)4ι(y3k)4··· (the initial factor of yik is a prefix of the initial factor of y(i+1)k). Notice that this chain stabilizes at the first repetition, hence it must stabilize in less than ||∆|| steps. In the same way, since ykis periodically geodesic one has a chain ··· <ϕ(y3k)<ϕ(y2k)<ϕ(yk) (the final factor of yik is a suffix of the final factor of y(i+1)k), which must also stabilize in less than ||∆|| steps. Therefore, for some t⩽||∆|| − 1 one has ι(ytk) = ι(y2tk) and ϕ(ytk) = ϕ(y2tk). We can take m=kt ⩽ ||∆||3− ||∆||2and we will have, on the one hand, inf(y2m) = 2 inf(ym) and ι(y2m) = ι(ym) (thus R(ym)>0), and on the other hand sup(y2m) = 2 sup(ym) and ϕ(y2m) = ϕ(ym) (thus R(y−m)) >0), so the result follows. Now we will place ourselves in the case in which a braid y∈SC(x) satisfies the above rigidity conditions, that is, R(y)>0 and R(y−1)>0 (by Proposition 5.11 we know how to find a braid which fulfill these requirements). We saw in Proposition 5.10 that in this case P(y) is rigid. We will now see that, if for some reason we need to consider some power of y, this makes no harm, as every power of ysatisfies the same properties (even the property of belonging to a sliding circuit). Proposition 5.12. Let x∈Bnand y∈SC(x)with ℓ(y)>0. If R(y)>0and R(y−1)>0, then for every m≥1one has y∈SC[m](x)(that is, ym∈SC(xm)), R(ym)>0,R(y−m)>0, and P(y)is a positive power of P(ym). Proof. We recall from [3, Proposition 3.9] that if y∈USS(x) and ℓ(y)>0, then R(y)⩽R(ym) for all m⩾1. Hence, if y∈SC(x) is such that R(y)>0 and R(y−1)>0, the same happens for every power of y. By Lemma 5.8, ι(ym) = ι(y) and ϕ(ym) = ϕ(y). Hence p(ym) = ι(ym)∧∂(ϕ(ym)) = ι(y)∧ ∂(ϕ(y)) = p(y). Therefore s(ym) = (s(y))m. By Lemma 5.9, s(y) also satisfies the required rigidity conditions, that is, R(s(y)) >0 and R(s(y)−1)>0. Hence p(s(y)m) = p(s(y)) and then s2(ym) = s(s(ym)) = s(s(y)m) = (s2(y))mfor every m > 0. Iterating this argument, one obtains p((st(y))m) = p(st(y)) and st(ym) = (st(y))mfor every t, m > 0. In other words, applying iterated cyclic sliding to ymis the same thing as applying iterated cyclic sliding to yand then taking the mth power, since the conjugating elements coincide. As yis in a sliding circuit, applying iterated cyclic sliding leads back to y, and the same happens to ym. That is, ymis also in a sliding circuit, as we wanted to show. Moreover, some positive power of P(ym) equals P(y) as the preferred prefixes along the circuits of yand ymcoincide. Actually, we will have P(ym) = P(y), unless there is some zin the sliding circuit of ysuch that zm=ym, in which case P(ym) will be shorter than P(y), but continuing along the sliding circuit of ymone will obtain several repetitions of P(ym) being equal to P(y). We end this section with a result about preferred conjugators which we shall need soon. It says that the preferred conjugators of any two elements in the same set of sliding circuits are conjugate, up to raising those preferred conjugators to some suitable powers. This will allow us to obtain information concerning P(y), for some y∈SC(x), just by comparing P(y) with P(z), for some other z∈SC(x). This time we do not require any rigidity condition. 20 Lemma 5.13. Let x∈Bnand y, z ∈SC(x). Then P(y)sis conjugate to P(z)tfor some s, t > 0, and one can take as conjugating element any braid αconjugating yto z. Proof. Let Nand Mbe the lengths of the sliding circuits of yand z, respectively. That is, sN(y) = yand sM(z) = z. Let αbe such that α−1yα =z. We can apply to αthe transport map defined in [16]. If one applies this transport map ktimes to α, we obtain an element denoted α(k), which is a conjugating element from sk(y) to sk(z). Namely, α(k)=p(y)p(s(y)) ···p(sk−1(y))−1αp(z)p(s(z)) ···p(sk−1(z)).(1) In [16, Lemma 8] it is shown that, in this situation, z∈SC(x) if and only if α(sN)=αfor some s > 0. This means that αconjugates ssN (y) = yto ssN (z), but since the conjugate of yby α is precisely z, it follows that ssN (z) = zhence sN =tM for some t > 0. But then Equality (1), replacing kby sN, reads α= (P(y)s)−1α P(z)tor, in other words, α−1P(y)sα=P(z)t. 5.3 Sliding circuits and canonical reduction systems Proposition 5.14. Let x∈Bnand y∈SC(x). If R(y)>0and R(y−1)>0, then CRS(P(y)) ⊂ CRS(y). Proof. Notice that the result holds if yis periodic, since the only periodic elements satisfying the rigidity hypothesis are powers of ∆, and then P(y) = 1, so both canonical reduction systems are empty. If yis pseudo-Anosov the result also holds, since P(y) is in the centralizer of yso it must be either pseudo-Anosov or periodic [19], and in either case CRS(P(y)) = ∅=CRS(y). We can then assume that yis non-periodic and reducible, that is, CRS(y)6=∅. And of course we can assume that CRS(P(y)) 6=∅, otherwise the result is trivially true. By Proposition 5.12, we can make the further assumption that yis pure, since ymwill satisfy the same hypothesis as y, and the canonical reduction systems of yand of its preferred conjugator are preserved by taking powers of y. Replacing P(y) by a power if necessary in the following discussion, we will also assume that P(y) is pure. Let F=CRS(y)∪ {∂(D2)}, and let us assume for a moment that all curves in Fare round. Since P(y) is pure and commutes with y,P(y) sends Fto itself, curve-wise. This implies that an essential reduction curve of P(y) either belongs to F(as we want to show) or can be isotoped to be disjoint from F. In the latter case, it would correspond to an essential reduction curve of P(y)[C∈F]for some [C]∈ F. Thus we must show that P(y)[C∈F ]does not admit an essential reduction curve, for every [C]∈ F. Let then [C]∈ F. We know that y[C∈F]is either periodic or pseudo-Anosov, and that the braid P(y)[C∈F]commutes with y[C∈F ]. If y[C∈F ]is pseudo-Anosov, then P(y)[C∈F ]must be either pseudo-Anosov or periodic, hence it admits no essential curves. If y[C∈F]is periodic, it has to be a power of the full twist, since yis pure. But in this case Proposition 5.7 tells us that p(y)[C∈F]is either trivial or a half twist (here we use that Fconsists of round curves). Hence, applying cyclic sliding to y, we obtain a braid whose component associated to Cis also a power of the half twist, and we can repeat the argument until one gets back to y, to conclude that P(y)[C∈F]is a (possibly trivial) power of ∆. Hence P(y)[C∈F ]does not admit an essential curve, also in this case. Therefore, all essential reduction curves of P(y) are essential curves of y, that is, CRS(P(y)) ⊂CRS(y) if CRS(y) is a family of round curves. Now we show the general case, in which the curves in CRS(y) are not necessarily round. We cannot apply the above argument as we do not know, a priori, that the components of P(y) corresponding 21 to the periodic components of yare powers of ∆. Nevertheless, we will be able to show this by comparing preferred prefixes with the aid of Lemma 5.13. We just need to find a suitable braid whose reduction curves are round and which satisfies the hypothesis of Proposition 5.14, that is, it belongs to a sliding circuit, and both the braid and its inverse have nonzero rigidity. By Corollary 5.3, for every N > 0 there is some element z∈SC[N](y) whose essential curves are all round. We can then take N=||∆||3− ||∆||2and use Proposition 5.11 to conclude that for some mwith 0 < m ⩽Nwe have R(zm)>0 and R(z−m)>0. As m≤N, we also have zm∈SC(ym). Notice that the canonical reduction systems of zand zmcoincide, so zmis a braid whose canonical reduction system is made of round curves, which belongs to a sliding circuit, and such that R(zm)>0 and R(z−m)>0, so zmis the braid we were looking for. To simplify notation, we recall from Proposition 5.12 that the result will be shown for yif it is shown for ym, so we can replace yby ym, and this will replace zby zm. We can then assume that zis a braid whose canonical reduction system is made of round curves, which belongs to a sliding circuit, and such that R(z)>0 and R(z−1)>0. As the result is shown for elements whose canonical reduction system is made of round curves, CRS(P(z)) ⊂CRS(z). But recall from Lemma 5.13 that P(z)sis conjugate to P(y)tfor some s, t > 0, and that a conjugating element αis precisely a conjugating element from zto y. Since the essential curves of P(z) and P(z)scoincide, we have CRS(P(z)s) = CRS(P(z)) ⊂ CRS(z). Conjugating both P(z)sand zby α, corresponds to applying αto their essential curves, hence it follows that CRS(P(y)t)⊂CRS(y). As the essential curves of P(y)tand P(y) coincide, this means CRS(P(y)) ⊂CRS(y), as we wanted to show. We have now assembled most of the ingredients for showing that our main result, Theorem 3.4, follows from the rigid case. The key lemma for this reduction to the rigid case is as follows. Lemma 5.15. Let x∈Bnbe a non-periodic, reducible braid. Let N=||∆||3− ||∆||2. For every element y∈SC[N](x)there is some m⩽Nsuch that either ymis rigid, or P(ym)is rigid, admits essential reduction curves, and all its essential reduction curves are essential reduction curves of y. Proof. Let x∈Bnbe a non-periodic, reducible braid, N=||∆||3− ||∆||2and y∈SC[N](x). By Proposition 5.11 there is some power ymwith m⩽Nsuch that R(ym)>0 and R(y−m)>0. Notice also that ym∈SC(xm). Hence ymsatisfies the hypothesis of Propositions 5.10 and 5.14, so P(ym) is rigid and CRS(P(ym)) ⊂CRS(ym). If CRS(P(ym)) 6=∅, the result follows. Suppose on the contrary that CRS(P(ym)) = ∅. This means that P(ym) must be either periodic or pseudo-Anosov. It cannot be pseudo-Anosov, as it commutes with the non-periodic, reducible braid ym, while pseudo-Anosov elements can only commute with pseudo-Anosov or periodic ones. Hence P(ym) is periodic. Notice that P(ym) cannot be a nontrivial power of ∆, since by Proposition 5.10 the left normal form of P(ym) is a product of preferred prefixes, each of them not equal to ∆ by definition. As the only rigid, periodic braids are the powers of ∆, it follows that P(ym) must be trivial. This is equivalent to saying that ymis rigid. The following result tells us how to deal with the rigid case. We will assume for the moment; it will be shown in the next section: Theorem 5.16. Let β∈Bnbe a non-periodic, reducible braid which is rigid. Then there is some positive integer k⩽nsuch that one of the following conditions holds: 1. βkpreserves a round essential curve, or 2. inf(βk)and sup(βk)are even, and either ∆−inf(βk)βkor β−k∆sup(βk)is a positive braid which preserves an almost round essential reduction curve whose corresponding interior strands do not cross. 22 In particular, some essential reduction curve for βis either round or almost round. We can finally show our main result, assuming that Theorem 5.16 holds. Proof of Theorem 3.4. Let x∈Bnbe a non-periodic, reducible braid, N=||∆||3− ||∆||2and y∈SC[N](x). Let m⩽Nbe the integer given by Lemma 5.15. If ymis rigid, then by Theorem 5.16 CRS(ym) contains a curve which is either round or almost round. As CRS(ym) = CRS(y), the result follows in this case. If ymis not rigid, then by Lemma 5.15, P(ym) is rigid and ∅ 6=CRS(P(ym)) ⊂CRS(ym) = CRS(y). By Theorem 5.16 again, some curve in CRS(P(ym)), and thus in CRS(y), is either round or almost round. This shows that every element in SC[N](x) admits an essential reduction curve which is either round or almost round. This implies the result. 6 Reducible rigid braids This section is devoted to the proof of Theorem 5.16. Let β∈Bnbe a non-periodic, reducible braid which is rigid. Then βbelongs to a sliding circuit (as s(β) = β), also ℓ(β)>0 and CRS(β)6=∅. Also, any power βkof βis also non-periodic, reducible and rigid, and has the same canonical reduction system as β. Notice that for every curve C ∈ CRS(β), there is some t⩽n/2 such that [C]βt= [C]. Replacing βtby its square if necessary, it follows that for every C ∈ CRS(x) there is some even k⩽nsuch that βkpreserves [C], and both inf(βk) and sup(βk) are even. Fix an innermost curve C ∈ CRS(β) and consider βkfor some even k⩽nsuch that [C]βk= [C]. Let ∆2px1···xrbe the left normal form of βk, and denote x=x1···xr= ∆−inf(βk)βk. Notice that CRS(β) = CRS(βk) = CRS(∆2px) = CRS(x), as ∆2preserves every simple closed curve of the punctured disc. Moreover x=x1···xris non-periodic, reducible and rigid. Denote F=CRS(x) = CRS(β)6=∅. As Cis an innermost curve of F, the component x[C∈F ] must be either periodic or pseudo-Anosov. Recall that in order to define x[C∈F ]one conjugates x by the minimal standardizer of Fto obtain y=bx, and the curve corresponding to C, namely b C, is an innermost essential curve of ywhich is round. By [20, Theorem 4.9] ybelongs to its Ultra Summit Set provided xdoes. It is not difficult to modify the proof in [20] to show that ybelongs to SC(x) provided xdoes. This is the case, as xis rigid. But it is shown in [16] that, if xis rigid, SC(x) consists precisely of the rigid conjugates of x. Hence yis rigid. Moreover, as xpreserves [C], y[ b C∈ b F]is a conjugate of x[C∈F], which is either periodic or pseudo-Anosov. Suppose y[ b C∈ b F]is periodic. As yis a rigid, positive braid, whose left normal form has the form y1···yr, one has that yry1is left weighted as written. But the left normal form of y[ b C∈ b F]is determined by the left normal form of y, in the sense explained in Lemma 5.4. Hence y[ b C∈ b F] must be a rigid, positive braid whose left normal form is the product of r(possibly trivial) simple elements. Since the only periodic rigid elements are powers of ∆, it follows that either y[ b C∈ b F]is trivial, or y[ b C∈ b F]= ∆r k(where kis the number of strands inside b C). If y[ b C∈ b F]is trivial, the interior braid of x= ∆−inf(βm)βmassociated to Cmust also be trivial, as it is a conjugate of y[ b C∈ b F]. By Proposition 2.3, Cis either round or almost round, so Theorem 5.16 holds in this case. 23 Suppose that y[ b C∈ b F]= ∆r k, and notice that r= sup(βm)−inf(βm) is even. Let us consider the n-strand braids x′and y′such that xx′= ∆rand yy′= ∆r. We remark that x′and y′are basically the inverses of xand y, multiplied by some even power of ∆ so that their infimum becomes 0. Hence x′and y′are positive, rigid braids of infimum 0 and canonical length r, whose canonical reduction systems coincide with those of xand y, respectively. Let αbe such that α−1xα =y. Since α−1∆rα= ∆ras ris even, we obtain that α−1x′α=y′. Moreover, y′ [ b C∈ b F]is trivial. Hence, the strands of x′interior to Cdo not cross. By Proposition 2.3, Cis either round or almost round. Now notice that x′=x−1∆r=β−m∆inf(βm)+r=β−m∆sup(βm). Hence Theorem 5.16 also holds in this case. It only remains to prove Theorem 5.16 in the case in which x[C∈F ]is pseudo-Anosov. Lemma 6.1. Let x∈Bn. Given two elements y, z ∈SC(x), there is a sequence of conjugations y=α1 s1 −→ α2 s2 −→ α3··· sr −→ αr+1 =z such that for every i= 1, . . . , r one has αi+1 =αsi i∈SC(x), and either si4ι(αi)or si4ι(α−1 i). Proof. This proof follows the ideas in [9, 13, 4]. First, we can assume that ℓ(y)>0, otherwise SC(x) = {∆p}for some p, and the result becomes trivial as y=z. Now yand zare conjugate since they belong to SC(x). Multiplying any conjugating element by a sufficiently large power of ∆, it follows that z=yαfor some positive element α. This conjugating element αcan obviously be decomposed into a product of indecomposable conjugating elements, that is, α=s1···sr, where αi+1 =ys1···si∈SC(x) for i= 1,...,r, and siis positive and cannot be decomposed as a product of two nontrivial positive elements si=ab such that αa i∈SC(x). Notice that simust be simple, otherwise we could take a=si∧∆ (which by Theorem 4.1 satisfies αa i∈SC(x)) to decompose si. We must show that such an indecomposable element simust be a prefix of either ι(αi) or ι(α−1 i). Denote t=si∧ι(α−1 i). We claim that (αi)t∈SC(x). Indeed, by definition, one has ι(α−1 i) = ∆∧(α−1 i∆−inf(α−1 i)). Since αi∈SC(x), it is clear that α∆ i∈SC(x) and that α(α−1 i∆−inf(α−1 i)) i∈ SC(x). By Theorem 4.1, αι(α−1 i) i=α∆∧(α−1 i∆−inf(α−1 i)) i∈SC(x). But αsi i=αi+1 ∈SC(x), so applying Theorem 4.1 again one has αι(α−1 i)∧si i= (αi)t∈SC(x), as we wanted to show. We then have a positive prefix t4sisuch that (αi)t∈SC(x). Since siis an indecomposable conjugator, it follows that either t=sior t= 1. In the former case si=t=si∧ι(α−1 i), which implies si4ι(α−1 i), hence the result holds in this case. Suppose then that t= 1. This means ι(α−1 i)∧si=∂(ϕ(αi)) ∧si= 1, which is equivalent to say that ϕ(αi)siis left weighted as written. Let ∆pa1···arbe the left normal form of αi. We have then shown that arsiis left weighted as written, so ∆pa1···arsiis the left normal form of αisi. But we know that αi+1 =s−1 iαisi∈SC(x). In particular ℓ(αi+1) = r, where αi+1 =s−1 i∆pa1···arsi. This implies that τp(si)4a1···arsi, where the right hand side is in left normal form and the left hand side is a simple element, hence τp(si)4a1, that is, si4τ−p(a1) = ι(αi), so the result also holds in this case. Finally, here is the result that completes the proof of Theorem 5.16: Proposition 6.2. Let xbe a reducible rigid braid, and let Cbe an invariant curve of xwhose corresponding interior braid is pseudo-Anosov. Then Cis round. Proof. We know from [16] that SC(x) is the set of rigid conjugates of x, hence x∈SC(x), and we know from Corollary 5.3 that there is an element ˜x∈SC(x) whose reduction curves are all 24 round. By Lemma 6.1 there is a chain of conjugations ˜x=α1 t1 −→ α2 t2 −→ α3··· tr −→ αr+1 =x such that for every i= 1, . . . , r one has αi+1 =αti i∈SC(x), and either ti4ι(αi) or ti4ι(α−1 i). Suppose that Cis not round. This means that the curve C˜xof ˜xcorresponding to Cis a round curve which loses its roundness after the application of t1···tr. This implies that there must be two rigid braids y, z ∈SC(x) (precisely αiand αi+1 for some i), conjugate by a simple element s (precisely ti), a round invariant curve Cyof ywhose corresponding interior braid is pseudo-Anosov, and the corresponding invariant curve of z, [Cz] = [Cy]s, which is not round. Moreover sis either a prefix of ι(y) or a prefix of ι(y−1) (as s=ti). Since the inverse of a pseudo-Anosov braid is also pseudo-Anosov, and the rigidity and reduction curves of a braid are preserved by taking inverses, we can replace yand zby y−1and z−1if necessary, so we can assume that sis a prefix of ι(y−1). Since taking powers and multiplying rigid braids by ∆2kare operations which do not affect their rigidity, their initial factors, their invariant curves or the geometric type of their corresponding interior braids, we can further assume that yand zare pure braids, and that inf(y) = inf(z) = 0. Suppose that some nontrivial positive prefix s′4sis such that [Cy]s′is round, and denote by ρthe minimal positive element such that s′4ρand yρis rigid (equivalently, yρ∈SC(x)). Since sis an indecomposable conjugator, we must have ρ=s. But we will now see that ρsends [Cy] to a round curve, while [Cy]ρ= [Cy]s= [Cz] is not round. A contradiction that will imply that s′= 1. Indeed, by [17, Algorithm 2, step 3(b)], ρcan be computed in the following way: first, while ys′/∈SSS(x), replace s′by s′·1∨(ys′)−1∆inf y∨ys′∆−sup y. Notice that the three elements 1, (ys′)−1∆inf yand ys′∆−sup ysend [Cy]s′to a round curve. In the terminology of [20], the three elements belong to the standardizer of [Cy]s′. Since it is shown in [20] that the standardizer of a curve is closed under ∨, it follows that each step of this procedure replaces s′by a bigger element, which belongs to the standardizer of [Cy]. Hence we can assume that ys′∈SSS(x). The second step to compute ρ, explained in [16, Theorem 2], consists of applying iterated sliding to ys′until one reaches a rigid element. Multiplying s′on the right by all conjugating elements, one obtains ρ. But each conjugating element for sliding maintains the roundness of our distinguished curve, from Proposition 5.2. Therefore, ρsends Cyto a round curve, but [Cy]ρ= [Cz] is not round. A contradiction. It follows that s′= 1, or in other words, there is no nontrivial prefix s′4sis such that [Cy]s′is round. Let p, p + 1,...,q be the punctures inside Cy. We will collect the strands of sinto three sets, L={1,...,p−1},I={p, p + 1,...,q}and R={q+ 1, q + 2,...,n}, depending whether they start to the left, inside or to the right of Cy. Since every prefix of smust deform the round curve Cy, and the braid sis simple, it follows that the strands in L(resp. in Iand in R) do not cross each other in s, since this would imply that two consecutive strands in L(resp. in Iand in R) would cross in s, and the corresponding crossing would be a prefix of spreserving the roundness of Cy, a contradiction. Also, no strand of sin Lcan cross all the strands in I, since this would imply that the strand p−1 would cross all the strands in I, and then σp−1σp···σq−1would be a prefix of s preserving the roundness of Cy, a contradiction. In the same way, no strand of sin Rcan cross all the strands in I. In summary, sis a simple braid of a very particular form: some strands of L may cross some (but not all) strands of I, some strands of Rmay cross some (but not all) strands of I, and any two strands belonging to the same group (L,I, or R) never cross. Recall that yand zare rigid, and let y1···yrand z1···zrbe their left normal forms. For i= 0 ...,r, we denote [Cy,i] = [Cy]y1···yiand [Cz,i] = [Cz]z1···zi. By Theorem 5.1, Cy,i is round for every i, and by the rigidity of zit follows that Cz,i is not round for any i. Now, for i= 0,...,r, consider the braid si= (y−1 i···y−1 1)s(z1···zi), which is the ith transport of sunder cycling 25