Matrix groups and presentation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T22:15:36Z http://mathoverflow.net/feeds/question/119410 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119410/matrix-groups-and-presentation Matrix groups and presentation expmat 2013-01-20T16:27:33Z 2013-01-29T18:56:37Z <p>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?</p> <p>More precisely, the algorithm should tell me:</p> <p>1) whether the group admits a finite presentation or not;</p> <p>2) in case it does admit a finite presentation, it should exhibit one such presentation.</p> <p>(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.)</p> http://mathoverflow.net/questions/119410/matrix-groups-and-presentation/120038#120038 Answer by Misha for Matrix groups and presentation Misha 2013-01-27T17:14:47Z 2013-01-29T18:56:37Z <p>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. <a href="http://www.cems.uvm.edu/~jvoight/articles/funddom-jtnb-fixederrata.pdf" rel="nofollow">here</a> 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 <a href="http://mathoverflow.net/questions/109967/algorithm-to-test-for-discrete-or-quasi-fuchsian-subgroups-of-psl2-c" rel="nofollow">here</a>. </p> <p>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. </p> <p>Edit: Look <a href="http://mathoverflow.net/questions/102932/what-finitely-presented-groups-embed-into-gl-2/103615#103615" rel="nofollow">here</a>, <a href="http://mathoverflow.net/questions/107082/decision-problem-for-finitely-generated-subgroups/107124#107124" rel="nofollow">here</a> and <a href="http://mathoverflow.net/questions/47961/undecidability-in-matrix-groups/90840#90840" rel="nofollow">here</a> for further indications of how difficult this problem is. </p> <p>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 <a href="http://mathoverflow.net/questions/109967/algorithm-to-test-for-discrete-or-quasi-fuchsian-subgroups-of-psl2-c" rel="nofollow">here</a>. 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). </p> <p>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 <a href="http://www.em-consulte.com/en/article/240370" rel="nofollow">here</a>) is the current state of the art in this regard. </p>