Euler and the Four-Squares Theorem

There are several questions in the Euler-Goldbach correspondence that I am unable to answer. Sometimes it does not take very much: in his letter to Goldbach dated June 9th, 1750, Euler conjectured that every odd number can be written as a sum of four squares in such a way that $n = a^2 + b^2 + c^2 + d^2$ and $a+b+c+d = 1$. I was just about to post this to MO when I saw that Euler's conjecture can be reduced to the Three-Squares Theorem in one line (am I supposed to spoil this right away?). Here's another one where I haven't found a proof yet.

In his letter to Goldbach dated Apr.15, 1747, Euler wrote:

The theorem Any number can be split into four squares'' depends on this:Any number of the form $4m+2$ can always be split into two parts such as $4x+1$ and $4y+1$, none of which has any divisor of the form $4p-1$'' (which does not appear difficult, although I cannot yet prove it).

Later, Euler attributed to Goldbach the much stronger claim that the two summands can be chosen to be prime, which is a strong form of the Goldbach conjecture.

Euler's intention was proving the Four-Squares Theorem (which he almost did. Assuming this result, write $4m+2 = a^2+b^2+c^2+d^2$; then congruences modulo $8$ show that two numbers on the right hand side, say $a$ and $b$, are even, and the other two are odd. Now $a^2 + c^2 = 4x+1$ and $b^2 + d^2 = 4y+1$ satisfy Euler's conditions except when $a$ and $c$ (or $b$ and $d$) have a common prime factor of the form $4n-1$. Can this be excluded somehow?

Hermite [Oeuvres I, p. 259] considered a similar problem:

Tout nombre impair est decomposable en quatre carres et, parmi ces decompositions, il en existe toujours de telles que la somme de deux carrees soit sans diviseurs communs avec la somme de deux autres. (Every odd number can be decomposed into four squares, and among these decompositions, there always exist some for which the sum of two squares is coprime to the sum of the other two.)

Hermite's proof contains a gap. Can Hermite's claim be proved somehow?

-
Euler's intention was proving the Four-Squares Theorem, which is trivial for sums of two squares. But 18 = 3^2 + 3^2 is not what Euler was looking for. –  Franz Lemmermeyer Sep 1 '10 at 9:51
As for the claim that for every positive odd integer $n$ there is always an integral point on the intersection of the hypersphere $2n+1 = a^2 + b^2 + c^2 + d^2$ and the hyperplane $a+b+c+d=1$: solve the last equation for $d$, plug it into the first, and multiply through by $4$ and subtract $1$. Then $8m+3$ becomes a sum of three squares, so Euler's result is equivalent to this special case of the Three-Squares Theorem, or, if you happen to know it, to Gauss's theorem that every number is the sum of three triangular numbers. –  Franz Lemmermeyer Sep 1 '10 at 9:54

We address the problem of Euler, showing an asymptotic lower bound for the number of ways of writing $n\equiv 2 \pmod 4$ as a sum of four squares $a^2+b^2+c^2+d^2$ where neither $a^2+b^2$ nor $c^2+d^2$ is divisible by any prime $\equiv 3 \pmod 4$. For simplicity we shall only count the solutions where $a^2+b^2\equiv c^2+d^2 \equiv 1\pmod 4$.

Let $r(n)$ denote the number of ways of writing $n$ as a sum of two squares so that $r(n) = 4 \sum_{d|n} \chi_{-4}(d)$ with $\chi_{-4}$ being the non-trivial character $\pmod 4$. Clearly the number of solutions we want is at least $$\sum_{\substack{{a+b=n} \\ {a\equiv b\equiv 1 \pmod 4}}} r(a)r(b) - 2 \sum_{p\equiv 3 \pmod 4} \sum_{\substack{{a+b=n} \\ {a\equiv b\equiv 1\pmod 4} \\ {p^2 |a} }} r(a) r(b) = S-2T,$$ say. (The first sum counts all possible solutions with $a\equiv b\equiv 1 \pmod 4$ and the second sum excludes all solutions with either $a$ or $b$ being divisible by the square of sum prime $\equiv 3 \pmod 4$, and by symmetry we may assume that $a$ is the one divisible by $p^2$.)

