Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Authors: Jinxiang Zeng and Linsheng Yin
Journal: Math. Comp. 84 (2015), 1469-1488
MSC (2010): Primary 11F30, 11G20, 11Y16, 14Q05, 14H05
DOI: https://doi.org/10.1090/S0025-5718-2014-02892-5
Published electronically: October 28, 2014
MathSciNet review: 3315517
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (88h:11036), https://doi.org/10.1215/S0012-7094-86-05346-9
  • [2] 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 (2007f:14020)
  • [3] 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 (2011i:11056), https://doi.org/10.1090/S0025-5718-10-02332-X
  • [4] 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, https://doi.org/10.1006/jsco.1996.0125
  • [5] J. Bosman, Explicit computations with modular Galois representations, Ph.D. thesis, Universiteit Leiden, December 2008. Available on https://openaccess.leidenuniv.nl/
  • [6] 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 (2009k:11207), https://doi.org/10.1090/S0025-5718-08-02066-8
  • [7] 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/
  • [8] C. Citro and A. Ghitza, Computing level one Hecke eigensystems $ (\textup {mod}~p)$, LMS J. Comput. Math. 16 (2013), 246-270. MR 3104940
  • [9] 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 (2010e:14019), https://doi.org/10.1016/j.jalgebra.2008.09.032
  • [10] M. Derickx, Torsion points on elliptic curves and gonalities of modular curves, Master thesis, Universiteit Leiden, 2012. Available on http://www.mderickx.nl/
  • [11] Fred Diamond and Jerry Shurman, A First Course in Modular Forms, Graduate Texts in Mathematics, vol. 228, Springer-Verlag, New York, 2005. MR 2112196 (2006f:11045)
  • [12] Tim Dokchitser and Vladimir Dokchitser, Identifying Frobenius elements in Galois groups, Algebra Number Theory 7 (2013), no. 6, 1325-1352. MR 3107565, https://doi.org/10.2140/ant.2013.7.1325
  • [13] 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; Edited by Bas Edixhoven and Jean-Marc Couveignes. MR 2849700
  • [14] 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 (91i:11060), https://doi.org/10.1215/S0012-7094-90-06119-8
  • [15] 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 (82k:10059), https://doi.org/10.2307/2374229
  • [16] F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425-445. MR 1890579 (2003j:14032), https://doi.org/10.1006/jsco.2001.0513
  • [17] M. van Hoeij, Low Degree Places on the Modular Curve $ X_1(N)$, http://arxiv.org/abs/1202.4355v2
  • [18] 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 (96h:14077), https://doi.org/10.1006/jsco.1994.1063
  • [19] 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 (83e:10033a), https://doi.org/10.2307/1999771
  • [20] Naomi Jochnowitz, Congruences between systems of eigenvalues of modular forms, Trans. Amer. Math. Soc. 270 (1982), no. 1, 269-285. MR 642341 (83e:10033b), https://doi.org/10.2307/1999772
  • [21] Chandrashekhar Khare, Serre's modularity conjecture: the level one case, Duke Math. J. 134 (2006), no. 3, 557-589. MR 2254626 (2007e:11060), https://doi.org/10.1215/S0012-7094-06-13434-8
  • [22] Kamal Khuri-Makdisi, Asymptotically fast group operations on Jacobians of general curves, Math. Comp. 76 (2007), no. 260, 2213-2239 (electronic). MR 2336292 (2009a:14072), https://doi.org/10.1090/S0025-5718-07-01989-8
  • [23] 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 (2011d:11091), https://doi.org/10.1090/S0025-5718-09-02303-5
  • [24] 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 (56 #5506)
  • [25] N. Mascot, Computing modular Galois representations, Rend. Circ. Mat. Palermo (2) 62 (2013), no. 3, 451-476. MR 3118315
  • [26] 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 (electronic). Kazuya Kato's fiftieth birthday. MR 2046611 (2005a:11069)
  • [27] 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 (83k:12011)
  • [28] 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 (56 #8497)
  • [29] 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 (88h:11031), https://doi.org/10.1007/BFb0072985
  • [30] Andrew V. Sutherland, Constructing elliptic curves over finite fields with prescribed torsion, Math. Comp. 81 (2012), no. 278, 1131-1147. MR 2869053 (2012m:11079), https://doi.org/10.1090/S0025-5718-2011-02538-X
  • [31] 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 (96a:14033), https://doi.org/10.1007/3-540-58691-1_60

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11F30, 11G20, 11Y16, 14Q05, 14H05

Retrieve articles in all journals with MSC (2010): 11F30, 11G20, 11Y16, 14Q05, 14H05


Additional Information

Jinxiang Zeng
Affiliation: Department of Mathematical Science, Tsinghua University, Beijing 100084, People’s Republic of China
Email: cengjx09@mails.tsinghua.edu.cn

Linsheng Yin
Affiliation: Department of Mathematical Science, Tsinghua University, Beijing 100084, People’s Republic of China
Email: lsyin@math.tsinghua.edu.cn

DOI: https://doi.org/10.1090/S0025-5718-2014-02892-5
Keywords: Modular forms, Hecke algebra, modular curves, elliptic curves, Jacobian
Received by editor(s): May 17, 2013
Received by editor(s) in revised form: September 17, 2013
Published electronically: October 28, 2014
Additional Notes: This work was partially supported by NSFC grant No.11271212.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society