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.

  • 1
    $\begingroup$ 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. $\endgroup$ – toshi Nov 27 '18 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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