Suppose I have a finitely presented group $G$. By this, I mean I know explicitly what $S$ and $R$ are such that $G = \langle S \mid R \rangle$. Suppose I have a subgroup generated by a finite set of words $W$ (that is, $H = \langle W \rangle \leq G$) and I also know all the elements of $W$ explicitly.

Is there an algorithm that gives me the index $[G:H]$? Or at least tells me whether it is finite or not?

  • 3
    $\begingroup$ No, even for $W=\emptyset$ (i.e.\ $H$ the trivial subgroup). There's no algorithm that imputs $S$ and $R$ (even fixing $S$ to have cardinal 2) and outputs yes iff $G$ is finite. $\endgroup$ – YCor Mar 1 '13 at 19:51
  • 1
    $\begingroup$ On the other hand, you may be consider $G$ as fixed group and ask if there's an algorithm that inputs $W$ and outputs what you ask. The answer is still no, when $G$ is $F\times F$ and $F$ is free on 2 generators and $W$ includes the generators of the diagonal, because subgroups of $F\times F$ containing the diagonal are natural in $1-1$ correspondence with normal subgroups of $F$. $\endgroup$ – YCor Mar 1 '13 at 19:55
  • 2
    $\begingroup$ I was about to add some information here, but changed my mind after you (virtually) stuck out your tongue at the last guy who tried to help. Sometimes a little politeness goes a long way, and a little impoliteness goes a long way in the opposite direction. $\endgroup$ – Steven Landsburg Mar 1 '13 at 20:28
  • 2
    $\begingroup$ The Todd-Coxeter coset enumeration procedure will output $|G:H|$ if it is finite, but there is no recursive upper bound for the time it will take as a function of $|G:H|$. If $|G:H|$ is infinite, then it will not halt (except in a few special cases, like subgroups of free groups). $\endgroup$ – Derek Holt Mar 1 '13 at 21:44
  • 1
    $\begingroup$ Yes in the case of $C_5\ast\mathbf{Z}$ there's such an algorithm, but it would be more fruitful to you to solve this by yourself. $\endgroup$ – YCor Mar 1 '13 at 21:45

Your Answer

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

Browse other questions tagged or ask your own question.