Conjugacy in Garside Groups III: Periodic braids

arXiv:math/0609616v2 [math.GT] 22 Feb 2007 Conjugacy in Garside Groups III: Periodic braids Joan S. Birman∗Volker Gebhardt Juan Gonz´alez-Meneses† February 19, 2007 Abstract An element in Artin’s braid group Bnis said to be periodic if some power of it lies in the center of Bn. In this paper we prove that all previously known algorithms for solving the conjugacy search problem in Bnare exponential in the braid index nfor the special case of periodic braids. We overcome this difficulty by putting to work several known isomorphisms between Garside structures in the braid group Bnand other Garside groups. This allows us to obtain a polynomial solution to the original problem in the spirit of the previously known algorithms. This paper is the third in a series of papers by the same authors about the conjugacy problem in Garside groups. They have a unified goal: the development of a polynomial algorithm for the conjugacy decision and search problems in Bn, which generalizes to other Garside groups whenever possible. It is our hope that the methods introduced here will allow the generalization of the results in this paper to all Artin-Tits groups of spherical type. 1 Introduction Given a group, a solution to the conjugacy decision problem is an algorithm that determines whether two given elements are conjugate or not. On the other hand, a solution to the conjugacy search problem is an algorithm that finds a conjugating element for a given pair of conjugate elements. In §1.4 of [6] we presented a project to find a polynomial solution to the conjugacy decision problem and the conjugacy search problem in the particular case of Artin’s braid group, that is, the Artin-Tits group of type An−1, with its classical or Artin presentation [1]: (1) BA n:σ1,...,σn−1 σiσj=σjσiif |i−j|>1, σiσjσi=σjσiσjif |i−j|= 1.. One of the steps in the mentioned project asks for a polynomial solution to the above conjugacy problems for special type of elements in the braid groups, called periodic braids. This is achieved in the present paper. More precisely, if we denote by |w|the letter length of a word win σ1,...,σn−1and their inverses, we will prove: ∗Partially supported by the U.S.National Science Foundation, under Grant DMS-0405586. †Partially supported by MTM2004-07203-C02-01 and FEDER. 1 Theorem 1. Let wXand wYbe two words in the generators σ1,...,σn−1and their inverses, representing two braids X, Y ∈BA n, and let l= max{|wX|,|wY|}. Then there is an algorithm of complexity O(l3n2log n)which does the following. (1) It determines whether Xand Yare periodic. (2) If yes, it determines whether they are conjugate. (3) If yes, it finds a braid C∈BA nsuch that Y=C−1XC. Here is a guide to this paper. In Section 2, we will review what is known and explain why steps (1) and (2) of Theorem 1 follow easily from the work in [17, 24, 22]. On the other hand, in Section 3 we show that the previously known solutions to the conjugacy search problem in the Artin-Tits group of type An−1present unexpected difficultites, which result in exponential complexity for periodic braids. Thus they do not meet the requirements of Theorem 1. A new idea allows us to overcome the difficulty. We have shown that the approach using the classical Garside structure does not work. The new idea is to put to work the other known Garside structure on the braid groups and in addition to consider a certain subgroup of the braid group that arises in the course of our work, and use two known Garside structures on it. This is accomplished in Section 4, where we give a solution to the conjugacy search problem for periodic braids which has the stated polynomial complexity. Section 4 divides naturally into two subsections, according to whether a given periodic braid is conjugate to a power of δor ε, two braids that are defined in Section 2 below. The proof in the two cases are treated in Sections 4.1 and 4.2 respectively. Finally, in Section 5 we compare actual running times of the algorithms developed in Section 4 to the ones of the best previously known algorithm. Remark 2. We learned from D. Bessis that he has characterized the conjugacy classes of periodic elements for all Artin-Tits groups of spherical type. We hope that this characterization will allow the generalization of both the techniques and the results of this paper to all other Artin-Tits groups of spherical type. Acknowledgements: We are grateful to D. Bessis for useful discussions about his work in [2] and his forthcoming results, to J. Michel for pointing out that our Corollaries 12 and 15 were known to specialists in Coxeter groups, and also to H. Morton for showing us the algorithm in [26]. 2 Known results imply steps (1) and (2) of Theorem 1 Our work begins with a review of known results. Garside groups were introduced by Dehornoy and Paris in [15]. The main examples of Garside groups are Artin-Tits groups of spherical type, in particular, Artin braid groups. In this paper we will use two known Garside structures in the Artin-Tits group of type An−1, and also one Garside structure in the Artin-Tits group of type Bm. Although we refer to [6] for a detailed description of Garside structures, we recall here that such a structure in a group Gis given by a lattice order on its elements, together with a distinguished element of G, called the Garside element, which is usually denoted by ∆. This partial order and this element ∆ must satisfy several suitable conditions [6]. 2 The classical Garside structure in the braid groups is related to the presentation (1). The positive braids are those which can be written as a word in σ1, . . . , σn−1(not using their inverses). The lattice order is defined by saying that X4Yif X−1Yis a positive braid (we will say that Xis a prefix of Y). There are special elements called simple braids which are those positive braids in which any two strands cross at most once. The Garside element ∆ is the positive braid in which any two strands cross exactly once, that is, ∆ = σ1(σ2σ1)(σ3σ2σ1)···(σn−1···σ1). It is also called the half twist, since its geometrical representation corresponds to a half twist of the nstrands. For every braid X∈BA n, given as a word of letter length l, there exists a left normal form, which is a unique way to decompose the braid as X= ∆px1···xr, where pis maximal and each xiis a simple braid, namely the maximal simple prefix of xi···xr. This left normal form can be computed in time O(l2nlog n) [19]. Artin proved in [1] that the center of BA nis infinite cyclic and generated by the full twist ∆2= (σ1σ2···σn−1)nof the braid strands. If the braid group is regarded as the mapping class group of the n-times punctured disc D2 n, then ∆2is a Dehn twist about a curve which lies in a collar neighborhood of the boundary ∂D2 nand is parallel to it. An element X∈BA n is said to be periodic if some power of Xis a power of ∆2. Periodic braids can be thought of as rotations of the disc. Indeed, there is a classical result by Eilenberg [17] and K´er´ekj´art´o[24] (see also [12]) showing that an automorphism of the disc which is a root of the identity (a periodic automorphism) is conjugate to a rotation. Since a finite order mapping class can always be realized by a finite order homeomorphism [23], this implies that a periodic braid is conjugate to a rotation. It is not difficult to see that a braid can be represented by a rotation of D2if and only if it is conjugate to a power of one of the two braids represented in Figure 1, that is, δ=σn−1σn−2···σ1and ε=σ1(σn−1σn−2···σ1). (If we need to specify the number of strands, we will write δ=δnand ε=εn.) Remark 3. The braid εdefined in Figure 1 has a fixed strand, namely strand 2. There are, to be sure, braids which are conjugate to εin which the fixed strand is the first one or the last one, seemingly more natural choices. However, εis a simple braid, and (as we shall prove in Proposition 13 below) there is no simple braid which is conjugate to εand which fixes either the first or the last strand. This is why we decided to use ε, which fixes the second strand, as a representative of its conjugacy class. And this is also the reason why, in Section 4.2 below, we identify the Artin-Tits group of type Bn−1with the subgroup of the n-strand braid group formed by those braids which fix the second strand, a choice that will surely seem awkward to specialists. The theorem of Eilenberg and K´er´ekj´art´o can then be restated as follows. Theorem 4. [17, 24] A braid Xis periodic if and only if it is conjugate to a power of either δor ε. Notice that δn=εn−1= ∆2. Since ∆2belongs to the center of BA n, this immediately gives an efficient algorithm to check whether a braid is periodic. Corollary 5. A braid X∈BA nis periodic if and only if either Xn−1or Xnis a power of ∆2. Proof. We only need to prove that the condition is necessary. Suppose that Xis periodic. By Theorem 4, Xis conjugate to a power of either δor ε. In the first case, X=C−1δkCfor 3 Figure 1: The periodic elements δand ε. some C∈BA n. Then Xn=C−1δknC=C−1∆2kC= ∆2k, where the last equality holds since ∆2is central. In the second case, X=C−1εkC, so that Xn−1=C−1εk(n−1)C=C−1∆2kC= ∆2k. After this result, one can determine whether Xis periodic, and also find the power of δor ε which is conjugate to X, by the following algorithm. Algorithm A. Input: A word win Artin generators and their inverses representing a braid X∈BA n. 1. Compute the left normal form of Xn−1. 2. If it is equal to ∆2k, return ‘Xis periodic and conjugate to εk’. 3. Compute the left normal form of Xn. 4. If it is equal to ∆2k, return ‘Xis periodic and conjugate to δk’. 5. Return ‘Xis not periodic’. Proposition 6. The complexity of Algorithm A is O(l2n3log n), where lis the letter length of w. Proof. Algorithm A computes two normal forms of words whose lengths are at most nl. By [19], these computations have complexity O((nl)2nlog n), and the result follows. We remark that if one knows, a priori, that the braid Xis periodic, then one can determine the power of δor εwhich is conjugate to Xby a faster method: Observe that the exponent sum of a braid X, written as a word in the generators σ1,...,σn−1and their inverses is well defined, since the relations in (1) are homogeneous. The exponent sum is furthermore invariant under conjugacy, hence every conjugate of δkhas exponent sum k(n−1), whereas every conjugate of εkhas exponent sum kn. Moreover, the exponent sum determines the conjugacy class of a periodic braid: Lemma 7. (Proposition 4.2 of [22]) Let Xbe a periodic braid. Then Xis conjugate to δk (resp. εk) if and only if Xhas exponent sum k(n−1) (resp. kn). 4 Computing the exponent sum of a word of length lhas complexity O(l). Hence, once it is known that two given braids are periodic, the conjugacy decision problem takes linear time. 3 Known algorithms are not efficient for periodic braids We have already determined all conjugacy classes of periodic braids, and we have seen that the conjugacy decision problem for these braids can be solved very fast. It is then natural to wonder whether this is also true for the conjugacy search problem. The first natural question is: Are the existing algorithms for the conjugacy search problem efficient for periodic braids? The best known algorithm to solve the conjugacy decision problem and also the conjugacy search problem in braid groups (and in every Garside group) is the one in [21], which consists of computing the ultra summit set of a braid, defined as follows. Denote by τthe inner automorphism that is defined by conjugation by ∆. Given Y∈BA nwhose left normal form is ∆py1···yr, we define its canonical length as ℓ(Y) = r, and call the conjugates c(Y) = ∆py2···yrτ−p(y1) and d(Y) = ∆pτp(yr)y2···yr−1of Yits cycling respectively its decycling. For every X∈BA n, the ultra summit set USS(X) is the set of conjugates Yof Xsuch that ℓ(Y) is minimal and ct(Y) = Yfor some t≥1. It is explained in [21] how the computation of USS(X) solves the conjugacy decision and search problems in Garside groups. The complexity of the conjugacy search algorithm given in [21] is proportional to the size of USS(X), so if one is interested in complexity, it is essential to know how large the ultra summit sets of periodic braids are. If they turned out to be small, the algorithm in [21] would be efficient, but we will see in this section that the sizes of ultra summit sets of periodic braids are in general exponential in n. More precisely, it was shown by Coxeter in 1934 [13, Theorem 11], that in any finite Coxeter group, any two elements which are the product of all standard generators, in arbitrary order, are conjugate. Applied to our case, one sees that the elements of USS(δ) are in bijection with the elements of the above kind, in the symmetric group Σn. One can count the number of different elements, and it follows that #(USS(δ)) = 2n−2. The same result is shown in [9, Chapter V, §6. Proposition 1], in the more general case in which the Coxeter group is defined by a tree, and also in [29, Lemma 3.2] and in [26, Theorem 2]. Moreover, it can be seen from the proof in [9] that any two elements in USS(δ) are conjugate by a sequence of special conjugations, that we denote partial cyclings in [6]. Concerning the elements in USS(ε), in [16, Proposition 9.1] it is shown that any two such elements are conjugate by a sequence of partial cyclings. It also follows from [16] that every element in USS(ε) is represented by a word of length n, which is the product of all n−1 generators, in some order, with one of the generators repeated. One can also count the number of different elements of this kind, to obtain that #(USS(ε)) = (n−2)2n−3. The above arguments show that the sizes of USS(δ) and USS(ε) are exponential with respect to the number of strands, hence the algorithm in [21] is not polynomial for conjugates of these braids. In this paper we shall study USS(δ) and USS(ε) in a new way. More precisely, in Corollaries 12 and 15 we will show that #(USS(δ)) = 2n−2and #(USS(ε)) = (n−2)2n−3 just by looking at the permutations induced by their elements. This will also provide a fast solution to the conjugacy search problem in the particular cases of conjugates of δor ε. 5 Once shown that the algorithm in [21] is not polynomial, in general, for periodic braids, in Section 4 we will give a procedure to solve the conjugacy search problem for all periodic braids in polynomial time. Let us then study the ultra summit sets of δand ε. First, we recall that the factors in a left normal form are simple braids, which are in bijection with the elements of the symmetric group Σn. More precisely, every braid X, being a mapping class group of the n-times punctured disc, determines a permutation πXof the npunctures. Conversely, there is exactly one simple braid for each permutation. We will then determine simple elements by their permutations, written as a product of disjoint cycles. For instance, the permutation associated to δis πδ= (1 2 ··· n), and the permutation associated to εis πε= (2)(1 3 4 ··· n). Remark 8. Although we described braids as mapping classes, we will not adopt the usual convention for compositions of maps. We consider braids as acting on the punctures from the right. This means that the braid σ1σ2first swaps the punctures in positions 1 and 2, and then the punctures in positions 2 and 3. Hence πσ1σ2= (132). Remark 9. The permutation associated to a simple braid sdetermines the pairs of strands that cross in s. More precisely, two strands iand j(i < j) cross in sif and only if the induced permutation reverses their order, that is, if πs(i)> πs(j). For simplicity of notation let us define, for 1 ≤i < j ≤n, the braids σ[i→j]=σiσi+1 ···σj−1 and σ[j→i]=σj−1σj−2···σi. Notice that σ[k→l](no matter which subindex is bigger) is the shortest positive braid sending the puncture kto the puncture l. Let us characterize the elements in USS(δ). Proposition 10. An element s∈BA nbelongs to USS(δ)if and only if it is simple and its permutation πsis a cycle of the form: πs= (1 u1u2···urn dtdt−1···d1), for some u1< u2<···< urand some dt> dt−1>···> d1, with r, t ≥0and r+t+ 2 = n. Moreover, in this case α−1sα =δ, where α=σ[d1→1] σ[d2→1] ···σ[dt→1]. Proof. First notice that, since δis simple, all elements in USS(δ) are simple, so that by the definition of a simple element they can be characterized by their permutations. Actually, USS(δ) is the set of simple conjugates of δ. Notice also that πδis a single cycle of length n. Since conjugation of braids in BA nimplies conjugation of their corresponding permutations, it follows that the elements in USS(δ), which are conjugates of δ, are simple elements determined by a cycle of length n. Moreover, if s∈USS(δ) then sn= ∆2, which is a positive braid in which any two strands cross exactly twice. Let s∈USS(δ). Its permutation can be written as πs= (1 u1u2· · · urn dtdt−1··· d1), where r, t ≥0 and r+t+ 2 = n. We must show that u1<···< urand dt>···> d1. See in Figure 2 an example of two simple braids whose permutations are cycles of length n, so the permutations are conjugate in the symmetric group, but one of the braids satisfies the above inequalities and the other one does not. 6 Figure 2: Two simple braids in BA 8whose permutations are cycles of length 8. By Proposition 10, the first one is conjugate to δand the second one is not. Notice that the exponent sum of the second one (i.e. the number of crossings or the letter length, in this case) is 9, while the exponent sum of conjugates of δ∈BA 8is 7. Suppose that ui> ui+1 for some i, where 1 ≤i < r, and consider the strands 1 and u1. We will see that these two strands cross more than twice in sn. Indeed, one has 1 < u1, but in sithese strands end at uiand ui+1, respectively. Since ui> ui+1, this means that they have crossed at least once in si. Now in srthese two strands end at urand n, respectively, and since uris necessarily less than n, they have crossed again. Next, in sr+1 they end at nand dt(or nand 1 if there are no dj’s), so they have crossed one more time. This means that in sr+1 the strands 1 and u1cross at least three times, showing that sncannot be equal to ∆2, a contradiction. Therefore u1<···< ur. Similarly, if we had di+1 < difor some i, then strands nand dtwould cross more than twice in sn, which is impossible. Therefore dt>···> d1. Conversely, suppose that sis simple and πs= (1 u1u2··· urn dtdt−1··· d1) for some u1<···< urand dt>···> d1. We will show that sis conjugate to δin a constructive way, by finding a conjugating element. First notice that if t= 0 then πs= (1 2 ··· n) = πδ. Since simple elements are determined by their permutations, this means that s=δ. Hence we can assume that t > 0. Denote k=d1. One has πs= (1 2 ··· k−1uk−1··· urn dt··· d2k). A schematic picture of the first kstrands of scan be seen in Figure 3. We will conjugate s by σ[k→1], so we consider s′=σ−1 [k→1] s σ[k→1]. Recall that two strands iand j(i < j) cross in sif and only if πs(i)> πs(j). Then we can easily check that the strand of sending at k (that is, the strand d2if t > 1 or the strand nif t= 1) does not cross the strands ending at 1,2,...,k−1 (that is, the strands k, 1,2,...,k−2, respectively). This implies that s σ[k→1] is a simple braid. Moreover, one can also check that the strand kof s(thus the strand kof s σ[k→1]) crosses the strands k−1, k −2,...,1, hence s′=σ−1 [k→1] s σ[k→1] is a simple braid. Since the permutation associated to σ[k→1] is (1 2 ··· k), it follows that πs′= (1 2 ··· k−1kuk−1··· urn dt··· d2). We can continue this process, by recurrence on t, conjugating by elements of the form σ[di→1] and obtaining new simple conjugates of swhose permutations have more indices between 1 and nat each step, until we get the permutation (1 2 ··· n), that is, until we obtain δ. In this 7 way we have shown that if sis a simple element with the permutation given in the statement, then α−1sα =δ, where α=σ[d1→1] σ[d2→1] ···σ[dt→1]. Therefore, we have determined the elements in USS(δ) in terms of their permutations. Figure 3: Conjugating sto s′. Remark 11. The above element αis simple, hence all elements in USS(δ) are conjugate to δby a simple element. Corollary 12. If δ=σn−1···σ1∈BA nthen #(USS(δ)) = 2n−2. Proof. The elements in USS(δ) are characterized by the permutation given in the above result, which is itself characterized by the sequence 1 < u1<··· < ur< n. The number of possible sequences is equal to the number of subsets of {2,...,n−1}which is precisely 2n−2. Now let us do the same for USS(ε). Proposition 13. An element s∈BA nbelongs to USS(ε)if and only if it is simple and πs= (a)(1 u1u2··· urn dtdt−1··· d1), for some u1< u2<···< urand some dt> dt−1>···> d1, with r, t ≥0and r+t+ 3 = n. Notice that a6= 1, n. Moreover, in this case one has β−1sβ =ε, where β=σ[d1→1] σ[d2→1] ···σ[dt→1] σ[b→2] and b=a+t−max{i:di< a}, 8 Proof. Since εis simple, the elements of USS(ε) are precisely the simple conjugates of ε; in particular, USS(ε) consists of simple elements whose permutation is the product of a cycle of length 1 (a fixed point) and a cycle of length n−1. Moreover, if s∈USS(ε) then sn−1= ∆2, where any two strands cross exactly twice. Let s∈USS(ε), and let πs= (a)(x1··· xn−1). If a= 1 then the first strand of sdoes not cross any other strand. This means that we can write sas a word in Artin generators in which the letter σ1does not appear. But in that case every power of swould satisfy the same property. In particular, the first strand of sn−1= ∆2would not cross any other strand, a contradiction. Hence a6= 1. In the same way one shows that a6=n. Therefore the permutation induced by scan be written as πs= (a)(1 u1u2··· urn dtdt−1··· d1). We can show that u1<··· < urand that dt>··· > d1, using the same proof as in Proposition 10. In Figure 4 we can see an example of two braids whose permutations are cycles of length n−1. The first one satisfies the above inequalities and the second one does not. Figure 4: Two simple braids in BA 8whose permutations are cycles of length 7. By Proposition 13, the first one is conjugate to εand the second one is not. As in Figure 2, the exponent sums of the two braids differ; the exponent sum of second one is 12, while the exponent sum of conjugates of ε∈BA 8is 8. Now let sbe a simple element such that πs= (a)(1 u1u2··· urn dtdt−1··· d1) for some u1< u2<···< ur, some dt> dt−1>···> d1and some a6= 1 or n. Suppose that t > 0. Similarly to the proof of Proposition 10, we will conjugate sby σ[d1→1], and this will reduce the index t. Let k=d1. If a > k one has πs= (a)(1 2 ··· k−1uk−1··· urn dt··· d2k), otherwise πs= (a)(1 2 ··· a−1a+ 1 ··· k−1uk−2··· urn dt··· d2k). The picture in the former case is the same as in Figure 3, while the latter case is represented in Figure 5. In either case, the strand of sthat ends at k(that is, d2if t > 1 or nif t= 1) 9 Lemma 20. The map ρ:A(Bn−1)→Pn,2given by ρ(s1) = σ2 1,ρ(s2) = σ1σ2σ−1 1and ρ(si) = σifor i > 2, is an isomorphism. Proof. Proposition 5.1 in [14] provides an isomorphism ρ0:A(Bn−1)→Pn,1, where Pn,1is the subgroup of BA nconsisting of braids which fix the first puncture. This isomorphism is given by ρ0(s1) = σ2 1and ρ0(si) = σifor i > 1, and it was already known to specialists, prior to [14]. Now we just need to notice that the inner automorphism ϕ:BA n→BA ngiven by ϕ(X) = σ1Xσ−1 1sends Pn,1isomorphically to Pn,2, and that ϕ|Pn,1◦ρ0=ρ. Remark 21. It is well known [14] that Pn,2(hence A(Bn−1)) can be identified with the braid group of the open annulus D2\{0}on n−1 strands. Indeed, an element X∈Pn,2fixes the second puncture, so it can be isotoped to a braid whose second strand in D2×[0,1] is a straight line, say {0} × [0,1]. This second strand can be considered to be a hole of D2, so X can be regarded as a braid on n−1 strands of D2\{0}. In order to avoid confusion, we will represent elements in Pn,2∈BA nin the usual way, as they are represented at the bottom of Figure 8, while elements of A(Bn−1) will be represented in the Birman-Ko-Lee style, as braids on D2\{0}whose base points are the (n−1)-st roots of unity, as we can see at the top of Figure 8. Figure 8: The generators of A(Bn−1), represented as braids on D2\{0}, and their images under the isomorphism ρ:A(Bn−1)→Pn,2. Lemma 22. The map θ′:A(Bn−1)→Sym2n−2given by θ′(s1) = an,1and θ′(si) = ai,i−1ai+n−1,i+n−2for i > 1, is an isomorphism. Proof. In [10], Brieskorn showed that an Artin-Tits group of finite type is the fundamental group of the regular orbit space of its corresponding Coxeter group, acting as a finite real reflection group on a complex space. In particular, since the Coxeter group associated to A(Bn−1) is W= Σn−1⋉(Z/2Z)n−1, where the symmetric group acts by permuting coordinates 16 (that is, Wis the signed permutation group), and its corresponding hyperplane arrangement is x1x2···xn−1Qi6=j(xi−xj)(xi+xj), it follows that A(Bn−1) = π1(XBn−1/W), where XBn−1={(x1,...,xn−1)∈Cn−1|xi6=±xjfor i6=j;xi6= 0 for all i}. A good way to describe the space XBn−1is as the set of (n−1)-tuples of pairs ((x1,−x1),(x2,−x2),...,(xn−1,−xn−1)), where each xi∈C, any two pairs are distinct, and xi6= 0 for all i. Considering the action of W, all the above pairs and (n−1)-tuples can be regarded as unordered. Hence XBn−1/W is the configuration space of 2n−2 disjoint and undistinguishable points in C, whose configuration is invariant under multiplication by −1. We can choose as a base point of this space the (2n−2)-nd roots of unity. Hence, an element of its fundamental group is represented by a braid which is invariant under a rotation by 180 degrees, that is, by a symmetric braid in BB 2n−2. It is important to note that two symmetric braids represent the same element in π1(XBn−1/W) if and only if they are isotopic through symmetric braids, hence one cannot say a priori that two symmetric braids that are isotopic in BB 2n−2represent the same element of π1(XBn−1/W). Fortunately, it is shown in [3] that two symmetric braids are isotopic in BB 2n−2if and only if they are isotopic through symmetric braids. That is, it is shown that A(Bn−1) = π1(XBn−1/W)∼ = Sym2n−2. Moreover, from the work in [3] one obtains an isomorphism θ:Sym2n−2→ A(Bn−1), where elements of Sym2n−2are symmetric braids based on the (2n−2)-nd roots of unity, and the elements of A(Bn−1) are considered as braids on the annulus D2\{0}based on the (n−1)- st roots of unity. The isomorphism θcan be easily described geometrically, since it just identifies antipodal points in C. That is, it sends z∈C\{0}to z2/|z|. This corresponds to a two-sheeted covering map of C\{0}, and since no strand of a symmetric braid touches the axis {0} × [0,1], this map is well defined. In Figure 9 we can see that θ(an,1) = s1and that θ(ai,i−1ai+n−1,i+n−2) = sifor i > 1, where in the picture one has ζk=e2kπi/(2n−2) and ξk=e2kπi/(n−1). Therefore θ′=θ−1, so it is an isomorphism. By Lemmas 20 and 22 we know that Pn,2∼ =A(Bn−1)∼ =Sym2n−2, and we also know how to transform any word in the generators s1,...,sn−1of A(Bn−1) and their inverses, into a word in either the Artin generators of Pn,2or the band generators of Sym2n−2, via the isomorphisms ρand θ′=θ−1. BA nBB 2n−2 ∪ ∪ Pn,2 ρ ←− A(Bn−1)θ′ −→ Sym2n−2. But in our algorithm we will need to translate any word in the Artin generators of BA n, representing an element of Pn,2, to a word in the band generators of Sym2n−2, and vice versa. Hence, we need the following results. 17 Figure 9: The map θtransforms the symmetric braids on the left hand side to the generators of A(Bn−1) on the right hand side. Lemma 23. Let X∈Pn,2⊂BA nbe given as a word of length lin the Artin generators and their inverses, X=σǫ1 µ1σǫ2 µ2···σǫl µl. For i= 0,...,l, let Xi=σǫ1 µ1σǫ2 µ2···σǫi µiand let ki=πXi(2), that is, the final position of the second strand of Xi. Then one obtains a word in the band generators and their inverses representing θ′(ρ−1(X)) ∈Sym2n−2, by replacing each letter σǫi µiusing the following rules: σµi→             aµi+1,µiaµi+n,µi+n−1if µi< ki−1−1, 1if µi=ki−1−1, aµi+n−1,µiif µi=ki−1, aµi,µi−1aµi+n−1,µi+n−2if µi> ki−1, and σ−1 µi→             a−1 µi+n,µi+n−1a−1 µi+1,µiif µi< ki−1−1, a−1 µi+n−1,µiif µi=ki−1−1, 1if µi=ki−1, a−1 µi+n−1,µi+n−2a−1 µi,µi−1if µi> ki−1. Moreover, this algorithm has complexity O(l), and produces a word of length at most 2l. Proof. Recall that we are given a braid X∈BA nthat fixes the second puncture, that is, X∈Pn,2, written as a word in the Artin generators of BA nand their inverses. We want to 18 write ρ−1(X) as a word in the generators s1,...,sn−1and their inverses, and then θ′(ρ−1(X)) as a word in the band generators of BB 2n−2. The first problem is that Xis not given as a word in the generators of Pn,2, but in the generators of BA n. We will then use the Reidemeister-Schreier method (see Section 2.3 of [27]) to decompose Xas a product of elements in Pn,2. In order to do this, notice that Pn,2is a subgroup of BA nof index n. The right coset of a braid Zdepends on where it sends the second puncture. If πZ(2) = k, we denote by Rka representative of the right coset Pn,2Z∈Pn,2\BA n. For technical reasons, we will choose as coset representatives the elements R1=σ1,R2= 1 and Rk=σ−1 [k→2] =σ−1 2···σ−1 k−1if k > 2. Then, for i= 0,...,l, we define Xi=Rki. That is, Xiis the chosen representative of Pn,2Xi∈Pn,2\BA n. Note that X0=Xl=R2= 1. By the Reidemeister-Schreier method, one has X= l Y i=1 Xi−1σǫi µiXi−1= l Y i=1 Rki−1σǫi µiR−1 ki, where each of the above lfactors belongs to Pn,2. Notice that ki=ki−1, unless either µi=ki−1 (in which case ki=ki−1+ 1) or µi=ki−1−1 (and then ki=ki−1−1). One can check that, depending on µiand ki−1, each of the above factors can be written in terms of the Artin generators and their inverses as follows. If ǫi= 1, one has: (Rki−1σµiR−1 ki) =                                σ−1 2σ1σ2if 1 = µi< ki−1−1, σµi+1 if 1 6=µi< ki−1−1, 1 if µi=ki−1−1, σ2 1if 1 = µi=ki−1, (σ−1 2σ−1 3···σ−1 µi−1)σµi(σµiσµi−1···σ2) if 1 6=µi=ki−1, σ1σ2σ−1 1if 2 = µi> ki−1, σµiif 2 6=µi> ki−1. If ǫi=−1, one obtains the inverses of the above, in the following way: (Rki−1σ−1 µiR−1 ki) =                                σ−1 2σ−1 1σ2if 1 = µi< ki−1−1, σ−1 µi+1 if 1 6=µi< ki−1−1, σ−2 1if 1 = µi=ki−1−1, (σ−1 2σ−1 3···σ−1 µi)σ−1 µi(σµi−1···σ2) if 1 6=µi=ki−1−1, 1 if µi=ki−1, σ1σ−1 2σ−1 1if 2 = µi> ki−1, σ−1 µiif 2 6=µi> ki−1. Now we need to apply ρ−1to each factor (Rki−1σǫi µiR−1 ki), and write the image in in terms of the generators s1,...,sn−1and their inverses. Recall that ρ(s1) = σ2 1,ρ(s2) = σ1σ2σ−1 1= 19 σ−1 2σ1σ2and ρ(si) = σifor i > 2. Notice also that ρ(s2s1s−1 2) = σ2 2, and that if µi>2 one has ρ(sµisµi−1···s3s2)s1(s−1 2s−1 3···s−1 µi)= (σµiσµi−1···σ3)σ2 2(σ−1 3···σ−1 µi) = (σ−1 2···σ−1 µi−1)σµi(σµi···σ2). Therefore, if ǫi= 1, one has: ρ−1(Rki−1σµiR−1 ki) =        sµi+1 if µi< ki−1−1, 1 if µi=ki−1−1, (sµisµi−1···s2)s1(s−1 2s−1 3···s−1 µi) if µi=ki−1, sµiif µi> ki−1, and if ǫi=−1, one obtains: ρ−1(Rki−1σ−1 µiR−1 ki) =        s−1 µi+1 if µi< ki−1−1, (sµisµi−1···s2)s−1 1(s−1 2s−1 3···s−1 µi) if µi=ki−1−1, 1 if µi=ki−1, s−1 µiif µi> ki−1. Finally, we need to apply θ′to the above factors. Notice that there are only two kinds of elements to consider. The first one is si, with i > 1, which by definition is mapped to θ′(si) = ai,i−1ai+n−1,i+n−2. The elements of the second kind are those of the form (sisi−1···s2)s1(s−1 2s−1 3···s−1 i), for i= 1,...,n−1. One can use the Birman-Ko-Lee presentation to show that the image under θ′of this element is precisely ai+n−1,i, but it is easier to show it geometrically, since the element (sisi−1···s2)s1(s−1 2s−1 3···s−1 i) is precisely the one in the right hand side of Figure 10, in which the puncture corresponding to the (n−1)-st root of unity ξimakes a loop around the origin. It is then easy to lift such a path via θ−1, obtaining the braid ai+n−1,i. Since θ−1=θ′, one has θ′(sisi−1···s2)s1(s−1 2s−1 3···s−1 i)=ai+n−1,i, as we wanted to show. Figure 10: The image under θof ai+n−1,i. One can finally transform the word X=σǫ1 µ1···σǫl µlto a word representing θ′(ρ−1(X)), if one replaces each σǫi µiby θ′(ρ−1(Rki−1σǫi µiR−1 ki)). By the above discussion, the formulae in the statement hold. It remains to notice that the numbers µiand ki, for i= 1,...,l can be obtained in time O(l), and that the procedure given by the statement replaces each letter of Xby at most two letters of θ′(ρ−1(X)). Hence the length of the obtained word is at most 2l, and the whole procedure has complexity O(l). 20 Now we also need to know how to translate an element Y∈Sym2n−2, given as a word in the band generators of BB 2n−2and their inverses, to a word representing ρ(θ(Y)) ∈Pn,2⊂BA n. We first need a preparatory result: Lemma 24. If Y∈Sym2n−2is given as a word of length lin the band generators of BB 2n−2 and their inverses, then one can compute in time O(l2n)a word δtp1p2···pkrepresenting Y, such that each pi∈Sym2n−2is either a symmetric polygonal braid ΣP, or the product of two commuting polygonal braids ΣP1ΣP2such that a rotation of 180 degrees permutes ΣP1and ΣP2. Moreover, |t| ≤ land k≤ln/2. Proof. The way to obtain the word p1···pkis just the computation of the left normal form of Yin BB 2n−2. It is shown in [28] that the set of symmetric non-crossing partitions of the (2n−2)-nd roots of unity (the symmetric simple elements in BB 2n−2) is a sublattice of the whole lattice of non-crossing partitions. This implies that the Garside structure of BB 2n−2 restricts to a Garside structure on Sym2n−2. Therefore, since δ∈Sym2n−2, the greatest common divisor of Yand any power of δis also symmetric, and hence every factor in the left normal form of Yis symmetric. By [4], the left normal form of Ycan be computed in time O(l2n). Once that it is computed, each non-δfactor is the product of mutually commuting polygonal braids, and the union of these polygons must be symmetric. Hence, each of these polygons is either symmetric, or it belongs of a pair of polygons which are permuted by a rotation of 180 degrees, so the result follows. Finally, notice that the left normal form of Yhas the form δty1···yswith |t| ≤ land s≤l. Now every yicontains at most one symmetric polygonal braid, namely the one containing the origin. The remaining polygonal braids of yicome in pairs. The symmetric polygonal braid, if it exists, involves at least two punctures, and each pair of polygonal braids involves at least 4 punctures. Hence yican be decomposed into a product of at most 1 + (2n−4)/4 = n/2 factors of the form pj. Since s≤l, one finally obtains k≤ln/2, as we wanted to show. Lemma 25. Let Y∈Sym2n−2be given as a word of length lin the band generators and their inverses, and let Y=δtp1···pkbe the decomposition given in Lemma 24. Then one obtains a word in the Artin generators and their inverses representing ρ(θ(Y)) as follows. 1. Each δ∈BB 2n−2should be replaced by ρ(θ(δ)) = ε∈BA n. 2. If piis the product of two polygonal braids ΣP1ΣP2, where the vertices of the polygons are {ζi1,...,ζid}and {−ζi1,...,−ζid}respectively, let k∈ {0, . . . , n −2}be such that {ζi1+k,...,ζid+k}={ζj1,...,ζjd}with 1≤j1<··· < jd< n. Then pishould be replaced by ρ(θ(ΣP1ΣP2)) = εkσ1    jd−1 Y i=j1+1 (i6=jk∀k) σ−1 i    (σjdσjd−1···σj1+1)σ−1 1ε−k. 3. If piis a symmetric polygonal braid ΣP, and the vertices of the polygon Pare {ζj1,...,ζjd,−ζj1,...,−ζjd}, 21 with 1≤j1<···< jd< n, then pishould be replaced by ρ(θ(ΣP)) = σ1    jd−1 Y i=j1+1 (i6=jk∀k) σ−1 i    (σjdσjd−1···σ1)σ1(σ−1 2···σ−1 j1)σ−1 1. Proof. Consider the element α=sn−1sn−2···s1∈ A(Bn−1). It is represented in the central picture of Figure 11. On the one hand, by Lemma 20 one has: ρ(α) = σn−1σn−2···σ3(σ1σ2σ−1 1)σ2 1=σ1(σn−1σn−2···σ1) = ε. On the other hand, Lemma 22 together with presentation (2) tell us that θ′(α) = (an−1,n−2a2n−2,2n−3)(an−2,n−3a2n−3,2n−4)···(a2,1an+1,n)an,1 = (a2n−2,2n−3a2n−3,2n−4···an+1,n)(an−1,n−2an−2,n−3···a2,1)an,1 = (a2n−2,2n−3a2n−3,2n−4···an+1,n)an,n−1(an−1,n−2an−2,n−3···a2,1) = δ. Therefore, since θ′=θ−1, one has ρ(θ(δ)) = ρ(α) = εand the first case holds. Figure 11: A geometric interpretation of ρ(θ(δ)) = ε. Now suppose that piis the product of two polygonal braids ΣP1ΣP2, where the vertices of the polygons are {ζi1,...,ζid}and {−ζi1,...,−ζid}. Notice that conjugation by δin BB 2n−2 rotates the base points, increasing each index by one. Therefore, since P1and P2belong to a non-crossing partition, there exists some k∈ {0,...,n−2}such that the rotation induced by δktransforms {P1, P2}into {P′ 1, P′ 2}, where the vertices of P′ 1belong to {ζ1,...,ζn−1}. Then ΣP1ΣP2=δkΣP′ 1ΣP′ 2δ−k. Since ρ(θ(δ)) = ε, in order to compute ρ(θ(ΣP1ΣP2)) it suffices to know the value of ρ(θ(ΣP′ 1ΣP′ 2)). See an example in Figure 12. Let ζj1,...,ζjdbe the vertices of P′ 1in increasing order, as in the statement. For simplicity of notation, denote j∗=j+n−1 for j= 1,...,n−1. The computation goes as follows: ΣP′ 1ΣP′ 2= (ajd,jd−1ajd−1,jd−2···aj2,j1)(aj∗ d,j∗ d−1aj∗ d−1,j∗ d−2···aj∗ 2,j∗ 1) = (ajd,jd−1aj∗ d,j∗ d−1)···(aj2,j1aj∗ 2,j∗ 1) = 2 Y i=d (aji,ji−1aj∗ i,j∗ i−1), 22 Figure 12: Translating pairs of symmetric polygonal braids in BB 2n−2to Artin generators in BA n. where the index idecreases from dto 2. Now one can check using Lemma 22 and presentation 2, or just by drawing the corresponding pictures, that for 1 ≤u < v < n one has θ′((s−1 u+1s−1 u+2 ···s−1 v−1)(svsv−1···su+1)) = av,uav∗,u∗. Hence, since θ′=θ−1, one obtains: θ(ΣP′ 1ΣP′ 2) = 2 Y i=d (s−1 ji−1+1s−1 ji−1+2 ···s−1 ji−1)(sjisji−1···sji−1+1). Notice that sicommutes with sjif |i−j|>1, hence all positive letters in the above formula can be collected to the right (the only exception would appear if ji−1and jiare consecutive for some i, but in that case the corresponding negative factor is empty). It follows that: θ(ΣP′ 1ΣP′ 2) = 2 Y i=d (s−1 ji−1+1s−1 ji−1+2 ···s−1 ji−1)!(sjdsjd−1· · · sj1+1). Also, the d−1 factors made by negative letters commute with each other, so one finally obtains: θ(ΣP′ 1ΣP′ 2) = d Y i=2 (s−1 ji−1+1s−1 ji−1+2 ···s−1 ji−1)!(sjdsjd−1· · · sj1+1). =    jd−1 Y i=j1+1 (i6=jk∀k) s−1 i    (sjdsjd−1···sj1+1). Now we must apply ρto the above element. Notice that all indices are greater than 1, so this will replace s2by σ1σ2σ−1 1and siby σifor i > 2. This is equivalent to replacing siby σ1σiσ−1 1 for every i > 1. Hence, applying ρreduces to replacing each siby σi, and then conjugating the whole element by σ−1 1. That is, ρ(θ(ΣP′ 1ΣP′ 2)) = σ1    jd−1 Y i=j1+1 (i6=jk∀k) σ−1 i    (σjdσjd−1···σj1+1)σ−1 1, 23 and ρ(θ(ΣP1ΣP2)) is precisely as we stated. It remains to show the third case, in which piis a single symmetric polygonal braid ΣP, where the vertices of Pare {ζj1,···ζjd,−ζj1,· · ·−ζjd}={ζj1,···ζjd, ζj1+n−1,···ζjd+n−1}. An example can be seen in Figure 13. Figure 13: Translating a single symmetric polygonal braid in BB 2n−2to Artin generators in BA n. Recall that j∗=j+n−1 for j= 1,...,n−1. In this case one has ΣP= (aj∗ d,j∗ d−1aj∗ d−1,j∗ d−2···aj∗ 2,j∗ 1)aj∗ 1,jd(ajd,jd−1ajd−1,jd−2···aj2,j1) = (aj∗ d,j∗ d−1aj∗ d−1,j∗ d−2···aj∗ 2,j∗ 1) (ajd,jd−1ajd−1,jd−2···aj2,j1)aj∗ 1,j1. One can apply the reasoning of the previous step to the first two factors, so it only remains to compute ρ(θ(aj∗ 1,j1)). This is done by noticing that aj∗ 1,j1= (aj1,j1−1aj∗ 1,j∗ 1−1)(aj1−1,j1−2aj∗ 1−1,j∗ 1−2)···(a2,1an+1,n)·an,1· ·(a−1 2,1a−1 n+1,n)···(a−1 j1−1,j1−2a−1 j∗ 1−1,j∗ 1−2)(a−1 j1,j1−1a−1 j∗ 1,j∗ 1−1), which yields θ(aj1,j∗ 1) = (θ′)−1(aj1,j∗ 1) = (sj1···s2)s1(s−1 2···s−1 j1). Since applying ρreduces to replacing s1by σ2 1, then siby σifor i > 1, and then conjugating everything by σ−1 1, one obtains: ρ(θ(aj1,j∗ 1)) = σ1(σj1···σ2)σ2 1(σ−1 2···σ−1 j1)σ−1 1. Therefore ρ(θ(ΣP)) = σ1    jd−1 Y i=j1+1 (i6=jk∀k) σ−1 i    (σjdσjd−1···σj1+1)(σj1···σ2)σ2 1(σ−1 2···σ−1 j1)σ−1 1, which is precisely the formula in the statement, so the proof is finished. 24 4.2.2 Using symmetric braids to solve the conjugacy search problem Recall that we are given X∈BA nas a word in the Artin generators σ1,...,σn−1and their inverses, and we know that Xis conjugate to εkfor some k6= 0. This means that the permutation πXconsists of the k-th power of a cycle of length n−1, that is πX= (a)(b1··· bn−1)k, where a6=bifor every i. The easy case happens when kis a multiple of n−1, say k= (n−1)t. Then εk= ∆2t, so X is conjugate to a power of ∆2. But since ∆2is a central element, this implies that X= ∆2t. Hence X=εkand we are done. We can then assume that kis not a multiple of n−1. This means that the only puncture which is fixed by Xis the a-th one. If we denote C1=σ[a→2], it clearly follows that Y=C−1 1XC1 fixes the second strand, that is, Y∈Pn,2. Notice also that ε∈Pn,2, so εk∈Pn,2. This means that Yand εkare two elements in Pn,2which are conjugate in BA n. Fortunately, they are also conjugate in Pn,2, as it is shown in the following result. Lemma 26. If Y, Z ∈Pn,2are conjugate braids whose permutations have a single fixed point (namely 2), then for every conjugating element C∈BA nsuch that C−1Y C =Z, one has C∈Pn,2. Proof. Let j=πC(2). If j6= 2, then πY C (2) = πC(πY(2)) = πC(2) = j, while πCZ(2) = πZ(πC(2)) = πZ(j)6=j(since the only fixed point of πZis 2, and j6= 2). This contradicts the assumption Y C =CZ, so we must have πC(2) = 2, that is C∈Pn,2. As a consequence, every conjugating element from Yto εk, when kis not a multiple of n−1, must belong to Pn,2. Therefore, finding a conjugating element from Yto εkin BA nreduces to solving the conjugacy search problem in Pn,2for conjugates of εk. Our strategy consists of applying θ′◦ρ−1, solving the resulting problem in Sym2n−2, and then mapping the solution back to Pn,2using ρ◦θ. Recall from Lemma 25 that ρ(θ(δ)) = ε, hence θ′(ρ−1(ε)) = δ∈Sym2n−2. Therefore we must solve the conjugacy search problem in Sym2n−2for θ′(ρ−1(Y)) and δk. Recall that, as a consequence of [28], the group Sym2n−2has a Garside structure which is the restriction of the Birman-Ko-Lee structure of BB 2n−2. The Garside element of this structure is hence δ, so the conjugacy search problem for powers of δ∈Sym2n−2can be solved very fast, by applying iterated cyclings and decyclings. But one does not need to care about the Garside structure of Sym2n−2, since one can directly work with the Garside structure of BB 2n−2, as it is shown in the following result. Lemma 27. Let Z∈Sym2n−2⊂BB 2n−2be given as a word of length lin the band generators and their inverses. Suppose that Zis conjugate to δkfor some k6= 0. Then by applying at most (2n−3)lcyclings and decyclings to Z, using the Garside structure of BB 2n−2, one conjugates Zto δkand the conjugating element that is obtained belongs to Sym2n−2. Proof. By [5], by applying at most (2n−3)lcyclings and decyclings to Zone obtains an element which has minimal canonical length. Since Zis conjugate to δk, and δis the Garside element of BB 2n−2, it follows that the resulting element is precisely δk. Hence one obtains C∈BB 2n−2such that C−1ZC =δk. 25 [22] J. Gonz´alez-Meneses, The nth root of a braid is unique up to conjugacy, Algebraic and Geometric Topology 3(2003), 1103-1118. [23] S. P. Kerckhoff, The Nielsen realization problem, Ann. of Math. (2) 117 (1983), no. 2, 235–265. [24] B. de Ker´ekj´art´o, ¨ Uber die periodischen Transformationen der Kreisscheibe und der Kugelfl¨ache, Math. Annalen 80 (1919), 3-7. [25] E-K Lee and S.J. Lee, Conjugacy classes of periodic braids, preprint arXiv:math.GT/0702349. [26] H. Morton and R. Hadji, Conjugacy for positive periodic permutation braids, preprint arXiv math.GT/0312209. [27] W. Magnus, A. Karass and D. Solitar, Combinatorial Group Theory, 1066, John Wiley and Sons. [28] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997) 195-222. [29] J.-Y. Shi, The enumeration of Coxeter elements. J. Algebraic Combin. 6(1997), no. 2, 161–171. Joan S. Birman Volker Gebhardt Juan Gonz´alez-Meneses Department of Mathematics, School of Computing and Mathematics, Departamento de ´ Algebra, Barnard College and Columbia University, University of Western Sydney, Universidad de Sevilla, 2990 Broadway, Locked Bag 1797, Apdo. 1160, New York, New York 10027, USA. Penrith South DC NSW 1797, Australia, 41080 Sevilla, Spain. [email protected] [email protected] [email protected] 32