# Identifying finite-index subgroups of SL2Z from generators

(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?

• 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. – user6976 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.
• 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