Let us focus just on evaluating the sum $T$; the sum $S$ is simpler and may be handled similarly. Write the sum $T$ as $\sum_{p \equiv 3 \pmod 4} T(p)$, so that (since $r(ap^2)=r(a)$)
$$T(p) = \sum_{\substack{ {a p^2 +b =n} \\ {a\equiv b\equiv 1\pmod 4}}} r(a) r(b).$$ Since $r(k)\ll k^{\epsilon}$ for all $k$, clearly $T(p) \ll n^{1+\epsilon}/p^2$, so that large primes $p$ contribute a negligible amount. Now let us suppose that $p$ is small.
Now if $a\equiv 1 \pmod 4$ we have $$r(a) = 4\sum_{k\ell =a} \chi_{-4}(a) = 8\sum_{\substack{ {k|a} \\ {k\le \sqrt{a} } }}^{\prime} \chi_{-4}(k),$$ using that $\chi_{-4}(k)=\chi_{-4}(\ell)$ (because $k\ell\equiv 1\pmod 4$), and the prime over the sum indicates that the term $k=\sqrt{a}$ is counted with weight $1/2$.
Therefore $$T(p) =8 \sum_{k}^{\prime} \chi_{-4}(k) \sum_{\substack{{b=n-p^2 k \ell} \\ {b\equiv 1\pmod 4} \\ {\ell \ge k}} } r(b).$$ Now the sum over $b$ above is just a sum over values $b$ that are at most $n-p^2 k^2$ and satisfying the congruence conditions $b\equiv 1\pmod 4$ and $b\equiv n \pmod{p^2k}$.
In other words, this is a problem of understanding the distribution of the sums of two squares function in arithmetic progressions.

Sums of two squares in arithmetic progressions. Let us quickly recall what is known about this problem. Let $R(x;q,a)$ be the sum of $r(n)$ over all $n\le x$ with $n\equiv a \pmod q$. The key result we need is that there is a good asymptotic formula for $R(x;q,a)$ uniformly for $q$ up to $x^{2/3-\epsilon}$. This is due to Selberg and Hooley (unpublished), with details first appearing in a paper of R. A. Smith. For a recent nice version see Tolev's paper in Proc. Steklov Inst. (2012, vol 276, 261--274), whose version we shall use. Let $\eta_a(q)$ denote the number of solutions to the congruence $x^2+y^2 \equiv a \pmod q$ with $1\le x, y \le q$. Then $$\sum_{\substack{ {n\le x} \\ {n\equiv a\pmod q}} } r(n) = \pi \frac{\eta_a(q)}{q^2} x + O((q^{\frac 12} + x^{\frac 13}) (a,q)^{\frac 12} x^{\epsilon}).$$ Note that this bound uses the Weil bound for Kloosterman sums; but for our application we need only a bound that permits $q$ a little larger than $\sqrt{x}$, and less precise elementary estimates for Kloosterman sums would suffice for this.

On the function $\eta_a(q)$. Note also that $\eta_a(q)$ is a multiplicative function of $q$, and is always $\ll q d(q)$ (where $d(q)$ is the number of divisors of $q$). In fact it is not hard to compute what $\eta_a(q)$ is, and as we shall need this below we summarize this calculation. If $p$ is an odd prime not dividing $a$ then we may show that $\eta_a(p^{k}) = p^{k-1} (p-\chi_{-4}(p))$. If $p$ is an odd prime that does divide $a$, then to compute $\eta_a(p^k)$ we classify the solutions to $x^2+y^2 \equiv a \pmod {p^k}$ as non-singular if $p$ doesn't divide one of $x$ or $y$ and singular otherwise. The non-singular solutions are seen to number $2p^{k-1}(p-1)$ if $p\equiv 1\pmod 4$ and $0$ if $p\equiv 3 \pmod 4$. As for the singular solutions, if $k=1$ then this number is just $1$; if $k\ge 2$ and $p^2 \nmid a$ there are no singular solutions; and if $k\ge 2$ and $p^2|a$ then the number of singular solutions is $p^2 \eta_{a/p^2}(p^{k-2})$. This describes fully how to compute $\eta_a(q)$. From this description and some calculation we find that $$\sum_{k=1}^{\infty} \chi_{-4}(k) \frac{\eta_a(k)}{k^{1+s}} = \frac{L(s,\chi_{-4})}{\zeta_2(s+1)} {\tilde \sigma}_s(n)$$ where $\zeta_2(s) = \zeta(s) (1-2^{-s})$ (the Euler factor at $2$ removed), and $${\tilde \sigma}_s(n) = \sum_{\substack{{d|n}\\ {d \text{ odd}} } } d^{-s}.$$
Given a prime $p\equiv 3 \pmod 4$, for our work on $T(p)$ we shall also need to understand the following related Dirichlet series: $$\sum_{k=1}^{\infty} \chi_{-4}(k) \frac{\eta_a(kp^2)}{k^{1+s}}$$ and by a similar calculation we see that if $p\nmid a$ this equals $$p(p+1)\Big(1-\frac{1}{p^{s+1}}\Big)^{-1} \frac{L(s,\chi_{-4})}{\zeta_2(s+1)} {\tilde \sigma}_s(n);$$ and if $p|a$ but $p^2\nmid a$ it is zero; and if $p^2|a$ it equals $$p^2 \frac{L(s,\chi_{-4})}{\zeta_2(s+1)} {\tilde \sigma}_s(n/p^2) .$$

