showing the subgroup membership problem is undecidable for $F_2 \times F_2$

Question

Let $F_2$ denote the free group of rank 2. Does anybody have a fast proof that the subgroup membership problem is undecidable for $F_2 \times F_2$? I saw a really fast proof last semester that started with a group with undecidable word problem and used that group to construct subgroups of $F_2 \times F_2$, but I've lost my notes from the talk. I tried looking at the original proof from the 1960's but I couldn't get an English translation. Thanks!

Answer 1

First, $F_2 \times F_2$ contains a copy of $F_n \times F_n$ for all $n \geq 1$, so it is enough to find such a group inside $F_n \times F_n$ for some $n$. Let $G$ be a finitely generated group with an unsolvable word problem and let $S$ be a generating set for $G$. Let $f : F(S) \times F(S) \rightarrow G \times G$ be the product of the natural projection $F(S) \rightarrow G$ with itself. Let $\Delta < G \times G$ be the diagonal subgroup, and define $H = f^{-1}(\Delta)$. Then $(x,y) \in H$ if and only if $x$ and $y$ define the same element of $G$, so it is clear that you can't solve the membership problem for $H$.

EDIT : If $G$ has a finite presentation with relations $R$, then $H$ is actually finitely generated. Indeed, I claim that $H$ is generated by the union of the sets $\{(x,x) | x \in S\}$ and $\{(r,1) | r \in R\}$ and $\{(1,r) | r \in R\}$. The only potential problem with this is that $R$ only normally generates the kernel of the projection $F(S) \rightarrow G$. However, observe that for $w \in F(S)$ and $r \in R$, the element $(wrw^{-1},1) = (w,w)(r,1)(w^{-1},w^{-1})$ is in the subgroup generated by the purported generating set, and similarly for $(r,wrw^{-1})$.

Answer 2

Here is a completion of the proof in Andy's answer. One needs to show that the subgroup is finitely generated (which is not true if $G$ is not finitely presented). The subgroup (also called the Mihailova subgroup) is generated by the elements $(a,a)$ and $(1,r)$, where $a$ runs over the generators of $F(S)$ and $r$ runs over the finite set of defining relations of $G$. The fact that the Mihailova subgroup (it consists of all pairs $(x,y)$ with $f(x)=f(y)$) is generated by these elements is easy. Clearly for every generator $(u,v)$ ($u=v=a$ or $u=1, v=r$) we have $f(u)=f(v)$. Conversely, if $f(u)=f(v)$, that is $f(uv^{-1})=1$ in $G$, the word $uv^{-1}$ can be represented as a product of conjugates of defining relators and their inverses. From this product it is easy to represent the pair $(u,v)$ as a product of generators (see, for example, this paper and the references there). For example, if $uv^{-1}=ara^{-1}$, then $(v,u)=(a,a)(1,r)(a,a)^{-1}(v,v)$ where $(v,v)$ is an obvious products of pairs of the form $(a,a)$.