Counting words of minimum length in an automorphic orbit.
The author studies the behaviour of the cardinality \(N(u)\) of the cyclic words of the free group \(F_n\), which have the same minimum length in the automorphic orbit of the cyclic word \(u\). More precisely, let \(u\) be a cyclic word in \(F_n\), which has the minimum length in its automorphic orbit \(\text{Orb}_{\Aut F_n}(u)=\{\psi(u):\psi\in\Aut F_n\}\) and let \(N(u)\) the cardinality of the set \(\{v:|v|=|u|\) and \(v=\varphi(u)\) for some \(\varphi\in\Aut F_n\}\) where \(|v|\) denotes the length of the cyclic word \(v\). The author proves that \(N(u)\) is bounded by a polynomial function with respect to \(|u|\), under the rather strong hypothesis that if two letters \(x,y\) with \(x\neq y^{\pm 1}\) occur in \(u\), then the total number of occurrences of \(x^{\pm 1}\) in \(u\) is not equal to the total number of occurrences of \(y^{\pm 1}\) in \(u\). One of the main results is: Let \(u\) be a cyclic word in \(F_n\) that satisfies the above mentioned hypothesis, and let \(N(u)\) be the cardinality of the set \(\{v\in\text{Orb}_{\Aut F_n}(u):|v|=|u|\}\). Then \(N(u)\) is bounded by a polynomial function of degree \(n(5n-7)/2\) with respect to \(|u|\). The proof is combinatorial by using \textit{J. H. C. Whitehead}'s results [Ann. Math. (2) 37, 782-800 (1936; Zbl 0015.24804)] and considering many cases for the Whitehead automorphisms involved. A proof without the imposed hypothesis would yield the polynomial time of Whitehead's algorithm for \(F_n\).
- A tighter bound for the number of words of minimum length in an automorphic orbit.
- Automorphic orbits in free groups.
- On the genericity of Whitehead minimality
- ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
- Cycles of free words in several independent random permutations with restricted cycle lengths
- Artificial Intelligence and Symbolic Computation
- Computing orbits of the automorphism group of the subsequence poset \(B_{m,n}\) for \(n\geq 2m\)
- Number of cyclically irreducible words in the alphabet of a free group of finite rank
- A hybrid search algorithm for the Whitehead minimization problem.
- Growing words in the free group on two generators.
- A Presentation for the Automorphism Group of a Free Group of Finite Rank
- Automorphic orbits in free groups.
- Equivalence of Elements Under Automorphisms of a Free Group
- Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 2144699 (Why is no real title available?)
- On equivalent sets of elements in a free group
- Automorphic orbits in free groups.
- Cylinders, multi-cylinders and the induced action of (F_n).
- Search and witness problems in group theory.
- Growing words in the free group on two generators.
- Average-case complexity of the Whitehead problem for free groups
- Short, Highly Imprimitive Words Yield Hyperbolic One-Relator Groups
- Lexicographically least words in the orbit closure of the Rudin-Shapiro word
- 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
- A tighter bound for the number of words of minimum length in an automorphic orbit.
This page was built for publication: Counting words of minimum length in an automorphic orbit.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2498873)
