Is there a simple way to compute the number of ways to write a positive integer as the sum of three squares?

It's a standard theorem that the number of ways to write a positive integer N as the sum of two squares is given by four times the difference between its number of divisors which are congruent to 1 mod 4 and its number of divisors which are congruent to 3 mod 4. Alternatively, there are no such representations if the prime factorization of N contains any prime of form 4k+3 an odd number of times. If the prime factorization of N contains all such primes an even number of times, then we have

r2(N) = 4(b1 + 1)(b2 + 1)...(br+1)

where b1, ..., br are the exponents of the primes congruent to 1 mod 4 in the factorization of N.

For example, 325 = 52 × 13 can be written in 4(2+1)(1+1) = 24 ways as a sum of squares. These are 182 + 12, 172 + 62, 152 + 102, and the representations obtained from these by changing signs and/or permuting.

Is there an analogous formula in the three-square case? I know that an integer can be written as the sum of three squares if and only if it is not of the form 4m(8n+7). There is a simple argument that shows that the number of ways to write all integers up to N as a sum of three squares is asymptotically 4πN3/2/3 -- representations of an integer less than N as a sum of three squares can be identified with points in the ball in R3 centered at the origin with radius N1/2. Differentiating, a "typical" integer near N should have about 2πN1/2 representations as a sum of three squares. From playing around with some data it looks like

limn → ∞ #{ k ≤ n and r3(k)/k1/2 ≤ x} / n

might be a nonzero constant. That is, for each positive real x, the probability that a random integer k can be written in no more than x k1/2 ways approaches some constant in the open interval (0, 1) as k → ∞.

One way to prove this (if it is in fact true) would be if there were some formula for r3(k), in terms of the prime factorization, which is why I'm curious.

