Orbit-blocking words and the average-case complexity of Whitehead’s problem in the free group of rank 2

Let <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>F</m:mi> <m:mn>2</m:mn> </m:msub> </m:math> F₂ denote the free group of rank 2. Our main technical result of independent interest is the following: for any element 𝑢 of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>F</m:mi> <m:mn>2</m:mn> </m:msub> </m:math> F₂ , there is some <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>g</m:mi> <m:mo>∈</m:mo> <m:msub> <m:mi>F</m:mi> <m:mn>2</m:mn> </m:msub> </m:mrow> </m:math> g∈ F₂ such that no cyclically reduced image of 𝑢 under an automorphism of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>F</m:mi> <m:mn>2</m:mn> </m:msub> </m:math> F₂ contains 𝑔 as a subword. We then address the computational complexity of the following version of the Whitehead automorphism problem: given a fixed <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>u</m:mi> <m:mo>∈</m:mo> <m:msub> <m:mi>F</m:mi> <m:mn>2</m:mn> </m:msub> </m:mrow> </m:math> u∈ F₂ , decide, on an input <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>v</m:mi> <m:mo>∈</m:mo> <m:msub> <m:mi>F</m:mi> <m:mn>2</m:mn> </m:msub> </m:mrow> </m:math> v∈ F₂ of length 𝑛, whether or not 𝑣 is an automorphic image of 𝑢. We show that there is an algorithm that solves this problem and has constant (i.e., independent of 𝑛) average-case complexity.