Lagrange's four-square theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that any natural number can be represented as the sum of four integer squares
where the four numbers are integers. For illustration, 3, 31 and 310 can be represented as the sum of four squares as follows:
This theorem was proven by Joseph Louis Lagrange in 1770.
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, who stated the theorem in the notes of his translation. But the theorem was not proven 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 for integers and . 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.
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 are easy to find in the literature. 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).
For a and b taking integral values between 0 and (p-1)/2 (included), the a2 are distinct residues modulo p, as are the -b2-1. 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 m p is the sum of four squares, x12 + x22 + x32 + x42. 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 r p 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 = m r, for some positive integer r less than m.
Finally, another appeal to Euler's four-square identity shows that m p m r = z12 + z22 + z32 + z42, where each zi is divisible by m (indeed, since each xi is congruent to his corresponding yi, z1 is congruent modulo m to y12 + y22 + y32 + y42 = m r; for the same reason the other zi are also divisible by m). It follows that, for wi = zi/m, w12 + w22 + w32 + w42 = r p, and this is in contradiction with the minimality of 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 are integers. Thus, the quaternion components are either all integers or all half-integers, depending on whether is even or odd, respectively. The set of Hurwitz quaternions forms a ring; that is to say, the sum or product of any two Hurwitz quaternions is likewise a Hurwitz quaternion.
where is the conjugate of . Note that the norm of a Hurwitz quaternion is always an integer. (If the coefficients are half-integers, then using modular arithmetic their squares are numbers equivalent to , and the sum of four such numbers is an integer.)
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 , . It follows easily that is a unit in the ring of Hurwitz quaternions if and only if .
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 . To show this for an odd prime integer , represent it as a quaternion and assume for now (as we shall show later) that it is not a Hurwitz irreducible; that is, it can be factored into two non-unit Hurwitz quaternions
The norms of are integers such that
and . This shows that both and are equal to (since they are integers), and is the sum of four squares
If it happens that the chosen has half-integer coefficients, it can be replaced by another Hurwitz quaternion. Choose in such a way that has even integer coefficients. Then
Since has even integer coefficients, will have integer coefficients and can be used instead of the original to give a representation of as the sum of four squares.
As for showing that is not a Hurwitz irreducible, Lagrange proved that any odd prime divides at least one number of the form , where and are integers. This can be seen as follows: since is prime, can hold for integers , only when . Thus, the set of squares contains distinct residues modulo . Likewise, contains residues. Since there are only residues in total, and , the sets and must intersect.
The number can be factored in Hurwitz quaternions:
The norm on Hurwitz quaternions satisfies a form of the Euclidean property: for any quaternion with rational coefficients we can choose a Hurwitz quaternion so that by first choosing so that and then so that for . Then we obtain
It follows that for any Hurwitz quaternions with , there exists a Hurwitz quaternion such that
The ring 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. Nevertheless, the property above implies that every right ideal is principal. Thus, there is a Hurwitz quaternion such that
In particular, for some Hurwitz quaternion . If were a unit, would be a multiple of , however this is impossible as is not a Hurwitz quaternion for . Similarly, if were a unit, we would have
so divides , which again contradicts the fact that is not a Hurwitz quaternion. Thus, is not Hurwitz irreducible, as claimed.
Lagrange's four-square theorem is a special case of the Fermat polygonal number theorem and Waring's problem. Another possible generalisation is the following problem: Given natural numbers , can we solve
for all positive integers in integers ? The case is answered in the positive by Lagrange's four-square theorem. The general solution was given by Ramanujan. He proved that if we assume, without loss of generality, that then there are exactly 54 possible choices for such that the problem is solvable in integers for all . (Ramanujan listed a 55th possibility , but in this case the problem is not solvable if .)
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
Some values of r4(n) occurs 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.
The sequence of positive integers whose representation as a sum of four squares is unique (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 OEIS).
These integers consist of the seven odd numbers 1, 3, 5, 7, 11, 15, 23 and all numbers of the form or .
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 OEIS).
These integers consist of the eight odd numbers 1, 3, 5, 9, 11, 17, 29, 41 and all numbers of the form or .
- Ireland and Rosen (1990). A Classical Introduction to Modern Number Theory. Springer-Verlag. ISBN 0-387-97329-X.
- The Ramanujan Conjecture and some Diophantine Equations, Peter Sarnak, lecture at Tata Institute of Fundamental Research, of the ICTS lecture series. Bangalore, 2013 via youtube.
- Theorems 166 to 169 in : E. Landau, Vorlesungen über Zahlentheorie, New York, Chelsea, 1927. Second edition translated into English by Jacob E. Goodman, Providence RH, Chelsea, 1958.
- Theorem 369 in : G.H. Hardy and E.M. Wright, An introduction to the theory of numbers, Oxford, Clarendon Press 1938.
- Paragraph 5.7 in : Ivan Niven and Herbert S. Zuckerman, An introduction to the theory of numbers, John Wiley and Sons 1960.
- Here the argument is a direct proof by contradiction. With the initial assumption that m>2, m<p, is some integer such that mp is the sum of four squares (not necessarily the smallest), the argument could be modified to become an infinite descent argument in the spirit of Fermat.
- Stillwell, John (2003). Elements of Number Theory. New York: Springer-Verlag. pp. 138–157. ISBN 0-387-95587-9. Zbl 1112.11002.
- Myung-Hwan Kim REPRESENTATIONS OF BINARY FORMS BY QUINARY QUADRATIC FORMS
- M. O. Rabin, J. O. Shallit, Randomized Algorithms in Number Theory, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256. doi:10.1002/cpa.3160390713
- Williams, Kenneth S. (2011). Number theory in the spirit of Liouville. London Mathematical Society Student Texts 76. Cambridge: Cambridge University Press. ISBN 978-0-521-17562-3. Zbl 1227.11002.
- Williams (2011) p.119