On the genericity of Whitehead minimality (Q905405)

A seminal paper by Whitehead from the 30's of last century solved the algorithmic problem of recognition of orbits of elements of the free group by the action of its automorphism group: given \(u,v\in F_r\), he effectively decided whether there exists an automorphism \(\varphi \in\mathrm{Aut}(F_r)\) such that \(\varphi(u)=v\). In this context, the finite family of the so-called Whitehead automorphisms was introduced, playing a central role together with the Pick reduction technique. The first part of this classical algorithm consists on computing a representative of the orbit of a given word \(u\in F_r\) of smallest possible length, i.e., computing minimal representatives of orbits. With the original algorithm this can be done in linear time with respect to the length of \(u\), but exponential on the ambient rank \(r\); an improvement by \textit{A. Roig} et al. [Int. J. Algebra Comput. 17, No. 8, 1611--1634 (2007; Zbl 1149.20024)] achieves the same goal in linear time with respect to \(|u|\), and polynomial time with respect to \(r\). It is known that most elements \(u\in F_r=F(A)\) (generically many, see [\textit{I. Kapovich} et al., Pac. J. Math. 223, No. 1, 113--140 (2006; Zbl 1149.20028)]) are strictly minimal in the sense that \(|\varphi (u)|>|u|\) for every \(\varphi \in \mathrm{Aut}(F_r)\), \(\varphi\) not being induced by a permutation of \(A^{\pm}\). The paper under review proves the corresponding version of this last result for subgroups: generically many finitely generated subgroups \(H\leq F_r\) satisfy \(|\varphi (H)|>|H|\) for every \(\varphi \in\mathrm{Aut}(F_r)\), \(\varphi\) not being induced by a permutation of \(A^{\pm}\). To make sense of these generic statements one needs to fix a distribution in the (infinite) set of objects of study (i.e., a measure of the objects, \(|w|\) and \(|H|\)). For the case of words (or cyclic words), the standard is to consider the length (or cyclic length), count the proportion of strictly minimal elements among those (finitely many) of up to a given length, and then make this length tend to infinity: Kapovich, Schupp and Shpilrain [loc. cit.] proved that this limit is 1, meaning that generically many elements of \(F_r\) are strictly minimal. For the case of subgroups there are two different distributions studied in the literature and the authors of the present paper prove that generically many of them are strict minimal in both senses: (1) the proportion of strictly minimal subgroups among those (finitely many) generated by \(k\)-tuples of words of length up to \(n\) tends to 1 when \(n\to \infty\); and (2) the proportion of strictly minimal subgroups among those (finitely many) whose Stallings graph has at most \(n\) vertices tends to 1 when \(n\to \infty\).