Finding elementary formulas for theta functions associated to even sums of squares

DOI10.1016/J.INDAG.2011.07.002MaRDI QIDQ648946zbMATHOpenAlexFDO

Authors Ila Varma

Publication date 29 November 2011

Published in Indagationes Mathematicae. New Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0572

zbMATH Keywords

log-polynomial time algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Sums of squares and representations by other particular quadratic forms (11E25) Theta series; Weil representation; theta correspondences (11F27)

Abstract: This article discusses the classical problem of how to calculate $r_n(m)$, the number of ways to represent an integer $m$ by a sum of $n$ squares from a computational efficiency viewpoint. Although this problem has been studied in great detail, there are very few formulas given for the purpose of computing $r_n(m)$ quickly. More precisely, for fixed $n$, we want a formula for $r_n(m)$ that computes in log-polynomial time (with respect to $m$) when the prime factorization of $m$ is given. Restricting to even $n$, we can view $het{a}_n(q)$, the theta function associated to sums of $n$ squares, as a modular form of weight $n/2$ on $Gamm{a}_1(4)$. In particular, we show that for only a small finite list of $n$ can $het{a}_n$ be written as a linear combination consisting entirely of Eisenstein series and cusp forms with complex multiplication. These are the only $n$ that give rise to "elementary" formulas for $r_n(m)$, i.e. formulas such that for a prime $p$, $r_n(p)$ can be calculated in $cO(log(p))$-time. Viewing $het{a}_n(q)$ as one of the simpler examples of modular forms that are not strictly Eisenstein, this result motivates the necessity of a log-polynomial time algorithm that directly calculates the Fourier coefficients of modular forms in the generic situation when there is no such formula, as described in Couveignes and Edixhoven's forthcoming book (for level 1 cases) and Peter Bruin's Ph.D. thesis (for higher level, including 4).

Recommendations

• Representations of integers as sums of an even number of squares
• scientific article; zbMATH DE number 1532371
• A SHORT PROOF OF MILNE'S FORMULAS FOR SUMS OF INTEGER SQUARES
• On the number of primitive representations of integers as sums of squares
• Bases for \(S_{k}({\Gamma}_{1}(4))\) and formulas for even powers of the Jacobi theta function

Cites work

• scientific article; zbMATH DE number 3833919 (Why is no real title available?)
• scientific article; zbMATH DE number 2134201 (Why is no real title available?)
• scientific article; zbMATH DE number 3565087 (Why is no real title available?)
• scientific article; zbMATH DE number 824714 (Why is no real title available?)
• scientific article; zbMATH DE number 825072 (Why is no real title available?)
• scientific article; zbMATH DE number 7426016 (Why is no real title available?)
• Algorithmic Number Theory
• Class fields over real quadratic fields and Hecke operators
• Computational Aspects of Modular Forms and Galois Representations
• Infinite families of exact sums of squares formulas, Jacobi elliptic functions, continued fractions, and Schur functions
• Modular Forms
• Modular forms, a computational approach. With an appendix by Paul E. Gunnells
• On Elliptic Curves with Complex Multiplication as Factors of the Jacobians of Modular Function Fields
• On the representation of a number as the sum of any number of squares, and in particular of twenty
• Quelques applications du théorème de densité de Chebotarev
• Sur la lacunarité des puissances de η
• The number of representations of an integer by a quadratic form.
• The real zeros of the Bernoulli polynomials
• The representation of integers as sums of squares
• Über die analytische Theorie der quadratischen Formen

This page was built for publication: Finding elementary formulas for theta functions associated to even sums of squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648946)