The subgroup membership problem for F_2 x F_2
So, I am not entirely sure what belongs in here so I thought I would share a very elegant proof I came across recently, due to one K.A. Mihailova, from 1958.
Background: Let be a group given in terms of generators and relations. It is a natural question to ask, given two words and ,
Unfortunately, this is a question which is insoluble in general: it is called the word problem for groups (note that this is equivalent to asking " ").
For more details, and examples, see wiki. Note that some of the examples there are finitely presented.
This is a driving question in group theory: Hyperbolic groups, probably the most studied class of groups of today, were defined so as to have soluble word (and conjugacy) problem*.
However, Free groups are nice. A word is freely equal to the trivial word if and only if it is the trivial word after freely reducing it. Free reduction is a finite process, so we have an algorithm to determine if a word is the trivial word or not. Similarly, two words are conjugate if and only if, after cyclically reducing them, they are cyclic shifts of one another. Finally, two free groups are isomorphic if and only if they are of the same rank - they are generated by the same number of elements. In fact, it is a theorem that every question you could want to know about free groups can be answered.
That said, the direct product of two free groups is not nice. This is counter-intuitive: free groups are nice, and so (surely) is the direct product! So presumably the direct product of two free groups is nice, no?
Question: For all finitely generated does there exist an algorithm to determine,
Solution: Firstly, note that contains a copy of for all . This is because (which is well-known). So it is enough to prove the result for for some .
So, let be a finitely presented group with insoluble word problem. Let in the natural way. Let be the diagonal subgroup and let , the pre-image of under . It is clearly a subgroup of . Then,
However, as has insoluble word problem you cannot solve the membership problem for .
That is the elegant bit of the proof over. One now has to prove that is finitely generated, which comes from the fact that is finitely presented. It is sufficient to show that,
(where ) which I shall leave as an exercise (it isn't too hard). Alternatively, you can find all this here.
The key point to take away is this: the direct product isn't nice...
*Basically, Gromov took an old algorithm, called Dehn's algorithm, which solved these two problems and found the most general class of groups which it would work for.