Computation of centralizers in braid groups and Garside groups

Rev. Mat. Iberoamericana 19 (2003), 367–384 Computation of Centralizers in Braid groups and Garside groups Nuno Franco and Juan Gonz´alez-Meneses Abstract We give a new method to compute the centralizer of an element in Artin braid groups and, more generally, in Garside groups. This method, together with the solution of the conjugacy problem given by the authors in [9], are two main steps for solving conjugacy systems, thus breaking recently discovered cryptosystems based in braid groups [2]. We also present the result of our computations, where we notice that our algorithm yields surprisingly small generating sets for the centralizers. Introduction Given a group G,thecentralizer of an element a∈G, denoted Z(a), is the subgroup of Gconsisting of all elements which commute with a. Our goal in this paper is to give a good algorithm to compute a generating set for the centralizer of an element in a Garside group. Garside groups were introduced by Dehornoy and Paris [7] (their original name was small Gaussian groups, but there has been a convention to call them Garside groups). We will consider Artin braid groups [1] as the main examples of Garside groups. Given an integer n≥2, the braid group on nstrands,Bn,isdefinedby the following presentation: (1) Bn=σ1,σ 2,...,σ n−1 σiσj=σjσi(|i−j|≥2) σiσi+1σi=σi+1σiσi+1 (i=1,...,n−2) . 2000 Mathematics Subject Classification: Primary 20F36; Secondary 20F10, 94A60. Keywords: Braid group, Garside group, centralizer, cryptography. 368 N. Franco and J. Gonz´ alez-Meneses Braid groups are of interest not only in Combinatorial Group Theory, but also in Low Dimensional Topology and, more recently, in Cryptography. Other examples of Garside groups are spherical (finite type) Artin groups [5] and torus knot groups, among others. Computing centralizers in a Garside group is of interest in itself, but can also be applied to solve other questions. For instance, consider two elements a, b in a Garside group G. Suppose that we know an element c∈Gthat conjugates ato b,thatis,c−1ac =b. Consider then the set Za,b =cZ(b)= {cα :α∈Z(b)}⊂G.ThenZa,b is the set of all elements in Gthat conjugate ato b: Indeed, an element d∈Gconjugates ato bif and only if d−1ad =b, then b=d−1(cc−1)a(cc−1)d=(d−1c)b(c−1d), so c−1d∈Z(b); hence d∈Za,b. This property may be used for solving conjugacy systems in Garside groups: Given a1,a 2,...,a k,b 1,b 2,...,b k∈G, find an element c∈Gsuch that c−1aic=bi,fori=1,...,k. The solutions of such a system are the elements in Za1,b1∩···∩Zak,bk. These kind of problems play a central role in some new public-key cryptosystems (see [2] and [12]), based on braid groups. To break such cryptosystems, one must solve a conjugacy system such as the previous one. The conjugacy problem in braid groups has been solved by Garside [10], and his algorithm has been improved in [8] and generalized to all Garside groups in [16]. In [9], the authors gave a more efficient algorithm than all the above, to solve the conjugacy problem in all Garside groups. So, given two conjugated elements a, b ∈Bn,weknowhowtofindanelementc∈G such that c−1ac =b. Using the algorithm that we shall explain in this paper, we can compute a generating set for Z(b), hence we know how to generate elements in Za,b. We still do not know how to compute an element in Za1,b1∩···∩Zak,bkeven if we know how to generate elements in each Zai,bi. We believe that a deeper study of the structure of centralizers in Garside groups will provide a solution to this problem. Anyway, we think that the algorithm we give to compute centralizers in Garside groups is a good step towards the solution of these systems. There exists another algorithm to compute the centralizer of an element in braid groups, which was given by Makanin [14]. It can be easily generalized to all Garside groups, but it is a fairly theoretical algorithm, which has a huge complexity and gives a large amount of redundant generators. One could also make use of the bi-automatic structure of Garside groups [6] to find the centralizer of an element. But this also seems quite inefficient. The new method that we introduce is quite simple and surprisingly efficient. Actually, the generating sets obtained in our computations with braid groups are so small, that they led us to conjecture that the centralizer of any braid in Bncan be generated by no more than n−1elements. Computation of Centralizers in Braid groups and Garside groups 369 After writing an early version of this paper, we were told by M. Korkmaz of a family of counterexamples to this conjecture, due to N. V. Ivanov (the smallest counterexample belongs to B9, while our computations were up to B8). Nevertheless, it has been recently proven by the second author and Bert Wiest [11] that, for a∈Bn,Z(a) can be generated by less than k(k+1) 2 elements if n=2kand k(k+3) 2elements if n=2k+1. The algorithm in this paper works as follows: given an element ain a Garside group G, it constructs a graph Γ associated to a, such that the fundamental group of Γ maps onto Z(a). Then it computes a generating set for the fundamental group of Γ, which maps to a generating set for Z(a). This paper is structured in the following way: In Section 1 we give the basic definitions and results concerning Garside groups. In Section 2, we introduce a special kind of elements, the minimal simple elements,which are used to construct the graph Γ. This graph is studied in Section 3. We explain our algorithm in detail in Section 4, then we study its complexity in Section 5 and, finally, in Section 6 we present the results obtained by implementing the algorithm. 1. Garside groups and simple elements In this section we will give the definitions of Garside monoids and groups, and the basic results which we shall need to present our algorithm. To find the proofs of the results, and more details, see [10], [8], [17], [3], [7], [6] and [15]. Consider a cancellative monoid M, with no invertible elements. We can define a partial order on its elements, called the prefix order, as follows: For a, b ∈M,wesaythata≺bif bcan be written in such a way that ais a prefix of b, that is, if there exists c∈Msuch that ac =b.Inthiscase,we say that ais a left divisor of b. There also exists the suffix order, but we will not use it in this paper, so in the above situation we will just say that adivides b,orthatbis a multiple of a. Given a, b ∈M, we can naturally define their (left) least common multiple,a∨b,andtheir(left)greatest common divisor,a∧b, if they exist. That is, a∨bis the minimal element (with respect to ≺) such that a≺a∨band b≺a∨b. Inthesameway,a∧bis the maximal element (with respect to ≺) such that a∧b≺aand a∧b≺b. Definition 1 Let Mbe a monoid. We say that x∈Mis an atom if x=1and if x=yz implies y=1or z=1.Mis said to be an atomic monoid if it is generated by its atoms and, moreover, for every a∈M,there exists an integer Na>0such that acannot be written as a product of more than Naatoms. 370 N. Franco and J. Gonz´ alez-Meneses Definition 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) l.c.m. and a (left and right) g.c.d. Definition 3 AGarside monoid is a Gaussian monoid which has a Garside element.AGarside element is an element ∆∈Mwhose left divisors coincide with their right divisors, they form a finite set, and they generate M. Definition 4 The left (and right) divisors of ∆in a Garside monoid Mare called simple elements. We denote by Sthe(finite)setofsimpleelements. It is known that every Garside monoid admits a group of fractions, and we have: Definition 5 AgroupGis called a Garside group if it is the group of fractions of a Garside monoid. The main example of a Garside monoid, as with groups, 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 [10] showed that B+ n⊂Bn.Actually, every Garside monoid embeds into its corresponding Garside group [7]. Braids in Bnare usually represented as ndisjoint strands in R3,whose endpoints are fixed, where every horizontal plane between the top and the bottom level intersects each strand in exactly one point, as in Figure 1. Simple elements in B+ nare easy to recognize: they are those braids in which any two strands cross at most once. The Garside element of B+ n is ∆ = (σ1σ2···σn−1)(σ1σ2···σn−2)···(σ1σ2)σ1,and is represented in Figure 1 for n= 4 (where, as usual, σirepresents a crossing of the strands in positions iand i+1). 1234 Figure 1: The Garside element ∆ ∈B+ 4. Computation of Centralizers in Braid groups and Garside groups 371 There is another important example of Garside monoid, the Birman-KoLee 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,wheren≥t>s>r≥1 Its group of fractions is again the braid group Bn. The Garside element in BKL+ nis δ=an,n−1an−1,n−2···a2,1.In this monoid we can perform some computations concerning braid groups faster than using Artin monoids. Anyway, using the algorithm in [9], the conjugacy problem has virtually the same complexity in both monoids. 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 l.c.m.’s and g.c.d.’s, it follows that (M,≺)hasa lattice structure, and Sbecomes a finite sublattice with minimum 1 and maximum ∆. In Figure 2 we can see the Hasse diagram of the lattice of simple elements in B+ 4, where the lines represent left divisibility (from bottom to top). σ2σ3σ2σ1 σ2σ1σ3σ2 σ1σ3σ2σ1 σ1σ2σ3σ2 σ1σ2σ1σ3 σ1σ2σ3σ2σ1σ2σ1σ3σ2σ1 σ3σ2σ1 ∆ σ2σ3σ2 σ2σ1σ3 σ1σ3σ2 σ1σ2σ3 σ1σ2σ1 σ3σ2 σ2σ3 σ2σ1 σ1σ3 σ1σ2 σ3 σ2 σ1 1 σ1σ2σ1σ3σ2 Figure 2: The lattice of simple elements in B+ 4. We end this section with an important result concerning Garside groups. Theorem 6 [7] For every element ain a Garside group G, there exists a unique word in the atoms of G(and their inverses) representing a,called the normal form of a, and there exists an algorithm that, given a word w in the atoms and their inverses, computes the normal form of the element represented by w. 372 N. Franco and J. Gonz´ alez-Meneses 2. Minimal simple elements Simple elements represent a key concept in almost every algorithm concerning Garside groups (or braid groups): they have been used to compute bi-automatic normal forms in [17] and [6], to solve the conjugacy problem in [16], [8] and [3], and to compute centralizers in [14]. In some cases, the complexity of these algorithms is too big due to the size of the set S.For instance, in B+ n, the cardinal of Sis n!, and this makes the algorithm in [8] work too slowly. This problem was avoided in [9], by considering minimal simple elements. We will also use minimal simple elements in this paper, so this section is devoted to them. Given an element ain a Garside group G, there exists a subset Csum(a)of the conjugacy class of a, called Summit Class of a, satisfying some suitable properties. In [8], when talking about braids, this subset is called Super Summit Set, but when we talk about Garside groups we prefer to use the terminology in [16]. Roughly speaking, Csum(a) is the set of conjugates of a having the ‘simplest’ normal form, in a certain sense. Hence, Csum(a)isan invariant of the conjugacy class of a(it does not depend on a, but on its conjugacy class). There exists a procedure, called ‘cycling and decycling’, to obtain an element a∈Csum(a) and an element xsuch that x−1ax =a(see [8]). The centralizers of aand aare then related as follows: Z(a)=xZ(a)x−1. Hence, if we know a generating set for Z(a), we obtain immediately a generating set for Z(a), with the same number of elements: it suffices to conjugate every generator by x. Therefore, we will just study the elements in the Summit Class of a. Consider an element v∈Csum(a). If we conjugate vby a nontrivial simple element, we obtain an element in G, that may or may not be in Csum(a). We will consider just the elements in S\{1}that conjugate v to an element in Csum(a). Among these simple elements, we take those which are minimal with respect to ≺, and we call this set Ssum v.Inother words, we define Ssum vas the set of minimal elements (with respect to ≺) in {s∈S\{1}:s−1vs ∈Csum(a)}. There are two important results concerning these minimal simple elements: Proposition 7 [9] Let Mbe a Garside monoid with tatoms, Gits corresponding Garside group, and a∈G. For every v∈Csum(a), the cardinal of Ssum vis no bigger than t. Proposition 8 [9] Let u, v be two conjugate elements in Csum(a).Then there exists a sequence u=u1,u 2,...,u k=vof elements in Csum(a)such that, for i=1,...,k−1, there exists si∈Ssum uiverifying uisi=siui+1. Computation of Centralizers in Braid groups and Garside groups 373 We will represent the above property as follows: u=u1 s1 −→ u2 s2 −→ u3→···→uk−1 sk−1 −→ uk=v, where si∈Ssum uifor every i, and the arrow means conjugation by the corresponding si. We call such a sequence a minimal chain from uto v. Example 1 Consider the braid monoid B+ 4. Aswesawintheprevious section, the set of simple elements in B+ 4has 24 elements (see Figure 2). Consider σ1∈Csum(σ1)⊂B4.ThenSsum σ1={σ1,σ 2σ1,σ 3}.Theconjugates of σ1by these three elements are, respectively, σ1,σ2and σ1.All of them lie in Csum(σ1). The conjugating elements are clearly minimal: σ1and σ3do not have nontrivial divisors, and the only nontrivial divisor of σ2σ1is σ2, which does not conjugate σ1to a positive element (hence to an element in Csum(σ1)). Remark 1 It is shown in [9] that for every v∈Csum(a)and every atom x, there exists at most one element s∈Ssum vwhich is a multiple of x.This is why the cardinal of Ssum vis bounded by the number of atoms. In B+ n,the atoms are σ1,...,σ n−1, and in the above example we can clearly see which element in Ssum σ1corresponds to each atom. In general, for a given v∈Csum(a), there are strictly fewer minimal simple elements than atoms, as we can see in the following example: Example 2 Let v=σ1σ2∈Csum(σ1σ2)⊂B+ 4.ThenSsum v={σ1,σ 3σ2σ1}. Indeed, conjugating we obtain σ−1 1(σ1σ2)σ1=σ2σ1,and (σ3σ2σ1)−1σ1σ2(σ3σ2σ1)=σ2σ3. But the minimal multiple of σ2which conjugates vto a positive element is σ2σ1σ2, which is also a multiple of σ1,soitisnotinSsum v(since it is not minimal). In [9] the authors give an algorithm to compute Ssum v,givenv∈Csum(a), and use it to compute the whole Summit Class of any element. Sometimes, a problem can be solved using either simple elements, or minimal simple elements. The latter possibility is usually much faster. For instance, in the braid monoid B+ n, computing the set Ssum vtakes time O(l2n4), where lis the word-length of v. After performing this fast computation, we can work with a set of less than n−1elements(Ssum v), instead of a set with n!elements(S). In order to compute centralizers in Garside groups, Makanin [14] used simple elements, but we are going to see in the next section how the use of minimal simple elements, and a new approach to the problem, can make the computations much faster. 374 N. Franco and J. Gonz´ alez-Meneses 3. Minimal summit graph We shall explain in this section a new approach to our problem, which involves the fundamental group of a certain graph. Consider an element a in a Garside group G. We want to find a generating set for the centralizer of a. As we said in Section 1, we will study the elements in its Summit Class Csum(a). Let us construct a directed graph Γ, that we call minimal summit graph of a. The vertices of Γ are the elements in Csum(a). The arrows of Γ are labelled by simple elements, in the following way: For every two vertices v and w, an arrow labelled by sgoes from vto wif and only if s∈Ssum vand s−1vs =w. In other words, sis a minimal simple element that conjugates v to an element in Csum(a), and wis the result of that conjugation. Therefore, every path in Γ going from a vertex uto another vertex v, and moving always in the sense of the arrows, is a minimal chain from uto v(see Proposition 8). The minimal summit graph of σ1∈B+ 4is represented in Figure 3, and that of σ1σ2in Figure 4. σ2σ1 σ1σ2 σ3σ2 σ2σ3 σ1σ2σ3 σ1 σ3 σ1 σ3 σ2 Figure 3: Minimal summit graph of σ1∈B+ 4. σ3 σ1σ2σ3σ1σ2σ3 σ2σ3 σ1σ2σ2σ1 σ3σ2 σ1 σ2 σ2 σ3σ2σ1 σ3σ2σ1 Figure 4: Minimal summit graph of σ1σ2∈B+ 4. The main idea in our algorithm is the following: Given a∈Csum(a), every element in Z(a) can be seen as a loop in Γ, based at a.Soevery generating set for the fundamental group of Γ corresponds to a generating set for Z(a) (recall that if we know a generating set for Z(a), we also know a generating set for Z(a)). Computation of Centralizers in Braid groups and Garside groups 375 We devote the rest of this section to proving this. We shall need the following results: Lemma 9 For every a∈G,thecentralizerofacan be generated by elements in M. Proof. Let c∈Z(a). We will try to write cas a product of positive elements in Z(a) (and their inverses). We know by [7] that there is an integer ksuch that ∆kis in the center of G(thus in Z(a)), and another integer r,big enough, such that ∆krc∈M. Hence, c=(∆ kr)−1(∆krc), where ∆kr and ∆krcbelong to M∩Z(a). This implies the result.  Theorem 10 [16] Let u, v ∈Csum(a)and x∈Msuch that x−1ux =v.Let s∈Sbe the maximal simple prefix of x, that is, sis maximal (with respect to ≺) among the simple elements dividing x.Thens−1us ∈Csum(a). Corollary 11 Let u, v ∈Csum(a),andx∈Mas above. Then there exists a decomposition x=s1s2···sk−1,andkelements u=u1,u 2,...,u k=v∈ Csum(a), such that u=u1 s1 −→ u2 s2 −→ u3→···→uk−1 sk−1 −→ uk=v, is a minimal chain from uto v. Proof. First, let us decompose x=t1t2···tp−1, where for every i,tiis the maximal simple prefix of titi+1 ···tp−1(this is the left greedy normal form of x, in the sense of [17]). By Theorem 10, we obtain a chain u=w1 t1 −→ w2 t2 −→ w3→···→wp−1 tp−1 −→ wp=v, where wi∈Csum(a)fori=1,...,p. But this chain is not necessarily minimal. Now, for every ti, we proceed as follows: if it is minimal (among the simple elements that conjugate wito an element in Csum(a)), we do not touch it. Otherwise, there exists an element r∈Ssum widividing ti.Sowecan decompose the arrow wi ti −→ wi+1 as wi r −→ wr −→ wi+1,whereti=rr  and w∈Csum(a). If ris not minimal, we decompose it in the same way. If we continue this process we obtain, at each step, a decomposition ti=r1···rm, where every rjis a simple element. Hence we have a chain r1≺r1r2≺r1r2r3≺ ··· ≺ (r1···rm) of simple elements. But the length of such a chain is bounded above, since there is a finite number of simple elements. Therefore, we cannot decompose tiindefinitely, and this process must stop. At the end, we will have decomposed every tias a product of minimal simple elements, so the result follows.  382 N. Franco and J. Gonz´ alez-Meneses When nbecomes bigger, it is more difficult to eliminate generators by hand. Nevertheless, we can show as an example the following table, where we can see a representative for every conjugacy class of elements of length 6 in B+ 4. We were able to reduce the number of generators to be less than or equal to3ineverycase: Centralizers of braids in B+ 4of length 6 aGenerators for Z(a) σ6 1σ1σ3σ2σ2 1σ2 σ5 1σ2σ3σ2σ2 1σ2σ3σ2 1σ2σ−3 1σ5 1σ2 σ5 1σ3σ1σ3σ2σ1σ3σ2 2σ1σ3σ2 σ4 1σ2 2σ3σ2σ2 1σ2σ3σ1σ2σ2 1σ2σ1σ4 1σ2 2 σ4 1σ2σ3σ2 1σ2σ1σ3σ−2 2σ−3 1σ4 1σ2σ3σ1σ2σ2 1σ2σ1σ3σ2σ−2 1 σ3 1σ3σ1σ3σ1σ3σ2σ1σ3σ2 2σ1σ3σ2 σ3 1σ3 2σ1σ2σ−2 1σ3σ2σ2 1σ2σ3σ1σ2σ2 1σ2σ1 σ3 1σ2 2σ3σ1σ2σ1σ3σ1σ2σ3σ2σ−2 1σ3 1σ2 2σ3 σ3 1σ2σ3σ2σ2 1σ3σ2σ−1 3σ−2 2σ−1 1σ1σ2σ1σ2σ1σ3σ2σ−1 1σ3 1σ2σ3σ2 σ1σ3σ1σ3σ1σ3σ1σ2σ1σ3σ2σ3 σ1σ2σ2 1σ2σ1σ1σ2σ3σ2σ2 1σ2σ3 σ2 1σ2σ1σ3σ2σ1σ2σ−1 1σ1σ3σ2σ3σ−1 2 σ2 1σ3 2σ3σ1σ2σ1σ3σ1σ2σ3σ2σ1σ−1 2σ−2 1σ2 1σ3 2σ3 σ2 1σ2 2σ2 3σ1σ2σ1σ3σ2 2σ3σ2σ1σ−1 2σ−2 1σ3 1σ2σ1σ3σ2σ−1 1σ2 1σ2 2σ2 3 σ2 1σ2σ2 3σ2σ3σ1σ2σ−1 1σ2 1σ2σ2 3σ2 σ1σ4 2σ3σ1σ3 2σ−1 3σ−1 1σ−1 2σ−1 1σ2 1σ2σ1σ3σ2 Actually, every time that we tried to reduce the number of generators associated to a conjugacy class, we were able to keep just n−1. Remark also that there are 1634 different conjugacy classes of elements of length l (4 ≤l≤20) in B+ 3, all of them with no more than two generators. So all these evidences led us to think that the centralizer of every braid in Bn could be generated by at most n−1elements. As we said, this conjecture turned out to be false, since a family of counterexamples due to N. V. Ivanov gives a lower bound for the number of generators which is a quadratic in n. Precisely, there has been recently shown [11] that the centralizer of every element in Bncan be generated by less than k(k+1) 2elements if n=2kand k(k+3) 2if n=2k+1. In any case, the above results are valid just for braids, so we still would like to have an upper bound for the minimal number of generators of Z(a), in the general case of Garside groups. Computation of Centralizers in Braid groups and Garside groups 383 Acknowledgements: The authors want to thank the Laboratorie de Topologie de l’Universit´e de Bourgogne, where we started to work in this subject, and to Luis Paris, Alain Jacquemard, Jos´eMar´ıa Tornero, Carmen Le´on, Mustafa Korkmaz, Arkadius Kalka and Bert Wiest for their valuable help. References [1] Artin, E.: Theory of braids. Annals of Math. 48 (1946), 101–126. [2] Anshel, I., Anshel, M. and Goldfeld, D.: An algebraic method for public-key cryptography. Math. Res. Lett. 6(1999), no. 3-4, 287–291. [3] Birman, J., Ko, K. H. and Lee, S. J.: A new approach to the word and conjugacy problems in the braid groups. Adv. Math. 139 (1998), no. 2, 322–353. [4] Birman, J., Ko, K. H. and Lee, S. J.: The infimum, supremum and geodesic length of a braid conjugacy class. Adv. Math. 164 (2001), 41–56. [5] Brieskorn, E. and Saito, K.: Artin-Gruppen und Coxeter-Gruppen. Invent. Math. 17 (1972), 245–271. [6] Dehornoy, P.: Groupes de Garside. Ann. Sci. ´ Ecole Norm. Sup. (4) 35 (2002), 267–306. [7] Dehornoy, P. and Paris, L.: Gaussian groups and Garside groups, two generalizations of Artin groups. Proc. London Math. Soc. 79 (1999), no. 3, 569–604. [8] Elrifai, E. A. and Morton, H. R.: Algorithms for positive braids. Quart. J. Math. Oxford 45 (1994), 479–497. [9] Franco, N. and Gonz´ alez-Meneses, J.: Conjugacy problem for braid groups and Garside groups, to appear in Journal of Algebra. Available at http://arxiv.org/math.GT/0112310 [10] Garside, F. A.: The braid group and other groups. Quart. J. Math. Oxford 20 (1969), 235–154. [11] Gonz´ alez-Meneses, J. and Wiest, B.: On the structure of the centralizer of a braid. In preparation. [12] Ko, K. H., Lee, S. J., Cheon, J. H., Han, J. W., Kang, J. and Park, C.: New public-key cryptosystem using braid groups. In Advances in cryptology–CRYPTO 2000 (Santa Barbara, CA), 166–183. Lecture Notes in Comput. Sci. 1880, Springer, Berlin, 2000. [13] Lyndon, R. C. and Schupp, P. E.:Combinatorial group theory.Reprint of the 1977 edition. Classics in Mathematics, Springer-Verlag, Berlin, 2001. 384 N. Franco and J. Gonz´ alez-Meneses [14] Makanin, G. S.: The normalizers in the braid group. Mat. Sb. (N. S.) 86 (128) (1971), 171–179. [15] Picantin, M.:Petits groupes gaussiens. Ph. D. Thesis, Universit´ede Caen, 2000. [16] Picantin, M.: The conjugacy problem in small Gaussian groups. Comm. Algebra 29 (2001), no. 3, 1021–1039. [17] Thurston, W. P.: 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. Recibido: 8 de abril de 2002 Revisado: 10 de diciembre de 2002 Nuno Franco Departamento de Matem´atica CIMA-UE, Universidade de ´ Evora 7000-´ Evora, Portugal [email protected] Juan Gonz´alez-Meneses Departamento de Matem´atica Aplicada I ETS Arquitectura, Universidad de Sevilla Avda. Reina Mercedes 2, 41012-Sevilla, Spain [email protected] This paper is dedicated to Jos´e Luis Vicente C´ordoba, on his 60th birthday. Both authors partially supported by the European Network TMR Sing. Eq. Diff. et Feuill. N. Franco partially supported by SFRH/BD/2852/2000. J. Gonz´alez-Meneses partially supported by MCYT, BFM2001-3207 and FEDER.