Computing fundamental domains for Fuchsian groups
Journal de théorie des nombres de Bordeaux, Volume 21 (2009) no. 2, p. 467-489

We exhibit an algorithm to compute a Dirichlet domain for a Fuchsian group Γ with cofinite area. As a consequence, we compute the invariants of Γ, including an explicit finite presentation for Γ.

Nous présentons un algorithme pour calculer un domaine de Dirichlet pour un groupe Fuchsien Γ, avec aire cofinie. Comme conséquence, nous calculons les invariants de Γ, ainsi qu’une présentation finie explicite pour Γ.

@article{JTNB_2009__21_2_467_0,
     author = {Voight, John},
     title = {Computing fundamental domains  for Fuchsian groups},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux 1},
     volume = {21},
     number = {2},
     year = {2009},
     pages = {467-489},
     doi = {10.5802/jtnb.683},
     mrnumber = {2541438},
     zbl = {pre05620663},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2009__21_2_467_0}
}
Voight, John. Computing fundamental domains  for Fuchsian groups. Journal de théorie des nombres de Bordeaux, Volume 21 (2009) no. 2, pp. 467-489. doi : 10.5802/jtnb.683. http://www.numdam.org/item/JTNB_2009__21_2_467_0/

[1] M. Alsina and P. Bayer, Quaternion orders, quadratic forms, and Shimura curves. CRM monograph series, vol. 22, AMS, Providence, 2004. | MR 2038122 | Zbl 1073.11040

[2] A. Beardon, The geometry of discrete groups. Grad. Texts in Math., vol. 91, Springer-Verlag, New York, 1995. | MR 1393195 | Zbl 0528.30001

[3] H.-J. Boehm, The constructive reals as a Java library. J. Log. Algebr. Program. 64 (2005), 3–11. | MR 2137732 | Zbl 1080.68005

[4] W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. I. The user language.. J. Symbolic Comput., 24 (3–4), 1997, 235–265. | MR 1484478 | Zbl 0898.68039

[5] K. S. Brown, Cohomology of groups. Grad. Texts in Math., vol. 87, Springer-Verlag, New York, 1982. | MR 672956 | Zbl 0584.20036

[6] H. Cohen, A course in computational algebraic number theory. Grad. Texts in Math., vol. 138, Springer-Verlag, New York, 1993. | MR 1228206 | Zbl 0786.11071

[7] H. Cohen, Advanced topics in computational algebraic number theory. Grad. Texts in Math., vol. 193, Springer-Verlag, Berlin, 2000. | MR 1728313 | Zbl 0977.11056

[8] D. Cox, J. Little, and D. O’Shea, Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra, 2nd ed. Undergrad. Texts in Math., Springer-Verlag, New York, 1997. | MR 1417938 | Zbl 0861.13012

[9] T. Dokchitser, Computing special values of motivic L-functions. Experiment. Math. 13 (2004), no. 2, 137–149. | MR 2068888 | Zbl 1139.11317

[10] U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp. 44 (1985), no. 170, 463–471. | MR 777278 | Zbl 0556.10022

[11] L. R. Ford, Automorphic functions, 2nd. ed. Chelsea, New York, 1972.

[12] I.M. Gel’fand, M.I. Graev, and I.I. Pyatetskii-Shapiro, Representation theory and automorphic functions. Trans. K.A. Hirsch, Generalized Functions, vol. 6, Academic Press, Boston, 1990. | MR 1071179 | Zbl 0718.11022

[13] P. Gowland and D. Lester, A survey of exact computer arithmetic. In Computability and Complexity in Analysis, Lecture Notes in Computer Science, eds. Blanck et al., vol. 2064, Springer, 2001, 30–47. | Zbl 0985.65043

[14] M. Imbert, Calculs de présentations de groupes fuchsiens via les graphes rubanés. Expo. Math. 19 (2001), no. 3, 213–227. | MR 1852073 | Zbl 0988.20035

[15] S. Johansson, On fundamental domains of arithmetic Fuchsian groups. Math. Comp 69 (2000), no. 229, 339–349. | MR 1665958 | Zbl 0937.11016

[16] S. Katok, Fuchsian groups. Chicago Lect. in Math., U. of Chicago Press, Chicago, 1992. | MR 1177168 | Zbl 0753.30001

[17] S. Katok, Reduction theory for Fuchsian groups. Math. Ann. 273 (1986), no. 3, 461–470. | MR 824433 | Zbl 0561.30036

[18] D. R. Kohel and H. A. Verrill, Fundamental domains for Shimura curves. Les XXIIèmes Journées Arithmetiques (Lille, 2001), J. Théor. Nombres Bordeaux 15 (2003), no. 1, 205–222. | Numdam | MR 2019012 | Zbl 1044.11052

[19] M.B. Pour-El and J.I. Richards, Computability in analysis and physics. Perspect. in Math. Logic, Springer, Berlin, 1989. | MR 1005942 | Zbl 0678.03027

[20] H. Shimizu, On zeta functions of quaternion algebras. Ann. of Math. (2) 81 (1965), 166–193. | MR 171771 | Zbl 0201.37903

[21] H. Verrill, Subgroups of PSL 2 (). Handbook of Magma Functions, eds. John Cannon and Wieb Bosma, Edition 2.14 (2007).

[22] M.-F. Vignéras, Arithmétique des algèbres de quaternions. Lect. Notes in Math., vol. 800, Springer, Berlin, 1980. | MR 580949 | Zbl 0422.12008

[23] J. Voight, Quadratic forms and quaternion algebras: algorithms and arithmetic. Ph.D. Thesis, University of California, Berkeley, 2005.

[24] K. Weihrauch, An introduction to computable analysis. Springer-Verlag, New York, 2000. | MR 1795407 | Zbl 0956.68056