Mathematics – Number Theory
Scientific paper
2011-11-02
Indagationes Mathematicae, Volume 22, Issues 1-2, 2011, Pages 12-26
Mathematics
Number Theory
14 pages
Scientific paper
10.1016/j.indag.2011.07.002
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 $\theta_n(q)$, the theta function associated to sums of $n$ squares, as a modular form of weight $n/2$ on $\Gamma_1(4)$. In particular, we show that for only a small finite list of $n$ can $\theta_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 $\theta_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).
No associations
LandOfFree
Finding elementary formulas for theta functions associated to even sums of squares does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finding elementary formulas for theta functions associated to even sums of squares, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding elementary formulas for theta functions associated to even sums of squares will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-329670