Generic-case complexity of Whitehead's algorithm, revisited

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 ,ϵ)$-minimal" conjugacy class $[w]$ in $F_N$, where $M\ge 1,\lambda >1$ and $0<ϵ<1$. Roughly, being $(M,\lambda ,ϵ)$-minimal means that every $\varphi \in Out(F_N)$ either increases the length $\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}_A$ by a factor of at least $\lambda$, or distorts the length $\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}_A$ multiplicatively by a factor $ϵ$-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 ,ϵ)$-minimal for some uniform constants $M,\lambda ,ϵ$. Consequently, for such $[w]$, Whitehead’s algorithm for the automorphic equivalence problem in $F_N$ works in quadratic time on the input $([w],[w^{\mathrm{\prime }}])$ where $[w^{\mathrm{\prime }}]$ is arbitrary, and in linear time if $[w^{\mathrm{\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.