2
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$ Dec 23, 2014 at 6:37
  • $\begingroup$ Thank you Noam D. Elkies, could you give me the references for these statements. $\endgroup$
    – M.Souf
    Dec 23, 2014 at 6:50
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 23, 2014 at 17:00
  • $\begingroup$ If you like my answer, please accept it officially (so that it turns green). Thanks in advance! $\endgroup$
    – GH from MO
    Aug 19, 2018 at 23:23

2 Answers 2

18
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.$

$\endgroup$
2
  • $\begingroup$ I edited your last two lines to make it more precise (and valid). $\endgroup$
    – GH from MO
    Dec 23, 2014 at 14:55
  • $\begingroup$ 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. $\endgroup$
    – Charles
    Dec 23, 2014 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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