TOPICS
Search

Sum of Squares Function


The number of representations of n by k squares, allowing zeros and distinguishing signs and order, is denoted r_k(n). The special case k=2 corresponding to two squares is often denoted simply r_2(n)=r(n) (e.g., Hardy and Wright 1979, p. 241; Shanks 1993, p. 162).

For example, consider the number of ways of representing 5 as the sum of two squares:

5=(-2)^2+(-1)^2
(1)
=(-2)^2+1^2
(2)
=2^2+(-1)^2
(3)
=2^2+1^2
(4)
=(-1)^2+(-2)^2
(5)
=(-1)^2+2^2
(6)
=1^2+(-2)^2
(7)
=1^2+2^2
(8)

so r_2(5)=8. Similarly,

4=(-2)^2+0^2+0^2
(9)
=0^2+(-2)^2+0^2
(10)
=0^2+0^2+(-2)^2
(11)
=0^2+0^2+2^2
(12)
=0^2+2^2+0^2
(13)
=2^2+0^2+0^2,
(14)

so r_3(4)=6.

The Wolfram Language function SquaresR[k, n] gives r_k(n). In contrast, the function PowersRepresentations[n, k, 2] gives a list of unordered unsigned representations of n as a list of k squares, e.g., giving the 5=1^2+2^2 as the only "unique" representation of 5.

The function r_2(n) is intimately connected with the Leibniz series and with Gauss's circle problem (Hilbert and Cohn-Vossen 1999, pp. 27-39). It is also given by the inverse Möbius transform of the sequence b_(2n)=0 and b_(2n+1)=4(-1)^n (Sloane and Plouffe 1995, p. 22). The average order of r_2(n) is pi, but the normal order is 0 (Hardy 1999, p. 55).

Jacobi gave analytic expressions for r_k(n) for the cases k=2, 4, 6, and 8 (Jacobi 1829; Hardy and Wright 1979, p. 316; Hardy 1999, p. 132). The cases k=2, 4, and 6 were found by equating coefficients of the Jacobi theta functions theta_3(x), theta_3^2(x), and theta_3^4(x). The solutions for k=10 and 12 were found by Liouville (1864, 1866) and Eisenstein (Hardy and Wright 1979, p. 316), and Glaisher (1907) gives a table of r_(2s)(n) for up to 2s=18. However, the formulas for 2s=14 and 2s=16 contained functions defined only as the coefficients of modular functions, but not arithmetically (Hardy and Wright 1979, p. 316). Ramanujan (2000) extended Glaisher's table up to k=24. Boulyguine (1915) found a general formula for r_(2s)(n) in which every function has an arithmetic definition (Hardy and Wright 1979, p. 316; Dickson 2005, p. 317).

r_3(n) was found as a finite sum involving quadratic reciprocity symbols by Dirichlet. r_5(n) and r_7(n) were found by Eisenstein, Smith, and Minkowski. Mordell, Hardy, and Ramanujan have developed a method applicable to representations by an odd number of squares (Hardy 1920; Mordell 1920, 1923; Estermann 1937; Hardy 1999).

To find in how many ways a positive integer n>1 can be expressed as a sum of k=2 squares ignoring order and signs, factor it as

 n=2^(a_0)p_1^(2a_1)...p_r^(2a_r)q_1^(b_1)...q_s^(b_s),
(15)

where the p_is are primes of the form 4k+3 and the q_is are primes of the form 4k+1. If n does not have such a representation with integer a_i because one or more of the powers of p_i is odd, then there are no representations. Otherwise, define

 B=(b_1+1)(b_2+1)...(b_r+1).
(16)

The number of representations of n as the sum of two squares ignoring order and signs is then given by

 r_2^'(n)={0   if any a_i is a half-integer; 1/2B   if all a_i are integers and B is even; 1/2(B-(-1)^(a_0))   if all a_i are integers and B is odd
(17)

(Beiler 1966, pp. 140-142).

