Skip to main content
1 of 3
GH from MO
  • 105.4k
  • 8
  • 293
  • 398

It is known that $f(n):=r_2(n)/4$ is a multiplicative function such that for $p\equiv 1\pmod{4}$ we have $f(p^k)=k+1$, while for $p\equiv 3\pmod{4}$ we have $f(p^k)=1$ or $f(p^k)=0$ depending on whether $k$ is odd or even. Using this information, one can show that $$r_2(n)\leq n^{\frac{\log 2+o(1)}{\log\log n}},$$ and this is best possible in the sense that $\log 2$ cannot be lowered here. The proof goes almost verbatim as the proof of Theorem 2 in Section 5.2 in Tenenbaum: Introduction to analytic and probabilistic number theory. In fact the statement of this theorem itself implies the above upper bound, because $f(n)\leq\tau(n)$. The lower bound only requires a Chebyshev type lower bound that $$\sum_{\substack{p\leq x\\p\equiv 1\pmod{4}}}\log p\gg x.$$

Regarding Noam Elkies's comment: Landau proved that the number of $n\leq x$ with $r_2(n)>0$ is asymptotically $$2^{-1/2}\prod_{p\equiv 3\pmod{4}}(1-p^{-2})^{-1/2}\frac{x}{\sqrt{\log x}}.$$ For a proof, see Section 1.8 in Brüdern: Einführung in die analytische Zahlentheorie.

GH from MO
  • 105.4k
  • 8
  • 293
  • 398