Lagrange's four-square theorem

For Lagrange's identity, see Lagrange's identity (disambiguation).

"four-square theorem" and "four square theorem" redirect here. For other uses, see four square (disambiguation).

Lagrange's four-square theorem, also known as Bachet's conjecture, states that any natural number can be represented as the sum of four integer squares

$p = a_0^2 %2B a_1^2 %2B a_2^2 %2B a_3^2\$

where the four numbers $a 0, a 1, a 2, a 3$ 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

This theorem was proven by Joseph Louis Lagrange in 1770, and corresponds to Fermat's theorem on sums of two squares.

1 Historical development
2 Proof using the Hurwitz integers
3 Generalizations
4 Algorithms
5 Uniqueness
6 See also
7 Notes
8 References
9 External links

Historical development

The theorem appears in the Arithmetica of Diophantus, translated into Latin by Bachet in 1621.

Adrien-Marie Legendre improved on the theorem in 1798 by stating 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)$ . His proof was incomplete, leaving a gap which was later filled by Carl Friedrich Gauss.

Proof using the Hurwitz integers

One of the ways to prove the theorem relies on Hurwitz quaternions, which are the analog of integers for quaternions.^[1] 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

$\alpha = \frac{1}{2} E_0 (1 %2B \mathbf{i} %2B \mathbf{j} %2B \mathbf{k}) %2BE_1\mathbf{i} %2BE_2\mathbf{j} %2BE_3\mathbf{k} = a_0 %2Ba_1\mathbf{i} %2Ba_2\mathbf{j} %2Ba_3\mathbf{k}$

where $E 0, E 1, E 2, E 3$ are integers. Thus, the quaternion components $a 0, a 1, a 2, a 3$ are either all integers or all half-integers, depending on whether $E 0$ is even or odd, respectively. The set of Hurwitz quaternions forms a ring; in particular, the sum or product of any two Hurwitz quaternions is likewise a Hurwitz quaternion.

The generalized Euclidean algorithm identifies the greatest common right or left divisor of two Hurwitz quaternions, where the "size" of the remainder $ρ$ is measured by the norm. The norm $N(α)$ of a quaternion $α$ is the nonnegative real number

$\mathrm{N}(\alpha) = \alpha\bar\alpha = a_0^2%2Ba_1^2%2Ba_2^2%2Ba_3^2$ ,

where $\bar\alpha=a_0 -a_1\mathbf{i} -a_2\mathbf{j} -a_3\mathbf{k}$ is the conjugate of $α$ .

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:

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

Since any natural number can be factored into powers of primes, the four-square theorem holds for all natural numbers if it is true for all prime numbers. It is true for $2 = 0 2 + 0 2 + 1 2 + 1 2$ . To show this for an odd prime integer $p$ , represent it as a quaternion $(p, 0, 0, 0)$ and assume that it can be factored into two Hurwitz quaternions

p = αβ

The norms of $p, α, β$ are nonnegative integers such that

N(p) = p 2 = N(αβ) = N(α)N(β)

But the norm has only two factors, both $p$ . Therefore, if it can be factored into Hurwitz quaternions, then $p$ is the sum of four squares

p = N(α) = a 02 + a 12 + a 22 + a 32

Lagrange proved that any odd prime $p$ divides at least one number of the form $1 + l 2 + m 2$ , where $l$ and $m$ are integers.^[1] The latter number can be factored in Hurwitz quaternions:

1 + l 2 + m 2 = (1 + l i + m j) (1 - l i - m j)

If $p$ could not be factored in Hurwitz quaternions, it would be a Hurwitz prime number by definition. Then, by unique factorization, $p$ would have to divide either $1 + l i + m j$ or to form another Hurwitz quaternion. But for $p >2$ , the number

1/ p \pm l / p i \pm m / p j

is not a Hurwitz integer. Therefore, every $p >2$ can be factored in Hurwitz quaternions, and the four-square theorem holds.

Generalizations

Lagrange's four-square theorem is a special case of the Fermat polygonal number theorem and Waring's problem. Another possible generalisation is the following problem: Given natural numbers $a, b, c, d$ , can we solve

n = ax 12 + bx 22 + cx 32 + dx 42

for all positive integers $n$ 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 $n$ . (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$ . ^[2])

Algorithms

Michael O. Rabin and Jeffrey Shallit^[3] have found randomized polynomial-time algorithms for computing a representation $n = x 12 + x 22 + x 32 + x 42$ for a given integer $n$ , in expected running time $O((log n) 2)$ .

Uniqueness

The sequence of positive integers whose representation as a sum of four squares is unique (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 OEIS).

These integers consist of the seven odd numbers 1, 3, 5, 7, 11, 15, 23 and all numbers of the form $2 \times 4 k, 6 \times 4 k$ or $14 \times 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 OEIS).

These integers consist of the eight odd numbers 1, 3, 5, 9, 11, 17, 29, 41 and all numbers of the form $2 \times 4 n, 6 \times 4 n$ or $14 \times 4 n$ .

Notes

^ ^a ^b Stillwell J (2003). Elements of Number Theory. New York: Springer-Verlag. pp. 138–157. ISBN 0-387-95587-9.
^ Myung-Hwan Kim REPRESENTATIONS OF BINARY FORMS BY QUINARY QUADRATIC FORMS
^ M. O. Rabin, J. O. Shallit, Randomized Algorithms in Number Theory, Communications on Pure and Applied Mathematics 39 (1986), no. S1, pp. S239–S256. doi:10.1002/cpa.3160390713

References

Ireland and Rosen (1990). A Classical Introduction to Modern Number Theory. Springer-Verlag. ISBN 0-387-97329-X.