Conjugacy problem for braid groups and Garside groups

arXiv:math/0112310v2 [math.GT] 28 Aug 2002 Conjugacy problem for braid groups and Garside groups1 Nuno Franco2 Dep. de Matem´atica, CIMA-UE Universit´e de Bourgogne Universidade de ´ Evora Laboratoire de Topologie 7000-´ Evora (Portugal) UMR 5584 du CNRS E-mail: [email protected] B.P. 47870 21078 - Dijon Cedex (France) E-mail: [email protected] and Juan Gonz´alez-Meneses3 Dept. de Matem´atica Aplicada I ETS Arquitectura Universidad de Sevilla Avda. Reina Mercedes, 2 41012-Sevilla (Spain) E-mail: [email protected] January, 2002 Key Words: Braid groups; Artin groups; Garside groups; Small Gaussian groups; Conjugacy problem. Subject Classification: Primary: 20F36. Secondary: 20F10. We present a new algorithm to solve the conjugacy problem in Artin braid groups, which is faster than the one presented by Birman, Ko and Lee [3]. This algorithm can be applied not only to braid groups, but to all Garside groups (which include finite type Artin groups and torus knot groups among others). 1. INTRODUCTION Given a group G, the conjugacy problem in Gconsists on finding an algorithm which, given a, b ∈G, determines if there exists c∈Gsuch that a=c−1bc. Sometimes one also needs to compute c, for instance, when one tries to attack cryptosystems based on conjugacy in G([2], [12]). We are mainly interested in Artin braid groups, which are defined, for n≥2, by the following presentation: 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) 1Both authors partially supported by the European network TMR Sing. Eq. Diff. et Feuill. 2Partially supported by SFRH/BD/2852/2000. 3Partially supported by BFM-3207. 1 The first conjugacy algorithm for braid groups was given by Garside [11]. It was improved by Elrifai and Morton [10] and, more recently, by Birman, Ko and Lee ([3] and [4]). In all these algorithms, one of the key points is the existence of a finite set S⊂Bn, whose elements are called simple elements, verifying some suitable properties (we will be more precise later). One of the main disadvantages is the size of S, which is always greater than 3n. In this paper we will show how one can avoid this problem by defining some small subsets of S, whose size is smaller than n−1. Their elements will be called minimal simple elements. Unlike S, these sets of minimal simple elements are not unique for every group: The suitable set of minimal simple elements must be recomputed many times in our algorithm. Nevertheless, we will see that it is much faster to compute and use these very small subsets, than to use the whole Sall the time. For instance, the known upper bound for the complexity of the Birman-Ko-Lee algorithm, to decide wether two braids aand bare conjugated in Bn, is O(kl2n3n) (where kis a number that will be explained later, and lis the maximum of the word lengths of aand b). An upper bound for the complexity of our algorithm for Bnis O(kl2n4). Let us mention that our algorithm, as well as the previous ones, also computes the element c∈Bnsuch that a=c−1bc. Moreover, since our construction relies on the existence of simple elements and their basic properties, we can extend our results to a much larger class of groups, called Garside groups. They were introduced by Dehornoy and Paris [9]. At the origin, these groups were called small Gaussian groups, but there has been a convention to call them Garside groups. They include, besides Artin braid groups, spherical (finite type) Artin groups, torus knot groups and others. One final remark: one important property of Garside groups is the existence of embedable monoids (for instance the monoid of positive braids, B+ n, which embeds in Bn). The conjugacy class of an element ain such a monoid is known to be a finite set, C+(a). We will also show how to compute C+(a), using the techniques mentioned above. This paper is structured as follows: In Section 2, we give a brief introduction to Garside monoids and groups; In Section 3, the known algorithms mentioned in this introduction are detailed; We introduce the minimal simple elements in Section 4, and in Section 5 we present our algorithms in detail; Complexity issues are treated in Section 6 and, finally, some effective computations are described in Section 7. 2. GARSIDE MONOIDS AND GROUPS The results contained in this section are well known, and can be found in [11], [10], [16], [3], [9], [8] and [14]. We will define the Garside monoids and Garside groups, and explain some basic properties. Given a cancellative monoid M, with no invertible elements, we can define two different partial orders on its elements, ≺and ≻. Given a, b ∈M, we say that a≺b(b≻a) if there exists c∈M such that ac =b(b=ca), and we say that ais a left (right) divisor of b. In this situation, we can naturally define the (left or right) least common multiple and greatest common divisor of two elements. Given a, b ∈M, we denote by a∨bthe left lcm of aand b, if it exists. That is, a minimal element (with respect to ≺) such that a≺a∨band b≺a∨b. We denote by a∧bthe left gcd of aand b, if it exists. That is, a maximal element (with respect to ≺),such that a∧b≺aand a∧b≺b. Definition 2.1. Let Mbe a monoid. We say that x∈Mis an atom if x6= 1 and if x=yz implies y= 1 or z= 1.Mis said to be an atomic monoid if it is generated by its atoms and, moreover, for every x∈M, there exists an integer Nx>0such that xcannot be written as a product of more than Nxatoms. 2 Definition 2.2. We say that a monoid Mis a Gaussian monoid if it is atomic, (left and right) cancellative, and if every pair of elements in Madmits a (left and right) lcm and a (left and right) gcd Definition 2.3. AGarside monoid is a Gaussian monoid which has a Garside element. A Garside element is an element ∆∈Mwhose left divisors coincide with their right divisors, they form a finite set, and they generate M. Definition 2.4. The left (and right) divisors of ∆in a Garside monoid Mare called simple elements. The (finite) set of simple elements is denoted by S. It is known that every Garside monoid admits a group of fractions. So we have: Definition 2.5. A group Gis called a Garside group if it is the group of fractions of a Garside monoid. The main example of a Garside monoid (actually the monoid studied by Garside) is the Artin braid monoid on nstrands, B+ n. It is defined by Presentation (1), considered as a presentation for a monoid. Its group of fractions is the braid group Bn, and Garside [11] showed that B+ n⊂Bn. Actually, every Garside monoid embeds into its corresponding Garside group [9]. The classical choice of a Garside element for B+ nis the following: ∆ = (σ1σ2···σn−1) (σ1σ2···σn−2)···(σ1σ2)σ1.It can be defined as the positive braid (braid in B+ n) in which any two strands cross exactly once (where, as usual, σirepresents a crossing of the strands in positions iand i+ 1). It is represented in Figure 1 for n= 4. The simple elements in this case are the positive braids in which any two strands cross at most once. Then one has #(S) = n! FIG. 1 The Garside element ∆ ∈B+ 4. Another important example of Garside monoid is the Birman-Ko-Lee monoid [3], which has the following presentation: BKL+ n=ats(n≥t > s ≥1) atsarq =arqats if (t−r) (t−q) (s−r) (s−q)>0 atsasr =atrats =asratr where n≥t > s > r ≥1(2) Its group of fractions is again the braid group Bn. The usual Garside element in BKL+ nis δ=an,n−1an−1,n−2···a2,1.The advantage of this monoid with respect to B+ nis that #(S) = Cn, where Cn=(2n)! n!(n+1)! <4nis the nth Catalan number. Hence, the number of simple elements is much smaller in this case, but it is still quite big, since Cn>3n. Notice also that |δ|=n−1, while in B+ n,|∆|=n(n−1) 2. As we mentioned before, there are other examples of Garside groups, such as finite type Artin groups, or torus knot groups (see [14] to find more examples of Garside groups). 3 From now on, Mwill denote a Garside monoid, Gits group of fractions and ∆ the corresponding Garside element. Since M⊂G, we will refer to the elements in Mas the positive elements of G. From the existence of left lcm’s and gcd’s, it follows that (M, ≺) has a lattice structure, and S becomes a finite sublattice with minimum 1 and maximum ∆.See in Figure 2 the Hasse diagram of the lattice of Sin B+ 4,where the lines represent left divisibility (from bottom to top). The analogous properties are also verified by ≻. FIG. 2 The lattice of simple elements in B+ 4. Definition 2.6. For a∈Mwe define LM (a)∈Sas the maximal simple left divisor of a, that is, LM (a) = ∆ ∧a. We also define RM (a)as the maximal simple right divisor of a. Proposition 2.7 ([11]).For a∈G, there exists a unique decomposition a= ∆pa1···al, called left normal form of a, where: 1. p= max {r∈Z: ∆−ra∈M}(hence a1···al∈M). 2. ai=LM (ai···al)∈S\{∆,1}, for all i= 1, ..., l. Symmetrically, one defines the right normal form of a∈G, using RM. Sometimes, if we are dealing with elements in Mand it does not lead to confusion, we will say that an element w=w1···wt∈Mis in left normal form to express that wi∈S\{1}for all iand, for some p≥0, the normal form of wis ∆pwp+1 ···wt. Later we will use these technical results: Lemma 2.8 ([13], Prop. 2.1).Let w1···wt∈Mbe in left normal form, and x1···xt∈ Min right normal form. For every v∈M, one has LM (vw1···wt) = LM (vw1)and RM (x1···xtv) = RM (xtv). Lemma 2.9 ([13], Prop. 5.3).Let w=w1···wt∈Mbe written in right normal form. If we write win any other way as a product of tsimple elements, w=u1···ut, then w1≺u1. 4 Lemma 2.10 ([7], 3.1).Let w=w1···wt∈Mbe written in right normal form, and let s∈S. Then we can decompose wi=w′ iw′′ i, for all i, in such a way that the right normal form of ws is (w′ 1)(w′′ 1w′ 2)···(w′′ t−1w′ t)(w′′ ts)if it has t+ 1 factors, or (w1w′ 2)···(w′′ t−1w′ t)(w′′ ts)if it has t factors. Corollary 2.11. Let w=w1···wt∈Mbe written in right normal form. Let s∈Sand suppose that we can write ws as a product of tsimple elements, that is, w1···wts=u1···ut. Then w1≺u1. Proof. Since ws can be written as a product of tsimple elements, then its right normal form has tfactors, say v1···vt. By Lemma 2.10, w1≺v1, and by Lemma 2.9 v1≺u1, so the result follows. We end this section with a last property of Garside groups: There is a power of their Garside element which belongs to the center. For instance, in Bnthe element ∆2=δngenerates the center of Bn. 3. KNOWN ALGORITHMS FOR THE CONJUGACY PROBLEM. We present here the Elrifai-Morton algorithm for the conjugacy problem in braid groups [10], which is also valid for Garside groups, as can be seen in [15]. It goes as follows: for every element a∈G, it computes a finite subset Csum(a) of the conjugacy class of a. This set is shown to be independent of a, so it is an invariant of its conjugacy class. Therefore, two elements aand bare conjugated if and only if Csum(a) = Csum(b). Let us explain the algorithm in more detail. 3.1. Definition of C≥m(a)and Csum(a) Proposition 3.1. [10, 15] Let a= ∆pa1···al∈Gbe in left normal form. Then the right normal form of ais as follows: a=x1···xl∆p, where land pare the same as above. Definition 3.2. Let a= ∆pa1···al∈Gbe in left normal form. We define the infimum, supremum and canonical length of a, respectively, by inf (a) = p, sup (a) = p+l, and kak=l. Definition 3.3. Let a∈Gand denote by C(a)the conjugacy class of a. We define the summit infimum, the summit supremum and the summit length of aas, respectively, max {inf (x) : x∈C(a)},min {sup (x) : x∈C(a)}and min {kxk:x∈C(a)}. Definition 3.4. Let a∈G. 1. For every integer m, we define C≥m(a) = {v∈C(a) : inf(v)≥m}. 2. We define the summit class of a,Csum (a), as the subset of C(a)containing all elements of minimal canonical length. Remarks: 1. One has C≥0(a) = C(a)∩M=C+(a). 2. In [10], Csum (a) is called the Super Summit Set. Proposition 3.5. [10, 15] For every b∈Csum(a), the infimum, supremum and canonical length of bare equal, respectively, to the summit infimum, the summit supremum and the summit length of a. It is known that C≥m(a) and Csum (a) are finite sets. Moreover, by Proposition 3.5, if C≥m(a)6=φ, then Csum (a)⊂C≥m(a). 5 3.2. Cycling and decycling Let τ:G→Gbe the automorphism defined by τ(a) = ∆−1a∆. The restriction of τto Sis a bijection τ:S→S. Definition 3.6. Let a= ∆pa1···al∈Gbe written in left normal form. The functions cycling and decycling are the maps cand d,from Gto itself, defined by: c(a) = ∆pa2···alτ−p(a1) ; d(a) = ∆pτp(al)a1···al−1. Notice that c(a) and d(a) are conjugates of a. Furthermore, for every a∈G, inf(a)≤ inf(c(a)) and sup(a)≥sup(d(a)). Suppose that we have an element a∈G, such that inf(a) is not equal to the summit infimum of a. Then we can try to increase the infimum by repeated cycling. By [10] (and [15]), this always works: there exists a positive integer ksuch that inf(ck(a)) >inf(a). We know a bound for this integer konly for some special Garside monoids and groups: If Mis homogeneous, i.e. it has only homogeneous relations (for instance, if Mis B+ nor BKL+ n), then every two words representing an element a∈Mhave the same length, denoted |a|. It is shown in [4] that, in this case, k < |∆|. Therefore, by repeated cycling, we can conjugate ato another element baof maximal infimum. Even if Mis not homogeneous, we know that we reached the summit infimum when we enter into a loop: at some point ck(v) = vfor some vconjugated to a. This always happens since the set C≥m(a) is finite for every m, in particular for the summit infimum. Once bais obtained, we can try to decrease its supremum by repeated decycling. By [10] (and [15]), this also works: either we enter into a loop, and then the supremum is minimal, or there exists an integer ksuch that sup(dk(ba)) <sup(ba). Again by [4], k < |∆|in homogeneous monoids. Therefore, using repeated cycling and decycling a finite number of times, one obtains an element ea∈Csum (a). And, if Mis homogeneous, this can be done in polynomial time in |a|. 3.3. The Elrifai-Morton algorithm Once that we obtained an element ea∈Csum(a), we can construct the whole Csum (a), by using the next result: Proposition 3.7. [10, 15] For u, v conjugate elements in Csum(a)(resp. C≥m(a)), there exists a sequence u=u1, u2, ..., uk=vof elements in Csum(a)(resp. C≥m(a)) such that, for i= 1,... ,k−1,uiand ui+1 are conjugated by an element in S. The Elrifai-Morton algorithm does the following: Given a, b ∈Git computes, using cyclings and decyclings, ea∈Csum(a) and e b∈Csum(b). Then it defines V1={ea}and it computes, by recurrence, Vi={s−1vs;s∈S, v ∈Vi−1} ∩ Csum(a). Since 1 ∈S, this creates an ascending chain of subsets of Csum(a). By the above proposition, one has Vk=Vk+1 for some k, and then Vk=Csum(a). Hence, when the chain stabilises, the whole Csum(a) has been computed. Then aand bare conjugated if and only if e b∈Csum (a). Remark 3.8. This algorithm can be modified to compute C≥m(a)for a∈Mand m∈Z. We just need to replace Csum(a)by C≥m(a)in the above discussion. 6 Notice that Csum(a) (resp. C≥m(a)) is computed at the cost of conjugating every element in Csum(a) (resp. C≥m(a)) by every element in S. All these sets are quite big, and this makes the algorithm to be slow. In what follows, we will get rid of the problem caused by the size of S, using the minimal simple elements. 4. MINIMAL SIMPLE ELEMENTS In this section we shall define some very small subsets of S, which will enable us to compute C≥m(a) and Csum(a), for a∈G, much faster than the previous algorithms. Recall the definition of the partial order ≺in M. Definition 4.1. Let Pbe a property for simple elements. We denote by SPthe set of simple elements satisfying P. The set of minimal simple elements for P,min(SP), is the set of minimal elements (with respect to ≺) in SP. We shall enforce Pto be closed under g.c.d, that is, if s1, s2∈SPthen s1∧s2∈SP. Let us see that, under this assumption, the set min(SP) turns to be very small. For every atom x∈M, let mult(x) = {s∈S;x≺s}. Lemma 4.2. Suppose that Pis closed under gcd, and let xbe an atom of M. If the set SP∩mult(x)is non-empty, then it has a unique minimal element, that we denote ρx. Proof. Suppose that there are two distinct minimal elements s1, s2∈SP∩mult(x). Since s1, s2∈SP, then s1∧s2∈SP. Moreover, since xdivides s1and s2, it also divides s1∧s2. Therefore s1∧s2∈SP∩mult(x), so s1and s2cannot be both minimal. Corollary 4.3. Suppose that Mhas matoms. If Pis closed under gcd, then #(min(SP)) ≤ m. Proof. Notice that every element in Mmust be divisible by an atom. Take s∈min(SP) and consider an atom x≺s. Since sis minimal in SP, it is also minimal in SP∩mult(x). Hence s=ρx. Therefore min(SP)⊂ {ρx:xis an atom} and the result follows. Example 4.4. In B+ nthere are n−1atoms, namely σ1,... ,σn−1. Therefore, if Pis a property closed under gcd, then min(SP)has at most n−1elements, while #(S) = n! Example 4.5. In BKL+ nthere are n(n−1) 2atoms (the generators in Presentation 2). Hence, if Pis a property closed under gcd, then #(min(SP)) ≤n(n−1) 2, while #(S) = Cn>3n. We must now define some suitable properties, closed under gcd, that will allow us to compute C≥m(a) and Csum(a), for a∈G. These properties will depend on some given elements in M, so we will have an infinite number of properties, each one corresponding to a set of minimal simple elements. 4.1. Minimal simple elements to compute C≥m(a) Definition 4.6. Let a∈Gand v∈C≥m(a), for some m∈Z. We will say that a simple element ssatisfies the property P≥m vif it conjugates vto an element in C≥m(a), that is, s−1vs ∈ C≥m(a). 7 Proposition 4.7. (Caracterization of elements satisfying P≥m v). If v∈C≥m(a), one can write v= ∆mw, where w∈M. Then a simple element ssatisfies the property P≥m vif and only if τm(s)≺ws. Proof. The first assertion comes from the definition of infimum. Let then v= ∆mw, where w∈M, and let s∈S. One has s−1vs =s−1∆mws = ∆mτm(s−1)ws = ∆m(τm(s))−1ws. Hence, ssatisfies P≥m vif and only if (τm(s))−1ws ∈M, that is, τm(s)≺ws. Proposition 4.8. For every v∈Mand every m∈Z, the property P≥m vis closed under gcd. Proof. Suppose that s1and s2satisfy P≥m v, and let s=s1∧s2. Notice that τpreserves gcd’s, since it preserves left divisibility. Hence τ(s) = τ(s1)∧τ(s2), and thus τm(s) = τm(s1)∧τm(s2). One has τm(s)≺τm(s1)≺vs1and τm(s)≺τm(s2)≺vs2. But it is easy to show that, for every v∈M,vs1∧vs2=vs. Hence, since τm(s) divides vs1and vs2then it divides its gcd, i.e. τm(s)≺vs. Therefore, ssatisfies P≥m v, and the result follows. Definition 4.9. For every v∈C≥m(a), we define S≥m v=min(SP≥m v). That is, S≥m vis the set of minimal simple elements (with respect to ≺) among those who conjugate vto an element in C≥m(a). Notice that, by Corollary 4.3 and Proposition 4.8, the cardinal of S≥m vfor every v∈C≥m(a) is no bigger than the number of atoms in M. Moreover, we have the following result, analogous to Proposition 3.7. Proposition 4.10. Given u, v ∈C≥m(a)for some a∈G, there exists a sequence u= u1, u2, ..., uk=vof elements in C≥m(a)such that, for i= 1, ..., k −1, the elements uiand ui+1 are conjugated by an element in S≥m ui. Proof. Just notice that any left or right divisor of a simple element is also a simple element, and then decompose every simple element in the sequence given by Proposition 3.7 into a product of minimal ones. This result implies that, in order to compute C≥m(a) for a∈M, it suffices to conjugate every v∈C≥m(a) by the elements in the small set S≥m v. 4.2. Minimal simple elements to compute Csum(a) Definition 4.11. Let a∈G, and let v∈Csum(a). We will say that a simple element s satisfies the property Psum vif it conjugates vto an element in Csum(a). In other words, if the canonical length of s−1vs is equal to the canonical length of v(which is the summit length of a). Proposition 4.12. For every v∈Csum(a), the property Psum vis closed under gcd. Proof. Let s1and s2be two simple elements satisfying Psum v, and denote s=s1∧s2. Write si=srifor i= 1,2, thus r1∧r2= 1. Suppose that inf(v) = pand kvk=t. Then v= ∆pv′, where v′∈Mand we can write v′as a product of tsimple elements (but not less). Since s1satisfies Psum v, one has s−1 1vs1= s−1 1∆pv′s1= ∆pτp(s−1 1)v′s1= ∆p(τp(s1))−1v′s1,where (τp(s1))−1v′s1∈Mand we can write it as a product of tsimple elements, say x1···xt. The same happens for (τp(s2))−1v′s2∈M. Now consider s−1vs. By Proposition 4.8 it belongs to C≥p(a), that is, (τp(s))−1v′s∈M. We must show that we can write this element as a product of tsimple elements. Suppose this is not true, and write (τp(s))−1v′s=z1···zt+1 in right normal form (it has no more than t+ 1 factors 8 since it is a right divisor of v′swhich has t+ 1 factors). One has x1···xt= (τp(s1))−1v′s1= (τp(r1))−1(τp(s))−1v′sr1= (τp(r1))−1z1···zt+1r1.Hence, z1···zt+1r1=τp(r1)x1···xt, and z1···zt+1 is in right normal form. Then by Corollary 2.11, z1≺τp(r1). In the same way, z1≺τp(r2). Therefore z1≺τp(r1)∧τp(r2) = τp(r1∧r2) = τp(1) = 1. A contradiction. Definition 4.13. For every v∈Csum(a), we define Ssum v=min(SPsum v). That is, Ssum v is the set of minimal simple elements (with respect to ≺) among those who conjugate vto an element in Csum(a). As before, by Corollary 4.3 and Proposition 4.12, the cardinal of Ssum vfor every v∈Mis no bigger than the number of atoms in M. Furthermore, we can adjust the algorithm by ElrifaiMorton to these new sets, since we have the following result, analogous to Propositions 3.7 and 4.10. Proposition 4.14. For u, v conjugate elements in Csum (a), there exists a sequence u= u1, ..., uk=vof elements in Csum (a)such that, for i= 1, ..., k −1, the elements uiand ui+1 are conjugated by an element in Ssum ui. The proof of this result parallels that of Proposition 4.10. It implies that, in order to compute Csum (a) for a∈G, it suffices to conjugate every v∈Csum (a) by the elements in Ssum v. We have then described small subsets of Swhich suffice to compute C≥m(a) and Csum(a). But we still need to show how to compute these subsets. This is what we do in the next section. 5. ALGORITHMS FOR THE CONJUGACY PROBLEM We shall explain in this section our algorithms to compute C≥m(a) and Csum(a), given a∈G. Let us first explain a technical algorithm, which we did not find in the literature. Let s∈S and v∈M. We will show how to compute their lcm s∨v. More precisely, our algorithm will compute a simple element s′such that s∨v=vs′. We must indicate that it is well known how to compute the lcm and the gcd of two simple elements, as well as the normal forms of any element in G. Algorithm 1 (for computing s′such that s∨v=vs′). 1. Compute the normal form of v=v1···vt. 2. s0=s. 3. For every i= 1,... ,t, compute si−1∨vi, and write it visi. 4. Return st. Proposition 5.1. Let s∈Sand v∈M. Let stbe the simple element computed by Algorithm 1. Then s∨v=vst. Proof. We proceed by induction on t= sup(v). If t= 1 the result is trivial, so suppose that t > 1 and the result is true for t−1. Denote v′=v1···vt−1. We have s∨v′=v′st−1, that is, st−1is the smallest element such that v′st−1is divisible by s. Therefore, an element r∈M satisfies s≺vr =v′(vtr) if and only if st−1≺vtr, and this is equivalent to st−1∨vt≺vtrt, that is vtst≺vtrhence st≺r. Therefore, stis the smallest element satisfying s≺vst, as we wanted to show. 9 Proposition 6.4. Given a∈BKLnas a word of length l, the complexity of computing Csum(a)(for the Birman-Ko-Lee presentation) is O(kl2n5), where kis the number of elements in Csum(a). Notice that the complexity of the known algorithm was O(kl2Cnn), so our algorithm improves it considerably. One interesting remark is that our algorithm works faster, a priori, for the monoid B+ nthan for BKL+ n. This is due to a simple fact: in our algorithm the number of atoms is more relevant than the number of simple elements. In BKL+ n, the number of simple elements is much smaller than in B+ n, but the number of atoms is n(n−1) 2, while in B+ nis n−1. 6.3. Artin monoids As we mentioned in the introduction, the Artin groups of finite type are Garside groups, so we can apply our algorithms to the corresponding Artin monoids (see [5] for an introduction to Artin monoids and groups). In [6] we can find algorithms to deal with Artin monoids: computation of normal forms, greatest common divisors, division algorithms, etc. Although these algorithms seem to be exponential in the length of the words involved, in [7] it is shown that finite type Artin groups are biautomatic, so there are quadratic algorithms to compute all of the above. Nevertheless, since we are mainly interested in comparing our algorithms with the previous ones, we just need to know the length of the Garside element ∆, and the number of simple elements in any given Artin group. Let then Gbe an Artin group of rank n, that is, An,Bn, Dn,En(if n= 6,7,8), Fn(if n= 4), Hn(n= 3,4) or I2(p) (if n= 2), and let hbe its Coxeter number. It is known that |∆|=nh 2, where h=O(n), and that #(S)≥n!. Hence, if the complexity of the conjugacy algorithm by Elrifai and Morton is O(xn!) for some xdepending on nand l, our algorithm will have complexity O(xn3). This is shown by using the same arguments as in the previous subsections. 7. EFFECTIVE COMPUTATIONS 7.1. Comparison with the Elrifai-Morton algorthim In the previous section, we found theoretical upper bounds for the complexity of our algorithms. We showed that our algorithm is, in theory, much better than the Elrifai-Morton one (for n > 5). In this section we effectively compare the two algorithms, in the following way: For given nand l, (3 ≤n≤5 and 10 ≤l≤20) we took 5000 random pairs of positive braids in Bnof length l(using Artin presentation), we tested conjugacy using both algorithms, and we compared the Average Running Time (ART) and the Maximum Running Time (MRT). We did the same for n= 6 and l= 10, for 1144 pairs. We can conclude that our algorithm is faster for n≥4, and much faster for n≥5 (We were not able to compute the cases n= 5 and l= 19,20 using the Elrifai-Morton algorithm since the computations were too long). In the tables below one can see the results: We wrote F-GM for our algorithm and E-M for the Elrifai-Morton one. The time is given 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. Exhaustive computation of conjugacy classes and summit classes In the previous section, we saw that the complexity of all our algorithms depends on the size of the sets C≥m(a) or Csum(a), for a∈M. In the cases of B+ nor BKL+ n, the only upper bounds known for these sets are exponential in nand in l=|a|. Nevertheless, we have the following (recall that, in this case, C+(a) = C≥0(a) = C(a)∩B+ n): 17 Conjecture: (Thurston, [16]) Let nbe a fixed integer and let a∈B+ n, having word length l. There is an upper bound for C+(a) which is a polynomial in l. The existence of this upper bound for C+(a), or even for Csum(a), would imply the following: Conjecture: (Birman, Ko and Lee, [4]) For every fixed integer n, there exists a solution for the conjugacy problem in Bn, which is polynomial in the word length of the elements involved. In order to have some numerical evidence to support these conjectures, we have computed, for n= 3,... ,8 and several values of l, all the conjugacy classes of words of length lin B+ n, as well as the corresponding summit classes. In the tables below we present the following data, for the set Wlof elements in B+ nhaving word length l: •CC+: The number of Conjugacy Classes in Wl⊂B+ n. •max C+: The size of the biggest one. That is, the number of elements in the biggest C+(a), for a∈Wl. •max Csum : The size of the biggest summit class. •v: A representative from one of those biggest summit class. That is, an element v∈ Csum(a), where Csum(a) has maximal size. n=3 l CC+max C+max Csum v 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 v 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 v 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 v 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 v 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 v 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 this work were developed during a stay of both authors at the Laboratoire de Topologie de l’Universit´e de Bourgogne at Dijon (France). We are very grateful to all members of the Laboratoire, and in particular to Luis Paris for his many useful suggestions. We are also grateful to Jean Michel for his precise and helpful comments on an earlier version of this paper. REFERENCES [1] E. Artin, Theory of braids, Annals of Math. 48 (1946), 101-126. [2] I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography. Math. Res. Lett. 6, No. 3-4 (1999), 287-291. [3] J. Birman, K. H. Ko and S. J. Lee, A new approach to the word and conjugacy problems in the braid groups, Adv. Math. 139, No. 2 (1998), 322-353. [4] J. Birman, K. H. Ko and S. J. Lee, The infimum, supremum and geodesic length of a braid conjugacy class, Preprint (2000). [5] N. Bourbaki, “Groupes et algebres de Lie”, Chaps. IV-VI, Hermann, Paris, 1968. [6] E. Brieskorn and K. Saito, Artin-Gruppen und Coxeter-Gruppen, Invent. Math. 17 (1972), 245-271. [7] R. Charney, Artin groups of finite type are biautomatic, Math. Ann. 292, No. 4 (1992), 671-683. [8] P. Dehornoy, Groupes de Garside, Ann. Scient. ´ Ec. Norm. Sup., 4es´erie, t. 35, 2002, 267-306. [9] P. Dehornoy and L. Paris, Gaussian groups and Garside groups, two generalizations of Artin groups, Proc. London Math. Soc. 79, No. 3 (1999), 569-604. [10] E. A. Elrifai, H. R. Morton, Algorithms for positive braids, Quart. J. Math. Oxford 45 (1994), 479-497. [11] F. A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20 (1969), 235-154. [12] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park, New publickey cryptosystem using braid groups. Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), 166-183, Lecture Notes in Comput. Sci. 1880, Springer, Berlin, 2000. [13] J. Michel, A note on words in braid monoids, J. of Algebra 215 (1999) 366-377. 20 [14] M. Picantin, Petits groupes gaussiens, Ph. D. Thesis, Universit´e de Caen (2000). [15] M. Picantin, The conjugacy problem in small Gaussian groups, Comm. Algebra 29, No. 3 (2001), 1021-1039. [16] W. P. Thurston, Braid Groups, Chapter 9 of “Word processing in groups”, D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston, Jones and Bartlett Publishers, Boston, MA, 1992. 21