Lagrange's Four Square Theorem/Proof 2

== Theorem ==
== Proof ==
=== Proof for Odd Primes ===
Suppose $p$ is an odd prime. 
Define:
:$S := \set {\alpha^2 \pmod p: \alpha \in \hointr 0 {\dfrac p 2} \cap \Z}$
Define: 
:$S' := \set {-1 - \beta^2 \pmod p: \beta \in \hointr 0 {\dfrac p 2} \cap \Z}$
Suppose for $\alpha, \alpha' \in S$: 
:$\alpha^2 \equiv \alpha'^2 \pmod p$ 
Obviously:
:$\paren {\alpha + \alpha'} \paren {\alpha - \alpha'} = \alpha^2 - \alpha'^2 \equiv 0 \pmod p$
Since $0 \le \alpha$, $\alpha' < \dfrac p 2$: 
:$\alpha + \alpha' \not \equiv 0 \pmod p$
Therefore $\alpha - \alpha' \equiv 0 \pmod p$.
This shows that $\alpha = \alpha'$.
Thus we have $\size S = \size {\hointr 0 {\dfrac p 2} \cap \Z} = 1 + \dfrac {p - 1} 2 = \dfrac {p + 1} 2$.
Choose $\beta, \beta' \in S'$:
:$-1 - \beta^2 \equiv -1 - \beta'^2 \pmod p$
By simple algebraic manipulation:
:$-1 - \beta^2 \equiv -1 - \beta'^2 \pmod p \iff \beta^2 \equiv \beta'^2 \pmod p$
Then by the same reasoning as above:
:$\card {S'} = \card S = \dfrac {p + 1} 2$
By the Pigeonhole Principle:
:$S \cap S' \ne \O$
Thus $\exists \alpha, \beta \in \Z$:
:$(1): \quad \alpha^2 + \beta^2 + 1 \equiv 0 \pmod p$
Define:
:$L = \set {\vec x = \tuple {x_1, x_2, x_3, x_4} \in \Z^4: x_1 \equiv \alpha x_3 + \beta x_4 \pmod p, x_2 \equiv \beta x_3 - \alpha x_4 \pmod p}$
If $\vec x$, $\vec y \in L$ and $\vec z = \tuple {z_1, z_2, z_3, z_4}$, then:
So $L$ is closed under vector addition.
So $L$ has additive inverses.
By Two-Step Subgroup Test, $\struct {L, +}$ is a subgroup of $\struct {\R^4, +}$.
For each $\vec x = \tuple {x_1, x_2, x_3, x_4} \in L$, one can write:
:$\vec x = x_3 \tuple {\alpha, \beta, 1, 0} + x_4 \tuple {\beta, -\alpha, 0, 1} + \floor {\dfrac {x_1} p} \tuple {p, 0, 0, 0} + \floor {\dfrac{x_2} p} \tuple {0, p, 0, 0}$
Thus:
:$\set {\tuple {\alpha, \beta, 1, 0}, \tuple {\beta, -\alpha, 0, 1}, \tuple {p, 0, 0, 0}, \tuple {0, p, 0, 0} }$
spans $L$.
Suppose we have for some $c_1, c_2, c_3, c_4 \in \Z$:
:$\vec 0 = c_1 \tuple {\alpha, \beta, 1, 0} + c_2 \tuple {\beta, -\alpha , 0, 1} + c_3 \tuple {p, 0, 0, 0} + c_4 \tuple {0, p, 0, 0}$
Extracting the various coordinates:
and so:
So:
:$\set {\tuple {\alpha, \beta, 1, 0}, \tuple {\beta, -\alpha, 0, 1}, \tuple {p, 0, 0, 0}, \tuple {0, p, 0, 0} }$
is linearly independent and thus a basis for $L$.
Thus:
Thus:
:$\span_\R L = \R^4$ 
So $L$ is a point lattice.
Define the quotient map:
:$\varphi: \N_p^2 \times \set {\tuple {0, 0} } \to \Z^4 / L$
:$\tuple {x, y, 0, 0} \mapsto \sqbrk {\tuple {x, y, 0, 0} }$
Since quotient maps are surjective:
:$\paren {\Z^4 / L} \le \size {\N_p^2 \times \set {\tuple {0, 0} } } = p^2$
So:
:$\map \det L = \# \paren {\Z^4 / L} < p^2$
Let $\norm {\, \cdot \,}$ denote the Euclidean metric.
Consider $\map {B_{\sqrt {2 p} } } {\vec 0}$, the open ball of radius $\sqrt {2 p}$.
Then:
:$\forall \vec x, \vec y \in \map {B_{\sqrt {2 p} } } {\vec 0}, \forall t \in \closedint 0 1$:
Thus the line between $\vec x$ and $\vec y$ is contained in $\map {B_{\sqrt{2 p} } } {\vec 0}$.
So $\map {B_{\sqrt {2 p} } } {\vec 0}$ is convex.
Let $\vec x \in \map {B_{\sqrt{2 p} } } {\vec 0}$.
Then $\vec x < \sqrt {2 p}$.
That means: 
:$\norm {-\vec x} = \size {-1} \norm {\vec x} = \norm {\vec x} < \sqrt{2 p}$
So:
:$-\vec x \in \map {B_{\sqrt{2 p} } } {\vec 0}$
Then $\map {B_{\sqrt{2 p} } } {\vec 0}$ is symmetric about the origin. 
By the ( the standard measure on $\R^n$):
:$\map {\operatorname {Vol} } {\map {B_{\sqrt{2 p} } } {\vec 0} } = \dfrac {\pi^2 \paren {\sqrt {2 p} }^4} 2 = 2 \pi^2 p^2$
Since $2\pi^2 > 1$:
:$\map {\operatorname {Vol} } {\map {B_{\sqrt{2 p} } } {\vec 0} } > \map \det L$
By Minkowski's Theorem:
:$L \cap \map {B_{\sqrt{2 p} } } {\vec 0} \ne \O$
Thus, if:
:$\vec a = \tuple {a_1, a_2, a_3, a_4} \in L \cap \map {B_{\sqrt{2 p} } } {\vec 0}$
then:
:$0 < a_1^2 + a_2^2 + a_3^2 + a_4^2 = \norm {\vec a}^2 < 2 p$
However:
So $\exists k \in \Z$:
:$(2): \quad 0 < a_1^2 + a_2^2 + a_3^2 + a_4^2 = k p \le 2 p$
Dividing $(2)$ by $p$:
:$0 < k < 2 \implies k = 1$
Thus:
:$a_1^2 + a_2^2 + a_3^2 + a_4^2 = p$
=== Proof for Composites ===
Suppose $x, y \in \Z$ are a sum of four squares with neither of $x$ or $y$ being primes.
Suppose either one is equal to $1$.
Then $x * 1 = x$ is a sum of four squares.
Suppose neither of them is equal to $1$.
Let $\mathbb H$ denote the set of Hurwitz quaternions.
Let $N: \mathbb H \to \R, a + b i + c j + d k \mapsto a^2 + b^2 + c^2 + d^2$ be the standard norm on $\mathbb H$.
Notice:
:$x$ is a sum of four squares $x$ is a norm of a Hurwitz quaternion
Then:
:$\exists \mu, \lambda \in \mathbb H: x = \map N \mu, y = \map N \lambda$
From Norm is Homomorphism:
:$ x y = \map N \mu \, \map N \lambda = \map N {\mu \lambda}$
Since $\mathbb H$ is a ring, we have:
:$\mu \lambda \in \mathbb H$
and thus $x y$ is a sum of four squares.
From the Fundamental Theorem of Arithmetic, every number can be written as a unique product of primes. 
Then 
Category:Lagrange's Four Square Theorem