Subexponential growth conjecture for equal-length Whitehead orbit elements
Subexponential growth conjecture for equal-length Whitehead orbit elements
Let be a free group, and let be a word whose length cannot be reduced by any elementary Whitehead automorphism; in particular, is cyclically reduced. Consider the elements in the automorphic orbit of having the same length as . Subexponential equal-length orbit conjecture. The number of such elements is subexponential in . This conjecture would imply that, for arbitrary rank , the average-case time complexity of the Whitehead algorithm is linear, extending the known rank-two result. The paper describes the required orbit-growth estimate as an open problem.
Sources & referencesView supporting material
Primary source
Vladimir Shpilrain, “Average-case complexity of the Whitehead problem for a free group”, arXiv:2105.01366 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.