Whitehead's algorithm is a mathematical algorithm in group theory for solving the automorphic equivalence problem in the finite rank free group Fn. The algorithm is based on a classic 1936 paper of J. H. C. Whitehead. It is still unknown (except for the case n = 2) if Whitehead's algorithm has polynomial time complexity.
Statement of the problem Let F n = F ( x 1 , … , x n ) {\displaystyle F_{n}=F(x_{1},\dots ,x_{n})} be a free group of rank n ≥ 2 {\displaystyle n\geq 2} with a free basis X = { x 1 , … , x n } {\displaystyle X=\{x_{1},\dots ,x_{n}\}} . The automorphism problem, or the automorphic equivalence problem for F n {\displaystyle F_{n}} asks, given two freely reduced words w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} whether there exists an automorphism φ ∈ Aut ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} such that φ ( w ) = w ′ {\displaystyle \varphi (w)=w'} . Thus the automorphism problem asks, for w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} whether Aut ( F n ) w = Aut ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} . For w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} one has Aut ( F n ) w = Aut ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} if and only if Out ( F n ) [ w ] = Out ( F n ) [ w ′ ] {\displaystyle \operatorname {Out} (F_{n})[w]=\operatorname {Out} (F_{n})[w']} , where [ w ] , [ w ′ ] {\displaystyle [w],[w']} are conjugacy classes in F n {\displaystyle F_{n}} of w , w ′ {\displaystyle w,w'} accordingly. Therefore, the automorphism problem for F n {\displaystyle F_{n}} is often formulated in terms of Out ( F n ) {\displaystyle \operatorname {Out} (F_{n})} -equivalence of conjugacy classes of elements of F n {\displaystyle F_{n}} . For an element w ∈ F n {\displaystyle w\in F_{n}} , | w | X {\displaystyle |w|_{X}} denotes the freely reduced length of w {\displaystyle w} with respect to X {\displaystyle X} , and ‖ w ‖ X {\displaystyle \|w\|_{X}} denotes the cyclically reduced length of w {\displaystyle w} with respect to X {\displaystyle X} . For the automorphism problem, the length of an input w {\displaystyle w} is measured as | w | X {\displaystyle |w|_{X}} or as ‖ w ‖ X {\displaystyle \|w\|_{X}} , depending on whether one views w {\displaystyle w} as an element of F n {\displaystyle F_{n}} or as defining the corresponding conjugacy class [ w ] {\displaystyle [w]} in F n {\displaystyle F_{n}} .
History The automorphism problem for F n {\displaystyle F_{n}} was algorithmically solved by J. H. C. Whitehead in a classic 1936 paper, and his solution came to be known as Whitehead's algorithm. Whitehead used a topological approach in his paper. Namely, consider the 3-manifold M n = # i = 1 n S 2 × S 1 {\displaystyle M_{n}=\#_{i=1}^{n}\mathbb {S} ^{2}\times \mathbb {S} ^{1}} , the connected sum of n {\displaystyle n} copies of S 2 × S 1 {\displaystyle \mathbb {S} ^{2}\times \mathbb {S} ^{1}} . Then π 1 ( M n ) ≅ F n {\displaystyle \pi _{1}(M_{n})\cong F_{n}} , and, moreover, up to a quotient by a finite normal subgroup isomorphic to Z 2 n {\displaystyle \mathbb {Z} _{2}^{n}} , the mapping class group of M n {\displaystyle M_{n}} is equal to Out ( F n ) {\displaystyle \operatorname {Out} (F_{n})} ; see. Different free bases of F n {\displaystyle F_{n}} can be represented by isotopy classes of "sphere systems" in M n {\displaystyle M_{n}} , and the cyclically reduced form of an element w ∈ F n {\displaystyle w\in F_{n}} , as well as the Whitehead graph of [ w ] {\displaystyle [w]} , can be "read-off" from how a loop in general position representing [ w ] {\displaystyle [w]} intersects the spheres in the system. Whitehead moves can be represented by certain kinds of topological "swapping" moves modifying the sphere system. Subsequently, Rapaport, and later, based on her work, Higgins and Lyndon, gave a purely combinatorial and algebraic re-interpretation of Whitehead's work and of Whitehead's algorithm. The exposition of Whitehead's algorithm in the book of Lyndon and Schupp is based on this combinatorial approach. Culler and Vogtmann, in their 1986 paper that introduced the Outer space, gave a hybrid approach to Whitehead's algorithm, presented in combinatorial terms but closely following Whitehead's original ideas.
Whitehead's algorithm Our exposition regarding Whitehead's algorithm mostly follows Ch.I.4 in the book of Lyndon and Schupp, as well as.
Overview The automorphism group Aut ( F n ) {\displaystyle \operatorname {Aut} (F_{n})} has a particularly useful finite generating set W {\displaystyle {\mathcal {W}}} of Whitehead automorphisms or Whitehead moves. Given w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} the first part of Whitehead's algorithm consists of iteratively applying Whitehead moves to w , w ′ {\displaystyle w,w'} to take each of them to an "automorphically minimal" form, where the cyclically reduced length strictly decreases at each step. Once we find automorphically these minimal forms u , u ′ {\displaystyle u,u'} of w , w ′ {\displaystyle w,w'} , we check if ‖ u ‖ X = ‖ u ′ ‖ X {\displaystyle \|u\|_{X}=\|u'\|_{X}} . If ‖ u ‖ X ≠ ‖ u ′ ‖ X {\displaystyle \|u\|_{X}\neq \|u'\|_{X}} then w , w ′ {\displaystyle w,w'} are not automorphically equivalent in F n {\displaystyle F_{n}} . If ‖ u ‖ X = ‖ u ′ ‖ X {\displaystyle \|u\|_{X}=\|u'\|_{X}} , we check if there exists a finite chain of Whitehead moves taking u {\displaystyle u} to u ′ {\displaystyle u'} so that the cyclically reduced length remains constant throughout this chain. The elements w , w ′ {\displaystyle w,w'} are not automorphically equivalent in F n {\displaystyle F_{n}} if and only if such a chain exists. Whitehead's algorithm also solves the search automorphism problem for F n {\displaystyle F_{n}} . Namely, given w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} , if Whitehead's algorithm concludes that Aut ( F n ) w = Aut ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} , the algorithm also outputs an automorphism φ ∈ Aut ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} such that φ ( w ) = w ′ {\displaystyle \varphi (w)=w'} . Such an element φ ∈ Aut ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} is produced as the composition of a chain of Whitehead moves arising from the above procedure and taking w {\displaystyle w} to w ′ {\displaystyle w'} .
Whitehead automorphisms A Whitehead automorphism, or Whitehead move, of F n {\displaystyle F_{n}} is an automorphism τ ∈ Aut ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} of F n {\displaystyle F_{n}} of one of the following two types:
There is a permutation σ ∈ S n {\displaystyle \sigma \in S_{n}} of { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} such that for i = 1 , … , n {\displaystyle i=1,\dots ,n} τ ( x i ) = x σ ( i ) ± 1 {\displaystyle \tau (x_{i})=x_{\sigma (i)}^{\pm 1}} Such τ {\displaystyle \tau } is called a Whitehead automorphism of the first kind. There is an element a ∈ X ± 1 {\displaystyle a\in X^{\pm 1}} , called the multiplier, such that for every x ∈ X ± 1 {\displaystyle x\in X^{\pm 1}} τ ( x ) ∈ { x , x a , a − 1 x , a − 1 x a } . {\displaystyle \tau (x)\in \{x,xa,a^{-1}x,a^{-1}xa\}.} Such τ {\displaystyle \tau } is called a Whitehead automorphism of the second kind. Since τ {\displaystyle \tau } is an automorphism of F n {\displaystyle F_{n}} , it follows that τ ( a ) = a {\displaystyle \tau (a)=a} in this case. Often, for a Whitehead automorphism τ ∈ Aut ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} , the corresponding outer automorphism in Out ( F n ) {\displaystyle \operatorname {Out} (F_{n})} is also called a Whitehead automorphism or a Whitehead move.
Examples Let F 4 = F ( x 1 , x 2 , x 3 , x 4 ) {\displaystyle F_{4}=F(x_{1},x_{2},x_{3},x_{4})} . Let τ : F 4 → F 4 {\displaystyle \tau :F_{4}\to F_{4}} be a homomorphism such that
τ ( x 1 ) = x 2 x 1 , τ ( x 2 ) = x 2 , τ ( x 3 ) = x 2 x 3 x 2 − 1 , τ ( x 4 ) = x 4 {\displaystyle \tau (x_{1})=x_{2}x_{1},\quad \tau (x_{2})=x_{2},\quad \tau (x_{3})=x_{2}x_{3}x_{2}^{-1},\quad \tau (x_{4})=x_{4}}
Then τ {\displaystyle \tau } is actually an automorphism of F 4 {\displaystyle F_{4}} , and, moreover, τ {\displaystyle \tau } is a Whitehead automorphism of the second kind, with the multiplier a = x 2 − 1 {\displaystyle a=x_{2}^{-1}} . Let τ ′ : F 4 → F 4 {\displaystyle \tau ':F_{4}\to F_{4}} be a homomorphism such that
τ ′ ( x 1 ) = x 1 , τ ′ ( x 2 ) = x 1 − 1 x 2 x 1 , τ ′ ( x 3 ) = x 1 − 1 x 3 x 1 , τ ′ ( x 4 ) = x 1 − 1 x 4 x 1 {\displaystyle \tau '(x_{1})=x_{1},\quad \tau '(x_{2})=x_{1}^{-1}x_{2}x_{1},\quad \tau '(x_{3})=x_{1}^{-1}x_{3}x_{1},\quad \tau '(x_{4})=x_{1}^{-1}x_{4}x_{1}}
Then τ ′ {\displaystyle \tau '} is actually an inner automorphism of F 4 {\displaystyle F_{4}} given by conjugation by x 1 {\displaystyle x_{1}} , and, moreover, τ ′ {\displaystyle \tau '} is a Whitehead automorphism of the second kind, with the multiplier a = x 1 {\displaystyle a=x_{1}} .
Automorphically minimal and Whitehead minimal elements For w ∈ F n {\displaystyle w\in F_{n}} , the conjugacy class [ w ] {\displaystyle [w]} is called automorphically minimal if for every φ ∈ Aut ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} we have ‖ w ‖ X ≤ ‖ φ ( w ) ‖ X {\displaystyle \|w\|_{X}\leq \|\varphi (w)\|_{X}} . Also, a conjugacy class [ w ] {\displaystyle [w]} is called Whitehead minimal if for every Whitehead move τ ∈ Aut ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} we have ‖ w ‖ X ≤ ‖ τ ( w ) ‖ X {\displaystyle \|w\|_{X}\leq \|\tau (w)\|_{X}} . Thus, by definition, if [ w ] {\displaystyle [w]} is automorphically minimal then it is also Whitehead minimal. It turns out that the converse is also true.
Whitehead's "Peak Reduction Lemma" The following statement is referred to as Whitehead's "Peak Reduction Lemma", see Proposition 4.20 in and Proposition 1.2 in: Let w ∈ F n {\displaystyle w\in F_{n}} . Then the following hold:
If [ w ] {\displaystyle [w]} is not automorphically minimal, then there exists a Whitehead automorphism τ ∈ Aut ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} such that ‖ τ ( w ) ‖ X < ‖ w ‖ X {\displaystyle \|\tau (w)\|_{X}<\|w\|_{X}} . Suppose that [ w ] {\displaystyle [w]} is automorphically minimal, and that another conjugacy class [ w ′ ] {\displaystyle [w']} is also automorphically minimal. Then Aut ( F n ) w = Aut ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} if and only if ‖ w ‖ X = ‖ w ′ ‖ X {\displaystyle \|w\|_{X}=\|w'\|_{X}} and there exists a finite sequence of Whitehead moves τ 1 , … , τ k ∈ Aut ( F n ) {\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})} such that τ k ⋯ τ 1 ( w ) = w ′ {\displaystyle \tau _{k}\cdots \tau _{1}(w)=w'} and ‖ τ i ⋯ τ 1 ( w ) ‖ X = ‖ w ‖ X for i = 1 , … , k . {\displaystyle \|\tau _{i}\cdots \tau _{1}(w)\|_{X}=\|w\|_{X}{\text{ for }}i=1,\dots ,k.}
Part (1) of the Peak Reduction Lemma implies that a conjugacy class [ w ] {\displaystyle [w]} is Whitehead minimal if and only if it is automorphically minimal.
The automorphism graph The automorphism graph A {\displaystyle {\mathcal {A}}} of F n {\displaystyle F_{n}} is a graph with the vertex set being the set of conjugacy classes [ u ] {\displaystyle [u]} of elements u ∈ F n {\displaystyle u\in F_{n}} . Two distinct vertices [ u ] , [ v ] {\displaystyle [u],[v]} are adjacent in A {\displaystyle {\mathcal {A}}} if ‖ u ‖ X = ‖ v ‖ X {\displaystyle \|u\|_{X}=\|v\|_{X}} and there exists a Whitehead automorphism τ {\displaystyle \tau } such that [ τ ( u ) ] = [ v ] {\displaystyle [\tau (u)]=[v]} . For a vertex [ u ] {\displaystyle [u]} of A {\displaystyle {\mathcal {A}}} , the connected component of [ u ] {\displaystyle [u]} in A {\displaystyle {\mathcal {A}}} is denoted A [ u ] {\displaystyle {\mathcal {A}}[u]} .
Whitehead graph For 1 ≠ w ∈ F n {\displaystyle 1\neq w\in F_{n}} with cyclically reduced form u {\displaystyle u} , the Whitehead graph Γ [ w ] {\displaystyle \Gamma _{[w]}} is a labelled graph with the vertex set X ± 1 {\displaystyle X^{\pm 1}} , where for x , y ∈ X ± 1 , x ≠ y {\displaystyle x,y\in X^{\pm 1},x\neq y} there is an edge joining x {\displaystyle x} and y {\displaystyle y} with the label or "weight" n ( { x , y } ; [ w ] ) {\displaystyle n(\{x,y\};[w])} which is equal to the number of distinct occurrences of subwords x − 1 y , y − 1 x {\displaystyle x^{-1}y,y^{-1}x} read cyclically in u {\displaystyle u} . (In some versions of the Whitehead graph one only includes the edges with n ( { x , y } ; [ w ] ) > 0 {\displaystyle n(\{x,y\};[w])>0} .) If τ ∈ Aut ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} is a Whitehead automorphism, then the length change ‖ τ ( w ) ‖ X − ‖ w ‖ X {\displaystyle \|\tau (w)\|_{X}-\|w\|_{X}} can be expressed as a linear combination, with integer coefficients determined by τ {\displaystyle \tau } , of the weights n ( { x , y } ; [ w ] ) {\displaystyle n(\{x,y\};[w])} in the Whitehead graph Γ [ w ] {\displaystyle \Gamma _{[w]}} . See Proposition 4.16 in Ch. I of. This fact plays a key role in the proof of Whitehead's peak reduction result.
Whitehead's minimization algorithm Whitehead's minimization algorithm, given a freely reduced word w ∈ F n {\displaystyle w\in F_{n}} , finds an automorphically minimal [ v ] {\displaystyle [v]} such that Aut ( F n ) w = Aut ( F n ) v . {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v.}
This algorithm proceeds as follows. Given w ∈ F n {\displaystyle w\in F_{n}} , put w 1 = w {\displaystyle w_{1}=w} . If w i {\displaystyle w_{i}} is already constructed, check if there exists a Whitehead automorphism τ ∈ Aut ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} such that ‖ τ ( w i ) ‖ X < ‖ w i ‖ X {\displaystyle \|\tau (w_{i})\|_{X}<\|w_{i}\|_{X}} . (This condition can be checked since the set of Whitehead automorphisms of F n {\displaystyle F_{n}} is finite.) If such τ {\displaystyle \tau } exists, put w i + 1 = τ ( w i ) {\displaystyle w_{i+1}=\tau (w_{i})} and go to the next step. If no such τ {\displaystyle \tau } exists, declare that [ w i ] {\displaystyle [w_{i}]} is automorphically minimal, with Aut ( F n ) w = Aut ( F n ) w i {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{i}} , and terminate the algorithm. Part (1) of the Peak Reduction Lemma implies that the Whitehead's minimization algorithm terminates with some w m {\displaystyle w_{m}} , where m ≤ ‖ w ‖ X {\displaystyle m\leq \|w\|_{X}} , and that then [ w m ] {\displaystyle [w_{m}]} is indeed automorphically minimal and satisfies Aut ( F n ) w = Aut ( F n ) w m {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{m}} .
Whitehead's algorithm for the automorphic equivalence problem Whitehead's algorithm for the automorphic equivalence problem, given w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} decides whether or not Aut ( F n ) w = Aut ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} . The algorithm proceeds as follows. Given w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} , first apply the Whitehead minimization algorithm to each of w , w ′ {\displaystyle w,w'} to find automorphically minimal [ v