Orbit-blocking words in free groups (Q6848917)

This paper studies orbit-blocking words in the free group \(F_r\). For \(w\in F_r\), a word \(v\) is called \(w\)-orbit-blocking if \(v\) is not a subword of the cyclic reduction of \(\varphi(w)\) for any automorphism \(\varphi\in \operatorname{Aut}(F_r)\). This extends the notion of a primitivity-blocking word, corresponding to the case \(w=x_1\).\N\NThe starting point is the cut vertex lemma by \textit{J. H. C. Whitehead} [Proc. London math. Soc. 41, 48--56 (1936; Zbl 0013.24801)]: the Whitehead graph of a cyclically reduced primitive element is either disconnected or has a cut vertex. The paper briefly recalls this classical criterion and also refers to a recent extension to primitive elements in subgroups of \(F_r\) (see [\textit{D. Ascari}, Groups Geom. Dyn. 18, No. 1, 235--264 (2024; Zbl 1540.20046)]). Building on this background, the authors prove that primitivity-blocking words cannot occur as subwords in several wider situations, including strongly reduced bases and derive corresponding generalizations for weakly reduced and partially reduced bases, as well as for images of slender words under strongly reduced automorphisms.\N\NThe main result shows that for every \(w\in F_r\) there exist \(w\)-orbit-blocking words. More precisely, if the cyclically reduced length of \(w\) is \(\ell\) and \(v_1,\dots,v_{\ell+1}\) is a sequence of primitivity-blocking words with no cancellation between consecutive terms and none between \(v_{\ell+1}\) and \(v_1\), then \(\prod_{i=1}^{\ell+1} v_i\) is \(w\)-orbit-blocking. The paper also gives new examples of primitivity-blocking words, proves the existence of an \(O(n^2)\) algorithm deciding primitivity-blocking in \(F_2\) and applies the orbit-blocking construction to a variant of Whitehead's problem, obtaining constant average-case time complexity for cyclically reduced random inputs of length \(n\).