Automorphic orbits in free groups. (Q1414027): Difference between revisions

What are the possible lengths of finite orbits of elements in the free group \(F_n\) of rank \(n\), under the action of an automorphism of the group? The first result of the paper states that these are exactly the orders of periodic automorphisms of \(F_n\) (which are known), but that this is no longer true for orbits of arbitrary endomorphisms of \(F_n\). In the second part of the paper, the complexity of the Whitehead algorithm is examined (which determines whether a given element in a free group is an automorphic image of another given element). The first part of the algorithm (reducing to a word of minimal length) is in quadratic time with respect to the length of the word. It is shown that the second part of the algorithm (comparing two words of the same minimal length) can be done in at most exponential time, and in polynomial time for the free group of rank two (this remains open for free groups of bigger ranks).