Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. (Q868743)

Let \(\Sigma=\{a_1,a_2,\dots,a_k\}^{\pm 1}\) be an alphabet and \(S\) be a set of words in the alphabet \(\Sigma\). For \(n\in\mathbb{N}\) let \(\rho(n,S)\) denotes the number of words \(w\in S\) with \(|w|\leq n\) (\(|w|\) is the reduced length of \(w\)). A subset \(B\subseteq S\) is `generic' in \(S\) if \(\lim_{n\to\infty}\frac{\rho(n,B)}{\rho(n,S)}=1\). If the convergence is exponentially fast, \(B\) is `exponentially generic' in \(S\). Let \(D\subseteq S\times S\), \(D\) is `generic' in \(S\times S\) if \(\lim_{n\to\infty}\frac{\rho(n,D)}{\rho(n,S\times S)}=1\), where \(\rho(n,D)\) denotes the number of pairs \((u,v)\in D\) such that \(|u|\leq n\) and \(|v|\leq n\). Let \(S\) be an infinite set of words in \(\Sigma\) and let \(D\subseteq S\times S\). Suppose that \(\Omega\) is an algorithm for deciding if an element \((u,v)\in S\times S\) belongs to \(D\). The algorithm \(\Omega\) `solves \(D\) with strong generic-case time complexity' in \(S\times S\) if there exists an exponentially \(S\times S\)-generic subset \(A\) of \(S\times S\) such that for any \((u,v)\in A\) with \(|u|\leq n,|v|\leq n\) the algorithm \(\Omega\) terminates on \((u,v)\) in at most \(t(n)\) steps, where \(t\) is a nondecreasing function. Here it is proved that the Whitehead algorithm, (which decides for two elements of a finitely generated free group, if there exists an automorphism which sends one to the other), has strongly linear time generic-case complexity. Let \(w\in F_k\) with the property: \(w\) is not a power and such that for every relabeling automorphism \(\tau\) of \(F_k\) the elements \(w\) and \(\tau(w)\) are not conjugate in \(F_k\). Moreover suppose that \(w\) is `strictly minimal', namely the cyclically reduced length \(\|\rho(w)\|\) is strictly greater than \(|w|\) for every noninner Whitehead automorphism \(\rho\) of the second kind. If \(TS'\) denotes the set of the elements of \(F_k\) whose cyclically reduced form has the above property, then it is proved: The set \(TS'\) is exponentially \(F_k\)-generic. There is a linear-time algorithm which, given a freely reduced word \(w\), decides if \(w\) belongs to \(TS'\). For any element \(w\in TS'\) the stabilizer of \(w\) in \(\Aut(F_k)\) is the infinite cyclic group generated by the inner automorphism induced by \(w\). These results combined with results of the first two authors [Math. Ann. 331, No. 1, 1-19 (2005; Zbl 1080.20029)] enable the authors to prove results on one-relator groups. There exists an exponentially \(C\)-generic set \(Q_k\) (\(C\) denotes the set of all cyclically reduced words in \(F_k\)) such that: For \(u\in Q_k\) the one relator group \(G_u=\langle a_1,a_2,\dots,a_k\mid u\rangle\) is a complete one-ended torsion free word-hyperbolic group. For \(u,v\in Q_k\) the groups \(G_u\) and \(G_v\) are isomorphic if and only if there exists a relabeling automorphism \(\tau\) of \(F_k\) such that \(\tau(u)\) is a cyclic permutation of either \(u\) or \(u^{-1}\). For \(u\in Q_k\) and \(v\in F_k\) there is a quadratic time algorithm which decides if the groups \(G_u\) and \(G_v\) are isomorphic. These results enable them to prove that the number of isomorphism types of \(k\)-generator one-relator groups with defining relators of the same cyclically reduced length grows in essentially the same way as the number of cyclic words of the same length. Except the algebraic methods the authors use probabilistic arguments, invoke ``The large deviation theory'' and refer to theorems from \textit{A. Dembo} and \textit{O. Zeitouni} [Large deviations techniques and applications. 2nd ed. Appl. Math. 38, New York: Springer (1998; Zbl 0896.60013)].