On Whitehead’s algorithm
Stephen M. Gersten · Bulletin of the American Mathematical Society · 1984
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. THEOREM W. There is an effective procedure for determining when two elements of S n are in the same orbit of the A-action. THEOREM M. The stabilizer in A of an element of S n is finitely presented, and a finite presentation can be effectively determined.In this note we indicate briefly the ideas that go into the proofs of Theorems W and M. Pull details will appear elsewhere.We use the theory of graphs defined in [2].A graph X is a nonempty set with involution, denoted XH4Ï, together with a retraction t : X -• V(X) of X onto the fixed point set V(X) of the involution.Morphisms of graphs preserve the involution and the retraction.The set V(X) is called the set of vertices of