# sum of 4 squares

Is there any natural number $A$ which cannot be written as: $$A=W^2+X^2+Y^2+Z^2$$ where $W,X,Y,Z \in \mathbb N \cup 0$

I was considering the fact that $a^2+b^2 \not = 1 \mod 4$ and was attempting to determine simular results for $3$ and $4$ squares when I realised that I could not find a number which did not work for $4$. I did a quick search and found that no numbers less than $1000$ contradict this. I have been trying to find a proof but have been, so far, unsuccessful. This is too general a concept to be new but I have not been exposed to it previously.

-
No, all numbers can be expressed as the sum of four squares. Check this out: en.wikipedia.org/wiki/Lagrange's_four-square_theorem – Daniel R Dec 16 '13 at 15:27
If you post that as an answer, that is sufficient. It shows me where to look to learn more. – kaine Dec 16 '13 at 15:29
I should have assumed this was tied to Lagrange and Gauss; it seems like everything is. – kaine Dec 16 '13 at 15:33

## 4 Answers

No, all numbers can be expressed as the sum of four squares. More information, and a proof using the Hurwitz integers, can be found here.

-

This is Legendre's theorem on the sum of four squares. As the squares are congruent to 0, 1 or 4 (mod 8), anything integer congruent to 7 (mod 8) cannot be written as the sum of three squares. Perhaps the easiest way to prove this theorem is using Quaternions, an extension of the complex numbers in $R^4$.

-
Lagrange, not Legendre. – egreg Dec 16 '13 at 15:47
Legendre did, apparently, extend this to develop the 3 squares situation (which is what vukov is describing) so it isn't completely off. – kaine Dec 16 '13 at 15:56

Just for completion, here is an elementary proof using modular arithmetic, which I wrote up previously for a number theory course.

Claim For any $n \in \mathbf{N}$ there exists $w,x,y,z \in \mathbf{Z}$ such that $n=w^2+x^2+y^2+z^2$.

Proof: First, we observe that sums of four squares are closed under multiplication. That is given $a,b,c,d,e,f,g,h$ integers, there are $w,x,y,z$ such that

$$(a^2+b^2+c^2+d^2)(e^2+f^2+g^2+h^2)=w^2+x^2+y^2+z^2.$$ I will not prove this, it follows from expanding the terms and finding the right expressions for $w,x,y,z$. Alternatively, there is a proof considering certain matrices over $\mathbf{C}$.

So, let $n \in \mathbf{N}$. By prime decomposition, there are primes $p_1,\dots_,p_k$ such that $n=p_1^{e_1}\cdots p_k^{e_k}$. If one of the $p_i$ is $2$ then notice that $2=1^2+1^2+0^2+0^2$. So that any power of $2$ is a sum of four squares by the previous result. Now, let $p \vert n$ such that $p \equiv 1 \mod 4$ or $p \equiv 3 \mod 4$.

Consider the sets $S_1=\{u^2 : u \in \{0,1,\dots,p-1\}\}$ and $S_2 = \{-1-v^2 : v \in \{0,1,\dots,p-1\}\}$. Since $p$ is a prime, we have there are $\frac{p-1}{2}$ nozero squares modulo $p$ and $\frac{p+1}{2}$ including $0$. $S_1$ and $S_2$ both contain precisely these numbers so that the cardinality of both is $\frac{p+1}{2}$. Thus, since there are only $p$ elements of the set $\{0,1,\dots,p-1\}$, we see $S_1 \cap S_2 \neq \emptyset$. Thus, there is $u,v\in \{0,1,\dots,p-1\}$ such that $u^2\equiv-1-v^2 \mod p$. Thus, we have $u^2+v^2+1\equiv 0 \mod p$. So that there is an integer $k$ such that $$u^2+v^2+1=kp.$$

Now, if $k=1$ we are done, since $p$ is the sum of three squares, we can add $0^2$ and the result holds. Suppose $k\neq 1$. We can see immediately that $k >1$, since $u^2+v^2+1 \geq 1$. So, we have $k \in \mathbf{N}$. We will then produce a strictly decreasing sequence of integers $k_1,k_2,\dots$ which are bounded below by $1$. As a result, there is $m$ such that $k_m=1$. In which case we have that $p$ is the sum of four squares.

Now, we examine our $k$. We have, by renaming $u$ and $v$ four integers $a,b,c,d$ such that $a^2+b^2+c^2+d^2=kp$. Now $k$ is either even or odd. If $k$ is even, then $kp$ must be even. Since the square of an even number is even and an odd number is odd, we then can only have 0,2 or 4 of $a,b,c,d$ even. Without loss of generality, take $a\equiv b\mod 2$ and $c \equiv d \mod 2$. Then, let $a_1=\frac{a+b}{2}, b_1=\frac{a-b}{2},c_1=\frac{c+d}{2}, d_1=\frac{c-d}{2}$ and observe that $${a_1}^2+{b_1}^2+{c_1}^2+{d_1}^2= \frac{a^2+b^2+c^2+d^2}{2}=\frac{kp}{2}.$$ Thus, there is $k_1 = k/2$ such that $k_1p$ is the sum of four squares.

Now, by repeating the above argument, we can assume we have found $k_l$ such that $k_l$ is odd. Thus, $k_l p={a_l}^2+{b_l}^2+{c_l}^2+{d_l}^2$. So, we can find $e,f,g,h \in \{\frac{-k+1}{2},\dots,\frac{k-1}{2}\}$ such that $a_l\equiv e,b_l\equiv f, c_l \equiv g, d_l \equiv h \mod k_l$. Thus, $e^2+f^2+g^2+h^2 < 4\left( \frac{k_l}{2}\right)^2=k_l^2$.

Thus $$({a_l}^2+{b_l}^2+{c_l}^2+{d_l}^2)(e^2+f^2+g^2+h^2) < k_l^2 k_l p.$$

So we can divide through by $k_l^2$ and find integers $a_{l+1},b_{l+1},c_{l+1},d_{l+1}$ such that ${a_{l+1}}^2+{b_{l+1}}^2+{c_{l+1}}^2+{d_{l+1}}^2=k_{l+1}p$ where $k_{l+1} < k_{l}$.

Thus, by repeating the arguments above, we have constructed a decreasing sequence of natural numbers $(k_i)$. So, we must have some $m$ such that $k_m=1$. In which case, we see that there are integers $w_0,x_0,y_0,z_0$ such that $$w_0^2+x_0^2+y_0^2+z_0^2 = k_m p=p.$$

As we've seen before, we have seen that sum of four squares are closed under multiplication, so that there are integers $w,x,y,z$ such that $n=w^2+x^2+y^2+z^2.$ as desired. Thus any integer is the sum of four squares.

-

This can even be extended to higher powers:

Edward Waring, says that for every natural number $n$ there exists an associated positive integer s such that every natural number is the sum of at most $s$ $k$th powers of natural numbers (for example, every number is the sum of at most 4 squares, or 9 cubes, or 19 fourth powers, etc.) from here.

-