On the computation of coefficients of modular forms: The reduction modulo 𝑝 approach

Zeng, Jinxiang; Yin, Linsheng

doi:10.1090/S0025-5718-2014-02892-5

On the computation of coefficients of modular forms: The reduction modulo $p$ approach
HTML articles powered by AMS MathViewer

by Jinxiang Zeng and Linsheng Yin PDF

Math. Comp. 84 (2015), 1469-1488 Request permission

Abstract:

In this paper, we present a probabilistic algorithm to compute the coefficients of modular forms of level one. Focusing on Ramanujan’s tau function, we give the explicit complexity of the algorithm. From a practical viewpoint, the algorithm is particularly well suited for implementations.

References

Avner Ash and Glenn Stevens, Modular forms in characteristic $l$ and special values of their $L$-functions, Duke Math. J. 53 (1986), no. 3, 849–868. MR 860675, DOI 10.1215/S0012-7094-86-05346-9
Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2162716
Houria Baaziz, Equations for the modular curve $X_1(N)$ and models of elliptic curves with torsion points, Math. Comp. 79 (2010), no. 272, 2371–2386. MR 2684370, DOI 10.1090/S0025-5718-10-02332-X
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
J. Bosman, Explicit computations with modular Galois representations, Ph.D. thesis, Universiteit Leiden, December 2008. Available on https://openaccess.leidenuniv.nl/
A. Bostan, F. Morain, B. Salvy, and É. Schost, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), no. 263, 1755–1778. MR 2398793, DOI 10.1090/S0025-5718-08-02066-8
P.J. Bruin, Modular curves, Arakelov theory, algorithmic applications, Ph.D. thesis, Universiteit Leiden, 2010. Available on http://www.math.leidenuniv.nl/en/theses/PhD/
Craig Citro and Alexandru Ghitza, Computing level one Hecke eigensystems (mod $p$), LMS J. Comput. Math. 16 (2013), 246–270. MR 3104940, DOI 10.1112/S1461157013000132
J.-M. Couveignes, Linearizing torsion classes in the Picard group of algebraic curves over finite fields, J. Algebra 321 (2009), no. 8, 2085–2118. MR 2501511, DOI 10.1016/j.jalgebra.2008.09.032
M. Derickx, Torsion points on elliptic curves and gonalities of modular curves, Master thesis, Universiteit Leiden, 2012. Available on http://www.mderickx.nl/
Fred Diamond and Jerry Shurman, A first course in modular forms, Graduate Texts in Mathematics, vol. 228, Springer-Verlag, New York, 2005. MR 2112196
Tim Dokchitser and Vladimir Dokchitser, Identifying Frobenius elements in Galois groups, Algebra Number Theory 7 (2013), no. 6, 1325–1352. MR 3107565, DOI 10.2140/ant.2013.7.1325
Bas Edixhoven and Jean-Marc Couveignes (eds.), Computational aspects of modular forms and Galois representations, Annals of Mathematics Studies, vol. 176, Princeton University Press, Princeton, NJ, 2011. How one can compute in polynomial time the value of Ramanujan’s tau at a prime. MR 2849700, DOI 10.1515/9781400839001
Benedict H. Gross, A tameness criterion for Galois representations associated to modular forms (mod $p$), Duke Math. J. 61 (1990), no. 2, 445–517. MR 1074305, DOI 10.1215/S0012-7094-90-06119-8
E. Grosswald, On Burgess’ bound for primitive roots modulo primes and an application to $\Gamma (p)$, Amer. J. Math. 103 (1981), no. 6, 1171–1183. MR 636957, DOI 10.2307/2374229
F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
M. van Hoeij, Low Degree Places on the Modular Curve $X_1(N)$, http://arxiv.org/abs/1202.4355v2
Ming-Deh Huang and Doug Ierardi, Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve, J. Symbolic Comput. 18 (1994), no. 6, 519–539. MR 1334660, DOI 10.1006/jsco.1994.1063
Naomi Jochnowitz, A study of the local components of the Hecke algebra mod $l$, Trans. Amer. Math. Soc. 270 (1982), no. 1, 253–267. MR 642340, DOI 10.1090/S0002-9947-1982-0642340-0
Naomi Jochnowitz, Congruences between systems of eigenvalues of modular forms, Trans. Amer. Math. Soc. 270 (1982), no. 1, 269–285. MR 642341, DOI 10.1090/S0002-9947-1982-0642341-2
Chandrashekhar Khare, Serre’s modularity conjecture: the level one case, Duke Math. J. 134 (2006), no. 3, 557–589. MR 2254626, DOI 10.1215/S0012-7094-06-13434-8
Kamal Khuri-Makdisi, Asymptotically fast group operations on Jacobians of general curves, Math. Comp. 76 (2007), no. 260, 2213–2239. MR 2336292, DOI 10.1090/S0025-5718-07-01989-8
Chang Heon Kim and Ja Kyung Koo, Generators of function fields of the modular curves $X_1(5)$ and $X_1(6)$, Math. Comp. 79 (2010), no. 270, 1047–1066. MR 2600555, DOI 10.1090/S0025-5718-09-02303-5
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
Nicolas Mascot, Computing modular Galois representations, Rend. Circ. Mat. Palermo (2) 62 (2013), no. 3, 451–476. MR 3118315, DOI 10.1007/s12215-013-0136-4
Hyunsuk Moon and Yuichiro Taguchi, Refinement of Tate’s discriminant bound and non-existence theorems for mod $p$ Galois representations, Doc. Math. Extra Vol. (2003), 641–654. Kazuya Kato’s fiftieth birthday. MR 2046611
Jean-Pierre Serre, Quelques applications du théorème de densité de Chebotarev, Inst. Hautes Études Sci. Publ. Math. 54 (1981), 323–401 (French). MR 644559
J.-P. Serre, Modular forms of weight one and Galois representations, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 193–268. MR 0450201
Jacob Sturm, On the congruence of modular forms, Number theory (New York, 1984–1985) Lecture Notes in Math., vol. 1240, Springer, Berlin, 1987, pp. 275–280. MR 894516, DOI 10.1007/BFb0072985
Andrew V. Sutherland, Constructing elliptic curves over finite fields with prescribed torsion, Math. Comp. 81 (2012), no. 278, 1131–1147. MR 2869053, DOI 10.1090/S0025-5718-2011-02538-X
Emil J. Volcheck, Computing in the Jacobian of a plane algebraic curve, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 221–233. MR 1322725, DOI 10.1007/3-540-58691-1_{6}0