The monomorphism problem in free groups. (Q974649)

Let \(F\) be the free group of finite rank \(n\). For two elements \(u,v\) in \(F\) we can formulate the natural decision problem: does there exist an algorithm that determines whether there is a homomorphism \(\varphi\colon F\to F\) such that \(\varphi(u)=v\)? If \(\varphi\) is required to be an automorphism, an endomorphism, or a monomorphism then this is called the automorphism problem, the endomorphism problem, or the monomorphism problem, respectively. The automorphism problem for free groups was answered positively by Whitehead. Makanin's algorithm implies that the endomorphism problem for free groups is solvable. In this paper the authors prove that the monomorphism problem for free groups is solvable by providing an explicit two-stage algorithm. The simple algorithm for Stage~I is at least exponential in the length \(|v|\); however, it is shown that this may be replaced by an algorithm that is polynomial in \(|v|\). Stage~II consists of applying Whitehead's algorithm. Whitehead's algorithm has been conjectured to be polynomial in the lengths \(|u|,|v|\), and this is known to be true either when \(n=2\) or when \(u,v\) satisfy certain technical conditions. It therefore follows, for example, that the monomorphism problem for the free group of rank 2 has a time complexity that is polynomial in \(|u|,|v|\). The paper closes by extending the methods developed to prove that the multiple monomorphism problem for free groups is solvable. That is, for any \(r\geq 1\) and any two tuples of words \((u_1,\dots,u_r)\), \((v_1,\dots,v_r)\) there is an algorithm that determines whether there is a monomorphism \(\varphi\colon F\to F\) such that \(\varphi(u_i)=v_i\) for all \(1\leq i\leq r\).