Conjugacy in Garside Groups III: Periodic braids

a Xi :ma h/0609616 2 [ma h.GT] 22 Feb 2007 Conjugacy in Ga side G oups III: Pe iodic b aids Joan S. Bi man∗Volke Gebha d Juan Gonz´alez-Meneses† Feb ua y 19, 2007 Abs ac An elemen in A in’s b aid g oup Bnis said o be pe iodic i some powe o i lies in he cen e o Bn. In his pape we p o e ha all p e iously known algo i hms o sol ing he conjugacy sea ch p oblem in Bna e exponen ial in he b aid index n o he special case o pe iodic b aids. We o e come his di icul y by pu ing o wo k se e al known isomo phisms be ween Ga side s uc u es in he b aid g oup Bnand o he Ga side g oups. This allows us o ob ain a polynomial solu ion o he o iginal p oblem in he spi i o he p e iously known algo i hms. This pape is he hi d in a se ies o pape s by he same au ho s abou he conjugacy p oblem in Ga side g oups. They ha e a uni ied goal: he de elopmen o a polynomial algo i hm o he conjugacy decision and sea ch p oblems in Bn, which gene alizes o o he Ga side g oups whene e possible. I is ou hope ha he me hods in oduced he e will allow he gene aliza ion o he esul s in his pape o all A in-Ti s g oups o sphe ical ype. 1 In oduc ion Gi en a g oup, a solu ion o he conjugacy decision p oblem is an algo i hm ha de e mines whe he wo gi en elemen s a e conjuga e o no . On he o he hand, a solu ion o he conjugacy sea ch p oblem is an algo i hm ha inds a conjuga ing elemen o a gi en pai o conjuga e elemen s. In §1.4 o [6] we p esen ed a p ojec o ind a polynomial solu ion o he conjugacy decision p oblem and he conjugacy sea ch p oblem in he pa icula case o A in’s b aid g oup, ha is, he A in-Ti s g oup o ype An−1, wi h i s classical o A in p esen a ion [1]: (1) BA n:σ1,...,σn−1 σiσj=σjσii |i−j|>1, σiσjσi=σjσiσji |i−j|= 1.. One o he s eps in he men ioned p ojec asks o a polynomial solu ion o he abo e conju- gacy p oblems o special ype o elemen s in he b aid g oups, called pe iodic b aids. This is achie ed in he p esen pape . Mo e p ecisely, i we deno e by |w| he le e leng h o a wo d win σ1,...,σn−1and hei in e ses, we will p o e: ∗Pa ially suppo ed by he U.S.Na ional Science Founda ion, unde G an DMS-0405586. †Pa ially suppo ed by MTM2004-07203-C02-01 and FEDER. 1 Theo em 1. Le wXand wYbe wo wo ds in he gene a o s σ1,...,σn−1and hei in e ses, ep esen ing wo b aids X, Y ∈BA n, and le l= max{|wX|,|wY|}. Then he e is an algo i hm o complexi y O(l3n2log n)which does he ollowing. (1) I de e mines whe he Xand Ya e pe iodic. (2) I yes, i de e mines whe he hey a e conjuga e. (3) I yes, i inds a b aid C∈BA nsuch ha Y=C−1XC. He e is a guide o his pape . In Sec ion 2, we will e iew wha is known and explain why s eps (1) and (2) o Theo em 1 ollow easily om he wo k in [17, 24, 22]. On he o he hand, in Sec ion 3 we show ha he p e iously known solu ions o he conjugacy sea ch p oblem in he A in-Ti s g oup o ype An−1p esen unexpec ed di icul i es, which esul in exponen ial complexi y o pe iodic b aids. Thus hey do no mee he equi emen s o Theo em 1. A new idea allows us o o e come he di icul y. We ha e shown ha he app oach using he classical Ga side s uc u e does no wo k. The new idea is o pu o wo k he o he known Ga side s uc u e on he b aid g oups and in addi ion o conside a ce ain subg oup o he b aid g oup ha a ises in he cou se o ou wo k, and use wo known Ga side s uc u es on i . This is accomplished in Sec ion 4, whe e we gi e a solu ion o he conjugacy sea ch p oblem o pe iodic b aids which has he s a ed polynomial complexi y. Sec ion 4 di ides na u ally in o wo subsec ions, acco ding o whe he a gi en pe iodic b aid is conjuga e o a powe o δo ε, wo b aids ha a e de ined in Sec ion 2 below. The p oo in he wo cases a e ea ed in Sec ions 4.1 and 4.2 espec i ely. Finally, in Sec ion 5 we compa e ac ual unning imes o he algo i hms de eloped in Sec ion 4 o he ones o he bes p e iously known algo i hm. Rema k 2. We lea ned om D. Bessis ha he has cha ac e ized he conjugacy classes o pe iodic elemen s o all A in-Ti s g oups o sphe ical ype. We hope ha his cha ac e iza- ion will allow he gene aliza ion o bo h he echniques and he esul s o his pape o all o he A in-Ti s g oups o sphe ical ype. Acknowledgemen s: We a e g a e ul o D. Bessis o use ul discussions abou his wo k in [2] and his o hcoming esul s, o J. Michel o poin ing ou ha ou Co olla ies 12 and 15 we e known o specialis s in Coxe e g oups, and also o H. Mo on o showing us he algo i hm in [26]. 2 Known esul s imply s eps (1) and (2) o Theo em 1 Ou wo k begins wi h a e iew o known esul s. Ga side g oups we e in oduced by Deho noy and Pa is in [15]. The main examples o Ga side g oups a e A in-Ti s g oups o sphe ical ype, in pa icula , A in b aid g oups. In his pape we will use wo known Ga side s uc u es in he A in-Ti s g oup o ype An−1, and also one Ga side s uc u e in he A in-Ti s g oup o ype Bm. Al hough we e e o [6] o a de ailed desc ip ion o Ga side s uc u es, we ecall he e ha such a s uc u e in a g oup Gis gi en by a la ice o de on i s elemen s, oge he wi h a dis inguished elemen o G, called he Ga side elemen , which is usually deno ed by ∆. This pa ial o de and his elemen ∆ mus sa is y se e al sui able condi ions [6]. 2 The classical Ga side s uc u e in he b aid g oups is ela ed o he p esen a ion (1). The posi i e b aids a e hose which can be w i en as a wo d in σ1, . . . , σn−1(no using hei in e ses). The la ice o de is de ined by saying ha X4Yi X−1Yis a posi i e b aid (we will say ha Xis a p e ix o Y). The e a e special elemen s called simple b aids which a e hose posi i e b aids in which any wo s ands c oss a mos once. The Ga - side elemen ∆ is he posi i e b aid in which any wo s ands c oss exac ly once, ha is, ∆ = σ1(σ2σ1)(σ3σ2σ1)···(σn−1···σ1). I is also called he hal wis , since i s geome ical ep esen a ion co esponds o a hal wis o he ns ands. Fo e e y b aid X∈BA n, gi en as a wo d o le e leng h l, he e exis s a le no mal o m, which is a unique way o de- compose he b aid as X= ∆px1···x , whe e pis maximal and each xiis a simple b aid, namely he maximal simple p e ix o xi···x . This le no mal o m can be compu ed in ime O(l2nlog n) [19]. A in p o ed in [1] ha he cen e o BA nis in ini e cyclic and gene a ed by he ull wis ∆2= (σ1σ2···σn−1)no he b aid s ands. I he b aid g oup is ega ded as he mapping class g oup o he n- imes punc u ed disc D2 n, hen ∆2is a Dehn wis abou a cu e which lies in a colla neighbo hood o he bounda y ∂D2 nand is pa allel o i . An elemen X∈BA n is said o be pe iodic i some powe o Xis a powe o ∆2. Pe iodic b aids can be hough o as o a ions o he disc. Indeed, he e is a classical esul by Eilenbe g [17] and K´e ´ekj´a ´o[24] (see also [12]) showing ha an au omo phism o he disc which is a oo o he iden i y (a pe iodic au omo phism) is conjuga e o a o a ion. Since a ini e o de mapping class can always be ealized by a ini e o de homeomo phism [23], his implies ha a pe iodic b aid is conjuga e o a o a ion. I is no di icul o see ha a b aid can be ep esen ed by a o a ion o D2i and only i i is conjuga e o a powe o one o he wo b aids ep esen ed in Figu e 1, ha is, δ=σn−1σn−2···σ1and ε=σ1(σn−1σn−2···σ1). (I we need o speci y he numbe o s ands, we will w i e δ=δnand ε=εn.) Rema k 3. The b aid εde ined in Figu e 1 has a ixed s and, namely s and 2. The e a e, o be su e, b aids which a e conjuga e o εin which he ixed s and is he i s one o he las one, seemingly mo e na u al choices. Howe e , εis a simple b aid, and (as we shall p o e in P oposi ion 13 below) he e is no simple b aid which is conjuga e o εand which ixes ei he he i s o he las s and. This is why we decided o use ε, which ixes he second s and, as a ep esen a i e o i s conjugacy class. And his is also he eason why, in Sec ion 4.2 below, we iden i y he A in-Ti s g oup o ype Bn−1wi h he subg oup o he n-s and b aid g oup o med by hose b aids which ix he second s and, a choice ha will su ely seem awkwa d o specialis s. The heo em o Eilenbe g and K´e ´ekj´a ´o can hen be es a ed as ollows. Theo em 4. [17, 24] A b aid Xis pe iodic i and only i i is conjuga e o a powe o ei he δo ε. No ice ha δn=εn−1= ∆2. Since ∆2belongs o he cen e o BA n, his immedia ely gi es an e icien algo i hm o check whe he a b aid is pe iodic. Co olla y 5. A b aid X∈BA nis pe iodic i and only i ei he Xn−1o Xnis a powe o ∆2. P oo . We only need o p o e ha he condi ion is necessa y. Suppose ha Xis pe iodic. By Theo em 4, Xis conjuga e o a powe o ei he δo ε. In he i s case, X=C−1δkC o 3 Figu e 1: The pe iodic elemen s δand ε. some C∈BA n. Then Xn=C−1δknC=C−1∆2kC= ∆2k, whe e he las equali y holds since ∆2is cen al. In he second case, X=C−1εkC, so ha Xn−1=C−1εk(n−1)C=C−1∆2kC= ∆2k. A e his esul , one can de e mine whe he Xis pe iodic, and also ind he powe o δo ε which is conjuga e o X, by he ollowing algo i hm. Algo i hm A. Inpu : A wo d win A in gene a o s and hei in e ses ep esen ing a b aid X∈BA n. 1. Compu e he le no mal o m o Xn−1. 2. I i is equal o ∆2k, e u n ‘Xis pe iodic and conjuga e o εk’. 3. Compu e he le no mal o m o Xn. 4. I i is equal o ∆2k, e u n ‘Xis pe iodic and conjuga e o δk’. 5. Re u n ‘Xis no pe iodic’. P oposi ion 6. The complexi y o Algo i hm A is O(l2n3log n), whe e lis he le e leng h o w. P oo . Algo i hm A compu es wo no mal o ms o wo ds whose leng hs a e a mos nl. By [19], hese compu a ions ha e complexi y O((nl)2nlog n), and he esul ollows. We ema k ha i one knows, a p io i, ha he b aid Xis pe iodic, hen one can de e mine he powe o δo εwhich is conjuga e o Xby a as e me hod: Obse e ha he exponen sum o a b aid X, w i en as a wo d in he gene a o s σ1,...,σn−1and hei in e ses is well de ined, since he ela ions in (1) a e homogeneous. The exponen sum is u he mo e in a ian unde conjugacy, hence e e y conjuga e o δkhas exponen sum k(n−1), whe eas e e y conjuga e o εkhas exponen sum kn. Mo eo e , he exponen sum de e mines he conjugacy class o a pe iodic b aid: Lemma 7. (P oposi ion 4.2 o [22]) Le Xbe a pe iodic b aid. Then Xis conjuga e o δk ( esp. εk) i and only i Xhas exponen sum k(n−1) ( esp. kn). 4 Compu ing he exponen sum o a wo d o leng h lhas complexi y O(l). Hence, once i is known ha wo gi en b aids a e pe iodic, he conjugacy decision p oblem akes linea ime. 3 Known algo i hms a e no e icien o pe iodic b aids We ha e al eady de e mined all conjugacy classes o pe iodic b aids, and we ha e seen ha he conjugacy decision p oblem o hese b aids can be sol ed e y as . I is hen na u al o wonde whe he his is also ue o he conjugacy sea ch p oblem. The i s na u al ques ion is: A e he exis ing algo i hms o he conjugacy sea ch p oblem e icien o pe iodic b aids? The bes known algo i hm o sol e he conjugacy decision p oblem and also he conjugacy sea ch p oblem in b aid g oups (and in e e y Ga side g oup) is he one in [21], which consis s o compu ing he ul a summi se o a b aid, de ined as ollows. Deno e by τ he inne au omo phism ha is de ined by conjuga ion by ∆. Gi en Y∈BA nwhose le no mal o m is ∆py1···y , we de ine i s canonical leng h as ℓ(Y) = , and call he conjuga es c(Y) = ∆py2···y τ−p(y1) and d(Y) = ∆pτp(y )y2···y −1o Yi s cycling espec i ely i s decycling. Fo e e y X∈BA n, he ul a summi se USS(X) is he se o conjuga es Yo Xsuch ha ℓ(Y) is minimal and c (Y) = Y o some ≥1. I is explained in [21] how he compu a ion o USS(X) sol es he conjugacy decision and sea ch p oblems in Ga side g oups. The complexi y o he conjugacy sea ch algo i hm gi en in [21] is p opo ional o he size o USS(X), so i one is in e es ed in complexi y, i is essen ial o know how la ge he ul a summi se s o pe iodic b aids a e. I hey u ned ou o be small, he algo i hm in [21] would be e icien , bu we will see in his sec ion ha he sizes o ul a summi se s o pe iodic b aids a e in gene al exponen ial in n. Mo e p ecisely, i was shown by Coxe e in 1934 [13, Theo em 11], ha in any ini e Coxe e g oup, any wo elemen s which a e he p oduc o all s anda d gene a o s, in a bi a y o de , a e conjuga e. Applied o ou case, one sees ha he elemen s o USS(δ) a e in bijec ion wi h he elemen s o he abo e kind, in he symme ic g oup Σn. One can coun he numbe o di e en elemen s, and i ollows ha #(USS(δ)) = 2n−2. The same esul is shown in [9, Chap e V, §6. P oposi ion 1], in he mo e gene al case in which he Coxe e g oup is de ined by a ee, and also in [29, Lemma 3.2] and in [26, Theo em 2]. Mo eo e , i can be seen om he p oo in [9] ha any wo elemen s in USS(δ) a e conjuga e by a sequence o special conjuga ions, ha we deno e pa ial cyclings in [6]. Conce ning he elemen s in USS(ε), in [16, P oposi ion 9.1] i is shown ha any wo such elemen s a e conjuga e by a sequence o pa ial cyclings. I also ollows om [16] ha e e y elemen in USS(ε) is ep esen ed by a wo d o leng h n, which is he p oduc o all n−1 gene a o s, in some o de , wi h one o he gene a o s epea ed. One can also coun he numbe o di e en elemen s o his kind, o ob ain ha #(USS(ε)) = (n−2)2n−3. The abo e a gumen s show ha he sizes o USS(δ) and USS(ε) a e exponen ial wi h espec o he numbe o s ands, hence he algo i hm in [21] is no polynomial o conjuga es o hese b aids. In his pape we shall s udy USS(δ) and USS(ε) in a new way. Mo e p ecisely, in Co olla ies 12 and 15 we will show ha #(USS(δ)) = 2n−2and #(USS(ε)) = (n−2)2n−3 jus by looking a he pe mu a ions induced by hei elemen s. This will also p o ide a as solu ion o he conjugacy sea ch p oblem in he pa icula cases o conjuga es o δo ε. 5 Once shown ha he algo i hm in [21] is no polynomial, in gene al, o pe iodic b aids, in Sec ion 4 we will gi e a p ocedu e o sol e he conjugacy sea ch p oblem o all pe iodic b aids in polynomial ime. Le us hen s udy he ul a summi se s o δand ε. Fi s , we ecall ha he ac o s in a le no mal o m a e simple b aids, which a e in bijec ion wi h he elemen s o he symme ic g oup Σn. Mo e p ecisely, e e y b aid X, being a mapping class g oup o he n- imes punc u ed disc, de e mines a pe mu a ion πXo he npunc u es. Con e sely, he e is exac ly one simple b aid o each pe mu a ion. We will hen de e mine simple elemen s by hei pe mu a ions, w i en as a p oduc o disjoin cycles. Fo ins ance, he pe mu a ion associa ed o δis πδ= (1 2 ··· n), and he pe mu a ion associa ed o εis πε= (2)(1 3 4 ··· n). Rema k 8. Al hough we desc ibed b aids as mapping classes, we will no adop he usual con en ion o composi ions o maps. We conside b aids as ac ing on he punc u es om he igh . This means ha he b aid σ1σ2 i s swaps he punc u es in posi ions 1 and 2, and hen he punc u es in posi ions 2 and 3. Hence πσ1σ2= (132). Rema k 9. The pe mu a ion associa ed o a simple b aid sde e mines he pai s o s ands ha c oss in s. Mo e p ecisely, wo s ands iand j(i < j) c oss in si and only i he induced pe mu a ion e e ses hei o de , ha is, i πs(i)> πs(j). Fo simplici y o no a ion le us de ine, o 1 ≤i < j ≤n, he b aids σ[i→j]=σiσi+1 ···σj−1 and σ[j→i]=σj−1σj−2···σi. No ice ha σ[k→l](no ma e which subindex is bigge ) is he sho es posi i e b aid sending he punc u e k o he punc u e l. Le us cha ac e ize he elemen s in USS(δ). P oposi ion 10. An elemen s∈BA nbelongs o USS(δ)i and only i i is simple and i s pe mu a ion πsis a cycle o he o m: πs= (1 u1u2···u n d d −1···d1), o some u1< u2<···< u and some d > d −1>···> d1, wi h , ≥0and + + 2 = n. Mo eo e , in his case α−1sα =δ, whe e α=σ[d1→1] σ[d2→1] ···σ[d →1]. P oo . Fi s no ice ha , since δis simple, all elemen s in USS(δ) a e simple, so ha by he de ini ion o a simple elemen hey can be cha ac e ized by hei pe mu a ions. Ac ually, USS(δ) is he se o simple conjuga es o δ. No ice also ha πδis a single cycle o leng h n. Since conjuga ion o b aids in BA nimplies conjuga ion o hei co esponding pe mu a ions, i ollows ha he elemen s in USS(δ), which a e conjuga es o δ, a e simple elemen s de e mined by a cycle o leng h n. Mo eo e , i s∈USS(δ) hen sn= ∆2, which is a posi i e b aid in which any wo s ands c oss exac ly wice. Le s∈USS(δ). I s pe mu a ion can be w i en as πs= (1 u1u2· · · u n d d −1··· d1), whe e , ≥0 and + + 2 = n. We mus show ha u1<···< u and d >···> d1. See in Figu e 2 an example o wo simple b aids whose pe mu a ions a e cycles o leng h n, so he pe mu a ions a e conjuga e in he symme ic g oup, bu one o he b aids sa is ies he abo e inequali ies and he o he one does no . 6 Figu e 2: Two simple b aids in BA 8whose pe mu a ions a e cycles o leng h 8. By P oposi- ion 10, he i s one is conjuga e o δand he second one is no . No ice ha he exponen sum o he second one (i.e. he numbe o c ossings o he le e leng h, in his case) is 9, while he exponen sum o conjuga es o δ∈BA 8is 7. Suppose ha ui> ui+1 o some i, whe e 1 ≤i < , and conside he s ands 1 and u1. We will see ha hese wo s ands c oss mo e han wice in sn. Indeed, one has 1 < u1, bu in si hese s ands end a uiand ui+1, espec i ely. Since ui> ui+1, his means ha hey ha e c ossed a leas once in si. Now in s hese wo s ands end a u and n, espec i ely, and since u is necessa ily less han n, hey ha e c ossed again. Nex , in s +1 hey end a nand d (o nand 1 i he e a e no dj’s), so hey ha e c ossed one mo e ime. This means ha in s +1 he s ands 1 and u1c oss a leas h ee imes, showing ha sncanno be equal o ∆2, a con adic ion. The e o e u1<···< u . Simila ly, i we had di+1 < di o some i, hen s ands nand d would c oss mo e han wice in sn, which is impossible. The e o e d >···> d1. Con e sely, suppose ha sis simple and πs= (1 u1u2··· u n d d −1··· d1) o some u1<···< u and d >···> d1. We will show ha sis conjuga e o δin a cons uc i e way, by inding a conjuga ing elemen . Fi s no ice ha i = 0 hen πs= (1 2 ··· n) = πδ. Since simple elemen s a e de e mined by hei pe mu a ions, his means ha s=δ. Hence we can assume ha > 0. Deno e k=d1. One has πs= (1 2 ··· k−1uk−1··· u n d ··· d2k). A schema ic pic u e o he i s ks ands o scan be seen in Figu e 3. We will conjuga e s by σ[k→1], so we conside s′=σ−1 [k→1] s σ[k→1]. Recall ha wo s ands iand j(i < j) c oss in si and only i πs(i)> πs(j). Then we can easily check ha he s and o sending a k ( ha is, he s and d2i > 1 o he s and ni = 1) does no c oss he s ands ending a 1,2,...,k−1 ( ha is, he s ands k, 1,2,...,k−2, espec i ely). This implies ha s σ[k→1] is a simple b aid. Mo eo e , one can also check ha he s and ko s( hus he s and ko s σ[k→1]) c osses he s ands k−1, k −2,...,1, hence s′=σ−1 [k→1] s σ[k→1] is a simple b aid. Since he pe mu a ion associa ed o σ[k→1] is (1 2 ··· k), i ollows ha πs′= (1 2 ··· k−1kuk−1··· u n d ··· d2). We can con inue his p ocess, by ecu ence on , conjuga ing by elemen s o he o m σ[di→1] and ob aining new simple conjuga es o swhose pe mu a ions ha e mo e indices be ween 1 and na each s ep, un il we ge he pe mu a ion (1 2 ··· n), ha is, un il we ob ain δ. In his 7 way we ha e shown ha i sis a simple elemen wi h he pe mu a ion gi en in he s a emen , hen α−1sα =δ, whe e α=σ[d1→1] σ[d2→1] ···σ[d →1]. The e o e, we ha e de e mined he elemen s in USS(δ) in e ms o hei pe mu a ions. Figu e 3: Conjuga ing s o s′. Rema k 11. The abo e elemen αis simple, hence all elemen s in USS(δ) a e conjuga e o δby a simple elemen . Co olla y 12. I δ=σn−1···σ1∈BA n hen #(USS(δ)) = 2n−2. P oo . The elemen s in USS(δ) a e cha ac e ized by he pe mu a ion gi en in he abo e esul , which is i sel cha ac e ized by he sequence 1 < u1<··· < u < n. The numbe o possible sequences is equal o he numbe o subse s o {2,...,n−1}which is p ecisely 2n−2. Now le us do he same o USS(ε). P oposi ion 13. An elemen s∈BA nbelongs o USS(ε)i and only i i is simple and πs= (a)(1 u1u2··· u n d d −1··· d1), o some u1< u2<···< u and some d > d −1>···> d1, wi h , ≥0and + + 3 = n. No ice ha a6= 1, n. Mo eo e , in his case one has β−1sβ =ε, whe e β=σ[d1→1] σ[d2→1] ···σ[d →1] σ[b→2] and b=a+ −max{i:di< a}, 8 P oo . Since εis simple, he elemen s o USS(ε) a e p ecisely he simple conjuga es o ε; in pa icula , USS(ε) consis s o simple elemen s whose pe mu a ion is he p oduc o a cycle o leng h 1 (a ixed poin ) and a cycle o leng h n−1. Mo eo e , i s∈USS(ε) hen sn−1= ∆2, whe e any wo s ands c oss exac ly wice. Le s∈USS(ε), and le πs= (a)(x1··· xn−1). I a= 1 hen he i s s and o sdoes no c oss any o he s and. This means ha we can w i e sas a wo d in A in gene a o s in which he le e σ1does no appea . Bu in ha case e e y powe o swould sa is y he same p ope y. In pa icula , he i s s and o sn−1= ∆2would no c oss any o he s and, a con adic ion. Hence a6= 1. In he same way one shows ha a6=n. The e o e he pe mu a ion induced by scan be w i en as πs= (a)(1 u1u2··· u n d d −1··· d1). We can show ha u1<··· < u and ha d >··· > d1, using he same p oo as in P oposi ion 10. In Figu e 4 we can see an example o wo b aids whose pe mu a ions a e cycles o leng h n−1. The i s one sa is ies he abo e inequali ies and he second one does no . Figu e 4: Two simple b aids in BA 8whose pe mu a ions a e cycles o leng h 7. By P oposi- ion 13, he i s one is conjuga e o εand he second one is no . As in Figu e 2, he exponen sums o he wo b aids di e ; he exponen sum o second one is 12, while he exponen sum o conjuga es o ε∈BA 8is 8. Now le sbe a simple elemen such ha πs= (a)(1 u1u2··· u n d d −1··· d1) o some u1< u2<···< u , some d > d −1>···> d1and some a6= 1 o n. Suppose ha > 0. Simila ly o he p oo o P oposi ion 10, we will conjuga e sby σ[d1→1], and his will educe he index . Le k=d1. I a > k one has πs= (a)(1 2 ··· k−1uk−1··· u n d ··· d2k), o he wise πs= (a)(1 2 ··· a−1a+ 1 ··· k−1uk−2··· u n d ··· d2k). The pic u e in he o me case is he same as in Figu e 3, while he la e case is ep esen ed in Figu e 5. In ei he case, he s and o s ha ends a k( ha is, d2i > 1 o ni = 1) 9 Lemma 20. The map ρ:A(Bn−1)→Pn,2gi en by ρ(s1) = σ2 1,ρ(s2) = σ1σ2σ−1 1and ρ(si) = σi o i > 2, is an isomo phism. P oo . P oposi ion 5.1 in [14] p o ides an isomo phism ρ0:A(Bn−1)→Pn,1, whe e Pn,1is he subg oup o BA nconsis ing o b aids which ix he i s punc u e. This isomo phism is gi en by ρ0(s1) = σ2 1and ρ0(si) = σi o i > 1, and i was al eady known o specialis s, p io o [14]. Now we jus need o no ice ha he inne au omo phism ϕ:BA n→BA ngi en by ϕ(X) = σ1Xσ−1 1sends Pn,1isomo phically o Pn,2, and ha ϕ|Pn,1◦ρ0=ρ. Rema k 21. I is well known [14] ha Pn,2(hence A(Bn−1)) can be iden i ied wi h he b aid g oup o he open annulus D2 {0}on n−1 s ands. Indeed, an elemen X∈Pn,2 ixes he second punc u e, so i can be iso oped o a b aid whose second s and in D2×[0,1] is a s aigh line, say {0} × [0,1]. This second s and can be conside ed o be a hole o D2, so X can be ega ded as a b aid on n−1 s ands o D2 {0}. In o de o a oid con usion, we will ep esen elemen s in Pn,2∈BA nin he usual way, as hey a e ep esen ed a he bo om o Figu e 8, while elemen s o A(Bn−1) will be ep esen ed in he Bi man-Ko-Lee s yle, as b aids on D2 {0}whose base poin s a e he (n−1)-s oo s o uni y, as we can see a he op o Figu e 8. Figu e 8: The gene a o s o A(Bn−1), ep esen ed as b aids on D2 {0}, and hei images unde he isomo phism ρ:A(Bn−1)→Pn,2. Lemma 22. The map θ′:A(Bn−1)→Sym2n−2gi en by θ′(s1) = an,1and θ′(si) = ai,i−1ai+n−1,i+n−2 o i > 1, is an isomo phism. P oo . In [10], B iesko n showed ha an A in-Ti s g oup o ini e ype is he undamen al g oup o he egula o bi space o i s co esponding Coxe e g oup, ac ing as a ini e eal e lec ion g oup on a complex space. In pa icula , since he Coxe e g oup associa ed o A(Bn−1) is W= Σn−1⋉(Z/2Z)n−1, whe e he symme ic g oup ac s by pe mu ing coo dina es 16 ( ha is, Wis he signed pe mu a ion g oup), and i s co esponding hype plane a angemen is x1x2···xn−1Qi6=j(xi−xj)(xi+xj), i ollows ha A(Bn−1) = π1(XBn−1/W), whe e XBn−1={(x1,...,xn−1)∈Cn−1|xi6=±xj o i6=j;xi6= 0 o all i}. A good way o desc ibe he space XBn−1is as he se o (n−1)- uples o pai s ((x1,−x1),(x2,−x2),...,(xn−1,−xn−1)), whe e each xi∈C, any wo pai s a e dis inc , and xi6= 0 o all i. Conside ing he ac ion o W, all he abo e pai s and (n−1)- uples can be ega ded as uno de ed. Hence XBn−1/W is he con igu a ion space o 2n−2 disjoin and undis inguishable poin s in C, whose con igu a ion is in a ian unde mul iplica ion by −1. We can choose as a base poin o his space he (2n−2)-nd oo s o uni y. Hence, an elemen o i s undamen al g oup is ep esen ed by a b aid which is in a ian unde a o a ion by 180 deg ees, ha is, by a symme ic b aid in BB 2n−2. I is impo an o no e ha wo symme ic b aids ep esen he same elemen in π1(XBn−1/W) i and only i hey a e iso opic h ough symme ic b aids, hence one canno say a p io i ha wo symme ic b aids ha a e iso opic in BB 2n−2 ep esen he same elemen o π1(XBn−1/W). Fo - una ely, i is shown in [3] ha wo symme ic b aids a e iso opic in BB 2n−2i and only i hey a e iso opic h ough symme ic b aids. Tha is, i is shown ha A(Bn−1) = π1(XBn−1/W)∼ = Sym2n−2. Mo eo e , om he wo k in [3] one ob ains an isomo phism θ:Sym2n−2→ A(Bn−1), whe e elemen s o Sym2n−2a e symme ic b aids based on he (2n−2)-nd oo s o uni y, and he elemen s o A(Bn−1) a e conside ed as b aids on he annulus D2 {0}based on he (n−1)- s oo s o uni y. The isomo phism θcan be easily desc ibed geome ically, since i jus iden i ies an ipodal poin s in C. Tha is, i sends z∈C {0} o z2/|z|. This co esponds o a wo-shee ed co e ing map o C {0}, and since no s and o a symme ic b aid ouches he axis {0} × [0,1], his map is well de ined. In Figu e 9 we can see ha θ(an,1) = s1and ha θ(ai,i−1ai+n−1,i+n−2) = si o i > 1, whe e in he pic u e one has ζk=e2kπi/(2n−2) and ξk=e2kπi/(n−1). The e o e θ′=θ−1, so i is an isomo phism. By Lemmas 20 and 22 we know ha Pn,2∼ =A(Bn−1)∼ =Sym2n−2, and we also know how o ans o m any wo d in he gene a o s s1,...,sn−1o A(Bn−1) and hei in e ses, in o a wo d in ei he he A in gene a o s o Pn,2o he band gene a o s o Sym2n−2, ia he isomo phisms ρand θ′=θ−1. BA nBB 2n−2 ∪ ∪ Pn,2 ρ ←− A(Bn−1)θ′ −→ Sym2n−2. Bu in ou algo i hm we will need o ansla e any wo d in he A in gene a o s o BA n, ep esen ing an elemen o Pn,2, o a wo d in he band gene a o s o Sym2n−2, and ice e sa. Hence, we need he ollowing esul s. 17 Figu e 9: The map θ ans o ms he symme ic b aids on he le hand side o he gene a o s o A(Bn−1) on he igh hand side. Lemma 23. Le X∈Pn,2⊂BA nbe gi en as a wo d o leng h lin he A in gene a o s and hei in e ses, X=σǫ1 µ1σǫ2 µ2···σǫl µl. Fo i= 0,...,l, le Xi=σǫ1 µ1σǫ2 µ2···σǫi µiand le ki=πXi(2), ha is, he inal posi ion o he second s and o Xi. Then one ob ains a wo d in he band gene a o s and hei in e ses ep esen ing θ′(ρ−1(X)) ∈Sym2n−2, by eplacing each le e σǫi µiusing he ollowing ules: σµi→             aµi+1,µiaµi+n,µi+n−1i µi< ki−1−1, 1i µi=ki−1−1, aµi+n−1,µii µi=ki−1, aµi,µi−1aµi+n−1,µi+n−2i µi> ki−1, and σ−1 µi→             a−1 µi+n,µi+n−1a−1 µi+1,µii µi< ki−1−1, a−1 µi+n−1,µii µi=ki−1−1, 1i µi=ki−1, a−1 µi+n−1,µi+n−2a−1 µi,µi−1i µi> ki−1. Mo eo e , his algo i hm has complexi y O(l), and p oduces a wo d o leng h a mos 2l. P oo . Recall ha we a e gi en a b aid X∈BA n ha ixes he second punc u e, ha is, X∈Pn,2, w i en as a wo d in he A in gene a o s o BA nand hei in e ses. We wan o 18 w i e ρ−1(X) as a wo d in he gene a o s s1,...,sn−1and hei in e ses, and hen θ′(ρ−1(X)) as a wo d in he band gene a o s o BB 2n−2. The i s p oblem is ha Xis no gi en as a wo d in he gene a o s o Pn,2, bu in he gene a o s o BA n. We will hen use he Reidemeis e -Sch eie me hod (see Sec ion 2.3 o [27]) o decompose Xas a p oduc o elemen s in Pn,2. In o de o do his, no ice ha Pn,2is a subg oup o BA no index n. The igh cose o a b aid Zdepends on whe e i sends he second punc u e. I πZ(2) = k, we deno e by Rka ep esen a i e o he igh cose Pn,2Z∈Pn,2 BA n. Fo echnical easons, we will choose as cose ep esen a i es he elemen s R1=σ1,R2= 1 and Rk=σ−1 [k→2] =σ−1 2···σ−1 k−1i k > 2. Then, o i= 0,...,l, we de ine Xi=Rki. Tha is, Xiis he chosen ep esen a i e o Pn,2Xi∈Pn,2 BA n. No e ha X0=Xl=R2= 1. By he Reidemeis e -Sch eie me hod, one has X= l Y i=1 Xi−1σǫi µiXi−1= l Y i=1 Rki−1σǫi µiR−1 ki, whe e each o he abo e l ac o s belongs o Pn,2. No ice ha ki=ki−1, unless ei he µi=ki−1 (in which case ki=ki−1+ 1) o µi=ki−1−1 (and hen ki=ki−1−1). One can check ha , depending on µiand ki−1, each o he abo e ac o s can be w i en in e ms o he A in gene a o s and hei in e ses as ollows. I ǫi= 1, one has: (Rki−1σµiR−1 ki) =                                σ−1 2σ1σ2i 1 = µi< ki−1−1, σµi+1 i 1 6=µi< ki−1−1, 1 i µi=ki−1−1, σ2 1i 1 = µi=ki−1, (σ−1 2σ−1 3···σ−1 µi−1)σµi(σµiσµi−1···σ2) i 1 6=µi=ki−1, σ1σ2σ−1 1i 2 = µi> ki−1, σµii 2 6=µi> ki−1. I ǫi=−1, one ob ains he in e ses o he abo e, in he ollowing way: (Rki−1σ−1 µiR−1 ki) =                                σ−1 2σ−1 1σ2i 1 = µi< ki−1−1, σ−1 µi+1 i 1 6=µi< ki−1−1, σ−2 1i 1 = µi=ki−1−1, (σ−1 2σ−1 3···σ−1 µi)σ−1 µi(σµi−1···σ2) i 1 6=µi=ki−1−1, 1 i µi=ki−1, σ1σ−1 2σ−1 1i 2 = µi> ki−1, σ−1 µii 2 6=µi> ki−1. Now we need o apply ρ−1 o each ac o (Rki−1σǫi µiR−1 ki), and w i e he image in in e ms o he gene a o s s1,...,sn−1and hei in e ses. Recall ha ρ(s1) = σ2 1,ρ(s2) = σ1σ2σ−1 1= 19 σ−1 2σ1σ2and ρ(si) = σi o i > 2. No ice also ha ρ(s2s1s−1 2) = σ2 2, and ha i µ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). The e o e, i ǫi= 1, one has: ρ−1(Rki−1σµiR−1 ki) =        sµi+1 i µi< ki−1−1, 1 i µi=ki−1−1, (sµisµi−1···s2)s1(s−1 2s−1 3···s−1 µi) i µi=ki−1, sµii µi> ki−1, and i ǫi=−1, one ob ains: ρ−1(Rki−1σ−1 µiR−1 ki) =        s−1 µi+1 i µi< ki−1−1, (sµisµi−1···s2)s−1 1(s−1 2s−1 3···s−1 µi) i µi=ki−1−1, 1 i µi=ki−1, s−1 µii µi> ki−1. Finally, we need o apply θ′ o he abo e ac o s. No ice ha he e a e only wo kinds o elemen s o conside . The i s one is si, wi h i > 1, which by de ini ion is mapped o θ′(si) = ai,i−1ai+n−1,i+n−2. The elemen s o he second kind a e hose o he o m (sisi−1···s2)s1(s−1 2s−1 3···s−1 i), o i= 1,...,n−1. One can use he Bi man-Ko-Lee p esen- a ion o show ha he image unde θ′o his elemen is p ecisely ai+n−1,i, bu i is easie o show i geome ically, since he elemen (sisi−1···s2)s1(s−1 2s−1 3···s−1 i) is p ecisely he one in he igh hand side o Figu e 10, in which he punc u e co esponding o he (n−1)-s oo o uni y ξimakes a loop a ound he o igin. I is hen easy o li such a pa h ia θ−1, ob aining he b aid 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 wan ed o show. Figu e 10: The image unde θo ai+n−1,i. One can inally ans o m he wo d X=σǫ1 µ1···σǫl µl o a wo d ep esen ing θ′(ρ−1(X)), i one eplaces each σǫi µiby θ′(ρ−1(Rki−1σǫi µiR−1 ki)). By he abo e discussion, he o mulae in he s a emen hold. I emains o no ice ha he numbe s µiand ki, o i= 1,...,l can be ob ained in ime O(l), and ha he p ocedu e gi en by he s a emen eplaces each le e o Xby a mos wo le e s o θ′(ρ−1(X)). Hence he leng h o he ob ained wo d is a mos 2l, and he whole p ocedu e has complexi y O(l). 20 Now we also need o know how o ansla e an elemen Y∈Sym2n−2, gi en as a wo d in he band gene a o s o BB 2n−2and hei in e ses, o a wo d ep esen ing ρ(θ(Y)) ∈Pn,2⊂BA n. We i s need a p epa a o y esul : Lemma 24. I Y∈Sym2n−2is gi en as a wo d o leng h lin he band gene a o s o BB 2n−2 and hei in e ses, hen one can compu e in ime O(l2n)a wo d δ p1p2···pk ep esen ing Y, such ha each pi∈Sym2n−2is ei he a symme ic polygonal b aid ΣP, o he p oduc o wo commu ing polygonal b aids ΣP1ΣP2such ha a o a ion o 180 deg ees pe mu es ΣP1and ΣP2. Mo eo e , | | ≤ land k≤ln/2. P oo . The way o ob ain he wo d p1···pkis jus he compu a ion o he le no mal o m o Yin BB 2n−2. I is shown in [28] ha he se o symme ic non-c ossing pa i ions o he (2n−2)-nd oo s o uni y ( he symme ic simple elemen s in BB 2n−2) is a subla ice o he whole la ice o non-c ossing pa i ions. This implies ha he Ga side s uc u e o BB 2n−2 es ic s o a Ga side s uc u e on Sym2n−2. The e o e, since δ∈Sym2n−2, he g ea es common di iso o Yand any powe o δis also symme ic, and hence e e y ac o in he le no mal o m o Yis symme ic. By [4], he le no mal o m o Ycan be compu ed in ime O(l2n). Once ha i is compu ed, each non-δ ac o is he p oduc o mu ually commu ing polygonal b aids, and he union o hese polygons mus be symme ic. Hence, each o hese polygons is ei he symme ic, o i belongs o a pai o polygons which a e pe mu ed by a o a ion o 180 deg ees, so he esul ollows. Finally, no ice ha he le no mal o m o Yhas he o m δ y1···yswi h | | ≤ land s≤l. Now e e y yicon ains a mos one symme ic polygonal b aid, namely he one con aining he o igin. The emaining polygonal b aids o yicome in pai s. The symme ic polygonal b aid, i i exis s, in ol es a leas wo punc u es, and each pai o polygonal b aids in ol es a leas 4 punc u es. Hence yican be decomposed in o a p oduc o a mos 1 + (2n−4)/4 = n/2 ac o s o he o m pj. Since s≤l, one inally ob ains k≤ln/2, as we wan ed o show. Lemma 25. Le Y∈Sym2n−2be gi en as a wo d o leng h lin he band gene a o s and hei in e ses, and le Y=δ p1···pkbe he decomposi ion gi en in Lemma 24. Then one ob ains a wo d in he A in gene a o s and hei in e ses ep esen ing ρ(θ(Y)) as ollows. 1. Each δ∈BB 2n−2should be eplaced by ρ(θ(δ)) = ε∈BA n. 2. I piis he p oduc o wo polygonal b aids ΣP1ΣP2, whe e he e ices o he polygons a e {ζi1,...,ζid}and {−ζi1,...,−ζid} espec i ely, le k∈ {0, . . . , n −2}be such ha {ζi1+k,...,ζid+k}={ζj1,...,ζjd}wi h 1≤j1<··· < jd< n. Then pishould be eplaced 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. I piis a symme ic polygonal b aid ΣP, and he e ices o he polygon Pa e {ζj1,...,ζjd,−ζj1,...,−ζjd}, 21 wi h 1≤j1<···< jd< n, hen pishould be eplaced 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. P oo . Conside he elemen α=sn−1sn−2···s1∈ A(Bn−1). I is ep esen ed in he cen al pic u e o Figu e 11. On he 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 he o he hand, Lemma 22 oge he wi h p esen a ion (2) ell us ha θ′(α) = (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) = δ. The e o e, since θ′=θ−1, one has ρ(θ(δ)) = ρ(α) = εand he i s case holds. Figu e 11: A geome ic in e p e a ion o ρ(θ(δ)) = ε. Now suppose ha piis he p oduc o wo polygonal b aids ΣP1ΣP2, whe e he e ices o he polygons a e {ζi1,...,ζid}and {−ζi1,...,−ζid}. No ice ha conjuga ion by δin BB 2n−2 o a es he base poin s, inc easing each index by one. The e o e, since P1and P2belong o a non-c ossing pa i ion, he e exis s some k∈ {0,...,n−2}such ha he o a ion induced by δk ans o ms {P1, P2}in o {P′ 1, P′ 2}, whe e he e ices o P′ 1belong o {ζ1,...,ζn−1}. Then ΣP1ΣP2=δkΣP′ 1ΣP′ 2δ−k. Since ρ(θ(δ)) = ε, in o de o compu e ρ(θ(ΣP1ΣP2)) i su ices o know he alue o ρ(θ(ΣP′ 1ΣP′ 2)). See an example in Figu e 12. Le ζj1,...,ζjdbe he e ices o P′ 1in inc easing o de , as in he s a emen . Fo simplici y o no a ion, deno e j∗=j+n−1 o j= 1,...,n−1. The compu a ion goes as ollows: Σ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 Figu e 12: T ansla ing pai s o symme ic polygonal b aids in BB 2n−2 o A in gene a o s in BA n. whe e he index idec eases om d o 2. Now one can check using Lemma 22 and p esen a ion 2, o jus by d awing he co esponding pic u es, ha o 1 ≤u < < n one has θ′((s−1 u+1s−1 u+2 ···s−1 −1)(s s −1···su+1)) = a ,ua ∗,u∗. Hence, since θ′=θ−1, one ob ains: θ(Σ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). No ice ha sicommu es wi h sji |i−j|>1, hence all posi i e le e s in he abo e o mula can be collec ed o he igh ( he only excep ion would appea i ji−1and jia e consecu i e o some i, bu in ha case he co esponding nega i e ac o is emp y). I ollows ha : θ(Σ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, he d−1 ac o s made by nega i e le e s commu e wi h each o he , so one inally ob ains: θ(Σ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 mus apply ρ o he abo e elemen . No ice ha all indices a e g ea e han 1, so his will eplace s2by σ1σ2σ−1 1and siby σi o i > 2. This is equi alen o eplacing siby σ1σiσ−1 1 o e e y i > 1. Hence, applying ρ educes o eplacing each siby σi, and hen conjuga ing he whole elemen by σ−1 1. Tha 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 p ecisely as we s a ed. I emains o show he hi d case, in which piis a single symme ic polygonal b aid ΣP, whe e he e ices o Pa e {ζj1,···ζjd,−ζj1,· · ·−ζjd}={ζj1,···ζjd, ζj1+n−1,···ζjd+n−1}. An example can be seen in Figu e 13. Figu e 13: T ansla ing a single symme ic polygonal b aid in BB 2n−2 o A in gene a o s in BA n. Recall ha j∗=j+n−1 o j= 1,...,n−1. In his 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 he easoning o he p e ious s ep o he i s wo ac o s, so i only emains o compu e ρ(θ(aj∗ 1,j1)). This is done by no icing ha 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 ρ educes o eplacing s1by σ2 1, hen siby σi o i > 1, and hen conjuga ing e e y hing by σ−1 1, one ob ains: ρ(θ(aj1,j∗ 1)) = σ1(σj1···σ2)σ2 1(σ−1 2···σ−1 j1)σ−1 1. The e o e ρ(θ(Σ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 p ecisely he o mula in he s a emen , so he p oo is inished. 24 4.2.2 Using symme ic b aids o sol e he conjugacy sea ch p oblem Recall ha we a e gi en X∈BA nas a wo d in he A in gene a o s σ1,...,σn−1and hei in e ses, and we know ha Xis conjuga e o εk o some k6= 0. This means ha he pe mu- a ion πXconsis s o he k- h powe o a cycle o leng h n−1, ha is πX= (a)(b1··· bn−1)k, whe e a6=bi o e e y i. The easy case happens when kis a mul iple o n−1, say k= (n−1) . Then εk= ∆2 , so X is conjuga e o a powe o ∆2. Bu since ∆2is a cen al elemen , his implies ha X= ∆2 . Hence X=εkand we a e done. We can hen assume ha kis no a mul iple o n−1. This means ha he only punc u e which is ixed by Xis he a- h one. I we deno e C1=σ[a→2], i clea ly ollows ha Y=C−1 1XC1 ixes he second s and, ha is, Y∈Pn,2. No ice also ha ε∈Pn,2, so εk∈Pn,2. This means ha Yand εka e wo elemen s in Pn,2which a e conjuga e in BA n. Fo una ely, hey a e also conjuga e in Pn,2, as i is shown in he ollowing esul . Lemma 26. I Y, Z ∈Pn,2a e conjuga e b aids whose pe mu a ions ha e a single ixed poin (namely 2), hen o e e y conjuga ing elemen C∈BA nsuch ha C−1Y C =Z, one has C∈Pn,2. P oo . Le j=πC(2). I j6= 2, hen πY C (2) = πC(πY(2)) = πC(2) = j, while πCZ(2) = πZ(πC(2)) = πZ(j)6=j(since he only ixed poin o πZis 2, and j6= 2). This con adic s he assump ion Y C =CZ, so we mus ha e πC(2) = 2, ha is C∈Pn,2. As a consequence, e e y conjuga ing elemen om Y o εk, when kis no a mul iple o n−1, mus belong o Pn,2. The e o e, inding a conjuga ing elemen om Y o εkin BA n educes o sol ing he conjugacy sea ch p oblem in Pn,2 o conjuga es o εk. Ou s a egy consis s o applying θ′◦ρ−1, sol ing he esul ing p oblem in Sym2n−2, and hen mapping he solu ion back o Pn,2using ρ◦θ. Recall om Lemma 25 ha ρ(θ(δ)) = ε, hence θ′(ρ−1(ε)) = δ∈Sym2n−2. The e o e we mus sol e he conjugacy sea ch p oblem in Sym2n−2 o θ′(ρ−1(Y)) and δk. Recall ha , as a consequence o [28], he g oup Sym2n−2has a Ga side s uc u e which is he es ic ion o he Bi man-Ko-Lee s uc u e o BB 2n−2. The Ga side elemen o his s uc u e is hence δ, so he conjugacy sea ch p oblem o powe s o δ∈Sym2n−2can be sol ed e y as , by applying i e a ed cyclings and decyclings. Bu one does no need o ca e abou he Ga side s uc u e o Sym2n−2, since one can di ec ly wo k wi h he Ga side s uc u e o BB 2n−2, as i is shown in he ollowing esul . Lemma 27. Le Z∈Sym2n−2⊂BB 2n−2be gi en as a wo d o leng h lin he band gene a o s and hei in e ses. Suppose ha Zis conjuga e o δk o some k6= 0. Then by applying a mos (2n−3)lcyclings and decyclings o Z, using he Ga side s uc u e o BB 2n−2, one conjuga es Z o δkand he conjuga ing elemen ha is ob ained belongs o Sym2n−2. P oo . By [5], by applying a mos (2n−3)lcyclings and decyclings o Zone ob ains an elemen which has minimal canonical leng h. Since Zis conjuga e o δk, and δis he Ga side elemen o BB 2n−2, i ollows ha he esul ing elemen is p ecisely δk. Hence one ob ains C∈BB 2n−2such ha C−1ZC =δk. 25 [22] J. Gonz´alez-Meneses, The n h oo o a b aid is unique up o conjugacy, Algeb aic and Geome ic Topology 3(2003), 1103-1118. [23] S. P. Ke ckho , The Nielsen ealiza ion p oblem, Ann. o Ma h. (2) 117 (1983), no. 2, 235–265. [24] B. de Ke ´ekj´a ´o, ¨ Ube die pe iodischen T ans o ma ionen de K eisscheibe und de Kugel l¨ache, Ma h. Annalen 80 (1919), 3-7. [25] E-K Lee and S.J. Lee, Conjugacy classes o pe iodic b aids, p ep in a Xi :ma h.GT/0702349. [26] H. Mo on and R. Hadji, Conjugacy o posi i e pe iodic pe mu a ion b aids, p ep in a Xi ma h.GT/0312209. [27] W. Magnus, A. Ka ass and D. Soli a , Combina o ial G oup Theo y, 1066, John Wiley and Sons. [28] V. Reine , Non-c ossing pa i ions o classical e lec ion g oups, Disc e e Ma h. 177 (1997) 195-222. [29] J.-Y. Shi, The enume a ion o Coxe e elemen s. J. Algeb aic Combin. 6(1997), no. 2, 161–171. Joan S. Bi man Volke Gebha d Juan Gonz´alez-Meneses Depa men o Ma hema ics, School o Compu ing and Ma hema ics, Depa amen o de ´ Algeb a, Ba na d College and Columbia Uni e si y, Uni e si y o Wes e n Sydney, Uni e sidad de Se illa, 2990 B oadway, Locked Bag 1797, Apdo. 1160, New Yo k, New Yo k 10027, USA. Pen i h Sou h DC NSW 1797, Aus alia, 41080 Se illa, Spain. jb@ma h.columbia.edu .gebha d @uws.edu.au [email protected] 32