Lagrange's four-square theorem
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. That is, the squares form an additive basis of order four. formula_1 where the four numbers formula_2 are integers. For illustration, 3, 31, and 310 in several ways, can be represented as the sum of four squares as follows: formula_3 This theorem was proven by Joseph Louis Lagrange in 1770. It is a special case of the Fermat polygonal number theorem. 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 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 formula_4 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. Proofs. 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. Proof using  the Hurwitz integers. Another way to prove the theorem relies on Hurwitz quaternions, which are the analog of integers for quaternions. 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 formula_5, can we solve formula_6 for all positive integers in integers formula_7? The case formula_8 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 formula_9 then there are exactly  54 possible choices for formula_5 such that the problem is solvable in integers formula_7 for all . (Ramanujan listed a 55th possibility formula_12, but in this case the problem is not solvable if formula_13.) Algorithms. In 1986, Michael O. Rabin and Jeffrey Shallit proposed randomized polynomial-time algorithms for computing a single representation formula_14 for a given integer , in expected running time formula_15. It was further improved to formula_16 by Paul Pollack and Enrique Treviño in 2018. Number of representations. The number of representations of a natural number "n" as the sum of four squares is denoted by "r"("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. formula_17 Equivalently, it is eight times the sum of all its divisors which are not divisible by 4, i.e. formula_18 We may also write this as formula_19 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 . Some values of "r"("n") occur  infinitely often as whenever "n" is even. The values of "r"("n")/"n" can be arbitrarily large: indeed, "r"("n")/"n" is infinitely often larger than 8. Uniqueness. The sequence of positive integers which have only one representation as a sum of four squares (up to order) is: These integers consist of the seven odd numbers 1, 3, 5, 7, 11, 15, 23 and all numbers of the form formula_20 or formula_21. 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 formula_20 or formula_21. Further refinements. Lagrange's four-square theorem can be refined in various ways. For example, Zhi-Wei Sun proved that each natural number can be written as a sum of four squares with some requirements on the choice of these four numbers. One may also wonder whether it is necessary to use the entire set of square integers to write each natural as the sum of four squares. Eduard Wirsing proved that there exists a set of squares with formula_24 such that every positive integer smaller than or  equal can be written as a sum of at most 4 elements of .