Twisted conjugacy in braid groups

TWISTED CONJUGACY IN BRAID GROUPS JUAN GONZ´ ALEZ-MENESES AND ENRIC VENTURA Abstract. In this note we solve the twisted conjugacy problem for braid groups, i.e. we propose an algorithm which, given two braids u, v ∈Bnand an automorphism ϕ∈Aut(Bn), decides whether v= (ϕ(x))−1ux for some x∈Bn. As a corollary, we deduce that each group of the form BnoH, a semidirect product of the braid group Bnby a torsion-free hyperbolic group H, has solvable conjugacy problem. 1. Introduction Let Gbe a group, and ϕ∈Aut(G) an automorphism (which we shall write on the left of the argument, g7→ ϕ(g)). We say that two elements u, v ∈Gare ϕ-twisted conjugated, denoted u∼ϕv, if there exists x∈Gsuch that v= (ϕ(x))−1ux. It is straightforward to see that ∼ϕis an equivalence relation on G, which coincides with standard conjugation in the case ϕ=Id (we shall use the symbol ∼instead of ∼Id). Reidemeister was the first author considering this concept (see [14]), which has an important role in modern Nielsen fixed point theory. As one might expect, in general, twisted conjugacy classes are much more complicated to understand than standard conjugacy classes in a group G. For instance, algorithmic recognition of them already presents big differences. The twisted conjugacy problem for a group Gconsists on finding an algorithm which, given an automorphism ϕ∈Aut(G) and two elements u, v ∈G, decides whether u∼ϕv or not. While the conjugacy problem (i.e. the Id-twisted conjugacy problem) is very easy for free groups, both conceptually and computationally, the twisted conjugacy problem is solvable but much harder in both senses, see Theorem 1.5 in [3]. Of course, a positive solution to the twisted conjugacy problem automatically gives a solution to the (standard) conjugacy problem, which in turn provides a solution to the word problem. The existence of a finitely presented group Gwith solvable word problem but unsolvable conjugacy problem is well known (see [13]). 2000 Mathematics Subject Classification. 20F36, 20F10. Key words and phrases. Braid group, twisted conjugacy. 1 2 JUAN GONZ ´ ALEZ-MENESES AND ENRIC VENTURA In the same direction, there exists a finitely presented group with solvable conjugacy problem, but unsolvable twisted conjugacy problem (see Corollary 4.9 in [2]). A subgroup A⩽Aut(G) is said to be orbit decidable if there is an algorithm which, given two elements u, v ∈Gas input, decides whether one can be mapped to the other up to conjugacy, by some automorphism in A, i.e. whether v∼α(u) for some α∈A(see [2] for more details). For example, the conjugacy problem in Gcoincides precisely with the orbit decidability of the trivial subgroup {Id}⩽ Aut(G). Let 1−→ Fα −→ Gβ −→ H−→ 1. be a short exact sequence of groups. Since α(F) is normal in G, for every g∈G, the right conjugation γgof Ginduces an automorphism of F,x7→ g−1xg, which will be denoted ϕg∈Aut(F) (note that, in general, ϕgdoes not belong to Inn(F)). It is clear that the set of all such automorphisms, AG={ϕg|g∈G}, forms a subgroup of Aut(F) containing Inn(F). We shall refer to it as the action subgroup of the given short exact sequence. Such a sequence is said to be algorithmic provided it is given along with algorithms: (i) to compute in the groups F,Gand H(i.e. multiply and invert elements), and compute images under αand β; (ii) to compute one pre-image in Gof any given element in H; and (iii) to compute pre-images in Fof elements in Gmapping to the trivial element in H. The typical example (though not the unique one) of an algorithmic short exact sequence occurs when groups are given by finite presentations and maps are given by images of generators. In fact, (i) is immediate, we can use the positive part of the membership problem for β(G) in Hto compute pre-images in Gof elements in H, and use the positive part of the membership problem for α(F) in Gto compute pre-images in Fof elements in Gmapping to 1H(see Section 2 in [2]). Assuming certain conditions on the groups Fand H, the main result in [2] establishes the following characterization of the solvability of the conjugacy problem for G, in terms of the orbit decidability for the corresponding action subgroup. Theorem 1.1 (Bogopolski, Martino, Ventura [2]).Let 1−→ Fα −→ Gβ −→ H−→ 1 be an algorithmic short exact sequence of groups such that (i) Fhas solvable twisted conjugacy problem, (ii) Hhas solvable conjugacy problem, and TWISTED CONJUGACY IN BRAID GROUPS 3 (iii) for every 16=h∈H, the subgroup hhihas finite index in its centralizer CH(h), and there is an algorithm which computes a finite set of coset representatives, zh,1, . . . , zh,th∈H, CH(h) = hhizh,1t · · · t hhizh,th. Then, the conjugacy problem for Gis solvable if and only if the action subgroup AG⩽Aut(F)is orbit decidable. Many groups satisfy conditions (ii) and (iii); for example, they are easily verified for a finitely generated free group, and with a bit more work, they can also be proven for torsion-free hyperbolic groups, see Proposition 4.11 in [2]. On the other hand, solvability of the twisted conjugacy problem is a stronger condition on F. In this sense, the introduction of [2] contains the following comment: “In light of Theorem 1.1, it becomes interesting, first, to collect groups Fwhere the twisted conjugacy problem can be solved. And then, for every such group F, to study the property of orbit decidability for subgroups of Aut(F): every orbit decidable (undecidable) subgroup of Aut(F)will correspond to extensions of Fhaving solvable (unsolvable) conjugacy problem”. The goal of the present paper is to contribute a new result into this direction, taking as a base group the braid group, F=Bn. Consider the braid group on nstrands, given by the classical presentation (1) Bn=*σ1, σ2, . . . , σn−1 σiσj=σjσi|i−j|>1 σiσjσi=σjσiσj|i−j|= 1 + It is well known that the conjugacy problem is solvable in Bn. The first, nonefficient solution was given by Garside [8]. It was subsequently improved in [6, 7, 1, 9, 10], in such a way that the current solution is very efficient in most cases. Theorem 1.2 (Garside [8]).The conjugacy problem is solvable in Bn. Also, the automorphism group of Bnis quite well understood. Among other results, the following one will be crucial for our argumentation. Theorem 1.3 (Dyer, Grossman [5]).Let Bnbe the braid group on nstrands. Then |Out(Bn)|= 2. More precisely, Aut(Bn) = Inn(Bn)tInn(Bn)·ε, where ε:Bn→Bnis the automorphism which inverts each generator, σi7→ σ−1 i. Using the above two results, we will solve the twisted conjugacy problem in Bn, and the orbit decidability problem for every subgroup A⩽Aut(Bn). As a consequence, we deduce that the conjugacy problem is solvable in certain extensions of Bn. 4 JUAN GONZ ´ ALEZ-MENESES AND ENRIC VENTURA Theorem 4.9. The twisted conjugacy problem is solvable in the braid group Bn. Theorem 5.1. Every finitely generated subgroup A⩽Aut(Bn)is orbit decidable. Theorem 5.2. Let G=BnoHbe an extension of the braid group Bnby a finitely generated group Hsatisfying conditions (ii) and (iii) above (for instance, take Htorsion-free hyperbolic). Then, Ghas solvable conjugacy problem. The structure of the paper is as follows. In Section 2 we review some known facts about normal forms for braids that will be used later. In Section 3 we determine a well defined finite subset of each ε-twisted conjugacy class in Bn. And in Section 4 we give an algorithm to construct such set from a given element in the class, solving the twisted conjugacy problem in Bn. Finally, in Section 5 we solve the orbit decidability problem for subgroups of Aut(Bn) and conclude Theorem 5.2. 2. Normal forms of braids In this section we will recall the notion of normal form for braids, as explained in [15, Chapter 9] and [6], and we shall also provide some technical lemmas that will be used to prove our main results. In the braid group Bn, an element is called positive if it can be written as a product of non-negative powers of the generators σ1, . . . , σn−1. It turns out that if we regard the standard presentation of the braid group (1) as a monoid presentation, it yields a monoid B+ nwhich embeds in Bn, and is precisely the submonoid of positive braids [8]. This means that two positive words represent the same braid if and only if one can be obtained from the other by a finite sequence of the following operations: Either replacing a subword σiσjby σjσifor |i−j|>1, or replacing a subword σiσjσiby σjσiσjfor |i−j|= 1. There is a partial order 4on the elements of Bn, called the prefix order, defined by a4bif and only if a−1bis positive. If aand bare positive this means that b can be written as a positive word in which aappears as a prefix. There is also asuffix order,<, defined by a<bif and only if ab−1is positive. These orders are known to be lattice orders, meaning that for every a, b ∈Bnthere is a unique greatest common divisor a∧b(resp. a∧Rb) and a unique least common multiple a∨b(resp. a∨Rb) with respect to 4(resp. <). The order 4is, by definition, invariant under left-multiplication. That is, a4 b⇔ca 4cb for all a, b, c ∈Bn. This implies that cx ∧cy =c(x∧y) and cx ∨cy =c(x∨y) for all c, x, y ∈Bn. Similarly, <is invariant under rightmultiplication, and one has xc ∧Ryc = (x∧Ry)cand xc ∨Ryc = (x∨Ry)cfor all c, x, y ∈Bn. TWISTED CONJUGACY IN BRAID GROUPS 5 The braid group Bnhas a special element called Garside element or half twist, ∆ = σ1(σ2σ1)(σ3σ2σ1)· · · (σn−1· · · σ1). Conjugation by ∆ preserves 4and <. We denote by τthe inner automorphism of Bndefined by ∆, that is, τ(x) = ∆−1x∆ for all x∈Bn. We recall that the center of Bnis infinite cyclic, generated by ∆2. Hence τpreserves 4and <(thus it preserves ∧,∨,∧Rand ∨R), and τ2= id. The set of positive prefixes of ∆, denoted [1,∆] = {s∈Bn; 1 4s4∆}, is called the set of simple elements of Bn. This set is finite, namely it has n! elements. Simple elements are the building blocks that conform the usual normal forms of braids. A simple element will be said to be proper if it is neither 1 nor ∆. The right complement ∂(s) of a simple element sis a simple element tsuch that st = ∆, that is, ∂(s) = s−1∆. The map ∂is a bijection of the set of simple elements. Moreover, ∂2=τ. The left complement of a simple element is precisely ∂−1(s)=∆s−1. If a positive element is written as a product of two simple elements s1s2, we say that such a decomposition is left weighted if s1is the maximal simple prefix of s1s2, that is s1s2∧∆ = s1, or alternatively (multiplying from the left by s−1 1), if s2∧∂(s1) = 1. We say that the decomposition s1s2is right weighted if s2is the maximal simple suffix of s1s2, that is s1s2∧R ∆ = s2, or alternatively (multiplying from the right by s−1 2), if s1∧R∂−1(s2) = 1. Given an element x∈Bn, we say that a decomposition x= ∆px1· · · xris the left normal form of xif pis the maximal integer such that ∆−pxis positive, each xi is a proper simple element, and xixi+1 is left weighted for i= 1, . . . , r−1. We say that a decomposition x=x0 1· · · x0 r∆pis the right normal form of xif pis the maximal integer such that x∆−pis positive, each x0 iis a proper simple element, and x0 ix0 i+1 is right weighted for i= 1, . . . , r −1. The left and right normal forms are unique decompositions, and the numbers pand rare determined by xand do not depend on the normal form (left or right) which is used to define them. In this way, one defines the infimum,supremum and canonical length of x as, respectively, inf(x) = p, sup(x) = p+rand `(x) = r. It will be convenient for our purposes to use the following notation. When we deal with a positive element x, and we say that its left normal form is x=x1· · · xr, (with no power of ∆ on the left), we are allowing some of the initial factors to be equal to ∆. That is, if inf(x) = p > 0, this will mean that x1=· · · =xp= ∆, so the actual normal form of xwould be ∆pxp+1 · · · xr. There is still another normal form that we shall use. It is well known [15, 4] that, for every x∈Bnthere exist unique positive elements uand v, with u∧v= 1, such that x=u−1v. If the left normal forms of uand vare, respectively, u=u1· · · urand v=v1· · · vs, the mixed normal form of xis 6 JUAN GONZ ´ ALEZ-MENESES AND ENRIC VENTURA defined to be x=u−1 r· · · u−1 1v1· · · vs. We recall from [15] that, if xcan be written as x=u−1vwith uand vpositive elements with left normal forms u1· · · ur and v1· · · vs, then u−1 r· · · u−1 1v1· · · vsis the mixed normal form of xif and only if u1∧v1= 1. We remark [15] that if x=u−1 r· · · u−1 1v1· · · vsis in mixed normal form as above, the left normal form of u−1is ∆−ru0 r· · · u0 1(where u0 i=∂−2i−1(ui)), and the left normal form of xis equal to x= ∆−ru0 r· · · u0 1v1· · · vs. Therefore, from the mixed normal form one can already obtain inf(x) = −r,`(x) = r+sand hence sup(x) = s. The following technical results will be used later. Lemma 2.1. Let aand bbe positive braids whose left normal forms are a= a1· · · ar,b=b1· · · bs, and whose right normal forms are a=a0 1· · · a0 r,b= b0 1· · · b0 s. Consider x=a−1b. If `(x)≤r+s−2k+ 1 for some integer k > 0, then either a0 1· · · a0 k4b1· · · bkor b0 1· · · b0 k4a1· · · ak. Proof. Let d=a∧b, and write a=dα and b=dβ. Then x=a−1b=α−1β, where αand βare positive elements such that α∧β= 1. Hence sup(α)+sup(β)+2k−1 = `(x)+2k−1≤r+s= sup(a)+sup(b). This implies that either sup(α)+k≤sup(a) or sup(β) + k≤sup(b). Suppose that sup(α) + k≤sup(a) = r. This means that αcan be written as a product of at most r−ksimple elements. But dα =a=a0 1· · · a0 r, where the latter decomposition is in right normal form. It follows that αmust be a suffix of a0 k+1 · · · a0 r, and then a0 1· · · a0 k4d. Hence a0 1· · · a0 k4dβ =b=b1· · · bs. Since the latter decomposition is in left normal form, one finally obtains a0 1· · · a0 k4b1· · · bk. In the case sup(β) + k≤sup(b) = s, one can apply the above reasoning to βand b, to obtain b0 1· · · b0 k4a1· · · ak. Let us denote by εthe automorphism of Bnthat sends σito σ−1 ifor i= 1, . . . , n −1. Also, let rev: Bn→Bnbe the anti-automorphism that sends each σito itself, that is, it sends a braid represented by a word w, to the braid represented by the same word written backwards. We will write, for every x∈Bn, rev(x) = ←− x. Let us also denote inv: Bn→Bnthe anti-automorphism inv(x) = x−1. Notice that the composition of any two of the maps in {ε, rev,inv}, in any order, yields the third one. Lemma 2.2. Let xbe a positive braid with sup(x) = r+k, where r≥k≥1. If `(ε(x)x)≤2r+ 1 then there exist positive braids aand bsuch that x=←− a ba and sup(b)≤r. Proof. Let x1· · · xr+kbe the left normal form of xand let y1· · · yr+kbe its right normal form. Hence ←−− xr+k· · · ←− x1is the right normal form of ←− xand ←−− yr+k· · · ←− y1 TWISTED CONJUGACY IN BRAID GROUPS 7 is its left normal form. Notice that ε(x)x= (←− x)−1x. Hence, if `(ε(x)x) = `((←− x)−1x)≤2r+ 1, Lemma 2.1 tells us that either ←−− xr+k· · · ←−− xr+1 4x1· · · xkor y1· · · yk4←−− yr+k· · · ←−− yr+1. Suppose that ←−− xr+k· · · ←−− xr+1 4x1· · · xk, and write x1· · · xk=←−− xr+k· · · ←−− xr+1αfor some positive α. Since r≥k, one can then write x= (←−− xr+k· · · ←−− xr+1)αxk+1 · · · xr(xr+1 · · · xr+k), so the result follows in this case taking a=xr+1 · · · xr+kand b=αxk+1 · · · xr(if k=rthen b=α). Notice that sup(b)≤ras bis a suffix of x1· · · xr. Now suppose that y1· · · yk4←−− yr+k· · · ←−− yr+1, and write ←−− yr+k· · · ←−− yr+1 =y1· · · ykβ for some positive β, which is equivalent to yr+1 · · · yr+k=←− β←− yk· · · ←− y1. Then x= (y1· · · yk)yk+1 · · · yr ←− β(←− yk· · · ←− y1). Taking a=←− yk· · · ←− y1and b=yk+1 · · · yr ←− β, which is a prefix of yk+1 · · · yk+r, the result follows also in this case.  We define a palindromic-free braid as a positive braid xthat cannot be decomposed as x=←− a ba for positive braids aand b, where ais nontrivial (see the equivalent definition 3.1). Palindromic-free braids will be crucial to show our main results. The above Lemma implies the following. Corollary 2.3. Let ube a positive braid with `(x) = m. Then `(ε(x)x)≤2m. If moreover uis palindromic-free and m > 1, then `(ε(x)x) = 2m. Proof. Recall that ε(x)=(←− x)−1. Since the canonical length of a braid is preserved under reversing (by symmetry of the relations in Bn) and also under taking inverses (by [6]), it follows that `(ε(x)) = m. Multiplying two braids of canonical length myields a braid of canonical length at most 2m, hence `(ε(x)x)≤2m. If uis palindromic-free and m > 1 we have the equality, as if we had `(ε(x)x)< 2m, then by setting r=m−1 and k= 1, we would have `(ε(x)x)≤2r+ 1, which by Lemma 2.2 implies that xis not palindromic-free.  3. ε-twisted conjugacy and palindromic-free braids Due to Theorem 1.3, the twisted conjugacy problem in Bnwill easily reduce to the ε-twisted conjugacy problem, namely given two braids u, v ∈Bndecide whether there exists another one w∈Bnsuch that v= (ε(w))−1uw. This problem has a very particular nature because (ε(w))−1=←− w, i.e. ε-twisted conjugating uby wamounts to multiply uon the right by wand on the left by ←− w,v=←− w uw. Let us concentrate on this case, where the twisting is given by ε. 8 JUAN GONZ ´ ALEZ-MENESES AND ENRIC VENTURA Note that the ε-twisted conjugation of a positive braid by a positive braid yields a positive braid. Also, note that, for any braid x∈Bnand any generator σi,xand σixσiare ε-twisted conjugated. Imposing positivity, this yields to the following definition: Definition 3.1. A positive braid xis said to be palindromic-free if σ−1 ixσ−1 i is not positive, for every i= 1, . . . , n −1. In other words, if xis a positive, palindromic-free braid and σi4x, that is, x=σiyfor some positive y, then y6<σi. However, notice that even if xis palindromic-free, one may have simultaneously σi4xand x<σifor some i. For instance if x=σi, or if x=σiσjwith |i−j|⩾2. Proposition 3.2. Every braid x∈Bnis ε-twisted conjugated to some positive, palindromic-free braid y. Proof. It is well known that for every braid x∈Bn, the braid x∆pis positive for pbig enough. Since ←− ∆ is positive (actually ←− ∆ = ∆), it follows that ←− ∆px∆p is positive for some pbig enough. Hence xis ε-twisted conjugated to a positive braid z. If zis not palindromic-free, there will exist a letter σisuch that z=σiz0σi for some positive braid z0whose word length is smaller than that of z. And, since ←− σi=σi,zis ε-twisted conjugated to z0. Repeating this process, as the word length of the resulting braid decreases at each step, one finally obtains a palindromic-free positive braid ε-twisted conjugated to z, thus to x. By the above argument, every positive braid xhas the form x=←− c yc for some positive, palindromic-free braid y. We remark that the element yis not unique. For instance, if x=σ2σ1σ2=σ1σ2σ1, then ycould be equal to either σ1or σ2. Another example is x=σ3σ2σ1σ2σ3=σ3σ1σ2σ1σ3=σ1σ2σ3σ2σ1, so ycould be equal, in this case, to either σ1or σ2or σ3. Recall that we are trying to find an algorithm to solve the ε-twisted conjugacy problem in Bn. After the above discussion, one may think that a possible solution could be to compute the set of positive, palindromic-free braids, ε-twisted conjugated to a given one. Clearly, two braids uand vare ε-twisted conjugated if and only if their corresponding sets coincide. Unfortunately, this attempt does not work because the mentioned set is not always finite, as one can see in the following example. Example 3.3. The set {σn 3σ2σ3σ4σ5σ1σ2σ3σ4σn 1;n≥0} ⊂ B6is an infinite family of positive, palindromic-free braids, which are pairwise ε-twisted conjugated. TWISTED CONJUGACY IN BRAID GROUPS 9 Proof. We will show that for every n≥0 one has: σn 5(σn 3σ2σ3σ4σ5σ1σ2σ3σ4σn 1)σn 5= (σ1σ3)nσ2σ3σ4σ5σ1σ2σ3σ4(σ3σ1)n. So all braids in the above family are ε-twisted conjugated to σ2σ3σ4σ5σ1σ2σ3σ4, and so to each other. To see this, first notice that σ5(σ2σ3σ4σ5σ1σ2σ3σ4)=(σ2σ3)σ5(σ4σ5σ1σ2σ3σ4) = (σ2σ3σ4σ5)σ4(σ1σ2σ3σ4) = (σ2σ3σ4σ5σ1σ2)σ4(σ3σ4) = (σ2σ3σ4σ5σ1σ2σ3σ4)σ3. On the other hand, by commutativity relations, σ2σ3σ4σ5σ1σ2σ3σ4=σ2σ1σ3σ2σ4σ3σ5σ4, hence σ1(σ2σ3σ4σ5σ1σ2σ3σ4) = σ1(σ2σ1σ3σ2σ4σ3σ5σ4) = (σ2σ1)σ2(σ3σ2σ4σ3σ5σ4) = (σ2σ1σ3σ2)σ3(σ4σ3σ5σ4) = (σ2σ1σ3σ2σ4σ3)σ4(σ5σ4) = (σ2σ1σ3σ2σ4σ3σ5σ4)σ5 = (σ2σ3σ4σ5σ1σ2σ3σ4)σ5. Therefore, as σ1,σ3and σ5commute, one has σn 5σn 3(σ2σ3σ4σ5σ1σ2σ3σ4)σn 1σn 5=σn 3(σ2σ3σ4σ5σ1σ2σ3σ4)σn 3σn 1σn 5 =σn 1σn 3(σ2σ3σ4σ5σ1σ2σ3σ4)σn 3σn 1, and the claim follows. It just remains to show that every element in the above family is palindromicfree. This could be easily done by using the standard topological representation of braids as collections of strands in R3, but we will show it algebraically. If n= 0, we have the braid α0=σ2σ3σ4σ5σ1σ2σ3σ4. We recall that the monoid B+ 6of positive braids embeds in B6, so we just need to use positive relations from the standard presentation (1) to determine which generators are prefixes or suffixes of α0. But notice that in the above word, no matter how many commutativity relations we apply, we can never obtain a subword of the form σiσjσi, because between two appearances of the letter σione always has both σi−1and σi+1. Hence, only commutativity relations can be applied, and it follows that this braid can only start with σ2, and can only end with σ4, thus it is palindromic-free. 16 JUAN GONZ ´ ALEZ-MENESES AND ENRIC VENTURA `(u) = `(v). Then there is a chain u=u0, u1, . . . , uk=vof positive, palindromicfree braids, with canonical length `(ui) = rfor all i, such that ui−1is simply ε-twisted conjugated to ui, for i= 1, . . . , k. Corollary 4.8. There exists an algorithm to compute MP F (x)for any given braid x∈Bn. Proof. If x= 1 then MPF(x) = {1}. So, let us assume x6= 1. First of all, compute a positive, palindromic-free, ε-twisted conjugate of x, say y, as it is explained in Proposition 3.2. Let r=`(y)⩾1, and let S={y} ⊂ Bn. Now, consider the following operation, which will have to be subsequently applied until all elements in Shave been processed: Choose z∈Swhich has not been processed, compute all positive palindromic-free elements which are simply ε-twisted conjugated to zand have canonical length less than or equal to r(this is clearly a finite, computable set), and then do the following: 1) if one of them, say z0, has length less than r, kill the whole process, reset y=z0,S={z0},r=`(z0)and start the algorithm again; 2) otherwise, add to Sall the computed elements (which have canonical length exactly equal to r), and mark zas processed. At each application of such operation, either the set Sgets restarted and rstrictly decreased, or the set Sgets increased by the addition of the new elements computed (some of which could already be present in the former S). But r⩾1 can only decrease a finite number of times, and |S|can only increase a finite number of times, since the number of braids with infimum zero and given canonical length is finite (recall that palindromic-free elements have infimum zero). Hence, after a finite number of applications of the previous operation (running over all elements z∈S), we shall get a set S6=∅closed under this operation, i.e. such that when applying that operation to any z∈Sthe set neither gets restarted nor gets increased (that is, all the elements computed are already present in S). At this time, Theorem 4.6 implies that the canonical length of the elements in S(which is constant) is the smallest possible among all positive palindromic-free braids which are ε-twisted conjugated to x. That is, S⊆MPF(x). Now, let u∈MP F (x). Choosing an arbitrary v∈S, Corollary 4.7 tells us that uand vare connected by a chain of positive, palindromic-free braids of minimal canonical length, each simply ε-twisted conjugated to the following one. Hence, by construction of S, we have u∈S. Therefore, S=MP F (x).  Theorem 4.9. The twisted conjugacy problem is solvable in the braid group Bn. TWISTED CONJUGACY IN BRAID GROUPS 17 Proof. Suppose we are given an automorphism ϕ:Bn→Bn(by the images of the generators), and two braids u, v ∈Bn. We have to decide whether there exists x∈Bnsuch that v= (ϕ(x))−1ux, and in the positive case compute such an x. By Theorem 1.3, either ϕis a conjugation (ϕ=γwfor some w∈Bn), or it is ε followed by a conjugation (ϕ=γwεfor some w∈Bn). We can clearly make this decision effective, and compute such a w. Indeed, in order to check whether ϕ= γw, we need to find some braid wsuch that w−1σiw=ϕ(σi) for i= 1, . . . , n −1. This is an instance of the so-called multiple simultaneous conjugacy problem in Bn, and algorithms to solve it (and to find such w) can be found in [12, 11]. On the other hand, checking whether ϕ=γwεand finding such wreduces to solving another instance of the multiple simultaneous conjugacy problem in Bn: namely, it amounts to find wsuch that w−1σ−1 iw=ϕ(σi) for i= 1, . . . , n −1. (Alternatively, in our specific situation, we can make the following conceptually much easier brute force algorithm: knowing, by Theorem 1.3, that there exists w∈Bnsuch that either w−1σiw=ϕ(σi) for i= 1, . . . , n−1, or w−1σ−1 iw=ϕ(σi) for i= 1, . . . , n−1, one can always enumerate all words w∈Bnand keep checking both conditions until finding the good one with the correct w.) We can therefore assume that wis known, and that ϕis equal either to γwor to γwε. In the first case ϕ(x) = w−1xw, and the equation v= (ϕ(x))−1ux is equivalent to wv =x−1(wu)x. Deciding the existence of such an xand finding it, is just an instance of the standard conjugacy problem in Bn(applied to wv and wu), which is well-known to be solvable, see Theorem 1.2. In the second case, ϕ(x) = w−1ε(x)w, and the equation v= (ϕ(x))−1ux is equivalent to wv = (ε(x))−1(wu)x=←− x(wu)x. Deciding the existence of such an xand finding it, is an instance of the ε-twisted conjugacy problem in Bn(applied to wv and wu), which can be solved by computing the sets MPF(wu) and MP F (wv) (see Corollary 4.8) and checking whether they coincide or not (meaning that wu and wv are or are not ε-twisted conjugated, respectively). Notice that, during the computations of MPF(wu) and MPF (wv), we can keep track of a ε-twisted conjugating element at each step, so that we can explicitly find a value for xin the case it exists. We remark that the full computation of the sets MP F (wu) and MPF (wv) will usually not be necessary. We can start the construction of both sets simultaneously, and kill the whole process giving a positive answer, as soon as we find an element zin common in both sets (since, in this case, both wu and wv are ε-twisted conjugated to z, an so to each other).  5. The conjugacy problem for some extensions of Bn. Theorem 5.1. Every finitely generated subgroup A⩽Aut(Bn)is orbit decidable. 18 JUAN GONZ ´ ALEZ-MENESES AND ENRIC VENTURA Proof. Let ϕ1, . . . , ϕm∈Aut(Bn) be given, and consider A=hϕ1, . . . , ϕmi⩽ Aut(Bn). For every i= 1, . . . , m, compute wi∈Bnand i= 0,1 such that ϕi=γwiεi i(see the first part of the proof of Theorem 4.9). Given two braids u, v ∈Bnwe have to decide whether or not vis conjugated to α(u) for some α∈A. If i= 0 for every i, then A⩽Inn(Bn) and so, the set {α(u)|α∈A}is a certain collection of conjugates of u. In this case, our problem just consists on deciding whether or not vis conjugated to u. This is doable by Theorem 1.2. Otherwise, the set {α(u)|α∈A}is a certain collection of conjugates of uand of ε(u). In this case, our problem just consists on deciding whether or not v is conjugated to either uor ε(u). This is again doable by two applications of Theorem 1.2.  The following theorem (and the interesting particular case expressed in the corollary below) are immediate consequences of Theorems 1.1, 4.9, and 5.1. Theorem 5.2. Let G=BnoHbe an extension of the braid group Bnby a finitely generated group Hsatisfying conditions (ii) and (iii) above (for instance, take Htorsion-free hyperbolic). Then, Ghas solvable conjugacy problem.  Corollary 5.3. For any ϕ1, . . . , ϕm∈Aut(Bn), the group hBn, t1, . . . , tm|t−1 iσti=ϕi(σ) (σ∈Bn)i has solvable conjugacy problem.  Acknowledgements The authors are grateful to the Centre de Recerca Matem`atica (CRM-Barcelona), since this research was initiated in the excellent research atmosphere during participation of both authors in one of the CRM workshops. The first named author acknowledges partial support from the MEC (Spain), Junta de Andaluc´ıa and FEDER, through projects MTM2007-66929, MTM2010-19355 and P09-FQM- 5112. The second author gratefully acknowledges partial support from the MEC (Spain) and the EFRD (EC) through project number MTM2008-01550. References [1] J. S. Birman, K. H. Ko, S. J. Lee, A new approach to the word and conjugacy problems in the braid groups. Adv. Math. 139(2) (1998), 322-353. [2] O. Bogopolski, A. Martino, E. Ventura, Orbit decidability and the conjugacy problem for some extensions of groups, Transactions of the AMS, 362(4) (2010), 2003–2036. [3] O. Bogopolski, A. Martino, O. Maslakova, E. Ventura, Free-by-cyclic groups have solvable conjugacy problem, Bulletin of the London Mathematical Society, 38(5) (2006), 787–794. TWISTED CONJUGACY IN BRAID GROUPS 19 [4] R. Charney, Geodesic automation and growth functions for Artin groups of finite type. Math. Ann., 301(2) (1995), 307324. [5] J.L. Dyer, E.K. Grossman, The automorphism groups of the braid groups, Amer. J. Math., 103(6) (1981), 1151–1169. [6] E. A. El-Rifai, H. R. Morton. Algorithms for positive braids, Quart. J. Math. Oxford Ser., (2) 45(180) (1994), 479-497. [7] N. Franco, J. Gonz´alez-Meneses, Conjugacy problem in braid groups and Garside groups. J. of Algebra, 266 (1) (2003), 112–132. [8] F. A. Garside, The braid group and other groups. Quart. J. Math. Oxford Ser., (2) 20 (1969), 235-254. [9] V. Gebhardt, A new approach to the conjugacy problem in Garside groups. J. Algebra, 292(1) (2005), 282-302. [10] V. Gebhardt, J. Gonz´alez-Meneses, The cyclic sliding operation in Garside groups. Math. Z., 265(1) (2010), 85–114. [11] J. Gonz´alez-Meneses, Improving an algorithm to solve multiple simultaneous conjugacy problems in braid groups. Contemp. Math., 372 (2005), 35–42. [12] S. J. Lee and E. Lee, Potential weaknesses of the commutator key agreement protocol based on braid groups. L.R. Knudsen (Ed.): EUROCRYPT 2002, LNCS 2332, pp. 14–28, 2002. [13] C.F. Miller III, On group-theoretic decision problems and their classification, Annals of Math., Studies 68, (1971). [14] K. Reidemeister, Automorphismen von homotopiekettenringen, Math. Ann., 112 (1936), 586–593. [15] Epstein et al. Word processing in groups. Jones and Bartlett Publishers, Boston, MA, 1992. Juan Gonz´ alez-Meneses Dep. ´ Algebra Universidad de Sevilla Apdo. 1160 41080 Sevilla, Spain E-mail address:[email protected] Enric Ventura Dept. Mat. Apl. III Universitat Polit` ecnica de Catalunya Manresa, Barcelona Catalunya E-mail address:[email protected]