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