Class polynomials for nonholomorphic modular functions

Abstract

We give algorithms for computing the singular moduli of suitable nonholomorphic modular functions F(z). By combining the theory of isogeny volcanoes with a beautiful observation of Masser concerning the nonholomorphic Eisenstein series E_2*(z), we obtain CRT-based algorithms that compute the class polynomials H_D(F;x), whose roots are the discriminant D singular moduli for F(z). By applying these results to a specific weak Maass form F_p(z), we obtain a CRT-based algorithm for computing partition class polynomials, a sequence of polynomials whose traces give the partition numbers p(n). Under the GRH, the expected running time of this algorithm is O(n^{5/2+o(1)}). Key to these results is a fast CRT-based algorithm for computing the classical modular polynomial Phi_m(X,Y) that we obtain by extending the isogeny volcano approach previously developed for prime values of m.

Minor revision to reflect referee comments, 23 pages

References in corpus (2)

• Isogeny volcanoes
• Efficient implementation of the Hardy-Ramanujan-Rademacher formula

Cited by in corpus (10)

• Isogeny volcanoes
• Flux Vacua and Modularity for ${\mathbb{Z}}_2$ Symmetric Calabi-Yau Manifolds
• Modular invariants and isogenies
• On class invariants for non-holomorphic modular functions and a question of Bruinier and Ono
• Explicit classification of isogeny graphs of rational elliptic curves
• What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I
• An explicit formula for the extended Gross-Keating datum of a quadratic form
• Iwasawa Invariants for elliptic curves over ${\mathbb{Z}}_p$-extensions and Kida's Formula
• Class invariants for certain non-holomorphic modular functions
• Computation of Gross-Keating invariants