# Sums of squares have zero upper density

Define the upper density of a set $A \subseteq \mathbf{N}$ to be

$$\bar{d}(A) = \limsup_{n \to \infty} \frac{|A \cap [1,n]|}{n}.$$

Let $A$ be the set of sums of two squares, i.e. $A = \{x^2 + y^2 : x,y \in \mathbf{Z}\}$.

I know that any prime congruent to 1 modulo 4 is the sum of two squares, as is the number $2$ itself. Also, for primes congruent to 3 modulo 4, I know that $p^{2n} = x^2+y^2$ for some $x,y$. Hence, since sums of two squares are closed under multiplication, any number, n, of the form:

$$n = 2^{\alpha} (\prod_{i \leq m_1} p_i^{\beta_i})^{2} \prod_{j \leq m_2} q_j^{\gamma_j},$$ Where $\alpha, \beta_i, \gamma_i, m_1, m_2$ are non-negative integers, $p_i$ is a prime congruent to 3 modulo 4, and $q_j$ is a prime congruent to 1 modulo 4.

I'm having difficulty passing to an argument about upper density about the set of all such $n$, though.

• Modulo some prime-power/squarefreeness considerations, what you want to show is that almost all odd numbers have at least one prime $\equiv 3\pmod 4$ in their factorization. Heuristically, since the primes are equidistributed mod $4$, you're showing that the set of 'heads-only' sequences has density zero in the set of all coinflip sequences. – Steven Stadnicki Oct 21 '13 at 21:56
• Also, your text does not make much sense, although the big formula is correct: some $n > 0$ is the sum of two squares if and only if the exponent for any prime divisor $p \equiv 3 \pmod 4$ is even. The true bound is this : the count up to large positive $x$ of sums of two squares is about $$\frac{0.7642 \; x}{ \sqrt {\log x}}$$ – Will Jagy Oct 21 '13 at 22:04

Only primes $\equiv 3\pmod 4$ are "obstacles" against $n$ being the sum of two squares. For each such prime $p$ at least those numbers $n\equiv kp\pmod {p^2}$, $1\le k<p$, are not the sum of two squares. This alone would leave us with a density of $$\prod_{p\equiv 3\pmod 4}\left(1-\frac{p-1}{p^2}\right).$$ However, we neclected higher powers of $p$, i.e. we should additionally filter out $kp^3\pmod{p^4}$, $1\le k<p$, and so on, which leads to $$\prod_{p\equiv 3\pmod 4}\left(1-\frac{p-1}{p^2}-\frac{p-1}{p^4}-\frac{p-1}{p^6}-\ldots\right)=\prod_{p\equiv 3\pmod 4}\left(1-\frac{1}{p+1}\right).$$ The product does not converge (that is: the sequnce of partial products tends to zero) and therefore the density is zero. How can we see that thr product diverges? The reciprocal is $\prod_{p\equiv 3}\left(1+\frac 1p\right)>\sum_{p\equiv 3}\frac 1p$. As far as I know, at least $\sum_p\frac 1p$ diverges and by the "equidistribution" of primes modulo $4$, so should $\sum_{p\equiv 3}\frac 1p$.
• It is true that $\sum_{p \equiv 3}1/p=\infty$.It is a difficult result.It is possible to solve this Q without it. – DanielWainfleet Sep 30 '15 at 5:41