Editing Lagrange's four-square theorem (section)

=== Proof using the Hurwitz integers ===
Another way to prove the theorem relies on [[Hurwitz quaternion]]s, which are the analog of [[integer]]s for [[quaternion]]s.<ref name="Stillwell_2003">{{harvnb|Stillwell|2003|pages=138–157}}.</ref> 

{{math proof|title=Proof using the Hurwitz integers|proof=
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
<math display="block">\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}</math>
where <math>E_0, E_1, E_2, E_3</math> are integers. Thus, the quaternion components <math>a_0, a_1, a_2, a_3</math> are either all integers or all half-integers, depending on whether <math>E_0</math> is even or odd, respectively. The set of Hurwitz quaternions forms a [[ring (mathematics)|ring]]; that is to say, the sum or product of any two Hurwitz quaternions is likewise a Hurwitz quaternion.

The [[field norm|(arithmetic, or field) norm]] <math>\mathrm N(\alpha)</math> of a rational quaternion <math>\alpha</math> is the nonnegative [[rational number]]
<math display="block">\mathrm{N}(\alpha) = \alpha\bar\alpha = a_0^2 + a_1^2 + a_2^2 + a_3^2</math>
where <math>\bar\alpha=a_0 -a_1\mathbf{i} -a_2\mathbf{j} -a_3\mathbf{k}</math> is the [[quaternion#Conjugation, the norm, and reciprocal|conjugate]] of <math>\alpha</math>. 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 <math>\tfrac{1}{4} + n : n \in \mathbb{Z}</math>, 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:
<math display="block"> \mathrm{N}(\alpha\beta)=\alpha\beta(\overline{\alpha\beta})=\alpha\beta\bar{\beta}\bar{\alpha}=\alpha \mathrm{N}(\beta)\bar\alpha=\alpha\bar\alpha \mathrm{N}(\beta)= \mathrm{N}(\alpha) \mathrm{N}(\beta).</math>

For any <math>\alpha\ne0</math>, <math>\alpha^{-1}=\bar\alpha\mathrm N(\alpha)^{-1}</math>. It follows easily that <math>\alpha</math> is a unit in the ring of Hurwitz quaternions if and only if <math>\mathrm N(\alpha)=1</math>.

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 <math>2 = 1^2 + 1^2 + 0^2 + 0^2</math>. To show this for an odd prime integer {{mvar|p}}, represent it as a quaternion <math>(p,0,0,0)</math> and assume for now (as we shall show later) that it is not a Hurwitz [[irreducible element|irreducible]]; that is, it can be factored into two non-unit Hurwitz quaternions
<math display="block">p = \alpha\beta.</math>

The norms of <math>p,\alpha,\beta</math> are integers such that
<math display="block">\mathrm N(p)=p^2=\mathrm N(\alpha\beta)=\mathrm N(\alpha)\mathrm N(\beta)</math>
and <math>\mathrm N(\alpha),\mathrm N(\beta) > 1</math>. This shows that both <math>\mathrm N(\alpha)</math> and <math>\mathrm N(\beta)</math> are equal to {{mvar|p}} (since they are integers), and {{mvar|p}} is the sum of four squares
<math display="block">p=\mathrm N(\alpha)=a_0^2+a_1^2+a_2^2+a_3^2.</math>

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

Since <math>\gamma</math> has even integer coefficients, <math>(\bar\omega\gamma-1)</math> will have integer coefficients and can be used instead of the original <math>\alpha</math> to give a representation of {{mvar|p}} as the sum of four squares.

As for showing that {{mvar|p}} is not a Hurwitz irreducible, [[Joseph Louis Lagrange|Lagrange]] proved that any odd prime {{mvar|p}} divides at least one number of the form <math>u=1+l^2+m^2</math>, where {{mvar|l}} and {{mvar|m}} are integers.<ref name="Stillwell_2003" /> This can be seen as follows: since {{mvar|p}} is prime, <math>a^2\equiv b^2\pmod p</math> can hold for integers <math>a,b</math>, only when <math>a\equiv\pm b\pmod p</math>. Thus, the set <math>X=\{0^2,1^2,\dots,((p-1)/2)^2\}</math> of squares contains <math>(p+1)/2</math> distinct [[modular arithmetic#Congruence classes|residues]] modulo {{mvar|p}}. Likewise, <math>Y=\{-(1+x):x\in X\}</math> contains <math>(p+1)/2</math> residues. Since there are only {{mvar|p}} residues in total, and <math>|X|+|Y| = p+1>p</math>, the sets {{mvar|X}} and {{mvar|Y}} must intersect.

The number {{mvar|u}} can be factored in Hurwitz quaternions:
<math display="block">1+l^2+m^2=(1+l\;\mathbf{i}+m\;\mathbf{j})(1-l\;\mathbf{i}-m\;\mathbf{j}).</math>

The norm on Hurwitz quaternions satisfies a form of the [[Euclidean domain|Euclidean]] property: for any quaternion <math> \alpha=a_0+a_1\mathbf{i}+a_2\mathbf{j}+a_3\mathbf{k} </math> with rational coefficients we can choose a Hurwitz quaternion <math> \beta=b_0+b_1\mathbf{i}+b_2\mathbf{j}+b_3\mathbf{k} </math> so that <math> \mathrm{N}(\alpha-\beta)<1 </math> by first choosing <math> b_0 </math> so that <math> |a_0-b_0| \leq 1/4 </math> and then <math> b_1, b_2, b_3 </math> so that <math> |a_i-b_i| \leq 1/2 </math> for <math> i = 1,2,3</math>. Then we obtain
<math display="block">\begin{align}
\mathrm{N}(\alpha-\beta) & =(a_0-b_0)^2+(a_1-b_1)^2+(a_2-b_2)^2+(a_3-b_3)^2 \\
& \leq \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{align}</math>

It follows that for any Hurwitz quaternions <math>\alpha,\beta</math> with <math>\alpha \neq 0</math>, there exists a Hurwitz quaternion <math>\gamma</math> such that
<math display="block">\mathrm N(\beta-\alpha\gamma)<\mathrm N(\alpha).</math>

The ring {{mvar|H}} of Hurwitz quaternions is not commutative, hence it is not an actual Euclidean domain, and it does not have [[unique factorization domain|unique factorization]] in the usual sense. Nevertheless, the property above implies that every right [[ideal (ring theory)|ideal]] is [[principal ideal|principal]]. Thus, there is a Hurwitz quaternion <math>\alpha</math> such that
<math display="block">\alpha H = p H + (1-l\;\mathbf{i}-m\;\mathbf{j}) H.</math>

In particular, <math>p=\alpha\beta</math> for some Hurwitz quaternion <math>\beta</math>. If <math>\beta</math> were a unit, <math>1-l\;\mathbf{i}-m\;\mathbf{j}</math> would be a multiple of {{mvar|p}}, however this is impossible as <math>1/p-l/p\;\mathbf{i}-m/p\;\mathbf{j}</math> is not a Hurwitz quaternion for <math>p>2</math>. Similarly, if <math>\alpha</math> were a unit, we would have
<math display="block">(1+l\;\mathbf{i}+m\;\mathbf{j})H = (1+l\;\mathbf{i}+m\;\mathbf{j})p H+(1+l\;\mathbf{i}+m\;\mathbf{j})(1-l\;\mathbf{i}-m\;\mathbf{j})H \subseteq p H</math>
so {{mvar|p}} divides <math>1+l\;\mathbf{i}+m\;\mathbf{j}</math>, which again contradicts the fact that <math>1/p-l/p\;\mathbf{i}-m/p\;\mathbf{j}</math> is not a Hurwitz quaternion. Thus, {{mvar|p}} is not Hurwitz irreducible, as claimed.
}}