Conjugacy in Garside groups I: Cyclings, powers, and rigidity
Abstract
In this paper a relation between iterated cyclings and iterated powers of elements in a Garside group is shown. This yields a characterization of elements in a Garside group having a rigid power, where ‘rigid’ means that the left normal form changes only in the obvious way under cycling and decycling. It is also shown that, given X in a Garside group, if some power X m is conjugate to a rigid element, then m can be bounded above by ||∆||3. In the particular case of braid groups {Bn, n ∈ N}, this implies that a pseudo-Anosov braid has a small power whose ultra summit set consists of rigid elements. This solves one of the problems in the way of a polynomial solution to the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in braid groups. In addition to proving the rigidity theorem, it will be shown how this paper fits into the authors’ program for finding a polynomial algorithm to the CDP/CSP, and what remains to be done.
Full text
arXiv:math/0605230v1 [math.GT] 9 May 2006 Conjugacy in Garside Groups I: Cyclings, Powers, and Rigidity Joan S. Birman∗Volker Gebhardt Juan Gonz´alez-Meneses† May 8, 2006 Abstract In this paper a relation between iterated cyclings and iterated powers of elements in a Garside group is shown. This yields a characterization of elements in a Garside group having a rigid power, where ‘rigid’ means that the left normal form changes only in the obvious way under cycling and decycling. It is also shown that, given Xin a Garside group, if some power Xmis conjugate to a rigid element, then mcan be bounded above by ||∆||3. In the particular case of braid groups {Bn, n ∈N}, this implies that a pseudo-Anosov braid has a small power whose ultra summit set consists of rigid elements. This solves one of the problems in the way of a polynomial solution to the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in braid groups. In addition to proving the rigidity theorem, it will be shown how this paper fits into the authors’ program for finding a polynomial algorithm to the CDP/CSP, and what remains to be done. Contents 1 Introduction 2 1.1 Garside groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Solving the word and conjugacy problems in Garside groups . . . . . . . . . . . . . . . . . 6 1.3 The Thurston-Nielsen trichotemy in the braid groups . . . . . . . . . . . . . . . . . . . . . 12 1.4 A project to solve the conjugacy problems in braid groups and a summary of our results . 13 2 Cyclings and powers. 15 2.1 Decomposition of powers of X. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Interplay between Cmand Rm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 The absolute initial and final factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 The stable ultra summit set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 Rigidity 27 3.1 Rigidity of an element and behavior under cyclings and powers. . . . . . . . . . . . . . . . 27 3.2 The ultra summit set of a rigid element is made of rigid elements . . . . . . . . . . . . . . 31 3.3 Elements having a rigid power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Consequences for pseudo-Anosov braids. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.5 A bound for the rigid power of an element. . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ∗Partially supported by the U.S. National Science Foundation under Grants DMS-9973232 and 0405586. †Partially supported by MTM2004-07203-C02-01 and FEDER. 1
1 Introduction Braid groups Bn, n = 1,2,3, . . ., were introduced in a foundational paper by Emil Artin [3] in 1925. In it Artin gave the well-known presentation: (1) Bn=σ1,...,σn−1σiσj=σjσiif |i−j|>1, σiσjσi=σjσiσjif |i−j|= 1.. 1 ··· i−1 i i+ 1 i+ 2 ··· n Figure 1: The elementary braid σi. The elementary braid σiis depicted in Figure 1. To study BnArtin used the fact that there is a canonical homomorphism π:Bn→Σn, where the image is the symmetric group, defined by sending a braid to the associated permutation of its endpoints. He went on to uncover the structure of the kernel of π, and used what he learned to solve the word problem in Bn: to decide, for arbitrary words X, Y in the generators and their inverses, whether they represent the same element of Bn. Artin also posed the conjugacy decision problem (CDP): to decide whether, for arbitrary X, Y ∈Bn, there exists Z∈Bnsuch that Y=Z−1XZ. A different but related problem, the conjugacy search problem (CSP) asks to find Z, provided that one knows that it exists. During the period 1925-1969 various efforts were made to solve the conjugacy problem, building on techniques which had been introduced in [3], but there was no significant progress. Then, in 1969 F. Garside [21] brought completely new techniques to bear, looking at Bnin a very new way which stressed the similarity of its combinatorics to those of Σn, rather than focussing on ker(π:Bn→Σn). Garside succeeded in solving both the word and conjugacy search problems simultaneously, and in a unified way. His methods were soon shown to apply to other groups too [12],[17], and over the years broadened to an entire class of groups which subsequently became known as Garside groups. The ideas that Garside introduced, and their subsequent improvements, are the subject of this paper, which is the first in a series with the unifying title ‘Conjugacy in Garside groups I, II, III,... They have a common goal: to improve Garside’s algorithm for the CDP/CSP in a Garside group to obtain, in the particular case of the braid group Bn, an algorithm which is polynomial both in nand an appropriate measure ||X||,||Y|| of the complexity of Xand Y. This would have implications as regards the security of certain codes in public key cryptography [2, 26]. The existence of such a polynomial algorithm for the word problem in all Garside groups is now known via the work of [18, 19] for the braid groups. In [15] and [14] the class of Garside groups is defined in a more general setting, and shown to be biautomatic. It is a consequence of the way the definitions were chosen in [15, 14] that in fact, Garside’s algorithm solves the word and CDP/CSP’s in all Garside groups. Our work in this paper is a step in a program that we have developed to prove that the CDP/CSP in Bn is polynomial in both nand ||X||. But all results in this paper are valid in every Garside group, except the results in §3.4 and Theorem 3.37, where we consider applications of these results to the special case of braid groups, in particular to pseudo-Anosov braids. Before we can state exactly what we do in this paper, and describe it in context, we need to set up necessary notation and review the known results and techniques. The combinatorial structure that we will use, and the new structure that we have uncovered, is quite complicated and, we think, interesting. In order to make this paper accessible to non-experts we give details and examples which those who are acquainted with the literature will probably wish to bypass quickly, moving on to §1.4, where we describe 2
the essential content of this paper and its context in our larger goal, and thence to §2, where our new contributions begin. Acknowledgements: J.Birman and J. Gonzalez-Meneses, who were working together, and V. Gebhardt, became acquainted with each other’s partial results at a conference in the Banff International Research Station for Mathematical Innovation and Discovery, in October 2004. There was some overlap, and also some recognition that differing viewpoints could lead to progress, so they decided to pool forces at that time. The three authors thank the PIMS, MSRI, MITACS and IM-UNAM for their wisdom in sponsoring international conferences which foster exactly this kind of fruitful interchange and collaboration. J. Birman thanks the Project MTM2004-07203-C02-01 of the Spanish Ministerio de Ciencia y Tecnolog´ıa for hosting her visit to Seville in November 2004, so that she and J. Gonzalez-Meneses could work together on this project. J. Gonz´alez-Meneses thanks the project MTM2004-07203-C02-01 and the Columbia University Department of Mathematics for hosting his two visits to New York, in July 2004 and March-April 2006. V. Gebhardt thanks the department of Algebra of the University of Seville, and the Junta de Andaluc´ıa, for funding his visit to Seville in January 2006. The work in this paper and [9, 10], which are being completed at this writing, was done simultaneously and independently from the work of S.J. Lee and E.K.Lee in [29, 30, 31]. We first became aware of that work when we were in the process of writing up this one. Some of this work, notably Proposition 2.23 below and the results in [9], were reported on in talks at conferences in Banff in October 2004 and Luminy in June 2005. 1.1 Garside groups Among the known equivalent definitions of Garside groups, we use the one which was suggested to us by John Crisp [13], because it seems the most natural of the many possible definitions. A group Gis said to be a Garside group if it satisfies properties (A), (B) and (C) below: (A) Gadmits a lattice order (G, ,∨,∧), invariant under left-multiplication. This means that there is a partial order on the elements of Gsuch that abimplies ca cb for every c∈G. Also, every pair of elements s, t ∈Gadmits a unique lcm s∨tand a unique gcd s∧t with respect to . This partial order defines a submonoid P⊂G, called the positive cone of G, defined by P={p∈G; 1 p}. Notice that the invariance of under left-multiplication implies that P∩P−1={1}, and also that ab⇐⇒ a−1b∈P. Hence the submonoid Pdetermines the partial order , so we shall equally talk about the lattice (G, P). We remark that if a, b ∈P then abif and only if ais a prefix of b, that is, there exists c∈Psuch that ac =b. This is why is sometimes called the prefix order. There is also a related suffix order, defined by baif ba−1∈P. It is important that abdoes not imply that ba. Sometimes we will get genuinely new information by using both orderings, even when the proofs are little more than copies of one-another. (B) There exists an element ∆ ∈P, called the Garside element, satisfying: (a) The interval [1,∆] = {s∈G; 1 s∆}generates G. Its elements are called the simple elements of G. We shall always assume that [1,∆] is finite, that is, that Ghas finite type. (b) Conjugation by ∆ preserves the positive cone P: ∆−1P∆ = P. We remark that if ∆ satisfies both (a) and (b), then [1,∆] also generates Pas a monoid, which is one of the properties usually required in the definition of a Garside element. (C) The monoid Pis atomic. This means that for every x∈Pthere exists an upper bound on the length of a (strict) chain 1≺x1≺ · · · ≺ xr=x. In other words, if we define the atoms of Gas the elements a∈Pwhich 3
cannot be decomposed in P(there are no nontrivial b, c ∈Psuch that a=bc), then for every x∈P there exists an upper bound on the number of atoms in a product x=a1a2···arwith each aian atom. In particular, if Pis atomic, one can define the length of an element x∈Pas the maximal length of such a chain, that is, ||x|| =max{n:x=a1a2···an,where ai∈P\{1} }. Notice that the atoms generate G. These data determine a Garside structure on G, which may be defined as follows: Let Gbe a countable group, Pbe a submonoid, and ∆ ∈P. The triple (G, P, ∆) is said to be a (finite type) Garside structure on Gif (G, P) is a lattice, ∆ is a Garside element (with [1,∆] finite), and Pis atomic. We remark that a given group Gmay admit more than one Garside structure. Example 1: Our first example is very simple: We consider the braid group B3and its two known Garside structures: 1A. The classical Garside structure is associated to the presentation (1) of B3. The Garside element is σ1σ2σ1=σ2σ1σ2. The elements in Pcorrespond to the braids in which all crossings are positive. The atoms are σ1and σ2. 1B. If we set x=σ1, y =σ2, z =σ2σ1σ−1 2we get the presentation hx, y, z |xy =yz =zxi. The Garside element is now ∆ = xy. See [37] for the way in which this structure was used to solve the shortest word problem in B3and to give an algorithm for determining the genus of knots and links which are closed 3-braids. This Garside structure was generalized to all nin [7]. Example 2: Free abelian groups of finite rank. This is another very simple example of a Garside group: Zn=hx1,...,xn|xixj=xjxi, i < ji. The positive cone is Nn={xe1 1···xen n;ei≥0,∀i}. The Garside element is ∆ = x1···xn, and the simple elements have the form xe1 1···xen nwhere ei∈ {0,1} for every i= 1,...,n. Hence there are 2nsimple elements. Example 3: The braid group Bn, with the classical Garside structure: Garside used the presentation (1). The usual Garside structure in this group is determined by (Bn, B+ n,∆), where B+ nis the monoid of positive braids, consisting of the elements in Bnthat can be written as a product of σi’s with no σ−1 i, and (2) ∆ = (σ1)(σ2σ1)(σ3σ2σ1)···(σn−1···σ1) is a half-twist on all of the strands. The atoms are σ1,...,σn−1. The elements in Pcorrespond to the braids in which all crossings are positive. The Garside element ∆ can be characterized as the only positive braid in which every pair of strands cross exactly once. The simple elements, in the case of Bn, are the positive braids in which every pair of strands cross at most once. It follows that every simple element corresponds to a permutation on the set of nelements (the strands). Hence there are n! simple elements in B+ n, with this Garside structure. Figure 2 shows the Hasse diagram representing the lattice of simple elements in B+ 4. In this diagram, an element ais joined by a line to an element bin the upper row if and only if ab. Moreover, each line type corresponds to a right multiplication by an atom: a single line corresponds to σ1, a double line to σ2and a dotted line to σ3. This lattice of simple elements determines the whole Garside structure of the group. Example 4: Spherical type Artin-Tits groups: [11] The previous three examples were particular cases of Artin-Tits groups. All Artin-Tits groups of spherical type are known to be Garside groups [12]. Given a finite set S, a Coxeter matrix over Sis a symmetric matrix M= (mst)s,t∈S, where mss = 1 for 4
Figure 2: The lattice of simple elements in B+ 4. They are 4! = 24 elements. all s∈Sand ms,t ∈ {2,3,··· ,∞}. Every Coxeter matrix Mdefines a group AMgiven by the following presentation: AM=*Sstst ··· |{z } mst terms =tsts ··· | {z } mst terms ,for all s, t ∈S+, where mst =∞means that there is no relation involving sand t. The group AMis called the Artin-Tits group associated to M, also called Artin group or generalized braid group. If one adds to the above presentation the relations s2= 1 for all s∈S, one obtains the group WM, called the Coxeter group associated to M. An Artin-Tits group is said to be of spherical type if its corresponding Coxeter group is finite. The usual Garside structure in these groups is given by (AM, A+ M,∆), where A+ Mis the monoid of positive elements, consisting of products of elements of S(the above presentation of AM, considered as a monoid presentation, gives A+ M), and the Garside element ∆ is defined as follows. The set of generators Scan be decomposed into two sets S=S1∪S2, where elements contained in the same set Sicommute. This decomposition can be easily obtained from the Coxeter graph of the group. The reader is referred to [11] for the definition of a Coxeter graph and its associated Coxeter matrix, and also for a list of the Coxeter graphs associated to the finite Coxeter groups. If the Coxeter graph Γ is connected, there is only one possible decomposition of Sin the above sense. Now define ∆1=Y s∈S1 sand ∆2=Y s∈S2 s. Then one has ∆ = ∆1∆2∆1∆2··· |{z } hterms , where his the Coxeter number of the corresponding Coxeter group. The Coxeter numbers corresponding to the spherical type Artin-Tits groups are the following. Type AlBlDlE6E7E8F4G2H3H4I2(p) h l + 1 2l2l−2 12 18 30 12 6 10 30 p As an example, the Garside element of the the spherical Artin-Tits group of type Blis ∆ = ((s1s3···sl)(s2s4···sl−1))lwhen lis odd, and ∆ = ((s1s3···sl−1)(s2s4· · · sl))lwhen lis even. Notice that the Artin-Tits monoid of type Alis precisely the Artin braid monoid on l+ 1 strands. Notice 5
also that the Garside structure given by this construction coincides with the original Artin structure for braid groups described above. We remark that every spherical type Artin-Tits group admits another Garside structure, discovered in [6], called the dual Garside structure. In the case of braid groups, the dual Garside structure is precisely the one discovered in [7]. Example 5: Torus knot groups. The fundamental group of the complement of a (p, q)-torus knot, where p, q > 1 are coprime, is given by the following presentation: hx, y |xp=yqi. If we consider the monoid given by this presentation, it is a Garside monoid with Garside element ∆ = xp. Example 6: The following two examples of Garside groups do not belong to a class of known groups, but they have interesting properties which are not satisfied by the groups in the previous examples. They were discovered and studied by Picantin in [35]. In both cases, we give presentations of the groups which, considered as monoid presentations, yield the corresponding Garside monoids. Hence we shall only define the Garside element, in each case. 1. G=x, y, z |xzxy =yzx2, yzx2z=zxyzx =xzxyz. The Garside element is ∆ = xzxyzx. In most examples of Garside groups, the Garside element ∆ is the least common multiple (with respect to ) of the atoms. In this example, since the relations are homogeneous, the atoms are just the letters x,yand z, and one has lcm(x, y, z) = xzxyz. But xzxyz 6= ∆. Indeed, since conjugation by ∆ must preserve the set of atoms, all atoms must be left and right divisors of ∆, but we have xzxyz 6 y, hence lcm(x, y, z) = xzxyz 6= lcm(x, y, z). This is an example of a Garside monoid in which the lcmof the atoms is not a Garside element. 2. G=x, y |xyxyx =y2. Garside element ∆ = y3. In this case, lcm(x, y) = lcm(x, y) = y2, but y2is not a Garside element. Indeed, since conjugation by ∆ must preserve the set of simple elements, the set of positive left-divisors and the set of positive right-divisors of ∆ must coincide. But this does not happen for y2. For instance xyxy y2but y26 xyxy. This is also an example of a Garside monoid in which the relations are not homogeneous, hence the length of a positive element is not given by the letter length of any representative. Construction of new Garside monoids. We already provided several examples of Garside monoids and groups. Using these monoids as building blocks, one can construct new Garside monoids and groups thanks to the following result. In [35] there is a definition of the so called crossed product of monoids, which also allows to construct new Garside monoids. Theorem 1.1. [35] The crossed product of Garside monoids is a Garside monoid. An example of crossed product, given in [28], is the semidirect product Z⋉Gn, where the action of Zon the free product Gn(Gis a Garside group) is given by cyclic permutations of coordinates. 1.2 Solving the word and conjugacy problems in Garside groups From now on, we will fix a Garside group Gwith a finite type Garside structure (G, P, ∆). We will show how to solve the word problem, giving a well known normal form for elements in a Garside group. The basic reference is [18]. While everything in that paper relates to the braid groups, most of it generalizes easily to arbitrary Garside groups, which were singled out as a class several years later [15, 14]. Definition 1.2. (Left normal form): Given X∈G, we will say that a decomposition X= ∆px1···xr (r≥0) is the left normal form of Xis it satisfies 1. p∈Zis maximal such that ∆pX. That is, x1···xr∈Pand ∆ 6 x1···xr 6
2. xi= (xi···xr)∧∆, for i= 1,...,r. That is, xiis the biggest simple prefix of xi···xr. One can also show by induction that ∆px1···xi=X∧∆p+i, for i= 1,...,r. It is known that one can check whether a given decomposition X= ∆px1···xris a left normal form by looking at each pair of consecutive factors xixi+1. We say that a pair of simple elements a, b ∈[1,∆] is left weighted, if the product ab is in left normal form as written, that is, if a= (ab)∧∆. Then ∆px1···xr is a left normal form if and only if x16= ∆ and each pair xixi+1 is left weighted. Notice that, if we consider the set of simple elements as a set of generators for G, then the decomposition defined above is a normal form in the usual sense, that is, a unique way to write any element of Gas a product of the generators and their inverses. If one wishes to obtain a normal form with respect to any other set of generators (for example the set of atoms), one just needs to choose a unique way to write each simple element in terms of the desired generators, and replace this in the left normal form. We now give several standard terms that will be needed to work with Garside groups. If X= ∆px1···xris in left normal form, the infimum, supremum and canonical length of X, are defined by inf(X) = p, sup(X) = p+rand ℓ(X) = r, respectively. The shift map τis the inner automorphism τ:G→Ggiven by τ(x) = ∆−1x∆. Given a simple element x, we define x∗=x−1∆. That is, x∗is the only simple element such that xx∗= ∆, and is called the right complement of x. The element x∗is the maximal element s(with respect to ) such that xs is simple. A product ab of simple elements aand bis left weighted if and only if a∗∧b= 1. It will be convenient to define the right complement map ∂: [1,∆] →[1,∆] by ∂(x) = x∗: Lemma 1.3. The map ∂: [1,∆] →[1,∆] is a bijection, and ∂2=τ. Proof. We show that ∂is a bijection by defining its inverse ∂−1: [1,∆] →[1,∆] as ∂−1(y) = ∆y−1. The element ∆y−1, sometimes denoted ∗y, is called the left complement of y. It is the only simple element such that ∗y y = ∆. On the other hand, ∂2(x) = ∂(x−1∆) = (∆−1x)∆ = τ(x), as we wanted to show. Corollary 1.4. There exists a positive integer esuch that ∆ebelongs to the center of G. More precisely, one has τ([1,∆]) = [1,∆] and τ(A) = A, where Ais the set of atoms in G, and τe=idGfor some positive integer e, so that ∆eis central. Proof. Since ∂([1,∆]) = [1,∆], it follows that τ([1,∆]) = ∂2([1,∆]) = [1,∆]. This also implies that τ(A) = A. Indeed, suppose that there is some atom asuch that τ(a) is not an atom. Then τ(a) is a simple element that can be decomposed into a product of two simple elements τ(a) = st. But then τ−1(s) and τ−1(t) are simple elements such that a=τ−1(τ(a)) = τ−1(s)τ−1(t). A contradiction, since ais an atom. Hence τ(A)⊂A. Since Ais a finite set, and τ:G→Gis a bijection, it follows that τ(A) = A. Finally, since τinduces a permutation in A, there exists a positive integer esuch that τeinduces the trivial permutation on A. Since the atoms generate G, it follows that τeis the trivial automorphism of G. That is to say, ∆eis central. Remark: In the braid group Bnone has e= 2, so ∆2is central. Furthermore, the center of Bnis the cyclic group generated by ∆2. The right complement plays an important role when comparing the left normal forms of Xand X−1. Theorem 1.5. [18] If X= ∆px1···xr, in left normal form, then the left normal form of X−1is equal to X−1= ∆−p−rx′ r···x′ 1, where x′ i=τ−p−i(∂(xi)) for i= 1,...,r. 7
Remark: Notice that x′ i=τ−p−i(∂(xi)) = ∂−2p−2i+1(xi), so the left normal form of X−1is equal to X−1= ∆−p−r∂−2p−2r+1(xr)∂−2p−2r+3(xr−1)···∂−2p−1(x1). Corollary 1.6. For every X∈G, one has inf(X−1) = −sup(X),sup(X−1) = −inf(X)and ℓ(X−1) = ℓ(X). See Section 9.5 of [19] for a proof that an n-braid of length mcan be put in left normal form in running time O(m2nlog n), with the usual Garside structure of Bn, and see [7] to find how one can compute the normal form in time O(m2n), using the dual Garside structure of Bn, usually known as Birman-Ko-Lee structure. In general, using the normal form algorithm, the complexity of computing the left normal form of a given element in a Garside group Gis O(m2p), where pis the complexity of computing the gcd of two simple elments in G. The number pusually depends on the length of ∆ (simple elements are smaller than ∆) and on the number of atoms in G, since one usually computes the gcd of two elements by iteratively testing if there is some atom which is a common prefix. We now explain the algorithms for solving the conjugacy decision and search problems (CDP/CSP) in Garside groups that were given in [21, 18, 20, 22]: given two elements X, Y ∈G, determine if Xand Y are conjugate and, if this is the case, compute a conjugating element Zsuch that XZ=Z−1XZ =Y. Each algorithm in [21, 18, 20, 22] is an improvement of the previous one, but the basic idea is the same in all of them: Given an element X∈G, the algorithm computes a finite subset IXof the conjugacy class of Xwhich has the following properties: (1) For every X∈G, the set IXis finite, non-empty and only depends on the conjugacy class of X. In particular, two elements X, Y ∈Gare conjugate if and only if IX=IYor, equivalently, IX∩IY6=∅. (2) Given X∈G, a representative e X∈IXand an element a∈Gsuch that Xa=e Xcan be computed effectively. (3) Given a non-empty subset I⊂IX, there is a finite process which either proves that I=IXor produces an element Z∈Iand an element b∈Gsuch that Zb∈IX\I. In particular, IXcan be constructed from any representative as the closure under this process. Given X, Y ∈G, solving the CDP/CSP then involves the following steps. (a) Find representatives e X∈IXand e Y∈IY. (b) Repeatedly use the process from (3), keeping track of the conjugating elements, to compute further elements of IXuntil either (i) e Yis found as an element of IX, proving Xand Yto be conjugate and providing a conjugating element, or (ii) the entire set IXhas been constructed without encountering e Y, proving that Xand Yare not conjugate. We now discuss, briefly, each particular algorithm in [21, 18, 20, 22]. In Garside’s original algorithm [21], the set IXis the Summit Set of X, denoted SS(X), which is the set of conjugates of Xhaving maximal infimum. This was improved by Elrifai and Morton [18] who considered IX=SSS(X), the super summit set of X, consisting of the conjugates of Xhaving minimal canonical length. They also show that SSS(X) is the set of conjugates of Xhaving maximal infimum and minimal supremum, at the same time. For instance, in the braid group Bnwith the usual Garside structure, one has SS(σ1) = SSS(σ1) = {σ1,...,σn−1}. A small example in which SSS(X) is strictly smaller than SS(X) is given by X= ∆σ1σ1∈B3, for which SSS(X) = {∆·σ1σ3}and SS(X) = {∆·σ1σ3,∆·σ1·σ1,∆·σ3·σ3}(the factors in each left normal form are separated by a dot). In general SSS(X) is much smaller than SS(X). Starting by a given element X, one can find an element e X∈SSS(X) by a sequence of special conjugations, called cyclings and decyclings. The conjugating elements involved in a cycling or a decycling will play a crucial role later, so we start by defining them. 8
Definition 1.7. Given X∈Gwhose left normal form is X= ∆px1···xr(r > 0), we define the initial factor of Xas ι(X) = τ−p(x1), and the final factor of Xas ϕ(X) = xr. If r= 0 we define ι(∆p) = 1 and ϕ(∆p) = ∆. Remark: Up to conjugation by ∆p, the simple element ι(X) (resp. ϕ(X)) corresponds to the first (resp. last) non-∆ factor in the left normal form of X. An equivalent definition of ι(X) and ϕ(X), which does not involve the left normal form of X(although it involves its infimum and supremum), is the following. •ι(X) = X∆−p∧∆. •ϕ(X) = (∆p+r−1∧X)−1X. This explains why ι(∆p) and ϕ(∆p) are defined in the above way. The initial and final factors of Xand X−1are closely related. Lemma 1.8. For every X∈Gone has ι(X−1) = ∂(ϕ(X)) and ϕ(X−1) = ∂−1(ι(X)). Proof. Let ∆px1···xrbe the left normal form of X, and suppose that r > 0. We know that ∆−p−rx′ r···x′ 1is the left normal form of X−1, where x′ i=τ−p−i(∂(xi)). Hence one has ι(X−1) = τp+r(x′ r) = τp+r(τ−p−r(∂(xr))) = ∂(xr) = ∂(ϕ(X)). Permuting Xand X−1in this formula yields ι(X) = ∂(ϕ(X−1)), hence ϕ(X−1) = ∂−1(ι(X)). If r= 0, that is if X= ∆p, then ι(X−1) = 1 = ∂(∆) = ∂(ϕ(X)), and ϕ(X−1) = ∆ = ∂−1(1) = ∂−1(ι(X)), so the result is also true in this case. Remark: The above result can be restated as follows: For every X∈G, one has ϕ(X)ι(X−1) = ∆ = ϕ(X−1)ι(X). We can now define the very special conjugations called cyclings and decyclings. Definition 1.9. Given X∈G, we call c(X) = Xι(X)the cycling of Xand we call d(X) = Xϕ(X)−1the decycling of X. In other words, if ∆px1···xris the left normal form of Xand r > 0, then c(X) = ∆px2···xrτ−p(x1),and d(X) = xr∆px2· · · xr−1. In the case ℓ(X) = 0, we have c(X) = d(X) = X. Roughly speaking, for an element of positive canonical length, the cycling of Xis computed by passing the first simple factor of Xto the end, while the decycling of Xis computed by passing the last simple factor of Xto the front. However, the powers of ∆ are not taken into account, which is why one must use the automorphism τ. Notice that the above decompositions of c(X) and d(X) are not, in general, left normal forms. Hence, if one wants to perform iterated cyclings or decyclings, one needs to compute the left normal form of the resulting element at each iteration. As we said above, cyclings and decyclings can be used to find an element in SSS(X), given X. The following result was shown for braid groups, but the same proof is valid for every Garside group. Choose any X∈G. Let r=ℓ(X) and let mbe the letter length of ∆ in the atoms of the given Garside structure. Theorem 1.10. [18], [8] Let (G, P, ∆) be a Garside structure of finite type. Choose X∈G, and let r=ℓ(X). Let mbe the letter length of ∆. 1. A sequence of at most rm cyclings and decyclings applied to Xproduces a representative e X∈ SSS(X). 2. If Y∈SSS(X)and α∈Pis such that Yα∈SSS(X)then Yα∧∆∈SSS(X). 9
c3(X) = 121343 ·12324 = C4·R4 c4(X) = X What about powers of X? Calculating left normal forms, we find that: X= 12132143 ·143 X2= ∆ ·2324321 ·14 ·143 X3= ∆2·12324 ·214 ·14 ·143 X4= ∆2·12132143 ·143 ·12324 ·214 ·14 ·143 X5= ∆3·2324321 ·14 ·143 ·12324 ·214 ·14 ·143 Since inf(X) = 0, the powers X2, X3, X4, X5have 1,2,2,3 unexpected ∆′s. A hint at how the normal forms of Xand Xmmight be related comes from a more careful inspection of this example (and many many other examples like it). The initial factors of the elements in the orbit of Xare C1= 12132143, C2= 121324321, C3= 12132432, C4= 121343. These are the ‘conjugating factors’ that are used when we cycle, that is, if Cm=C1C2···Cm,then cm(X) = XCm.Here are the left normal forms for C1,C2, . . . , C5: C1= 12132143 = first simple factor in X C2= 12132143121324321 = ∆ ·2324321 = product of first 2 simple factors in X2 C3= 1213214312132432112132432 = ∆2·12324 = product of first 3 simple factors in X3 C4= ∆2·12132143 ·143 = product of first 4 simple factors in X4 C5= ∆3·2324321 ·14 = product of first 5 simple factors in X5 One of the main results in this paper states that, for every X∈USS(X), the product of the first m factors in the left normal form of Xm∆−mp, where we include powers of ∆ in the count, is precisely Cm, the product of the conjugating elements involved in the first mcyclings of X. This will allow us to determine which elements admit a rigid power and, under some hypothesis, we find an upper bound for the smallest power which is rigid. In the particular case of braid groups, these results apply to pseudo- Anosov braids, since we will show in §3.4 that every pseudo-Anosov braid in its ultra summit set has a rigid power. 2.1 Decomposition of powers of X. In this section we will decompose Xmas a product of two elements, each of which is determined by the iterated cyclings of X∈G. Assume from now on that X∈SSS(X) and ℓ(X)≥1. We will develop some basic properties of this decomposition for elements of a Garside group. We first need some notation. If the left normal form of Xis ∆px1···xr, recall that ι(X) = τ−p(x1) is the initial factor of X, and that the cycling of Xis defined by c(X) = Xι(X). If we apply iterated cyclings to X, the conjugating elements will be denoted by C1, C2,... That is, Ci=ι(ci−1(X)) for i≥1. Hence one has cm(X) = XC1···Cm. The letter Cin the symbol Cicomes from conjugating element, since one conjugates ci−1(X) by Cito obtain ci(X). The element Xcan be decomposed as follows: X= ∆px1···xr=C1∆px2···xr. We denote R1= x2···xr, so X=C1∆pR1. For the iterated cyclings of X, we denote Riin a similar way, that is, the element satisfying ci−1(X) = Ci∆pRi. The letter Rcomes from remainder. Notice that every Ciis a simple element, while Riis simple only if ℓ(X)≤2, and it is trivial if ℓ(X) = 1. The important fact about these elements relies on how they behave when they are multiplied in the right way. Definition 2.1. Let X∈SSS(X) with inf(X) = pand ℓ(X)≥1. For i≥1, let Ciand Ribe the elements defined above. Then, for every m≥1, we define: •Cm=C1···Cm •Rm=τ−p(Rm)τ−2p(Rm−1)···τ−mp(R1). 16
Notice that Rm∆pm = (∆pRm)(∆pRm−1)···(∆pR1). Since later we will deal not only with X, but with successive cyclings of X, we want to define the corresponding elements above, for ck(X). Hence we define C[k,m]and R[k,m]to be the elements Cm and Rmabove, but defined with respect to ck(X). This yields the analogous definition with the indices shifted by k: Definition 2.2. Let X∈SSS(X) with inf(X) = pand ℓ(X)≥1. For i≥1, let Ciand Ribe the elements defined above. Then, for every m≥1 and k≥0, we define: •C[k,m]=Ck+1 ···Ck+m •R[k,m]=τ−p(Rk+m)τ−2p(Rk+m−1)···τ−mp(Rk+1). Notice that R[k,m]∆pm = (∆pRk+m)(∆pRk+m−1)···(∆pRk+1). Clearly, Cm=C[0,m]and Rm=R[0,m]. In the particular case in which X∈USS(X), that is, X∈SSS(X) and ct(X) = Xfor some positive integer t, we can extend the above definition to negative values of k, as follows. We know that cm(X)∈ USS(X) for every m≥0. If we denote by O(X) the orbit of Xunder cycling, we can define c−m(X) to be the element Y∈ O(X) such that cm(Y) = X(although cycling is not injective in the whole G, it is a bijection in USS(X), so we hope this notation will not cause confusion). Recall that we defined Ci=ι(ci−1(X)), and Riin such a way that ci−1(X) = Ci∆pRi, for every i≥1. The same definitions can now be given for every i∈Z, as we have definitions for the negative cyclings of X. Since O(X) is a finite set, the sequences {Ci}i∈Zand {Ri}i∈Zare periodic. Therefore, we have definitions for the elements Ci,Ri, and also C[k,m]and R[k,m]for every i, k ∈Zand every m≥1. Let us show a result that will be useful later. Lemma 2.3. Let X∈SSS(X)with inf(X) = pand ℓ(X)≥1. For every m, k ≥1one has R[k−1,m]∆pm Ck=Ck+mR[k,m]∆pm. In other words, (∆pRk+m−1)···(∆pRk)Ck=Ck+m(∆pRk+m)···(∆pRk+1). Moreover, if X∈USS(X), the same equality holds for every k∈Z. Proof. We first show the result for X∈SSS(X) and k≥1. If m= 1, the result is true since (∆pRk)Ck= ck(X) = Ck+1(∆pRk+1) by definition. Suppose the result true for m−1. Then one has (∆pRk+m−1)(∆pRk+m−2)···(∆pRk)Ck= (∆pRk+m−1)Ck+m−1(∆pRk+m−1)···(∆pRk+1) =ck+m−1(X)(∆pRk+m−1)···(∆pRk+1) = Ck+m(∆pRk+m)(∆pRk+m−1)···(∆pRk+1), so the result is also true for mand we are done. If X∈USS(X) and k < 0, the same proof is valid. We will now see how the element Xmcan be decomposed in terms of Cmand Rm, together with some properties concerning the normal form of these two factors. Lemma 2.4. Let X∈SSS(X), with ℓ(X)≥1. Let Ci,Ri,Cmand Rmbe the elements defined above. Then: 1. The m-th power of Xhas the decomposition Xm=CmRm∆mp. 2. In this decomposition, inf(Rm) = 0 and ι(Rm)Cm+1, for every m≥1. 3. In general inf(Cm)≥0. If ℓ(X)>1, one has sup(Cm) = m,ℓ(Cm)>0and ϕ(Cm)ϕ(cm(X)), for every m≥1. 17
Remark: The left normal form of Cmis not so easy to understand, as we saw in the example that was given at the beginning of Section 2. Uncovering it, and relating it to the left normal form of Xm, will be a major part of our investigations. Proof: 1. For m= 1 the result is clear, since X=C1∆pR1=C1R1∆pby definition. Now suppose that Xm−1=Cm−1Rm−1∆(m−1)p. Then one has Xm=Xm−1X=Cm−1Rm−1∆(m−1)pC1(∆pR1). By Lemma 2.3 with k= 1, it then follows that Xm=Cm−1CmR[1,m−1]∆(m−1)p(∆pR1) = CmR[1,m−1]∆mpR1 =CmR[1,m−1]τ−mp(R1)∆mp =CmRm∆mp, so the result is true for every m≥1. 2. To prove that inf(Rm) = 0 and that ι(Rm)Cm+1, for every m≥1, we notice that Rmis positive by definition. Hence both statements will follow if we can show that ∆ ∧RmCm+1. If m= 1 one has R1=τ−p(x2···xr), hence ∆ ∧R1=τ−p(x2). We also have C2=ι(c(X)) = ι(∆px2···xrτ−p(x1)). Since X∈SSS(X), we have inf(x2···xrτ−p(x1)) = 0, so the first factor in its left normal form is equal to x2sfor some simple element s. Hence C2=ι(∆px2···xrτ−p(x1)) = τ−p(x2s). Therefore ∆ ∧R1=τ−p(x2)τ−p(x2s) = C2, and the result is true for m= 1. Suppose that ∆ ∧Rm−1Cmfor some m. By definition, Rm=τ−p(RmRm−1), hence ∆∧Rm= ∆ ∧τ−p(RmRm−1) = τ−p(∆ ∧(RmRm−1)). Notice that, since inf(Rm−1) = 0 by the induction hypothesis, the initial factor of RmRm−1depends only on Rmand on the initial factor of Rm−1, that is, ∆∧(RmRm−1) = ∆ ∧(Rm(∆ ∧Rm−1)) ∆∧(RmCm). But ∆pRmCm=cm(X), and ι(cm(X)) = Cm+1, hence ∆ ∧(RmCm) = τp(Cm+1). Therefore ∆∧(RmRm−1)τp(Cm+1), and then ∆∧Rm=τ−p(∆ ∧(RmRm−1)) τ−p(τp(Cm+1)) = Cm+1, as we wanted to show. 3. We prove (3) by induction on m. If m= 1 then C1=C1. As ℓ(X)>0, C1is a non-trivial simple element, whence sup(C1) = ℓ(C1) = 1. As X∈SSS(X), the number of canonical factors cannot decrease when passing from Xto c(X). In particular, the factor C1moved to the end cannot be absorbed completely which shows ϕ(C1) = C1ϕ(c(X)). Suppose the result true for some m≥1 and let F=ϕ(Cm) = ϕ(C1···Cm). As above we see that ϕ(cm(X)) Cm+1 cannot be simple, as X(and hence cm(X)) is super summit. Notice that we used ℓ(X)>1 here. Since Fϕ(cm(X)) by induction, this implies that F Cm+1 also has supremum 2. It is well known [32] that if one multiplies a left normal form y1···ymby a simple element Cm+1, then the left normal form of the product is computed by by applying mlocal transformations to pairs of consecutive factors, starting by the rightmost pair. In this way one can compute the normal form of every element, so we will refer to this as the normal form algorithm. Since sup(Cm) = mby induction hypothesis, and FCm+1 is not simple, the normal form algorithm implies that sup(Cm+1) = sup(C1···Cm+1) = m+ 1. This algorithm together with Fϕ(cm(X)) and ℓ(X)>1 also implies that ϕ(Cm+1) = ϕ(C1· · · CmCm+1) = ϕ(FCm+1)ϕ(ϕ(cm(X)) Cm+1) = ϕ(cm+1(X)). 18
Finally, since Cm+1 6= ∆ and FCm+1 has supremum 2, it follows that ϕ(Cm+1) = ϕ(FCm+1)6= ∆, so ℓ(Cm+1)>0. Since the super summit set of an element is closed under cycling, Lemma 2.4 is still true if we apply it to every iterated cycling of X. If furthermore X∈USS(X), the same will be true for every element in O(X). This yields the following result. Lemma 2.5. Let X∈SSS(X), with ℓ(X)≥1. With the above notation, one has, for every k≥0and every m≥1: 1. The m-th power of ck(X)has the decomposition (ck(X))m=C[k,m]R[k,m]∆mp. 2. In this decomposition, inf(R[k,m]) = 0 and ι(R[k,m])Ck+m+1, for every m≥1. 3. In general inf(C[k,m])≥0. If ℓ(X)>1, one has sup(C[k,m]) = m,ℓ(C[k,m])>0and ϕ(C[k,m]) ϕ(ck+m(X)), for every m≥1. Moreover, if X∈USS(X), the result holds for every k∈Z. Notice that in C[k,m]and R[k,m], the first index determines an element in the cycling orbit of X, and the second index determines its power. One can also think of mas being the number of factors in the decompositions of C[k,m]and R[k,m]given by the definitions. But this is not necessarily the number of factors in their normal forms. 2.2 Interplay between Cmand Rm. Having proved that Xm=CmRm∆pm, we will show that if Xbelongs to its ultra summit set, this decomposition is left weighted, that is, ϕ(Cm)ι(Rm) is in left normal form as written. In other words, since we know by Lemma 2.4 that sup(Cm) = m, we will show that the product of the first mfactors, including ∆’s, in the left normal form of Xm∆−pm is precisely Cm. If X∈USS(X), recall that by Lemma 2.3, one has R[k−1,m]∆pm Ck=Ck+mR[k,m]∆pm, for every k∈Z. We will actually see that the initial factor of this element is precisely Ck+m, no matter how many remainders we multiply on the right, that is, no matter how big is m. Lemma 2.6. Let X∈SSS(X)with inf(X) = pand ℓ(X)≥1. For every m≥1and k≥0, one has (Ck+mR[k,m])∧∆ = Ck+m. If furthermore X∈USS(X), this is also true for every k∈Z. Proof. If m= 1, we need to show that (Ck+1R[k,1])∧∆ = Ck+1, but we have ck(X) = Ck+1∆pRk+1 = Ck+1R[k,1]∆p, where this decomposition is left weighted by definition. So the result is true for m= 1. Suppose the result true for m−1. This means that (Ck+m−1R[k,m−1])∧∆ = Ck+m−1. If we multiply on the left by Rk+m−1we get (Rk+m−1Ck+m−1R[k,m−1])∧(Rk+m−1∆) = Rk+m−1Ck+m−1. Notice that ∆Rk+m−1∆, hence if we consider the maximal simple prefix of each element in the above equality, we obtain (Rk+m−1Ck+m−1R[k,m−1])∧∆ = (Rk+m−1Ck+m−1)∧∆. On the other hand, recall that (∆pRk+m−1)Ck+m−1=ck+m−1(X) = Ck+m(∆pRk+m), hence Rk+m−1Ck+m−1=τp(Ck+m)Rk+m, where τp(Ck+m) is the maximal simple prefix of this element. Therefore, one has (Rk+m−1Ck+m−1R[k,m−1])∧∆ = (Rk+m−1Ck+m−1)∧∆ = τp(Ck+m). 19
Now notice that ∆pRk+m−1Ck+m−1R[k,m−1] =Ck+m∆pRk+mR[k,m−1] =Ck+mR[k,m]∆p. This means that Rk+m−1Ck+m−1R[k,m−1] =τp(Ck+mR[k,m]), and we just showed that its maximal simple prefix is precisely τp(Ck+m). Applying τ−pto this element, one obtains (Ck+mR[k,m])∧∆ = Ck+m, as we wanted to show. The proof for X∈USS(X) and k < 0 is the same. It will possibly help to understand the situation if we extract a particular case from the above result, assuming that X∈USS(X): Lemma 2.7. Let X∈USS(X)with inf(X) = pand ℓ(X)≥1. For every m≥1, one has (C1R[1−m,m])∧∆ = C1. In other words, the biggest simple prefix of C1τ−p(R1)τ−2p(R0)τ−3p(R−1)···τ−mp(R2−m) is C1, no matter how big is m. We can now show that the decomposition CmRmis left weighted. This will actually be a particular case of the following stronger result. Proposition 2.8. Let X∈USS(X)with ℓ(X)≥1. With the above notation, for every k, l, m, n ∈ Z, such that m, n ≥1and k+m=l+n, the decomposition C[k,m]R[l,n]is left weighted. That is, ϕ(C[k,m])ι(R[l,n])∧∆ = ϕ(C[k,m]). Proof. We proceed by induction on m. If m= 1, one has C[k,1]R[l,n]=Ck+1R[l,n]. Since k+ 1 = l+n by hypothesis, it follows from Lemma 2.6 that the biggest simple prefix of this element is precisely Ck+1. Hence C[k,1]R[l,n]is left weighted, and the result is true for m= 1. Now consider k, l, m, n as above, with m > 1, and suppose the result true for m−1. This implies that C[k,m−1]R[l−1,n]is left weighted, since k, l −1, m −1, n satisfy the required hypothesis. (Notice that if we had required k, l ≥0, we would not have been able to apply the induction hypothesis here, since we could have had l−1<0; This is why we require X∈USS(X) and not only in SSS(X).) Let C[k,m−1] = ∆qy1···ysand R[l−1,n]=z1···ztin left normal form. Then C[k,m−1]R[l−1,n]= ∆qy1···ysz1···ztis in left normal form as written, by induction hypothesis. Now multiply this element on the right by τ−pn(Cl). By the normal form algorithm, since ∆qy1···ysz1···ztis already in left normal form and τ−pn(Cl) is a simple element, then the left normal form of ∆qy1···ysz1···ztτ−pn(Cl) is computed by by applying s+tlocal transformations to pairs of consecutive factors, starting by the rightmost pair. When we apply the first ttransformations, we obtain the left normal form of z1···ztτ−pn(Cl) = R[l−1,n]τ−pn(Cl). By Lemma 2.3, this element is equal to Cl+nR[l,n]=Ck+mR[l,n]. Moreover, by Lemma 2.6, Ck+mis the biggest simple prefix of this element. Hence the left normal form of z1···ztτ−pn(Cl) has the form Ck+mz′ 1···z′ t, where z′ 1···z′ t=R[l,n]. We then have C[k,m−1]R[l−1,n]τ−pn(Cl) = C[k,m−1]Ck+mR[l,n]= ∆qy1···ysCk+mz′ 1···z′ t, where the last t+ 1 factors in the latter decomposition are in left normal form. If we continue applying the normal form algorithm, we perform slocal transformations to the element y1···ysCk+m, which is equal to C[k,m−1]Ck+m=C[k,m]. Since the resulting factorization of C[k,m]R[l,n] is in left normal form by construction, it follows that ϕ(C[k,m])ι(R[l,n]) is left weighted, as we wanted to show. 20
This result implies one of the strongest relations between cyclings and powers of an element Xin its ultra summit set: Theorem 2.9. Let X∈USS(X)with inf(X) = pand ℓ(X)>1. For every m≥1, the product of the first mfactors (including ∆’s) in the left normal form of Xm∆−mp is equal to Cm. That is, (Xm∆−mp)∧∆m=Cm. In particular, ι(Xm) = ι(Cm). Proof. The first claim is a straightforward consequence of the previous result and Lemma 2.4, since Xm∆−mp =CmRm, where the latter decomposition is left weighted and sup(Cm) = m. The second claim follows from the fact that ι(Y) = ι(Y∆t) for every Y∈Gand every t∈Z. Hence ι(Xm) = ι(Xm∆−mp) = ι(CmRm). Since the latter decomposition is left weighted, and ℓ(Cm)>0, it follows that ι(Xm) = ι(Cm), as we wanted to show. Corollary 2.10. For X∈USS(X)and m≥1, one has inf(Xm) = minf(X) + inf(Cm). In particular, the unexpected ∆′sin Xmare determined entirely by the Cmpart of the normal form of Xm. Proof. Since we know by Lemma 2.4 that ℓ(Cm)>0, it follows from Theorem 2.9 that all ∆’s in the left normal form of Xmcan be seen in ∆pmτpm(Cm), where p= inf(X). Hence inf(Xm) = pm + inf(Cm), and the result follows. We end this section with an immediate corollary concerning how the infimum and supremum of an element, in its ultra summit set, behave when one raises the element to some power. This is related to the translation number of the element (see [31]). Notice that the following result is closely related to Proposition 3.6 in [29]. Corollary 2.11. Let X∈USS(X). For every m≥1, one has inf(Xm) + inf(X)≤inf(Xm+1)≤inf(Xm) + inf(X) + 1. If X−1∈USS(X−1), then sup(Xm) + sup(X)−1≤sup(Xm+1)≤sup(Xm) + sup(X). Proof. Let p= inf(X). By the previous corollary, inf(Xm) = pm + inf(Cm) and inf(Xm+1) = p(m+ 1) + inf(Cm+1). Hence, the first inequality will be true if and only if inf(Cm)≤inf(Cm+1)≤inf(Cm) + 1. But Cm+1 =CmCm+1, where Cm+1 is a simple element. The result then follows from the following well know fact, which is a direct consequence of the normal form algorithm: If an element in a Garside group is multiplied by a simple element, then its infimum either is preserved or is increased by one. The second inequality is equivalent to the first one, since sup(X) = −inf(X−1) by Corollary 1.6. 21
2.3 The absolute initial and final factors In this section we will define some simple factors related to an element X∈USS(X). They are defined in terms of the cycling elements Ci, but they are closely related to powers of X, as we will see. We called them the absolute initial and final factors of X. In general, the absolute initial and final factors are related to, but do not coincide with, the initial and final factors of X. Nevertheless we will see that, if Xhas a rigid power Xm, the absolute initial and final factors of Xcoincide with the initial and final factors of Xm. Suppose that X∈USS(X). We saw in Lemma 2.5 that ϕ(C[k,m]) = ϕ(Ck+1 ···Ck+m)ϕ(ck+m(X)), where this is true for every m≥1 and every k∈Z. This implies a very interesting fact: if we fix the number k+mand take different values of k, that is, if we start with Ck+mand multiply it on the left by Ck+m−1, then by Ck+m−2, etc., then the final factor of each of the resulting elements is a left multiple of ϕ(ck+m(X)). For instance, if we take k+m= 0, we have ϕ(C−m+1C−m+2 ···C−1C0)ϕ(X), for every m≥1. In the same way, by Lemma 2.5 we know that ι(R[k,m]) = ι(τ−p(Rk+m)τ−2p(Rk+m−1)···τ−mp(Rk+1)) Ck+m+1 for every m≥1 and every k∈Z, where p= inf(X). Hence, if we fix k+m, say k+m= 0, we have (recall that C1=ι(X)) ι(τ−p(R0)τ−2p(R−1)···τ−mp(R−m+1)) ι(X), for every m≥1. In the particular case in which inf(X) = p= 0, this formula is even more similar to the above one, since one has: ι(R0R−1···R−m+1)ι(X), for every m≥1. But it is even more interesting to relate the values of ϕ(C−m+1C−m+2 ···C−1C0) and of ι(τ−p(R0)τ−2p(R−1)···τ−mp(R−m+1)), respectively, for different values of m. It turns out that they form ordered chains with respect to and , respectively, as shown in the following result. Proposition 2.12. Let X∈USS(X)with ℓ(X)>1. For every k, m ∈Zwith m > 0, one has ϕ(C[k,m])ϕ(C[k−1,m+1])and ι(R[k,m])ι(R[k−1,m+1]). In other words, for every k∈Zthere are chains: ϕ(C[k,1])ϕ(C[k−1,2])ϕ(C[k−2,3]) · · · and ι(R[k,1])ι(R[k−1,2])ι(R[k−2,3]) · · · Proof. We know that sup(C[k,m]) = mand sup(C[k−1,m+1]) = m+ 1. Moreover, C[k−1,m+1] = CkCk+1 ···Ck+m=CkC[k,m]. Hence, if we write C[k,m]= ∆qc1···csin left normal form (where q+s=m and s > 0), then ϕ(C[k,m]) = csϕ(Ck∆qc1···cs) = ϕ(C[k−1,m+1]). On the other hand, let p= inf(X). One has R[k−1,m+1] =τ−p(Rk+m)τ−2p(Rk+m−1)···τ−mp(Rk+1)τ−(m+1)p(Rk) = R[k,m]·τ−(m+1)p(Rk), that is, R[k,m]R[k−1,m+1]. Since we know that inf(R[k,m]) = inf(R[k−1,m+1]) = 0, it follows that ι(R[k,m])ι(R[k−1,m+1]). 22
Since the chains given by the above proposition consist of proper simple elements, we know that the chains must stabilize. But we will furthermore show that they stabilize fast. More precisely, they stabilize exactly at the first repetition. Moreover, the corresponding chains for all elements in O(X) stabilize at the same time. This is proved by the next 4 lemmas and the proposition that follows them. Lemma 2.13. Let X∈USS(X)with ℓ(X)>1and m > 0. If ϕ(C[k,m]) = ϕ(C[k−1,m+1])for some k∈Z, then ϕ(C[i,m]) = ϕ(C[i−1,m+1])for every i∈Z. Proof. Since Xbelongs to a closed orbit under cycling, the sequences {C[i,m]}i∈Zand {C[i,m+1]}i∈Zare periodic, hence it suffices to show the case i=k+ 1. The property ϕ(C[k,m]) = ϕ(C[k−1,m+1]), that is, ϕ(Ck+1 ···Ck+m) = ϕ(Ck···Ck+m), can be reinterpreted as follows. Since sup(Ck+1 ···Ck+m) = mand sup(Ck···Ck+m) = m+ 1, their final factors coincide if and only if the first m−1 factors of the first element, multiplied on the left by Ck, coincide with the first mfactors of the second element. In other words, (Ck···Ck+m)∧(Ck∆m−1) = (Ck···Ck+m)∧∆m. We can now apply Gebhardt’s transport [22] to the whole equality. We know that the transport of ∆m is ∆m. Notice that the transport of Ck(based at ck−1(X)) is Ck+1. This implies, by recurrence, that the transport of Ck···Ck+mis Ck+1 ···Ck+m+1, and also that the transport of Ck∆m−1is Ck+1∆m−1. Since the transport preserves greatest common divisors, the transport of the above equality yields (Ck+1 ···Ck+m+1)∧(Ck+1∆m−1) = (Ck+1 ···Ck+m+1)∧∆m, that is, ϕ(C[k+1,m]) = ϕ(C[k,m+1]), and the result is shown. Lemma 2.14. Let X∈USS(X)with ℓ(X)>1. If ϕ(C[k,m]) = ϕ(C[k−1,m+1])for some k, m ∈Zwith m > 0, then ϕ(C[i,j]) = ϕ(C[i−1,j+1])for every i∈Zand every j≥m. Proof. We know by Lemma 2.13 that ϕ(C[i,m]) = ϕ(C[i−1,m+1]) for every i∈Z. We just need to be able to increase the second subindex. But if ϕ(Ci+1 ···Ci+m) = ϕ(Ci···Ci+m)6= ∆, and we multiply both elements on the right by Ci+m+1, since we know that no unexpected decrease of supremum will happen (sup(C[i,m+1]) = m+ 1), it follows that ϕ(Ci+1 ···Ci+mCi+m+1) = ϕ(ϕ(Ci+1 ···Ci+m)Ci+m+1) =ϕ(ϕ(Ci···Ci+m)Ci+m+1) = ϕ(Ci···Ci+mCi+m+1). Hence ϕ(C[i,m+1]) = ϕ(C[i−1,m+2]) for every i∈Z. By induction on m, it follows that ϕ(C[i,j]) = ϕ(C[i−1,j+1]) for every j≥m, as we wanted to show. The analogous results can now be shown for the chain involving prefixes of R[k,m]. Lemma 2.15. Let X∈USS(X)with ℓ(X)>1and m≥1. If ι(R[k,m]) = ι(R[k−1,m+1])for some k∈Z, then ι(R[i,m]) = ι(R[i−1,m+1])for every i∈Z. Proof. As above, since Xbelongs to a closed orbit under cycling, it suffices to show the case i=k+1. We want to reinterpret the equality ι(R[k,m]) = ι(R[k−1,m+1]). If we recall that (ck(X))m=C[k,m]R[k,m]∆mp where p= inf(X), and that inf(R[k,m]) = 0, then we see that (ck(X))m∧C[k,m]∆mp+1=C[k,m]ι(R[k,m]) ∆mp =Ck+1 ···Ck+mι(R[k,m]) ∆mp. In the same way, we obtain (ck−1(X))m+1 ∧C[k−1,m+1]∆(m+1)p+1=C[k−1,m+1] ι(R[k−1,m+1]) ∆(m+1)p 23
=Ck···Ck+mι(R[k−1,m+1]) ∆mp+p. Therefore the equality ι(R[k,m]) = ι(R[k−1,m+1]) can be rewritten as follows: Ck(ck(X))m∧(C[k,m]∆mp+1)∆p= (ck−1(X))m+1 ∧C[k−1,m+1]∆(m+1)p+1. If we apply Gebhardt’s transport to the whole equality, it follows that Ck+1 (ck+1(X))m∧(C[k+1,m]∆mp+1)∆p= (ck(X))m+1 ∧C[k,m+1]∆(m+1)p+1, hence ι(R[k+1,m]) = ι(R[k,m+1]), and the result is shown. Lemma 2.16. Let X∈USS(X)with ℓ(X)>1. If ι(R[k,m]) = ι(R[k−1,m+1])for some k, m ∈Zwith m > 0, then ι(R[i,j]) = ι(R[i−1,j+1])for every i∈Zand every j≥m. Proof. We know by Lemma 2.15 that ι(R[i,m]) = ι(R[i−1,m+1]) for every i∈Z. We just need to be able to increase the second subindex. But ι(R[i,m]) = ι(R[i−1,m+1]) is equivalent to ι((∆pRi+m)(∆pRi+m−1)···(∆pRi+1)) = ι((∆pRi+m)(∆pRi+m−1)···(∆pRi)), where p= inf(X). If we multiply both elements on the left by ∆pRi+m+1, since we know that there is no unexpected increase of infimum (inf(R[i,m+1]) = 0), it follows that ι((∆pRi+m+1)(∆pRi+m)···(∆pRi+1)) = ι((∆pRi+m+1)ι((∆pRi+m)···(∆pRi+1))) =ι((∆pRi+m+1)ι((∆pRi+m)···(∆pRi))) = ι((∆pRi+m)(∆pRi+m−1)···(∆pRi)). Hence ι(R[i,m+1]) = ι(R[i−1,m+2]) for every i∈Z. By induction on m, it follows that ι(R[i,j]) = ι(R[i−1,j+1]) for every j≥m, as we wanted to show. Proposition 2.17. Let X∈USS(X)with ℓ(X)>1. Given k∈Z, the chain ϕ(C[k,1])ϕ(C[k−1,2])ϕ(C[k−2,3]) · · · stabilizes whenever ϕ(C[k−j+1,j]) = ϕ(C[k−j,j+1]), and this happens for some j < ||∆||. Moreover, for all i∈Z, the analogous chains starting at ϕ(C[i,1])stabilize at the same value of j. Also, the chain ι(R[k,1])ι(R[k−1,2])ι(R[k−2,3]) · · · stabilizes whenever ι(R[k−j+1,j]) = ι(R[k−j,j+1]), and this happens for some j < ||∆||. Moreover, for all i∈Z, the analogous chains starting at ι(R[i,1])stabilize at the same value of j. Proof. By Lemma 2.14, all chains stabilize whenever ϕ(C[k−j+1,j]) = ϕ(C[k−j,j+1]) for some j. Up to that point, the chains must be made of strict inequalities. But the maximal length of such a chain (formed by nontrivial simple elements) is bounded by the length of ∆. The proof that the second sequence stabilizes is identical. Definition 2.18. Given X∈USS(X) with ℓ(X)>1, we define the absolute final factor F(X) of Xas the factor in which the above descending chain stabilizes, for k=−1, that is: F(X) = ϕ(C[−m,m]), for m≥ ||∆|| − 1. In other words, F(X) = ϕ(C−m+1C−m+2 ···C−1C0),for mbig enough. 24
Definition 2.19. Given X∈USS(X) with ℓ(X)>1, we define the absolute initial factor I(X) of Xas the factor in which the above ascending chain stabilizes, for k=−1, that is: I(X) = ι(R[−m,m]), for m≥ ||∆|| − 1. In other words, I(X) = ι(τ−p(R0)τ−2p(R−1)···τ−mp(R−m+1)),or alternatively I(X) = ι((∆pR0)(∆pR−1)···(∆pR−m+1)),for mbig enough, where p= inf(X). Proposition 2.20. Given X∈USS(X)with ℓ(X)>1, the decomposition F(X)I(X)is left weighted as written. Proof. This is an immediate consequence of Proposition 2.8, since F(X)I(X) = ϕ(C[−m,m])ι(R[−m,m]) for mbig enough. We have seen at the beginning of this section that F(X)ϕ(X) and I(X)ι(X). But we will see now that the absolute factors are also related to the initial and final factors of powers of X. Proposition 2.21. Let X∈USS(X)with inf(X) = pand ℓ(X)>1. For every m≥1such that Xm∈SSS(Xm), one has: •F(X)ϕ(Xm). •I(X)ι(Xm). Proof. The case m= 1 is a straightforward consequence of Lemma 2.5, for k=−m. Suppose that m > 1. We know from Theorem 2.9 that the left normal form of (c−m(X))m= (C−m+1 ···C0)Xm(C−1 0···C−1 −m+1) is equal to ∆pm+qy1···ysz1···zt, where ∆qy1···ys=τpm(C−m+1 ···C0) and q+s=m. If we conjugate this element by C−m+1 ···C0we obtain Xm= ∆pmz1···zt∆qτ−pm(y1···ys). But if Xm∈SSS(Xm), we also have Ym∈SSS(Xm) for every Yin the cycling orbit of X: Indeed, Ym= (XCt)m= (Xm)Ctfor some t, where Ct= (Xm∆−mp)∧∆tby Theorem 2.9. Since Xm∆−mp and ∆tconjugate Xmto elements in their super summit sets (namely τ−mp(Xm) and τt(Xm), respectively), it follows by Theorem 1.12 that Ym= (Xm)Ct∈SSS(Xm). In particular (c−m(X))m∈SSS(Xm), hence ℓ(Xm) = ℓ((c−m(X))m) = s+t. Since the above decomposition of Xmhas precisely s+tnon-∆ factors, and the final one is τ−pm(ys), it follows that τ−pm(ys)ϕ(Xm). That is, ϕ(C−m+1 ···C0)ϕ(Xm). Notice that we can apply the same reasoning to every element in the cycling orbit of X, in particular to c−m(X). It follows that ϕ(C−2m+1 ···C−m)ϕ((c−m(X))m) = zt. Hence, since multiplying Ci’s never decreases the supremum, one has ϕ(C−2m+1 ···C−mC−m+1 ···C0) = ϕ(ϕ(C−2m+1 ···C−m)C−m+1 ···C0) ϕ(zt∆qτ−pm(y1···ys)) = ϕ(Xm). Applying the same reasoning again, one obtains by induction on kthat ϕ(C−km+1 ···C0)ϕ(Xm) for every k≥1. When kis big enough so that km ≥ ||∆|| − 1, this implies F(X)ϕ(Xm), as we wanted to show. 25
Proof. Let ∆px1···xrbe the left normal form of X. By Proposition 3.7, all iterated cyclings of Xare rigid. Then one can easily show by recurrence that if i=kr +jwith 0 ≤j≤r−1, the left normal form of ci(X) is equal to ∆pτkp(xj+1)···τkp(xr)τ(k+1)p(x1)···τ(k+1)p(xj). Hence, if eis such that τe= 1, one has cer(X) = ∆pτep(x1)···τep(xr) = ∆px1···xr=X, so Xbelongs to a closed orbit under cycling, and the orbit length is a divisor of re =ℓ(X)e. By Lemma 3.5 Xis rigid if and only if so is X−1. This means that ci(X−1) is rigid for every i≥1. But we know by [18] that ci(X−1) = (di(X))−1, hence di(X) is also rigid for every i≥1. Furthermore, by the above arguments X−1belongs to a closed orbit under cycling, thus Xbelongs to a closed orbit under decycling. But an element belonging to closed orbits under cycling and decycling belongs to its ultra summit set (since one can always reach the ultra summit set by iterated cycling and decycling), so it follows that X∈USS(X). For elements which belong to their ultra summit set, the converse of Lemma 3.13 is also true. Lemma 3.14. If Y∈USS(X)is not rigid, then neither ci(Y)nor di(Y)are rigid for any i≥1. Proof. It clearly suffices to show the result for i= 1. First, c(Y) has the same rigidity as Yby Proposition 3.7, hence it cannot be rigid. Now suppose that d(Y) is rigid. This is clearly not possible if ℓ(Y) = 1, so we can suppose that ℓ(Y)>1. If ∆py1···yris the left normal form of Y, then d(Y) = ∆pτp(yr)y1···yr−1, although this decomposition is not the left normal form of d(Y). Nevertheless, since y1···yr−1is in left normal form, we know, by the left normal form algorithm (see for instance [19]) that there is a decomposition yi=aibifor i= 1,...,r−1 such that the left normal form of d(Y) is precisely ∆p(τp(yr)a1)(b1a2)···(br−2ar−1)(br−1). Since we are assuming that d(Y) is rigid, we have that (br−1)(yrτ−p(a1)) is left weighted as written. Notice that this implies that yr−1(yrτ−p(a1)) is left weighted as written. Hence the left normal form of y1···yrτ−p(y1) is precisely y1···yr−1(yrτ−p(a1))τ−p(b1). In other words, R(Y) = r−1 r. By Proposition 3.7, all iterated cyclings of Yhave rigidity r−1 r. This implies, in particular, that cr−1(Y) = Yτ−p(y1···yr−1)= ∆pyrτ−p(y1···yr−1) = τ−p(d(Y)), but this latter element is supposed to be rigid. A contradiction. Hence no iterated decycling of Ycan be rigid. We can finally prove the main result concerning the elements of the ultra summit set of a rigid element. Theorem 3.15. Let Xbe rigid and ℓ(X)>1. Then every element in USS(X)is rigid. Proof. Suppose that there exists an element in USS(X) which is not rigid. Since every two elements in USS(X) are connected by a sequence of conjugations by simple elements, there must be a non-rigid element in USS(X) which is the conjugate of a rigid one by a simple element. Hence we can assume without loss of generality that Xs=Yfor some non-rigid element Y∈USS(X) and some simple element s. We will also assume that sis a maximal element (with respect to ) in the set of all simple elements conjugating Xto a non-rigid element in USS(X). We will get a contradiction by showing that Xis conjugate to c(d(Y)) by a simple element which is a proper right multiple of s. Let ∆px1···xrbe the left normal form of Xand let ∆py1···yrbe the left normal form of Y. Since Xs=Y, it is known by [22] that there exist simple elements s0,...,srsuch that s0=τp(s), sr=sand yi=s−1 i−1xisifor i= 1,...,r. That is, the left normal form of Yis ∆py1···yr= ∆p(s−1 0x1s1)(s−1 1x2s2)···(s−1 r−1xrsr). Now consider d(X) and d(Y). By Lemma 3.12, these two elements belong to USS(X). Since Xis rigid, the left normal form of d(X) is ∆pτp(xr)x1···xr−1. However, Yis not rigid, so the left normal form of d(Y) is not ∆pτp(yr)y1···yr−1, since τp(yr)y1is not left weighted as written. (Here we use the fact that r=ℓ(X)>1.) Hence, ι(d(Y)) = yrtfor some nontrivial simple element t. 32
The elements d(X) and d(Y) are also connected through a conjugation by a simple element. Namely, d(X)sr−1= ∆pτp(sr−1)−1τp(xr)x1···xr−1sr−1= ∆pτp(yr)y1···yr−1=d(Y). Hence, by [22] again, there exist simple elements t0,...,trsuch that t0=τp(sr−1), tr=sr−1and the left normal form of d(Y) is ∆p(t−1 0τp(xr)t1)(t−1 1x1t2)· · · (tr−1xr−1tr). Therefore ι(d(Y)) = τ−p(t0)−1xrτ−p(t1) = s−1 r−1xrτ−p(t1). Since we saw that ι(d(Y)) = yrt= (s−1 r−1xrs)t, it follows that st =τ−p(t1), which is a simple element. If we denote u=τ−p(t1), we just showed that s≺u(strict) and that ι(d(Y)) = s−1 r−1xru. Finally, notice that Xu= ((Xx−1 r)sr−1)s−1 r−1xru= (d(X)sr−1)s−1 r−1xru=d(Y)ι(d(Y)) =c(d(Y)). But since Yis not rigid and belongs to USS(X), Lemma 3.14 tells us that d(Y) is not rigid. Since d(Y) also belongs to USS(X) by Lemma 3.12, it follows again by Lemma 3.14 that c(d(Y)) is not rigid, and belongs to USS(X). But su, so this contradicts the maximality of s, and we are done. Corollary 3.16. If Xis rigid and ℓ(X)>1, then USS(X)is the set of rigid conjugates of X. Proof. Let Ybe a rigid conjugate of X. Since Yis rigid, it belongs to its ultra summit set and since it is conjugate to X, its ultra summit set is precisely USS(X). Conversely, every element in USS(X) is rigid by the above result. Corollary 3.17. If Xis rigid and ℓ(X)>1, then USS(X−1)is the set of inverses of the elements in USS(X). Proof. This is a direct consequence of Corollary 3.16 and the fact that Y∈Gis rigid if and only if Y−1 is rigid (Lemma 3.5). Remark: If ℓ(X) = 1, then USS(X) may contain rigid and non-rigid elements. For instance, the simple element 12321435 ∈B6is rigid (since 12321435 ·12321435 is left weighted), but it is conjugate (by 23) to the simple element 12134325, which is not rigid (the left normal form of 12134325 12134325 is 1213432514 ·213245). Clearly both elements belong to the ultra summit set, since they are simple. 3.3 Elements having a rigid power In this section we will characterize elements X∈Ghaving a rigid power Xmfor some integer m6= 0. Notice that such an element cannot be periodic. Otherwise, since rigidity is preserved by powers, some rigid power of X(which, by definition, has positive canonical length) would also be a power of ∆ (which has zero canonical length), and this is not possible. If the element Xbelongs to its ultra summit set, we can say something more. Proposition 3.18. Let X∈USS(X)with ℓ(X)≥1. If Xhas a rigid power, then there exists some M > 0such that CM= ∆kXtfor some integers k, t, where t > 0and ∆kis central. Proof. Let p= inf(X). If ℓ(X) = 1 then XM=CM∆−pM for every M, so we just need to take Mbig enough so that ∆Mis central, and we are done. Hence we can assume that ℓ(X)>1. Let e > 0 be such that ∆eis central, let m > 0 be such that Xmis rigid, and let Nbe the orbit length of Xunder cycling. Consider T=emN. By Lemma 2.4 one has XT=CTRT∆pT , and by Proposition 2.8, ϕ(CT)ι(RT) is left weighted. Since Tis a multiple of e, ∆pT is central. Since Tis a multiple of m, it follows that XTis rigid, hence ϕ(XT)ι(XT) = ϕ(RT)ι(CT) is also left weighted (notice that the equality holds since ∆pT is central). Finally, since Tis a multiple of N, it follows that CTcommutes with X, thus it commutes with XT. Then one has: XT= (XT)CT=RT∆pT CT= ∆pT RTCT. Moreover, since ϕ(RT)ι(CT) is left weighted, ϕ(XT) = ϕ(CT). Hence ϕ(CT)ι(CT) = ϕ(XT)ι(XT) is left weighted by the rigidity of XT, so it follows that CTis also rigid. In particular, inf((CT)k) = kinf(CT) for every k > 0. Since Tis a multiple of N, one has (CT)k=CT k. Hence, by considering a suitable multiple 33
of T, we can assume that inf(CT) is a multiple of e, that is, CT= ∆eqy1···yr, and RT=z1···zs, where yrz1and zsy1are left weighted. Then one has ∆e(pmN+q)y1···yrz1···zs=XT= ∆e(pmN+q)z1···zsy1···yr, where both decompositions of XTare in left normal form. In other words, the left normal form of XTis invariant under some cyclic permutations of its factors. This is only possible if there is some rigid element Y=y1···ya(where a= gcd(r, s)), such that Yi=y1···yrand Yj=y1···yrz1···zsfor some i, j > 0. But then CT j = (CT)j= (∆e(pmN+q)y1···yr)j= ∆ej(pmN+q)Yij. Since Yij = (y1···yrz1···zs)i, it follows that Yij = ∆ek′XT i for some k′∈Z. Denoting M=T j,t=T i and k=e(k′+jpmN +jq), one finally obtains CM= ∆kXt, as we wanted to show. We will now show that the converse of Proposition 3.18 is also true for elements of canonical length greater than 1, by the following two results. Proposition 3.19. Let X∈USS(X)with ℓ(X)>1. Suppose that CM= ∆kXtfor some integers M, k, t, where M, t > 0and ∆kis central. Then R(X−m)>0for some m > 0. Proof. Notice that CMcommutes with X, hence Mis a multiple of the orbit length of X, and then (CM)r=CMr for every r≥1. This implies C2M= (CM)2= ∆2k(Xt)2, where ∆2kis also central. Hence, replacing Mby a multiple if necessary, we can assume that M≥ ||∆||. By Lemma 2.4, sup(CM) = Mand sup(C2M) = 2M. Hence sup((Xt)2) = −2k+ 2M= 2(−k+M) = 2 sup(Xt). At the same time, since Mis a multiple of the orbit length of Xand M≥ ||∆||, one has ϕ(CM) = F(cM(X)) = F(X) and also ϕ(C2M) = F(X). Therefore ϕ((Xt)2) = ϕ(C2M) = F(X) = ϕ(CM) = ϕ(Xt). By Lemma 3.5, this means that R(X−t)>0, so we take m=tand we are done. Proposition 3.20. Let X∈USS(X)with ℓ(X)>1. Suppose that CM= ∆kXtfor some integers M, k, t, where M, t > 0and ∆kis central. Then XTis rigid for some T > 0. Proof. We know by Proposition 3.19 that R(X−m)>0 for some m > 0. We also know that CMr = ∆krXtr for every r≥1. Hence, replacing Mby a multiple, if necessary, we can assume that both M and tare multiples of m. Since R(X−m)>0, and Mand tare multiples of m, Corollary 3.6 implies that ϕ(XM) = ϕ(Xm) = ϕ(Xt) = ϕ(CM). Notice that M−t6= 0, otherwise RMwould be a power of ∆, while ℓ(RM)>0 by Lemma 2.4. Hence |M−t|is also a nontrivial multiple of m, so we have ϕ(CM) = ϕ(X|M−t|). On the other hand, by Lemma 2.4 one has XM=CMRM∆pM = ∆kXtRM∆pM , where p= inf(X). Since ∆kis central, this means RM=X−t∆−kXM∆−pM =XM−t∆−k−Mp. Recall that ℓ(RM)>0, hence ι(RM) = ι(XM−t). Moreover M−t > 0, otherwise we would have ϕ(CM) = ϕ(Xt−M) and ι(RM) = ι(XM−t) = ∂(ϕ(Xt−M)), whence ϕ(CM)ι(RM) = ∆ and this contradicts Proposition 2.8, which states that ϕ(CM)ι(RM) is left weighted. Therefore M−t > 0, and then ϕ(CM) = ϕ(XM−t). Therefore ϕ(XM−t)ι(XM−t) = ϕ(CM)ι(RM) is left weighted, hence XM−tis rigid and we just take T=M−t. We have then shown the following result. Theorem 3.21. Let X∈USS(X)with ℓ(X)>1. Then Xhas a rigid power if and only if CM= ∆kXt for some integers M, k, t, where M, t > 0and ∆kis central. Moreover, in this case M−t > 0and Mcan be chosen so that RM= ∆sXM−twhere ∆sis central, and XM,Xtand XM−tare all rigid. Proof. The first claim is shown in Propositions 3.18 and 3.20. In the proof of Proposition 3.20 it is also shown that in this case M−t > 0. Replacing Mby some suitable multiples, we replace XM,Xtand XM−tby powers, hence we can choose Min such a way that these three elements are rigid. A very interesting consequence of this result is the following 34
Theorem 3.22. Let X∈USS(X)with ℓ(X)≥1. If Xhas a rigid power, then all elements in USS(X) have rigid powers. Proof. By Theorem 3.21, CM= ∆kXtfor some integers M, k, t, where M, t > 0 and ∆kis central. We can also assume that Mis a multiple of the orbit length of X. Let Y∈USS(X). For i≥1, let C′ i,R′ i,C′ iand R′ idenote the elements analogous to Ci,Ri,Ciand Ri, defined for Yinstead of X. Let αbe a positive element such that α−1Xα =Y. In [22], the M-th transport of αis defined as the element βsuch that α−1CMβ=C′ M. It is shown in [22] that some iterated transport of αwill be equal to α. Hence, replacing Mby a multiple if necessary, we can assume that β=α. But then C′ M=α−1CMα=α−1∆kXtα= ∆kα−1Xtα= ∆kYt. By Theorem 3.21 this means that Yalso has a rigid power. 3.4 Consequences for pseudo-Anosov braids. The results from the previous subsection have a very important consequence in the case of braid groups. The structure of centralizers of pseudo-Anosov braids is well known, and this allows to show that pseudo- Anosov braids in their ultra summit set have rigid powers. Theorem 3.23. Let X∈Bnbe a pseudo-Anosov braid. If X∈USS(X)and ℓ(X)>1, then Xhas a rigid power. Proof. Let Nbe the orbit length of Xunder cycling. Then CNcommutes with X. It is known [25, 24] that if Xis pseudo-Anosov, every element in the centralizer of Xhas a common power with X, up to multiplication by a central power of ∆. Hence (CN)r= ∆kXtfor some integers r,k,t, where ∆kis central. Moreover we can assume that r > 0, otherwise we consider the inverse of the above equation. Since Nis the orbit length of X, (CN)r=CNr, hence taking M=Nr one has CM= ∆kXtfor some positive Mand some integers k, t such that ∆kis central. By Theorem 3.21, we only need to show that t > 0. Suppose that t < 0. Replacing Mby a multiple if necessary, we can assume that M≥ ||∆||, hence ϕ(CM) = F(X) = ϕ(CMr) = ϕ(Xtr) for every r≥1. We can also assume that Mis a (positive) multiple of t, hence t−Mwill be a (negative) multiple of t, and then ϕ(CM) = ϕ(Xt−M). On the other hand, by Lemma 2.4, we know that XM=CMRM∆Mp, where p= inf(X). Hence RM= XM−t∆−k−Mp, and then ι(RM) = ι(XM−t) = ∂(ϕ(Xt−M)). This would contradict Proposition 2.8, which states that ϕ(CM)ι(RM) is left weighted. Therefore t > 0, and Theorem 3.21 implies that Xhas a rigid power. Corollary 3.24. Every pseudo-Anosov braid has a rigid power, up to conjugacy. Proof. Let Ybe a pseudo-Anosov braid, and let X∈SU(Y). That is, Xis conjugate to Yand all powers of Xbelong to their ultra summit set. We know that powers of ∆ are not pseudo-Anosov but periodic, hence ℓ(X)≥1. We will first show that we have ℓ(Xm)>1 for some m > 1. Indeed, if ℓ(Xm) = 1 for all m > 1, since the set of simple elements is finite we would have Xa= ∆usand Xb= ∆vsfor the same simple element sand a6=b. But then Xb−a= ∆v−u, which is not possible since a pseudo-Anosov braid cannot be periodic. Since the property of being pseudo-Anosov is preserved by powers, Xmis a pseudo-Anosov braid such that ℓ(Xm)>1. Moreover, Xm∈USS(Xm), as X∈SU(Y). Hence we can apply Theorem 3.23 to Xm and it follows that some power of Xm, thus some power of X, is rigid. Since Xis conjugate to Y, the result follows. We remark that generic elements of Bnare pseudo-Anosov. This means that most elements in Bnhave rigid powers, up to conjugacy. 35
3.5 A bound for the rigid power of an element. In this section we will show that, if X∈USS(X) has a rigid power, and several powers of Xbelong to their ultra summit sets, then Xmis rigid for some small m, namely m < ||∆||3. Moreover, if ℓ(X)>1 we can take m < ||∆||2. In the particular case of braid groups, using the Artin structure one has ||∆|| =n(n−1)/2, and using the Birman-Ko-Lee structure ||∆|| =n−1. Hence in both cases the bound is polynomial on the number of strands, and does not depend on the length of the braid. We first need to show two results concerning elements having rigid powers and absolute final factors. Proposition 3.25. Let X∈USS(X)with ℓ(X)>1. Suppose that Xhas a rigid power, and that Xt∈USS(Xt)for some t > 1. Then F(X) = F(Xt). Proof. By Theorem 3.21, one has CM= ∆kXrfor some M, k, r such that M, r > 0 and ∆kis central. Replacing Mby a multiple if necessary, so that Mis a multiple of the orbit length of Xunder cycling, one has C[−M,M]=CM= ∆kXr. In the same way, Xtalso has a rigid power. Moreover, since ℓ(Ct)≥1, ℓ(Rt)≥1 and CtRtis left weighted, one has ℓ(Xt)>1. Hence we can apply Theorem 3.21 to Xtand we obtain C(t) [−M′,M′]= C(t) M′= ∆k′Xtr′for some M′, r′>0 and some k′such that ∆k′is central. Replacing Mand M′above by some suitable multiples, we can assume that r=tr′, and also that M, M′≥ ||∆||. Hence F(Xt) = ϕ(C[−M′,M′]) = ϕ(∆k′Xtr′) = ϕ(∆kXr) = ϕ(C[−M,M]) = F(X). Proposition 3.26. Let X∈USS(X)with ℓ(X)>1, and suppose that Xhas a rigid power. If R(X)>0, then ι(X) = I(X). If R(X−1)>0, then ϕ(X) = F(X). Proof. By Theorem 3.21, there exists some M > 0 such that CM= ∆kXtand RM= ∆sXM−t, where t > 0, M−t > 0, and both ∆kand ∆sare central. Suppose that R(X−1)>0. By Corollary 3.6 this implies that ϕ(Xm) = ϕ(X) for every m≥1. We can assume that Mis a multiple of the orbit length of X, hence C[−M,M]=CM. If one chooses Mbig enough (replacing it by a multiple if necessary), one has F(X) = ϕ(C[−M,M]) = ϕ(CM) = ϕ(Xt) = ϕ(X). Now suppose that R(X)>0. Then ι(Xm) = ι(X) for every m > 0, by Corollary 3.6. In the same way as above, since Mis a multiple of the orbit length of Xand M−t > 0, replacing M(and thus t) by a multiple if necessary one has I(X) = ι(R[−M,M]) = ι(RM) = ι(∆sXM−t) = ι(XM−t) = ι(X). In order to obtain the claimed bound on rigid powers, we need to investigate how the left normal form of C[k,m]is modified when we multiply it on the left by Ck. We actually show the following, more general result. Proposition 3.27. Let X∈USS(X)with ℓ(X)>1, and suppose that Xhas a rigid power. Let t > 1 be such that Xt∈USS(Xt). Consider C1···Cm= ∆ky1···ysand Cm+1 · · · Cm+t= ∆qz1···zrin left normal form. Then, the final t−1factors in the left normal form of C1···Cm+tare precisely z2···zr. Proof. We will need to use the factors Ciand Ricorresponding to the element Y= (cm(X))t. In order to avoid an excessive use of indices, we will denote them by C′ iand R′ i. That is, C′ 1=ι(Y), and the other elements C′ iand R′ iare defined in the same way as the corresponding elements for X. We know by Theorem 2.9 that Cm+1 ···Cm+tis equal to the product of the first tfactors (including ∆’s) in the left normal form of (cm(X))t∆−pt (where p= inf(X)). Hence C′ 1=ι((cm(X))t) = τ−q(z1), and τ−q(z2)R′ 1. Now one has C1···CmCm+1 ···Cm+t =C1···Cm∆qz1···zr =C1···Cmτ−q(z1)τ−q(z2)∆qz3···zr. 36
By Proposition 2.12 and the definition of absolute final factors, one has ϕ(C1···Cm)F(cm(X)). Recall from the proof of Proposition 2.23 that if Xt∈USS(Xt) then (cm(X))talso belongs to its ultra summit set, since the action of cycling or decycling any power of X(in particular X) preserves the set of powers of Xbelonging to their ultra summit set. Moreover, since Xhas a rigid power, Theorem 3.22 implies that cm(X) also has a rigid power. We can then apply Proposition 3.25 to obtain F(cm(X)) = F((cm(X))t) = F(Y). Hence ϕ(C1···Cm)F(Y). This yields the following: ϕ(C1···Cmτ−q(z1)) = ϕ(C1···CmC′ 1)ϕ(F(Y)C′ 1) = ϕ(C′ −a+1 ···C′ −1C′ 0C′ 1) for abig enough. But we know by Lemma 2.5 that the decomposition ϕ(C′ −a+1 ···C′ −1C′ 0C′ 1)R′ 1 is left weighted. Hence ϕ(C1···Cmτ−q(z1)) τ−q(z2) is also left weighted, and the factors z2···zrare not modified when computing the left normal form of C1···Cm+t. The fact that the left normal forms of C[−m,m]are not modified too much when one increases m, implies a strong property on the initial factors of powers of X: they are comparable by . First we need the following technical result. Lemma 3.28. Let A= ∆px1···xr∈G, and let sbe a simple element. Then either ι(As)ι(A)or ι(A)ι(As). Proof. Suppose there is no unexpected ∆ when multiplying Aby s, that is, inf(As) = p. Then ι(∆px1···xrs) = τ−p(x1t) for some (possibly trivial) simple element t. Hence ι(A) = τ−p(x1) τ−p(x1t) = ι(As). Now suppose there is an unexpected ∆, that is, inf(As) = p+ 1. Let α= (x2···xrs)∧∆. Then ι(As) = ι(∆px1···xrs) = ι(∆px1α). Moreover, x1α= ∆βfor some simple element β, that is, α=∂(x1)β. Since αis simple, it follows that β∂2(x1) = τ(x1). Therefore ι(As) = ι(∆px1α) = ι(∆p+1β)ι(∆p+1τ(x1)) = τ−p(x1) = ι(A). Proposition 3.29. Let X∈USS(X)with ℓ(X)>1. Suppose that Xhas a rigid power, and let t≥1 such that Xt∈USS(Xt). Then for every m≥1, the simple elements ι(C1···Cm)and ι(C1···Cm+t) are comparable. That is, either ι(C1···Cm)ι(C1···Cm+t) or ι(C1···Cm+t)ι(C1···Cm). Proof. Write C1···Cm= ∆ky1···ysand Cm+1 ···Cm+t= ∆qz1···zr. We know by Proposition 3.27 that ϕ(y1···ysτ−q(z1)) τ−q(z2) is left weighted. Hence ι(C1···Cm+t) = ι(∆ky1···ysτ−q(z1)), where τ−q(z1) is simple. By Lemma 3.28, this implies that ι(C1· · · Cm+t) is comparable to ι(∆ky1···ys) = ι(C1···Cm), as we wanted to show. We can finally state the result concerning the initial factors of powers of X. 37
Corollary 3.30. Let X∈USS(X)with ℓ(X)>1, and suppose that Xhas a rigid power. If Xm∈ USS(Xm)for m= 1,...,||∆||, then the set {ι(X), ι(X2),···ι(X||∆||)} is totally ordered by (although the total order given by does not necessarily coincide with the above enumeration). Proof. We just need to recall from Theorem 2.9 that ι(Xm) = ι(C1···Cm) for every m≥1, and use the above result. Since every two elements are comparable by , the set is totally ordered. Corollary 3.31. With the above conditions, there exist some integers a, b with 1≤a < b ≤ ||∆|| such that ι(Xa) = ι(Xb). Proof. The length of a strict chain of simple elements 1 ≺s1≺s2≺ · · · ≺ sr≺∆ is bounded by ||∆||. Since the elements in {ι(X), ι(X2),···ι(X||∆||)}are totally ordered, the lack of a repeated pair would provide a chain of bigger length, which is not possible. It is important to notice that, in the sequence ι(X), ι(X2), ι(X3),..., when one encounters the first repetition, the sequence becomes periodic. And the period is the distance between the two repeated elements. This is given by the following result. Proposition 3.32. With the above conditions, if ι(Xa) = ι(Xb)then ι(Xa+k) = ι(Xb+k)for every k≥0. Proof. By hypothesis ι(C1···Ca) = ι(Xa) = ι(Xb) = ι(C1···Cb). Applying to this equality the transport defined in [22], one obtains ι(C2···Ca+1) = ι(C2···Cb+1). Let ι=ι(C2···Ca+1) = ι(C2···Cb+1). By Proposition 3.27, if we multiply C2···Ca+1 or C2···Cb+1 on the left by C1, only their initial factors (which in both cases are equal to ι) are modified. Moreover, since sup(C1· · · Ca+1) = a+ 1, it follows that sup(C1ι) = 2. Hence the initial factor of C1···Ca+1 is equal either to ∆ ∧(C1ι) (if the infimum does not increase) or to (C1ι)∆−1(if the infimum increases). In any case, ι(C1···Ca+1) = ι(C1ι). In the same way, ι(C1···Cb+1) = ι(C1ι), hence ι(Xa+1) = ι(Xb+1). Induction on kfinishes the proof. The above results can be used to bound the smallest power of Xhaving some rigidity. Proposition 3.33. Let X∈USS(X)with ℓ(X)>1, and suppose that Xhas a rigid power. If Xt∈ USS(Xt)for t= 1,...,||∆||, then R(Xm)>0for some positive m < ||∆||. Proof. We know by Corollary 3.31 that ι(Xa) = ι(Xb) for some 1 ≤a < b ≤ ||∆||, and by Proposition 3.32 that the sequence ι(Xa), ι(Xa+1), ι(Xa+2),... is periodic of period d=b−a. Since the interval [a, b] has length d, there exists a unique m,a≤m < b, which is a multiple of d. Then ι(Xm) = ι(Xm+m) = ι((Xm)2). Hence, by Lemma 3.4, we will have R(Xm)>0 if we show that inf(X2m) = 2 inf(Xm). Suppose that Xm= ∆py1···yr. Since m < b ≤ ||∆|| one has Xm∈USS(Xm), so ∆ 6 y2···yrτ−p(y1), which implies ∆ 6 y2···yrτ−p(y1···yr) since τ−p(y1) is the biggest simple prefix of τ−p(y1···yr). Then y1∆6 y1y2···yrτ−p(y1···yr). But if inf(X2m) = 2p+ 1 then, since X2m= (Xm)2= ∆py1· · · yr∆py1···yr, we would have ∆ τp(y1···yr)y1· · · yr, and since ι(X2m) = ι(Xm) = τ−p(y1), it would follow that ∆τp+1(y1)τp(y1···yr)y1· · · yr. Applying τ−pto this inequality, we would obtain ∆τ(y1) = y1∆ y1···yrτ−p(y1···yr), a contradiction. Therefore inf(X2m) = 2p= inf(Xm), and since ι(X2m) = ι(Xm) it follows from Lemma 3.4 that R(Xm)>0. Theorem 3.34. Let X∈USS(X)with ℓ(X)>1, and suppose that Xhas a rigid power. If Xt∈ USS(Xt)for every tsuch that −||∆|| ≤ t≤ ||∆||, then there is some m < ||∆||2such that Xmis rigid. 38
Proof. By Proposition 3.33, R(Xp)>0 for some 0 < p < ||∆||. Applying Proposition 3.33 to X−1, one obtains that R(X−q)>0 for some 0 < q < ||∆||. Let m= lcm(p, q)≤pq < ||∆||2. Since Xmis a power of Xp, it follows from Corollary 3.11 that Xmit belongs to a closed orbit under cycling, hence it has maximal infimum in its conjugacy class [18]. In the same way, since X−mis a power of X−q, it follows from Corollary 3.11 that X−mbelongs to a closed orbit under cycling, thus Xmbelongs to a closed orbit under decycling, and hence it has minimal supremum in its conjugacy class [18]. Therefore Xm∈SSS(Xm), and since it belongs to a closed orbit under cycling, Xm∈USS(Xm). Moreover, by Proposition 3.9, R(Xm)>0 and R(X−m)>0, since they are powers of Xpand X−q. This implies by Proposition 3.26 that ι(Xm) = I(Xm) and ϕ(Xm) = F(Xm). Since F(Xm)I(Xm) is left weighted by Proposition 2.20, it follows that ϕ(Xm)ι(Xm) is left weighted as written, hence Xmis rigid, as we wanted to show. Remark: The proof of the above result is based on the fact that if an element Xis such that R(X)>0 and R(X−1)>0, and if Xhas a rigid power, then Xis already rigid. The hypothesis of Xhaving a rigid power is necessary, since we could have Xand X−1with some rigidity without Xbeing rigid, even if X∈SU(X). For instance, if we consider the reducible braid X=σ1σ3·σ3∈B4, we have R(X) = R(X−1) = 1/2, but neither Xnor any power of Xis rigid, since Xm= (σ1σ3)m·σm 3. In this case X∈SU(X) and R(Xm) = 1/2 for every m6= 0. We can also find a bound for the smallest rigid power in the case ℓ(X) = 1, thanks to the following result. Lemma 3.35. Let X∈Gwith ℓ(X) = 1. If Xt∈USS(Xt)for t= 1,...,||∆||, then ℓ(Xm)6= 1 for some m≤ ||∆||. Proof. Suppose that ℓ(Xt) = 1 for t= 1,...,||∆||. We will show that the set {ι(X), ι(X2),...,ι(X||∆||)} is totally ordered by showing that any two elements in that set are comparable. Indeed, given s, t ∈ {1,...,||∆||} with s < t, we have ℓ(Xt−s) = 1, hence ι(Xt) = ι(XsXt−s) = ι(Xsι(Xt−s)). Since ι(Xt−s) is simple, Lemma 3.28 implies that either ι(Xt)ι(Xs) or ι(Xs)ι(Xt). Therefore, {ι(X), ι(X2),...,ι(X||∆||)}is a totally ordered set of proper simple elements, thus ι(Xa) = ι(Xb) for some 1 ≤a < b ≤ ||∆||. But since ℓ(Xa) = ℓ(Xb) = 1, this means that Xb−ais a power of ∆, a contradiction. Therefore, ℓ(Xm)6= 1 for some m≤ ||∆||. We can finally remove the hypothesis ℓ(X)>1 in order to bound the rigid power of an element. Theorem 3.36. Let X∈USS(X), and suppose that Xhas a rigid power. If Xt∈USS(Xt)for every tsuch that −||∆||2≤t≤ ||∆||2, then there is some m < ||∆||3such that Xmis rigid. Proof. If ℓ(X)>1 the result follows from Theorem 3.34. If ℓ(X) = 1, Lemma 3.35 implies that ℓ(Xr)6= 1 for some r≤ ||∆||. We cannot have ℓ(Xr) = 0, otherwise Xwould be periodic and would not have a rigid power. Hence ℓ(Xr)>1, and (Xr)t∈USS((Xr)t) for −||∆|| ≤ t≤ ||∆||. The hypothesis of Theorem 3.34 are then satisfied by Xr, hence (Xr)sis rigid for some s < ||∆||2. Therefore Xrs is rigid with rs < ||∆||3. In the case of braid groups, the above result implies the following. Theorem 3.37. If X∈Bnis a pseudo-Anosov braid, then USS(Xm)consists of rigid braids, for m < ||∆||3. Moreover, if the canonical length of the elements in USS(X)is greater than 1, then m < ||∆||2. Proof. By Corollary 3.24, some conjugate Yof Xhas a rigid power. Moreover, one can choose Y∈ SU(X), hence by Theorem 3.36 Ymis rigid for m < ||∆||3(and m < ||∆||2if ℓ(Y)>1). In the proof of Theorem 3.36 we see that we can assume ℓ(Ym)>1, hence it follows from Theorem 3.15 that USS(Ym) consists of rigid elements. 39
To summarize the consequences for pseudo-Anosov braids, we can solve the CDP/CSP problem for two pseudo-Anosov elements X, Y ∈Bnusing rigid braids. We just need to compute an element in USS(Xt) for each t= 1,2,... until we find one of them, say e Xm∈USS(Xm) which is rigid and has canonical length greater than one. By the above result, m < ||∆||3. Then all elements in USS(Xm) will be rigid, so the computation of USS(Xm) is easier than in the general case, as will be seen in [9], and we will possibly be able to bound the size of USS(Xm). Moreover, since pseudo-Anosov braids have unique roots, if one solves the CDP/CSP for Xmand Ym, finding some conjugating element Z, then Zis also a conjugating element for Xand Y, so this solves the CDP/CSP for Xand Y. References [1] S. I. Adyan, Fragments of the word ∆in the braid group, (Russian) Mat. Zametki 36, no. 1 (1984), 25-34. [2] I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public key crypography, Math research letters 6, No. 3-4 (1999), 287-291. [3] E. Artin, Theorie der Z¨opfe, Abh. Math. Sem. Hamburg, 4(1925), 47-72. [4] D. Benardete, M. Guitierrez and Z. Nitecki, A combinatorial approach to reducibility of mapping classes, Mapping class groups and moduli spaces of Riemann surfaces (G¨ottingen, 1991/Seattle, WA, 1991), 1–31, Contemp. Math., 150, Amer. Math. Soc., Providence, RI, 1993. [5] D. Benardete, M. Guitierrez and Z. Nitecki, Braids and the Nielsen-Thurston classification, J. Knot Theory and its Ramifications 4(1995), 549-618. [6] D. Bessis, The dual braid monoid, Ann. Sci. ´ Ecole Norm. Sup. 36 (2003), no. 5, 647-683. [7] J. Birman, K. Y. 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. [8] J. Birman, K. Y. Ko and S. J. Lee, The infimum, supremum and geodesic length of a braid conjugacy class, Adv. Math. (2001), 164, No. 1, (2001), 41-56. [9] J. Birman, V. Gebhardt and J. Gonz´alez-Meneses, Conjugacy in Garside groups II: Structure of the Ultra Summit Set [10] J. Birman, V. Gebhardt and J. Gonz´alez-Meneses, Conjugacy in Garside groups III: Periodic Braids [11] N. Bourbaki, GROUPS ET ALGEBRES DE LIE, Chapitres 4,5,6, Hermann, Paris 1968. [12] E. Brieskorn and K. Saito, Artin-Gruppen und Coxeter-Gruppen, Invent. Math. 17 (1972), 245-272. [13] J. Crisp, private communication. [14] P. Dehornoy, Groupes de Garside, Ann. Scient. Ec. Norm. Sup. 35 (2002), 267-306. [15] P. Dehornoy and L. Paris, Gaussian groups and Garside groups, two generalizations of Artin groups, Proc. London Math. Soc. 79(1999), No. 3, 569-604. [16] I. Dynnikov and B. Wiest, On the complexity of braids, arXiv math.GT/0403177. [17] P. Deligne, Les immeubles des groupes de tresses generalises, Invent. Math. 17 (1972), 273-302. [18] E. ElRifai and H. Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser (2), 45 (180) (1994), 479-497. [19] D. Epstein, J. Cannon, F. Holt, S. Levy, M. Patterson and W. Thurston, WORD PROCESSING IN GROUPS, Jones and Bartlett, Boston, MA 1992. 40
[20] N. Franco and J. Gonz´alez-Meneses, The conjugacy problem for braid groups and Garside groups, Journal of Algebra, 266, No. 1 (2003), 112-132. [21] F. Garside, The braid group and other groups, Quart. J. Math Oxford 20 (1969), 235-254. [22] V. Gebhardt, A new approach to the conjugacy problem in Garside groups, Journal of Algebra 292, No. 1 (2005),282-302. [23] J. Gonz´alez-Meneses, The nth root of a braid is unique up to conjugacy, Algebraic and Geometric Topology 3(2003), 1103-1118. [24] J. Gonz´alez-Meneses and B. Wiest, On the structure of the centralizer of a braid, Ann. Sci. ´ Ecole Norm. Sup. (4) 37 (2004), no. 5, 729-757. [25] N. V. Ivanov, Subgroups of Teichm¨uller modular groups, Translations of mathematical monographs vol. 115 (1992), AMS. [26] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park, New publlic key cryptosystems using braid groups, in Lecture Notes in Computer Science 1880, Springer, Berlin 2000. [27] S. J. Lee, Garside theory on reducible braids, arXiv math.GT/0506188. [28] S. J. Lee, Garside groups are strongly translation discrete, arXiv math.GT/0411470. [29] E.K. Lee and S.J. Lee, Stable super summit sets in Garside groups, arXiv math.GT/0602582. [30] E.K. Lee and S.J. Lee, Translation numbers in a Garside group are rational with uniformly bounded denominators, arXiv math.GT/0604061. [31] E.K. Lee and S.J. Lee, Some power of an element in a Garside group is conjugate to a periodically geodesic element, arXiv math.GN/0604144. [32] J. Michel, A note on words in braid monoids, J. Algebra 215 (1999), no. 1, 366-377. [33] J. Nielsen, Collected Mathematical Papers of Jakob Nielsen, edited by V. Hansen, Birkh¨auser (1986), [N-18], [N-20] and [N-21]. [34] M. Picantin, The conjugacy problem in small Gaussian groups, Comm. Algebra 29, No. 3 (2001), 1021-1039. [35] M. Picantin, PhD thesis. Universit´e de Caen, 2000. Available at www.liafa.jussieu.fr/ picantin/publi.html [36] W. Thurston, On the topology and geometry of diffeomorphisms of surfaces, Bull. Amer. Math. Soc. 19 (1988), 109-140. [37] P. J. Xu, The genus of closed 3-braids, Journal of Knot Theory and its Ramifications 1, No. 3 (1992), 303-326. Joan S. Birman Volker Gebhardt Juan Gonz´alez-Meneses Department of Mathematics, School of Computing and Mathematics, Departamento de ´ Algebra, Barnard College andColumbia University, University of Western Sydney, Universidad de Sevilla, 2990 Broadway, Locked Bag 1797, Apdo. 1160, New York, New York 10027, USA. Penrith South DC NSW 1797, Australia, 41080 Sevilla, Spain. [email protected] [email protected] menes[email protected] 41