Lagrange’s four square theorem

Posted by: Steven Sam | February 10, 2009

Lagrange’s four square theorem

I wanted to present a proof of Lagrange’s four square theorem that I had seen a few years ago that I really like. I think there’s also some approaches using analytic number theory and algebraic number theory, but this one uses convex geometry (!) First, let me state the theorem (my convention here is that $\mathbf{N}$ denotes the nonnegative integers):

Theorem (Lagrange). Every nonnegative integer can be written as a sum of four squares, i.e., the function $\mathbf{N}^4 \to \mathbf{N}$ given by $(x,y,z,w) \mapsto x^2 + y^2 + z^2 + w^2$ is surjective.

In order to make this (reasonably) self-contained, let’s give some definitions we’ll use.

A lattice $\Lambda$ is a discrete subgroup of $\mathbf{R}^d$ which spans $\mathbf{R}^d$ in the sense of vector spaces. Basically, a lattice will be some subgroup of $\mathbf{R}^d$ which is isomorphic to $\mathbf{Z}^d$ . If $\{v_1, \dots, v_d\}$ is a basis for $\Lambda$ , define $\det \Lambda := \det (v_1 \cdots v_d)$ to be the determinant of $\Lambda$ . Define the fundamental parallelepiped of $\Lambda$ to be the set $\{ a_1v_1 + \cdots + a_dv_d \mid 0 \le a_i < 1 \}$ .

Now we just need some convex geometry. The main tool will be Minkowski’s theorem. The proof is short, so I’ll include it.

Lemma (Blichfeldt). Let $\Lambda \subset \mathbf{R}^d$ be a lattice and $X \subseteq \mathbf{R}^d$ be a measurable set. If $\text{vol} X > \det \Lambda$ , then there exist distinct $x,y \in X$ such that $x-y \in \Lambda$ .

Proof. Let $\Pi$ be the fundamental parallelepiped of $\Lambda$ . Then $\mathbf{R}^d = \coprod_{u \in \Lambda} \Pi + u$ (disjoint union), and hence $X = \coprod_{u \in \Lambda} X \cap (\Pi + u)$ . Define $X_u := (X - u) \cap \Pi$ . Then

$\displaystyle \text{vol} X = \sum_{u \in \Lambda} \text{vol} (X_u + u) = \sum_{u \in \Lambda} \text{vol} X_u > \det \Lambda = \text{vol} \Pi$ .

