## Fast evaluation of modular functions using Newton iterations and the AGM

HTML articles powered by AMS MathViewer

- by Régis Dupont PDF
- Math. Comp.
**80**(2011), 1823-1847

## Abstract:

We present an asymptotically fast algorithm for the numerical evaluation of modular functions such as the elliptic modular function $j$. Our algorithm makes use of the natural connection between the arithmetic-geometric mean (AGM) of complex numbers and modular functions. Through a detailed complexity analysis, we prove that for a given $\tau$, evaluating $N$ significative bits of $j(\tau )$ can be done in time $O(\mathcal {M}(N)\log N)$, where $\mathcal {M}(N)$ is the time complexity for the multiplication of two $N$-bit integers. However, this is only true for a*fixed*$\tau$ and the time complexity of this first algorithm greatly increases as $\mathrm {Im}(\tau )$ does. We then describe a second algorithm that achieves the same time complexity independently of the value of $\tau$ in the classical fundamental domain $\mathcal {F}$. We also show how our method can be used to evaluate other modular forms, such as the Dedekind $\eta$ function, with the same time complexity.

## References

- Harald Baier and Günter Köhler,
*How to compute the coefficients of the elliptic modular function $j(z)$*, Experiment. Math.**12**(2003), no. 1, 115–121. MR**2002678** - Jonathan M. Borwein and Peter B. Borwein,
*Pi and the AGM*, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1987. A study in analytic number theory and computational complexity; A Wiley-Interscience Publication. MR**877728** - Richard P. Brent,
*Multiple-precision zero-finding methods and the complexity of elementary function evaluation*, Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975) Academic Press, New York, 1976, pp. 151–176. MR**0423869** - David A. Cox,
*The arithmetic-geometric mean of Gauss*, Enseign. Math. (2)**30**(1984), no. 3-4, 275–330. MR**767905** - M. Deuring,
*Die Klassenkörper der komplexen Multiplikation*, Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil II (Article I 2, vol. 23, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1958 (German). MR**0167481** - R. Dupont. Borchardt’s mean, theta constants in genus $2$ and applications, 2005. In preparation.
- Andreas Enge,
*The complexity of class polynomial computation via floating point approximations*, Math. Comp.**78**(2009), no. 266, 1089–1107. MR**2476572**, DOI 10.1090/S0025-5718-08-02200-X - A. Enge. The complexity of modular polynomial computation via floating point evaluation and interpolation, 2005. In preparation.
- Andreas Enge and François Morain,
*Comparing invariants for class fields of imaginary quadratric fields*, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 252–266. MR**2041089**, DOI 10.1007/3-540-45455-1_{2}1 - A. Enge and P. Zimmermann. mpc – Multiprecision Complex arithmetic library version 0.4, 2004. Available at http://www.loria.fr/~zimmerma/free/.
- C. F. Gauss.
*Werke*. Dieterich, Göttingen, 1866–1933. - T. Granlund
*et al.*gmp – GNU Multiprecision library version 4.1, 2002. Available at http://www.swox.com/gmp/. - G. Hanrot, V. Lefèvre, P. Pélissier, and P. Zimmermann. mpfr – Multiple Precision Floating point computations with exact Rounding library version 2.1.0, 2004. Available at http://www.mpfr.org.
- David Mumford,
*Tata lectures on theta. I*, Progress in Mathematics, vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR**688651**, DOI 10.1007/978-1-4899-2843-6 - Bruno Schoeneberg,
*Elliptic modular functions: an introduction*, Die Grundlehren der mathematischen Wissenschaften, Band 203, Springer-Verlag, New York-Heidelberg, 1974. Translated from the German by J. R. Smart and E. A. Schwandt. MR**0412107** - H. Weber.
*Lehrbuch der Algebra*, volume III. Chelsea Publishing Company, New York, 1902.

## Additional Information

**Régis Dupont**- Affiliation: INRIA Futurs, Projet TANC, Laboratoire LIX, École polytechnique, 91128 Palaiseau, France
- Email: regis.dupont@m4x.org
- Received by editor(s): May 27, 2005
- Published electronically: March 4, 2011
- © Copyright 2011 Régis Dupont
- Journal: Math. Comp.
**80**(2011), 1823-1847 - MSC (2000): Primary 65D20; Secondary 33E05, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-2011-01880-6
- MathSciNet review: 2785482