Short addition sequences for theta functions

Classical modular functions and forms may be evaluated numerically using truncations of the q-series of the Dedekind eta-function or of Jacobi theta-constants. We show that the special structure of the exponents occurring in these series makes it possible to evaluate their truncations to N terms with N+o(N) multiplications; the proofs use elementary number theory and sometimes rely on a Bateman-Horn type conjecture. We furthermore obtain a baby-step giant-step algorithm needing only a sublinear number of multiplications, more precisely O (N/log^r N) for any r>0. Both approaches lead to a measurable speed-up in practical precision ranges, and push the cross-over point for the asymptotically faster arithmetic- geometric mean algorithm even further.

(joint work with William Hart and Fredrik Johansson) ​