Similarly, r_2(n) for n>1 is given by

 r_2(n)={0   if any a_i is a half-integer; 4B   if all a_i are integers.
(18)

A positive integer can be represented as the sum of two squares iff each of its prime factors of the form 4k+3 occurs as an even power, as first established by Euler in 1738. In Lagrange's four-square theorem, Lagrange proved that every positive integer can be written as the sum of at most four squares, although four may be reduced to three except for numbers of the form 4^n(8k+7).

Diophantus first studied a problem equivalent to finding three squares whose sum is 3a+1, and stated that for this problem, a must not be of the form 8n+2, which is however an insufficient condition (Dickson 2005, p. 259). In 1621, Bachet subsequently excluded 8n+2 and 32n+9. Finally, Fermat (ca. 1636) remarked that Bachet's condition failed to exclude a=37, 149, etc., and gave the correct sufficient condition that a must not be of the form ((24k+7)4^n-1)/3, so 3a+1 not of the form (24k+7)4^n, or equivalently (8m+7)4^n.

In 1636, Fermat stated that no integer of the form 8k+7 is the sum of three rational squares, and in 1638, Descartes proved this for integer squares. In 1658, Fermat subsequently asserted (but did not prove) that 2p, where p is any prime of the form 8n-1 (i.e., any prime of the form 8n+7) is the sum of three squares. In 1775, Lagrange made some progress on Fermat's assertion, but could not completely prove it. In 1785, Legendre remarked that Fermat's assertion is true for all odd numbers (not just primes), and then gave an incomplete proof that either every number or its double is a sum of three squares.

Beguelin (1774) had concluded that every integer congruent to 1, 2, 3, 5 or 6 (mod 8) is a sum of three squares, but without adequate proof (Dickson 2005, p. 15). Then, in Legendre's 1798 Théorie des nombres, Legendre proved that every positive integer not of the form 8n+7 or 4n is a sum of three squares having no common factor (Nagell 1951, p. 194; Wells 1986, pp. 48 and 56; Hardy 1999, p. 12; Savin 2000).

r_2(n) is 0 whenever n has a prime divisor of the form 4k+3 to an odd power; it doubles upon reaching a new prime of the form 4k+1. The first few values are 1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, ... (OEIS A004018). A Lambert series was given by

 sum_(n=1)^inftyr_2(n)x^n=4sum_(n=1)^infty((-1)^(n+1)x^(2n+1))/(1-x^(2n+1))
(19)

(Hardy and Wright 1979, p. 258). The generating function for r_2(n) is given by

sum_(n=0)^(infty)r_2(n)x^n=((q^2)_infty^(10))/((q)_infty^4(q^4)_infty^4)
(20)
=theta_3^2(x)
(21)
=1+4x+4x^2+4x^4+8x^5+4x^8+4x^9
(22)

where theta_3(q) is a Jacobi elliptic function and (q)_infty is a q-Pochhammer symbol.

It is given explicitly by

r_2(n)=4sum_(d=1,3,...|n)(-1)^((d-1)/2)
(23)
=4[d_1(n)-d_3(n)]
(24)
=4sum_(d|n)sin(1/2pid),
(25)

where d_k(n) is the number of divisors of n of the form 4m+k (Hilbert and Cohn-Vossen 1999, pp. 37-38; Hardy 1999, p. 12).

r_2(n) obeys the unexpected identities

 sum_(n=0)^infty(r_2(n))/(sqrt(n+a))e^(-2pisqrt((n+a)b))=sum_(n=0)^infty(r_2(n))/(sqrt(n-b))e^(-2pisqrt((n+b)a))
(26)

for R[sqrt(a)],R[sqrt(b)]>0,

 sum_(0<=n<=x)(r_2(n))/(sqrt(x-n))=2pisqrt(x)+sum_(n=1)^infty(r_2(n))/(sqrt(n))sin(2pisqrt(nx))
(27)

and

 sum_(0<=n<=x)r_2(n)=pix+sqrt(x)sum_(n=1)^infty(r_2(n))/(sqrt(n))J_1(2pisqrt(nx))
(28)

(Hardy 1999, p. 82).

The first few values of the summatory function (e.g., Hardy and Wright 1979, p. 270) defined by

 R(N)=sum_(n=1)^Nr_2(n)
(29)

are 0, 4, 8, 8, 12, 20, 20, 20, 24, 28, 36, ... (OEIS A014198), where the modified function defined by Shanks (1993) is

R^*(N)=sum_(n=0)^(N)r_2(n)
(30)
=1+R(n)
(31)

Explicit values of R^*(n) for several powers of 10 are given in the following table (Mitchell 1966; Shanks 1993, pp. 165 and 234).

nR^*(10^n)
05
137
2317
33149
431417
5314197
63141549
8314159053
1031415925457
123141592649625
1431415926535058
r2

Asymptotic results include

sum_(k=1)^(n)r_2(k)=pin+O(sqrt(n))
(32)
sum_(k=1)^(n)(r_2(k))/k=K+pilnn+O(n^(-1/2)),
(33)

where K is a constant known as the Sierpiński constant. The left plot above shows

 [sum_(k=1)^nr_2(k)]-pin,
(34)

with +/-sqrt(n) illustrated by curved envelope, and the right plot shows

 [sum_(k=1)^n(r_2(k))/k]-pilnn,
(35)

with the value of K indicated as the solid horizontal line.

The number of solutions of

 x^2+y^2+z^2=n
(36)

for a given n without restriction on the signs or relative sizes of x, y, and z is given by r_3(n). Gauss proved that if n is squarefree and n>4, then

 r_3(n)={24h(-n)   for n=3 (mod 8); 12h(-4n)   for n=1,2,5,6 (mod 8); 0   for n=7 (mod 8)
(37)

(Arno 1992), where h(x) is the class number of x.

The generating function for r_3(n) is given by

sum_(n=0)^(infty)r_3(n)x^n=theta_3^3(x)
(38)
=1+6x+12x^2+8x^3+6x^4+24x^5+24x^6+12x^8+30x^9+...,
(39)

and in general,

 sum_(n=0)^inftyr_k(n)x^n=theta_3^k(x).
(40)

For r_4(n),

 r_4(n)=8sum_(d|n,4d)d.
(41)

Identities for r_6(n), and r_8(n) are given by

r_6(n)=16sum_(d|n)chi(d^')d^2-4sum_(d|n)chi(d)d^2
(42)
r_8(n)=16sum_(d|n)(-1)^(n+d)d^3,
(43)

where d^'=n/d and

 chi(d)={1   if d=4k+1; -1   if d=4k-1; 0   if d=2k
(44)

(Jacobi 1829, §40-42; Smith 1965; Hardy and Wright 1979, p. 314).

For r_(10)(n),

 r_(10)(n)=4/5[E_4(n)+16E_4^'(n)+8chi_4(n)],
(45)

where

E_4(n)=sum_(d=1,3,...|n)(-1)^((d-1)/2)d^4
(46)
E_4^'(n)=sum_(d^'=1,3,...|n)(-1)^((d^'-1)/2)d^4
(47)
chi_4(n)=1/4sum_(a^2+b^2=n)(a+bi)^4.
(48)

This equation and that for r_(12)(n) were given by Liouville (1864, 1866).

r_(16)(n)=-(32)/3(-1)^n[sigma_1^'(n)+sigma_3^'(n)+sigma_5^'(n)]+(-1)^n(256)/3sum_(k=1)^(n-1)[sigma_1^'(k)sigma_5^'(n-k)-sigma_3^'(k)sigma_3^'(n-k)]
(49)
r_(24)(n)=rho_(24)(n)+(128)/(691)[(-1)^(n-1)259tau(n)-512tau(1/2n)]
(50)
=(-1)^n(16)/9[17sigma_3^('')(n)+8sigma_5^('')(n)+2sigma_7^('')(n)]+(-1)^n(512)/9sum_(k=1)^(n-1)[sigma_3^('')(k)sigma_7^('')(n-k)-sigma_5^('')(k)sigma_5^('')(n-k)],
(51)

where

sigma_r^'(n)=sum_(d|n)(-1)^(d+n/d)d^r
(52)
sigma_r^('')(n)=sum_(d|n)(-1)^dd^r,
(53)

rho_(24)(n) is a so-called singular series, and tau(n) is the tau function.

Similar expressions exist for larger even k, but they quickly become extremely complicated and can be written simply only in terms of expansions of modular functions.


See also

Class Number, Diophantine Equation--2nd Powers, Fermat's Polygonal Number Theorem, Gauss's Circle Problem, Landau-Ramanujan Constant, Leibniz Series, Prime Factor, Primitive Pythagorean Triple, Pythagorean Quadruple, Pythagorean Triple, Sierpiński Constant, Tau Function

Explore with Wolfram|Alpha

References

Arno, S. "The Imaginary Quadratic Fields of Class Number 4." Acta Arith. 60, 321-334, 1992.Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.Boulyguine, M. B. "Sur la représentation d'un nombre entier par une somme de carrés." Comptes Rendus Hebdomadaires de Séances de l'Académie des Sciences 161, 28-30, 1915.Dickson, L. E. History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Dover, pp. 259 and 317, 2005.Eisenstein, G. "Note sur la représentation d'un nombre par la somme de cinq carrés." J. reine angew. Math. 35, 368-369, 1847.Eisenstein, G. "Zur Theorie der quadratischen Zerfällung der Primzahlen 8n+3, 7n+2 und 7n+4." J. reine angew. Math. 37, 97-126, 1848.Estermann, T. "On the Representation of a Number as a Sum of Squares." Acta Arith. 2, 47-79, 1936. Reprinted in Prace mat.-fiz. 45, 93-125, 1937.Ewell, J. A. "New Representations of Ramanujan's Tau Function." Proc. Amer. Math. Soc. 128, 723-726, 1999.Glaisher, J. W. L. "On the Numbers of a Representation of a Number as a Sum of 2r Squares, where 2r Does Not Exceed 18." Proc. London Math. Soc. 5, 479-490, 1907.Grosswald, E. Representations of Integers as Sums of Squares. New York: Springer-Verlag, 1985.Hardy, G. H. "On the Expression of a Number as the Sum of Two Squares." Quart. J. Math. 46, 263-283, 1915.Hardy, G. H. "The Average Order of the Arithmetical Functions P(x) and Delta(x)." Proc. London Math. Soc. 15, 192-213, 1916.Hardy, G. H. "On the Representation of a Number as the Sum of Any Number of Squares, and Particular of Five." Trans. Amer. Math. Soc. 21, 255-284, 1920.Hardy, G. H. "The Representation of Numbers as Sums of Squares." Ch. 9 in Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. and Wright, E. M. "The Function r(n)," "Proof of the Formula for r(n)," "The Generating Function of r(n)," and "The Order of r(n)," and "Representations by a Larger Number of Squares." §16.9, 16.10, 17.9, 18.7, and 20.13 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 241-243, 256-258, 270-271, and 314-315, 1979.Hilbert, D. and Cohn-Vossen, S. Geometry and the Imagination. New York: Chelsea, 1999.Jacobi; C. G. J. Fundamenta Nova Theoriae Functionum Ellipticarum. Königsberg, Germany, 1829.Jones, G. A. and Jones, J. M. "Sum of Squares." Ch. 10 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 191-215, 1998.Liouville, J. "Extrait d'une lettre adressée a M. Besge (concerning the representation of the double of an odd number as the sum of 12 squares)." J. de math. pure et appl. 9, 296-298, 1864.Liouville, J. "Nombre des représentations d'un entier quelconque sous la forme d'une somme de dix carrés." J. de math. pure et appl. 11, 1-8, 1866.Milne, S. "Infinite Families of Exact Sums of Squares Formulas, Jacobi Elliptic Functions, Continued Fractions, and Schur Functions." Ramanujan J. 6, 7-149, 2002. Reprinted in Development in Mathematics 5. Boston, MA: Kluwer 2002.Minkowski, H. "Mémoire sur la théorie des formes quadratiques à coefficients entiers." Mémoirs présentés par divers savants à l'Academie des Sciences de l'Institut de France 29, 1-180, 1887.Mitchell, W. C. "The Number of Lattice Points in a k-Dimensional Hypersphere." Math. Comput. 20, 300-310, 1966.Mordell, L. J. "On the Representation of a Number as a Sum of 2^r Squares." Quart. J. Math. 48, 93-104, 1920.Mordell, L. J. "On the Representation of a Number as a Sum of an Odd Number of Squares." Trans. Cambridge Philos. Soc. 22, 361-372, 1923.Moreno, C. J. and Wagstaff, S. S. Sums of Squares of Integers. Chapman & Hall/CRC, 2005.Nagell, T. Introduction to Number Theory. New York: Wiley, 1951.Ramanujan, S. Collected Papers of Srinivasa Ramanujan (Ed. G. H. Hardy, P. V. S. Aiyar, and B. M. Wilson). Providence, RI: Amer. Math. Soc., 2000.Savin, A. "Shape Numbers." Quantum 11, 14-18, 2000.Séroul, R. "Prime Number and Sum of Two Squares." §2.11 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 18-19, 2000.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 162-153, 1993.Sloane, N. J. A. Sequences A004018/M3218 and A014198 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Smith, H. J. S. "Mémoire sur la représentation des nombres par des sommes de cinq carrés." Mémoirs présentés par divers savants à l'Academie des Sciences de l'Institut de France, Ser. 2 29, No. 1, 1-72, 1887.Smith, H. J. S. Report on the Theory of Numbers. New York: Chelsea, 1965.Uspensky, J. V. "On Jacobi's Arithmetical Theorems Concerning the Simultaneous Representation of Numbers by Two Different Quadratic Forms." Trans. Amer. Math. Soc. 30, 385-404, 1928.Wagon, S. "The Magic of Imaginary Factoring." Mathematica in Education and Res. 5, 43-47, 1996.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, 1986.

Referenced on Wolfram|Alpha

Sum of Squares Function

Cite this as:

Weisstein, Eric W. "Sum of Squares Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SumofSquaresFunction.html

Subject classifications