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

(This question is reposted from math.SE, since it's sat there for a while with no answers. Apologies if it's not considered research-level, but I'm not a group theorist myself.)

Suppose I have a finite set of elements $x_1, \dots, x_n$ of the modular group $\operatorname{SL}_2(\mathbf{Z})$. Is there is an algorithm that will determine in finitely many steps whether or not the subgroup generated by $x_1, \dots, x_n$ has finite index?

share|cite|improve this question
Yes, there are many. Perhaps the most practical way is to work out a fundamental domain for the action on the hyperbolic plane, and then to see whether it has finite volume. I'm leaving this as a comment because there should be someone around who knows a reference. – HJRW Nov 29 '11 at 11:00
@HW: I did not see your comment when I typed my answer. My answer is essentially the same as yours but using a different language. – Mark Sapir Nov 29 '11 at 11:09

Yes, there is an algorithm. First find the intersection $U$ of $H=\langle x_1,..., x_n\rangle$ with the free subgroup of index 12 in $SL_2(\mathbb{Z})$ (the free group has two generators $a,b$). Let it be generated by words $u_1,...,u_m$. Consider the Stallings graph associated with $U$. It is a finite labeled graph where every edge is labeled by $a,b,a^{-1}$ or $b^{-1}$ and no two edges sharing the initial/termnal vertex have the same label. The index is finite if and only if every vertex of that graph has degree 4. See, for example, Margolis, S.; Sapir, M.; Weil, P. Closed subgroups in pro-V topologies and the extension problem for inverse automata. Internat. J. Algebra Comput. 11 (2001), no. 4, 405–445 and the references there.

share|cite|improve this answer
Thanks for this answer. I will certainly have a look at your paper with Margolis and Weil. Could I just ask you to elaborate slightly on how one calculates a generating set for the intersection $U$? – David Loeffler Nov 29 '11 at 11:41
@David: To find the generators of the intersection, you can use the Schreier lemma:'s_subgroup_lemma – Mark Sapir Nov 29 '11 at 11:58
Also most probably you can avoid finding the intersection and consider the analog of Stallings' graph for subgroups of free products. See, for example, Soma, Teruhiko, Intersection of finitely generated surface groups. J. Pure Appl. Algebra 66 (1990), no. 1, 81–95 and more recent papers by Ivanov and Ivanov-Dicks. – Mark Sapir Nov 29 '11 at 12:02

Your Answer


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

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