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

DOI10.1016/J.INDAG.2011.07.002zbMATH Open1244.11044arXiv1111.0572OpenAlexW3099087851MaRDI QIDQ648946FDOQ648946

Authors: Ila Varma 

Publication date: 29 November 2011

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

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).

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

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

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)

Cites Work

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

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)