Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Sure, I meant $ \Omega $. Thank you. –  Sergey Finsky Dec 23 '12 at 11:13
add comment

3 Answers

up vote 8 down vote accepted

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.

share|improve this answer
    
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
add comment

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

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

share|improve this answer
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.