MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – YCor Mar 1 '13 at 19:51
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$. – YCor Mar 1 '13 at 19:55
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. – Steven Landsburg Mar 1 '13 at 20:28
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). – Derek Holt Mar 1 '13 at 21:44
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. – YCor Mar 1 '13 at 21:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.