2
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ Reidemeister-Schreier still works but gives an infinite presentation. $\endgroup$ Aug 26, 2012 at 12:35
  • 3
    $\begingroup$ 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. $\endgroup$
    – Misha
    Aug 26, 2012 at 13:57
  • $\begingroup$ @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). $\endgroup$
    – Dan
    Aug 26, 2012 at 14:35
  • 3
    $\begingroup$ 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. $\endgroup$
    – user6976
    Aug 26, 2012 at 16:34
  • 1
    $\begingroup$ @Yves: The key words in my comment are "22 defining relations (very explicit)". $\endgroup$
    – user6976
    Aug 26, 2012 at 17:34

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$
    – Dan
    Aug 26, 2012 at 20:42
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 26, 2012 at 21:57
  • $\begingroup$ @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). $\endgroup$
    – HJRW
    Aug 27, 2012 at 10:25
  • $\begingroup$ 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. $\endgroup$
    – Dan
    Aug 27, 2012 at 10:54
  • $\begingroup$ Exactly!${}{}{}$ $\endgroup$
    – HJRW
    Aug 27, 2012 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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