Back to $T(p)$. We now use the asymptotic formula above in our expression for $T(p)$. Since $\eta_1(4) = 8$ we obtain that $$T(p) = 4\pi \sum_{k \le \sqrt{n}/p} \chi_{-4}(k) \Big( \frac{\eta_n(p^2k)}{p^4 k^2} (n-p^2k^2) + O\Big((p\sqrt{k} +n^{\frac 13}) (n,p^2k)^{\frac 12} n^{\epsilon}\Big)\Big).$$ There are three cases: either $p\nmid n$, $p|n$ but $p^2\nmid n$, and $p^2|n$.

Consider the first case when $p\nmid n$. Here the error terms may be bounded easily as $$O\Big( \frac{n^{\frac 56+\epsilon}}{p} + \frac{n^{\frac 34+\epsilon}}{\sqrt{p}}\Big).$$ Now consider the main term which is $$4\pi \frac{n}{p^4} \sum_{k\le \sqrt{n}/p} \chi_{-4}(k) \frac{\eta_n(p^2k)}{k^2} \Big(1 - \frac{p^2k^2}{n}\Big).$$ We can express this as a contour integral (for some suitably large $c$) $$4\pi \frac{n}{p^4} \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \Big(\sum_{k=1}^{\infty} \chi_{-4}(k) \frac{\eta_n(p^2k)}{k^{2+s}}\Big) \Big( \frac{\sqrt{n}}{p}\Big)^s \frac{2}{s(s+2)}ds.$$ Using our knowledge of the Dirichlet series above, we get that the above is $$4\pi \frac{n}{p^4} \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} p (p+1) \Big(1-\frac{1}{p^{2+s}}\Big)^{-1} \frac{L(1+s,\chi_{-4})}{\zeta_2(s+2)} {\tilde \sigma}_{1+s}(n) \Big(\frac{\sqrt{n}}{p}\Big)^s \frac{2}{s(s+2)} ds.$$ Now moving the line of integration to Re$(s)=-1+\epsilon$ we obtain that the above is $$4\pi \frac{n}{p^4} \Big( p(p+1) \Big(1-\frac{1}{p^2}\Big)^{-1} \frac{L(1,\chi_{-4})}{\zeta_2(2)} {\tilde \sigma}_1(n) + O\Big( p^3 n^{-\frac 12+\epsilon}\Big) \Big).$$ Since $L(1,\chi_{-4}) =\pi/4$ and $\zeta_2(2) = \pi^2/8$ the above is $$8 \frac{n}{p^2} \Big(1-\frac{1}{p}\Big)^{-1} {\tilde \sigma}_1(n) + O\Big( \frac{n^{\frac 12+\epsilon}}{p}\Big).$$ Thus in this case we find that $$T(p) = 8\frac{n}{p^2} \Big(1-\frac{1}{p}\Big)^{-1} {\tilde \sigma}_1(n) + O\Big( \frac{n^{\frac 56+\epsilon}}{p} + \frac{n^{\frac 34+\epsilon}}{\sqrt{p}} \Big).$$ Recall also that $T(p) \ll n^{1+\epsilon}/p^2$ which is useful if $p$ is very large.

In the second case when $p|n$ but $p^2\nmid n$, trivially $T(p)=0$.

Finally if $p^2|n$ then we carry out a similar argument to the one above. This gives $$T(p) = 8\frac{n}{p^2} {\tilde \sigma}_1(n/p^2) + O \Big(n^{\frac 56+\epsilon} +\sqrt{p} n^{\frac 34+\epsilon} \Big).$$ Once again $T(p)\ll n^{1+\epsilon}/p^2$ which is useful for large $p$.

Putting all our work above, and splitting into the cases $p\le n^{1/6}$ (where we use our asymptotic formula) and $p>n^{1/6}$ (where we use the trivial bound $\ll n^{1+\epsilon}/p^2$) we obtain that $$T(p) = 8n {\tilde \sigma}_1(n) \sum_{\substack{{p\equiv 3 \pmod 4} \\ {p\nmid n}}} \frac{1}{p(p-1)} + 8n \sum_{\substack{{p\equiv 3 \pmod 4} \\ {p^2 |n}}} \frac{1}{p^2} {\tilde \sigma}_1(n/p^2) +O(n^{\frac 56+\epsilon}).$$

Conclusion. In the same way, we find that $$S = 8n {\tilde \sigma}_1(n) + O(n^{\frac 56+\epsilon}).$$ It follows that the number of solutions to Euler's question is at least $$S-2T \ge 8n {\tilde \sigma}_1(n) \Big( 1- \sum_{p\equiv 3 \pmod 4} \frac{2}{p(p-1)}\Big) + O(n^{\frac 56+\epsilon}) \ge 4n {\tilde \sigma}_1(n) + O(n^{\frac 56+\epsilon}).$$

Remarks. With more work one can establish an asymptotic in Euler's problem rather than just the lower bound. Similarly one can give an asymptotic in Hermite's problem. In principle one can make all the error terms explicit, and possibly obtain a complete result for all $n$, but this would entail a lot of work.
Lastly in connection with Hermite's problem, a classical problem of Hardy and Littlewood asks for the representations of numbers as $p+x^2+y^2$ with $p$ a prime. This was resolved by Hooley on GRH, and Linnik unconditionally. Once the Bombieri-Vinogradov theorem became available, the result became much simpler.
This could be modified to give a stronger version of Hermite's problem for large $n$, by also asking for $p$ to be $1\pmod 4$ -- a cross between Hermite and Goldbach.

-
This could be a nice paper. –  Gerry Myerson Sep 3 '13 at 6:52
Who is "we", and where will all of this be published? –  Franz Lemmermeyer Sep 3 '13 at 9:16
To Gerry Myerson and Franz Lemmermeyer -- Thanks for your comments. At the moment I have no intention of publishing this any further. I enjoyed very much Franz's article on the Euler-Goldbach correspondence, and it was fun to work this out. After all, how often does one get to answer a question of Euler? –  Lucia Sep 3 '13 at 19:38

The post below is jointly by Rainer Dietmann and Christian Elsholtz. We had worked on the problem since a while and had an independent asymptotic solution to Euler's problem. Our argument is possibly easier, but in it's current form it does does not achieve the correct order of magnitude of the number of solutions. This seems to be a very nice feature of Lucia's approach!

We had intended to make the argument entirely explicit in order to prove the statement for all $n$, not only for sufficienly large $n$. (See also the comments after the second argument below).

We also had intended to prepare these results for publication.

Lucia, we would appreciate if you could contact us by email, the email adresses (RD in Royal Holloway and CE in Graz) are easy to find.

$\textbf{Theorem:}$ Let $n$ be a sufficiently large positive integer with $n \equiv 2 \pmod 4$. Then $n$ can be written as the sum of two positive integers, none of them having any prime factor $p$ with $p \equiv 3 \pmod 4$.

This asymptotically answers a question of Euler. Important partial results are due to R.D. James (TAMS 43 (1938), 296--302) who proved the ternary case and an approximation to the binary case. Indeed the ternary case allows for an elementary proof, based on Gaus' theorem on the sum of three triangular numbers: Any integer $k$ can be written as $k = \frac{x(x-1)}{2}+ \frac{y(y-1)}{2} + \frac{z(z-1)}{2}$ and therefore $$4k + 3 = (x^2 + (x - 1)^2) + (y^2 + (y - 1)^2) + (z^2 + (z - 1)^2).$$ Observe that $(x^2 + (x - 1)^2)$ is a sum of two adjacent squares, and thus cannot be divisible by any prime $p = 3 \mod 4$. (Recall here and for later reference the following $\textbf{Fact:}$ if $p|n = s^2 +t^2$, with $p = 3 \mod 4$ prime, then $p|s$ and $p|t$.)

