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. That is, the squares form an additive basis of order four:
p = a 2 + b 2 + c 2 + d 2 , {\displaystyle p=a^{2}+b^{2}+c^{2}+d^{2},} where the four numbers a , b , c , d {\displaystyle a,b,c,d} are integers. For illustration, 3, 31, and 310 can be represented as the sum of four squares as follows:
3 = 1 2 + 1 2 + 1 2 + 0 2 31 = 5 2 + 2 2 + 1 2 + 1 2 310 = 17 2 + 4 2 + 2 2 + 1 2 = 16 2 + 7 2 + 2 2 + 1 2 = 15 2 + 9 2 + 2 2 + 0 2 = 12 2 + 11 2 + 6 2 + 3 2 . {\displaystyle {\begin{aligned}3&=1^{2}+1^{2}+1^{2}+0^{2}\\[3pt]31&=5^{2}+2^{2}+1^{2}+1^{2}\\[3pt]310&=17^{2}+4^{2}+2^{2}+1^{2}\\[3pt]&=16^{2}+7^{2}+2^{2}+1^{2}\\[3pt]&=15^{2}+9^{2}+2^{2}+0^{2}\\[3pt]&=12^{2}+11^{2}+6^{2}+3^{2}.\end{aligned}}}
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 4 k ( 8 m + 7 ) {\displaystyle 4^{k}(8m+7)} 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. 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 a , b , c , d {\displaystyle a,b,c,d} , can we solve
n = a x 1 2 + b x 2 2 + c x 3 2 + d x 4 2 {\displaystyle n=ax_{1}^{2}+bx_{2}^{2}+cx_{3}^{2}+dx_{4}^{2}}
for all positive integers n in integers x 1 , x 2 , x 3 , x 4 {\displaystyle x_{1},x_{2},x_{3},x_{4}} ? The case a = b = c = d = 1 {\displaystyle a=b=c=d=1} 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 a ≤ b ≤ c ≤ d {\displaystyle a\leq b\leq c\leq d} then there are exactly 54 possible choices for a , b , c , d {\displaystyle a,b,c,d} such that the problem is solvable in integers x 1 , x 2 , x 3 , x 4 {\displaystyle x_{1},x_{2},x_{3},x_{4}} for all n. (Ramanujan listed a 55th possibility a = 1 , b = 2 , c = 5 , d = 5 {\displaystyle a=1,b=2,c=5,d=5} , but in this case the problem is not solvable if n = 15 {\displaystyle n=15} .)
Algorithms In 1986, Michael O. Rabin and Jeffrey Shallit proposed randomized polynomial-time algorithms for computing a single representation n = x 1 2 + x 2 2 + x 3 2 + x 4 2 {\displaystyle n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}} for a given integer n, in expected running time O ( log 2 ( n ) ) {\displaystyle \mathrm {O} (\log ^{2}(n))} . It was further improved to O ( log 2 ( n ) log ( log ( n ) ) − 1 ) {\displaystyle \mathrm {O} (\log ^{2}(n)\log(\log(n))^{-1})} 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 of integers 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.
r 4 ( n ) = { 8 ∑ m ∣ n m if n is odd 24 ∑ m | n m odd m if n is even . {\displaystyle r_{4}(n)={\begin{cases}8\sum \limits _{m\mid n}m&{\text{if }}n{\text{ is odd}}\\[12pt]24\sum \limits _{\begin{smallmatrix}m|n\\m{\text{ odd}}\end{smallmatrix}}m&{\text{if }}n{\text{ is even}}.\end{cases}}}
Equivalently, it is eight times the sum of all its divisors which are not divisible by 4, i.e.
r 4 ( n ) = 8 ∑ m : 4 ∤ m ∣ n m . {\displaystyle r_{4}(n)=8\sum _{m\,:\,4\nmid m\mid n}m.}
We may also write this as
r 4 ( n ) = 8 σ ( n ) − 32 σ ( n / 4 ) , {\displaystyle r_{4}(n)=8\sigma (n)-32\sigma (n/4)\ ,}
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 of non-negative integers (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 2 ( 4 k ) , 6 ( 4 k ) {\displaystyle 2(4^{k}),6(4^{k})} or 14 ( 4 k ) {\displaystyle 14(4^{k})} . 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 2 ( 4 k ) , 6 ( 4 k ) {\displaystyle 2(4^{k}),6(4^{k})} or 14 ( 4 k ) {\displaystyle 14(4^{k})} .
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 S with | S | = O ( n 1 / 4 log 1 / 4 n ) {\displaystyle |S|=O(n^{1/4}\log ^{1/4}n)} such that every positive integer smaller than or equal to n can be written as a sum of at most 4 elements of S.
See also Fermat's theorem on sums of two squares Fermat's polygonal number theorem Waring's problem Legendre's three-square theorem Sum of two squares theorem Sum of squares function 15 and 290 theorems
Notes
References Hardy, G. H.; Wright, E. M. (2008) [1938]. Heath-Brown, D. R.; Silverman, J. H.; Wiles, Andrew (eds.). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 978-0-19-921985-8. Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (2nd ed.). Springer. doi:10.1007/978-1-4757-2103-4. ISBN 978-1-4419-3094-1. Landau, Edmund (1958) [1927]. Elementary Number Theory. Vol. 125. Translated by Goodman, Jacob E. (2nd ed.). AMS Chelsea Publishing. Niven, Ivan; Zuckerman, Herbert S. (1960). An introduction to the theory of numbers. Wiley. Oh, Byeong-Kweon (2000). "Representations of Binary Forms by Quinary Quadratic Forms" (PDF). Trends in Mathematics. 3 (1): 102–107. Archived from the original (PDF) on 2017-02-02. Retrieved 2017-01-21. Rabin, M. O.; Shallit, J. O. (1986). "Randomized Algorithms in Number Theory". Communications on Pure and Applied Mathematics. 39 (S1): S239–S256. doi:10.1002/cpa.3160390713. Ramanujan, S. (1916). "On the expression of a number in the form ax2 + by2 + cz2 + du2". Mathematical Proceedings of the Cambridge Philosophical Society. 19: 11–21. Sarnak, Peter (2013). "The Ramanujan Conjecture and some Diophantine Equations". YouTube (Lecture at Tata Institute of Fundamental Research). ICTS Lecture Series. Bangalore, India. Stillwell, John (2003). Elements of Number Theory. Undergraduate Texts in Mathematics. Springer. doi:10.1007/978-0-387-21735-2. ISBN 978-0-387-95587-2. Zbl 1112.11002. Sun, Z.-W. (2017). "Refining Lagrange's four-square theorem". J. Number Theory. 175: 167–190. arXiv:1604.06723. doi:10.1016/j.jnt.2016.11.008. S2CID 119597024. Williams, Kenneth S. (2011). Number theory in the spirit of Liouville. London Mathematical Society Student Texts. Vol. 76. Cambridge University Press. ISBN 978-0-521-17562-3. Zbl 1227.11002. Spencer, Joel (1996). "Four Squares with Few Squares". Number Theory: New York Seminar 1991–1995. Springer US. pp. 295–297. doi:10.1007/978-1-4612-2418-1_22. ISBN 9780387948263. Pollack, P.; Treviño, E. (2018). "Finding the four squares in Lagrange's theorem" (PDF). Integers. 18A: A15.
External links Proof at PlanetMath.org Another proof An applet decomposing numbers as sums of four squares OEIS index to sequences related to sums of squares and sums of cubes Weisstein, Eric W. "Lagrange's Four-Square Theorem". MathWorld.