Since each $X_u \subseteq \Pi$ , there must exist distinct $u, u' \in \Lambda$ such that $X_u \cap X_{u'} \ne \emptyset$ . Take $v \in X_u \cap X_{u'}$ and set $x = v+u$ and $y=v+u'$ . $\blacksquare$

Lemma (Minkowski). Let $\Lambda \subset \mathbf{R}^d$ be a lattice and $K \subseteq \mathbf{R}^d$ be a centrally symmetric (i.e., $x \in K$ implies $-x \in K$ ) convex set such that $\text{vol} K > 2^d \det \Lambda$ . Then $K$ contains a nonzero element of $\Lambda$ .

Proof. Set $K' := \frac{1}{2}K$ , so $\text{vol} K' = \frac{1}{2^d} \text{vol} K > \det \Lambda$ . Then there exist distinct $x,y \in K'$ such that $x-y \in \Lambda$ . Since $-y \in K'$ , we have $x-y \in 2K' = K$ . $\blacksquare$

Now we can write down a proof of Lagrange’s four square theorem.

Proof. Pick $n \in \mathbf{N}$ . We break the proof up into three steps.

Step 1: Reduce to the case that $n$ is prime. The sum of four squares $a^2+b^2+c^2+d^2$ is the square of the norm of a quaternion $a+bi+cj+dk$ . Since norm is multiplicative, the product of two sums of four squares is itself a sum of four squares. This can be checked directly, but it’s not really that interesting.

Step 2: Find $\alpha, \beta \in \mathbf{Z}$ such that $\alpha^2 + \beta^2 + 1 \equiv 0 \pmod n$ . If $n=2$ , take $\alpha = 1$ , $\beta = 0$ . Otherwise, assume $n$ is odd. Define
$S := \{ \alpha^2 \pmod n \mid 0 \le \alpha < \frac{n}{2} \}$ . Choose $0 \le \alpha, \alpha' < \frac{n}{2}$ with $\alpha^2 \equiv \alpha'^2 \pmod n$ . Then $(\alpha + \alpha')(\alpha - \alpha') \equiv 0 \pmod n$ , and $\alpha + \alpha' \not\equiv 0 \pmod n$ since $\alpha + \alpha' < n$ , which implies that $\alpha - \alpha' \equiv 0 \pmod n$ , and hence $\alpha = \alpha'$ . So $S$ has $\frac{n+1}{2}$ elements.

Similarly, define $S' := \{ -1 -\beta^2 \pmod n \mid 0 \le \beta < \frac{n}{2} \}$ . Pick $0 \le \beta, \beta' < \frac{n}{2}$ such that $\beta^2 \equiv \beta'^2$ . Then as before, $\beta = \beta'$ , so $S'$ also has $\frac{n+1}{2}$ elements. Hence $S \cap S'$ cannot be empty by the pigeonhole principle, so we can find $\alpha$ and $\beta$ such that $\alpha^2 \equiv -1 - \beta^2 \pmod n$ .

Step 3: Construct a suitable lattice and centrally symmetric convex body $K$ such that a lattice point in $K$ will correspond to an expression of $n$ as a sum of four squares. Define $\Lambda := \{ a \in \mathbf{Z}^4 \mid a_1 \equiv \alpha a_3 + \beta a_4 \pmod n,\quad a_2 \equiv \beta a_3 - \alpha a_4 \pmod n \}$ . Being a subgroup of $\mathbf{Z}^4$ , it is clear that $\Lambda$ is discrete. Also, the set $\{0,\dots,n-1\}^2 \times \{(0,0)\}$ surjects onto $\mathbf{Z}^4 / \Lambda$ under the projection, so $\Lambda$ has finite index in $\mathbf{Z}^4$ , and hence has full rank and $\det \Lambda = \#(\mathbf{Z}^4 / \Lambda) \le n^2$ . Define $B := \{a \in \mathbf{R}^4 \mid \|a\| < \sqrt{2n}\}$ . Since

$\displaystyle \text{vol} B = \frac{\pi^2}{2}(\sqrt{2n})^4 = 2\pi^2n^2 > 16n^2 \ge 2^4 \det \Lambda$ ,

we can apply Minkowski’s theorem to find $a \in \Lambda$ such that $0 < \|a\|^2 < 2n$ . Now $\|a\|^2 = a_1^2 + a_2^2 + a_3^2 + a_4^2$ implies $\|a\|^2 \equiv (\alpha a_3 + \beta a_4)^2 + (\beta a_3 - \alpha a_4)^2 + a_3^2 + a_4^2 \equiv 0 \pmod n$ , and hence $a_1^2 + a_2^2 + a_3^2 + a_4^2$ is a multiple of $n$ . From $0 < \|a\|^2 < 2n$ , this multiple must be 1. $\blacksquare$

And there you have it!

-Steven

About these ads

Posted in Algebra | Tags: convex geometry, number theory

Responses

Minkowski’s theorem is surprisingly useful for even elementary number theory…

Do you know any other proof of the four-square theorem? The Minkowski theory proof is the only one I know, but there has to be one that uses machinery available in Lagrange’s time.
By: Alon Levy on February 16, 2009
at 1:30 AM
Sorry for the late response. I found this proof on the wikipedia article on Lagrange’s four square theorem:

http://www.alpertron.com.ar/4SQUARES.HTM

Apparently it is algorithmic.
By: Steven Sam on February 24, 2009
at 7:35 AM
Hardy & Wright (Introduction to the theory of numbers) give several proofs, but one uses the quaternionic integers throughout, in a manner analogous to the proof of Fermat’s two square theorem using Gaussian integers. This is apparently due to Hurwitz, so quaternionic integers are sometimes called Hurwitz integers.
They also give a proof using elliptic functions that gives the number of representations.
By: Robert on March 2, 2009
at 2:54 AM
The product of two sums of four squares isn’t necessarily a sum of four squares.
It is when for example, w^2+x^2+y^2+z^2=e^2
(a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2)=
(a^2+b^2+c^2+d^2)e^2.
By: Allan on June 4, 2009
at 6:13 AM
Allan:

The product of two sums of four squares _is_ necessarily a sum of four squares. It’s a bit messy, but you can see it here:
Euler’s four-square identity
By: Steven Sam on June 4, 2009
at 6:30 AM
Thanks, didn’t know this before.
By: Allan on June 17, 2009
at 3:41 PM

Concrete Nonsense