HOME

TheInfoList



Click Here for Items Related To - Lagrange's four-square theorem
OR:
Lagrange's four-square theorem on:   [Wikipedia]   [Google]   [Amazon]

Lagrange's four-square theorem, also known as Bachet's conjecture, states that every
nonnegative integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
can be represented as a sum of four non-negative integer
squares In geometry, a square is a regular polygon, regular quadrilateral. It has four straight sides of equal length and four equal angles. Squares are special cases of rectangles, which have four equal angles, and of rhombuses, which have four equal si ...
. That is, the squares form an additive basis of order four: p = a^2 + b^2 + c^2 + d^2, where the four numbers a, b, c, d are integers. For illustration, 3, 31, and 310 can be represented as the sum of four squares as follows: \begin 3 & = 1^2+1^2+1^2+0^2 \\ pt31 & = 5^2+2^2+1^2+1^2 \\ pt310 & = 17^2+4^2+2^2+1^2 \\ pt& = 16^2 + 7^2 + 2^2 +1^2 \\ pt& = 15^2 + 9^2 + 2^2 +0^2 \\ pt& = 12^2 + 11^2 + 6^2 + 3^2. \end This theorem was proven by
Joseph Louis Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi LagrangiaFermat polygonal number theorem.


Historical development

From examples given in the ''
Arithmetica Diophantus of Alexandria () (; ) was a Greek mathematics, Greek mathematician who was the author of the ''Arithmetica'' in thirteen books, ten of which are still extant, made up of arithmetical problems that are solved through algebraic equations ...
,'' it is clear that
Diophantus Diophantus of Alexandria () (; ) was a Greek mathematician who was the author of the '' Arithmetica'' in thirteen books, ten of which are still extant, made up of arithmetical problems that are solved through algebraic equations. Although Jose ...
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 Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French people, French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transforma ...
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(8m+7) 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
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s for
quaternion In mathematics, the quaternion number system extends the complex numbers. Quaternions were first described by the Irish mathematician William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space. The algebra of quater ...
s..


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 number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s a,b,c,d, can we solve n=ax_1^2+bx_2^2+cx_3^2+dx_4^2 for all positive integers in integers x_1,x_2,x_3,x_4? The case 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\leq b\leq c\leq d then there are exactly 54 possible choices for a,b,c,d such that the problem is solvable in integers x_1,x_2,x_3,x_4 for all . (Ramanujan listed a 55th possibility a=1,b=2,c=5,d=5, but in this case the problem is not solvable if n=15.)


Algorithms

In 1986, Michael O. Rabin and
Jeffrey Shallit Jeffrey Outlaw Shallit (born October 17, 1957) is an American computer scientist and mathematician. He is an active number theorist and a noted critic of intelligent design. He is married to Anna Lubiw, also a computer scientist. Early life ...
proposed randomized polynomial-time algorithms for computing a single representation n=x_1^2+x_2^2+x_3^2+x_4^2 for a given integer , in expected running time \mathrm(\log(n)^2). It was further improved to \mathrm(\log(n)^2 \log(\log(n))^) 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 ''r''4(''n''). Jacobi's four-square theorem states that this is eight times the sum of the
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...
s of ''n'' if ''n'' is odd and 24 times the sum of the odd divisors of ''n'' if ''n'' is even (see
divisor function In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as ''the'' divisor function, it counts the ''number of divisors of an integer'' (includi ...
), i.e. r_4(n)=\begin8\sum\limits_m&\textn\text\\ 2pt24\sum\limits_m&\textn\text. \end Equivalently, it is eight times the sum of all its divisors which are not divisible by 4, i.e. r_4(n)=8\sum_m. We may also write this as 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 A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
''p'' we have the explicit formula .. Some values of ''r''4(''n'') occur infinitely often as whenever ''n'' is even. The values of ''r''4(''n'')/''n'' can be arbitrarily large: indeed, ''r''4(''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 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 ... . 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) or 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 ... . 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) or 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 with , S, = O(n^\log^ n) such that every positive integer smaller than or equal to can be written as a sum of at most 4 elements of .


See also

*
Fermat's theorem on sums of two squares In additive number theory, Pierre de Fermat, Fermat's theorem on sums of two squares states that an Even and odd numbers, odd prime number, prime ''p'' can be expressed as: :p = x^2 + y^2, with ''x'' and ''y'' integers, if and only if :p \equiv ...
* Fermat's polygonal number theorem * Waring's problem * Legendre's three-square theorem *
Sum of two squares theorem In number theory, the sum of two squares theorem relates the prime decomposition of any integer to whether it can be written as a sum of two Square number, squares, such that for some integers , . An integer greater than one can be written as a ...
* Sum of squares function * 15 and 290 theorems


Notes


References

* * * * * * * * * * * * *


External links


Proof at PlanetMath.orgAnother proofAn applet decomposing numbers as sums of four squaresOEIS index to sequences related to sums of squares and sums of cubes
* {{DEFAULTSORT:Lagrange's Four-Square Theorem Additive number theory Articles containing proofs Squares in number theory Theorems in number theory