(I apologize if this is something that is well-known to number theorists, although I'd appreciate a pointer if it is. I am not a number theorist, I just play around with this sort of thing every so often and generate amusing conjectures.)

• The Mathworld article has one: mathworld.wolfram.com/SumofSquaresFunction.html – Qiaochu Yuan Oct 31 '09 at 20:57
• In addition to the formula (which is not very explicit) there is a reference before equation (15) to a different representation. – Qiaochu Yuan Oct 31 '09 at 21:01
• The mean square of r_3(k)/k^(1/2) is known, in the following sense (arXiv math/0502007v2): r_3(1)^2 + ... + r_3(n)^2 ~ 8 pi^4/(21 zeta(3)) * n^2. Differentiating, r_3(n)^2 itself is typically around (16 pi^4/(21 zeta(3))) n, or ~61.74n. But r_3(1)+...+r_3(n) ~ 4Pi/3*n^(3/2), so r_3(n) is typically near 2Pi*n^(1/2). The mean of the square is thus 4Pi^2 * n, less than the square of the mean, suggesting strongly that the distribution is nontrivial. – Michael Lugo Nov 1 '09 at 18:29
• I believe that even the criterion for whether there's at least one way to write a number as the sum of three squares does not have an easy description, so the answer must be no. – Zsbán Ambrus Apr 27 '10 at 9:56
• @Zsbán Ambrus: Michael Lugo was correct in saying "an integer can be written as the sum of three squares if and only if it is not of the form $4^m(8n+7)$." See : Dickson_Diagonal_1939.pdf on my site zakuski.math.utsa.edu/~kap/forms.html – Will Jagy May 2 '10 at 1:10

I just can't stop myself from putting up the following, from the MOTD on the Berkeley server:

Oct  2: Warning: Due to a known bug, the default Linux document viewer
evince prints N*N copies of a PDF file when N copies requested.
copies of PDF documents, or use the fact that every natural number
is a sum of at most four squares.

• It's been ten years since I upvoted and forgot this; it would be nice to be able to upvote again. – Dror Speiser Dec 24 '19 at 16:31

Medium answer: For n square free, this is closely related to the class number of Q(sqrt{-n}); this is a result of Gauss. See Mathworld for a precise statement. This class number can then be rewritten in terms of the quadratic residue symbol. We can either use the class number formula to get an expresion as an infinite sum, or use Dirichlet's evaluation of L(1, chi) (same Wikipedia link) to give a finite expression.

When n is not square free, one can still give an answer in terms of the product of the class number and certain elementary correction factors, but the correction factors are so bad that no one wants to write them down. (By no one, I mean that the first half dozen papers I found on mathscinet wouldn't do it.)

Long answer: I did find a paper with all the details. See Theorem B of Bateman "On the representations of a number as the sum of three squares." Trans. Amer. Math. Soc. 71, (1951). 70--101. That's right, I won't write it down either :).

• Thanks. It seems that the formulas for the number of ways to write n as a sum of k squares are much simpler when k is even than when k is odd. My conjecture, suitably rewritten, still seems to be true from numerical data: lim (n → ∞) #{k ≤ n and r_j(k)/k^(j/2-1) ≤ x} / n seems to be nontrivial, at least for x in a certain range. I'm now trying to familiarize myself with the literature, which is a daunting task since so many people have studied this... – Michael Lugo Nov 2 '09 at 19:48
• Hmmm. Since a positive proportion of integers are square free, you could just concentrate on that case. Then you are asking whether the class number h(n) is less than x*sqrt{n} with positive probability. I'm pretty sure that this is either known or conjectured to be true. – David E Speyer Nov 2 '09 at 21:33
• Bounds for the class number of imaginary quadratic fields follow from the Brauer-Siegel formula. See e.g. Davenport's book. – Felipe Voloch Apr 27 '10 at 2:27
• Actually, the nice formula for square-free $n$ generalizes nicely to primitive representations. From this formula, it is straightforward to generate Bateman's formula for all representations. – GH from MO Jun 3 '14 at 23:55

I put a fair amount of effort into this, just about as the recent duplicate question was being closed. So I am moving it.

I wanted to include the viewpoint of Burton Wadsworth Jones, given in his little book "The Arithmetic Theory of Quadratic Forms." The theorem, with many cases, is that the number of "primitive" or "proper" representations $R_{0}(n)$ of a number by $x^2 + y^2 + z^2,$ (meaning $\gcd (x,y,z) = 1$) is a multiple of the class number of binary quadratic forms of discriminant $-4n,$ but the multiple changes depending on congruence properties of $n.$ Also there are "ground" cases, here $n=1,$ which are done separately anyway.To get the actual number of representations for a number that is not squarefree it is necessary to take a sum.

Let's see, if $n$ is a multiple of 4 there are no primitive representations, as $x^2 + y^2 + z^2 \equiv 0 \pmod 4$ means that $x,y,z$ are all even. But that is fine, because this also means that the number of representations of $4n$ is exactly the same as the number of representations of $n.$ Also, if $n \equiv 7 \pmod 8$ there are no representations at all.

For $n > 1$ and $n \equiv 1 \pmod 8,$ $\; \; R_{0}(n) = 12 h(-4n).$

For $n \equiv 3 \pmod 8,$ $\; \; R_{0}(n) = 8 h(-4n).$

For $n \equiv 5 \pmod 8,$ $\; \; R_{0}(n) = 12 h(-4n).$

For $n \equiv 2 \pmod 8,$ $\; \; R_{0}(n) = 12 h(-4n).$

For $n \equiv 6 \pmod 8,$ $\; \;R_{0}(n) = 12 h(-4n).$

Just to include something that is not entirely about proper representations, from the Hecke eigenform method one gets, with p an odd prime, $$R(p^2 n) = (p + 1 - (-n|p) ) \; \; R(n) - \; \; p \; R( n / p^2)$$ where $R(n)$ is the number of representations including both proper and improper, the Jacobi symbol $(-n|p)$ is taken to be 0 if $p | n,$ while $R(n/p^2)$ is taken to be 0 if $p^2$ does not divide $n.$ This appears in an article by Hirschhorn and Sellers called, and I think this is clever, "On representations of a number as a sum of three squares" which appeared about 1999 in a journal with the word "Discrete" in the title. I just have a preprint here.

• The paper is Michael D. Hirschhorn and James A. Sellers, On representations of a number as a sum of three squares, Discrete Math. 199 (1999), no. 1-3, 85-101, MR1675913 (2000a:11141). – Gerry Myerson Apr 27 '10 at 0:00
• This is a very nice answer! You organized the data much more clearly than any of the articles I found. – David E Speyer Apr 27 '10 at 0:07
• (also copied from the duplicate thread) We (me, Michel, and Venkatesh) write something about this question in the preprint "Linnik's Ergodic method and the distribution of integral points on spheres." In particular, we explain how the set of (SO_3(Z) classes of) representations of n is naturally a torsor for a class group, thus recovering the above formulas for R_0(n) in the squarefree case. (None of this is really original to us except maybe the use of the word "torsor.") – JSE Apr 27 '10 at 1:45
• The stuff relating to class number is due to Gauss, is in the Disquisitiones, and is described in Grosswald's 1985 book Representations of Integers as Sums of Squares. Chapter 4 is called Representations as Sums of Three Squares. Section 8, Gauss's Theorem is pages 51-53. There is a difference in presentation, you do need to know that if $n >3, \; n \equiv 3 \pmod 8,$ then $h(-4n) = 3 h(-n).$ – Will Jagy Jun 27 '12 at 19:22
• Just checking: you meant $h(d)$ to count the class number of not-necessarily-primitive binary quadratic forms of discriminant $d<0$? So $h(d)$ is not the class number of the quadratic order of discriminant $d$? Something must be up because $R_0(3) = 4\cdot 8 = 32$ by counting orbits of $(0,\pm 1, \pm 1, \pm 1)$, but the only reduced primitive quadratic form of discriminant $-12$ is $x^2+3y^2$. – John Voight Jan 7 '17 at 2:02

See Granville-Soundararajan, The distribution of values of L(1, \chi),'' for (whatever is known about) the distribution of r_3(n)/sqrt(n).