On the conjugacy problem for cyclic extensions of free groups
a r
X i
v
:m
a
t h /
4
2
6
v
1
[
m
a
t h
.
G
R
]
4
F
e b
2
4
ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS VALERIJ BARDAKOV,LEONID BOKUT,AND ANDREI VESNIN Abstract.We study the conjugacy problem in cyclic extensions of free groups.It is shown that the conjugacy problem is solvable in split extensions of ?nitely generated free groups by virtually inner automor-phisms.An algorithm for construction of the unique representative (the conjugacy normal form)for each conjugacy class is given.1.Introduction One of fundamental problems in the combinatorial group theory is the conjugacy problem formulated by M.Dehn (1912)together with two other problems:the word problem and the isomorphism problem [33,Ch.2,§1].M.Dehn proved that the conjugacy problem is solvable in fundamental groups of closed orientable https://www.wendangku.net/doc/767130069.html,ter his method have been extended to the class of groups with small cancellation [33,Ch.5].Let us recall basic results about solvability of the conjugacy problem in some classes of groups.In [25]M.Gromov introduced a class of groups which are now referred to as word hyperbolic groups.Among examples of word hyperbolic groups are ?nite groups,free groups,small cancellation groups satisfying a metric small cancellation condition C ′(λ)with 0<λ≤1/6.In particular,the fundamen-tal group of an oriented surface of genus g >1is hyperbolic.It is known [13]that the conjugacy problem in word hyperbolic groups is solvable.Also it is solvable in such generalizations of word hyperbolic groups as relative hyper-bolic groups and semi-hyperbolic groups.At the same time,word hyperbolic
groups are contained in the class of bi-automatic groups,which are contained in the class of automatic groups itself.The class of automatic groups belong to the class of combable group.It is known that the conjugacy problem is solvable in bi-automatic groups.Recently,M.R.Bridson [12]demonstrated that there exist combable groups in which the conjugacy problem is unsolv-able.The question about solvability of the conjugacy problem in automatic groups is still open.
2BARDAKOV,BOKUT,AND VESNIN
We will interested in groups F n(t)=F n? t which are semi-direct pro-ducts of a free group F n and a cyclic group t ,where conjugation by t induces an automorphism?∈Aut(F n).In particular,if t is of in?nite order, then F n(t)is the mapping torus of F n corresponding to the automorphism ?and is denoted by
F n(?)= x1,x2,...,x n,t|t?1x i t=?(x i),i=1,2,...,n .
If t is of?nite order(which is divided by order of?)then there exists a homomorphism of F n(?)onto F n(t).
The study of groups F n(?)is also motivated by their relation with fun-damental groups of closed3-manifolds?bering over a circle(see[20]).
In[23]J.M.Gersten and J.R.Stallings asked about word hyperbolicity of
F n(?).It was shown by M.Bestvina and M.Feighn[5]and by P.Brinkmann
[15]that F n(?)is word hyperbolic if and only if?having no nontrivial periodic conjugacy classes(i.e.there no non-trivial element f of F n and non-zero integer k such that?k(f)is conjugated to f in F n).The solvability of the conjugacy problem for such groups follows from the solvability of the conjugacy problem in word hyperbolic groups.
We remark that some one-relator groups as well as some Artin groups can be presented as cyclic extensions of free groups(see discussions in Sec-tion2).The conjugacy problem in one-relator groups in still open.At the same time,it is solvable in one-relator groups with torsion.This result was announced by B.Newman[36].S.Pride[39]proved this fact for the case when the de?ning relation is of the form r n for n>2.Another proof of this fact was given by V.N.Bezverhnii[6]https://www.wendangku.net/doc/767130069.html,rsen[32]proved that the conjugacy problem is solvable in one-relator groups with non-trivial center. For some classes of one-relator groups the conjugacy problem was solved by G.A.Gurevich[26,27]and A.A.Fridman[21].
It is known that the conjugacy problem is solvable in braid groups and knot groups[22,40,41].The solvability of the conjugacy problem in link groups seems still open.
Recall that the conjugacy problem is solvable in the Novikov group A p
1,p2 [38]if and only if the word problem is solvable in the corresponding Post
system P(A p
1,p2)[9],[10,Ch.7].
Surveys on the conjugacy problem in various classes of groups can be found in[28]and[37].The problem on solvability of the conjugacy problem in groups F n(?)was formulated also by I.Kapovich[29,Problem6.2].
It is known that the solvability of the conjugacy problem does not pre-serve under?nite extensions[24].Moreover,D.Collins and https://www.wendangku.net/doc/767130069.html,ler[16] constructed a group G containing a subgroup H of index two such that the conjugacy problem is solvable in H but not solvable in G.At the same paper they constructed a group with solvable conjugacy problem which contains a subgroup of index two with non-solvable conjugacy problem.
One of possible approaches to solve the conjugacy problem in groups F n(t) is investigation of the property to be conjugacy separable.
ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS3 A group G is said to be conjugacy separable if for any pair of non-conjugated elements of G there exists a homomorphism of G to a?nite group such that images of these elements are also non-conjugated.It was shown by A.I.Malcev[34],if a?nitely generated group is conjugacy separa-ble then the conjugacy problem in this group is solvable.Thus,the following problem aries naturally:
Problem.
4BARDAKOV,BOKUT,AND VESNIN
Applying,if necessary,Lemma11.8from[33,ch.5]we can assume that the exponent sum of t in r is equal to zero.We will use the Magnus–Moldavanskii method to represent G as HNN-extension.Let us de?ne new generators a i=t?i at i,i∈Z and let r′be the presentation of the word r written in these generators.We write a i∈r′if a i or a?1i is a subword of r′, and denoteμ=min{i|a i∈r′}andν=max{i|a i∈r′}.Let us de?ne
H= a i,μ≤i≤ν|r′=1 ,
A= a i,μ≤i<ν ,
B= a i,μ Then we can write G= H,t|t?1At=B,? ,where isomorphism?acts as the following ?(a i)=a i+1,i=μ,μ+1,...,ν?1. If aνappears in r′only once(with degree+1or?1),then using r′we can express aνvia other generators and eliminate it from the generating system for H.Thus H is a free generated group which coincides with A.In this case G= H,t|t?1Ht=B,? is said to be an ascending HNN-extension of H.If,moreover,B=H,then ?is an automorphism of H,and G=F n(?),where n=ν?μ?1,is a cyclic extension of a free group. Analogously,if aμcan be expressed from r′via other generators,we get that H coincides with B. As a noticeable example,let us consider2-generated Artin group: A(m)= x,y|w m(x,y)=w m(y,x) , where m≥3is integer and w m(u,v)= (uv)n,if m=2n, (uv)n u,if m=2n+1. We recall that A(2n+1)is the fundamental group of the(2n+1,2)-torus knot complement in the3-sphere and A(2n)is the fundamental group of the (2n,2)-torus2-component link complement in the3-sphere.These knots and links arise as closures of2-strand braids. Changing generators of A(m)in the same way as in[11](where the Gr¨o bner–Shirshov bases for these groups were constructed)we will get the following result. Proposition 2.1.Any2-generated Artin group is a split extension of a free group of?nite rank and a cyclic group generated by a virtually inner automorphism. Proof.Let us consider the group A(2n)= x,y|(xy)n=(yx)n ,n≥2, Denoting t=x and y i=t i yt?i,where i=0,1,...,n?1,we get the following presentation: A(2n)=F n(?)= y0,y1,...,y n?1,t|t?1y i t=?(y i),i=0,...,n?1 , ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS5 where F n is the free group generated by y0,...,y n?1and?is de?ned by: ?(y0)=y0y1···y n?2y n?1y?1n?2···y?11y?10, ?(y i)=y i?1,i=1,2,...,n?1. It is easy to check that the element?=y0y1···y n?1is such that?(?)=?(see also[11])and the automorpihsm?n acts as the following: ?n(y i)=?y i??1,i=0,1,...,n?1, so?is an virtually inner automorphism of F n. Let us consider the group A(2n+1)= x,y|(xy)n x=(yx)n y .Denoting t=x,z=yx?1=yt?1,and z i=t i zt?i,where i=0,1,...,2n?1,we get the following presentation A(2n+1)=F2n(ψ)= z0,...,z2n?1,t|t?1z i t=ψ(z i),i=0,...,2n?1 , where F2n is the free group generated by z0,z1,...,z2n?1andψis de?ned by: ψ(z0)=z0z2···z2n?2z?12n?1z?12n?3···z?13z?11, ψ(z i)=z i?1,i=1,...,2n?1. It is easy to check that the element Σ=z0z2···z2n?2(z0z1···z2n?1)?1z1z3···z2n?1 is such thatψ(Σ)=Σ(see also[11])and the automorphismψ2(2n+1)acts as the following: ψ2(2n+1)(z i)=Σz iΣ?1,i=0,1,...,2n?1, so,ψis an virtually inner automorphism of F n. We remark that the conjugacy problem in2-generator Artin groups is solvable since these groups are Artin groups of?nite type. 3.Finitely generated free groups and virtually inner automorphisms Let F n= x1,x2,...,x n be the free group of rank n≥2with words from the alphabet X={x±11,...,x±1n}.In some cases,we will need to distinguish words which represent the same element of the group.We will write U=V if two words(or two elements of the group)are equal as elements of the group, and U≡V if two words are equal graphically.Denote by|V|the length of a word V in the alphabet X.A word V is said to be reduced if it contains no part xx?1,x∈X.A reduced word V de?nes a non-identity element if and only if|V|≥1.A reduced word obtained by reducing of an original word will be referred to as its reduction.By||V||we will denote the length of the reduction of a word V.Further,a reduced word V=xε1i 1xε2i 2 ···xεn i n , whereεi=±1,i=1,...,n,is said to be cyclically reduced if i1=i n or if i1=i n thenε1=?εn.Clearly,every element of a free group is conjugated 6BARDAKOV,BOKUT,AND VESNIN to an element given by a cyclically reduced word referred to as its cyclic reduction. We will use standard notations Aut(F n)and Inn(F n)for the group of automorphisms and the group of inner automorphisms of F n,respectively. An automorphism?∈Aut(F n)is said to be virtually inner if?m∈Inn(F n) for some positive integer m. In particular,any automorphism?of?nite order is virtually inner. Denote by F n(t)=F n? t the semi-direct product,where the genera-tor t of the cyclic group t is such that the conjugation by t induces an automorphism?,i.e.t?1ft=?(f)for any f∈F n.Remark that F n?F n(t). We will show that the following property holds. Theorem3.1.If?is a virtually inner automorphism of a free group F n, n≥2,then the conjugacy problem is solvable for F n(t). To prove this result,we will?nd an unique representative for each conju-gacy class. Any element v∈F n(t)can be presented in the form t?V where?∈Z if t has in?nite order,and0≤?<|t|if t has?nite order|t|;V is a word of the alphabet X(we will also say that V is a X-part of v).Moreover,if V is reduced then such a presentation of v is unique. Let?∈Aut(F n)be a virtually inner automorphism such thatψ=?m is an inner automorphism of F n.Without loss of generality we can assume that m is taken the smallest positive integer having such a property.There exists a reduced word?∈F n such that ?m(f)=??1f? for any f∈F n.It is easy to check(see also[3,Lemma2])that following properties hold. Lemma3.1.(1)Automorphisms?andψcommute. (2)If k=mq+r,where q∈Z and0≤r≤m?1,then for any word U of the alphabet X we have ?k(U)=?r(??q U?q). (3)?(?)=?. Let us de?ne a linear order“<”on the set of irreducible words in the alphabet X.Assume that elements of X are ordered in the following way: x1 We write U A reduced word V∈F n is said to be?-reduced if|V|≤||??k V?k||for all k∈Z.Obviously,if V is cyclically reduced,then the length of any word conjugated to V is not less than the length of V,so V is?-reduced. ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS7 Lemma3.2.Suppose that?is cyclically reduced.A reduced word V∈F n is?-reduced if|V|≤||??εV?ε||forε=±1. Proof.See[3,Lemma3]. If?is cyclically reduced,Lemma3.2gives the?nite algorithm to?nd for a given reduced word V a?-reduced word V?conjugated to V by some power of?.Indeed,it is enough to repeat conjugations of V by?ε,ε=±1, few times.If the length of the obtained word is less than the length of the previous word,we will conjugate again.If not,then the obtained word is a ?-reduced word V?conjugated to V.Such a construction of a?-reduced word V?conjugated to V by some power of?will be referred to as a?-reduction. We remark that if?is not cyclically reduced,then the analog of Lemma3.2 does not hold.It is clear from the following example. Example.Let U,W,Σ∈F n be nonempty reduced words such that for an integer|k|>1words?≡U?1W?1ΣW U and V≡U?1W?1Σk W U2are reduced.If k>1,we get ??1V?=U?1W?1Σk?1W UW?1ΣW U, ??2V?2=U?1W?1Σk?2W UW?1Σ2W U, ··· ??(k?1)V?k?1=U?1W?1ΣW UW?1Σk?1W U, ??k V?k=W?1Σk W U. It is easy to see that |V|<||??1V?||=||??2V?2||=...=||??(k?1)V?k?1||, but||??k V?k||<|V|. If k Lemma3.3.Suppose?is not cyclically reduced.Let V be a reduced word such that|V|≤||??εV?ε||,ε=±1.Then one of the following cases holds: (1)V is?-reduced. (2)?≡U?11U?12??111?2?11U2U1and V≡U?11U?12W U2U1,for some re-duced?11,?2,U1,U2and cyclically reduced W for which there exist integers k,|k|>1,and m≥0and reducedΦ,W0such that either a)U?12??111??k2?11≡ΦW?m and W≡Φ?1W0, or b)??111?k2?11U2≡W?mΦand W≡W0Φ?1. In addition,Φdoes not end by W?1,and W0is either nonempty or W0≡1 with U?11Φ?1U1be reduced. In case(2)V?=??k V?k is?-reduced word conjugated to V.Moreover, case(2)describe all possible cases when|V|≤||??εV?ε||,ε=±1,but ||??k V?k||<|V|for some|k|>1. Proof.See[3,Lemma4]. 8BARDAKOV,BOKUT,AND VESNIN If?is not cyclically reduced,Lemma3.3gives the?nite algorithm to ?nd for a given reduced word V a?-reduced word V?conjugated to V by some power of?.If?and V are of the form represented in case(2)of Lemma3.3,then we de?ne V?=??k V?k.In this case we say that V?is a?-reduction of V.If?and V are others,then we follow the same steps as described after Lemma3.2. Remark that V?is not uniquely determined by V(see[3,Proposition2]). 4.Constructing of conjugated normal form Now we will study?-reduced elements of the group F n(t).A word v= t?V∈F n(t),?∈Z,V∈F n,is said to be?-reduced if V is?-reduced. In virtue of Lemma3.1(3),the conjugation of v=t?V by any power?m means the conjugation of V by?m,i.e. ??m v?m=??m t?V?m=t?(t????m t?)V?m =t???(??m)V?m=t???m V?m. For any integer k we will denote by V[k]a reduction of t?k V t k=?k(V). Remark that t?m V[l]t m=V[l+m]and that V[0]=V if V is a reduced word. If length of a reduced word V in the alphabet X is bigger than1then it can be presented as a product V≡V′V′′of two nonempty reduced words. The word V′will be referred to as an initial part of V and V′′will be referred as a?nal part of V.Denote by I(V)the set of all initial parts of V and by F(V)the set of all?nal parts of V. Consider v∈F n(t)and?x its presentation v≡t?V,?∈Z,where V is re-duced word in the alphabet X.Conjugation by t?induces an automorphism ψ=??of the free group F n. For a reduced word V≡V′V′′in the alphabet X with V′∈I(V),V′′∈F(V)we say that a word V′′ [?] V′is a cyclicψ-shift of a?nal part of V and a word V′′V′ [??]is a cyclicψ-shift of an initial part of V.Remark that these elements can be obtained by a conjugation of v.Indeed,conjugating v by (V′′)?1we will get V′′v(V′′)?1=t?t??V′′t?V′=t?V′′[?]V′, and conjugating v by(V′)[??]we will get (V′[??])?1vV′[?]=t?t??(V′[??])?1t?V′V′′V′[??]=t?V′′V′[??]. If|V′|=1,i.e.V′=xεi,ε=±1,then the corresponding cyclicψ-shift will be referred to as a cyclicψ-shift of the initial letter.If|V′′|=1then the corresponding cyclicψ-shift will be referred to as a cyclicψ-shift of the?nal letter. A reduced word V will be referred to as a cyclicallyψ-reduced if there doesn’t exist a cyclicψ-shift of its?nal part and there doesn’t exist a cyclic ψ-shift of its initial part which decreases length of V.Obviously,applying ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS9 cyclicψ-shifts of?nal(or initial)parts to a given word V we will get a cyclicallyψ-reduced word conjugated to V. Now let us construct conjugating normal form for an element v=t?V. Without loss of generality,we can assume that V is cyclicallyψ-reduced and ?-reduced.For a given V let us construct a set of words V?which contains V and such elements which are conjugated to V by elements of the group ? and are?-reduced.All of them have the same length as V.By Lemma3.2 and Lemma3.3the set V?is?nite.Applying to elements of V?cyclicψ-shifts of all initial parts and all?nal parts,we will construct the set(V?)ψ. Applying to obtained words?-reducing,we will get a set((V?)ψ)?each element of which is?-reduced.Consider the subset of((V?)ψ)?consisting of cyclicallyψ-reduced words.Multiplying each of obtained words on left by t?we will get a set of words from F n(t).Let us denote the obtained set by D0(v). Remark that in the free group the set of words obtained from a given word V by cyclic shifts is?nite.But the set of words obtained from a word v∈F n(t)by cyclicψ-shifts can be in?nite if t has in?nite order.Indeed,it is clear from following relations ψk?1(V)ψk?2(V)···ψ(V)V v V?1ψ(V?1)···ψk?2(V?1)ψk?1(V?1) =t?ψk(V),for k>0; ψk(V?1)ψk+1(V?1)···ψ?1(V?1)vψ?1(V)···ψk+1(V)ψk(V) =t?ψk(V),for k<0, that the element v≡t?V is conjugated to t?ψk(V)for any integer k.More-over,the conjugation can be done by an element of the free group F n. For each integer k we de?ne a set D k(v)=D0(t?ψk(V)),and D(v)=∪k∈Z D k(v).Let us verify that D(v)is?nite. Lemma4.1.For integer?and m as above denote d=gcd(m,?).Then D(v)=∪k∈{0,d,...,m?d}D0(t??k(V)). Proof.For any integer k we haveψk(V)=??k(V).Let r,0≤r ??k(V)=??q?r(V)?q. Let?=?1d and m=m1d for some integer?1and m1.If k runs over the set Z then r runs over the set{0,d,2d,...,m?d}.Let us show that D k(v)=D0(t??r(V)),that will give the statement.Indeed,by the de?ni-tion,D k(v)=D0(t???q?r(V)?q).Denote U=V[r]=?r(V)and consider elements from D0(t??r(V)).By the de?nition,D0(t??r(V))consists of words whose X-parts are theψ-shiftsψ(U2)U1or U2ψ?1(U1),where U≡U1U2,to which?-reducing andψ-reducing are applied.To construct D k(v)we must pass from a word??q?r(V)?q to a?-reduced word,which,in a general case,can be di?erent from U=?r(V).But,according to the de?nition of 10BARDAKOV,BOKUT,AND VESNIN D0(v),the set of?-reduced words constructed from??q?r(V)?q coincides with the set of?-reduced words constructed from?r(V).So,corresponding sets of all cyclicψ-shifts of initial parts and of?nals parts also coincide. Therefore,D k(v)=D0(t??r(V)). Lemma4.2.The set D(v)has the following properties: (1)If u∈D(v)then D(u)=D(v); (2)Let elements v≡t?V and w≡t?W be conjugated by an element of the group H= F n,t m .Suppose that words V and W are cyclicallyψ-reduced and?-reduced.Then D(v)=D(w). Proof.Since D(v)consists of elements conjugated by elements of H,item (2),obviously,implies(1).Let us prove(2).Let u≡t ms U be a conjugating element,where s is some integer and U is a reduced word.By the assump-tion,w=u?1vu,i.e.we have the following equality in the free group F n: (1)W=U?1 [?] ??s V?s U. Since t???s=??s t?,denoting U′=?s U we get U?1 [?]??s=(U′ [?] )?1,i.e. W=U?1 [?]??s V?s U=(U′ [?] )?1V U′.Therefore,without loss of generality, we can assume that in(1)the exponent s is equal to zero.Since W is cyclicallyψ-reduced,the product U?1 [?] V U contains cancellations.Moreover, these cancellations are either in the product U?1 [?]V or in the product V U, but not in the both. Case1. Suppose that there are cancellations in the product U?1 [?] V. Then U?1 [?] must be cancelled wholly,i.e.V≡U[?]V1.Then W=U?1 [?]V U≡U?1 [?] (U[?]V1)U=V1U and w≡t?V1U is obtained from v≡t?U[?]V1by the shift of the initial part U[?].Indeed,according to the above described procedure,we need to conjugate v by U=U[0]: U?1 [0]vU[0]=U?1 [0] (t?U[?]V1)U[0]=t?U?1 [?] U[?]V1U[0]=t?V1U=w. Therefore,D(v)=D(w). Case1(b). ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS11 Case2. Suppose that V is cancelling wholly in the product V U and after that there are cancellations of letters of the remaining part of U with letters of U?1 [?].Then we can represent U≡V?1U1,therefore U?1 [?] =U?1 1[?] V[?] and (2)U?1 [?]V U=U?1 1[?] V[?]V V?1U1=U?1 1[?] V[?]U1. If U1is cancelling wholly with V[?]then V[?]≡V2U?11and U?1 1[?]V[?]U1≡U?1 1[?] V2U?11U1=U?1 1[?] V2=W. If word V[?]in the product V[?]U1is cancelling wholly,then we will use induction by length of U. Remark that W arises in the process of the construction of D1(v).Indeed, D1(v)=D0(t?V[?])=D0(t?V2U?11) and W is obtained from V2U?11by the cyclicψ-shift of the?nal part. Case2(b). D(v)=∪0≤k Obviously,this set is?nite.Let D(v).Such v are conjugated in F n(t).To show uniqueness of D(w)= 12BARDAKOV,BOKUT,AND VESNIN =U?1t?mq t?(t?r V t r)t mq U=U?1t?mq(t?r vt r)t mq U, i.e.w is conjugated to t?r vt r by an element from the group F n,t m .By the construction,D(t?r vt r)? D(w)= D(v)as in Section4.From this set we choose words of minimal length.Then,from such words,choose the conjugacy normal form u and u= Let G=F?M,where M?Aut(F n)is such that the image of M in the group Out(F n)=Aut(F n)/Inn(F n)under the natural homomor-phism is?nite group.Does the conjugacy problem solvable in G? Let us show that the answer on this question is a?rmative if M is?nite group. Proposition 4.1.Let G=F n?M,where M is a?nite subgroup of Aut(F n).Then the conjugacy problem is solvable for G. Proof.Let us suppose that M has k elements: M={α0=e,α1,...,αk}. We order these elements in the following way: α0<α1<...<αk. Consider elements v=αi V and u=αj U from G,where V and U are reduced words from F n.Obviously,if elementsαi andαj are not conjugated in M, then elements v and u are not conjugated in G.So,we can suppose that αi andαj are conjugated in https://www.wendangku.net/doc/767130069.html,ing,if necessary,a conjugation,we can assume that v=?V and u=?U,where?∈M,and?is taken the smallest representative of the class of conjugated elements that containsαi andαj. ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS13 Further,as in the proof of Theorem3.1,we construct sets D0(v)and D0(u). In addition,?≡1.De?ne D(v)= k i=0D0(vαi),D(u)= k i=0 D0(uαi). For each of these sets we choose a word that has the smallest X-part in respect to the above de?ned ordering.Such a word will be the conjugated normal form of the corresponding word.Therefore,if obtained words coin- cide,then elements u and v are conjugated in G.If they are di?erent,then elements u and v are not conjugated in G. 5.Countably generated free group and shifting automorphism Let F∞= ...,x?1,x0,x1,x2,... be the free group with countably in?-nite number of generators with words from the alphabet X={...,x±1?1,x±10, x±11,x±12,...}.Consider an automorphism?:F∞→F∞acting by shifting generators:?(x i)=x i?1,where i∈Z.We will call?the shifting auto- morphism.Denote by F∞(?)=F∞? t the split extension,where t is the generator of the cyclic group t such that the conjugation by t induces the automorphism?,i.e.t?1x i t=x i?1for i∈Z.Remark that F∞?F∞(?). De?ning relations for F∞(?)can be written as following: x i t=tx i?1,x i t?1=t?1x i+1 x?1i t=tx?1i?1,x?1i t?1=t?1x?1i+1, where i∈https://www.wendangku.net/doc/767130069.html,ing the same arguments as in the proof of Lemma2.1from [11],we remark that these relations together with trivial relations form the Gr¨o bner–Shirshov basis for F∞(?). In the present section we will show that the following property holds. Theorem5.1.Ifφis the shift automorphism of the free group F∞then the conjugacy problem is solvable for F∞(?). Any element of F∞(?)is uniquely presented in the form t m V,where m∈Z and V∈F∞is a reduced word.To prove the decidability of the conjugacy problem for the group F∞(?)we will show that for each class of conjugated elements we can choose the unique representative(the conjugacy normal form),and that two elements from F∞(?)are conjugated if and only if the representatives of corresponding classes coincide. For any integer m let?m be an automorphism of the group F∞de?ned by ?m(x i)=t?m x i t m=x i?m. By V[m]we denote a free reduction of the word?m(V).A word W is said to be?m-conjugated to a word V by a word U?1if W≡?m(U)V U?1=U[m]V U?1. Obviously,two words t m V and t m W from F∞(?)are conjugated by an element of F∞if and only if corresponding words V and W from F∞are 14BARDAKOV,BOKUT,AND VESNIN ?m–conjugated.A reduced word V is said to be cyclically?m-reduced if it can not be presented in the form V≡ψm(U)V0U?1, for non-trivial U∈F∞. Lemma5.1.Each element v∈F∞(?),presented by a word t m V,is conju-gated to a word t m V0,where V0is cyclically?m-reduced. Proof.If V is not cyclically?m-reduced,then v can be presented in the form v≡t m?m(U)V0U?1, where V0is cyclically?m-reduced Conjugating this word by U we get U?1vU≡U?1(t m?m(U)V0U?1)U=U?1t m t?m Ut m V0=t m V0. A word v≡t m V∈F∞(?)is said to be cyclically?m-reduced if the word V∈F∞is cyclically?m-reduced. Suppose that a word V∈F∞has some x k as the?nal letter,i.e.V≡Ux k.Let us de?ne the cyclic?m-shift of the?nal letter,denoted byτm,as following: τm:V≡Ux k→?m(x k)V x?1 k ≡?m(x k)(Ux k)x?1 k =x k?m U. Obviously,if v=t m V then v′=t mτm(V)is conjugated to v by x?1j: x j vx?1j=x j(t m Ux j)x?1j=t m x j t?m t m U=t m x j?m U=v′. Let us de?ne a linear order”<”on the set of reduced words of the alphabet X.Assume that elements of X are ordered in the following way: ... We write U Remark the following obvious property: Lemma5.2.Let words U1,U2,...,U p representing elements of F∞be or-dered in the following way: U1 and m be an integer.Then the following ordering holds ?m(U1) that can be also written as U1[m] ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS15 For a?m-reduced word v≡t m V∈F∞(?),with|V|=n,de?ne a set D(v)={t mτi m(V)|i=0,1,...,n?1}. Let us choose a word from D(v),say t m V0,such that its X-part V0is smallest in respect to above de?ned lexicographical order.Suppose that V0starts from a letter xεk,ε=±1.Then the word?k(V0)starts from the letter xε0. For such chosen V0and k,the word Suppose that there are no cancellations.Then U w U?1=U t k U?1 [k] V[?]=t k V[?]. Thus,for any m,the cyclic?m-shifts of UwU?1can be obtained from the cyclic?m-shift of v using conjugation by t??.Therefore,a conjugate normal form of w coincides with a conjugate normal form of v. Let us assume that below w≡t k W is cyclically?https://www.wendangku.net/doc/767130069.html,ing in-duction by length|U|of U we will show that W can be obtained from V by cyclic?k–shift and conjugation by some degree of t.Then there must be some cancellations in the word U?1 [k]V[?]U. Case2. Suppose that there are cancellations in the product U?1 [k] V[?],i.e. V[?]≡V′[?]V′′[?],U?1 [k] =(U′)?1(V′[?])?1,U[k]=V′[?]U′. 16BARDAKOV,BOKUT,AND VESNIN Then U?1 [k] V[?]U≡(U′)?1(V′[?])?1(V′[?]V′′[?])V′[??k]U′[?k]=(U′)?1V′′[?]V′[??k]U′[?k], and there are no cancellations in the product V[?]U.We see that the element V′′[?]V′ [??k] can be obtained from V′V′′by a cyclic k–shift,i.e. V′′v(V′′)?1=t k V′′[k]V′, and a conjugation by t??+k.Since|U′|<|U|,the induction assumption can be applied,and we get the statement. As a consequence of the above considerations we get the statement of Theorem5.1. References [1]S.I.Adyan,V.G.Durnev,Decision problems for groups and semigroups,Uspekhi Mat.Nauk55(2000),no.2(332),3–94(Russian);translated in Russ.Math.Surveys 55(2000),no.2,207–296. [2]K.Appel,On Artin groups and Coxeter groups of large type,in:Contributions in group theory,50–78,Contemp.Math.33,Amer.Math.Soc.,Providence,RI,1984. [3]V.Bardakov,L.Bokut,A.Vesnin,Twisted conjugacy in free groups and Makanin’s question,Seoul National University,2003,RIM-GARC Preprint Series03–12,19pp., aviliable from arXiv:math.GR/0401349. [4]K.Bencsath, B.Fine, A.M.Gaglione, A.Myasnikov,F.Roehl,G.Rosenberger, D.Spellman,Aspects of the theory of free groups,in:Algorithmic problems in groups and semigroups(Lincoln,NE,1998),51–90,Trends Math.,Birkha¨u ser Boston, Boston,MA,2000. [5]M.Bestvina,M.Feighn,A combination theorem for negatively curved groups,J.Di?. Geom.,35(1992),no.1,85–101;ibid.43(1996),no.4,783–788. [6]V.N.Bezverkhnii,Solution of the conjugacy problem for words in some classes of groups,Algorithmic problems in the theory of groups and semigroups,Tulsk.Gos. Ped.Inst.,Tula,1990,103–152(Russian). [7]V.N.Bezverkhnii,Solution of the conjugacy problem for words in Artin and Coxeter groups of large type,Algorithmic problems in the theory of groups and semigroups, Tulsk.Gos.Ped.Inst.,Tula,1986,21–61(Russian). [8]V.N.Bezverkhnii,I.V.Dobrynina,Solution of the conjugacy problem for words in Coxeter groups of large type,Chebyshev Sbornik,4(1)(2003),10–33(Russian). [9]L.A.Bokut,Degrees of unsolvability of the conjugacy problem for?nitely presented groups,Algebra i Logika7(1968),no.5,4–70;ibid7(1968),no.6,4–52.(Russian) [10]L.A.Bokut,G.P.Kukin,Algorithmic and combinatorial algebra,Mathematics and its Applications,255.Kluwer Academic Publishers Group,Dordrecht,1994. [11]L.Bokut,A.Vesnin,Gr¨o bner–Shirshov bases for some braid groups,17pp.to appear in Journal of Symbolic Computations,(2004). [12]M.R.Bridson,The conjugacy and isomorphism problems for combable groups,Math. Ann.327(2003),no.2,305–314. [13]M.R.Bridson,A.Hae?iger,Metric spaces of non-positive curvature,Grundl.Math. Wiss.,319,Springer-Verlag,Berlin–Heidelberg,1999. [14]E.Brieskorn,K.Saito,Artin-Gruppen und Coxeter-Gruppen,Invent.Math.17 (1972),245–271. [15]P.Brinkmann,Hyperbolic automorphisms of free groups,Geom.Funct.Anal.10 (2000),no.5,1071–1089. ON THE CONJUGACY PROBLEM FOR CYCLIC EXTENSIONS OF FREE GROUPS17 [16]D.Collins,https://www.wendangku.net/doc/767130069.html,ler III,The conjugasy problem and subgroups of?nite index,Proc. London Math.Soc.(3)34(1977),no.3,535–556. [17]M.Dehn,¨Uber unendichle diskontinuerliche Gruppen,Math.Ann.71(1912),116– 144. [18]J.L.Dyer,Separating conjugates in free-by-?nite groups,J.London Math.Soc.(2) 20(1979),no.2,215–221. [19]J.L.Dyer,Separating conjugates in amalgamated free products and HNN extensions, J.Austral.Math.Soc.,Ser A29(1980),no.1,35–51. [20]M.Feighn,M.Handel,Mapping tori of free group automorphisms are coherent,Ann. of Math.(2)149(1999),no.3,1061–1077. [21]A.A.Fridman,A solution of the conjugacy problem in a certain class of groups, in:Mathematical logic,theory of algorithms and theory of sets(dedicated to P.S. Novikov on the occasion of his seventieth birthday).Proc.Steklov Inst.Math.133 (1977),233–242,276. [22]F.A.Garside,The braid group and other groups,Quart.J.Math.Oxford Ser.(2)20 (1969),235–254. [23]S.M.Gersten,J.R.Stallings,Irreducible outer automorphisms of a free group,Proc. Amer.Math.Soc.,111(1991),no.2,309–314. [24]A.V.Goryaga,A.S.Kirkinskii,The decidability of the conjugacy problem cannot be transferred to?nite extensions of groups,Algebra i Logika14(4)(1975),393–406. (Russian) [25]M.Gromov,Hyperblic groups,in:Essays in Group Theory,Ed.S.M.Gersten,Math. Sci.Res.Inst.Publ.8,Springer,New-York,1987,75–263. [26]G.A.Gurevich,On the conjugacy problem for groups with one de?ning relation,Sov. Math.,Dokl.13(1972),1436–1439. [27]G.A.Gurevich,On the conjugacy problem for groups with a single de?ning relation, in:Mathematical logic,theory of algorithms and theory of sets(dedicated to P.S. Novikov on the occasion of his seventieth birthday).Proc.Steklov Inst.Math.133 (1977),108–120. [28]R.D.Hurwitz,A survey of the conjugacy problem,Contributions to group theory, 278–298,Contemp.Math.,33,Amer.Math.Soc.,Providence,RI,1984. [29]I.Kapovich,Mapping tori of endomorphisms of free groups,Comm.in Algebra28 (2000),no.6,2895–2917. [30]O.G.Kharlampovich,M.V.Sapir,Algoritmic problems in varieties,Internat.J.Al- gebra Comput.5(1995),no.4-5,379–602. [31]The Kourovka notebook.Unsolved problems in group theory.Fifteenth augmented edition.Edited by V.D.Mazurov and E.I.Khukhro.Russian Academy of Sciences Siberian Division,Institute of Mathematics,Novosibirsk,2002.125pp. [32]https://www.wendangku.net/doc/767130069.html,rsen,The conjugacy problem and cyclic HNN constructions,J.Austral.Math. Soc.Ser.A23(1977),no.4,385–401. [33]R.C.Lyndon,P.E.Schupp,Combinatorial group theory.Ergebnisse der Mathematik und ihrer Grenzgebiete,89.Springer-Verlag,Berlin-New York,1977. [34]A.I.Malcev,On homomorphisms onto?nite groups,Uchen.Zapiski Ivanovsk.ped. instituta18(1958),no.5,49–60(also in“Selected papers”,Vol.1,Algebra,(1976), 450–461) [35]A.I.Malcev,On isomorphi matrix representations of in?nite groups,Mat.Sbornik8 (1940),no.3,405–422. [36]B.Newman,Some results on one-relator groups,Bull.Amer.Math.Soc.74(1968), 568–571. [37]G.A.Noskov,V.N.Remeslennikov,V.A.Roman’kov,In?nite groups,Itogi Nauki Tekh.,Ser.Algebra Topologiya Geom.17(1979),65–157(Russian). [38]P.S.Novikov,Unsolvability of the conjugacy problem in the theory of groups,Izv. Akad.Nauk SSSR.Ser.Mat.18(1954),485–524(Russian). 18BARDAKOV,BOKUT,AND VESNIN [39]S.Pride,Small cancellation conditions satis?ed by one-relator groups,Math.Z.184 (1983),no.2,283–286. [40]Z.Sela,The conjugcy problem for knot groups,Topology32(1993),no.2,363–369. [41]C.M.Weinbaum,The word and conjugacy problems for the knot group of any tame, prime,alternating knot,Proc.Amer.Math.Soc.30(1971),22–26. Sobolev Institute of Mathematics,Novosibirsk630090,Russia E-mail address:bardakov@math.nsc.ru Sobolev Institute of Mathematics,Novosibirsk630090,Russia E-mail address:bokut@math.nsc.ru Sobolev Institute of Mathematics,Novosibirsk630090,Russia E-mail address:vesnin@math.nsc.ru