It is known (sum of two squares theorem) that a number can be written as a sum of two squares (that is, as $n = x^2 + y^2$ for integers $x$ and $y$) if and only if, in its prime factorization, every prime congruent to $3$ modulo $4$ (namely, each prime $3$, $7$, $11$, $19$, $23$, $31$, etc.) occurs to an even power (possibly $0$).

It is further known (Landau–Ramanujan constant: 1, 2, 3) that the number of such numbers less than $x$ is asymptotically equivalent to $K \dfrac{x}{\sqrt{\ln x}}$ where $$K \approx 0.76422.$$

Now, what if we want to count only the numbers $n$ that can be written as $x^2 + y^2$ where both $x$ and $y$ are non-zero? This sequence is OEIS A000404 rather than OEIS A001481.

By the same reasoning that leads to the sum-of-two-squares theorem, these are the numbers $n$ such that in the prime factorization of $n$, every prime that is congruent to $3$ modulo $4$ occurs to an even power, and there is at least one another prime. (In other words, from the set of sums-of-two-squares, we're excluding only numbers of the form $m^2$ where every prime factor of $m$ is congruent to $3$ modulo $4$.)

Asymptotically, how many such numbers are there less than a given $x$? That is, I gather that it must be $K' \dfrac{x}{\sqrt{\ln x}}$ for some constant $K'$; what is the exact value of $K'$?

Some questions that look relevant, though I don't understand all of the mathematics involved: Numbers divisible only by primes of the form 4k+1 on MathOverflow, and, linked from it, Asymptotic for primitive sums of two squares on this site.

  • $\begingroup$ if you just want $x,y$ nonzero in $x^2 + y^2,$ the numbers you are discarding are squares. The count of removed numbers up to some $X$ is at most $\sqrt X,$ so there is no change caused in the dominant term $\frac{KX}{\log X}$ $\endgroup$ – Will Jagy Feb 24 '20 at 19:59
  • $\begingroup$ @WillJagy Oh yeah that makes sense. (Initially I thought it should be the same but then I guess I was overthinking it.) Could you post that as an answer so I could accept it? :-) $\endgroup$ – ShreevatsaR Feb 24 '20 at 21:05

The set that is being discarded is of negligible density in the original set (sums of two squares). The new set is made up of squares, the count up to some bound $X$ is $\sqrt X.$ Divide this by $\frac{BX}{\sqrt \log X}$ and the limit is zero. Therefore, subtracting off this set leaves the dominant term unchanged, namely $\frac{BX}{\sqrt \log X}$ with known constant $B$

The dominant term is worked out in William J. LeVeque, Topics in Number Theory. I have the Dover edition, both volumes in one paperback. He includes an error estimate in Theorem 7-28, $$ \frac{BX}{\sqrt \log X} + O \left( \frac{x}{ (\log x)^{3/4}} \right) $$ and your square root term is considerably smaller than that


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.