2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Will Jagy Jan 31 '15 at 3:45
  • $\begingroup$ 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. $\endgroup$ – pretzelman Jan 31 '15 at 3:48
  • 1
    $\begingroup$ 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. $\endgroup$ – awllower Jan 31 '15 at 4:07
  • 2
    $\begingroup$ @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.$ $\endgroup$ – Will Jagy Jan 31 '15 at 4:26
2
$\begingroup$

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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.