Short addition sequences for theta functions - Archive ouverte HAL Access content directly
Journal Articles Journal of Integer Sequences Year : 2018

Short addition sequences for theta functions

(1) , (2) , (1)
1
2

Abstract

The main step in numerical evaluation of classical Sl2 (Z) modular forms and elliptic functions is to compute the sum of the first N nonzero terms in the sparse q-series belonging to the Dedekind eta function or the Jacobi theta constants. We construct short addition sequences to perform this task using N + o(N) multiplications. Our constructions rely on the representability of specific quadratic progressions of integers as sums of smaller numbers of the same kind. For example, we show that every generalised pentagonal number c 5 can be written as c = 2a + b where a, b are smaller generalised pentagonal numbers. We also give a baby-step giant-step algorithm that uses O(N/ log r N) multiplications for any r > 0, beating the lower bound of N multiplications required when computing the terms explicitly. These results lead to speed-ups in practice.
Fichier principal
Vignette du fichier
addseq.pdf (375.01 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01355926 , version 1 (24-08-2016)
hal-01355926 , version 2 (07-03-2018)

Identifiers

Cite

Andreas Enge, William Hart, Fredrik Johansson. Short addition sequences for theta functions. Journal of Integer Sequences, 2018, 18 (2), pp.1-34. ⟨hal-01355926v2⟩
452 View
346 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More