Generic-case complexity of Whitehead's algorithm, revisited

Abstract

In \cite{KSS06} it was shown that with respect to the simple non-backtracking random walk on the free group $F_N=F(a_1,\dots ,a_N)$ the Whitehead algorithm has strongly linear time generic-case complexity and that "generic" elements of $F_N$ are "strictly minimal" in their $Out(F_N)$-orbits. Here we generalize these results, with appropriate modifications, to a much wider class of random processes generating elements of $F_N$. We introduce the notion of a ''$(M,\lambda ,\epsilon )$-minimal" conjugacy class $[w]$ in $F_N$, where $M\ge 1,\lambda >1$ and $0<\epsilon <1$. Roughly, being $(M,\lambda ,\epsilon )$-minimal means that every $\varphi \in Out(F_N)$ either increases the length $||w|{|}_A$ by a factor of at least $\lambda$, or distorts the length $||w|{|}_A$ multiplicatively by a factor $\epsilon$-close to $1$, and that the number of automorphically minimal $[u]$ in the orbit $Out(F_N)[w]$ is bounded by $M$. We then show that if a conjugacy class $[w]$ in $F_N$ is sufficiently close to a "filling" projective geodesic current $[\nu ]\in PCurr(F_N)$, then, after applying a single "reducing" automorphism $\psi =\psi (\nu )\in Out(F_N)$ depending on $\nu$ only, the element $\psi ([w])$ is $(M,\lambda ,\epsilon )$-minimal for some uniform constants $M,\lambda ,\epsilon$. Consequently, for such $[w]$, Whitehead's algorithm for the automorphic equivalence problem in $F_N$ works in quadratic time on the input $([w],[w^{\prime }])$ where $[w^{\prime }]$ is arbitrary, and in linear time if $[w^{\prime }]$ is also projectively close to $[\nu ]$. We then show that a wide class of random processes produce "random" conjugacy classes $[w_n]$ that projectively converge to some filling current in $PCurr(F_N)$. For such $[w_n]$ Whitehead's algorithm has at most quadratic generic-case complexity.

An updated and improved version. The use of Gekhtman's result has been corrected to account for the symmetrization issue. Statements of the main results have been added to the Introduction. various other fixes and cleanup

References in corpus (3)

• The Poisson boundary of $\text{Out}(F_N)$
• On the genericity of Whitehead minimality
• Equidistribution of closed geodesics along random walk trajectories with respect to the harmonic invariant measure