Automorphic orbits in free groups: recent progress
This survey reviews recent progress on automorphic orbits in free groups, focusing on orbit-blocking words, Whitehead's automorphism problem, potentially positive elements, and (bounded) translation equivalence. A word is \(w\)-orbit-blocking if it never occurs as a subword of the cyclic reduction of an automorphic image of \(w\). The survey explains how \(w\)-orbit-blocking words can be constructed from primitivity-blocking words. In particular, if \(w\in F_r\) has cyclically reduced length \(\ell\), then a product of \(\ell+1\) primitivity-blocking words, with no cancellation between consecutive factors or between the last and the first, is \(w\)-orbit-blocking. It also records the shortest primitivity-blocking words for \(r>2\) and a quadratic-time algorithm for recognizing primitivity-blocking words in \(F_2\).\N\NConcerning Whitehead's automorphism problem, the survey compares worst-case, generic-case, and average-case complexity. In \(F_2\) the worst-case complexity is at most quadratic, while the generic-case complexity of the classical Whitehead algorithm is linear. For the variant with a fixed word \(u\) and a cyclically reduced random input \(v\), an algorithm with constant average-case complexity is described. The survey also discusses potential positivity, including a recent algorithm in \(F_2\) with quadratic worst-case complexity, linear generic-case complexity, and constant average-case complexity for cyclically reduced inputs, as well as the problem of counting potentially positive elements of a given length. Finally, it considers translation equivalence and bounded translation equivalence and the corresponding algorithmic recognition problems.
- A fine property of Whitehead's algorithm
- A remark on Whitehead's cut-vertex lemma
- A tighter bound for the number of words of minimum length in an automorphic orbit.
- Automorphic orbits in free groups.
- Automorphic orbits in free groups: words versus subgroups.
- Average-case complexity and decision problems in group theory.
- Average-case complexity of the Whitehead problem for free groups
- Characters of free groups represented in the two-dimensional special linear group.
- Complexity and randomness in group theory. GAGTA book 1
- Counting words of minimum length in an automorphic orbit.
- Detecting automorphic orbits in free groups.
- Fast Pattern Matching in Strings
- Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
- Generic-case complexity, decision problems in group theory, and random walks.
- Group-theoretic orbit decidability.
- Growth of primitive elements in free groups.
- scientific article; zbMATH DE number 5155088 (Why is no real title available?)
- scientific article; zbMATH DE number 2144699 (Why is no real title available?)
- On certain sets of elements in a free group.
- On equivalent sets of elements in a free group
- On Jordan's theorem for complex linear groups
- On several problems about automorphisms of the free group of rank two.
- Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2
- Orbit-blocking words in free groups
- Positive One-Relator Groups
- Stability of Numerical Invariants in Free Groups
- The residual finiteness of positive one-relator groups
- Train tracks and automorphisms of free groups
- Translation equivalence in free groups
- Translation equivalent elements in free groups
- What does a basis of F(a,b) look like?
This page was built for publication: Automorphic orbits in free groups: recent progress
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7309763)
