Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.