show/hide this revision's text 2 added 1803 characters in body
here: http://mathoverflow.net/questions/109967/algorithm-to-test-for-discrete-or-quasi-fuchsian-subgroups-of-psl2-c.

As far as I know, it is an open problem to determine what happens for subgroups of Hilbert modular groups $SL(2, O)$, where $O$ is, say, ring of integers of a totally real quadratic number field. It is not even known if all finitely generated subgroups are finitely presented. Conjecturally, this is not the case.

Edit: Look here, here and here for further indications of how difficult this problem is.

In the case of discrete subgroups of $PSL(2, {\mathbb C})$ there is a glimmer of hope for computing presentations (f.g. discrete subgroups are known to be finitely-presentable). Namely, in all known examples, a discrete f.g. subgroup $\Gamma$ of $PSL(2, K)\subset PSL(2, {\mathbb C})$ is either geometrically finite (in which case there is an algorithm for computing presentation) or is a geometrically infinite subgroup of a lattice in $PSL(2, {\mathbb C})$. In the latter case, the subgroup $\Gamma$ is isomorphic to a Fuchsian group and $\Gamma$ is virtually normal in the ambient lattice, thus, there is an algorithm for computing a finite presentation of $\Gamma$, outlined in Agol's answer here. However, my guess is that there are also "algebraic" geometrically infinite groups which are not contained in $PSL(2,C)$-lattices (it is a known open problem).

For general arithmetic lattices (excluding, say, finite index subgroups of the group of integer points of a split algebraic group over ${\mathbb Z}$) there is only one (known) way to compute finite presentation, namely, by computing a fundamental domain or some version of it. Work of Cartwright and Steger (see here) is the current state of the art in this regard.

show/hide this revision's text 1

Suppose that $K\subset {\mathbb R}$ and that your subgroup $\Gamma$ on $PSL(2,K)$ is discrete (as a subgroup of $PSL(2,{\mathbb R})$. Then there is an algorithm for computing Dirichlet fundamental domain for $\Gamma$, which is due to Troe Jorgensen: See e.g. here for the description of the algorithm. I think, Igor Rivin even implemented this algorithm (he might be able to tell you how fast it works in practice). The key is that finitely-generated Fuchsian groups are geometrically finite and, i.e., have finitely-sided fundamental polygons. Once you have a fundamental domain, you can compute the presentation (see the same link above). However, once you get to discrete subgroups of $PSL(2,{\mathbb C})$, geometric finiteness fails and, my guess, is that the problem is again algorithmically unsolvable, see the discussion here: http://mathoverflow.net/questions/109967/algorithm-to-test-for-discrete-or-quasi-fuchsian-subgroups-of-psl2-c

As far as I know, it is an open problem to determine what happens for subgroups of Hilbert modular groups $SL(2, O)$, where $O$ is, say, ring of integers of a totally real quadratic number field. It is not even known if all finitely generated subgroups are finitely presented. Conjecturally, this is not the case.