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

This article discusses the classical problem of how to calculate rn(m)rn(m), the number of ways to represent an integer mm by a sum of nn 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 rn(m)rn(m) quickly. More precisely, for fixed nn, we want a formula for rn(m)rn(m) that computes in log-polynomial time (with respect to mm) when the prime factorization of mm is given. Restricting to even nn, we can view θn(q)θn(q), the theta function associated to sums of nn squares, as a modular form of weight n/2n/2 on Γ1(4)Γ1(4). In particular, we show that for only a small finite list of nn can θnθn be written as a linear combination consisting entirely of Eisenstein series and cusp forms with complex multiplication. These are the only nn that give rise to “elementary” formulas for rn(m)rn(m), i.e. formulas such that for a prime pp, rn(p)rn(p) can be calculated in O(log(p))O(log(p))-time. Viewing θn(q)θ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).