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!
2 Answers
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})$.

$\begingroup$ Thanks for the answer. That $H$ subgroup won't necessarily be finitely generated, right? $\endgroup$– danFeb 4, 2011 at 17:54

$\begingroup$ I added the details giving that $H$ can be assumed to be finitely generated (at the same time that Mark was typing his answer). $\endgroup$ Feb 4, 2011 at 18:06
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)$.