Using a well known result of the late George Greaves, one gets a short proof of the Theorem.

$\textbf{Proof.}$ By a result of Greaves (Acta Arith 29 (1976), 257--274), each sufficiently large positive integer $n$ with $n \equiv 2 \pmod 4$ can be written in the form $$n = p^2+q^2+x^2+y^2$$ for rational primes $p, q$ and integers $x, y$, and the number of such representations is at least of order of magnitude $n (\log n)^{-5/2}$. We write $a=p^2+x^2$ and $b=q^2+y^2$ and take multiplicities into account: namely the number of representations $r_2(a)$ of $a$ as a sum of two squares is $r_2(a) \leq d(a)\ll a^{\varepsilon}\ll n^{\varepsilon}$. The same holds for $r_2(b)$. We therefore find that there are at least $$n^{1-2\varepsilon}$$ many tuples $(a, b)$ with positive integers $a, b$, such that $n=a+b$ and both $a$ and $b$ are the sum of the square of a prime and the square of an integer. Now suppose that $w$ is a prime with $w \equiv 3 \pmod 4$ and $w$ divides $a=p^2+x^2$, say. Then by the `fact' above and as $p$ is prime this implies that $p=w$ and $x$ is divisible by $w$. Therefore, at most $O(1+n^{1/2}/w)$ many $a$ can be divisible by $w$, and for any such $a$ there will be only one corresponding $b$ since $a+b=n$. The same argument applies if $w$ divides $b$. Moreover, clearly $w$ can be at most $n^{1/2}$. Summing over all such $w$ we conclude that the number of tuples $(a,b)$ with $a+b=n$ and $a, b$ of the form above, where one of $a$ and $b$ is divisible by any prime congruent $3 \mod 4$, is at most $O(n^{1/2} \log \log n)$, which is of smaller order of magnitude than the expression $n^{1-2\varepsilon}$ above. This finishes the proof.

$\textbf{Remark.}$ It seems likely that the number of representations $f(n)$ can be greatly improved by observing that one only needs $r_2(a)$ on average. This should produce $f(n)$ within a logarithmic factor. Moreover it seems possible to adapt Greaves's argument by replacing $p^2$ and $q^2$ by squares of integers not containing a prime $3\bmod 4$, achieving a further logarithmic saving.

(Let us briefly reflect why the argument works: Greaves uses the fact that Iwaniec's half dimensional sieve can also handle sums of two squares. The contribution from the almost trivial 'fact' is also quite useful.)

Let us briefly sketch another possible approach, which could be more suitable for getting a result for all positive integers: Let $f(n)$ denote the number of representations as a sum of two integers, both not containing any prime factor $3 \bmod 4$. Let $r_{(a,b,c,d)}(n)$ denote the number of representations as sum $ax^2+by^2+cz^2+dt^2$. We intend to show that $$n^\varepsilon r(n) \gg r_{(1,1,1,1)}(n)- 2 \sum_{p=3 \bmod 4} r_{(1,1,p^2,p^2)}(n) \gg r_{(1,1,1,1)}(n).$$ Observe that $r_{(1,1,p^2,p^2)}(n)\approx \frac{1}{p^2}r_{(1,1,1,1)}$ and that $\sum_{p =3\mod 4} \frac{1}{p^2}$ is a small and finite number.

For a completely explicit result all we need is an explicit lower bound on $r_{(1,1,1,1)}(n)$, which can be derived from Jacobi's formula, and an explicit upper bound on expressions like $r_{(1,1,p^2,p^2)}(n)$, which can be obtained either by the circle method using a Kloosterman refinement, a modular forms approach, or via Dirichlet's hyperbola method. The big question then is if the resulting numerical bounds allow the remaining finitely many cases to be checked by a computer.

-
Dear Rainer and Christian: I'll get in touch with you later today. For the moment let me note that the second approach you mention is in fact the one used in my answer (essentially), and I agree that it could be made entirely explicit. More by email ... –  Lucia Sep 5 '13 at 14:11