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) \le \sum_{p \le n}1 \ll \frac{n}{\log n}.$$
Could we do better or the above estimate is the best possible?
 A: One can do a bit better. For simpler presentation assume that we instead consider the function $b'$ that is the indicator function of integers all of whose prime divisors are $1 \mod 4$. We have $b'\leq b$ but $b'$ and $b$ agree on square-free odd integers and any proof for $b'$ can be adapted to $b$. Furthermore, we have $\sum_{p\leq n} b'(n-p)\ll \sum_{d\mid P'(z) \atop (d,n)=1 }\lambda_d^+ \#\{p\leq n: p\equiv n \mod d \} $ by the upper bound of Brun. Here $P'(z)$ is the product of all primes $p<z$ with $p\equiv 1 \mod 4$. Using Bombieri--Vinogradov we obtain $$\ll \frac{n}{\log n } \sum_{d\mid P'(z) \atop (d,n)=1 }\lambda_d^+\phi(d)^{-1}\ll  \frac{n}{\log n } \prod_{p<z \atop p\equiv 1 \mod 4} (1-1/p) \ll  \frac{n}{(\log n)^{3/2} } $$ since one can take $z$ so that $\log z\gg \log n$. Hence, one can save $\sqrt{\log n}$ from the trivial estimate.
A: 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. 
