Sum of Squares Theorems

Sum of squares theorems are theorems in additive number theory concerning the expression of integers as sums of squares of other integers. For example, $30 = 1^2 + 2^2 + 5^2$, so 30 can be expressed as a sum of three squares. However, brute force will reveal that 23 cannot be expressed as a sum of three squares. Sum of squares theorems give formulaic ways to differentiate which numbers can and cannot be expressed as sums of squares. This is especially useful for very large numbers, for which brute force methods are computationally impractical.

Sum of squares theorems have found various applications in applied number theory, such as cryptography and integer factoring algorithms. They are often used as intermediate steps in the proofs of other theorems in elementary number theory. Numerous results have been proven concerning what types of integers can be expressed as a sum of $k$ squares for $k \ge 2$, i.e. what form $n$ must take such that $n = a_1^2 + \dots + a_k^2$ for $n, a_i \in \mathbb{Z}$.

In the case that $k=2$, Fermat's theorem on the sum of two squares says that an odd prime $p$ is expressible as a sum of two squares if and only if $p = 4n + 1$ for some positive integer $n$. Formally, Fermat's theorem on the sum of two squares says

For odd prime $p$ $$\exists\ x, y \in \mathbb{Z} \mid p = x^2 + y^2$$ if and only if $$p \equiv 1 \bmod 4.$$

For example, odd primes $5$, $17$, and $41$ are all congruent to $1 \bmod 4$. As predicted by Fermat's theorem on the sum of two squares, each can be expressed as a sum of two squares: $5 = 1^2 + 2^2$, $17 = 1^2 + 4^2$, and $41 = 4^2 + 5^2$. On the other hand, odd primes $7$, $19$, and $31$ are all congruent to $3 \bmod 4$ and cannot be expressed as a sum of two squares.

Proof

The first proof of Fermat's theorem on the sum of two squares was given by Leonhard Euler in 1749. It uses the technique of proof by infinite descent, which intuitively makes use of the fact that the positive integers are finitely bounded from below. The full proof is fairly involved, so a general outline of Euler's proof follows.

1. Use Diophantus' identity to show that the product of two numbers, each of which is a sum of two squares, is itself a sum of two squares.

2. Using Diophantus' identity again, show that a number which is a sum of two squares and is divisible by a prime which is a sum of two squares implies the quotient is a sum of two squares.

3. Using the result from 2, prove by contraposition that a number which can be written as a sum of two squares and is divisible by a number which is not a sum of two squares implies the quotient has a factor which is not a sum of two squares.

4. By infinite descent, prove that if $a$ and $b$ are relatively prime, then every factor of $a^2 + b^2$ is a sum of two squares.

5. Using Fermat's little theorem, show that every prime of the form $4n + 1$ is a sum of two squares.
   

Applications

If an odd integer $n$ can be expressed as the product $n=a^{2}b,$ where all factors of $b$ are congruent to $1 \bmod 4$, then $n$ can be expressed as a sum of two squares. This is equivalent to saying that $n$ can be expressed as a sum of two squares if all prime factors of $n$ congruent to $3 \bmod 4$ have an even exponent. Finding $x$ and $y$ such that $b = x^2 + y^2$ implies $n = (ax)^2 + (ay)^2$, which is a sum of two squares, so the proof reduces to showing that $\exists\ x, y \in \mathbb{Z} \mid b = x^2 + y^2$ when $b$ is a product of primes congruent $1 \bmod 4$. The proof is relatively straightforward by repeated application of Fermat's theorem on the sum of two squares and the Brahmagupta-Fibonacci Identity or the Diophantus' identity.

One application of the prior result is that composite numbers that can be expressed as a sum of two squares are comparatively easy to factor. Euler's factorization method requires expressing a number $n$ as a sum of two different sums of two squares, i.e. $n = a^2 + b^2 = c^2 + d^2$. Using this knowledge, the algorithm deterministically determines nontrivial factors of $n$. Unfortunately, the algorithm has seen limited use since there is no easy way to determine whether $n$ has prime factors congruent to $3 \bmod 4$ with odd exponents.

In the case that $k=3$, Legendre's three square theorem says that a natural number $n$ is expressible as a sum of three squares if and only if $n \neq 4^a(8b+7)$ for integers $a$ and $b$. Formally, Legendre's three square theorem says the following:

For $n \in \mathbb{N}$

