# Number of representable as sum of 2 squares

How to find asymptotically (or some reasonable bound, at least $o(n)$) number of numbers, representable as a sum of squares of 2 numbers? (in case of bound I am interested in both: lower and upper bounds)

I know how to find explicitly the number of ways to represent given number in such a way. (can be found here)

Thank you!

P.S. For one lower bound you can use this problem, it'll give you somewhat $\Omega (n^{\frac{3}{4}})$.

-
Sure, I meant $\Omega$. Thank you. –  Sergey Finsky Dec 23 '12 at 11:13

Let $S_2(x)$ be the number of integers $\leq x$ which are a sum of two squares. Landau, in 1906, showed that $$S_2(x) \sim K \frac{x}{\sqrt{\log x}}$$ where $$K = \frac{1}{\sqrt{2}} \prod_{p \equiv 3 \mod 4} \frac{1}{\sqrt{1-p^{-2}}}$$ I can't find a proof online, but there are references to the statement in many places, such as here.

-
I have this suspicion it's straightforward if you know a lot about zeta functions, and look at $$\prod_p \left(1 - \frac{1}{p^s} \right)$$ where $s = 1$ if $p \equiv 0,1 \pmod 4$, otherwise $s = 2$. Alas, I know very little about zeta functions. :( –  Hurkyl Dec 23 '12 at 12:58
Yes, it'd be nice if somebody posted whole proof, because it's know quite straightforward. But thank you very much, I would never expect to see asymptotics for this problem, thought, there'll be only some bounds. –  Sergey Finsky Dec 23 '12 at 15:57
@SergeyFinsky, a complete proof is given in LeVeque, now available as an inexpensive combined two-volumes-in-one paperback. Note that $K \approx 0.7642...$ So, Dover publications paperback store.doverpublications.com/0486425398.html theorem 7-28 pages 261-263, with error term, in the Volume II section. They have volume I numbered up to page 202, then they start over at 1, so I guess the whole paperback is 500 pages with prefaces and all. –  Will Jagy Dec 23 '12 at 20:38
@SergeyFinsky, I see, all of section 7-5 leads up to that, so actually pages 257-263. Furthermore, this builds on the proof of the Prime Number Theorem, and is presented as an illustration of the relevant techniques, so all of Chapter 7, pages 229-263. So, get the book. It's a bargain. –  Will Jagy Dec 23 '12 at 20:47
David, posted pages with proof from LeVeque as an answer. Hardly could be said to be self-contained. –  Will Jagy Dec 23 '12 at 21:33

Posting pages 260-263 from LeVeque. The evident hair on page 262 is not part of the book proper; it evidently fell from my own head onto the scanner, and is one I could ill afford to lose.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

-

A number can be written as a sum of two squares if and only if it is not divisible an odd number of times by any prime that is $3$ modulo $4$.

In particular, every prime that is $1$ modulo $4$ is a sum of two squares. By the prime number theorem, there are $\Theta(\frac{n}{\log n})$ primes in the interval $[0, n]$. By Dirichlet's theorem on arithmetic progressions, asymptotically half of these are $1$ modulo $4$.

Therefore, the number of numbers less than $n$ that can be written as a sum of two squares is $\Omega(\frac{n}{\log n})$

-
Dirichlet's theorem does not imply that, you should cite Prime number theorem for arithmetic progressions instead –  ryu jin Dec 23 '12 at 14:32
To quote wikipedia: Stronger forms of Dirichlet's theorem state that ... different arithmetic progressions with the same modulus have approximately the same proportions of primes. This is the same result you cite under a different name. –  Hurkyl Dec 23 '12 at 20:17
Hurkyl, the pages just before the answer i posted, in the LeVeque book, give a heuristic you might like, in about one and a half pages, 257-259. –  Will Jagy Dec 23 '12 at 21:40