TY - JOUR
T1 - Automorphic orbits in free groups
AU - Myasnikov, Alexei G.
AU - Shpilrain, Vladimir
PY - 2003/11/1
Y1 - 2003/11/1
N2 - Let Fn be the free group of a finite rank n. We study orbits Orbφ (u), where u is an element of the group Fn, under the action of an automorphism φ. If an orbit like that is finite, we determine precisely what its cardinality can be if u runs through the whole group Fn, and φ runs through the whole group Aut(Fn). Another problem that we address here is related to Whitehead's algorithm that determines whether or not a given element of a free group of finite rank is an automorphic image of another given element. It is known that the first part of this algorithm (reducing a given free word to a free word of minimum possible length by elementary Whitehead automorphisms) is fast (of quadratic time with respect to the length of the word). On the other hand, the second part of the algorithm (applied to two words of the same minimum length) was always considered very slow. We give here an improved algorithm for the second part, and we believe this algorithm always terminates in polynomial time with respect to the length of the words. We prove that this is indeed the case if the free group has rank 2.
AB - Let Fn be the free group of a finite rank n. We study orbits Orbφ (u), where u is an element of the group Fn, under the action of an automorphism φ. If an orbit like that is finite, we determine precisely what its cardinality can be if u runs through the whole group Fn, and φ runs through the whole group Aut(Fn). Another problem that we address here is related to Whitehead's algorithm that determines whether or not a given element of a free group of finite rank is an automorphic image of another given element. It is known that the first part of this algorithm (reducing a given free word to a free word of minimum possible length by elementary Whitehead automorphisms) is fast (of quadratic time with respect to the length of the word). On the other hand, the second part of the algorithm (applied to two words of the same minimum length) was always considered very slow. We give here an improved algorithm for the second part, and we believe this algorithm always terminates in polynomial time with respect to the length of the words. We prove that this is indeed the case if the free group has rank 2.
UR - http://www.scopus.com/inward/record.url?scp=0242511156&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0242511156&partnerID=8YFLogxK
U2 - 10.1016/S0021-8693(03)00339-9
DO - 10.1016/S0021-8693(03)00339-9
M3 - Article
AN - SCOPUS:0242511156
SN - 0021-8693
VL - 269
SP - 18
EP - 27
JO - Journal of Algebra
JF - Journal of Algebra
IS - 1
ER -