$$\exists\ x, y, z \in \mathbb{Z} \mid n = x^2 + y^2 + z^2$$

if and only if

$$\nexists\ a, b \in \mathbb{Z} \mid n = 4^a(8b+7).$$

For example, $13$, $26$, and $41$ cannot be expressed in the form $4^a(8b+7)$ for some integers $a$ and $b$. As predicted by Legendre's three square theorem, each can be expressed as a sum of three squares: $13 = 0^2 + 2^2 + 3^2$, $26 = 1^2 + 3^2 + 4^2$, and $41 = 3^2 + 4^2 + 4^2$. On the other hand, brute force will reveal that $15 = 4^0(8 \cdot 1 + 7)$, $28 = 4^1(8 \cdot 0 + 7)$, and $92 = 4^1(8 \cdot 2 + 7)$ cannot be expressed as a sum of three squares.

The proof for Legendre's three square theorem is quite complicated and thus is not included here. In fact, a proof for the case of $k=4$ was found in 1770, a full 28 years before Legendre discovered his first proof for the case $k=3$.

In the case that $k=4$, Lagrange's four square theorem, also known as Bachet's conjecture, says that every positive integer $n$ can be expressed as a sum of four squares. Formally, Lagrange's four square theorem says the following:

For $n \in \mathbb{N}$

$$\exists\ a, b, c, d \in \mathbb{Z} \mid n = a^2 + b^2 + c^2 + d^2.$$

For example, $3 = 0^2+1^2+1^2+1^2$, $31 = 1^2+1^2+2^2+5^2$, and $310 = 1^2+2^2+4^2+17^2$.

Given Legendre's three square theorem, proving Lagrange's four square theorem is fairly straightforward.

1. If $\exists\ a, b \in \mathbb{Z} \mid n = 4^a(8b+7)$, then $n$ is congruent to $0 \bmod 4$ or $3 \bmod 4$, when $a \neq 0$ or $a=0$, respectively.

2. Else, $n$ is congruent to $1 \bmod 4$ or $2 \bmod 4$, so $n$ can be expressed as a sum of three squares. Since $n = x^2 + y^2 + z^2$ by Legendre's three square theorem, this implies $n = 0^2 + x^2 + y^2 + z^2$, a sum of four squares.

3. For the case $n \equiv 3 \bmod 4$, since $n - 1$ is expressible as a sum of three squares $($since $n - 1 \equiv 2 \bmod 4)$ by Legendre's three square theorem, $n$ can be expressed as a sum of four squares by adding $1^2$ to $(n - 1)$'s three square sum. Since $\exists\ x, y, z \in \mathbb{Z} \mid n - 1 = x^2 + y^2 + z^2$, it follows that $n = 1^2 + x^2 + y^2 + z^2$, which is a sum of four squares.

4. For the case $n \equiv 0 \bmod 4$, note that $n = 4m = 2^{2}m$. Thus, if a sum of four squares exists for $m$, then it exists for $n$ as well, since $m = a^2 + b^2 + c^2 + d^2 \implies n = 4m = (2a)^2 + (2b)^2 + (2c)^2 + (2d)^2$. Repeatedly dividing $n$ by $4$ will eventually yield a number congruent to $1 \bmod 4$, $2 \bmod 4$, or $3 \bmod 4$, which can be expressed as a sum of four squares by the previous three steps. $_\square$
   

Express $28$ as a sum of four squares.

Hint: Use the proof of Lagrange's four square theorem above.

SHOW ANSWER

Since $28 \equiv 0 \bmod 4$, the fourth case applies, and the answer will be of the form $28 = 4m = (2a)^2 + (2b)^2 + (2c)^2 + (2d)^2,$ where $m=7$. Thus, we need to find $a, b, c, d$ that satisfy $7 = a^2 + b^2 + c^2 + d^2$. Since $7 \equiv 3 \bmod 4$, the third case applies, and $7 = 1^2 + a^2 + b^2 + c^2$.

A quick guess and check for $6 = a^2 + b^2 + c^2$ $($by the second case, since $6 \equiv 2 \bmod 4)$ reveals $a=1, b=1, c=2$. Thus, $28 = (2\times1)^2 + (2\times1)^2 + (2\times1)^2 + (2\times2)^2 = 2^2 + 2^2 + 2^2 + 4^2$. $_\square$

• Fermat's Polygonal Number Theorem
• Waring's Problem