Short addition sequences for theta functions

Andreas Enge 1 William Hart 2 Fredrik Johansson 1
1 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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.
Type de document :
Article dans une revue
Journal of Integer Sequences, University of Waterloo, 2018, 18 (2), pp.1-34
Liste complète des métadonnées

https://hal.inria.fr/hal-01355926
Contributeur : Andreas Enge <>
Soumis le : mercredi 24 août 2016 - 14:48:31
Dernière modification le : vendredi 9 mars 2018 - 01:26:12
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 14:05:38

Fichiers

addseq.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01355926, version 1
  • ARXIV : 1608.06810

Citation

Andreas Enge, William Hart, Fredrik Johansson. Short addition sequences for theta functions. Journal of Integer Sequences, University of Waterloo, 2018, 18 (2), pp.1-34. 〈hal-01355926v1〉

Partager

Métriques

Consultations de la notice

375

Téléchargements de fichiers

82