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

Responses

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

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

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

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

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

  6. Thanks, didn’t know this before.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 69 other followers

%d bloggers like this: