# $S=\{0,1,2,…,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?

I'm currently working on a proof, and have broken it down into a series of problems. I've had success with every part except one. My question is (and it may be really easy; it's getting late):

'Let $q$ be a prime such that $q\equiv 3 \mod 4$. Given the set $S=\{0,1,2,...,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?'

I've been trying to think of a clever way to exploit Fermat, but have been unsuccessful. I know that any prime $3 \mod 4$ cannot be written as the sum of two squares [so $S$ has max of $q^2-1$ elements which can be written as the sum of two squares].

Also, I know that any integer $n$ can be written as the sum of two squares iff it's prime factorization contains an even number of primes $3 \mod 4$. Maybe you good people of the Stack Exchange could help guide me in the right direction.

• you are incorrect on the characterization: a number for which every prime factor $q \equiv 3 \pmod 4$ has an even exponent is the sum of two squares. We can estimate the count of such numbers up to a bound, not count exactly – Will Jagy Jan 31 '15 at 3:45
• if the prime has an even exponent, then it occurs an even number of times in the prime factorization, no? For example, $3^4\cdot 7^6$ -- $7$ occurs $6$ (even) times, $3$ occurs $4$ (even) times in the prime factorization. – pretzelman Jan 31 '15 at 3:48
• But the converse does not hold: there could be an even number of prime factors $\equiv3\pmod4$ while each of them appears an odd number of times. – awllower Jan 31 '15 at 4:07
• @awllower, not widely known example in all details, a number is represented by $x^2 + 5 y^2$ if and only if all prime factors $q \equiv 11,13,17,19 \pmod {20}$ have even exponents, while the sum of the exponents of any prime factors $2$ or $p \equiv 3,7 \pmod {20}$ is even. So, for example, $6 = 1+5,$ $14 = 9+5,$ $21 = 1 + 5 \cdot 4.$ – Will Jagy Jan 31 '15 at 4:26

I do not believe there is any closed-form exact count of sums of two squares up to a positive $x,$ any more than there is a simple way to count the primes up to $x.$
Meanwhile, in LeVeque two volumes in one, in volume 2, page 260, Theorem 7-28, we have that the count of numbers up to some positive $x$ that are sums of two squares is $$\frac{Bx}{\sqrt {\log x}} + O \left( \frac{x}{\left(\log x \right)^{3/4}}\right)$$ where the constant $B \approx 0.7642.$