Short addition sequences for theta functions
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| dc.contributor.author | ENGE, Andreas | |
| hal.structure.identifier | Fachbereich Mathematik [Kaiserslautern] | |
| dc.contributor.author | HART, William | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| dc.contributor.author | JOHANSSON, Fredrik | |
| dc.date.accessioned | 2024-04-04T03:06:40Z | |
| dc.date.available | 2024-04-04T03:06:40Z | |
| dc.date.issued | 2018 | |
| dc.identifier.issn | 1530-7638 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193356 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | University of Waterloo | |
| dc.title.en | Short addition sequences for theta functions | |
| dc.type | Article de revue | |
| dc.subject.hal | Mathématiques [math]/Théorie des nombres [math.NT] | |
| dc.identifier.arxiv | 1608.06810 | |
| dc.description.sponsorshipEurope | Algorithmic Number Theory in Computer Science | |
| bordeaux.journal | Journal of Integer Sequences | |
| bordeaux.page | 1-34 | |
| bordeaux.volume | 18 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01355926 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01355926v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Journal%20of%20Integer%20Sequences&rft.date=2018&rft.volume=18&rft.issue=2&rft.spage=1-34&rft.epage=1-34&rft.eissn=1530-7638&rft.issn=1530-7638&rft.au=ENGE,%20Andreas&HART,%20William&JOHANSSON,%20Fredrik&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||