# Sieve bound for the sum of two squares

Let $$S(n) = \sum_{p \le n} b(n-p),$$ where $$b(a)=1$$ is $$a$$ is a sum of two squares of positive integers and $$b(a)=0$$ otherwise. Trivially by PNT we have $$S(n) \ll \sum_{p \le n}1 \le \frac{n}{\log n}.$$ Could we do better or the above estimate is the best possible?

The order of magnitude is correct. This paper by C. Hooley gives the asymptotic formula conditioned on GRH, with the order of magnitude $$n/(\log n)$$. There is also this unconditional result due to Linnik, where he gets a lower bound of the same order of magnitude. Your argument already gives an upper bound of the correct order of magnitude, so this is the exact order of magnitude.
• But the theorem of Linnik and the result of Hooley count the number of solutions, no? Basically as I see Linnik gives asymptotic formula for $$\sum_{p \le n} r(n-p),$$ where $r(n)$ is the number of representations of $n$ as a sum of two squares, while I have $b(n-p)$ instead. – toshi Nov 27 '18 at 13:11