Automorphic orbits in free groups.

DOI10.1016/S0021-8693(03)00339-9MaRDI QIDQ1414027zbMATH OpenOpenAlexFDO

Authors Vladimir Shpilrain, Alexei Myasnikov

Publication date 19 November 2003

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0211157

zbMATH Keywords

automorphismscomplexity of Whitehead algorithmendomorphismsfree groupsorbits

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Automorphisms of infinite groups (20E36) Analysis of algorithms and problem complexity (68Q25)

Abstract: Let $F_n$ be the free group of a finite rank $n$. We study orbits $Or{b}_{phi}(u)$, where $u$ is an element of the group $F_n$, under the action of an automorphism $phi$. If an orbit like that is finite, we determine precisely what its cardinality can be if $u$ runs through the whole group $F_n$, and $phi$ runs through the whole group $Aut(F_n)$. 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.

Review text

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).

Recommendations

• scientific article; zbMATH DE number 2144699
• Counting words of minimum length in an automorphic orbit.
• Detecting automorphic orbits in free groups.
• Rescuing the Whitehead method for free products. I: Peak reduction
• A tighter bound for the number of words of minimum length in an automorphic orbit.

Cites work

• A Characterization of Periodic Automorphisms of a Free Group
• Finite groups of automorphisms of free groups
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3224578 (Why is no real title available?)
• On equivalent sets of elements in a free group
• On generalised free products
• On the maximum order of torsion elements in \(GL(n,\mathbb{Z})\) and \(\text{Aut}(F_n)\)
• Periodic ends, growth rates, Hölder dynamics for automorphisms of free groups
• Primitives in the free group on two generators
• Train tracks and automorphisms of free groups
• What does a basis of F(a,b) look like?

Cited in

(31)

• Automorphisms of free groups with boundaries.
• On the word problem for special monoids
• Primitive and almost primitive elements of Schreier varieties
• Criteria for equidistribution of solutions of word equations on \(\mathrm{SL}(2)\).
• Equations in simple matrix groups: algebra, geometry, arithmetic, dynamics.
• A hybrid search algorithm for the Whitehead minimization problem.
• Counting words of minimum length in an automorphic orbit.
• Growth of primitive elements in free groups.
• Random equations in free groups.
• Classification of automorphic conjugacy classes in the free group on two generators.
• Search and witness problems in group theory.
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• On an algorithm to decide whether a free group is a free factor of another
• Growing words in the free group on two generators.
• Automorphisms of free groups have asymptotically periodic dynamics
• Automorphic orbits in free groups: words versus subgroups.
• The primitivity index function for a free group, and untangling closed curves on hyperbolic surfaces.With the appendix by Khalid Bou–Rabee
• Problèmes de densité d'orbites pour des groupes d'automorphismes de C2
• POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS
• Average-case complexity of the Whitehead problem for free groups
• Short, Highly Imprimitive Words Yield Hyperbolic One-Relator Groups
• Detecting automorphic orbits in free groups.
• On endomorphisms of the direct product of two free groups
• Quantifying orbit detection: \(\varphi\)-order and \(\varphi\)-spectrum
• Orbit-blocking words in free groups
• Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2
• Automorphic orbits in free groups: recent progress
• Palindromic primitives and palindromic bases in the free group of rank two.
• A tighter bound for the number of words of minimum length in an automorphic orbit.
• The subadditive ergodic theorem and generic stretching factors for free group automorphisms.
• The monomorphism problem in free groups.

This page was built for publication: Automorphic orbits in free groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1414027)