Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank \(2\) (Q7020053)

Let \(F_2\) be the free group of rank \(2\), with two generators \(a\) and \(b\) and let \(w \in F_2\). The authors call a reduced word \(v \in F_2\) \emph{an orbit-blocking word} for \(w\) if for every automorphism \(\phi\) of \(F_2\), the word \(v\) is not a subword of the cyclic reduction of \(\phi(w)\).\N\NLet \(w \in F_2\) and let \(\vert w \vert\) be the word length of \(w\) with respect to the generating set \(\{a^{\pm 1}, b^{\pm 1}\}\). The main result of the paper (Theorem 1 and its proof) shows that for all integers \(s, t > \vert w \vert + 1\), the element \(a^sb^t\) is an orbit-blocking word for \(w\).\N\NThe proof of Theorem 1 hinges on the theorem of [\textit{M. Cohen} et al., Math. Ann. 257, 435--445 (1981; Zbl 0458.20028)], which describes constraints on the powers of \(a\) and \(b\) that appear in the cyclically reduced constituents a basis of \(F_2\). Theorem 1 settles Problem (F40) of [\textit{G. Baumslag} et al., Contemp. Math. 296, 1--38 (2002; Zbl 1065.20042)] in the special case of \(F_2\).\N\NThe authors then consider the following version of the Whitehead automorphism problem: given a fixed element \(u \in F_2\), decide, on a cyclically reduced input \(v \in F_2\) of length \(n\), whether or not there is an automorphism \(\phi\) of \(F_2\) such that \(v = \phi(u)\). The authors show in Theorem 3 that the average-case time complexity of this problem is constant, i.e., it does not depend on \(n\). If one uses the double-ended queue computing model instead of a classical Turing machine, then the ``cyclically reduced'' condition on \(v\) can be dropped. The algorithm devised by the authors is a combination of two different algorithms running in parallel: one is fast but may be inconclusive, whereas the other one is conclusive but relatively slow; the idea of such a combination goes back to [\textit{I. Kapovich} et al., Adv. Math. 190, No. 2, 343--359 (2005; Zbl 1065.20044)]. The fast algorithm of this paper is built upon the orbit-blocking words of Theorem 1. A result similar to Theorem 3 was proved in [\textit{V. Shpilrain}, Commun. Algebra 51, No. 2, 799--806 (2023; Zbl 1516.20068)] for \(F_r\), the free group of rank \(r\) with \(r > 1\) arbitrary, but only when the fixed element \(u\) is primitive.\N\NThe paper is pleasant to read and it mentions several stimulating open problems. At the time of writing, the two principal results, namely Theorems 1 and 3, are being extended to \(F_r\) for every \(r > 2\) in [\textit{L. Koch-Hyde} et al., ``Orbit-blocking words in free groups'', Preprint, arXiv:2505.00477].