A positive integer $n$ can be written primitively as the sum of two squares, meaning $n = x^2 + y^2$ with $\gcd(x,y)=1,$ precisely when $n$ is not divisible by $4$ or by any prime $q \equiv 3 \pmod 4.$

Since this applies to primes $p \equiv 1 \pmod 4,$ the count of such numbers up to some large positive $x$ is at least $$ \frac{x}{2 \log x}. $$

On the other hand, it cannot be any larger than all sums of two squares up to $x,$ which is about $$ \frac{0.7642 \; x}{\sqrt{ \log x}}. $$

The ratio of these two quantities becomes arbitrarily large as $x$ grows.

Question: what is the true asymptotic for the count of numbers up to $x$ that are primitively the sum of two squares?

Numerical experiment suggests closer to the larger quantity but needing to be smaller by a factor that grows more slowly than anything else in sight, perhaps

$$ \frac{ x}{\sqrt{ \log x} \; \; \log \log x} $$ or the like.


1 Answer 1


The formula for the (asymptotic number) of integers which are the sum of two squares is obtained by Perron's formula as applied to to the infinite product:

$$\left(1 - \frac{1}{2^s} \right)^{-1} \prod_{1 \mod 4} \left(1 - \frac{1}{p^s} \right)^{-1} \prod_{3 \mod 4} \left(1 - \frac{1}{p^{2s}} \right)^{-1}.$$

The reason why one can compute the asymptotic is that this function is (very close) to the square-root of $\zeta_{\mathbf{Q}(i)}(s)$.

The answer to your question follows from applying exactly the same method to the modified function:

$$L(s) = \left(1 + \frac{1}{2^s} \right) \prod_{1 \mod 4} \left(1 - \frac{1}{p^s} \right)^{-1}.$$

In both cases, the answer depends on the precise asymptotics of these functions as $s \rightarrow 1$. However, thes functions differ (in ratio) by a holomorphic function in $\mathrm{Re}(s) > 1/2$ which is non-vanishing in this range. Looking at Perron's formula, you will obtain exactly the same answer, except the constant will be modified by the ratio of these functions as $s = 1$, which is:

$$\frac{3}{4} \cdot \prod_{3 \mod 4} \left(1 - \frac{1}{p^2} \right) \sim 0.642.$$

You can also see this heuristically; if $H(x)$ is the number of integers which can be (primively) expressed as the sum of two squares, and $G(x)$ as the sum of two squares in any way, then

$$G(x) = H(x) + H(x/4) + H(x/9) + H(x/16) + \ldots $$

where the sum is taken over all the terms in

$$ \prod_{2,3 \mod 4} \left(1 - \frac{1}{p^2} \right)^{-1}.$$

  • 1
    $\begingroup$ Huh; so it is just a smaller constant in the $\sqrt{\log x}$ recipe, and my experiments on computer had just not gone far enough to suggest that $\endgroup$
    – Will Jagy
    May 14, 2015 at 21:07
  • $\begingroup$ There we go; the (possible) constant I am getting from the computer is consistent with $0.4907,$ which is $0.7642 \cdot 0.642,$ getting there anyway, currently $0.493$ $\endgroup$
    – Will Jagy
    May 14, 2015 at 21:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .