Lagrange's four-square theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every nonnegative integer can be represented as a sum of four non-negative integer squares.
It is a special case of the Fermat polygonal number theorem.
From examples given in the Arithmetica, it is clear that Diophantus was aware of the theorem.
This book was translated in 1621 into Latin by Bachet (Claude Gaspard Bachet de Méziriac), who stated the theorem in the notes of his translation.
[2] Adrien-Marie Legendre extended the theorem in 1797–8 with his three-square theorem, by proving that a positive integer can be expressed as the sum of three squares if and only if it is not of the form
for integers k and m. Later, in 1834, Carl Gustav Jakob Jacobi discovered a simple formula for the number of representations of an integer as the sum of four squares with his own four-square theorem.
This is also linked to Apollonian gaskets, which were more recently related to the Ramanujan–Petersson conjecture.
[3] Several very similar modern versions[4][5][6] of Lagrange's proof exist.
The proof below is a slightly simplified version, in which the cases for which m is even or odd do not require separate arguments.
It is sufficient to prove the theorem for every odd prime number p. This immediately follows from Euler's four-square identity (and from the fact that the theorem is true for the numbers 1 and 2).
To see this, take some a and define c as a2 mod p. a is a root of the polynomial x2 − c over the field Z/pZ.
In a field K, any polynomial of degree n has at most n distinct roots (Lagrange's theorem (number theory)), so there are no other a with this property, in particular not among 0 to (p − 1)/2.
Similarly, for b taking integral values between 0 and (p − 1)/2 (inclusive), the −b2 − 1 are distinct.
Now let m be the smallest positive integer such that mp is the sum of four squares, x12 + x22 + x32 + x42 (we have just shown that there is some m (namely n) with this property, so there is a least one m, and it is smaller than p).
We show by contradiction that m equals 1: supposing it is not the case, we prove the existence of a positive integer r less than m, for which rp is also the sum of four squares (this is in the spirit of the infinite descent[7] method of Fermat).
For this purpose, we consider for each xi the yi which is in the same residue class modulo m and between (–m + 1)/2 and m/2 (possibly included).
It follows that y12 + y22 + y32 + y42 = mr, for some strictly positive integer r less than m. Finally, another appeal to Euler's four-square identity shows that mpmr = z12 + z22 + z32 + z42.
But the fact that each xi is congruent to its corresponding yi implies that all of the zi are divisible by m. Indeed,
It follows that, for wi = zi/m, w12 + w22 + w32 + w42 = rp, and this is in contradiction with the minimality of m. In the descent above, we must rule out both the case y1 = y2 = y3 = y4 = m/2 (which would give r = m and no descent), and also the case y1 = y2 = y3 = y4 = 0 (which would give r = 0 rather than strictly positive).
For both of those cases, one can check that mp = x12 + x22 + x32 + x42 would be a multiple of m2, contradicting the fact that p is a prime greater than m. Another way to prove the theorem relies on Hurwitz quaternions, which are the analog of integers for quaternions.
The proof of the main theorem begins by reduction to the case of prime numbers.
Euler's four-square identity implies that if Lagrange's four-square theorem holds for two numbers, it holds for the product of the two numbers.
To show this for an odd prime integer p, represent it as a quaternion
chosen has half-integer coefficients, it can be replaced by another Hurwitz quaternion.
As for showing that p is not a Hurwitz irreducible, Lagrange proved that any odd prime p divides at least one number of the form
The ring H of Hurwitz quaternions is not commutative, hence it is not an actual Euclidean domain, and it does not have unique factorization in the usual sense.
[10]) In 1986, Michael O. Rabin and Jeffrey Shallit[11] proposed randomized polynomial-time algorithms for computing a single representation
The sequence of positive integers which cannot be represented as a sum of four non-zero squares is: These integers consist of the eight odd numbers 1, 3, 5, 9, 11, 17, 29, 41 and all numbers of the form
Eduard Wirsing proved that there exists a set of squares S with
such that every positive integer smaller than or equal to n can be written as a sum of at most 4 elements of S.[15]
