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!


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$
    – dan
    Feb 4 '11 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 '11 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.