# Presentations of infinite index subgroups

Suppose we have a finitely presented group $G$ with a concrete presentation and a subgroup $H$, generated by a finite set of elements from $G$. How to find the presentation for $H$?

If $H$ has finite index we can use Reidemeister-Schreier procedure. But what if $H$ has infinite index? What methods exist? Are there some methods if $H$ is normal?

-
Reidemeister-Schreier still works but gives an infinite presentation. – Benjamin Steinberg Aug 26 '12 at 12:35
There are fp groups where for fp subgroups there is no algorithm to compute finite presentation. The examples are due to Martin Bridson and HW who will probably say more on this soon. This, in general, infinite presentation is the best you can hope for, although in practice, things could be more manageable. – Misha Aug 26 '12 at 13:57
@Benjamin Steinberg: Yes, but we choose subgroup to be finitely generated, so I think it's reasonable to hope to find at least recursive presentations (under certain conditions). – Dan Aug 26 '12 at 14:35
There is one finitely presented group containing all recursively presented groups as subgroups (Borisov). I think the group has something like 22 defining relations (very explicit). Conversely every f.g. subgroup of a f.p. group is recursively presented. So the question does not make sense as asked. – Mark Sapir Aug 26 '12 at 16:34
@Yves: The key words in my comment are "22 defining relations (very explicit)". – Mark Sapir Aug 26 '12 at 17:34

The following answer will only be about decidability results or, more often, undecidability results. Of course, if you have a particular group in mind, it may be that something positive can be said. I will leave others to talk about practical algorithms.

Let $G=\langle X\mid R \rangle$ be a finitely presented group, $S$ a finite subset and $H=\langle S\rangle$.

As you mentioned recursive presentations in your comment, let me mention that there is a naive algorithm that always finds a recursive presentation for $H$: just enumerate all words in $S$ that happen to lie in $\langle\langle R \rangle\rangle$. Of course, as there are finitely presented groups that are not coherent, $H$ may not be finitely presentable, so this is the best you can hope for.

Even if you assume that $H$ is finitely presentable, as Misha says, there is no algorithm to compute a finite presentation for $H$. This follows immediately from the undecidability of the word problem: if you could compute a presentation for $\langle w\rangle$ then, in particular, you could determine whether or not $w=1$.

Of course, the next thing to wonder is whether there are examples with solvable word problem. Collins constructed a group with solvable word problem and unsolvable order problem --- that is, you can tell whether or not an element $w$ is trivial, but you can't compute the order of $w$. Again, it follows that you can't compute a presentation for $\langle w\rangle$.

The examples so far are specially constructed to behave badly. Bridson and I used work of Haglund and Wise to give examples which show that you can't compute presentations for finitely presentable subgroups even in 'naturally occurring' classes like automatic groups and matrix groups. You can also look at Section 8 of our paper for a summary of positive results.

-
Thanks for interesting examples. But can you clarify the part about recursive presentation and that naive algorithm? Do you suppose that $G$ have solvable w.p.? How can we decide whether or not word in $S$ lie in $\langle\langle R \rangle\rangle$ without knowing the w.p. solution for $G$? – Dan Aug 26 '12 at 20:42
@Dan: HW said to enumerate the words in $S$ that lie in $\langle\langle R\rangle\rangle$; that can be done, because $\langle\langle R\rangle\rangle$ is certainly r.e., even if it isn't recursive. This will give you an r.e. presentation for $H$, but you can convert it to a recursive presentation by "padding" the relators (put in lots of $a^{-1}a$ factors) so that they're enumerated in order of increasing length. – Andreas Blass Aug 26 '12 at 21:57
@Dan - Andreas is exactly right. This is a slightly unfortunate bit of terminology. A presentation is recursive if the set of all relators is r.e.; we do not also require that the set of all non-relators is r.e. (which would, indeed, be equivalent to solvability of the word problem). – HJRW Aug 27 '12 at 10:25
Oh I see. The set of relators for $H$ is just an $\bf intersection$ of 2 r.e. sets - words in $S$ and words in $\langle\langle R\rangle\rangle$. And yes, terminology is a bit confusing. – Dan Aug 27 '12 at 10:54
Exactly!${}{}{}$ – HJRW Aug 27 '12 at 10:55