MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The sum-of-squares function (denoted $r_{2}(n)$) gives the number of ways in which a given number $n$ is expressible as the sum of two squares. The following is from the article on this function from Wolfram Mathworld.

To find the the number of representations of $n$ as the sum of two squares (ignoring order and signs), factor $n$ as
$$n= 2^{a_0}p_{1}^{2a_{1}}...p_{r}^{2a_{r}}q_{1}^{b_{1}}...q_{s}^{b_{s}}$$ where $p_{i}$s are primes of the form $4k+3$ and $q_{i}$s 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=\prod_{i=1}^{r}(b_{i}+1)$$ Then, the required number will be $0$ if any $a_{i}$ is a half-integer,$\frac{B}{2}$ if all $a_{i}$ are integers and $B$ is even, and $\frac{1}{2}(B-(-1)^{a_0})$ if all $a_{i}$ are integers and $B$ is odd.

Now the questions I want to ask are two.

  1. If I want to write an algorithm to find out the value of this function at a large integer, then using the above definition wouldn't give the best result since it is required to factor the integer first, and Integer Factorization is known to be computationally difficult. So, is there any other formula for this function which allows us to "put in" the value of $n$ to get the required result without having to resort to finding out the prime factorization of $n$ first?

  2. If there was such a formula for the sum-of-squares function, would that be preferred over the above? Are there any reasons why such a formula would be more advantageous?

    Thanks in advance!

share|cite|improve this question
The value of r_2 is stronger than a primality test for odd sums $N$ of two coprime squares since there is essentially a unique representation if and only if $N$ is prime. Moreover, the knowledge of two representations of $N$ as a sum of two squares allows you to factor $N$. This doesn't prove anything, but perhaps suggests that you should not expect too much. – Franz Lemmermeyer Apr 26 '11 at 14:34
Terry Tao's heuristic here… would seem to predict that you probably can't find an efficient way to compute this. – David Speyer Apr 26 '11 at 14:52
If $N=pq$ is 1 mod 4 and the product of two (large) distinct primes, then $N$ is expressible as the sum of two squares iff $p$ and $q$ are both 1 mod 4. But figuring out whether the factors are both 1 mod 4 or both 3 mod 4 is believed to be a hard problem. – Kevin Buzzard Apr 26 '11 at 22:19
For some more comments you can take a look at this question… that discusses how hard it is just to determine if $r_2$ is zero or not. – Zander Apr 27 '11 at 0:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.