On the structure of the centralizer of a braid

arXiv:math/0305156v2 [math.GT] 12 Sep 2003 On the structure of the centralizer of a braid Juan Gonz´ alez-Meneses1and Bert Wiest Dpto. de Matem´atica Aplicada I, E.T.S. Arquitectura, Universidad de Sevilla, Avda. Reina Mercedes, 2. 41012 Sevilla, Spain; [email protected] and IRMAR (UMR 6625 du CNRS), Universit´e de Rennes 1, Campus de Beaulieu, 35042 Rennes cedex, France; [email protected]niv-rennes1.fr Abstract The mixed braid groups are the subgroups of Artin braid groups whose elements preserve a given partition of the base points. We prove that the centralizer of any braid can be expressed in terms of semidirect and direct products of mixed braid groups. Then we construct a generating set of the centralizer of any braid on nstrands, which has at most k(k+1) 2 elements if n= 2k, and at most k(k+3) 2elements if n= 2k+ 1. These bounds are shown to be sharp, due to work of N.V.Ivanov and of S.J.Lee. Finally, we describe how one can explicitly compute this generating set. AMS Classification 20F36; 20E07, 20F65. Keywords braid, centralizer, Nielsen-Thurston theory. 1 Introduction and statement of the results In 1971, Makanin [25] gave an algorithm for computing a generating set of the centralizer Z(β) of any given element βof the n-string braid group Bn. His method, however, tends to yield very large, and highly redundant generating sets. One hint that much smaller generating sets could be found came from the experimental results of Gonz´alez-Meneses and Franco, which were obtained with a radically improved version of Makanin’s algorithm, based on new theoretical work [16]. Also, it has probably been clear to specialists for a long time that Nielsen-Thurston theory could be used to improve upon Makanin’s results. However, there seems to be no such result in the literature, and the aim of the present paper is to fill this gap. Although our main interest was to compute, for any given β∈Bn, a small generating set of Z(β), we succeed in describing this centralizer in terms of semidirect and direct products of mixed braid groups (see [26, 27]). These 1Partially supported by MCYT, BFM2001-3207 and FEDER. 1 groups are defined as follows: let X={P1,...,Pn}be the base points of the braids in Bn. Given a partition Pof X, the mixed braid group BPconsists of those braids whose associated permutation preserves each coset of P. The well known classification of mapping classes of a punctured surface into periodic, reducible and pseudo-Anosov ones, yields an analogous classification for braids. If βis reducible, then one can decompose it, in a certain sense, into atubular braid b β, and some interior braids β[1],...,β[t], all of them having less than nstands. The main result of this paper is the following: Theorem 1.1 Let β∈Bn. One has: (1) If βis pseudo-Anosov , then Z(β)≃Z2. (2) If βis periodic, then Z(β)is either Bnor isomorphic to a braid group on an annulus. (3) If βis reducible, then there exists a split exact sequence: 1−→ Z(β[1])× · · · × Z(β[t])−→ Z(β)−→ Z0(b β)−→ 1, where Z0(b β)is a subgroup of Z(b β), isomorphic either to Z2or to a mixed braid group. Notice that Z≃B2=B{{1,2}} , also Bn=B{{1,...,n}}, and finally the braid group over an annulus on kstrands is isomorphic to B{{1,...,k},{k+1}} ⊂Bk+1. Hence all these groups can be seen as mixed braid groups. Then, by recurrence on the number of strands we deduce the following: Corollary 1.2 For every β∈Bn, the centralizer Z(β)can be expressed in terms of semidirect and direct products of mixed braid groups. Using the above structure we shall construct, for any braid β∈Bn, a generating set of Z(β) having very few elements. More precisely, we obtain: Theorem 1.3 If β∈Bn, then the centralizer Z(β)can be generated by at most k(k+1) 2elements if n= 2k, and at most k(k+3) 2elements if n= 2k+ 1. We will present an example, communicated to us by S. J. Lee, showing that the above bound is sharp. That is, we will define, for every positive integer n, a braid in Bnwhose centralizer cannot be generated by less than k(k+1) 2elements if n= 2k, or less than k(k+3) 2elements if n= 2k+ 1. (The first to observe 2 that the number of generators of the centralizer may grow quadratically with the number of strands was N.V.Ivanov [21].) However, the above bound refers to the worst case, and one could be interested in the minimal number of generators of a particular braid. We shall give a generating set which is in some sense the smallest “natural” generating set for the centralizer of a braid. However, we shall also give an example that illustrates the difficulty of finding the absolutely minimum possible number of generators. Let us mention that, for the special case of reducible braids conjugated to a generator σi, its centralizer has already been described in [14]. The plan of the paper is as follows: in section 2 we set up notation and some standard machinery, and give the mentioned example by S. J. Lee. In section 3 we study Z(β) in the case where βis periodic, section 4 deals with the pseudo- Anosov case, and section 5 the reducible one, which is the most involved. In section 6 we define a generating set which is no larger than the stated upper bound. In section 7 we describe a generating set which is as small as possible while still reflecting the geometric structure of the Nielsen-Thurston decomposition. We also give an example to show that by algebraic trickery, even smaller sets can be obtained. Finally in section 8 we discuss how the generating set that we defined can be found algorithmically. 2 Prerequisites from Nielsen-Thurston theory We denote by Dthe closed disk of radius 2 centered at 0 in the complex plane. For any n∈N, the disk D, together with any choice of ndistinct points in its interior, is denoted Dn, and the distinguished points are called the punctures. We shall use different choices for the exact position of the punctures at different times - they may be lined up on the real axis, or regularly distributed on a circle of radius 1, or again one of them may be in the centre while the remaining n−1 are distributed over the circle of radius 1. In most instances, the position of the punctures is irrelevant, and we shall leave it unspecified. We recall that the braid group Bnis the group of isotopy classes of homeomorphisms fixing (pointwise) the boundary and permuting the punctures of Dn. Here the isotopies must fix pointwise the boundary and the punctures. Alternatively, Bncould be defined as the group of isotopy classes of disjoint movements of the punctures, starting and ending with the configuration of Dn. Yet another definition of Bnis as the set of isotopy classes of braids with n strings in the cylinder D×[0,1], where the start and end points of the strings 3 are exactly the puncture points in Dn× {0}and Dn× {1}. We shall use all three points of view. We shall often work with a certain quotient of the group Bn, rather than with Bnitself. We recall that the center of Bnis isomorphic to the integers, and generated by the full twist ∆2(where ∆ is Garside’s half twist). Geometrically, the group projection Bn→Bn/h∆2iis given by smashing the boundary curve of Dnto a puncture, so that Bn/h∆2iis naturally a subgroup of the mapping class group of the sphere with n+ 1 punctures. In order to keep notation manageable, we shall use the same letters for elements of the braid group Bn and for their image in the quotient Bn/h∆2i. This abuse of notation should not cause confusion. We say that an element β∈Bnis periodic if the element of Bn/h∆2irepre- sented by βis of finite order. Equivalently, βis periodic if there exists a k∈N such that in Bnwe have that βkis equal to some power of ∆2. We say an element βof Bnis reducible if there exists a nonempty multicurve Cin Dn(i.e. a system of disjoint simple closed curves in Dn, none of them isotopic to the boundary or enclosing a single puncture) which is stabilized by β, i.e. such that β(C) is isotopic to C. Note that βmay permute different components of the multicurve C. The following definition is taken from [8] (see also [20]). To every reducible braid β∈Bnone can associate a canonical invariant multicurve: its canonical reduction system, which by definition is the collection of all isotopy classes c of simple closed curves which have the following two properties: firstly, cmust be stabilized by some power of β, and secondly any simple closed curve which has non-zero geometric intersection number with cmust not be stabilized by any power of β. For instance, let us consider the punctured disk D6, where the 6 punctures are arranged uniformly on the circle of radius 1 around 0. Then the rotation of the punctures around the circle by an angle of 2π 3is a periodic element of B6(of period 3), it is also reducible (e.g. the three simple closed curves encircling punctures 1 and 2, 3 and 4, and 5 and 6 respectively form an invariant multicurve), but its canonical reduction system is empty. This example, however, is somewhat untypical: if a non-periodic braid is reducible, then its canonical reduction system is nonempty (see [20]). If Cis an invariant multicurve of a reducible braid β, then we define the tubular braid induced by βand Cto be the braid on fewer strings obtained from β by removing from Dnall the disks bounded by outermost curves of C, and collapsing each outermost curve of Cto a puncture point. It should be stressed that this braid is only defined up to conjugacy. 4 An alternative way to look at the same defintion is the following: let us consider again βas an isotopy class of ndisjoint strings in D×[0,1] with extremal points at the puncture points of Dn× {0}and Dn× {1}, such that each disk D× {t}intersects each string exactly once. Now our picture can be completed by embedded cylinders in D×[0,1] which are disjoint from each other and from the strings of the braid, each of which intersects each disk D× {t}in exactly one circle, and whose boundary components are exactly the outermost curves of Cin D×{0}and D×{1}. We can interpret the solid cylinders bounded by these cylinders as “fat strings”, and the resulting braid with some fat strings is exactly the tubular braid defined above. The interior braids induced by βand Care the braids on fewer strings induced by βat the interior of the discs bounded by the outermost curves of C. They can be thought of as the braids ‘inside’ the tubes of the tubular braid. Therefore, for every reducible braid β, and every invariant multicurve C, we can decompose βinto one tubular braid and some interior braids – as many as the number of outermost curves in C. Finally, we have the notion of a pseudo-Anosov element of Bn, for which we refer to [13] or [20]. Roughly speaking, β∈Bnis pseudo-Anosov if it is represented by a homeomorphism of Dnwhich preserves two transverse measured foliations on Dn(called the “stable” and the “unstable” foliation), while scaling the measure of the unstable one by some factor λwhich is greater than 1, and the measure of the stable one by 1 λ. Thurston’s theorem [32, 13] states that every irreducible element of Bnis either periodic or pseudo-Anosov. We end this section with the promised example, due to S. J. Lee, that should be helpful for understanding the relationship between the Nielsen-Thurston decomposition and the centralizer subgroup of a braid β∈Bn. This example was also found independently by N. V. Ivanov and H. Hamidi-Tehrani [22]. Example 2.1 Suppose that n= 2m, and denote by σithe standard generator of Bn, in which the ith and the (i+ 1)st punctures permute their positions in a clockwise sense. We define β=σ1σ2 3σ3 5···σm 2m−1. The canonical reduction system of βconsists of mcircles, the ith one enclosing the punctures 2i−1 and 2i. The corresponding tubular braid is the trivial braid of Bm, and the interior braids are, respectively, σ1,σ2 1, . . . , σm 1(notice that all of them are non-conjugate, since conjugate braids have the same exponent sum). 5 Let D(1),...,D(m)be the disks bounded by the above circles. As we shall see, any braid that commutes with βhas to send each disk D(i)to itself (since the interior braids are non-conjugate). A generating set of the centralizer subgroup of βis given by (i) for each i∈ {1,...,m}, the braid σ2i−1, whose support is contained in D(i), (ii) any generating set for the pure braid group on mstrings Pm– all the generators here act as the identity on D(1) ∪...∪D(m), and can be seen as a pure tubular braid on mstrings (tubes), where the ith tube starts and ends at D(i). It can be easily shown that, in this case, Z(β)≃Zm×Pm. The essential observation now is the following: it can be deduced by the presentation given in [6], that the abelianization of Pmis isomorphic to Zm(m−1)/2(see also [1]). Hence, the abelianization of Z(β) is isomorphic to Zm×Zm(m−1)/2. Therefore, at least m+m(m−1) 2=m(m+1) 2generators are needed for the centralizer of the braid β. The case when n= 2m+ 1 is analogous. The braid proposed by S. J. Lee is: β=σ2σ2 4σ3 6···σm 2m. This time the first strand is not enclosed by any curve of the canonical reduction system of β, and one has: Z(β)≃Zm×Pm+1 . Hence, in this case the minimal possible number of generators is m+m(m+1) 2=m(m+3) 2. By proving theorem 1.3, we will show that the above examples are the worst one can find. 3 The periodic case We have to start by describing the periodic elements of Bn. In order to state this classification result, which is classical, we need to define two braids. If Dnis the disk with npunctures arranged regularly on the circle of radius 1, then the braid which we shall call δ(n)is represented by a clockwise movement of all punctures on this circle by an angle 2π n. If no confusion is possible, we shall simply write δ, without indicating the number of strands (note that this braid is the Garside element of the Birman-Ko-Lee structure of Bn[7]). Similarly, if we think of Dnas having one puncture in the centre, and n−1 punctures arranged circularly around it, then we define γ(n)∈Bnto be the braid given by a circular movement of the n−1 punctures by an angle of 2π n−1, 6 while leaving the central puncture fixed. Again, for simplicity we shall often only write γinstead of γ(n). The result that classifies periodic braids, which is due to Eilenberg [11] and de Ker´ekj´art´o [23] (see [10] for a modern exposition) is: Lemma 3.1 Every periodic braid in Bnis conjugate to a power of δ(n)or γ(n). Thus we only need to consider the centralizer subgroups of δk (n)and γk (n)for all n, k ∈Z, since the centralizers of conjugate elements are isomorphic by an inner automorphism of Bn. This problem has been solved by Bessis, Digne and Michel [4], on the wider context of complex reflexion groups. We shall explain their result in the particular case of braid groups: We suppose first that β=δk (n)where, without loss of generality, k⩾0. Let d= gcd(n, k). For u= 1,...,n, we will denote Pu=ei2πu/n the punctures of Dn, so β=δk (n)sends Puto Pu+kfor every u(the indices are taken modulo n). Hence the permutation induced by βhas dorbits (cycles) of length r=n d, that we denote by C1,...,Cd. See in figure 1 an example where n= 12, k= 9, d= 3 and r= 4: the braid δ(12) and the three orbits of δ9 (12) . Figure 1: The braid δ∈B12 , and the three orbits of δ9(in black, white and grey). If r > 1 (that is if d < n), consider the once punctured disc D∗=D\{0}, and the r−sheeted covering θ=θr:D∗→D∗defined by θ(aeit) = aeitr = aeitn/d . The orbits C1,...,Cdare sent by θto the points Q1,...,Qd, where Qu=ei2πu/d . If we consider the half-line L={aeiπ/d, a ∈]0,2]}(notice that Lpasses between Qdand Q1), then D∗\Lis a fundamental region for θ(see figure 2). 7 Figure 2: The covering map θ=θ4associated to δ9 (12) . Now notice that every braid in Bd(D∗) can be lifted, by θ−1, to a braid in Bnin a natural way. The resulting braid is a 2πd n-symmetric braid, that is, it is invariant under a rotation by an angle of 2πd n. But then it is also invariant under a rotation of angle 2πk n; in other words, the resulting braid commutes with β. Hence we have a natural homomorphism: θ∗:Bd(D∗)→Bnwhose image is contained in Z(β). Then one has Theorem 3.2 ([4]) The natural homomorphism θ∗:Bd(D∗)→Z(δk (n))is an isomorphism. In other words, every element in the centralizer of β=δk (n)can be seen (via θ) as a braid on a once punctured disc, that is, a braid on an annulus. Notice that if r= 1 (that is, if kis a multiple of n), then βis a power of δn (n)= ∆2 (n). In this case θis the identity map, and the fundamental region is the whole Dn. Hence the centralizer of βis the whole Bn, as one should expect. Since we are interested in minimising the set of generators, we observe that if d=n(thus r= 1), then Z(β) = Bnis generated by two elements, namely Artin’s σ1and Birman-Ko-Lee’s δ. In a similar way, if 1 < d < n, then the braid group Bd(D∗) is generated by just two elements, namely δ(n)=θ∗(δ(d)) and the braid θ∗(σ1) shown in figure 3(a). Notice that this case contains the above one, where θ∗is the identity. Finally, if d= 1 then B1(D∗) is cyclic. Thus we have: Proposition 3.3 If kand nare coprime, then Z(δk (n))is generated by a single element, namely δ(n). If, by contrast, gcd(k, n)⩾2, then Z(δk (n))is generated by two elements: δ(n)and the braid θ∗(σ1). 8 Figure 3: Generators θ∗ 3(σ1) and ¯ θ∗ 3(σ1) of the centralisers of δ4 (12) and γ4 (13) . It is clear that the generating set given by proposition 3.3 is indeed minimal. Next we study the centralizer of β=γk (n), still following the work in [4]. This time we call d= gcd(n−1, k), and r= (n−1)/d. If d < n −1, the above map θinduces a natural homomorphism ¯ θ∗=¯ θ∗ r:Bd(D∗)→Bn, where this time the central point of Dis considered as a puncture. Hence, the central strand of every braid coming from Bd(D∗) is trivial. We observe that the image of this homomorphism is contained in Z(β), and in fact one has: Theorem 3.4 ([4]) The natural homomorphism ¯ θ∗ r:Bd(D∗)→Z(γk (n))is an isomorphism. By contrast, if d=n−1, then βis a power of γn−1= ∆2, so θ∗ r= 1, Z(β) = Bn and everything works as above. Hence we have Proposition 3.5 If kand n−1are coprime, then Z(γk (n))is generated by a single element, namely γ(n). If, by contrast, gcd(k, n−1) = d⩾2, then Z(γk (n)) is generated by two elements: γ(n)=¯ θ∗(δ(d))and the braid ¯ θ∗(σ1). See figure 3(b) for an illustration of the braid ¯ θ∗(σ1). We summarize all the results in this section as follows: Corollary 3.6 The centralizer of any periodic braid in Bneither equals Bn or is isomorphic to Bd(D∗), for some d < n. In particular, it can be generated by at most two elements. We end with a result that will be helpful later: Corollary 3.7 If kis not a multiple of n, then Z(δk (n))∼ =Z(γk (n+1)). 9 Figure 7: How to move β[i]from Ci,4to Ci,2, when ri= 4. 5.2 Centralizer of a braid in regular form We will now study the centralizer of β, assuming that βis in regular form. Recall that the only non-trivial interior braids of βare denoted β[1],...,β[t], and that b βis the tubular braid associated to βand R(β). In this section we will show that there is an exact sequence: 1→Z(β[1])× · · · × Z(β[t])g −→ Z(β)p −→ Z0(b β)→1, where Z0(b β) is a subgroup of Z(b β). Later on we will see that this sequence splits. For i∈ {1,...,t}, consider the centralizer Z(β[i]) in Bmi. We define a map gi:Z(β[i])→BR(β)as follows: given γ∈Z(β[i]), gi(γ) is the braid α∈BR(β) satisfying bα= 1, αj,k = 1 for j6=i, and αi,k =γfor k= 1,...,ri. We need to show the following: Proposition 5.2 The map gidefined above is an injective homomorphism, and its image is contained in Z(β). Proof The map giis given by the diagonal homomorphism Z(β[i])→Z(β[i])× ...×Z(β[i]) (rifactors), followed by the homomorphism induced by an inclusion of ricopies of an mi-times punctured disk into ridisjoint subdisks (each containing mipunctures) of Dn. By the results of [28] we can deduce that gi is indeed an injective homomorphism. It remains to show that for every γ∈Z(β[i]) one has α=gi(γ)∈Z(β). Since bαis trivial, \ α−1βα =bα−1b βbα=b β. So we just need to show that the interior braids of α−1βα and βcoincide. For j6=i, the braids αj,k are trivial for every k, so α−1βαj,k =βj,k . Now, for k6=ri, one has α−1βαi,k = 16 α−1 i,k βi,k αi,k+1 =γ−11γ= 1 = βi,k . Finally, since γcommutes with β[i], one has α−1βαi,ri=α−1 i,riβi,riαi,1=γ−1β[i]γ=β[i]=βi,ri. Therefore α−1βα =β, so the image of giis contained in Z(β). Proposition 5.3 The map g:Z(β[1])× · · · × Z(β[t])−→ Z(β)defined by g(γ1,...,γt) = g1(γ1)···gt(γt)is an injective homomorphism. Proof Given γ∈Z(β[i]), the only nontrivial strands in gi(γ) are those inside the tubes Ci,1,...,Ci,ri. Hence if i6=j,γ∈Z(β[i]) and δ∈Z(β[j]), then gi(γ) and gj(δ) commute. Since every giis a homomorphism, this shows that gis also a homomorphism. But we know by the previous proposition that giis injective for i= 1,...,t. Using an argument similar to the proof of proposition 5.2, one can deduce that gis also injective. Now we will relate Z(β) and Z(b β). Every braid in Z(β) preserves the canonical reduction system of β(see [20]), so it must preserve R(β). That is, Z(β)⊂ BR(β). Let p:BR(β)→Bmbe the homomorphism which sends αto bα, the tubular braid induced by αand R(β). If we take α∈Z(β) then β=α−1βα, so p(β) = p(α−1βα) = p(α)−1p(β)p(α). Hence p(α) commutes with p(β) = b β. Therefore, if we restrict pto Z(β) we get p:Z(β)→Z(b β). Unfortunately, neither p:BR(β)→Bmnor its restriction p:Z(β)→Z(b β) are surjective, but we shall see that the elements in the image of pin either case can be easily characterised by the permutation they induce. Notice that pinduces a bijection epfrom R(β) to {P1,...,Pm}, the punctures of Dm. We denote by τthe inverse of ep. Definition 5.4 Let η∈Bm, and let πηbe the permutation induced by η on the punctures of Dm. We say that πηis consistent with R(β)if, for i= 1,...,m,τ(Pi)and τ(πη(Pi)) enclose the same number of punctures. Proposition 5.5 An element η∈Bmis in the image of p:BR(β)→Bmif and only if πηis consistent with R(β). Proof If ηis in the image of p, let α∈BR(β)with p(α) = η. Then, for every i= 1,...,m,τ(Pi) and τ(πη(Pi)) are the top and bottom circles of a tube determined by α. Hence they must enclose the same number of punctures (the number of strands inside the tube). Conversely, suppose that πηis consistent with R(β). Take i∈ {1,...,m}and suppose that τ(Pi) = Cj,k . Then take the ith strand of ηand consider it as a 17 tube, enclosing the trivial braid on mjstrands. Do this for every i= 1,...,m. The resulting braid, ψ(η), is well defined since πηis consistent with R(β), and it belongs to BR(β). Moreover, p(ψ(η)) = ηby construction. The homomorphism ψintroduced in this proof will play a prominent rˆole in what follows: if η∈Bm, then ψ(η) is the braid in BR(β)whose tubular braid equals η, and whose interior braids are all trivial. All the elements in Bmthat shall be considered from now on will have permutations consistent with R(β). Hence, by abuse of notation, we will identify Ci,k =ep(Ci,k) and Ci=ep(Ci) if it does not lead to confusion. We still need to characterise the elements in the image of p:Z(β)→Z(b β). We just know that their permutations must be consistent with R(β), but this is not sufficient. Recall that the permutation induced by βon the components of R(β) has torbits, C1,...Ct. The key observation now is that every element α∈Z(β) preserves these orbits setwise, though it could permute them. Therefore, for i= 1,...,t, one has α(Ci) = Cjfor some j. In the same way, for any η∈Z(b β) one has α(Ci) = Cjfor some j. Lemma 5.6 Let α∈Z(β). If α(Ci) = Cjfor some i, j ∈ {1,...,t}, then β[i]=β[j]. Proof Since α(Ci) = Cj, the two orbits have the same length, which we shall denote r; thus r=ri=rj. Now βris a braid that preserves Ci,k and Cj,k for every k, and is such that (βr)i,k =β[i]and (βr)j,k =β[j]. Now since α commutes with β, then it also commutes with βr. Suppose that αsends Ci,1to Cj,k . Then β[j]= (βr)j,k = (α−1βrα)j,k = (αi,1)−1(βr)i,1αi,1= (αi,1)−1β[i]αi,1. Therefore β[i]and β[j]are conjugate, and since βis in regular form, β[i]=β[j], as we wanted to prove. Lemma 5.6 imposes another condition for a braid in Z(b β) to be in p(Z(β)): Definition 5.7 Let η∈Z(b β). We say that πηis consistent with βif it is consistent with R(β)and, furthermore, for every i, j ∈ {1,...,t}such that η(Ci) = Cj, one has β[i]=β[j]. Definition 5.8 Z0(b β)is the subgroup of Z(b β)consisting of those elements whose permutation is consistent with β. 18 Then lemma 5.6 can be restated as follows: If α∈Z(β) then p(α)∈Z0(b β). Moreover, we can prove the following: Proposition 5.9 The homomorphism p:Z(β)−→ Z0(b β)is surjective. Proof Let η∈Z0(b β). We shall construct a preimage of ηunder pin two steps. Since πηis consistent with β(thus with R(β)), we can, as a first step, consider the braid ψ(η)∈Bn. We then have p(ψ(η)) = η; but ψ(η) does not necessarily commute with β, since the interior braids of ψ(η)−1βψ(η) could differ from those of β. Actually, since the interior braids of ψ(η) are all trivial, conjugating βby ψ(η) just permutes the interior braids of β. More precisely, the braid ψ(η)−1βψ(η) equals β, except that, for each i∈ {1,...,t}, it may not be the tube Ci,riwhich contains the nontrivial interior braid β[i], but some other tube from the family Ci. Our aim in the second step is thus to fill the tubes of ψ(η) with more suitable interior braids, in order to obtain a braid that commutes with β. For every i∈ {1,...,t}, we know that ψ(η) sends Cito some Cj. Let ki∈ {1,...,ri}be such that ψ(η) sends Ci,kito Cj,rj, and consider the braid µ(i, ki) defined at the end of Subsection 5.1. If we conjugate βby µ(i, ki) we move β[i] from Ci,rito Ci,ki. If we further conjugate by ψ(η), then β[i]goes to Cj,rj. But ηis consistent with β, so β[i]=β[j]. Hence, the interior braids in Cjare preserved. We can do this for i= 1,...,t, so we obtain that the braid t Y i=1 µ(i, ki)!ψ(η) commutes with βand its tubular braid is η, so it is in p−1(η)∩Z(β). This shows the result. We can finally bring together all the results in this section to state the following: Theorem 5.10 Let β∈Bnbe a non-periodic reducible braid in regular form. Then the sequence 1→Z(β[1])× · · · × Z(β[t])g −→ Z(β)p −→ Z0(b β)→1 is exact. Proof By proposition 5.3 gis injective, and by proposition 5.9 pis surjective. It just remains to show that im(g) = ker(p). 19 By construction, every element in the image of ginduces a trivial tubular braid, so im(g)⊂ker(p). Let then α∈ker(p), that is, bα= 1. Since α∈Z(β), we have α−1βα =β, and since βi,k = 1 for k6=ri, we must have α−1 i,k 1αi,k+1 = 1, so αi,k =αi,k+1 for k= 1,...,ri−1. Hence αi,1=αi,2=· · · =αi,rifor every i. Moreover, we have β[i]=βi,ri=α−1 i,riβi,riαi,1=α−1 i,1β[i]αi,1, so αi,1∈Z(β[i]). Therefore, α=g1(α1,1)g2(α2,1)···gt(αt,1) = g(α1,1, α2,1, . . . , αt,1). That is, ker(p)⊂im(g). 5.3 Finding a section for p In this subsection we will prove that the exact sequence of theorem 5.10 splits. We recall that b βis obtained from βby collapsing the disks bounded by outermost curves in the canonical reduction system of βto single punctures. In particular, the canonical reduction system of b βmust be empty. Hence, b βis either periodic or pseudo-Anosov. We will distinguish these two cases, to define a multiplicative section for p, but first we will show an easy particular case. Recall that a braid is pure if it induces the trivial permutation of its base points. Proposition 5.11 If b βis pure, there is a homomorphism h:Z0(b β)→Z(β) such that p◦h= 1. Proof We shall prove that in this case, the homomorphism ψconstructed in the proof of proposition 5.5 is such a section. Let η∈Z0(b β). Since b βis pure, Ci={Ci,1}for all i. Hence, if ηsends Cito Cjthen it sends the tube Ci,1 (containing β[i]) to the tube Cj,1(containing β[j]=β[i], since βis in regular form). Therefore, filling every tube in ηwith the trivial braid, that is, defining h(η) = ψ(η), yields indeed an element of Z(β). Next we study the general case, depending whether b βis periodic or pseudo- Anosov. Proposition 5.12 If b βis periodic, there is a homomorphism h:Z0(b β)→Z(β) such that p◦h= 1. Proof Recall that we are studying βup to conjugacy. This implies that we can also study b βup to conjugacy since, for every ξ∈Bm, if we conjugate β by ψ(ξ) we are conjugating b βby ξ. Moreover, after conjugating by ψ(ξ), β continues to be in regular form (up to renaming the circles in R(β)). Therefore 20 we can suppose, up to conjugacy, that b βis a rigid rotation of the disc, that is, a power of δ(m)or γ(m). Suppose first that b β=δk (m)for some k. We can suppose that kis not a multiple of m, since in that case b βwould be a power of ∆2 (m), thus it would be pure, and this case has already been studied in proposition 5.11. Recall the analysis of periodic braids in section 3: the base points Q1,...,Qmof b βwill be evenly distributed along a circle of radius 1 around 0. Let d= gcd(m, k)< m and r=m/d. Then b βsends Qito Qi+k, and there are dorbits C1,...,Cdof length r. The orbit Ciwill contain the points Quwhere u≡i(mod d). Since we can choose which tubes of βcontain the interior braids, we will suppose that these are the tubes starting at Qm−d+1, Qm−d+2,...,Qm, that is, the last dpoints of Dm. We will consider now some line segments in Dwhich separate the points Q1,...,Qminto rsets of dpoints. Let Lbe the line segment joining the origin with the border of D, passing between the points Qm−dand Qm−d+1 , and let L′be the segment passing between Qmand Q1. Notice that Land L′determine a sector which contains the points Qm−d+1, . . . , Qm, corresponding to the tubes of βwith nontrivial interior braids. Let ϕ:C→Cbe the rotation around the origin by an angle of 2πk/m (the angle induced by b β), and denote Li=ϕi(L). Since gcd(m, k) = d, the segments L0,...,Lr−1 divide Dinto m/d =rsectors, each one of angle 2π/r and containing the points Qid+1,...,Qid+dfor some i. Take the smallest integer e > 0 such that ϕe(L) = L′. Then one has L0=Land Le=L′. We are interested in the union of segments L=L1∪L2∪ · · · ∪ Le(see figure 8 for an example). Figure 8: The segments L,L′, and the union of segments L, for b β=δ6∈B15 . Let then η∈Z0(b β). In order to define h(η), it suffices to define its interior braids. This is done as follows: recall that, since ηcommutes with b β, it can be isotoped to a symmetric braid (with respect to the rotation ϕ), so we take a symmetric representative of η. For every base point Qiof b β(corresponding 21 to a circle Cj,u ), consider the strand of ηstarting at Qi(the ith strand of η). Then we define the interior braid h(η)j,u = (β[j])L(η,i), where L(η, i)∈Z is the algebraic number of times that the ith strand of ηcrosses L. This is well defined by theorem 3.2 (if you take two distinct representatives of ηas a symmetric braid, they are isotopic through symmetric braids, so the strands never touch the origin and the intersection number L(η, i) is preserved). In other words, we define h(η) as follows: we start with trivial interior braids, and we follow the movement of the strands of η. Each time a strand crosses a segment of Lin the positive sense, we multiply its interior braid by β[j](where jis the index of the orbit Cjof that strand). And every time a strand crosses Lin the negative sense, we multiply its interior braid by β−1 [j]. We have thus defined a map h:Z0(b β)→BR(β). To show that his a homomorphism, it suffices to see that the interior braids of ηξ are the product of those of ηand ξ, for η, ξ ∈Z0(b β). Suppose that the ith strand of ηgoes from Qi(corresponding to Cj,u ) to Qi′(corresponding to Cj′,u′). Hence η sends Cjto Cj′, and since η∈Z0(b β), it follows that β[j]=β[j′]. One also has, by definition, L(ηξ, i) = L(η, i) + L(ξ, i′). Therefore (ηξ)j,u = (β[j])L(ηξ,i)= (β[j])L(η,i)(β[j])L(ξ,i′)=ηj,uξj′,u′, so his a homomorphism. We must finally show that, with this definition, h(η)∈Z(β), for every η∈ Z0(b β). We will define first some special braids. For every i, j ∈ {1,...,d} such that i < j and β[i]=β[j], define the symmetric braid Si,j =Sj,i = θ∗ r(σi···σj−2σj−1σj−2···σi) (see figure 3 in section 3 to recall the definition of θ∗ r, and figure 9 here for an example). The braid Si,j commutes with b β(since it is symmetric), and it permutes the orbits Ciand Cj, preserving the others. Hence Si,j ∈Z0(b β). Moreover, its strands do not cross L, so by definition of h one has h(Si,j) = ψ(Si,j) (the interior braids are trivial). Figure 9: The braid S1,3, for b β=δ6∈B15 (assuming that β[1] =β[3] ). But h(Si,j) commutes with β, since the only tubes it permutes are those of 22 the orbits Ciand Cj; among these tubes, the only two with non-trivial interior braids are exchanged, and their corresponding interior braids are equal (β[i]= β[j]). Hence the interior braids of βare preserved by ψ(Si,j) = h(Si,j), so h(Si,j)∈Z(β). Take then an arbitrary η∈Z0(b β). We must show that h(η)∈Z(β). Suppose that ηsends Cito Cjfor some i, j. Then β[i]=β[j], so Si,j is defined, and the braid ηSi,j preserves the orbit Ci. We can continue this way, until we obtain a braid ηSi1,j1···Sik,jkthat commutes with b βand preserves every orbit Ci, for i= 1,...,d. Since h(Si,j)∈Z(β) for every i, j, and his a homomorphism, in order to show that h(η)∈Z(β) it suffices to show that h(ηSi1,j1···Sik,jk)∈ Z(β). Therefore, we can suppose that ηpreserves every orbit Ci. Denote α=h(η). We need to show that the interior braids of α−1βα coincide with those of β. Since ηpreserves all orbits, we will consider just the tubes of C1, the other ones being analogous. Suppose that αsends the circle C1,u to C1,r . Then it must send C1,v to C1,v−ufor every v(the indices are taken modulo r). We will identify the points Q1,...,Qmwith their corresponding circles Ci,v . For every v= 1,...,r, let bvbe the strand of ηstarting at C1,v . Since η is symmetric, we have ϕ(bv) = bv+1 . Suppose that bvcrosses ttimes the segment Li, where i∈ {0,...,r−1}. Then bv+1 will cross ttimes the segment ϕ(Li) = Li+1 . Therefore, if bvcrosses ltimes L, and if it crosses l0times L0 and letimes Le, then bv+1 crosses l−le+l0times L. If v6=rand v6=u, then bvneither starts nor ends at C1,r . Then it crosses L0 and Lethe same number of times. Hence, bvand bv+1 cross Lthe same number of times, say l. Therefore, if v6=r, u, one has (α−1βα)1,v−u= (α1,v)−1β1,vα1,v+1 =β−l [1] 1βl [1] = 1 = β1,v−u. If u=v=r, then bvstarts at ends at C1,r . Hence, as above, it crosses L0 and Lethe same number of times, so bv=brand bv+1 =b1cross Lthe same number of times, say l. We then have (α−1βα)1,v−u= (α−1βα)1,r = (α1,r)−1β1,rα1,1=β−l [1] β[1]βl [1] =β[1] =β1,r =β1,v−u. Hence, if u=r, we have already seen all the possible cases. We will then suppose that u6=r. If v=r, then bvstarts (but does not end) at C1,r . Hence, it crosses Leone more time (in the positive sense) than it crosses L0. Therefore, if bv=brcrosses ltimes L, then bv+1 =b1crosses it l−1 times. One has: (α−1βα)1,v−u= (α−1βα)1,r−u= (α1,r)−1β1,rα1,1=β−l [1] β[1]βl−1 [1] = 1 = β1,r−u=β1,v−u. Finally, if v=uthen bvends (but does not start) at C1,r . In this case, it crosses Leone less time (in the positive sense) than it crosses L0. Hence, if 23 bv=bucrosses ltimes L, then bv+1 =bu+1 crosses it l+ 1 times. One then has: (α−1βα)1,v−u= (α−1βα)1,r = (α1,u)−1β1,uα1,u+1 =β−l [1] 1βl+1 [1] =β[1] = β1,r =β1,v−u. Therefore, in every possible case we have (α−1βα)1,v−u=β1,v−u, for every v. This means that the interior braids of (α−1βα) and of βcoincide, that is, α=h(η) commutes with β, as we wanted to show. This completes the proof of proposition 5.12 in the case b β=δk (m), and it only remains to deal with the case when b β=γk (m). As above, we can suppose that kis not a multiple of m−1, since in that case b βwould be pure, and this case has already been treated in proposition 5.11. Hence, the only fixed point in the permutation induced by b βis the origin. Therefore, every ηcommuting with b βmust fix the origin. This means that, for every η∈Z0(b β), we can fill its central tube with the trivial braid, and the other tubes in the same way as above (defining L, and counting the number of times each strand crosses L). This defines a homomorphism h:Z0(b β)→Z(β) which is a section of p. The proof is the same as above. It remains to study the case when b βis pseudo-Anosov. Proposition 5.13 If b βis pseudo-Anosov, then there is a homomorphism h:Z0(b β)→Z(β)such that p◦h= 1. Proof In this case, we know that Z(b β) is a free abelian group of rank 2, generated by a pseudo-Anosov and a periodic braid. Hence, Z0(b β) is an abelian group of rank one or two. Notice that ∆2 (m)∈Z0(b β), because this braid commutes with b βand because π∆2is trivial, and thus consistent with β. Hence Z0(b β) contains at least one periodic element. On the other hand, b βbelongs itself to Z0(b β), since πb βis clearly consistent with β. Hence in Z0(b β) there are also pseudo-Anosov braids. Since all powers of a periodic braid are periodic, and all powers of a pseudo-Anosov braid are pseudo-Anosov, it follows that Z0(b β) has in fact rank two. More precisely, Z0(b β) = hηi × hρi, where ηis pseudo-Anosov and ρis periodic. In particular, we have b β∈ hηi × hρi, and the three braids b β,ηand ρare mutually commuting. Our aim is to define two commuting braids h(ρ) and h(η) in Z(β) which are preimages of ρrespectively ηunder p. The definition of h(ρ) is very simple: we take an arbitrary preimage of ρunder p– this is possible since pis surjective by proposition 5.9. It remains to construct h(η). 24 Lemma 5.14 Suppose α∈BR(β), that is, the braid αpreserves the set of outermost curves in the canonical reduction system of β. Suppose also that µ, ν ∈Z(bα). Suppose that ιµ∈BR(β)is a braid with trivial tubes (i.e. bιµ= 1) such that ψ(µ)·ιµ∈Z(α). Finally, suppose that µand νinduce the same permutation. Then we have as well that ψ(ν)·ιµ∈Z(α). In other words, if two tubular braids commute with bα, if they induce the same permutation, and if some “filling” of one of them commutes even with α, then the same filling of the other will also commute with α. Proof of lemma 5.14 Conjugating αby ψ(ν)·ιµ∈Z(α) yields a certain braid α′; we have to check that α′=α. Firstly, we have an equality of tubular braids b α′=bα, because ν, the tubular braid of ψ(ν)·ιµ, commutes with bα. Moreover, since µand νinduce the same permutations, we have for i= 1,...,m that the ith tube of α′contains the same braid as the ith tube of (ψ(µ)·ιµ)−1·α·(ψ(µ)·ιµ). Since ψ(µ)·ιµcommutes with α, this is in turn the same as the ith tube of α. In summary, αand α′have the same tubular braids, and corresponding tubes contain the same interior braids, which implies that α=α′. Next we have to think in detail about the orbit structure of b β. Let us choose arbitrarily a puncture Pof the disk Dm(on which b βacts), and let O(b β, ρ) be the orbit of that puncture under the action of the subgroup hb βi × hρiof Z0(b β). Let O(b β, ρ, η) be the orbit of Punder the action of the group hρi × hηi(note that this group is also isomorphic to Z2, and contains b β). We are going to suppose without loss of generality that O(b β, ρ, η) contains all punctures of Dm, and we shall specify how the tubes of ηcorresponding to this orbit shall be filled – indeed, if there are other orbits, then these can be treated in same way, independently. Special case: Let us start by considering the simpler special case that O(b β, ρ, η) = O(b β, ρ), i.e. that the action of ηpreserves the (b β, ρ)-orbit. In this case we have Lemma 5.15 There exist integers kand lsuch that ηand b βk·ρlinduce the same permutations on O(b β, ρ). Proof of lemma 5.15 One can choose kand lsuch that b βkρl(P) = η(P), simply because η(P) is in the orbit of Punder the action of b βand ρ. Now if 25 ⩽S+ 1 2−m−1 2+b+m 2 =S(S+ 1) 2+b+m−1 = S(S+ 1) 2+b+u+v ⩽S(S+ 1) 2+S+v=S(S+ 3) 2+v. If v= 0 then b= 0 and k=S, so |G′|⩽S(S+3) 2=p(n). If v= 1 then n= 2S+2 and k=S+1. Then |G′|⩽S(S+3) 2+1 = (S+1)(S+2) 2= p(n). If v= 2 then n= 2S+ 3 and k=S+ 1. Then |G′|⩽S(S+3) 2+ 2 = S2+3S+4 2< (S+1)(S+4) 2=p(n). Finally, if v⩾3 then n= 2S+v+ 1 so k⩾S+v/2. Hence p(n)⩾(S+v/2)(S+v/2 + 1) 2=S2+ (v+ 1)S+v(v+ 2)/4 2 ⩾S(S+ 3) 2+S/2 + v/2>S(S+ 3) 2+v⩾|G′|. Therefore, in every case |G′|⩽p(n), and theorem 1.3 is proved. Recall that, in example 2.1, we defined braids of any number of strands whose centralizer could not be generated by less than p(n) elements. Therefore, the bound given by theorem 1.3 is the best possible one. 7 Small generating sets We saw in the previous section an upper bound for the number of generators of the centralizer of a braid β, in terms of its number of strings. But one could obtain a better bound if more information about βis given. In this section we will define a new generating set Gfor Z(β), which is in most cases smaller than the set G′defined before. It is also the smallest possible “natural” generating set, in the sense that each generator belongs to one of the t+ 1 factors in the semidirect product decomposition in theorem 1.1(c). Thus in a philosophical sense, Gis the “right” generating set, even though it is not in general the smallest possible one, as we shall see at the end of this section. If βis periodic or pseudo-Anosov, we already know a minimal generating set, with at most two elements. We also know a minimal generating set for any 32 mixed braid group (see the proof of proposition 6.1). Hence we can define Gby induction on the number of strands, when βis a reducible, non-periodic braid. We can also suppose that βis in regular form. We recall that the interior braids are denoted β[1],...,β[t], and the tubular braid b β. Definition 7.1 We will say that i, j ∈ {1,...,t}are permutable if there exists some η∈Z0(b β)such that η(Ci) = Cj. Remark that permutability is an equivalence relation, and the definition of Z0(b β) says that if iand jare permutable then β[i]=β[j]. Let then {i1,...,ir} ⊂ {1,...,t}be coset representatives for permutability. Let Gikbe a minimal set of generators for Z(β[ik]), and G0be a minimal set of generators for Z0(b β). Then we define G=gi1(Gi1)∪ · · · ∪ gir(Gir)∪ h(GH). Notice that G⊂G′, and they coincide if and only if there is no pair of permutable indices. Proposition 7.2 Gis a generating set of Z(β). Proof From the exact sequence of theorem 5.10 it follows that, if Giis a set of generators for Z(β[i]), then a set of generators for Z(β) is G′=g1(G1)∪ · · · ∪ gt(Gt)∪h(G0). Hence, we just need to show that if j∈ {1, . . . , t}\{i1,...,ir}, then every element in gj(Gj) can be written as a product of elements in G. Take then jas above. There must be some ikpermutable with j, so β[j]=β[ik] and there is some η∈Z0(b β) such that η(Cik) = Cj. Notice that Gjis a set of generators for Z(β[j]) = Z(β[ik]), so every γ∈Gjcan be written as a product of elements in Gik. Hence the braid α=h(η)−1gik(γ)h(η) can be written as a product of elements in G. Moreover, one has bα=d h(η)−11d h(η) = 1, and the only nontrivial interior braids in αare those corresponding to Cj. Since the interior braids h(η)ik,l for every lare just powers of β[ik]=β[j], and γ commutes with β[j], it follows that for every l,αj,l =γ. Therefore α=gj(γ), so every element in gj(Gj) can be written as a product of elements in G, thus Gis a generating set for Z(β). The generating set we have just defined is, unfortunately, not always the smallest possible one: Example 7.3 Consider the five string braid β=σ3σ4σ2σ3σ1σ2σ2σ3σ4σ1σ2σ3 – the canonical reduction system of this braid has two round circles, one containing punctures number 1, 2 and 3, the other punctures number 4 and 5; the 33 tubular braid is just a full twist of the two fat strings: b β=σ2 1. Moreover, the interior braids of each tube is trivial. According to theorem 1.1, the centralizer of this braid is Z(β)∼ =(B3×B2)⋊PB2∼ =(B3×Z)⋊ Z and the generating set constructed in this section has four elements: two for B3, and one for each factor Z. We now claim that this generating set is not as small as possible. Indeed, B3×Zcan be generated by only two elements (and thus Z(β) can be generated by three elements). To see this, recall that the 3-string braid group is isomorphic to the group of the (2,3)-torus knot. Thus B3has a presentation hy, z |y3z−2= 1i(with y=σ1σ2and z=σ1σ2σ1). Moreover, the factor Zis generated by σ4. Now the two generators (y, σ4) and (z, σ4) generate B3×Z, because (1, σ4) can be written as (y, σ4)3(z, σ4)−2. 8 Some algorithmic aspects The aim of this section is to present the essential ingredients for an algorithm which, for any given braid, finds a generating set of its centralizer subgroup that matches the description of the previous sections. Since, for any braid βand any k∈Z, the centralizer subgroups of βand β∆2kcoincide, we can always assume that βis positive. We start by mentioning that algorithms that perform the Nielsen-Thurston classification, and give the invariant folitations in the pseudo-Anosov case (in the form of train tracks), are available – notably, there are Bestvina-Haendel’s [5] and of Los’ [24] algorithms; and computer implementations are available on the web [9, 19]. We recall briefly the idea of the two automatic structures on braid groups that are relevant for us: for the first one, given by Garside [17] and Thurston [33] (and refined by El-Rifai and Morton [12]), we think of Dnhas having the n punctures lined up on the real line in the disk D. For the second one, given by Birman, Ko, and Lee [7], we think of Bnas having the npunctures regularly spaced on the circle of radius 1. Apart from that, the structures are exactly analogue. In the Garside-Thurston structure, there is a canonical way to write βas a product of divisors of ∆, namely by pushing each crossing between two strings into a factor as far to the left as possible. This normal form is called the left greedy normal form. For instance, in this normal form all factors which 34 are equal to ∆ (not just divisors of it) are grouped together at the very left of the product decomposition. Analogously, Birman-Ko-Lee write each braid as a product of divisors of δin a left-greedy way. If βis a positive braid, then its super summit set is the subset of all elements αof its conjugacy class which satisfy the following conditions: (i) αis positive, (ii) the writing of αin left greedy normal form has as few factors as possible among all elements satisfying (i), (iii) the writing of of αin left greedy normal form has as many factors on the left as possible equal to ∆ (or δ), among all elements satisfying (i) and (ii). Two positive elements of Bnare conjugate if and only if their super summit sets coincide. Given β∈Bnthere is an algorithm, given in [15] (which is an improvement of the algorithm in [12]), to compute its super summit set. It is as follows: first we repeatedly cycle β(i.e. move the first factor different from ∆, respectively δ, to the end and calculate the left greedy form of the resulting braid), until this process runs into a loop. At this point we are guaranteed to have achieved condition (ii) above. Then we repeatedly decycle (i.e. move the last factor to the front and calculate the left greedy form of the resulting braid) until we run into a loop. Then all elements of this loop belong to the super summit set. Afterwards, all other elements of the super summit set can be found recursively by conjugating already known elements by (suitable) divisors of ∆ (respectively δ), and retaining the result if it belongs to the super summit set. This algorithm for computing the super summit set is necessary for our purposes. Now suppose we are given a braid β∈Bnand we want to compute its centralizer. First we need to determine if βis periodic, reducible or pseudo- Anosov, and then we can use the results in this paper. Remark 8.1 Very recently, V. Gebhardt [18] presented a better algorithm for the conjugacy problem in braid groups. He defined the ultra summit set, which is in general much smaller than the super summit set described here. Periodic elements Deciding whether a given element βof Bnis periodic is very easy: one calculates the n−1st and the nth power of β. Then βis periodic if and only if one of the two results is a power of ∆2. 35 If βn−1= ∆2kfor some k∈N, then βis conjugate to γk (n)(as can be easily seen from lemma 3.1), and a conjugating element can be found explicitly using either of the two standard algorithms. Similarly, if βn= ∆2k, then βis conjugate to δk (n), and either algorithm yields an explicit conjugating element. In either case, one can find explicitly a generating set of the centralizer subgroup with only two elements, using propositions 3.3 or 3.5. Finding reducing curves of reducible elements After establishing that an element βof Bnis not periodic, we need to check whether it is reducible, and if it is, we want to find explicitly an invariant multicurve. This is, in fact, a standard part of Bestvina-Haendel’s [5] and of Los’ [24] algorithms. We want to point out one particulary elegant alternative, which is due to Benardete, Gutierrez and Nitecki [3] (see also [2]). We think of Dnas having the npunctures lined up horizontally, and we look at Garside-Thurston’s left greedy normal form. The key observation from [3] is the following: suppose that Cis an invariant multicurve of a braid β, and that the normal form of β is β=β1·...·βk, where β1,...,βk∈Bnare divisors of ∆. Moreover, suppose that all components of Care round (i.e. actual geometric circles in Dn). Then we have not only that β1·...·βn(C) = C, but also that all components of all the multicurves β1·...·βi(C) are round for i= 1,...,k. As remarked in [3] this implies as a corollary that invariant multicurves are visible as round curves in the super summit set of β, and in particular the reducibilty of a braid is easily detectable from the super summit set. To prove the corollary we note that βhas a conjugate in which all components of the curve system Care round; moreover, βand its conjugate have the same super summit set. Now cycling and decycling this conjugate does not change the fact that there is a round invariant curve system, by the key observation above. At the end of the cycling/decycling procedure we have found elements of the super summit set which contain the desired round invariant curves. Now it is shown in [3] how to determine if a given braid preserves a system of disjoint round curves. And there is a finite number of these systems. Moreover, since for each element of the super summit set we know how it can be conjugated to obtain β, we can find explicitly all curves that belong to a reduction system for β. We can then easily determine, by its definition, which of these curves belong to the canonical reduction system of β. That is, we can compute the canonical reduction system of β. 36 By the results in this paper, Z(β) is then a semi-direct product of two groups that can be computed by induction on the number of strings. Hence, it only remains to study the case when βis pseudo-Anosov. Pseudo-Anosov elements: commutation with δk (n) Suppose that our braid βfails the tests of periodicity and reducibility, hence it is known to be pseudo-Anosov. We need to check if it commutes with a periodic braids other than powers of ∆2. We shall think of Dnas having its npunctures uniformly distributed over the circle of radius 1, and we consider Birman-Ko-Lee’s left-greedy normal form. We want to decide algorithmically whether βis conjugate to a braid αwith the property that αcommutes with δk (n)for some positive integer k < n. If it is, we want to know the conjugating braid explicitly. The following result yields such an algorithm. Proposition 8.2 Suppose that a pseudo-Anosov braid βhas a conjugate which commutes with δk (n)for some integer k. Then there exists an element α of the super summit set of βwhich has the property that α, and in fact every factor of the left greedy normal form of α, commutes with δk (n). Proof Let β′be a conjugate of βwhich commutes with δk (n). If β′=β′ 1·...·β′ r is the left-greedy normal form of β′, then each factor β′ iis a divisor of δ(n)which is 2πk n-symmetric. This follows from the fact that the very definition of the leftgreedy normal form is completely rotation symmetric. More precisely, the fact that two consecutive factors β′ iβ′ i+1 determine a left-greedy normal form is not modified by rotating them. Hence, the product (δ−k (n)β′ 1δk (n))···(δ−k (n)β′ rδk (n)) is in left-greedy normal form. Since this product equals δ−k (n)β′δk (n)=β′, whose leftgreedy normal form is β′ 1···β′ k, we obtain that δ−1 (n)β′ iδ(n)=β′ i, for i= 1,...,r. Using the same argument inductively, we see that the cycling and decycling procedure only ever creates braids in left greedy normal form in which all factors are 2πk n-symmetric. Now we notice that it is very easy to decide if a given divisor of δ(in the Birman-Ko-Lee context) is invariant under a given rotation. Hence one can determine if a braid commutes with an (explicitly computable) conjugate of δk (n)by looking at the elements of its super summit set. 37 Pseudo-Anosov elements: commutation with γk (n) Now we want to determine if a given pseudo-Anosov braid commutes with a conjugate of γk (n), for a given positive integer k < n −1. This is only possible if there is some index i∈ {1,...,n}such that βpreserves Pi, as can be easily seen by looking at the corresponding permutations. Call Pi={{Pi},{P1,...,Pi−1, Pi+1,...,Pn}}, a partition of {P1,...,Pn}. Then βshould belong to BPi. There is a natural map fi:BPi→Bn−1which consists of forgetting the ith string. Notice that, if a braid αcommutes with γk (n)(where P1is considered to be the central point of D(n)) then f1(α) commutes with f1(γk (n)) = δk (n−1) . Hence we have a necessary condition that must be satisfied. If βpreserves a puncture Pi, then we conjugate it to some αthat preserves P1, and we test whether a conjugate of f1(α) commutes with δk (n−1) for some k < n −1. If this does not happen, for i= 1,...,n, then no conjugate of βcommutes with γk (n). This necessary condition is of course not sufficient. A sufficient and testable condition is now given by the following result. Recall that, by corollary 3.7, there is an isomorphism χ= (¯ θ∗)−1θ∗from Z(δk (n−1)) to Z(γk (n)), given by adding a trivial string at the centre of Dn−1. Notice that, if ζ∈Z(γk (n)), then χ(f1(ζ)) = ζ. Then one has: Proposition 8.3 Suppose that α∈Bnpreserves P1, and eα=f1(α)commutes with δk (n−1) . Then the following two statements are equivalent. (i) αis conjugate to an element ζof Bnwhich commutes with γk (n), and the conjugating homeomorphism preserves P1. (ii) αis conjugate to χ(eα). Proof The implication (ii)⇒(i) is immediate, by choosing ζ:= χ(eα). For the implication (i)⇒(ii), we suppose that (i) holds, that is, there is an element η∈BP1such that η−1αη =ζ, where ζ∈Z(γk (n)). We can apply f1to all these elements, denoting eη=f1(η) and e ζ=f1(ζ). This yields (eη)−1eαeη=e ζ, where eα, e ζ∈Z(δk (n−1)). If we show that eη∈Z(δk (n−1)), then we can apply χto all factors, obtaining χ(eη)−1χ(eα)χ(eη) = χ(e ζ) = ζ, hence χ(eα) is conjugate to ζwhich is conjugate to α, and the result follows. 38 Let us then show that eηcommutes with δk (n−1) . Notice that ζis a pseudo- Anosov braid that commutes with γk (n). Hence it preserves a projective foliation Fζ, which is invariant under a rotation by an angle of 2πk n−1. But in this case e ζ also preserves Fζ, with the same stretch factor, hence it is also pseudo-Anosov. Since eαis conjugated to e ζ, then it is pseudo-Anosov as well, and we call Feα its corresponding projective foliation (which is also invariant under the same rotation, since eαcommutes with δk (n−1) ). Since (eη)−1eαeη=e ζ, we have that eη sends Feαto Fζ. Now consider the braid d=eη−1δk (n−1)eη. It is conjugate to δk (n−1) , and hence periodic. Moreover, it preserves Fζ, so it commutes with e ζ. But the periodic elements in the centralizer of e ζform a cyclic group containing δk (n−1) , and δk (n−1) is the only element having exponent sum (n−2)k. Since dhas exactly the same exponent sum, it follows that d=δk (n−1) . Hence eηcommutes with δ(n−1) , and the result follows. An algorithm for testing whether a braid βis conjugate to a braid which commutes with γk (n)is now easy to construct: for each of the npunctures test whether the puncture is fixed by β, and whether forgetting this puncture yields a braid which is conjugate to a braid eαthat commutes with δk (n). (We know how to do this, by the results of the previous subsection). For each puncture that does satisfy this property, test whether χ(eα) (which is obtained from eα by adding a “trivial” string in the centre), is conjugate to β. If, for one of the punctures, this is the case, then the answer is “yes”, otherwise “no”. Pseudo-Anosov elements: finding roots It remains to describe a last step for computing a generating set for Z(β), when βis pseudo-Anosov. We assume that we have already computed the subgroup hρiof periodic braids commuting with β. Then we can multiply βby a suitable power of ρ, to obtain a braid bthat preserves the singular leaves of the projective foliations corresponding to β. Then we know that Z(β) = hαi × hρi, where αis the smallest possible root of b. The last problem, therefore, is to determine whether a given pseudo-Anosov braid bhas a kth root, for given k, and to compute that root. This problem has been solved in [31] (generalised to all Garside groups in [30]). Moreover, since the number of possible values of kis finite (we are assuming that bis positive), we have an algorithm for computing α, thus a generating set for Z(β). 39 Acknowledgements We are grateful to a number of people for discussions and valuable ideas that greatly contributed to this research. The examples of Nikolai V. Ivanov [21, 22], which we learned about through discussions with Mustafa Korkmaz, were an important inspiration and greatly helped us clarify our ideas. It was thus from Ivanov (via Korkmaz) that we learned that the number of generators may have to grow quadratically with the number of strings, contradicting a conjecture in [16]. We are very grateful to Sang Jin Lee who later, but independently of Ivanov, came up with his examples, conjectured that they represent the worst case, and kindly communicated these ideas to us by email. (Hessam Hamidi-Teherani found the same examples as Lee immediately after listening to Ivanov’s talk, but we didn’t learn this until very recently.) We also thank David Bessis for useful discussions, and Joan Birman for telling us about the references [2] and [3]. References [1] V. I. Arnold, The cohomology ring of the group of dyed braids, Mat.Zametki, V. 5 (1969), 227-231. [2] D. Benardete, M. Gutierrez, Z. Nitecki, A combinatorial approach to reducibility of mapping classes, Contemporary Math. 150 (1993), 1–31. [3] D. Benardete, M. Gutierrez, Z. Nitecki, Braids and the Nielsen-Thurston classification, J. Knot Theory and its Ramifications 4 (1995), 549-618. [4] D. Bessis, F. Digne, J. Michel, Springer theory in braid groups and the Birman- Ko-Lee monoid, Pacific J. Math. 205 (2002), no. 2, 287–309. [5] M. Bestvina, M. Haendel, Train-tracks for surface homeomorphisms, Topology 34 (1995), 109–140. [6] J. Birman, Braids, links, and mapping class groups, Annals of Math. Studies, 82, Princeton University Press 1975. [7] J. Birman, K. H. Ko, S. J. Lee, A new approach to the word and conjugacy problems in the braid groups, Adv. Math. 139 (1998), 322–353. [8] J. Birman, A. Lubotzky and J. McCarthy, Abelian and solvable subgroups of the mapping class groups, Duke Math.J. 50 (1983), 1107-1120. [9] P. Brinkmann, An implementation of the Bestvina-Handel algorithm for surface homeomorphisms, Experiment. Math. 9 (2000), 235–240. Computer program available at www.math.uiuc.edu/~brinkman/software/train/ [10] A. Constantin, B. Kolev, The theorem of Ker´ekj´art´o on periodic homeomorphisms of the disc and the sphere, Enseign. Math (2) 40 (1994) No 3-4, 193-204. [11] S. Eilenberg, Sur les transformations p´eriodiques de la surface de sph`ere, Fund. Math. 22 (1934), 28–41. 40 [12] E. A. El-Rifai, H. R. Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser. (2) 45 (1994), no. 180, 479–497. [13] A. Fathi, F. Laudenbach, V. Poenaru, Travaux de Thurston sur les surfaces - seminaire Orsay, Asterisque 66–67, Soci´et´e Math. de France, 1991. [14] R. Fenn, D. Rolfsen, J. Zhu, Centralisers in the braid group and singular braid monoid, l’Enseignment Math´ematique 42 (1996), 75–96. [15] N. Franco, J. Gonz´alez-Meneses, Conjugacy problem for braid groups and Garside groups. To appear in Journal of Algebra. [16] N. Franco, J. Gonz´alez-Meneses, Computation of centralizers in braid groups and Garside groups. To appear in Revista Matem´atica Iberoamericana. [17] F. A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20 (1969), 235–254. [18] V. Gebhardt, A New Approach to the Conjugacy Problem in Garside Groups, Preprint (2003). arXiv:math.GT/0306199. [19] T. Hall, Computer implementation of Bestvina-Handel algorithm available at www.liv.ac.uk/maths/PURE/MIN SET/CONTENT/members/T Hall.html [20] N. V. Ivanov, Subgroups of Teichm¨uller modular groups, Translations of mathematical monographs vol. 115 (1992), AMS. [21] N. V. Ivanov, talk at the special session “Mapping class groups and the geometric theory of Teichm¨uller spaces” at the 974th meeting of the AMS, Ann Harbour, MI, March 1–3, 2002. [22] N. V. Ivanov, Examples of centralizers in the Artin braid groups, Preprint (2003), arXiv:math.GT/0306418 [23] B. de Ker´ekj´art´o, ¨ Uber die periodischen Transformationen der Kreisscheibe und der Kugelfl¨ache, Math. Annalen 80 (1919), 3–7. [24] J. Los, Pseudo-Anosov maps and invariant train tracks in the disc: a finite algorithm, Proc. London Math. Soc. (3) 66 (1993), 400–430. [25] G. S. Makanin, On normalizers in the braid group, Mat.Sb. 86 (128), 1971, 171–179. [26] S. Manfredini, Some subgroups of Artin’s braid group. Special issue on braid groups and related topics (Jerusalem, 1995). Topology Appl. 78 (1997), no. 1-2, 123–142. [27] S. Yu. Orevkov, Quasipositivity test via unitary representations of braid groups and its applications to real algebraic curves, J. Knot Theory Ramifications 10 (2001), no. 7, 1005–1023. [28] L. Paris, D. Rolfsen, Geometric subgroups of surface braid groups, Ann. Inst. Fourier 49 (1999), 101-156 [29] R. C. Penner, J. L. Harer, Combinatorics of train tracks, Annals of Mathematics Studies, 125. Princeton University Press, Princeton, NJ, 1992. 41