On the computation of modular forms on noncongruence subgroups

Berghaus, David; Monien, Hartmut; Radchenko, Danylo

doi:10.1090/mcom/3903

On the computation of modular forms on noncongruence subgroups
HTML articles powered by AMS MathViewer

by David Berghaus, Hartmut Monien and Danylo Radchenko;

Math. Comp. 93 (2024), 1399-1425

DOI: https://doi.org/10.1090/mcom/3903

Published electronically: October 30, 2023

HTML | PDF | Request permission

Abstract:

We present two approaches that can be used to compute modular forms on noncongruence subgroups. The first approach uses Hejhal’s method for which we improve the arbitrary precision solving techniques so that the algorithm becomes about up to two orders of magnitude faster in practical computations. This allows us to obtain high precision numerical estimates of the Fourier coefficients from which the algebraic expressions can be identified using the LLL algorithm. The second approach is restricted to genus zero subgroups and uses efficient methods to compute the Belyi map from which the modular forms can be constructed.

References

A. Abdelfattah, H. Anzt, E. G. Boman, E. Carson, T. Cojean, J. Dongarra, A. Fox, M. Gates, N. J. Higham, X. S. Li, J. Loe, P. Luszczek, S. Pranesh, S. Rajamanickam, T. Ribizel, B. F. Smith, K. Swirydowicz, S. Thomas, S. Tomov, Y. M. Tsai, and U. M. Yang. A survey of numerical linear algebra methods utilizing mixed-precision arithmetic. The International Journal of High Performance Computing Applications, 35(4):344–369, 2021.
A. O. L. Atkin and H. P. F. Swinnerton-Dyer, Modular forms on noncongruence subgroups, Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968) Proc. Sympos. Pure Math., Vol. XIX, Amer. Math. Soc., Providence, RI, 1971, pp. 1–25. MR 337781
G. V. Belyĭ, A new proof of the three-point theorem, Mat. Sb. 193 (2002), no. 3, 21–24 (Russian, with Russian summary); English transl., Sb. Math. 193 (2002), no. 3-4, 329–332. MR 1913596, DOI 10.1070/SM2002v193n03ABEH000633
G. V. Belyĭ, Galois extensions of a maximal cyclotomic field, Izv. Akad. Nauk SSSR Ser. Mat. 43 (1979), no. 2, 267–276, 479 (Russian). MR 534593
Gabriel Berger, Hecke operators on noncongruence subgroups, C. R. Acad. Sci. Paris Sér. I Math. 319 (1994), no. 9, 915–919 (English, with English and French summaries). MR 1302789
D. Berghaus, H. Monien, and D. Radchenko, A database of modular forms on noncongruence subgroups, 2023.
Andrew R. Booker, Andreas Strömbergsson, and Akshay Venkatesh, Effective computation of Maass cusp forms, Int. Math. Res. Not. , posted on (2006), Art. ID 71281, 34. MR 2249995, DOI 10.1155/IMRN/2006/71281
R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 520733, DOI 10.1145/322092.322099
Richard P. Brent and Paul Zimmermann, Modern computer arithmetic, Cambridge Monographs on Applied and Computational Mathematics, vol. 18, Cambridge University Press, Cambridge, 2011. MR 2760886
F. Calegari, V. Dimitrov, and Y. Tang, The unbounded denominators conjecture, 2021.
Erin Carson and Nicholas J. Higham, A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems, SIAM J. Sci. Comput. 39 (2017), no. 6, A2834–A2856. MR 3732948, DOI 10.1137/17M1122918
William Yun Chen, Moduli interpretations for noncongruence modular curves, Math. Ann. 371 (2018), no. 1-2, 41–126. MR 3788845, DOI 10.1007/s00208-017-1575-6
James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1
David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
James Demmel, Yozo Hida, William Kahan, Xiaoye S. Li, Sonil Mukherjee, and E. Jason Riedy, Error bounds from extra-precise iterative refinement, ACM Trans. Math. Software 32 (2006), no. 2, 325–351. MR 2272365, DOI 10.1145/1141885.1141894
Andrew Fiori and Cameron Franc, The unbounded denominators conjecture for the noncongruence subgroups of index 7, J. Number Theory 240 (2022), 611–640. MR 4458253, DOI 10.1016/j.jnt.2021.11.014
I. Gohberg and V. Olshevsky, Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl. 202 (1994), 163–192. MR 1288487, DOI 10.1016/0024-3795(94)90189-9
The PARI Group, Pari/gp version 2.13.2, http://pari.math.u-bordeaux.fr/, 2021, [Online; accessed 22 March 2022].
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Array programming with NumPy. Nature, 585(7825):357–362, Sept. 2020.
Dennis A. Hejhal, On eigenfunctions of the Laplacian for Hecke triangle groups, Emerging applications of number theory (Minneapolis, MN, 1996) IMA Vol. Math. Appl., vol. 109, Springer, New York, 1999, pp. 291–315. MR 1691537, DOI 10.1007/978-1-4612-1544-8_{1}1
Dennis A. Hejhal, On eigenvalues of the Laplacian for Hecke triangle groups, Zeta functions in geometry (Tokyo, 1990) Adv. Stud. Pure Math., vol. 21, Kinokuniya, Tokyo, 1992, pp. 359–408. MR 1210796, DOI 10.2969/aspm/02110359
Tim Hsu, Identifying congruence subgroups of the modular group, Proc. Amer. Math. Soc. 124 (1996), no. 5, 1351–1359. MR 1343700, DOI 10.1090/S0002-9939-96-03496-X
Fredrik Johansson, A fast algorithm for reversion of power series, Math. Comp. 84 (2015), no. 291, 475–484. MR 3266971, DOI 10.1090/S0025-5718-2014-02857-3
Fredrik Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput. 66 (2017), no. 8, 1281–1292. MR 3681746, DOI 10.1109/TC.2017.2690633
F. Johansson, Faster arbitrary-precision dot product and matrix multiplication, In 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH), pp. 15–22, 2019.
Ian Kiming, Matthias Schütt, and Helena A. Verrill, Lifts of projective congruence groups, J. Lond. Math. Soc. (2) 83 (2011), no. 1, 96–120. MR 2763946, DOI 10.1112/jlms/jdq062
Michael Klug, Michael Musty, Sam Schiavone, and John Voight, Numerical calculation of three-point branched covers of the projective line, LMS J. Comput. Math. 17 (2014), no. 1, 379–430. MR 3356040, DOI 10.1112/S1461157014000084
Chris Kurth and Ling Long, On modular forms for some noncongruence subgroups of $\textrm {SL}_2(\Bbb Z)$. II, Bull. Lond. Math. Soc. 41 (2009), no. 4, 589–598. MR 2521354, DOI 10.1112/blms/bdp061
A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534.
Wen-Ching Winnie Li, Ling Long, and Zifeng Yang, Modular forms for noncongruence subgroups, Q. J. Pure Appl. Math. 1 (2005), no. 1, 205–221. MR 2155139, DOI 10.4310/PAMQ.2005.v1.n1.a9
LMFDB Collaboration, The L-functions and modular forms database, http://www.lmfdb.org, 2022, [Online; accessed 22 March 2022].
M. H. Millington, Subgroups of the classical modular group, J. London Math. Soc. (2) 1 (1969), 351–357. MR 244160, DOI 10.1112/jlms/s2-1.1.351
H. Monien, The sporadic group j2, hauptmodul and belyi map, 2017, arXiv:1703.05200.
H. Monien, The sporadic group co3, hauptmodul and belyi map, 2018, arXiv:1802.06923.
Michael Musty, Sam Schiavone, Jeroen Sijsling, and John Voight, A database of Belyi maps, Proceedings of the Thirteenth Algorithmic Number Theory Symposium, Open Book Ser., vol. 2, Math. Sci. Publ., Berkeley, CA, 2019, pp. 375–392. MR 3952023
M. Richards, Computing covering maps for subgroups of $\gamma (1)$ with genus $\geq 1$, Ph.D. thesis, University of Oxford, 1995.
S. M. Rump, Approximate inverses of almost singular matrices still contain useful information, Technical Report 90.1, Hamburg University of Technology, 1990.
Siegfried M. Rump, Inversion of extremely ill-conditioned matrices in floating-point, Japan J. Indust. Appl. Math. 26 (2009), no. 2-3, 249–277. MR 2589475, DOI 10.1007/BF03186534
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
B. Selander and A. Strömbergsson, Sextic coverings of genus two which are branched at three points, Preprint (2003), http://www2.math.uu.se/~astrombe/papers/papers.html.
J.-P. Serre, A course in arithmetic, Graduate Texts in Mathematics, No. 7, Springer-Verlag, New York-Heidelberg, 1973. Translated from the French. MR 344216, DOI 10.1007/978-1-4684-9884-4
J. Sijsling and J. Voight, On computing Belyi maps, Numéro consacré au trimestre “Méthodes arithmétiques et applications”, automne 2013, Publ. Math. Besançon Algèbre Théorie Nr., vol. 2014/1, Presses Univ. Franche-Comté, Besançon, 2014, pp. 73–131 (English, with English and French summaries). MR 3362631
W. A. Stein, F. Strömberg, S. Ehlen, and N. Skoruppa et. al., Purplesage (psage), https://github.com/fredstro/psage, 2022, [Online; accessed 22 March 2022].
W. A. Stein et. al., Sage mathematics software (version 9.2), https://www.sagemath.org/, 2021, [Online; accessed 22 March 2022].
W. W. Stothers, Level and index in the modular group, Proc. Roy. Soc. Edinburgh Sect. A 99 (1984), no. 1-2, 115–126. MR 781088, DOI 10.1017/S0308210500025993
Fredrik Strömberg, Maass waveforms on $(\Gamma _0(N),\chi )$ (computational aspects), Hyperbolic geometry and applications in quantum chaos and cosmology, London Math. Soc. Lecture Note Ser., vol. 397, Cambridge Univ. Press, Cambridge, 2012, pp. 187–228. MR 2895234
Fredrik Strömberg, Noncongruence subgroups and Maass waveforms, J. Number Theory 199 (2019), 436–493. MR 3926206, DOI 10.1016/j.jnt.2018.11.020
Holger Then, Maass cusp forms for large eigenvalues, Math. Comp. 74 (2005), no. 249, 363–381. MR 2085897, DOI 10.1090/S0025-5718-04-01658-8
P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: fundamental algorithms for scientific computing in Python, Nature Methods 17 (2020), 261–272.
John Voight and John Willis, Computing power series expansions of modular forms, Computations with modular forms, Contrib. Math. Comput. Sci., vol. 6, Springer, Cham, 2014, pp. 331–361. MR 3381459, DOI 10.1007/978-3-319-03847-6_{1}3
J. H. Wilkinson, Progress report on the Automatic Computing Engine, Report MA/17/1024, 1948.