Whitehead's algorithm

Whitehead's algorithm is a mathematical algorithm in group theory for solving the automorphic equivalence problem in the finite rank free group F_n. The algorithm is based on a classic 1936 paper of J. H. C. Whitehead.^[1] It is still unknown (except for the case n = 2) if Whitehead's algorithm has polynomial time complexity.

Statement of the problem

Let ${\displaystyle F_{n}=F(x_{1},\dots ,x_{n})}$  be a free group of rank ${\displaystyle n\geq 2}$  with a free basis ${\displaystyle X=\{x_{1},\dots ,x_{n}\}}$ . The automorphism problem, or the automorphic equivalence problem for ${\displaystyle F_{n}}$  asks, given two freely reduced words ${\displaystyle w,w'\in F_{n}}$  whether there exists an automorphism ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$  such that ${\displaystyle \varphi (w)=w'}$ .

Thus the automorphism problem asks, for ${\displaystyle w,w'\in F_{n}}$  whether ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ . For ${\displaystyle w,w'\in F_{n}}$  one has ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$  if and only if ${\displaystyle \operatorname {Out} (F_{n})[w]=\operatorname {Out} (F_{n})[w']}$ , where ${\displaystyle [w],[w']}$  are conjugacy classes in ${\displaystyle F_{n}}$  of ${\displaystyle w,w'}$  accordingly. Therefore, the automorphism problem for ${\displaystyle F_{n}}$  is often formulated in terms of ${\displaystyle \operatorname {Out} (F_{n})}$ -equivalence of conjugacy classes of elements of ${\displaystyle F_{n}}$ .

For an element ${\displaystyle w\in F_{n}}$ , ${\displaystyle |w|_{X}}$  denotes the freely reduced length of ${\displaystyle w}$  with respect to ${\displaystyle X}$ , and ${\displaystyle \|w\|_{X}}$  denotes the cyclically reduced length of ${\displaystyle w}$  with respect to ${\displaystyle X}$ . For the automorphism problem, the length of an input ${\displaystyle w}$  is measured as ${\displaystyle |w|_{X}}$  or as ${\displaystyle \|w\|_{X}}$ , depending on whether one views ${\displaystyle w}$  as an element of ${\displaystyle F_{n}}$  or as defining the corresponding conjugacy class ${\displaystyle [w]}$  in ${\displaystyle F_{n}}$ .

History

The automorphism problem for ${\displaystyle F_{n}}$  was algorithmically solved by J. H. C. Whitehead in a classic 1936 paper,^[1] and his solution came to be known as Whitehead's algorithm. Whitehead used a topological approach in his paper. Namely, consider the 3-manifold ${\displaystyle M_{n}=\#_{i=1}^{n}\mathbb {S} ^{2}\times \mathbb {S} ^{1}}$ , the connected sum of ${\displaystyle n}$  copies of ${\displaystyle \mathbb {S} ^{2}\times \mathbb {S} ^{1}}$ . Then ${\displaystyle \pi _{1}(M_{n})\cong F_{n}}$ , and, moreover, up to a quotient by a finite normal subgroup isomorphic to ${\displaystyle \mathbb {Z} _{2}^{n}}$ , the mapping class group of ${\displaystyle M_{n}}$  is equal to ${\displaystyle \operatorname {Out} (F_{n})}$ ; see.^[2] Different free bases of ${\displaystyle F_{n}}$  can be represented by isotopy classes of "sphere systems" in ${\displaystyle M_{n}}$ , and the cyclically reduced form of an element ${\displaystyle w\in F_{n}}$ , as well as the Whitehead graph of ${\displaystyle [w]}$ , can be "read-off" from how a loop in general position representing ${\displaystyle [w]}$  intersects the spheres in the system. Whitehead moves can be represented by certain kinds of topological "swapping" moves modifying the sphere system.^[3][4][5]

Subsequently, Rapaport,^[6] and later, based on her work, Higgins and Lyndon,^[7] 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^[8] is based on this combinatorial approach. Culler and Vogtmann,^[9] 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,^[8] as well as.^[10]

Overview

The automorphism group ${\displaystyle \operatorname {Aut} (F_{n})}$  has a particularly useful finite generating set ${\displaystyle {\mathcal {W}}}$  of Whitehead automorphisms or Whitehead moves. Given ${\displaystyle w,w'\in F_{n}}$  the first part of Whitehead's algorithm consists of iteratively applying Whitehead moves to ${\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 ${\displaystyle u,u'}$  of ${\displaystyle w,w'}$ , we check if ${\displaystyle \|u\|_{X}=\|u'\|_{X}}$ . If ${\displaystyle \|u\|_{X}\neq \|u'\|_{X}}$  then ${\displaystyle w,w'}$  are not automorphically equivalent in ${\displaystyle F_{n}}$ .

If ${\displaystyle \|u\|_{X}=\|u'\|_{X}}$ , we check if there exists a finite chain of Whitehead moves taking ${\displaystyle u}$  to ${\displaystyle u'}$  so that the cyclically reduced length remains constant throughout this chain. The elements ${\displaystyle w,w'}$  are not automorphically equivalent in ${\displaystyle F_{n}}$  if and only if such a chain exists.

Whitehead's algorithm also solves the search automorphism problem for ${\displaystyle F_{n}}$ . Namely, given ${\displaystyle w,w'\in F_{n}}$ , if Whitehead's algorithm concludes that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ , the algorithm also outputs an automorphism ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$  such that ${\displaystyle \varphi (w)=w'}$ . Such an element ${\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 ${\displaystyle w}$  to ${\displaystyle w'}$ .

Whitehead automorphisms

A Whitehead automorphism, or Whitehead move, of ${\displaystyle F_{n}}$  is an automorphism ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$  of ${\displaystyle F_{n}}$  of one of the following two types:

(i) There is a permutation ${\displaystyle \sigma \in S_{n}}$  of ${\displaystyle \{1,2,\dots ,n\}}$  such that for ${\displaystyle i=1,\dots ,n}$ 

${\displaystyle \tau (x_{i})=x_{\sigma (i)}^{\pm 1}}$ 

Such ${\displaystyle \tau }$  is called a Whitehead automorphism of the first kind.

(ii) There is an element ${\displaystyle a\in X^{\pm 1}}$ , called the multiplier, such that for every ${\displaystyle x\in X^{\pm 1}}$ 

${\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 ${\displaystyle F_{n}}$ , it follows that ${\displaystyle \tau (a)=a}$  in this case.

Often, for a Whitehead automorphism ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ , the corresponding outer automorphism in ${\displaystyle \operatorname {Out} (F_{n})}$  is also called a Whitehead automorphism or a Whitehead move.

Examples

Let ${\displaystyle F_{4}=F(x_{1},x_{2},x_{3},x_{4})}$ .

Let ${\displaystyle \tau :F_{4}\to F_{4}}$  be a homomorphism such that

${\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 ${\displaystyle F_{4}}$ , and, moreover, ${\displaystyle \tau }$  is a Whitehead automorphism of the second kind, with the multiplier ${\displaystyle a=x_{2}^{-1}}$ .

Let ${\displaystyle \tau ':F_{4}\to F_{4}}$  be a homomorphism such that

${\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 ${\displaystyle F_{4}}$  given by conjugation by ${\displaystyle x_{1}}$ , and, moreover, ${\displaystyle \tau '}$ is a Whitehead automorphism of the second kind, with the multiplier ${\displaystyle a=x_{1}}$ .

Automorphically minimal and Whitehead minimal elements

For ${\displaystyle w\in F_{n}}$ , the conjugacy class ${\displaystyle [w]}$  is called automorphically minimal if for every ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$  we have ${\displaystyle \|w\|_{X}\leq \|\varphi (w)\|_{X}}$ . Also, a conjugacy class ${\displaystyle [w]}$  is called Whitehead minimal if for every Whitehead move ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$  we have ${\displaystyle \|w\|_{X}\leq \|\tau (w)\|_{X}}$ .

Thus, by definition, if ${\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 ^[8] and Proposition 1.2 in:^[10]

Let ${\displaystyle w\in F_{n}}$ . Then the following hold:

(1) If ${\displaystyle [w]}$  is not automorphically minimal, then there exists a Whitehead automorphism ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$  such that ${\displaystyle \|\tau (w)\|_{X}<\|w\|_{X}}$ .

(2) Suppose that ${\displaystyle [w]}$  is automorphically minimal, and that another conjugacy class ${\displaystyle [w']}$  is also automorphically minimal. Then ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$  if and only if ${\displaystyle \|w\|_{X}=\|w'\|_{X}}$  and there exists a finite sequence of Whitehead moves ${\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})}$  such that

${\displaystyle \tau _{k}\cdots \tau _{1}(w)=w'}$ 

and

${\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 ${\displaystyle [w]}$  is Whitehead minimal if and only if it is automorphically minimal.

The automorphism graph

The automorphism graph ${\displaystyle {\mathcal {A}}}$  of ${\displaystyle F_{n}}$  is a graph with the vertex set being the set of conjugacy classes ${\displaystyle [u]}$  of elements ${\displaystyle u\in F_{n}}$ . Two distinct vertices ${\displaystyle [u],[v]}$  are adjacent in ${\displaystyle {\mathcal {A}}}$  if ${\displaystyle \|u\|_{X}=\|v\|_{X}}$  and there exists a Whitehead automorphism ${\displaystyle \tau }$  such that ${\displaystyle [\tau (u)]=[v]}$ . For a vertex ${\displaystyle [u]}$  of ${\displaystyle {\mathcal {A}}}$ , the connected component of ${\displaystyle [u]}$  in ${\displaystyle {\mathcal {A}}}$  is denoted ${\displaystyle {\mathcal {A}}[u]}$ .

Whitehead graph

For ${\displaystyle 1\neq w\in F_{n}}$  with cyclically reduced form ${\displaystyle u}$ , the Whitehead graph ${\displaystyle \Gamma _{[w]}}$  is a labelled graph with the vertex set ${\displaystyle X^{\pm 1}}$ , where for ${\displaystyle x,y\in X^{\pm 1},x\neq y}$  there is an edge joining ${\displaystyle x}$  and ${\displaystyle y}$  with the label or "weight" ${\displaystyle n(\{x,y\};[w])}$  which is equal to the number of distinct occurrences of subwords ${\displaystyle x^{-1}y,y^{-1}x}$  read cyclically in ${\displaystyle u}$ . (In some versions of the Whitehead graph one only includes the edges with ${\displaystyle n(\{x,y\};[w])>0}$ .)

If ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$  is a Whitehead automorphism, then the length change ${\displaystyle \|\tau (w)\|_{X}-\|w\|_{X}}$  can be expressed as a linear combination, with integer coefficients determined by ${\displaystyle \tau }$ , of the weights ${\displaystyle n(\{x,y\};[w])}$  in the Whitehead graph ${\displaystyle \Gamma _{[w]}}$ . See Proposition 4.16 in Ch. I of.^[8] 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 ${\displaystyle w\in F_{n}}$ , finds an automorphically minimal ${\displaystyle [v]}$  such that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v.}$ 

This algorithm proceeds as follows. Given ${\displaystyle w\in F_{n}}$ , put ${\displaystyle w_{1}=w}$ . If ${\displaystyle w_{i}}$  is already constructed, check if there exists a Whitehead automorphism ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$  such that ${\displaystyle \|\tau (w_{i})\|_{X}<\|w_{i}\|_{X}}$ . (This condition can be checked since the set of Whitehead automorphisms of ${\displaystyle F_{n}}$  is finite.) If such ${\displaystyle \tau }$  exists, put ${\displaystyle w_{i+1}=\tau (w_{i})}$  and go to the next step. If no such ${\displaystyle \tau }$  exists, declare that ${\displaystyle [w_{i}]}$  is automorphically minimal, with ${\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 ${\displaystyle w_{m}}$ , where ${\displaystyle m\leq \|w\|_{X}}$ , and that then ${\displaystyle [w_{m}]}$  is indeed automorphically minimal and satisfies ${\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 ${\displaystyle w,w'\in F_{n}}$  decides whether or not ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ .

The algorithm proceeds as follows. Given ${\displaystyle w,w'\in F_{n}}$ , first apply the Whitehead minimization algorithm to each of ${\displaystyle w,w'}$  to find automorphically minimal ${\displaystyle [v],[v']}$  such that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v}$  and ${\displaystyle \operatorname {Aut} (F_{n})w'=\operatorname {Aut} (F_{n})v'}$ . If ${\displaystyle \|v\|_{X}\neq \|v'\|_{X}}$ , declare that ${\displaystyle \operatorname {Aut} (F_{n})w\neq \operatorname {Aut} (F_{n})w'}$  and terminate the algorithm. Suppose now that ${\displaystyle \|v\|_{X}=\|v'\|_{X}=t\geq 0}$ . Then check if there exists a finite sequence of Whitehead moves ${\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})}$  such that

${\displaystyle \tau _{k}\dots \tau _{1}(v)=v'}$ 

and

${\displaystyle \|\tau _{i}\dots \tau _{1}(v)\|_{X}=\|v\|_{X}=t{\text{ for }}i=1,\dots ,k.}$ 

This condition can be checked since the number of cyclically reduced words of length ${\displaystyle t}$  in ${\displaystyle F_{n}}$  is finite. More specifically, using the breadth-first approach, one constructs the connected components ${\displaystyle {\mathcal {A}}[v],{\mathcal {A}}[v']}$  of the automorphism graph and checks if ${\displaystyle {\mathcal {A}}[v]\cap {\mathcal {A}}[v']=\varnothing }$ .

If such a sequence exists, declare that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ , and terminate the algorithm. If no such sequence exists, declare that ${\displaystyle \operatorname {Aut} (F_{n})w\neq \operatorname {Aut} (F_{n})w'}$  and terminate the algorithm.

The Peak Reduction Lemma implies that Whitehead's algorithm correctly solves the automorphic equivalence problem in ${\displaystyle F_{n}}$ . Moreover, if ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ , the algorithm actually produces (as a composition of Whitehead moves) an automorphism ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$  such that ${\displaystyle \varphi (w)=w'}$ .

Computational complexity of Whitehead's algorithm

• If the rank ${\displaystyle n\geq 2}$  of ${\displaystyle F_{n}}$  is fixed, then, given ${\displaystyle w\in F_{n}}$ , the Whitehead minimization algorithm always terminates in quadratic time ${\displaystyle O(|w|_{X}^{2})}$  and produces an automorphically minimal cyclically reduced word ${\displaystyle u\in F_{n}}$  such that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})u}$ .^[10] Moreover, even if ${\displaystyle n}$  is not considered fixed, (an adaptation of) the Whitehead minimization algorithm on an input ${\displaystyle w\in F_{n}}$  terminates in time ${\displaystyle O(|w|_{X}^{2}n^{3})}$ .^[11]
• If the rank ${\displaystyle n\geq 3}$  of ${\displaystyle F_{n}}$  is fixed, then for an automorphically minimal ${\displaystyle u\in F_{n}}$  constructing the graph ${\displaystyle {\mathcal {A}}[u]}$  takes ${\displaystyle O\left(\|u\|_{X}\cdot \#V{\mathcal {A}}[u]\right)}$  time and thus requires a priori exponential time in ${\displaystyle |u|_{X})}$ . For that reason Whitehead's algorithm for deciding, given ${\displaystyle w,w'\in F_{n}}$ , whether or not ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ , runs in at most exponential time in ${\displaystyle \max\{|w|_{X},|w'|_{X}\}}$ .
• For ${\displaystyle n=2}$ , Khan proved that for an automorphically minimal ${\displaystyle u\in F_{2}}$ , the graph ${\displaystyle {\mathcal {A}}[u]}$  has at most ${\displaystyle O\left(\|u\|_{X}\right)}$  vertices and hence constructing the graph ${\displaystyle {\mathcal {A}}[u]}$  can be done in quadratic time in ${\displaystyle |u|_{X}}$ .^[12] Consequently, Whitehead's algorithm for the automorphic equivalence problem in ${\displaystyle F_{2}}$ , given ${\displaystyle w,w'\in F_{2}}$  runs in quadratic time in ${\displaystyle \max\{|w|_{X},|w'|_{X}\}}$ .

Applications, generalizations and related results

• Whitehead's algorithm can be adapted to solve, for any fixed ${\displaystyle m\geq 1}$ , the automorphic equivalence problem for m-tuples of elects of ${\displaystyle F_{n}}$  and for m-tuples of conjugacy classes in ${\displaystyle F_{n}}$ ; see Ch.I.4 of ^[8] and ^[13]
• McCool used Whitehead's algorithm and the peak reduction to prove that for any ${\displaystyle w\in F_{n}}$  the stabilizer ${\displaystyle \operatorname {Stab} _{\operatorname {Out} (F_{n})}([w])}$  is finitely presentable, and obtained a similar results for ${\displaystyle \operatorname {Out} (F_{n})}$ -stabilizers of m-tuples of conjugacy classes in ${\displaystyle F_{n}}$ .^[14] McCool also used the peak reduction method to construct of a finite presentation of the group ${\displaystyle \operatorname {Aut} (F_{n})}$  with the set of Whitehead automorphisms as the generating set.^[15] He then used this presentation to recover a finite presentation for ${\displaystyle \operatorname {Aut} (F_{n})}$ , originally due to Nielsen, with Nielsen automorphisms as generators.^[16]
• Gersten obtained a variation of Whitehead's algorithm, for deciding, given two finite subsets ${\displaystyle S,S'\subseteq F_{n}}$ , whether the subgroups ${\displaystyle H=\langle S\rangle ,H'=\langle S'\rangle \leq F_{n}}$  are automorphically equivalent, that is, whether there exists ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$  such that ${\displaystyle \varphi (H)=H'}$ .^[17]
• Whitehead's algorithm and peak reduction play a key role in the proof by Culler and Vogtmann that the Culler–Vogtmann Outer space is contractible.^[9]
• Collins and Zieschang obtained analogs of Whitehead's peak reduction and of Whitehead's algorithm for automorphic equivalence in free products of groups.^[18][19]
• Gilbert used a version of a peak reduction lemma to construct a presentation for the automorphism group ${\displaystyle \operatorname {Aut} (G)}$  of a free product ${\displaystyle G=\ast _{i=1}^{m}G_{i}}$ .^[20]
• Levitt and Vogtmann produced a Whitehead-type algorithm for saving the automorphic equivalence problem (for elects, m-tuples of elements and m-tuples of conjugacy classes) in a group ${\displaystyle G=\pi _{1}(S)}$  where ${\displaystyle S}$  is a closed hyperbolic surface.^[21]
• If an element ${\displaystyle w\in F_{n}=F(X)}$  chosen uniformly at random from the sphere of radius ${\displaystyle m\geq 1}$  in ${\displaystyle F(X)}$ , then, with probability tending to 1 exponentially fast as ${\displaystyle m\to \infty }$ , the conjugacy class ${\displaystyle [w]}$  is already automorphically minimal and, moreover, ${\displaystyle \#V{\mathcal {A}}[w]=O\left(\|w\|_{X}\right)=O(m)}$ . Consequently, if ${\displaystyle w,w'\in F_{n}}$  are two such ``generic" elements, Whitehead's algorithm decides whether ${\displaystyle w,w'}$  are automorphically equivalent in linear time in ${\displaystyle \max\{|w|_{X},|w'|_{X}\}}$ .<sup>[10]</sup>
• Similar to the above results hold for the genericity of automorphic minimality for ``randomly chosen" finitely generated subgroups of ${\displaystyle F_{n}}$ .^[22]
• Lee proved that if ${\displaystyle u\in F_{n}=F(X)}$  is a cyclically reduced word such that ${\displaystyle [u]}$  is automorphically minimal, and if whenever ${\displaystyle x_{i},x_{j},i<j}$  both occur in ${\displaystyle u}$  or ${\displaystyle u^{-1}}$  then the total number of occurrences of ${\displaystyle x_{i}^{\pm 1}}$  in ${\displaystyle u}$  is smaller than the number of occurrences of ${\displaystyle x_{i}^{\pm 1}}$ , then ${\displaystyle \#V{\mathcal {A}}[u]}$  is bounded above by a polynomial of degree ${\displaystyle 2n-3}$  in ${\displaystyle |u|_{X}}$ .^[23] Consequently, if ${\displaystyle w,w'\in F_{n},n\geq 3}$  are such that ${\displaystyle w}$  is automorphically equivalent to some ${\displaystyle u}$  with the above property, then Whitehead's algorithm decides whether ${\displaystyle w,w'}$  are automorphically equivalent in time ${\displaystyle O\left(\max\{|w|_{X}^{2n-3},|w'|_{X}^{2}\}\right)}$ .
• The Garside algorithm for solving the conjugacy problem in braid groups has a similar general structure to Whitehead's algorithm, with "cycling moves" playing the role of Whitehead moves.^[24]
• Clifford and Goldstein used Whitehead-algorithm based techniques to produce an algorithm that, given a finite subset ${\displaystyle Z\subseteq F_{n}}$  decides whether or not the subgroup ${\displaystyle H=\langle Z\rangle \leq F_{n}}$  contains a primitive element of ${\displaystyle F_{n},}$  that is an element of a free generating set of ${\displaystyle F_{n}.}$ ^[25]
• Day obtained analogs of Whitehead's algorithm and of Whitehead's peak reduction for automorphic equivalence of elements of right-angled Artin groups.^[26]

References

1. J. H. C. Whitehead, On equivalent sets of elements in a free group, Ann. of Math. (2) 37:4 (1936), 782–800. MR1503309
2. Suhas Pandit, A note on automorphisms of the sphere complex. Proc. Indian Acad. Sci. Math. Sci. 124:2 (2014), 255–265; MR3218895
3. Allen Hatcher, Homological stability for automorphism groups of free groups, Commentarii Mathematici Helvetici 70:1 (1995) 39–62; MR1314940
4. Karen Vogtmann, Automorphisms of free groups and outer space. Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part I (Haifa, 2000). Geometriae Dedicata 94 (2002), 1–31; MR1950871
5. Andrew Clifford, and Richard Z. Goldstein, Sets of primitive elements in a free group. Journal of Algebra 357 (2012), 271–278; MR2905255
6. Elvira Rapaport, On free groups and their automorphisms. Acta Mathematica 99 (1958), 139–163; MR0131452
7. P. J. Higgins, and R. C. Lyndon, Equivalence of elements under automorphisms of a free group. Journal of the London Mathematical Society (2) 8 (1974), 254–258; MR0340420
8. Roger Lyndon and Paul Schupp, Combinatorial group theory. Reprint of the 1977 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2001. ISBN 3-540-41158-5MR1812024
9. Marc Culler; Karen Vogtmann (1986). "Moduli of graphs and automorphisms of free groups" (PDF). Inventiones Mathematicae. 84 (1): 91–119. doi:10.1007/BF01388734. MR 0830040. S2CID 122869546.
10. Ilya Kapovich, Paul Schupp, and Vladimir Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific Journal of Mathematics 223:1 (2006), 113–140
11. Abdó Roig, Enric Ventura, and Pascal Weil, On the complexity of the Whitehead minimization problem. International Journal of Algebra and Computation 17:8 (2007), 1611–1634; MR2378055
12. Bilal Khan, The structure of automorphic conjugacy in the free group of rank two. Computational and experimental group theory, 115–196, Contemp. Math., 349, American Mathematical Society, Providence, RI, 2004
13. Sava Krstić, Martin Lustig, and Karen Vogtmann, An equivariant Whitehead algorithm and conjugacy for roots of Dehn twist automorphisms. Proceedings of the Edinburgh Mathematical Society (2) 44:1 (2001), 117–141
14. James McCool, Some finitely presented subgroups of the automorphism group of a free group. Journal of Algebra 35:1-3 (1975), 205–213; MR0396764
15. James McCool, A presentation for the automorphism group of a free group of finite rank. Journal of the London Mathematical Society (2) 8 (1974), 259–266; MR0340421
16. James McCool, On Nielsen's presentation of the automorphism group of a free group. Journal of the London Mathematical Society (2) 10 (1975), 265–270
17. Stephen Gersten, On Whitehead's algorithm, Bulletin of the American Mathematical Society 10:2 (1984), 281–284; MR0733696
18. Donald J. Collins, and Heiner Zieschang, Rescuing the Whitehead method for free products. I. Peak reduction. Mathematische Zeitschrift 185:4 (1984), 487–504 MR0733769
19. Donald J. Collins, and Heiner Zieschang, Rescuing the Whitehead method for free products. II. The algorithm. Mathematische Zeitschrift 186:3 (1984), 335–361; MR0744825
20. Nick D. Gilbert, Presentations of the automorphism group of a free product. Proceedings of the London Mathematical Society (3) 54 (1987), no. 1, 115–140.
21. Gilbert Levitt and Karen Vogtmann, A Whitehead algorithm for surface groups, Topology 39:6 (2000), 1239–1251
22. Frédérique Bassino, Cyril Nicaud, and Pascal Weil, On the genericity of Whitehead minimality. Journal of Group Theory 19:1 (2016), 137–159 MR3441131
23. Donghi Lee, A tighter bound for the number of words of minimum length in an automorphic orbit. Journal of Algebra 305:2 (2006), 1093–1101; MRMR2266870
24. Joan Birman, Ki Hyoung Ko, and Sang Jin Lee, A new approach to the word and conjugacy problems in the braid groups, Advances in Mathematics 139:2 (1998), 322–353; Zbl 0937.20016 MR1654165
25. Andrew Clifford, and Richard Z. Goldstein, Subgroups of free groups and primitive elements. Journal of Group Theory 13:4 (2010), 601–611; MR2661660
26. Matthew Day, Full-featured peak reduction in right-angled Artin groups. Algebraic and Geometric Topology 14:3 (2014), 1677–1743 MR3212581

Further reading

• Heiner Zieschang, On the Nielsen and Whitehead methods in combinatorial group theory and topology. Groups—Korea '94 (Pusan), 317–337, Proceedings of the 3rd International Conference on the Theory of Groups held at Pusan National University, Pusan, August 18–25, 1994. Edited by A. C. Kim and D. L. Johnson. de Gruyter, Berlin, 1995; ISBN 3-11-014793-9 MR1476976
• Karen Vogtmann's lecture notes on Whitehead's algorithm using Whitehead's 3-manifold model