Asymptotic growth of sum-of-two-squares function

Question

Let $r(n)$ denote the sum-of-two-squares function for $n \in \mathbb N$, that is, the number of pairs $(i,j) \in \mathbb Z^2$ such that $i^2+j^2=n$.

The paper Trigonometric polynomials and lattice points by Cilleruelo and Córdoba states (see second paragraph):

It is a well-known fact that $r(n) = O(n^\epsilon)$ for every $\epsilon > 0$.

Can you provide any reference where this result is proved, or discussed, or at least mentioned?

Answer 1

Niven/Zuckerman/Montgomery's An Introduction to the Theory of Numbers (5th ed., 1991) contains two standard (within the field) formulas for the number of such representations, which they call $R(n)$:

• Theorem 3.22: if $n=2^\alpha \prod_p p^\beta \prod_q q^\gamma$ where $p$ runs over the primes dividing $n$ that are $1$ (mod $4$) and $q$ runs over the primes dividing $n$ that are $3$ (mod $4$), then $R(n)$ equals $0$ unless all the $\gamma$ are even, in which case $R(n) = 4\prod_p(\beta+1)$.
• Corollary 3.23: $\frac14R(n)$ equals the number of divisors of $n$ that are $1$ (mod $4$) minus the number of divisors of $n$ that are $3$ (mod $4$); in other words, $R(n) = 4 \sum_{\substack{d\mid n \\ d\text{ odd}}} (\frac{-1}d)$ using the Jacobi symbol.

Either way we see that $R(n) \le 4\tau(n)$, where $\tau(n)$ is the number of divisors of $n$; and it is well known (but more well known and hopefully easier to find) that $\tau(n) \ll_\varepsilon n^\varepsilon$.

Caution: Niven/Zuckerman/Montgomery use $R(n)$ for the total number of representations of $n$ as the sum of two squares, but they also use $r(n)$ as the number of representations where the two squares are relatively prime; take care when reading.

Answer 2

The quick version: $$ r(n) < n^{\frac{1}{\log \log n}} $$ where the logarithms are base $e \approx 2.718281828459$

Turned out I had a program to do this. The sequence below, $$ 5, 65, 325, 5525, 160225, 5928325,... $$ are those with surprisingly many representations as the sum of two squares. The surprise is the same as in Ramanujan's Superior Highly Composite numbers, or Alaoglu and Erdos's Colossally Abundant numbers. For each of my numbers $n,$ there is a real $ \delta > 0$ such that $$ \frac{r(n)}{n^\delta} $$ is maximized for that $\delta$

Let's see, each number in the list is a prime $p \equiv 1 \pmod 4$ times the number in the line above it. The prime with exponent increased is the second item in each line

Compare https://oeis.org/A071383

=========================================================

index  prime jumped   product

1  5   5= 5
2  13   65= 5 13
3  5   325= 5^2 13
4  17   5525= 5^2 13 17
5  29   160225= 5^2 13 17 29
6  37   5928325= 5^2 13 17 29 37
7  41   243061325= 5^2 13 17 29 37 41
8  5   1215306625= 5^3 13 17 29 37 41
9  53   64411251125= 5^3 13 17 29 37 41 53
10  61   3929086318625= 5^3 13 17 29 37 41 53 61
11  73   286823301259625= 5^3 13 17 29 37 41 53 61 73
12  13   3728702916375125= 5^3 13^2 17 29 37 41 53 61 73
13  89   331854559557386125= 5^3 13^2 17 29 37 41 53 61 73 89
14  97   32189892277066454125= 5^3 13^2 17 29 37 41 53 61 73 89 97
15  17   547228168710129720125= 5^3 13^2 17^2 29 37 41 53 61 73 89 97
16  5   2736140843550648600625= 5^4 13^2 17^2 29 37 41 53 61 73 89 97
17  29   79348084462968809418125= 5^4 13^2 17^2 29^2 37 41 53 61 73 89 97
18  5   396740422314844047090625= 5^5 13^2 17^2 29^2 37 41 53 61 73 89 97
19  37   14679395625649229742353125= 5^5 13^2 17^2 29^2 37^2 41 53 61 73 89 97
20  13   190832143133439986650590625= 5^5 13^3 17^2 29^2 37^2 41 53 61 73 89 97
21  41   7824117868471039452674215625= 5^5 13^3 17^2 29^2 37^2 41^2 53 61 73 89 97
22  53   414678247028965090991733428125= 5^5 13^3 17^2 29^2 37^2 41^2 53^2 61 73 89 97
23  17   7049530199492406546859468278125= 5^5 13^3 17^3 29^2 37^2 41^2 53^2 61 73 89 97
24  61   430021342169036799358427564965625= 5^5 13^3 17^3 29^2 37^2 41^2 53^2 61^2 73 89 97
25  5   2150106710845183996792137824828125= 5^6 13^3 17^3 29^2 37^2 41^2 53^2 61^2 73 89 97
26  73   156957789891698431765826061212453125= 5^6 13^3 17^3 29^2 37^2 41^2 53^2 61^2 73^2 89 97
27  89   13969243300361160427158519447908328125= 5^6 13^3 17^3 29^2 37^2 41^2 53^2 61^2 73^2 89^2 97
index  prime jumped   product

=========================================================