Lagrange's four-square theorem

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

Unlike in three dimensions in which distances between 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 roots of every natural number

Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as a sum of four non-negative integer squares. That is, the squares form an additive basis of order four.

$${\displaystyle p=a^2+b^2+c^2+d^2}$$

where the four numbers ${\displaystyle a,b,c,d}$ are integers. For illustration, 3, 31, and 310 in several ways, can be represented as the sum of four squares as follows:

$${\displaystyle \begin{array}{rl}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.\end{array}}$$

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 ${\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.

The classical proof

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).

The residues of a² modulo p are distinct for every a between 0 and (p − 1)/2 (inclusive). To see this, take some a and define c as a² mod p. a is a root of the polynomial x² − c over the field Z/pZ. So is p − a (which is different from a). In a field K, any polynomial of degree n has at most n distinct roots (Lagrange's theorem (number theory)), so there are no other a with this property, in particular not among 0 to (p − 1)/2.

Similarly, for b taking integral values between 0 and (p − 1)/2 (inclusive), the −b² − 1 are distinct. By the pigeonhole principle, there are a and b in this range, for which a² and −b² − 1 are congruent modulo p, that is for which

$${\displaystyle a^2+b^2+1^2+0^2=np.}$$

Now let m be the smallest positive integer such that mp is the sum of four squares, x₁² + x₂² + x₃² + x₄² (we have just shown that there is some m (namely n) with this property, so there is a least one m, and it is smaller than p). 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 rp 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 x_i the y_i which is in the same residue class modulo m and between (–m + 1)/2 and m/2 (possibly included). It follows that y₁² + y₂² + y₃² + y₄² = mr, for some strictly positive integer r less than m.

Finally, another appeal to Euler's four-square identity shows that mpmr = z₁² + z₂² + z₃² + z₄². But the fact that each x_i is congruent to its corresponding y_i implies that all of the z_i are divisible by m. Indeed,

$${\displaystyle \{\begin{array}{lllll}{z}_1& =x_1{y}_1+x_2{y}_2+x_3{y}_3+x_4{y}_4& \equiv x_1^2+x_2^2+x_3^2+x_4^2& =mp\equiv 0& (\mathrm{mod}m),\\ z_2& =x_1{y}_2-x_2{y}_1+x_3{y}_4-x_4{y}_3& \equiv x_1{x}_2-x_2{x}_1+x_3{x}_4-x_4{x}_3& =0& (\mathrm{mod}m),\\ z_3& =x_1{y}_3-x_2{y}_4-x_3{y}_1+x_4{y}_2& \equiv x_1{x}_3-x_2{x}_4-x_3{x}_1+x_4{x}_2& =0& (\mathrm{mod}m),\\ z_4& =x_1{y}_4+x_2{y}_3-x_3{y}_2-x_4{y}_1& \equiv x_1{x}_4+x_2{x}_3-x_3{x}_2-x_4{x}_1& =0& (\mathrm{mod}m).\end{array}}$$

It follows that, for w_i = z_i/m, w₁² + w₂² + w₃² + w₄² = rp, and this is in contradiction with the minimality of m.

In the descent above, we must rule out both the case y₁ = y₂ = y₃ = y₄ = m/2 (which would give r = m and no descent), and also the case y₁ = y₂ = y₃ = y₄ = 0 (which would give r = 0 rather than strictly positive). For both of those cases, one can check that mp = x₁² + x₂² + x₃² + x₄² would be a multiple of m², contradicting the fact that p is a prime greater than m.

Proof using the Hurwitz integers

Another way to prove the theorem relies on Hurwitz quaternions, which are the analog of integers for quaternions.

Proof using the Hurwitz integers

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

$${\displaystyle \alpha =\frac{1}{2}{E}_0(1+\mathbf{i}+\mathbf{j}+\mathbf{k})+E_1\mathbf{i}+E_2\mathbf{j}+E_3\mathbf{k}=a_0+a_1\mathbf{i}+a_2\mathbf{j}+a_3\mathbf{k}}$$

where ${\displaystyle E_0,E_1,E_2,E_3}$ are integers. Thus, the quaternion components ${\displaystyle a_0,a_1,a_2,a_3}$ are either all integers or all half-integers, depending on whether ${\displaystyle E_0}$ 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.

The (arithmetic, or field) norm ${\displaystyle \mathrm{N}(\alpha )}$ of a rational quaternion ${\displaystyle \alpha }$ is the nonnegative rational number

$${\displaystyle \mathrm{N}(\alpha )=\alpha \overline{\alpha }=a_0^2+a_1^2+a_2^2+a_3^2}$$

where ${\displaystyle \overline{\alpha }=a_0-a_1\mathbf{i}-a_2\mathbf{j}-a_3\mathbf{k}}$ is the conjugate of ${\displaystyle \alpha }$. Note that the norm of a Hurwitz quaternion is always an integer. (If the coefficients are half-integers, then their squares are of the form ${\displaystyle \frac{1}{4}+n:n\in \mathbb{Z}}$, 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:

$${\displaystyle \mathrm{N}(\alpha \beta )=\alpha \beta (\overline{\alpha \beta })=\alpha \beta \overline{\beta }\overline{\alpha }=\alpha \mathrm{N}(\beta )\overline{\alpha }=\alpha \overline{\alpha }\mathrm{N}(\beta )=\mathrm{N}(\alpha )\mathrm{N}(\beta ).}$$

For any ${\displaystyle \alpha \ne 0}$, ${\displaystyle {\alpha }^{-1}=\overline{\alpha }\mathrm{N}(\alpha {)}^{-1}}$. It follows easily that ${\displaystyle \alpha }$ is a unit in the ring of Hurwitz quaternions if and only if ${\displaystyle \mathrm{N}(\alpha )=1}$.

The proof of the main theorem begins by reduction to the case of prime numbers. Euler's four-square identity implies that if Lagrange'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 ${\displaystyle 2=1^2+1^2+0^2+0^2}$. To show this for an odd prime integer p, represent it as a quaternion ${\displaystyle (p,0,0,0)}$ 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

$${\displaystyle p=\alpha \beta .}$$

The norms of ${\displaystyle p,\alpha ,\beta }$ are integers such that

$${\displaystyle \mathrm{N}(p)=p^2=\mathrm{N}(\alpha \beta )=\mathrm{N}(\alpha )\mathrm{N}(\beta )}$$

and ${\displaystyle \mathrm{N}(\alpha ),\mathrm{N}(\beta )>1}$. This shows that both ${\displaystyle \mathrm{N}(\alpha )}$ and ${\displaystyle \mathrm{N}(\beta )}$ are equal to p (since they are integers), and p is the sum of four squares

$${\displaystyle p=\mathrm{N}(\alpha )=a_0^2+a_1^2+a_2^2+a_3^2.}$$

If it happens that the ${\displaystyle \alpha }$ chosen has half-integer coefficients, it can be replaced by another Hurwitz quaternion. Choose ${\displaystyle \omega =(\pm 1\pm \mathbf{i}\pm \mathbf{j}\pm \mathbf{k})/2}$ in such a way that ${\displaystyle \gamma \equiv \omega +\alpha }$ has even integer coefficients. Then

$${\displaystyle p=(\overline{\gamma }-\overline{\omega })\omega \overline{\omega }(\gamma -\omega )=(\overline{\gamma }\omega -1)(\overline{\omega }\gamma -1).}$$

Since ${\displaystyle \gamma }$ has even integer coefficients, ${\displaystyle (\overline{\omega }\gamma -1)}$ will have integer coefficients and can be used instead of the original ${\displaystyle \alpha }$ to give a representation of p as the sum of four squares.

As for showing that p is not a Hurwitz irreducible, Lagrange proved that any odd prime p divides at least one number of the form ${\displaystyle u=1+l^2+m^2}$, where l and m are integers. This can be seen as follows: since p is prime, ${\displaystyle a^2\equiv b^2(\mathrm{mod}p)}$ can hold for integers ${\displaystyle a,b}$, only when ${\displaystyle a\equiv \pm b(\mathrm{mod}p)}$. Thus, the set ${\displaystyle X=\{0^2,1^2,\dots ,((p-1)/2{)}^2\}}$ of squares contains ${\displaystyle (p+1)/2}$ distinct residues modulo p. Likewise, ${\displaystyle Y=\{-(1+x):x\in X\}}$ contains ${\displaystyle (p+1)/2}$ residues. Since there are only p residues in total, and ${\displaystyle |X|+|Y|=p+1>p}$, the sets X and Y must intersect.

The number u can be factored in Hurwitz quaternions:

$${\displaystyle 1+l^2+m^2=(1+l\mathbf{i}+m\mathbf{j})(1-l\mathbf{i}-m\mathbf{j}).}$$

The norm on Hurwitz quaternions satisfies a form of the Euclidean property: for any quaternion ${\displaystyle \alpha =a_0+a_1\mathbf{i}+a_2\mathbf{j}+a_3\mathbf{k}}$ with rational coefficients we can choose a Hurwitz quaternion ${\displaystyle \beta =b_0+b_1\mathbf{i}+b_2\mathbf{j}+b_3\mathbf{k}}$ so that ${\displaystyle \mathrm{N}(\alpha -\beta )<1}$ by first choosing ${\displaystyle b_0}$ so that ${\displaystyle |a_0-b_0|\le 1/4}$ and then ${\displaystyle b_1,b_2,b_3}$ so that ${\displaystyle |a_i-b_i|\le 1/2}$ for ${\displaystyle i=1,2,3}$. Then we obtain

$${\displaystyle \begin{array}{rl}\mathrm{N}(\alpha -\beta )& =(a_0-b_0{)}^2+(a_1-b_1{)}^2+(a_2-b_2{)}^2+(a_3-b_3{)}^2\\ & \le {\left(\frac{1}{4}\right)}^2+{\left(\frac{1}{2}\right)}^2+{\left(\frac{1}{2}\right)}^2+{\left(\frac{1}{2}\right)}^2=\frac{13}{16}<1.\end{array}}$$

It follows that for any Hurwitz quaternions ${\displaystyle \alpha ,\beta }$ with ${\displaystyle \alpha \ne 0}$, there exists a Hurwitz quaternion ${\displaystyle \gamma }$ such that

$${\displaystyle \mathrm{N}(\beta -\alpha \gamma )<\mathrm{N}(\alpha ).}$$

The ring H 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 ${\displaystyle \alpha }$ such that

$${\displaystyle \alpha H=pH+(1-l\mathbf{i}-m\mathbf{j})H.}$$

In particular, ${\displaystyle p=\alpha \beta }$ for some Hurwitz quaternion ${\displaystyle \beta }$. If ${\displaystyle \beta }$ were a unit, ${\displaystyle 1-l\mathbf{i}-m\mathbf{j}}$ would be a multiple of p, however this is impossible as ${\displaystyle 1/p-l/p\mathbf{i}-m/p\mathbf{j}}$ is not a Hurwitz quaternion for ${\displaystyle p>2}$. Similarly, if ${\displaystyle \alpha }$ were a unit, we would have

$${\displaystyle (1+l\mathbf{i}+m\mathbf{j})H=(1+l\mathbf{i}+m\mathbf{j})pH+(1+l\mathbf{i}+m\mathbf{j})(1-l\mathbf{i}-m\mathbf{j})H\subseteq pH}$$

so p divides ${\displaystyle 1+l\mathbf{i}+m\mathbf{j}}$, which again contradicts the fact that ${\displaystyle 1/p-l/p\mathbf{i}-m/p\mathbf{j}}$ is not a Hurwitz quaternion. Thus, p is not Hurwitz irreducible, as claimed.

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 ${\displaystyle a,b,c,d}$, can we solve

$${\displaystyle n=a{x}_1^2+b{x}_2^2+c{x}_3^2+d{x}_4^2}$$

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

Algorithms

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

Number of representations

Main article: Jacobi's four-square theorem

The number of representations of a natural number n as the sum of four squares of integers 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.

$${\displaystyle r_4(n)=\{\begin{array}{ll}8\sum _{m\mid n}m& \text{if }n\text{ is odd}\\ 24\sum _{\begin{array}{c}m|n\\ m\text{ odd}\end{array}}m& \text{if }n\text{ is even}.\end{array}}$$

Equivalently, it is eight times the sum of all its divisors which are not divisible by 4, i.e.

$${\displaystyle r_4(n)=8\sum _{m:4\nmid m\mid n}m.}$$

We may also write this as

$${\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 r₄(p) = 8(p + 1).

Some values of r₄(n) occur infinitely often as r₄(n) = r₄(2^mn) whenever n is even. The values of r₄(n)/n can be arbitrarily large: indeed, r₄(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 ${\displaystyle 2(4^k),6(4^k)}$ or ${\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 ${\displaystyle 2(4^k),6(4^k)}$ or ${\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 ${\displaystyle |S|=O(n^{1/4}{\log }^{1/4}n)}$ such that every positive integer smaller than or equal n can be written as a sum of at most 4 elements of S.