## 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. – HW Nov 29 2011 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 2011 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 2011 at 11:41 @David: To find the generators of the intersection, you can use the Schreier lemma: en.wikipedia.org/wiki/Schreier's_subgroup_lemma – Mark Sapir Nov 29 2011 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 2011 at 12:02