a Xi :ma h/0112310 2 [ma h.GT] 28 Aug 2002
Conjugacy p oblem o b aid g oups and Ga side g oups1
Nuno F anco2
Dep. de Ma em´a ica, CIMA-UE Uni e si ´e de Bou gogne
Uni e sidade de ´
E o a Labo a oi e de Topologie
7000-´
E o a (Po ugal) UMR 5584 du CNRS
E-mail: nm @ue o a.p B.P. 47870
21078 - Dijon Cedex (F ance)
E-mail: nm @u-bou gogne.
and
Juan Gonz´alez-Meneses3
Dep . de Ma em´a ica Aplicada I
ETS A qui ec u a
Uni e sidad de Se illa
A da. Reina Me cedes, 2
41012-Se illa (Spain)
E-mail: [email protected]
Janua y, 2002
Key Wo ds: B aid g oups; A in g oups; Ga side g oups; Small Gaussian g oups; Conjugacy
p oblem.
Subjec Classi ica ion: P ima y: 20F36. Seconda y: 20F10.
We p esen a new algo i hm o sol e he conjugacy p oblem in A in b aid g oups, which is as e
han he one p esen ed by Bi man, Ko and Lee [3]. This algo i hm can be applied no only o b aid
g oups, bu o all Ga side g oups (which include ini e ype A in g oups and o us kno g oups among
o he s).
1. INTRODUCTION
Gi en a g oup G, he conjugacy p oblem in Gconsis s on inding an algo i hm which, gi en
a, b ∈G, de e mines i he e exis s c∈Gsuch ha a=c−1bc. Some imes one also needs o
compu e c, o ins ance, when one ies o a ack c yp osys ems based on conjugacy in G([2],
[12]).
We a e mainly in e es ed in A in b aid g oups, which a e de ined, o n≥2, by he ollowing
p esen a ion:
Bn=σ1, σ2,... ,σn−1σiσj=σjσi(|i−j| ≥ 2)
σiσi+1σi=σi+1σiσi+1 (1 ≤i≤n−2) (1)
1Bo h au ho s pa ially suppo ed by he Eu opean ne wo k TMR Sing. Eq. Di . e Feuill.
2Pa ially suppo ed by SFRH/BD/2852/2000.
3Pa ially suppo ed by BFM-3207.
1
The i s conjugacy algo i hm o b aid g oups was gi en by Ga side [11]. I was imp o ed
by El i ai and Mo on [10] and, mo e ecen ly, by Bi man, Ko and Lee ([3] and [4]).
In all hese algo i hms, one o he key poin s is he exis ence o a ini e se S⊂Bn, whose
elemen s a e called simple elemen s, e i ying some sui able p ope ies (we will be mo e p ecise
la e ). One o he main disad an ages is he size o S, which is always g ea e han 3n.
In his pape we will show how one can a oid his p oblem by de ining some small subse s
o S, whose size is smalle han n−1. Thei elemen s will be called minimal simple elemen s.
Unlike S, hese se s o minimal simple elemen s a e no unique o e e y g oup: The sui able se
o minimal simple elemen s mus be ecompu ed many imes in ou algo i hm. Ne e heless, we
will see ha i is much as e o compu e and use hese e y small subse s, han o use he whole
Sall he ime.
Fo ins ance, he known uppe bound o he complexi y o he Bi man-Ko-Lee algo i hm, o
decide we he wo b aids aand ba e conjuga ed in Bn, is O(kl2n3n) (whe e kis a numbe ha
will be explained la e , and lis he maximum o he wo d leng hs o aand b). An uppe bound
o he complexi y o ou algo i hm o Bnis O(kl2n4).
Le us men ion ha ou algo i hm, as well as he p e ious ones, also compu es he elemen
c∈Bnsuch ha a=c−1bc. Mo eo e , since ou cons uc ion elies on he exis ence o simple
elemen s and hei basic p ope ies, we can ex end ou esul s o a much la ge class o g oups,
called Ga side g oups. They we e in oduced by Deho noy and Pa is [9]. A he o igin, hese
g oups we e called small Gaussian g oups, bu he e has been a con en ion o call hem Ga side
g oups. They include, besides A in b aid g oups, sphe ical ( ini e ype) A in g oups, o us kno
g oups and o he s.
One inal ema k: one impo an p ope y o Ga side g oups is he exis ence o embedable
monoids ( o ins ance he monoid o posi i e b aids, B+
n, which embeds in Bn). The conjugacy
class o an elemen ain such a monoid is known o be a ini e se , C+(a). We will also show how
o compu e C+(a), using he echniques men ioned abo e.
This pape is s uc u ed as ollows: In Sec ion 2, we gi e a b ie in oduc ion o Ga side
monoids and g oups; In Sec ion 3, he known algo i hms men ioned in his in oduc ion a e
de ailed; We in oduce he minimal simple elemen s in Sec ion 4, and in Sec ion 5 we p esen
ou algo i hms in de ail; Complexi y issues a e ea ed in Sec ion 6 and, inally, some e ec i e
compu a ions a e desc ibed in Sec ion 7.
2. GARSIDE MONOIDS AND GROUPS
The esul s con ained in his sec ion a e well known, and can be ound in [11], [10], [16], [3],
[9], [8] and [14]. We will de ine he Ga side monoids and Ga side g oups, and explain some basic
p ope ies.
Gi en a cancella i e monoid M, wi h no in e ible elemen s, we can de ine wo di e en pa ial
o de s on i s elemen s, ≺and ≻. Gi en a, b ∈M, we say ha a≺b(b≻a) i he e exis s c∈M
such ha ac =b(b=ca), and we say ha ais a le ( igh ) di iso o b.
In his si ua ion, we can na u ally de ine he (le o igh ) leas common mul iple and g ea es
common di iso o wo elemen s. Gi en a, b ∈M, we deno e by a∨b he le lcm o aand b, i
i exis s. Tha is, a minimal elemen (wi h espec o ≺) such ha a≺a∨band b≺a∨b. We
deno e by a∧b he le gcd o aand b, i i exis s. Tha is, a maximal elemen (wi h espec o
≺),such ha a∧b≺aand a∧b≺b.
De ini ion 2.1. Le Mbe a monoid. We say ha x∈Mis an a om i x6= 1 and i x=yz
implies y= 1 o z= 1.Mis said o be an a omic monoid i i is gene a ed by i s a oms and,
mo eo e , o e e y x∈M, he e exis s an in ege Nx>0such ha xcanno be w i en as a
p oduc o mo e han Nxa oms.
2
De ini ion 2.2. We say ha a monoid Mis a Gaussian monoid i i is a omic, (le and
igh ) cancella i e, and i e e y pai o elemen s in Madmi s a (le and igh ) lcm and a (le
and igh ) gcd
De ini ion 2.3. AGa side monoid is a Gaussian monoid which has a Ga side elemen . A
Ga side elemen is an elemen ∆∈Mwhose le di iso s coincide wi h hei igh di iso s, hey
o m a ini e se , and hey gene a e M.
De ini ion 2.4. The le (and igh ) di iso s o ∆in a Ga side monoid Ma e called simple
elemen s. The ( ini e) se o simple elemen s is deno ed by S.
I is known ha e e y Ga side monoid admi s a g oup o ac ions. So we ha e:
De ini ion 2.5. A g oup Gis called a Ga side g oup i i is he g oup o ac ions o a
Ga side monoid.
The main example o a Ga side monoid (ac ually he monoid s udied by Ga side) is he A in
b aid monoid on ns ands, B+
n. I is de ined by P esen a ion (1), conside ed as a p esen a ion o
a monoid. I s g oup o ac ions is he b aid g oup Bn, and Ga side [11] showed ha B+
n⊂Bn.
Ac ually, e e y Ga side monoid embeds in o i s co esponding Ga side g oup [9].
The classical choice o a Ga side elemen o B+
nis he ollowing: ∆ =
(σ1σ2···σn−1) (σ1σ2···σn−2)···(σ1σ2)σ1.I can be de ined as he posi i e b aid (b aid in B+
n)
in which any wo s ands c oss exac ly once (whe e, as usual, σi ep esen s a c ossing o he
s ands in posi ions iand i+ 1). I is ep esen ed in Figu e 1 o n= 4. The simple elemen s
in his case a e he posi i e b aids in which any wo s ands c oss a mos once. Then one has
#(S) = n!
FIG. 1 The Ga side elemen ∆ ∈B+
4.
Ano he impo an example o Ga side monoid is he Bi man-Ko-Lee monoid [3], which has
he ollowing p esen a ion:
BKL+
n=a s(n≥ > s ≥1) a sa q =a qa s i ( − ) ( −q) (s− ) (s−q)>0
a sas =a a s =as a whe e n≥ > s > ≥1(2)
I s g oup o ac ions is again he b aid g oup Bn. The usual Ga side elemen in BKL+
nis
δ=an,n−1an−1,n−2···a2,1.The ad an age o his monoid wi h espec o B+
nis ha #(S) = Cn,
whe e Cn=(2n)!
n!(n+1)! <4nis he n h Ca alan numbe . Hence, he numbe o simple elemen s is
much smalle in his case, bu i is s ill qui e big, since Cn>3n. No ice also ha |δ|=n−1,
while in B+
n,|∆|=n(n−1)
2.
As we men ioned be o e, he e a e o he examples o Ga side g oups, such as ini e ype A in
g oups, o o us kno g oups (see [14] o ind mo e examples o Ga side g oups).
3
F om now on, Mwill deno e a Ga side monoid, Gi s g oup o ac ions and ∆ he co e-
sponding Ga side elemen . Since M⊂G, we will e e o he elemen s in Mas he posi i e
elemen s o G.
F om he exis ence o le lcm’s and gcd’s, i ollows ha (M, ≺) has a la ice s uc u e, and S
becomes a ini e subla ice wi h minimum 1 and maximum ∆.See in Figu e 2 he Hasse diag am
o he la ice o Sin B+
4,whe e he lines ep esen le di isibili y ( om bo om o op). The
analogous p ope ies a e also e i ied by ≻.
FIG. 2 The la ice o simple elemen s in B+
4.
De ini ion 2.6. Fo a∈Mwe de ine LM (a)∈Sas he maximal simple le di iso o a,
ha is, LM (a) = ∆ ∧a. We also de ine RM (a)as he maximal simple igh di iso o a.
P oposi ion 2.7 ([11]).Fo a∈G, he e exis s a unique decomposi ion a= ∆pa1···al,
called le no mal o m o a, whe e:
1. p= max { ∈Z: ∆− a∈M}(hence a1···al∈M).
2. ai=LM (ai···al)∈S {∆,1}, o all i= 1, ..., l.
Symme ically, one de ines he igh no mal o m o a∈G, using RM.
Some imes, i we a e dealing wi h elemen s in Mand i does no lead o con usion, we will
say ha an elemen w=w1···w ∈Mis in le no mal o m o exp ess ha wi∈S {1} o all
iand, o some p≥0, he no mal o m o wis ∆pwp+1 ···w .
La e we will use hese echnical esul s:
Lemma 2.8 ([13], P op. 2.1).Le w1···w ∈Mbe in le no mal o m, and x1···x ∈
Min igh no mal o m. Fo e e y ∈M, one has LM ( w1···w ) = LM ( w1)and
RM (x1···x ) = RM (x ).
Lemma 2.9 ([13], P op. 5.3).Le w=w1···w ∈Mbe w i en in igh no mal o m. I we
w i e win any o he way as a p oduc o simple elemen s, w=u1···u , hen w1≺u1.
4
Lemma 2.10 ([7], 3.1).Le w=w1···w ∈Mbe w i en in igh no mal o m, and le s∈S.
Then we can decompose wi=w′
iw′′
i, o all i, in such a way ha he igh no mal o m o ws
is (w′
1)(w′′
1w′
2)···(w′′
−1w′
)(w′′
s)i i has + 1 ac o s, o (w1w′
2)···(w′′
−1w′
)(w′′
s)i i has
ac o s.
Co olla y 2.11. Le w=w1···w ∈Mbe w i en in igh no mal o m. Le s∈Sand
suppose ha we can w i e ws as a p oduc o simple elemen s, ha is, w1···w s=u1···u .
Then w1≺u1.
P oo . Since ws can be w i en as a p oduc o simple elemen s, hen i s igh no mal o m
has ac o s, say 1··· . By Lemma 2.10, w1≺ 1, and by Lemma 2.9 1≺u1, so he esul
ollows.
We end his sec ion wi h a las p ope y o Ga side g oups: The e is a powe o hei Ga side
elemen which belongs o he cen e . Fo ins ance, in Bn he elemen ∆2=δngene a es he
cen e o Bn.
3. KNOWN ALGORITHMS FOR THE CONJUGACY PROBLEM.
We p esen he e he El i ai-Mo on algo i hm o he conjugacy p oblem in b aid g oups [10],
which is also alid o Ga side g oups, as can be seen in [15].
I goes as ollows: o e e y elemen a∈G, i compu es a ini e subse Csum(a) o he
conjugacy class o a. This se is shown o be independen o a, so i is an in a ian o i s conjugacy
class. The e o e, wo elemen s aand ba e conjuga ed i and only i Csum(a) = Csum(b).
Le us explain he algo i hm in mo e de ail.
3.1. De ini ion o C≥m(a)and Csum(a)
P oposi ion 3.1. [10, 15] Le a= ∆pa1···al∈Gbe in le no mal o m. Then he igh
no mal o m o ais as ollows: a=x1···xl∆p, whe e land pa e he same as abo e.
De ini ion 3.2. Le a= ∆pa1···al∈Gbe in le no mal o m. We de ine he in imum,
sup emum and canonical leng h o a, espec i ely, by in (a) = p, sup (a) = p+l, and kak=l.
De ini ion 3.3. Le a∈Gand deno e by C(a) he conjugacy class o a. We de ine
he summi in imum, he summi sup emum and he summi leng h o aas, espec i ely,
max {in (x) : x∈C(a)},min {sup (x) : x∈C(a)}and min {kxk:x∈C(a)}.
De ini ion 3.4. Le a∈G.
1. Fo e e y in ege m, we de ine C≥m(a) = { ∈C(a) : in ( )≥m}.
2. We de ine he summi class o a,Csum (a), as he subse o C(a)con aining all elemen s
o minimal canonical leng h.
Rema ks:
1. One has C≥0(a) = C(a)∩M=C+(a).
2. In [10], Csum (a) is called he Supe Summi Se .
P oposi ion 3.5. [10, 15] Fo e e y b∈Csum(a), he in imum, sup emum and canonical
leng h o ba e equal, espec i ely, o he summi in imum, he summi sup emum and he summi
leng h o a.
I is known ha C≥m(a) and Csum (a) a e ini e se s. Mo eo e , by P oposi ion 3.5, i
C≥m(a)6=φ, hen Csum (a)⊂C≥m(a).
5
3.2. Cycling and decycling
Le τ:G→Gbe he au omo phism de ined by τ(a) = ∆−1a∆. The es ic ion o τ o Sis
a bijec ion τ:S→S.
De ini ion 3.6. Le a= ∆pa1···al∈Gbe w i en in le no mal o m. The unc ions
cycling and decycling a e he maps cand d, om G o i sel , de ined by:
c(a) = ∆pa2···alτ−p(a1) ;
d(a) = ∆pτp(al)a1···al−1.
No ice ha c(a) and d(a) a e conjuga es o a. Fu he mo e, o e e y a∈G, in (a)≤
in (c(a)) and sup(a)≥sup(d(a)).
Suppose ha we ha e an elemen a∈G, such ha in (a) is no equal o he summi in imum
o a. Then we can y o inc ease he in imum by epea ed cycling. By [10] (and [15]), his
always wo ks: he e exis s a posi i e in ege ksuch ha in (ck(a)) >in (a). We know a bound
o his in ege konly o some special Ga side monoids and g oups: I Mis homogeneous, i.e.
i has only homogeneous ela ions ( o ins ance, i Mis B+
no BKL+
n), hen e e y wo wo ds
ep esen ing an elemen a∈Mha e he same leng h, deno ed |a|. I is shown in [4] ha , in his
case, k < |∆|.
The e o e, by epea ed cycling, we can conjuga e a o ano he elemen bao maximal in imum.
E en i Mis no homogeneous, we know ha we eached he summi in imum when we en e
in o a loop: a some poin ck( ) = o some conjuga ed o a. This always happens since he
se C≥m(a) is ini e o e e y m, in pa icula o he summi in imum.
Once bais ob ained, we can y o dec ease i s sup emum by epea ed decycling. By [10]
(and [15]), his also wo ks: ei he we en e in o a loop, and hen he sup emum is minimal, o
he e exis s an in ege ksuch ha sup(dk(ba)) <sup(ba). Again by [4], k < |∆|in homogeneous
monoids.
The e o e, using epea ed cycling and decycling a ini e numbe o imes, one ob ains an
elemen ea∈Csum (a). And, i Mis homogeneous, his can be done in polynomial ime in |a|.
3.3. The El i ai-Mo on algo i hm
Once ha we ob ained an elemen ea∈Csum(a), we can cons uc he whole Csum (a), by
using he nex esul :
P oposi ion 3.7. [10, 15] Fo u, conjuga e elemen s in Csum(a)( esp. C≥m(a)), he e
exis s a sequence u=u1, u2, ..., uk= o elemen s in Csum(a)( esp. C≥m(a)) such ha , o
i= 1,... ,k−1,uiand ui+1 a e conjuga ed by an elemen in S.
The El i ai-Mo on algo i hm does he ollowing: Gi en a, b ∈Gi compu es, using cyclings
and decyclings, ea∈Csum(a) and e
b∈Csum(b). Then i de ines V1={ea}and i compu es, by
ecu ence,
Vi={s−1 s;s∈S, ∈Vi−1} ∩ Csum(a).
Since 1 ∈S, his c ea es an ascending chain o subse s o Csum(a). By he abo e p oposi ion,
one has Vk=Vk+1 o some k, and hen Vk=Csum(a). Hence, when he chain s abilises, he
whole Csum(a) has been compu ed. Then aand ba e conjuga ed i and only i e
b∈Csum (a).
Rema k 3.8. This algo i hm can be modi ied o compu e C≥m(a) o a∈Mand m∈Z. We
jus need o eplace Csum(a)by C≥m(a)in he abo e discussion.
6
No ice ha Csum(a) ( esp. C≥m(a)) is compu ed a he cos o conjuga ing e e y elemen
in Csum(a) ( esp. C≥m(a)) by e e y elemen in S. All hese se s a e qui e big, and his makes
he algo i hm o be slow. In wha ollows, we will ge id o he p oblem caused by he size o S,
using he minimal simple elemen s.
4. MINIMAL SIMPLE ELEMENTS
In his sec ion we shall de ine some e y small subse s o S, which will enable us o compu e
C≥m(a) and Csum(a), o a∈G, much as e han he p e ious algo i hms.
Recall he de ini ion o he pa ial o de ≺in M.
De ini ion 4.1. Le Pbe a p ope y o simple elemen s. We deno e by SP he se o simple
elemen s sa is ying P. The se o minimal simple elemen s o P,min(SP), is he se o minimal
elemen s (wi h espec o ≺) in SP.
We shall en o ce P o be closed unde g.c.d, ha is, i s1, s2∈SP hen s1∧s2∈SP. Le us
see ha , unde his assump ion, he se min(SP) u ns o be e y small. Fo e e y a om x∈M,
le mul (x) = {s∈S;x≺s}.
Lemma 4.2. Suppose ha Pis closed unde gcd, and le xbe an a om o M. I he se
SP∩mul (x)is non-emp y, hen i has a unique minimal elemen , ha we deno e ρx.
P oo . Suppose ha he e a e wo dis inc minimal elemen s s1, s2∈SP∩mul (x). Since
s1, s2∈SP, hen s1∧s2∈SP. Mo eo e , since xdi ides s1and s2, i also di ides s1∧s2.
The e o e s1∧s2∈SP∩mul (x), so s1and s2canno be bo h minimal.
Co olla y 4.3. Suppose ha Mhas ma oms. I Pis closed unde gcd, hen #(min(SP)) ≤
m.
P oo . No ice ha e e y elemen in Mmus be di isible by an a om. Take s∈min(SP) and
conside an a om x≺s. Since sis minimal in SP, i is also minimal in SP∩mul (x). Hence
s=ρx. The e o e
min(SP)⊂ {ρx:xis an a om}
and he esul ollows.
Example 4.4. In B+
n he e a e n−1a oms, namely σ1,... ,σn−1. The e o e, i Pis a
p ope y closed unde gcd, hen min(SP)has a mos n−1elemen s, while #(S) = n!
Example 4.5. In BKL+
n he e a e n(n−1)
2a oms ( he gene a o s in P esen a ion 2). Hence,
i Pis a p ope y closed unde gcd, hen #(min(SP)) ≤n(n−1)
2, while #(S) = Cn>3n.
We mus now de ine some sui able p ope ies, closed unde gcd, ha will allow us o compu e
C≥m(a) and Csum(a), o a∈G. These p ope ies will depend on some gi en elemen s in M, so
we will ha e an in ini e numbe o p ope ies, each one co esponding o a se o minimal simple
elemen s.
4.1. Minimal simple elemen s o compu e C≥m(a)
De ini ion 4.6. Le a∈Gand ∈C≥m(a), o some m∈Z. We will say ha a simple
elemen ssa is ies he p ope y P≥m
i i conjuga es o an elemen in C≥m(a), ha is, s−1 s ∈
C≥m(a).
7
P oposi ion 4.7. (Ca ac e iza ion o elemen s sa is ying P≥m
). I ∈C≥m(a), one can
w i e = ∆mw, whe e w∈M. Then a simple elemen ssa is ies he p ope y P≥m
i and only
i τm(s)≺ws.
P oo . The i s asse ion comes om he de ini ion o in imum. Le hen = ∆mw, whe e
w∈M, and le s∈S. One has s−1 s =s−1∆mws = ∆mτm(s−1)ws = ∆m(τm(s))−1ws. Hence,
ssa is ies P≥m
i and only i (τm(s))−1ws ∈M, ha is, τm(s)≺ws.
P oposi ion 4.8. Fo e e y ∈Mand e e y m∈Z, he p ope y P≥m
is closed unde gcd.
P oo . Suppose ha s1and s2sa is y P≥m
, and le s=s1∧s2. No ice ha τp ese es gcd’s,
since i p ese es le di isibili y. Hence τ(s) = τ(s1)∧τ(s2), and hus τm(s) = τm(s1)∧τm(s2).
One has τm(s)≺τm(s1)≺ s1and τm(s)≺τm(s2)≺ s2. Bu i is easy o show ha , o
e e y ∈M, s1∧ s2= s. Hence, since τm(s) di ides s1and s2 hen i di ides i s gcd, i.e.
τm(s)≺ s. The e o e, ssa is ies P≥m
, and he esul ollows.
De ini ion 4.9. Fo e e y ∈C≥m(a), we de ine S≥m
=min(SP≥m
). Tha is, S≥m
is he
se o minimal simple elemen s (wi h espec o ≺) among hose who conjuga e o an elemen
in C≥m(a).
No ice ha , by Co olla y 4.3 and P oposi ion 4.8, he ca dinal o S≥m
o e e y ∈C≥m(a)
is no bigge han he numbe o a oms in M. Mo eo e , we ha e he ollowing esul , analogous
o P oposi ion 3.7.
P oposi ion 4.10. Gi en u, ∈C≥m(a) o some a∈G, he e exis s a sequence u=
u1, u2, ..., uk= o elemen s in C≥m(a)such ha , o i= 1, ..., k −1, he elemen s uiand ui+1
a e conjuga ed by an elemen in S≥m
ui.
P oo . Jus no ice ha any le o igh di iso o a simple elemen is also a simple elemen ,
and hen decompose e e y simple elemen in he sequence gi en by P oposi ion 3.7 in o a p oduc
o minimal ones.
This esul implies ha , in o de o compu e C≥m(a) o a∈M, i su ices o conjuga e e e y
∈C≥m(a) by he elemen s in he small se S≥m
.
4.2. Minimal simple elemen s o compu e Csum(a)
De ini ion 4.11. Le a∈G, and le ∈Csum(a). We will say ha a simple elemen s
sa is ies he p ope y Psum
i i conjuga es o an elemen in Csum(a). In o he wo ds, i he
canonical leng h o s−1 s is equal o he canonical leng h o (which is he summi leng h o a).
P oposi ion 4.12. Fo e e y ∈Csum(a), he p ope y Psum
is closed unde gcd.
P oo . Le s1and s2be wo simple elemen s sa is ying Psum
, and deno e s=s1∧s2. W i e
si=s i o i= 1,2, hus 1∧ 2= 1.
Suppose ha in ( ) = pand k k= . Then = ∆p ′, whe e ′∈Mand we can w i e
′as a p oduc o simple elemen s (bu no less). Since s1sa is ies Psum
, one has s−1
1 s1=
s−1
1∆p ′s1= ∆pτp(s−1
1) ′s1= ∆p(τp(s1))−1 ′s1,whe e (τp(s1))−1 ′s1∈Mand we can w i e
i as a p oduc o simple elemen s, say x1···x . The same happens o (τp(s2))−1 ′s2∈M.
Now conside s−1 s. By P oposi ion 4.8 i belongs o C≥p(a), ha is, (τp(s))−1 ′s∈M. We
mus show ha we can w i e his elemen as a p oduc o simple elemen s. Suppose his is no
ue, and w i e (τp(s))−1 ′s=z1···z +1 in igh no mal o m (i has no mo e han + 1 ac o s
8
since i is a igh di iso o ′swhich has + 1 ac o s). One has x1···x = (τp(s1))−1 ′s1=
(τp( 1))−1(τp(s))−1 ′s 1= (τp( 1))−1z1···z +1 1.Hence, z1···z +1 1=τp( 1)x1···x , and
z1···z +1 is in igh no mal o m. Then by Co olla y 2.11, z1≺τp( 1). In he same way,
z1≺τp( 2). The e o e z1≺τp( 1)∧τp( 2) = τp( 1∧ 2) = τp(1) = 1. A con adic ion.
De ini ion 4.13. Fo e e y ∈Csum(a), we de ine Ssum
=min(SPsum
). Tha is, Ssum
is he se o minimal simple elemen s (wi h espec o ≺) among hose who conjuga e o an
elemen in Csum(a).
As be o e, by Co olla y 4.3 and P oposi ion 4.12, he ca dinal o Ssum
o e e y ∈Mis no
bigge han he numbe o a oms in M. Fu he mo e, we can adjus he algo i hm by El i ai-
Mo on o hese new se s, since we ha e he ollowing esul , analogous o P oposi ions 3.7 and
4.10.
P oposi ion 4.14. Fo u, conjuga e elemen s in Csum (a), he e exis s a sequence u=
u1, ..., uk= o elemen s in Csum (a)such ha , o i= 1, ..., k −1, he elemen s uiand ui+1 a e
conjuga ed by an elemen in Ssum
ui.
The p oo o his esul pa allels ha o P oposi ion 4.10. I implies ha , in o de o compu e
Csum (a) o a∈G, i su ices o conjuga e e e y ∈Csum (a) by he elemen s in Ssum
.
We ha e hen desc ibed small subse s o Swhich su ice o compu e C≥m(a) and Csum(a).
Bu we s ill need o show how o compu e hese subse s. This is wha we do in he nex sec ion.
5. ALGORITHMS FOR THE CONJUGACY PROBLEM
We shall explain in his sec ion ou algo i hms o compu e C≥m(a) and Csum(a), gi en a∈G.
Le us i s explain a echnical algo i hm, which we did no ind in he li e a u e. Le s∈S
and ∈M. We will show how o compu e hei lcm s∨ . Mo e p ecisely, ou algo i hm will
compu e a simple elemen s′such ha s∨ = s′. We mus indica e ha i is well known how o
compu e he lcm and he gcd o wo simple elemen s, as well as he no mal o ms o any elemen
in G.
Algo i hm 1 ( o compu ing s′such ha s∨ = s′).
1. Compu e he no mal o m o = 1··· .
2. s0=s.
3. Fo e e y i= 1,... , , compu e si−1∨ i, and w i e i isi.
4. Re u n s .
P oposi ion 5.1. Le s∈Sand ∈M. Le s be he simple elemen compu ed by Algo-
i hm 1. Then s∨ = s .
P oo . We p oceed by induc ion on = sup( ). I = 1 he esul is i ial, so suppose ha
> 1 and he esul is ue o −1. Deno e ′= 1··· −1. We ha e s∨ ′= ′s −1, ha
is, s −1is he smalles elemen such ha ′s −1is di isible by s. The e o e, an elemen ∈M
sa is ies s≺ = ′( ) i and only i s −1≺ , and his is equi alen o s −1∨ ≺ , ha
is s ≺ hence s ≺ . The e o e, s is he smalles elemen sa is ying s≺ s , as we wan ed
o show.
9
P oposi ion 6.4. Gi en a∈BKLnas a wo d o leng h l, he complexi y o compu ing
Csum(a)( o he Bi man-Ko-Lee p esen a ion) is O(kl2n5), whe e kis he numbe o elemen s
in Csum(a).
No ice ha he complexi y o he known algo i hm was O(kl2Cnn), so ou algo i hm imp o es
i conside ably.
One in e es ing ema k is ha ou algo i hm wo ks as e , a p io i, o he monoid B+
n han
o BKL+
n. This is due o a simple ac : in ou algo i hm he numbe o a oms is mo e ele an
han he numbe o simple elemen s. In BKL+
n, he numbe o simple elemen s is much smalle
han in B+
n, bu he numbe o a oms is n(n−1)
2, while in B+
nis n−1.
6.3. A in monoids
As we men ioned in he in oduc ion, he A in g oups o ini e ype a e Ga side g oups, so we
can apply ou algo i hms o he co esponding A in monoids (see [5] o an in oduc ion o A in
monoids and g oups). In [6] we can ind algo i hms o deal wi h A in monoids: compu a ion
o no mal o ms, g ea es common di iso s, di ision algo i hms, e c. Al hough hese algo i hms
seem o be exponen ial in he leng h o he wo ds in ol ed, in [7] i is shown ha ini e ype
A in g oups a e biau oma ic, so he e a e quad a ic algo i hms o compu e all o he abo e.
Ne e heless, since we a e mainly in e es ed in compa ing ou algo i hms wi h he p e ious
ones, we jus need o know he leng h o he Ga side elemen ∆, and he numbe o simple
elemen s in any gi en A in g oup. Le hen Gbe an A in g oup o ank n, ha is, An,Bn,
Dn,En(i n= 6,7,8), Fn(i n= 4), Hn(n= 3,4) o I2(p) (i n= 2), and le hbe i s Coxe e
numbe . I is known ha |∆|=nh
2, whe e h=O(n), and ha #(S)≥n!.
Hence, i he complexi y o he conjugacy algo i hm by El i ai and Mo on is O(xn!) o some
xdepending on nand l, ou algo i hm will ha e complexi y O(xn3). This is shown by using he
same a gumen s as in he p e ious subsec ions.
7. EFFECTIVE COMPUTATIONS
7.1. Compa ison wi h he El i ai-Mo on algo him
In he p e ious sec ion, we ound heo e ical uppe bounds o he complexi y o ou algo-
i hms. We showed ha ou algo i hm is, in heo y, much be e han he El i ai-Mo on one
( o n > 5). In his sec ion we e ec i ely compa e he wo algo i hms, in he ollowing way: Fo
gi en nand l, (3 ≤n≤5 and 10 ≤l≤20) we ook 5000 andom pai s o posi i e b aids in
Bno leng h l(using A in p esen a ion), we es ed conjugacy using bo h algo i hms, and we
compa ed he A e age Running Time (ART) and he Maximum Running Time (MRT). We did
he same o n= 6 and l= 10, o 1144 pai s.
We can conclude ha ou algo i hm is as e o n≥4, and much as e o n≥5 (We we e
no able o compu e he cases n= 5 and l= 19,20 using he El i ai-Mo on algo i hm since he
compu a ions we e oo long).
In he ables below one can see he esul s: We w o e F-GM o ou algo i hm and E-M o
he El i ai-Mo on one. The ime is gi en in seconds.
n= 3
l10 11 12 13 14 15
ART F-GM 0.1526 0.2011 0.2361 0.3038 0.3386 0.3951
ART E-M 0.1144 0.1460 0.1692 0.2133 0.2367 0.2723
MRT F-GM 2.429 3.599 4.680 6.080 7.450 6.960
MRT E-M 1.659 2.539 3.220 4.089 5.029 4.599
16
l16 17 18 19 20
ART F-GM 0.3896 0.5021 0.5473 0.6494 0.7292
ART E-M 0.2710 0.3392 0.3710 0.4329 0.4841
MRT F-GM 11.299 10.530 12.469 15.090 16.539
MRT E-M 7.219 6.729 7.970 9.950 11.039
n= 4
l10 11 12 13 14 15
ART F-GM 0.3559 0.4796 0.6772 0.7870 1.0264 1.2599
ART E-M 0.6118 0.7233 1.0127 1.2086 1.5909 1.9538
MRT F-GM 8.680 11.390 16.519 23.949 33.969 42.029
MRT E-M 16.319 22.329 28.440 41.579 61.790 74.999
l16 17 18 19 20
ART F-GM 1.4548 1.7436 2.2029 2.6616 2.9942
ART E-M 2.3106 2.7995 3.5548 4.3280 4.7226
MRT F-GM 41.910 62.940 72.940 103.470 148.989
MRT E-M 70.039 107.969 137.720 173.060 245.740
n= 5
l10 11 12 13 14 15
ART F-GM 1.0997 1.8463 2.7657 3.7962 3.8195 4.4797
ART E-M 7.8690 11.1207 17.1455 23.2491 26.2595 29.7934
MRT F-GM 21.239 46.070 65.530 88.940 139.180 155.260
MRT E-M 177.489 322.039 456.669 611.609 1068.970 1178.790
l16 17 18 19 20
ART F-GM 5.6410 7.1540 8.8198 9.4597 10.6614
ART E-M 38.7974 51.0028 62.0018
MRT F-GM 254.770 411.320 401.409 516.119 532.469
MRT E-M 2116.239 3221.880 3218.93
n= 6
l10
ART F-GM 2.2450
ART E-M 506.224
MRT F-GM 43.935
MRT E-M 7495.288
7.2. Exhaus i e compu a ion o conjugacy classes and summi classes
In he p e ious sec ion, we saw ha he complexi y o all ou algo i hms depends on he size
o he se s C≥m(a) o Csum(a), o a∈M. In he cases o B+
no BKL+
n, he only uppe bounds
known o hese se s a e exponen ial in nand in l=|a|. Ne e heless, we ha e he ollowing
( ecall ha , in his case, C+(a) = C≥0(a) = C(a)∩B+
n):
17
Conjec u e: (Thu s on, [16]) Le nbe a ixed in ege and le a∈B+
n, ha ing wo d leng h l.
The e is an uppe bound o C+(a) which is a polynomial in l.
The exis ence o his uppe bound o C+(a), o e en o Csum(a), would imply he ollowing:
Conjec u e: (Bi man, Ko and Lee, [4]) Fo e e y ixed in ege n, he e exis s a solu ion o he
conjugacy p oblem in Bn, which is polynomial in he wo d leng h o he elemen s in ol ed.
In o de o ha e some nume ical e idence o suppo hese conjec u es, we ha e compu ed,
o n= 3,... ,8 and se e al alues o l, all he conjugacy classes o wo ds o leng h lin B+
n, as
well as he co esponding summi classes. In he ables below we p esen he ollowing da a, o
he se Wlo elemen s in B+
nha ing wo d leng h l:
•CC+: The numbe o Conjugacy Classes in Wl⊂B+
n.
•max C+: The size o he bigges one. Tha is, he numbe o elemen s in he bigges
C+(a), o a∈Wl.
•max Csum : The size o he bigges summi class.
• : A ep esen a i e om one o hose bigges summi class. Tha is, an elemen ∈
Csum(a), whe e Csum(a) has maximal size.
n=3
l CC+max C+max Csum
4 3 6 2 σ3
1σ2
5 3 10 6 σ3
1σ2
2
6 5 12 8 σ4
1σ2
2
7 5 16 10 σ5
1σ2
2
8 8 20 12 σ6
1σ2
2
9 9 29 14 σ7
1σ2
2
10 13 30 16 σ8
1σ2
2
11 16 40 18 σ9
1σ2
2
12 27 48 20 σ10
1σ2
2
13 33 64 22 σ11
1σ2
2
14 50 80 24 σ12
1σ2
2
15 70 125 26 σ13
1σ2
2
16 107 126 28 σ14
1σ2
2
17 153 160 30 σ15
1σ2
2
18 241 192 32 σ16
1σ2
2
19 349 256 34 σ17
1σ2
2
20 542 320 36 σ18
1σ2
2
18
n=4
l CC+max C+max Csum
4 7 12 4 σ3
1σ2
5 9 20 12 σ3
1σ2
2
6 16 40 16 σ4
1σ2
2
7 21 54 22 σ5
1σ2σ3
8 36 72 32 σ6
1σ2σ3
9 54 94 50 σ4
1σ2
2σ2
3σ2
10 96 156 60 σ5
1σ2
2σ2
3σ2
11 160 252 70 σ6
1σ2
2σ2
3σ2
12 304 344 88 σ5
1σ2
2σ1σ3σ1σ2σ3
13 538 582 114 σ6
1σ2
2σ1σ3σ1σ2σ3
14 1030 752 140 σ7
1σ2
2σ1σ3σ1σ2σ3
15 1954 1114 166 σ8
1σ2
2σ1σ3σ1σ2σ3
n=5
l CC+max C+max Csum
4 10 24 8 σ2
1σ2σ3
5 15 36 18 σ3
1σ2
2
6 28 80 24 σ4
1σ2
2
7 44 136 44 σ5
1σ2σ3
8 81 188 64 σ6
1σ2σ3
9 141 288 104 σ5
1σ2σ3σ2σ4
10 281 516 156 σ6
1σ2σ3σ2σ4
11 520 702 208 σ7
1σ2σ3σ2
4
12 1194 1018 260 σ8
1σ2σ3σ2
4
n=6
l CC+max C+max Csum
4 13 36 16 σ1σ2σ3σ4
5 22 56 30 σ1σ2σ1σ2
4
6 44 120 36 σ4
1σ2σ3
7 76 272 72 σ4
1σ2σ3σ4
8 148 412 124 σ5
1σ2σ3σ4
9 276 576 208 σ5
1σ2σ3σ2
4
10 573 1032 372 σ5
1σ2σ3σ4σ2
5
n=7
l CC+max C+max Csum
4 14 60 24 σ1σ2σ2
4
5 26 84 60 σ1σ2σ1σ2
4
6 56 160 72 σ1σ2σ4σ2σ2
1
7 104 408 108 σ4
1σ2σ3σ4
8 215 824 192 σ4
1σ2σ3σ4σ5
9 424 1160 416 σ4
1σ2σ3σ4σ2
5
10 914 1992 744 σ5
1σ2σ3σ4σ2
5
19
n=8
l CC+max C+max Csum
4 15 100 48 σ1σ2σ3σ5
5 29 144 100 σ1σ2σ1σ2
4
6 66 216 144 σ1σ2σ1σ3σ2
5
7 130 544 168 σ1σ2σ1σ3σ4σ2
6
8 281 1236 360 σ1σ2σ1σ3
4σ2
5
ACKNOWLEDGMENTS
The main ideas in his wo k we e de eloped du ing a s ay o bo h au ho s a he Labo a oi e de
Topologie de l’Uni e si ´e de Bou gogne a Dijon (F ance). We a e e y g a e ul o all membe s o he
Labo a oi e, and in pa icula o Luis Pa is o his many use ul sugges ions. We a e also g a e ul o Jean
Michel o his p ecise and help ul commen s on an ea lie e sion o his pape .
REFERENCES
[1] E. A in, Theo y o b aids, Annals o Ma h. 48 (1946), 101-126.
[2] I. Anshel, M. Anshel and D. Gold eld, An algeb aic me hod o public-key c yp og aphy.
Ma h. Res. Le . 6, No. 3-4 (1999), 287-291.
[3] J. Bi man, K. H. Ko and S. J. Lee, A new app oach o he wo d and conjugacy p oblems
in he b aid g oups, Ad . Ma h. 139, No. 2 (1998), 322-353.
[4] J. Bi man, K. H. Ko and S. J. Lee, The in imum, sup emum and geodesic leng h o a
b aid conjugacy class, P ep in (2000).
[5] N. Bou baki, “G oupes e algeb es de Lie”, Chaps. IV-VI, He mann, Pa is, 1968.
[6] E. B iesko n and K. Sai o, A in-G uppen und Coxe e -G uppen, In en . Ma h. 17
(1972), 245-271.
[7] R. Cha ney, A in g oups o ini e ype a e biau oma ic, Ma h. Ann. 292, No. 4 (1992),
671-683.
[8] P. Deho noy, G oupes de Ga side, Ann. Scien . ´
Ec. No m. Sup., 4es´e ie, . 35, 2002,
267-306.
[9] P. Deho noy and L. Pa is, Gaussian g oups and Ga side g oups, wo gene aliza ions o
A in g oups, P oc. London Ma h. Soc. 79, No. 3 (1999), 569-604.
[10] E. A. El i ai, H. R. Mo on, Algo i hms o posi i e b aids, Qua . J. Ma h. Ox o d 45
(1994), 479-497.
[11] F. A. Ga side, The b aid g oup and o he g oups, Qua . J. Ma h. Ox o d 20 (1969),
235-154.
[12] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Pa k, New public-
key c yp osys em using b aid g oups. Ad ances in c yp ology—CRYPTO 2000 (San a
Ba ba a, CA), 166-183, Lec u e No es in Compu . Sci. 1880, Sp inge , Be lin, 2000.
[13] J. Michel, A no e on wo ds in b aid monoids, J. o Algeb a 215 (1999) 366-377.
20
[14] M. Pican in, Pe i s g oupes gaussiens, Ph. D. Thesis, Uni e si ´e de Caen (2000).
[15] M. Pican in, The conjugacy p oblem in small Gaussian g oups, Comm. Algeb a 29, No.
3 (2001), 1021-1039.
[16] W. P. Thu s on, B aid G oups, Chap e 9 o “Wo d p ocessing in g oups”, D. B. A.
Eps ein, J. W. Cannon, D. F. Hol , S. V. F. Le y, M. S. Pa e son and W. P. Thu s on,
Jones and Ba le Publishe s, Bos on, MA, 1992.
21
