Lagrange's four-square theorem: Difference between revisions

Revision as of 22:29, 22 September 2023

Latest revision as of 22:51, 8 August 2025

(13 intermediate revisions by 10 users not shown)

Line 4:

[[File:distances_between_double_cube_corners.svg|thumb|Unlike in three dimensions in which distances between [[Vertex (geometry)|vertices]] of a [[polycube]] with unit edges excludes √7 due to [[Legendre's three-square theorem]], Lagrange's four-square theorem states that the analogue in four dimensions yields [[square root]]s of every [[natural number]] ]]

'''Lagrange's four-square theorem''', also known as '''[https://mathworld.wolfram.com/BachetsConjecture.html Bachet's conjecture]''', states that every [[natural number|nonnegative integer]] can be represented as a sum of four non-negative integer [[square number|squaresquares]]s.{{r|andrews}} That is, the squares form an [[additive basis]] of order four.:

<math display="block">p = a^2 + b^2 + c^2 + d^2,</math>

where the four numbers <math>a, b, c, d</math> are integers. For illustration, 3, 31, and 310 in several ways, can be represented as the sum of four squares as follows:

<math display="block">\begin{align}

3 & = 1^2+1^2+1^2+0^2 \\[3pt]

Line 16:

\end{align}</math>

This theorem was proven by [[Joseph -Louis Lagrange]] in 1770. It is a special case of the [[Fermat polygonal number theorem]].

==Historical development==

Line 118:

<math display="block">n=ax_1^2+bx_2^2+cx_3^2+dx_4^2</math>

for all positive integers {{mvar|n}} in integers <math>x_1,x_2,x_3,x_4</math>? The case <math>a=b=c=d=1</math> is answered in the positive by Lagrange's four-square theorem. The general solution was given by [[Ramanujan]].<ref>{{harvnb|Ramanujan|19171916}}.</ref> He proved that if we assume, without loss of generality, that <math>a\leq b\leq c\leq d</math> then there are exactly 54 possible choices for <math>a,b,c,d</math> such that the problem is solvable in integers <math>x_1,x_2,x_3,x_4</math> for all {{mvar|n}}. (Ramanujan listed a 55th possibility <math>a=1,b=2,c=5,d=5</math>, but in this case the problem is not solvable if <math>n=15</math>.<ref>{{harvnb|Oh|2000}}.</ref>)

==Algorithms==

In 1986, [[Michael O. Rabin]] and [[Jeffrey Shallit]]<ref>{{harvnb|Rabin|Shallit|1986}}.</ref> proposed [[randomized algorithm|randomized]] [[polynomial-time algorithm]]s for computing a single representation <math>n=x_1^2+x_2^2+x_3^2+x_4^2</math> for a given integer {{mvar|n}}, in expected running time <math>\mathrm{O}(\log^2(n)^2)</math>. It was further improved to <math>\mathrm{O}(\log^2(n)^2 \log(\log(n))^{-1})</math> by Paul Pollack and Enrique Treviño in 2018.<ref>{{harvnb|Pollack|Treviño|2018}}.</ref>

==Number of representations==

Line 143:

==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 ... {{OEIS|A006431}}.

Line 156:

==Further refinements==

Lagrange's four-square theorem can be refined in various ways. For example, [[Zhi-Wei Sun]]<ref>{{harvnb|Z.-W. Sun|2017}}.</ref> 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 {{mvar|S}} with <math>|S| = O(n^{1/4}\log^{1/4} n)</math> such that every positive integer smaller than or equal to {{mvar|n}} can be written as a sum of at most 4 elements of {{mvar|S}}.<ref>{{harvnb|Spencer |1996.}}</ref>

==See also==

Line 243:

| first = Byeong-Kweon

| title = Representations of Binary Forms by Quinary Quadratic Forms

| journal = Trends in Mathematics

| year = 2000

| volume = 3

Line 249:

| pages = 102–107

| url = http://trends.mathnet.or.kr/mathnet/kms_tex/974363.pdf

| archive-date = 2017-02-02

| access-date = 2017-01-21

| archive-url = https://web.archive.org/web/20170202074451/http://trends.mathnet.or.kr/mathnet/kms_tex/974363.pdf

| url-status = dead

}}

*{{Cite journal

Line 266 ⟶ 270:

}}

*{{Cite journal

| lastlast1=Ramanujan | first1=S. | authorlink1=Srinivasa Ramanujan

| title = On the expression of a number in the form ''ax''² + ''by''² + ''cz''² + dw''du''²

| first = S.

| journal=[[Mathematical Proceedings of the Cambridge Philosophical Society]]

| author-link = Srinivasa Ramanujan

| year = 19171916

| title = On the expression of a number in the form ax² + by² + cz² + dw²

| volume=19

| journal = Proc. Camb. Phil. Soc.

| volume pages= 1911–21

| url=https://archive.org/details/proceedingsofcam1920191721camb/page/n23/mode/2up}}

| year = 1917

| pages = 11–21

}}

*{{Cite web

| last = Sarnak

Line 340 ⟶ 342:

*[http://planetmath.org/proofoflagrangesfoursquaretheorem Proof at PlanetMath.org]

*[http://www.alpertron.com.ar/4SQUARES.HTM Another proof]

*[http://www.alpertron.com.ar/FSQUARES.HTM anAn applet decomposing numbers as sums of four squares]

*[https://oeis.org/wiki/Index_to_OEIS:_Section_Su#ssq OEIS index to sequences related to sums of squares and sums of cubes]

*{{mathworld|urlname=LagrangesFour-SquareTheorem|title=Lagrange's Four-Square Theorem}}

{{Joseph-Louis Lagrange}}