On Whitehead’s algorithm

One can decide effectively when two finitely generated subgroups of a finitely generated free group F are equivalent under an automorphism of F. The subgroup of automorphisms of F mapping a given finitely generated subgroup S of F into a conjugate of S is finitely presented. In two famous articles [9, 10] which appeared in 1936, J. H. C. Whitehead, using the theory of three-dimensional handlebodies, proved that one can effectively decide when two n-tuples of cyclic words of a finitely generated free group F are equivalent by an automorphism of F. The proof of this result has been simplified successively [7, 3] and the result itself has been immensely influential. Whitehead himself poses the problem of generalizing his theorem [10, p. 800]; namely he raises the question of deciding when two finitely generated subgroups of F are equivalent by an automorphism of F. In 1974 McCool [6] deduced a profound consequence of Whitehead's theorem, proving that the stabilizer, in the automorphism group of F, of an ntuple of cyclic words is finitely presented. Using graph-theoretic techniques we developed in [1] (the results of which were announced in [2]), we have succeeded both in settling Whitehead's question and in generalizing McCool's results. Let A denote the automorphism group of F, and let S denote the set of conjugacy classes of finitely generated subgroups of F with its natural A action. Let S n denote the cartesian product of n copies of S with diagonal A action.