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.J. H. C. Whitehead, On equivalent sets of elements in a free group, Ann. of Math. (2) 37:4 (1936), 782–800. It is still unknown (except for the case n = 2) if Whitehead's algorithm has polynomial time complexity.
Statement of the problem
Let be a free group of rank with a free basis . The automorphism problem, or the automorphic equivalence problem for asks, given two freely reduced words whether there exists an automorphism such that .
Thus the automorphism problem asks, for whether . For one has if and only if , where are conjugacy classes in of accordingly. Therefore, the automorphism problem for is often formulated in terms of -equivalence of conjugacy classes of elements of .
For an element , denotes the freely reduced length of with respect to , and denotes the cyclically reduced length of with respect to . For the automorphism problem, the length of an input is measured as or as , depending on whether one views as an element of or as defining the corresponding conjugacy class in .
History
The automorphism problem for 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 , the connected sum of copies of . Then , and, moreover, up to a quotient by a finite normal subgroup isomorphic to , the mapping class group of is equal to ; see.Suhas Pandit, A note on automorphisms of the sphere complex. Proc. Indian Acad. Sci. Math. Sci. 124:2 (2014), 255–265; Different free bases of can be represented by isotopy classes of "sphere systems" in , and the cyclically reduced form of an element , as well as the Whitehead graph of , can be "read-off" from how a loop in general position representing intersects the spheres in the system. Whitehead moves can be represented by certain kinds of topological "swapping" moves modifying the sphere system.Allen Hatcher, Homological stability for automorphism groups of free groups, Commentarii Mathematici Helvetici 70:1 (1995) 39–62; 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; Andrew Clifford, and Richard Z. Goldstein, Sets of primitive elements in a free group. Journal of Algebra 357 (2012), 271–278;
Subsequently, Rapaport,Elvira Rapaport, On free groups and their automorphisms. Acta Mathematica 99 (1958), 139–163; and later, based on her work, Higgins and Lyndon,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; 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,Roger Lyndon and Paul Schupp, Combinatorial group theory. Reprint of the 1977 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2001. as well as.
Overview
The automorphism group has a particularly useful finite generating set of Whitehead automorphisms or Whitehead moves. Given the first part of Whitehead's algorithm consists of iteratively applying Whitehead moves to 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 of , we check if . If then are not automorphically equivalent in .
If , we check if there exists a finite chain of Whitehead moves taking to so that the cyclically reduced length remains constant throughout this chain. The elements are not automorphically equivalent in if and only if such a chain exists.
Whitehead's algorithm also solves the search automorphism problem for . Namely, given , if Whitehead's algorithm concludes that , the algorithm also outputs an automorphism such that . Such an element is produced as the composition of a chain of Whitehead moves arising from the above procedure and taking to .
Whitehead automorphisms
A Whitehead automorphism, or Whitehead move, of is an automorphism of of one of the following two types:
There is a permutation of such that for Such is called a Whitehead automorphism of the first kind. There is an element , called the multiplier, such that for every Such is called a Whitehead automorphism of the second kind. Since is an automorphism of , it follows that in this case.
Often, for a Whitehead automorphism , the corresponding outer automorphism in is also called a Whitehead automorphism or a Whitehead move.
Examples Let .
Let be a homomorphism such that
Then is actually an automorphism of , and, moreover, is a Whitehead automorphism of the second kind, with the multiplier .
Let be a homomorphism such that
Then is actually an inner automorphism of given by conjugation by , and, moreover, is a Whitehead automorphism of the second kind, with the multiplier .
Automorphically minimal and Whitehead minimal elements
For , the conjugacy class is called automorphically minimal if for every we have . Also, a conjugacy class is called Whitehead minimal if for every Whitehead move we have .
Thus, by definition, if 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: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
Let . Then the following hold:
If is not automorphically minimal, then there exists a Whitehead automorphism such that .
Suppose that is automorphically minimal, and that another conjugacy class is also automorphically minimal. Then if and only if and there exists a finite sequence of Whitehead moves such that and
Part (1) of the Peak Reduction Lemma implies that a conjugacy class is Whitehead minimal if and only if it is automorphically minimal.
The automorphism graph
The automorphism graph of is a graph with the vertex set being the set of conjugacy classes of elements . Two distinct vertices are adjacent in if and there exists a Whitehead automorphism such that . For a vertex of , the connected component of in is denoted .
Whitehead graph
For with cyclically reduced form , the Whitehead graph is a labelled graph with the vertex set , where for there is an edge joining and with the label or "weight" which is equal to the number of distinct occurrences of subwords read cyclically in . (In some versions of the Whitehead graph one only includes the edges with .)
If is a Whitehead automorphism, then the length change can be expressed as a linear combination, with integer coefficients determined by , of the weights in the Whitehead graph . 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 , finds an automorphically minimal such that
This algorithm proceeds as follows. Given , put . If is already constructed, check if there exists a Whitehead automorphism such that . (This condition can be checked since the set of Whitehead automorphisms of is finite.) If such exists, put and go to the next step. If no such exists, declare that is automorphically minimal, with , and terminate the algorithm.
Part (1) of the Peak Reduction Lemma implies that the Whitehead's minimization algorithm terminates with some , where , and that then is indeed automorphically minimal and satisfies .
Whitehead's algorithm for the automorphic equivalence problem
Whitehead's algorithm for the automorphic equivalence problem, given decides whether or not .
The algorithm proceeds as follows. Given , first apply the Whitehead minimization algorithm to each of to find automorphically minimal such that and . If , declare that and terminate the algorithm. Suppose now that . Then check if there exists a finite sequence of Whitehead moves such that and
This condition can be checked since the number of cyclically reduced words of length in is finite. More specifically, using the breadth-first approach, one constructs the connected components of the automorphism graph and checks if .
If such a sequence exists, declare that , and terminate the algorithm. If no such sequence exists, declare that and terminate the algorithm.
The Peak Reduction Lemma implies that Whitehead's algorithm correctly solves the automorphic equivalence problem in . Moreover, if , the algorithm actually produces (as a composition of Whitehead moves) an automorphism such that .
Computational complexity of Whitehead's algorithm
A priori, the worst-case asymptotic time complexity of Whitehead's algorithm may be exponential in terms of the size of an input word. Whether that bound is achieved is unknown. There are several partial results showing stronger bounds on aspects of the algorithm.
Whitehead's minimization algorithm runs in polynomial time for a fixed rank of free group. If the rank of is fixed, then, given , the Whitehead minimization algorithm always terminates in quadratic time and produces an automorphically minimal word in the automorphic orbit of . Moreover, even if is not considered fixed, (an adaptation of) the Whitehead minimization algorithm on an input terminates in time .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; If the rank of is fixed, then for an automorphically minimal constructing the graph takes time and thus requires a priori exponential time in . For that reason Whitehead's algorithm for deciding, given , whether or not , runs in at most exponential time in . For , Khan proved that for an automorphically minimal , the graph has at most vertices and hence constructing the graph can be done in quadratic time in .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 Consequently, Whitehead's algorithm for the automorphic equivalence problem in , given runs in quadratic time in . For fixed , Lee proved that for automorphically minimal in which the number of times each generator appears (either with positive or negative exponent) is unique, the size of is , a polynomial with respect to the length of . The set of words for which this applies is generic in .
The average-case time complexity of Whitehead's algorithm is also unknown. For a fixed rank of free group, if is bounded by a polynomial, then the average time complexity is linear. Thus it is linear when restricted to .
Applications, generalizations and related results