Dual Garside structure and reducibility of braids

DUAL GARSIDE STRUCTURE AND REDUCIBILITY OF BRAIDS MATTHIEU CALVEZ Abstract. Benardete, Gutierrez and Nitecki showed an important result which relates the geometrical properties of a braid, as a homeomorphism of the punctured disk, to its algebraic Garside-theoretical properties. Namely, they showed that if a braid sends a standard curve to another standard curve, then the image of this curve after each factor of the left normal form of the braid (with the classical Garside structure) is also standard. We provide a new simple, geometric proof of the result by Benardete-Gutierrez-Nitecki, which can be easily adapted to the case of the dual Garside structure of braid groups, with the appropriate definition of standard curves in the dual setting. This yields a new algorithm for determining the Nielsen-Thurston type of braids. 1. Introduction Braid groups are both mapping class groups and Garside groups. The links between these two features of braid groups seem to be very deep and their investigation is currently the goal of several works. In particular the Garside-theoretic approach to the problem of deciding algorithmically the Nielsen-Thurston type of a given braid turns out to be very fruitful [1],[19],[18],[17],[5]. The n-strand braid group is naturally identified with the mapping class group of the n-times punctured disk Dn. Braids induce a (right) action on the set of isotopy classes of simple closed curves in Dn: considering the isotopy class [C] of a simple closed curve Cand an n-braid x, the isotopy class of simple closed curves resulting from the action of xon [C] will be denoted by [C]x. The simple closed curves we shall consider in the present paper will be nondegenerate, that is surrounding more than one and less than npunctures. Let us assume for the moment that Dnis parametrized as the disk with diameter [0, n + 1] in C and points 1,2,. . . , n removed. In this setting, a curve Cis said to be standard, or round, if it is isotopic to a geometric circle in Dn. That is, if the punctures enclosed by Care consecutive. An isotopy class [C] is said to be standard, or round, if some (hence every) representative is round. Round curves are particularly useful for decomposing a reducible braid into its corresponding components [17]. As every reducible braid has a conjugate which preserves a family of round curves [1], searching for such a conjugate becomes a possible strategy both for determining whether a braid is reducible and for finding its geometric components. Benardete, Gutierrez and Nitecki [1] explain how to determine whether such a conjugate exists, and also how to find it, thanks to the classical Garside structure of braid groups. Braid groups are the main examples of Garside groups [6]. This means that they admit a lattice structure, and a special element denoted ∆, satifying some properties first discovered by Garside in [12]. We will refer to this as the classical Garside structure of the braid group. Using this structure, one can define the left normal form of a braid x, which is a unique decomposition of the form x= ∆px1· · · xr(see [8],[7]) in which the factors belong to the set of the so-called simple elements. 2010 Mathematics Subject Classification. 20F36. This work was done while the author was staying at the University of Seville. The visit was partially supported by a grant for international mobility by the Universit´e Europ´eenne de Bretagne and by the spanish research group FQM-218 (Junta de Andaluc´ıa). 1 2 MATTHIEU CALVEZ The result by Benardete, Gutierrez and Nitecki, which relates round curves and left normal forms, is the following: Theorem 1 ([1],[19]).Let Cbe a standard curve in Dn. Let x= ∆px1···xrbe a braid in (classical) left normal form. If [C]xis standard, then [C]∆px1···xmis standard for m= 1, . . . , r. Thanks to this result, and applying special conjugations called cyclings and decyclings, it is possible to determine whether a braid has a conjugate which preserves a family of round curves, hence it is possible to know whether a braid is reducible, with the aid of the Garside structure of the braid group [1]. The method mentioned in the previous paragraph needs to compute a big subset of the conjugacy class of a braid. This has been improved in [18], avoiding the computation of such a big subset, at the cost of enlarging the set of standard curves to include round and also almost-round curves. This raises the question whether the notion of round curves, and the use of the classical Garside structure, are the best choices for this kind of techniques. There is another well-known Garside structure of the braid group, discovered by Birman, Ko and Lee [3], which is known as the dual Garside structure. With respect to this structure, the left normal form of a braid is a unique decomposition x=δpx1· · · xr, where δis the special (Garside) element, and the factors are simple, with respect to the dual structure. In this paper we prove the analogue of Theorem 1 in the dual setting. We remark that the proofs of Theorem 1 given in [1] and [19] cannot be adapted in a natural way to the dual Garside structure of the braid group. For that reason we give a new proof of Theorem 1, in the classical setting, which can be naturally adapted to the dual setting. To this purpose we also introduce a natural notion of standard curve related to the dual Garside structure of the braid group. Namely, as round curves determine standard parabolic subgroups of the braid group, with the Artin strucure, the standard curves in the dual setting will be those determining standard parabolic subgroups, with the dual structure. It is important to mention that a generalization of Theorem 1 to Artin-Tits groups of spherical type, with the classical Garside structure, is given in [15]. The powerful algebraic methods used in [15] are based in the theory of Garside categories and seem to allow further generalization of Theorem 1 to dual Garside structures [16], although this does not appear in the literature. Here we present simple, geometric proofs, for the particular but important cases of the two well known structures of the braid groups. Our proof of Theorem 1 can be sketched as follows. We show that if Cis round and [C]∆px1is not round, then [C]∆px1···xmis not round for m= 1, . . . , r. Hence [C]∆px1···xrcannot be round, contradicting the hypothesis. We assume the usual Artin generator σi, for i= 1, . . . , n−1, to be the counterclockwise half Dehn twist along the segment [i, i + 1]. We will see that if [C]∆px1is not round, then a portion of (a suitable representative of) [C]∆px1crosses the real line in the way shown in Figure 1, for some i < j < k. Moreover, x1σjis simple, meaning that the strands of x1ending at jand j+ 1 do not cross. Figure 1. Strands which arrive at positions jand j+ 1 (depicted as crosses) have not crossed in x1. We then prove by recursion that, as x1· · · xris in left normal form, the above properties must hold for [C]∆px1···xm, for m= 1, . . . , r. That is, some portion of (a suitable representative of) [C]∆px1···xmmust cross the real line as in Figure 1, for some im< jm< km, where xmσjmis simple. This implies in particular that [C]∆px1···xris not round, showing Theorem 1. DUAL GARSIDE STRUCTURE AND REDUCIBILITY OF BRAIDS 3 This proof can be adapted to the dual setting as follows. First, in order to work with the dual Garside structure of the braid group, it is more convenient to parametrize Dnas the unit disk in Cwith set of punctures {1 2e−2ikπ n, k = 1, . . . , n}. Throughout the paper the puncture 1 2e−2ikπ n will be denoted kfor brevity, and the disk Dnwith this parametrization will be denoted D∗ n. We remark that, if one defines standard curves as isotopy classes of geometric circles, as above, then the analogue of Theorem 1 is not true in the dual setting (see Example 12). Hence we need a different definition for standard curves, adapted to the dual Garside structure: Definition 2 (See also Definition 13).A simple closed curve in D∗ nis called standard if it is isotopic to a curve which can be expressed, in polar coordinates, as a function ρ=ρ(θ), for θ∈[0,2π[. See Figure 2(a). An isotopy class [C]is said to be standard if some (hence every) representative is standard. The main result of this paper is the following: Theorem 3. Let Cbe a standard curve in D∗ n. Let x=δpx1· · · xrbe a braid in dual left normal form. If [C]xis standard, then [C]δpx1···xmis standard for m= 1, . . . , r. Figure 2. (a) shows a standard curve as in Definition 2. (b) A part of a nonstandard curve. The proof of this result parallels the one of Theorem 1 and its simplicity allows to outline it right here. First recall that the usual generators of the dual Garside structure are the braids ai,j =aj,i corresponding to the counterclockwise half Dehn twist along the chord segment joining the punctures iand j, for each pair 1 ⩽i, j ⩽n, with i=j. We will see that if [C]δpx1is not standard, then a portion of (a suitable representative of) [C]δpx1 crosses the circle of radius 1 2in the way shown in Figure 2(b), for some 1 ⩽i, j ⩽n. Moreover, x1ai,j is simple. We then prove by recursion that, as x1· · · xris in left normal form, the above properties must hold for [C]δpx1···xm, for m= 1, . . . , r. That is, some portion of (a suitable representative of) [C]δpx1···xmmust cross the circle of radius 1 2as in Figure 2(b), for some 1 ⩽im, jm⩽n, where xmaim,jmis simple. This implies in particular that [C]δpx1···xris not standard, showing Theorem 3. The following two sections contain the detailed proofs of Theorems 1 and 3, respectively. The last section contains a new algorithm for solving the reducibility problem in braid groups, based on Theorem 3. Acknowledgements. Thanks to Eddy Godelle for his receptiveness to questions about his papers on parabolic subgroups of Garside groups. The author also wishes to thank Juan Gonz´alez-Meneses for countless helpful comments on earlier versions of the paper. 2. The classical Artin-Garside case This section deals with the classical case. Throughout the section, we thus assume Dnto be parametrized as the disk with diameter [0, n + 1] in Cand with the points 1,2, . . . , n removed. In order to make rigorous the idea expressed in Figure 1, we associate to each isotopy class of simple closed curves [C] in Dna unique reduced word W([C]) which we shall define in Subsection 2.1. The 4 MATTHIEU CALVEZ word W([C]) allows to describe carefully the action of positive braids on [C]; this will be achieved in Subsection 2.2. Subsection 2.3 will be devoted to the proof of Theorem 1. 2.1. From curves to words. We will always assume that the curves under consideration are nondegenerate, simple and closed, so unless otherwise stated, the word “curve” alone will mean “nondegenerate simple closed curve”. Let Cbe a curve in Dn, and suppose that it has a finite number of crossings with the real line, which are all transverse. We shall associate to Ca word W(C) that we now define. Our strategy to define the word W(C) already mostly appears in [10], Appendix A. We proceed as follows. Choose a point ∗of Cwhich lies on the real line as well as an orientation for C. Running along Cfollowing the chosen orientation, starting and ending at ∗, determines a word in the alphabet X={`,a,0, . . . , n}as follows: each arc through the upper half plane contributes a letter ato the word, each arc through the lower half plane, a letter `, and each intersection with the segment ]i, i + 1[ yields the letter i. The number corresponding to ∗can be chosen to be either at the beginning or at the end of the word. The word obtained in this way will be denoted W(C) and we call it the word associated to C. Choosing another point ∗or putting the letter determined by the intersection point ∗at the beginning or at the end of W(C) corresponds to a cyclic permutation of the letters in W(C), whereas choosing the reverse orientation of Cyields the reverse of W(C). Hence, words associated to curves are to be considered up to cyclic permutation of their letters and up to reverse. Example 4. Let Cbe the curve depicted in Figure 3. If we fix ∗in the interval ]1,2[ and the Figure 3. The curve Cof Example 4. clockwise orientation, then the word associated to Cis W(C) = 1 a2`0a6`3a5`6a3`2a0`. Notice that two curves related by an isotopy of Dnfixing the real diameter setwise have the same associated word. We say that the word associated to Cis reduced if it does not contain any subword of the form i`ior iai. We say that a curve Cis reduced if its associated word W(C) is reduced. Notice that reduced curves are exactly those which do not bound any bigon (see [10]) together with the real line. According to [10], every curve Cis isotopic to a reduced one Cred, which is unique up to isotopy of Dnfixing the real diameter setwise. We thus may finally define, for each isotopy class of curves [C] in Dn, its associated reduced word as W([C]) = W(Cred). 2.2. The action of positive braids. Let B+ nbe the submonoid of Bngenerated by σ1, . . . , σn−1, called the monoid of positive braids. Instead of the usual Artin generators, it will be convenient to work with the following bigger generating set of B+ n: {Σp,k =σp−1. . . σp−k,1⩽k < p ⩽n}. According to our previous convention that σiis a counterclockwise half-Dehn twist along the segment [i, i + 1], the braid Σp,k corresponds to a move of the puncture numbered pthrough the DUAL GARSIDE STRUCTURE AND REDUCIBILITY OF BRAIDS 5 upper half plane up to the position p−kwhile the punctures p−1, p −2, . . . , p −kare shifted one position to the right. Given the isotopy class of a curve Cand a positive braid xwe are going to describe which transformations have to be performed on the word W=W([C]) in order to obtain the word W([C]x). To this purpose we first focus on the case x= Σp,k. Since the generators we are considering are mainly moves of punctures through the upper half plane, we assume that the action of the braids Σp,k mainly modifies the upper arcs occuring in Cred (from which new lower arcs can arise) while the lower arcs are only modified by translating their endpoints. This will be described by the following formulae, which are also depicted in figure 4. We define, for i<j: (iaj)Σp,k =       iajif [p−k, p[∩ {i, j}=∅(F1) (i+ 1) a(j+ 1) if [p−k, p[∩ {i+ 1, j}={i+ 1, j}(F2) (i+ 1) a(p−k)`(p−k−1) ajif [p−k, p[∩ {i, j}={i}(F3) ia(p−k−1) `(p−k)a(j+ 1) if [p−k, p[∩ {i+ 1, j}={j}(F4) We can define in the same way (jai)Σp,k . It suffices to take the reverse of the above formulae (the picture is exactly the same than in Figure 4). Figure 4. How the action of the braid Σp,k does transform upper arcs? In dashed lines is represented the trace of the move of the puncture initially numbered p(up to the position p−k). In continuous lines the arc iajon the left hand side and its image (iaj)Σp,k on the right hand side. Now, let f Wbe the word obtained by replacing each subword iajin Wby the corresponding subword (iaj)Σp,k . This transforms the lower arcs (i`j) in W, just by translating their endpoints. Notice that f Wis not necessarily reduced, so that W([C]Σp,k ) and f Ware possibly not the same. The following explains how to turn f Winto the reduced word W([C]Σp,k ): Lemma 5. Let [C]be an isotopy class of curves and W=W([C]). Let 1⩽k < p ⩽n. Let f Wbe as above, and let WΣp,k be the word obtained from f Wby removing all instances of subwords of the form p`pa. Then WΣp,k =W([C]Σp,k ). Proof. We observe that the formulae defining (iaj)Σp,k do not contain any subword of the form c`cnor cac. Thus the possible instance of such a subword in f Wnecessarily arises from the 6 MATTHIEU CALVEZ transformation of a lower arc. Notice that a lower arc c`dcan only be transformed into an arc k`l, with k∈ {c, c+1}and l∈ {d, d+1}. Hence the latter arc forms a bigon with the horizontal axis if and only if c+ 1 = d,k=c+ 1 and l=d(up to reverse we may suppose that c < d), in which case f Wcontains the subword d`d. By the formulae defining (iaj)Σp,k , this happens if and only if d=p, that is c`d= (p−1) `p. In particular we have shown that no subword of the form caccan arise in f W. We now claim that removing the subwords p`pais sufficient in order to turn f Winto a reduced word; that is, every sequence p`pain f Wis a subsequence of a larger one, of the form aap`pab, with a=b. Let ha(p−1) `palbe a subword of W. As Cis a simple curve, h, l must be in one of the following three cases (see Figure 5): 1) h < p −1< p < l, 2) l⩽h < p −1< p, 3) p−1< p < l ⩽h. We shall show that in the three cases, the subword aap`pabof f Wyielded by the action of Σp,k satisfies a∈ {p−k, . . . , p −1} and b∈ {0, . . . , p −k−1} ∪ {p+ 1, . . . , n}, and thus a=b, as claimed. Figure 5. The possible cases of subwords ha(p−1) `palappearing in W, with the distinct possible moves of the point p. In the first two cases the arc (hap) will yield a=h+1 or a=p−k, satisfying a∈ {p−k, . . . , p−1}. In the third case we will also obtain a=p−k. On the other hand, in the first and third cases we have b=l(hence b > p); in the second case, either b=lif p−k⩾l+ 1 or b=p−k−1 otherwise (and b < p −k). This achieves the proof of the lemma.  We thus can associate to each isotopy class of curves [C] and each braid Σp,k the word W([C])Σp,k defined thanks to the above construction. We are now able to define, for each isotopy class of curves [C], the image of its associated reduced word W=W([C]) under the action of some positive braid x. Indeed, if xis expressed as a product x=∏r m=1 Σpm,km, then by Lemma 5, the inductive formula Wx= (W∏r−1 m=1 Σpm,km)Σpr,kr defines a word on Xwhich is the reduced word associated to [C]x(hence it does not depend on the chosen decomposition of xin terms of braids Σp,k). This can be written W([C]x) = W([C])x. DUAL GARSIDE STRUCTURE AND REDUCIBILITY OF BRAIDS 7 2.3. Proof of Theorem 1. By abuse of notation, instead of speaking about isotopy classes of simple closed curves, we will simply speak about curves, meaning that we are considering the reduced representatives. Consequently, the letter Cwill denote the reduced representative of the isotopy class of the curve Cand its associated reduced word will be denoted W(C). We introduce a class of curves which is larger than the class of round curves: Definition 6. A curve Cwill be called almost-round if the word W(C)(up to cyclic permutation of its letters and reversing) can be written as W(C) = w1w2, where the arcs in w1are oriented from left to right whereas those in w2are oriented from right to left. (See Figure 6). Figure 6. The curve in Part (a) is almost-round since its associated reduced word can be written as W=w1w2= (1 a4`6a9`10 a11)(`8a6`4a3`). The curve in Part (b) is not almost-round. The reduced words associated to almost-round curves satisfy the following necessary condition: Lemma 7. Let Cbe an almost-round, not round curve. Then W(C)(up to cyclic permutation and reversing) must contain a subword of the form iaj`lfor some 0⩽i < j < l ⩽n. Proof. The curve Chas a unique local minimum (and a unique local maximum) in the horizontal direction. Let ∗be this local minimum. Choose the clockwise orientation for C, and notice that the arcs oriented from left to right starting at ∗form a subword i1ai2. . . aik(ending with an upper arc, as Cis simple). If k >2, then i1ai2`i3satisfies the required hypothesis. If k= 2, choose the counterclockwise orientation. As Cis not round, W(C) must start with a subword i′ 1`i′ 2. . . `i′ kwith k⩾4 and i′ 2ai′ 3`i′ 4does the job.  Before proving Theorem 1, we introduce some more notation. We will say that some 0 < j < n is a bending point for (or bends) a curve Cif the reduced word W(C) admits (up to cyclic permutation of its letters and up to reverse) a subword of the form iaj`l, for some 0 ⩽i < j < l ⩽n. Lemma 7 thus asserts that an almost-round, not round curve admits at least one bending point. Given a simple braid s, and a bending point jfor some curve C,jwill be said to be compatible with sif the strands jand j+ 1 of sdo not cross in s. The following is the key for Theorem 1: Lemma 8. Let s1, s2be two simple braids such that s1·s2is in left normal form, and let Cbe a curve. Let jbe a bending point for C, compatible with s1. Then there exist some bending point j′ for Cs1, which is compatible with s2. In order to prove this lemma, we recall that simple braids are those positive braids in which any pair of strands crosses at most once (see [7]). We also recall the following well-known fact (see [11]): any simple braid scan be decomposed in a unique manner as a product s= n ∏ p=2 Σp,kp, where 0 ⩽kp< p and Σp,0= 1. This allows us to see sas a sequence of moves of the strands numbered from 2 to n(in this order), each of them getting kppositions to the left (the number kp depending on s). Notice that the pth strand of sdoes not cross (in s) any of the strands being to the left of the position p−kp. 8 MATTHIEU CALVEZ Proof of Lemma 8. As s1·s2is in left normal form, it is sufficient to show that there exist some bending point j′for Cs1such that the strands numbered j′and j′+1 at the end of s1do not cross in s1([7]). Let s1= ( j−1 ∏ p=2 Σp,kp)·Σj,kj·Σj+1,kj+1 ·( n ∏ p=j+2 Σp,kp) be the decomposition of s1in terms of the braids Σp,k. Acting on Cby s1following the above factorization, we will be able to find at each step a bending point ιfor the resulting curve such that the strands at respective positions ιand ι+ 1 at the end of this step have not yet crossed in s1. The first factor ∏j−1 p=2 Σp,kpinvolves moves of punctures which are to the left of j. Hence, due to Formulae (F1) and (F3) and Lemma 5, jis still a bending point for the resulting curve. Moreover strands ending at jand j+ 1 have not crossed in this first factor. The factor Σj,kjmoves the jth puncture to the left; once again due to Formulae (F1) and (F3) and Lemma 5, the resulting reduced word admits a subword i′aj`(with i′< j); jis still a bending point for the corresponding curve. Notice that the former jth puncture lies (now at position j−kj) under the arc i′ajand that strands ending at positions jand j+ 1 have not crossed. Then, the factor Σj+1,kj+1 moves the j+ 1st puncture to the left. As jwas a bending point for C, compatible with s1, the strands which started at positions jand j+ 1 do not cross in s1, hence this movement of the j+ 1st puncture cannot exceed the position j−kj: it ends at the diameter of the upper arc i′ajand by Formula (F4) and Lemma 5, the position ιj+1 := j−kj+1 is now a bending point for the resulting curve (see Figure 7). Moreover by construction the strands ending at ιj+1 and ιj+1 + 1 have not crossed in s1. Figure 7. The action of the braid Σj+1,kj+1 ; as the strands represented as bold crosses cannot cross, the point j+ 1 is “blocked” in its move to the left by the position j−kj. Finally, observe that for j+ 2 ⩽q⩽n, the movement of the qth puncture yields some bending point ιqfor the resulting curve: this is ιq=ιq−1+ 1 if this movement ends to the left of ιq−1and ιq=ιq−1otherwise. Thus j′:= ιnis a bending point of Cs1and strands numbered j′and j′+ 1 at the end of s1do not cross in s1by construction. This shows that the bending point j′of Cs1 is compatible with s2.2 We can now achieve the proof of Theorem 1. Recall that we consider a braid x= ∆px1. . . xrin left normal form which sends a round curve Cto another round curve C′=Cx. Since the braid ∆ corresponds to a rotation of Dn, the curve C∆tis round for all integers tand we may suppose, up to multiplication by ∆−p, that the left normal form of xis just x1. . . xr. In order to prove Theorem 1, it is sufficient to prove that the curve Cx1is round, since once this fact is proven, we are given a braid x2. . . xrin left normal form whose action transforms the round curve Cx1into the round curve C′, and the result follows by induction on the number of factors in the left normal DUAL GARSIDE STRUCTURE AND REDUCIBILITY OF BRAIDS 9 form of x. We shall give a proof by contradiction, assuming that the curve Cx1is not round. However it is almost round, as x1is a simple braid, see [18]. According to Lemma 7, there must exist a bending point j1for Cx1. Notice that punctures which lie above the curve Cx1come from strands which started to the right of Cat the beginning of x1 as well as punctures which lie below Cx1come from strands which started to the left of C. By Lemma 7, the puncture j1lies either below the curve Cx1or is enclosed by it whereas the puncture j1+ 1 lies either above, or is enclosed by Cx1. Moreover, at most one of them is enclosed by Cx1. This implies that the strands in positions j1and j1+ 1 at the end of x1do not cross in x1. In other words, j1is a bending point for Cx1compatible with x2(as x1·x2is in left normal form). Now, by induction on m= 1, . . . , r−1 and by Lemma 8, there exist j2, . . . , jr−1such that jmbends the curve Cx1...xmand is compatible with xm+1, for all m= 1, . . . , r −1. The proof of Lemma 8 also ensures that Cx1...xrhas a bending point jr. In particular we have shown that the curve Cx1...xr=Cxis not round, provided that Cx1is not round. This is a contradiction; therefore Cx1is round and Theorem 1 is shown. 3. The dual case, proof of Theorem 3 In this section we shall be interested in the dual (or BKL) Garside structure of the braid group [3]. We thus adopt the parametrization D∗ nof the n-times punctured disk defined in the Introduction. We shall associate to each isotopy class of simple closed curves [C] in D∗ n, a unique reduced word W([C]) to be defined in Subsection 3.1. Reduced words will be a tool for describing the action of dual positive braids on simple closed curves in D∗ nin Subsection 3.2. Finally, Theorem 3 will be proved in Subsection 3.3. 3.1. From curves in D∗ nto reduced words. As in the previous section, all the curves we are considering are nondegenerate, simple and closed. We shall speak about “curves” when we really mean “nondegenerate simple closed curves”. Notation : the circle of radius 1 2in D∗ ncentered at the origin will be denoted by Γ. Given i, j ∈ {1, . . . , n}, the move of the puncture iclockwise along Γ up to the position jdescribes an arc of Γ which we will denote by (i, j). The arc (i, i) is just the puncture i. Let Cbe a curve in D∗ n, and suppose that it has a finite number of crossings with the circle Γ, which are all transverse. We shall associate to Ca word W(C) that we now define. Choose a point ∗of Cwhich lies on the circle Γ and choose an orientation for C. Running along C following the chosen orientation, starting and ending at ∗, determines a word in the alphabet Y={`,x,y,,,1, . . . , n}as follows. Each arc through the inner component of D∗ n−Γ contributes a letter `to the word. Each intersection of Cwith the arc (i, i + 1) of Γ contributes a letter i. Finally arcs of Cthrough the outer component of D∗ n−Γ contribute a letter y, (xrespectively) if they are oriented clockwise (counterclockwise, respectively); except those as in Figure 8 (a) (thus having their endpoints in the same arc (i, i+ 1) of Γ) which contribute a letter or , in a a natural way according to their orientation. The number corresponding to the intersection point ∗can be chosen to be either at the beginning or at the end of the word. The word obtained in this way will be denoted by W(C) and we call it the word associated to C. Choosing another point ∗or putting the letter determined by ∗at the beginning or at the end of W(C) corresponds to a cyclic permutation of the letters in W(C), whereas choosing the reverse orientation of Cyields the reverse of W(C), exchanging with each other the letters yand x(and , respectively). Hence, words associated to curves are to be considered up to cyclic permutation of their letters and up to reverse, exchanging the orientation of outer arcs. 16 MATTHIEU CALVEZ under consideration are not periodic and the curves, simple, closed and nondegenerate, will be considered up to isotopy so that the term curve will be applied to the isotopy class of a curve. From Theorem 3, it follows that if a braid preserves a family of standard curves, then its cyclic sliding [13] also preserves a family of standard curves (see Proposition 4.2. and Corollary 4.3. in [17]). Therefore: Proposition 17. Let xbe a reducible braid. Then there exist some yin SCBKL(x)(the set of sliding circuits of x[13], with respect to the dual structure) which preserves a family of (pairwise disjoint) standard curves. The main result of this section asserts that this last condition, i.e. preserving a (non-empty) family of pairwise disjoint standard curves, is checkable in polynomial time. In fact, we shall prove: Theorem 18. There is an algorithm which decides whether a given n-strand braid xin dual left normal form x=δpx1. . . xℓadmits a standard invariant curve. Moreover this algorithm takes time O(ℓ·n4). Proof. Given a subset I0of {1, . . . , n}(of cardinality 2 ⩽#(I0)⩽n−1) and a braid xin dual left normal form x=δpx1. . . xℓ, the main task of the algorithm is to construct a bigger set S(I0, x) of punctures, which must be enclosed by the image under xof any standard curve Csurrounding punctures in I0, provided Cxis standard. This is achieved by the following, which is the key-result: Lemma 19. Suppose we are given a dual simple braid s, decomposed into pairwise disjoint polygons s=P1. . . Pg, together with a proper subset Iof {1, . . . , n}of cardinality at least 2, whose elements are enumerated p1, . . . , pkin this order (up to cyclic permutation) running along the circle Γclockwise (we will put pk+1 =p1). For each i= 1, . . . , k, consider all the polygons among P1, . . . , Pghaving at least one vertex, but not all, in (pi+ 1, pi+1 −1) and which does not have pi as a vertex, and take for each of them its leftmost vertex in the arc (pi+ 1, pi+1 −1). Let I′be the union of Iwith all punctures collected in the above way. If Cis a standard curve surrounding the punctures in I(and possibly other punctures) such that Csis standard, then Csurrounds the punctures in I′. Moreover, if I′=I, the standard curve whose set of inner punctures is exactly I is sent to a standard curve by s. Figure 14. An example that illustrates Lemma 19: here the simple braid sis decomposed as s=P1. . . P4, and Iis made of 4 points p1, p2, p3, p4. Then running along each arc (pi, pi+1) allows the construction of I′, which consists of adding punctures depicted as crosses to I. Proof. First observe that the image of a standard curve under sis standard if and only if the image of this curve under each of the Pi’s is standard (Remark 10). Now, for a polygon Qand a standard curve Coriented counterclockwise, according to Formulae (F′), the following are equivalent: DUAL GARSIDE STRUCTURE AND REDUCIBILITY OF BRAIDS 17 • CQis standard. •for each inner arc a`bof Cwhich is transverse to Q, the puncture bis a vertex of Q. Let Cbe a standard curve (oriented counterclockwise) surrounding the punctures in I, such that Cs is standard. The punctures in I′−I(that is the punctures added to Iby the process of Lemma 19) cannot lie in the outer component of D∗ n− C. Indeed, the belonging of such a puncture to the outer component of D∗ n− C would yield some inner arc a`bof C, transverse to a polygon in s not having bas a vertex; this would be in contradiction with the above remarks. See Figure 14. Now let CIbe the standard curve surrounding exactly the punctures in I(oriented counterclockwise) and suppose that the process of Lemma 19 yields I′=I. Then, whenever a polygon in s and an inner arc a`bof CIare transverse, the puncture bis a vertex of the involved polygon (otherwise some puncture in (b+ 1, a) would be added to Iby the process of Lemma 19). By the remark above, it follows that Cs Iis standard, as claimed.  The set I′of the above lemma depends only on Iand s, and we will denote by S(I, s) the set ρ(s)(I′) (where ρis the natural morphism Bn−→ Sn). Lemma 19 says that if Cis a standard curve surrounding the punctures in Iand Csis standard, then Csmust surround the punctures in S(I, s). Using Theorem 3 and an induction on the number of non-δfactors in the left normal form of xallows to construct the set S(I0, x). First, we set S(I0, δpx1) = S(ρ(δp)(I0), x1). Then we define, for i= 1, . . . , ℓ −1, S(I0, δpx1. . . xi+1) = S(S(I0, δpx1. . . xi), xi+1). Notice that the set S(I0, x) can be computed in time O(ℓ·n). Notice also that, in virtue of Lemma 19, the equality S(I, x) = Iimplies that the curve whose set of inner punctures is exactly I is x-invariant. The last step in the proof of Theorem 18 is the following: Proposition 20. Let a, b be any pair of punctures in {1, . . . , n}. There is an algorithm which decides whether a given n-braid xof length ℓadmits a standard invariant reduction curve surrounding the punctures aand b. Moreover this algorithm runs in time O(ℓ·n2). Proof. The algorithm does the following: •set I0={a, b}, •for m= 1, . . . , n −2, compute the set Im=S(Im−1, x)∪Im−1. Remark that Ii−1⊂Iifor all i. If In−2={1, . . . , n}, then the algorithm answers negatively; otherwise, the standard curve which surrounds exactly the punctures in In−2is x-invariant. Indeed, in the latter case, there must exist some k, 1 ⩽k < n −2, such that #(Ik) = #(Ik+1), and therefore Ik=Ik+1 =In−2. This means that S(Ik, x) = Ikand therefore the standard curve whose set of inner punctures is exactly In−2(and thus contains aand b) is x-invariant. The complexity of the algorithm is O(ℓ·n2), according to the above estimation about the computation of S(I0, x).  Iterating the above algorithm for each pair of points in {1, . . . , n}yields the algorithm in the statement of Theorem 18, since the number of pairs of points in {1, . . . , n}is n·(n−1) 2, so that the complexity of the whole algorithm is O(l·n4) as claimed.  We observe that this algorithm is the analogue of Theorem 2.9. in [18]. The result in [18] deals with the classical structure, but needs an additional hypothesis about the triviality of the “inner” braid; we believe that obtaining the same conclusion without this hypothesis could be an indication that the dual structure is more adapted for the kind of problems we are dealing with. The algorithm deciding the Nielsen-Thurston type of a given braid xis as follows: 18 MATTHIEU CALVEZ 1. Test whether xis periodic [2], and if it is so, return “periodic”, and stop. 2. Compute the set of sliding circuits (for the dual structure) of x[14]. 3. For each element yof SCBKL(x), for each k= 1, . . . , n 2, apply the algorithm of Theorem 18 to the braid yk(a curve belonging to a family fixed by ymust indeed be fixed by some power yk, with k= 1, . . . , n 2). 4. Stop whenever a positive answer is found, and return “reducible”; otherwise return “pseudo- Anosov”. The complexity of this algorithm is not bounded above by a polynomial in nand ℓsince the size of the set of sliding circuits is known to be exponential in general [13], [20]. References [1] D. Benardete, M. Gutierrez, Z. Nitecki, A combinatorial approach to reducibility of mapping classes, Contemp. Math. 150 (1993), 1-31. [2] J. S. Birman, V. Gebhardt, J. Gonz´alez-Meneses, Conjugacy in Garside groups III: Periodic braids, J. Alg. 316 (2007), 746-776. [3] J. Birman, K.H. Ko, S.J. Lee, A new approach to the word problem in the braid groups, Adv. Math. 139 (1998), 322-353. [4] J. S. Birman, A. Lubotzky, J. McCarthy, Abelian and solvable subgroups of the mapping class groups, Duke Math. 50 (1983), 1107-1120. [5] M. Calvez, B. Wiest, Fast algorithmic Nielsen-Thurston classification of four-strand braids, arXiv:1004.0067. [6] P. Dehornoy, L. Paris, Gaussian groups and Garside groups, two generalisations of Artin groups, Proc. London Math. Soc. (3) 79 (1999), 569-604. [7] E. ElRifai, H. Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser. (2) 45 (1994), 479-497. [8] D.B.A. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson, W. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. [9] A. Fathi, F. Laudenbach, V. Poenaru, Travaux de Thurston sur les surfaces, Ast´erisque 66-67, SMF 1991/1979. [10] G. Fenn, M. Greene, D. Rolfsen, C. Rourke, B. Wiest, Ordering the braid groups, Pacific J. Math. 191 (1999), 49-74. [11] P. de la Harpe, An invitation to Coxeter groups, in E. Ghys, A. Haefliger, A. Verjovsky, Group theory from a geometrical viewpoint, World Scientific, 1991. [12] F. Garside, The braid group and other groups, Quart. J. Math. Oxford Ser. (2) 20 (1969), 235-254. [13] V. Gebhardt, J. Gonz´alez-Meneses, The cyclic sliding operation in Garside groups, Mathematische Zeitschrift 265 (1), (2010), 85-114. [14] V. Gebhardt, J. Gonz´alez-Meneses, Solving the conjugacy problem in Garside groups by cyclic sliding, J. Symb. Comp. (6) 45 (2010), 629-656. [15] E. Godelle, Parabolic subgroups of Garside groups II: ribbons, J. Pure Appl. Algebra 214 (2010), 2044-2062. [16] E. Godelle, Personal communication. [17] J. Gonz´alez-Meneses, On reduction curves and Garside properties of braids, arXiv:1006.2258. [18] J. Gonz´alez-Meneses, B. Wiest, Reducible braids and Garside theory, arXiv:1008.0238. [19] E.K. Lee, S.J. Lee, A Garside theoretic approach to the reducibility problem in braid groups, J. Algebra 320 no. 2 (2008), 783-820. [20] M. V. Prasolov, Small braids having a big Ultra Summit Set, Mat. Zametki, 89 no. 4 (2011), 577-588. [21] W. Thurston, On the geometry and dynamics of diffeomorphisms of surfaces, B. Amer. Math. Soc. no. 19 (1988), 417-431.