Whitehead's Decision Problems for Automorphisms of Free Group

Abstract

Let F be a free group of finite rank. Given words u, v ∈ F, J.H.C. Whitehead solved the decision problem of finding an automorphism φ ∈ Aut(F), carrying u to v. He used topological methods to produce an algorithm. Higgins and Lyndon gave a very concise proof of the problem based on the works of Rapaport. We provide a detailed account of Higgins and Lyndon’s proof of the peak reduction lemma and the restricted version of Whitehead’s theorem, for cyclic words as well as for sets of cyclic words, with a full explanation of each step. Then, we give an inductive proof of Whitehead’s minimization theorem and describe Whitehead’s decision algorithm. Noticing that Higgins and Lyndon’s work is limited to the cyclic words, we extend their proofs to ordinary words and sets of ordinary words. In the last chapter, we mention an example given by Whitehead to show that the decision problem for finitely generated subgroups is more difficult and outline an approach due to Gersten to overcome this difficulty. We also give an extensive literature survey of Whitehead’s algorithm