Take the 2-minute tour ×

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.)

share|improve this question
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 '13 at 17:20
The question was updated to respond to Sapir's pickyness... ;) –  expmat Jan 20 '13 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 '13 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 '13 at 11:29
@Misha: really? How can I see it in that case? Do you have a reference for it? –  expmat Jan 26 '13 at 23:41
show 3 more comments

2 Answers

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.

share|improve this answer
add comment

This question is most interesting for infinite groups. However, if $G$ is a finite (finitely generated) subgroup of ${\rm GL}_2(K)$, then I claim that there is an algorithm to produce a presentation for $G$. Consider the three mutually exclusive cases where $G$ is (1) primitive, (2) imprimitive, or (3) irreducible.

First, the finite primitive subgroups $G$ of ${\rm GL}_2({\mathbb C})$ (I think) have the form $G=Z(G)H$ where $Z(G)$ is finite cyclic and $H$ is isomorphic to $\langle \ell,m,n\rangle:=\langle r,s,t\mid r^\ell=s^m=t^n=rst\rangle$ where $\langle \ell,m,n\rangle= \langle2,3,3 \rangle\cong{\rm SL}_2(3), \langle 2,3,4\rangle$, or $\langle2,3,5\rangle\cong{\rm SL}_2(5)$. Second, an imprimitive $G$ has a (finite) abelian normal subgroup of index 2; examples include the generalized quaternion groups $\langle 2,2,n\rangle$ and the dihedral groups $(2,2,n)$. In the third case, each generator for $G$ has a common 1-dimensional eigenspace. I claim that there is enough information here to provide an algorithm to produce a finite presentation for $G$. I may have made an error as this is a quick post.

share|improve this answer
add comment

Your Answer


