Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares.
Contents
- Historical development
- The classical proof
- Proof using the Hurwitz integers
- Generalizations
- Algorithms
- Number of representations
- Uniqueness
- References
where the four numbers
This theorem was proven by Joseph Louis Lagrange in 1770.
Historical development
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. But the theorem was not proved until 1770 by Lagrange.
Adrien-Marie Legendre completed 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
The formula is also linked to Descartes' theorem of four "kissing circles", which involves the sum of the squares of the curvatures of four circles. This is also linked to Apollonian gaskets, which were more recently related to the Ramanujan–Petersson conjecture.
The classical proof
Several very similar modern versions 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).
The residues of a2 modulo p are distinct for every a between 0 and (p − 1)/2 (inclusive). 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. So is p − a (which is different from a). 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. By the pigeonhole principle, there are a and b in this range, for which a2 and −b2 − 1 are congruent modulo p, that is for which
with 0 < n < p.
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 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 (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 his 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 prime greater than m.
Proof using the Hurwitz integers
One of the ways to prove the theorem relies on Hurwitz quaternions, which are the analog of integers for quaternions. The Hurwitz quaternions consist of all quaternions with integer components and all quaternions with half-integer components. These two sets can be combined into a single formula
where
The (arithmetic, or field) norm
where
Since quaternion multiplication is associative, and real numbers commute with other quaternions, the norm of a product of quaternions equals the product of the norms:
For any
The proof of the main theorem begins by reduction to the case of prime numbers. Euler's four-square identity implies that if Langrange's four-square theorem holds for two numbers, it holds for the product of the two numbers. Since any natural number can be factored into powers of primes, it suffices to prove the theorem for prime numbers. It is true for
The norms of
and
If it happens that the
Since
As for showing that
The number
The norm on Hurwitz quaternions satisfies a form of the Euclidean property: for any quaternion
It follows that for any Hurwitz quaternions
The ring
In particular,
so
Generalizations
Lagrange's four-square theorem is a special case of the Fermat polygonal number theorem and Waring's problem. Another possible generalization is the following problem: Given natural numbers
for all positive integers
Algorithms
Michael O. Rabin and Jeffrey Shallit have found randomized polynomial-time algorithms for computing a single representation
Number of representations
The number of representations of a natural number n as the sum of four squares is denoted by r4(n). Jacobi's four-square theorem states that this is eight times the sum of the divisors of n if n is odd and 24 times the sum of the odd divisors of n if n is even (see divisor function), i.e.
Equivalently, it is eight times the sum of all its divisors which are not divisible by 4, i.e.
We may also write this as
where the second term is to be taken as zero if n is not divisible by 4. In particular, for a prime number p we have the explicit formula r4(p) = 8(p + 1).
Some values of r4(n) occur infinitely often as r4(n) = r4(2mn) whenever n is even. The values of r4(n)/n can be arbitrarily large: indeed, r4(n)/n is infinitely often larger than 8 √ log n.
Uniqueness
The sequence of positive integers which have only one representation as a sum of four squares (up to order) is:
1, 2, 3, 5, 6, 7, 8, 11, 14, 15, 23, 24, 32, 56, 96, 128, 224, 384, 512, 896 ... (sequence A006431 in the OEIS).These integers consist of the seven odd numbers 1, 3, 5, 7, 11, 15, 23 and all numbers of the form
The sequence of positive integers which cannot be represented as a sum of four non-zero squares is:
1, 2, 3, 5, 6, 8, 9, 11, 14, 17, 24, 29, 32, 41, 56, 96, 128, 224, 384, 512, 896 ... (sequence A000534 in the OEIS).These integers consist of the eight odd numbers 1, 3, 5, 9, 11, 17, 29, 41 and all numbers of the form