Welcome to MathOverflow

Question

6

2

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.

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?
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!

flag	asked Apr 26 2011 at 13:55 Koundinya Vajjha 666●10●21

3

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 2011 at 14:34

3

Terry Tao's heuristic here mathoverflow.net/questions/3820/… would seem to predict that you probably can't find an efficient way to compute this. – David Speyer Apr 26 2011 at 14:52

3

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 2011 at 22:19

3

For some more comments you can take a look at this question mathoverflow.net/questions/57981/… that discusses how hard it is just to determine if $r_2$ is zero or not. – Zander Apr 27 2011 at 0:31

Is there another simple formula for the sum-of-squares function?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.