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?
 A: 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.
