# Growth of $r_{2}(n)$

Let $n$ be a positive integer. From Jacobi's two-square theorem we know that the number $r_{2}(n)$ of representations of $n$ as a sum of two squares is given by $$r_{2}(n)=4(d_{1}(n)-d_{3}(n)),$$ where $$d_{i}(n)=\sum_{d\mid n,d\equiv i{\rm (mod\,4)}} 1.$$ But, what can we say about the growth of $r_{2}(n)$ when $n$ increases? Is it a polynomial or logarithmic growth (according to $n$)? and what is the best-known approximation in this sense?

Thank you.

• It is known that $r_2(n)$ is usually zero: the number of $n<x$ such that $r_2(n) > 0$ is asymptotic to a multiple of $x\,\big/\sqrt{\log x} = o(x)$. But if $n$ is a product of $k$ distinct primes each congruent to $1 \bmod 4$ then $r_2(n) = 2^{k+2}$, which is $n^{o(1)}$ but grows much faster than polynomial in $\log n$ if we use the first $k$ primes in that congruence class. – Noam D. Elkies Dec 23 '14 at 6:37
• Thank you Noam D. Elkies, could you give me the references for these statements. – M.Souf Dec 23 '14 at 6:50
• Sorry, if I had references to hand I'd have given an answer rather than a comment. I see that meanwhile GH from MO supplied a more thorough answer with sources, so I refer you to his answer for further information. – Noam D. Elkies Dec 23 '14 at 17:00
• If you like my answer, please accept it officially (so that it turns green). Thanks in advance! – GH from MO Aug 19 '18 at 23:23

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 even or odd. 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 sharpness of $\log 2$ 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.

Plotting records (from A071383 and A071385) suggests that an upper bound of the form $$\log r_2(n)\ll\log^\alpha n$$ is plausible, perhaps for $\alpha$ around $0.6$ or $0.7$. Polynomial bounds seem too large, while polylog bounds seem too small.

Edit: See the answer by GH from MO which shows that $$\leq\frac{(\log 2+o(1))\log n}{\log\log n}$$ should be used in place of $\ll\log^\alpha n.$

• I edited your last two lines to make it more precise (and valid). – GH from MO Dec 23 '14 at 14:55
• Note: I gave my answer only because there were no others at the time, and I wanted to give some support for an intermediate (between logarithmic and polynomial) growth rate. – Charles Dec 23 '14 at 15:00

There is no good asymptotic expansion for $r_2(n)$. However, it is well known that $$\sum_{n\le x}r_2(n) = \pi x + \mathcal{O}(\sqrt{x})$$ by counting lattice points in a circle of radius $\sqrt{x}$. (The error term can be improved)

• While it's nice to see the Gauss Circle Problem get an airing, I don't think this answers the original question – Yemon Choi Dec 23 '14 at 6:11
• @Yemon, the original question was, "what can we say about the growth of $r_2(n)$ when $n$ increases?" and strictly speaking the only possible answer is, "we can't say anything about it, since $r_2(n)$ doesn't grow as $n$ increases; it bobs up and down". The original question needs to be changed before it can sensibly be answered. One reasonable change is to ask how the function grows on average. And Mayank answers that question. – Gerry Myerson Dec 25 '14 at 1:01