## Matrix groups and presentation

Suppose $K$ is a number field and I have a subgroup of $GL_2(K)$ for which I know a (finite) set of generators. Is there an algorithm that gives me a presentation of the group?

More precisely, the algorithm should tell me:

1) whether the group admits a finite presentation or not;

2) in case it does admit a finite presentation, it should exhibit one such presentation.

(For the purposes of this problem, let's assume $K$ is "computable", meaning that the computer knows a $\mathbb{Q}$-basis for it and the multiplications between those elements.)

-
 The question does not make sense because you do not explain how are the generators given", i.e. how do you represent real numbers? – Mark Sapir Jan 20 at 17:20 The question was updated to respond to Sapir's pickyness... ;) – expmat Jan 20 at 17:31 I apologize if my comment was perceived as offensive by some people. The point is that following Mark Sapir's comment (which, I admit, was valid and constructive), I updated it to make it more precise and meaningful. – expmat Jan 20 at 21:59 Expmat: If you assume that the subgroup is discrete and $K\subset {\mathbb R}$ then the answer is positive; if not then it becomes a hard problem which likely has negative answer. – Misha Jan 26 at 11:29 @Misha: really? How can I see it in that case? Do you have a reference for it? – expmat Jan 26 at 23:41

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.

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.

-