5
$\begingroup$

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

  • 0
    Sure, I meant $ \Omega $. Thank you.2012-12-23

3 Answers 3

9

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.

  • 0
    David, posted pages with proof from LeVeque as an answer. Hardly could be said to be self-contained.2012-12-23
5

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.

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

enter image description here

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

enter image description here

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

4

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})$

  • 0
    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.2012-12-23