12
$\begingroup$

In this famous paper by Borel and Harish-Chandra, Arithmetic Subgroups of Algebraic Groups, it is proved that, in characterisitic zero, arithmetic groups are finitely presented. I have an extremely vague idea of how the argument goes, but I was wondering if anything was known about how this would be done algorithmically. To be specific, (following work by Grunewald and Segal) an arithmetic group $\Gamma \leq \mathrm{GL}(n,\mathbb C)$ is said to be expicitly given if we have the following data:

  • a system $S$ of polynomial equations defining the algebraic group $V(S)= \mathcal G$ (which contains $\Gamma$),
  • a known upper bound $k$ for the index $[\mathrm{GL}(n,\mathbb Z)\cap \mathcal G:\Gamma]$, and
  • a procedure which given $g \in \mathrm{GL}(n,\mathbb Z)\cap \mathcal G$ will decide if $g \in \Gamma$.

Then my question is: If $\Gamma$ is an explicitly given arithmetic group, is it possible to compute the presentation of $\Gamma$ or, even better, to get the orbihedron whose fundamental group is $\Gamma$, which is used in the construction of Borel and Harish-Chandra?

If there is a reference for this, or if this is known to be impossible, that would be awesome!

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I believe their proof "computes" a presentation but there is no primitive recursive bound in how long their algorithm takes. $\endgroup$
    – Benjamin Steinberg
    Commented Sep 28, 2018 at 1:24
  • $\begingroup$ Hi! Thanks for that! At the moment I'm only interested in theoretical computability. So what you're saying is that the proof is constructive and one could conceivably go through each step and there are no anticipated obstacles to computability. $\endgroup$
    – NWMT
    Commented Sep 28, 2018 at 11:19
  • $\begingroup$ That's what I believe but there are bigger experts than me. $\endgroup$
    – Benjamin Steinberg
    Commented Sep 28, 2018 at 11:30
  • $\begingroup$ Actually I just had a look at the Grunewald-Segal paper in Annals, I quote: "Algorithm B does no more than laboriously make each step of their [Borel & Harish-Chandra] constructive." However, the output of Algorithm B s just a set of generating matrices for the arithmetic group $\Gamma$. $\endgroup$
    – NWMT
    Commented Sep 28, 2018 at 12:57
  • $\begingroup$ I haven't looked at the paper in years. My belief is everything in the paper is effective but I don't remember if they looked specifically at computing a presentation. $\endgroup$
    – Benjamin Steinberg
    Commented Sep 28, 2018 at 14:46

1 Answer 1

Reset to default
5
$\begingroup$

You might want to study the work of Detinko, Flannery, and co-authors. For example:

Detinko, A.; Flannery, D. L.; Hulpke, A., Zariski density and computing in arithmetic groups, ZBL06825254.

Detinko, A. S.; Flannery, D. L.; Hulpke, A., Algorithms for arithmetic groups with the congruence subgroup property., J. Algebra 421, 234-259 (2015). ZBL1319.20040.

(moving comment up to the main body): They find things like the congruence depth (the index of the principal congruence subgroup), so the co-volume, and then (at least in the special linear and symplectic case you can use the Minkowski model (the PSD cone) of the symmetric space to construct the fundamental polyhedron (the bound tells you when to stop), so pretty much what you are asking for.

In the real hyperbolic case, there is the very interesting paper of Mark and Paupert:

Presentations for cusped arithmetic hyperbolic lattices, by Alice Mark and Julien Paupert.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Though the two papers you cite have something to do with computational questions involving arithmetic groups, they do not appear to have anything to do with the specific question the OP asked. $\endgroup$
    – Andy Putman
    Commented Sep 28, 2018 at 16:24
  • $\begingroup$ Right, I saw those results. They actually go further and present algorithms that actually work on computers, but only for restricted classes. That being said I don't think they compute presentations; I could have misunderstood their results though, since I'm not an expert. $\endgroup$
    – NWMT
    Commented Sep 28, 2018 at 19:20
  • $\begingroup$ @NWMT I should probably move this to the main answer, but the point is this: using their methods you can bound the volume (since you can find the congruence depth), and then (at least in the special linear and symplectic case you can use the Minkowski model (the PSD cone) of the symmetric space to construct the fundamental polyhedron (the bound tells you when to stop), so pretty much what you are asking for. $\endgroup$
    – Igor Rivin
    Commented Sep 28, 2018 at 19:56
  • $\begingroup$ Someone downvoted this answer? $\endgroup$
    – Igor Rivin
    Commented Sep 28, 2018 at 19:57
  • $\begingroup$ @NWMT (and of course the last reference has presentations in the title, so does compute them (also practically). $\endgroup$
    – Igor Rivin
    Commented Sep 28, 2018 at 19:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .