FourSquare Theorem
The story begins with a coding problem:
Given a positive integer \(n\), find the least number of perfect square numbers (for example, \(1, 4, 9, 16\), …) which sum to \(n\).
A DP Algorithm
The above problem can be solved with a simple DP algorithm:
int solve(int n)
{
vector<int> v(n + 1, INT_MAX);
v[0] = 0;
for (int i = 1;i <= n;i++)
for (int j = 1;j * j <= i;j++)
v[i] = min(v[i], v[i  j * j] + 1);
return v[n];
}
Not much surprise. But what if you run it through \([1, 100]\), or even more? The result is always between 1 and 4.
Theorems
In fact there is a Lagrange’s foursquare theorem which states:
Every natural number can be represented as the sum of four integer squares.
In fact there is also a Legendre’s threesquare theorem which states:
A natural number can be represented as the sum of three squares of integers if and only if \(n\) is not of the form \(n = 4^a(8b + 7)\) for integers \(a\) and \(b\).
A Faster Algorithm
With these two theorems we have a faster solution to the above problem:
int solve(int n)
{
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;
if (int(sqrt(n)) * int(sqrt(n)) == n)
return 1;
for(int i = 1;i * i < n;i++) {
int j = n  i * i;
if (int(sqrt(j)) * int(sqrt(j)) == j)
return 2;
}
return 3;
}
We now give an analysis of this algorithm. If not otherwise noted, all integers we consider in the analysis below are positive integers.
Analysis

Lagrange’s foursquare theorem shows that the answer to any number \(n\) is no more than 4. Legendre’s threesquare theorem shows that the answer is greater than 3 when \(n\) is not of the form \(n = 4^a(8b + 7)\). So the answer must be exactly 4 when \(n\) is of the form \(n = 4^a(8b + 7)\).

In all other cases the answers can only be 1, 2 or 3. We first determine whether the answer is 1 by checking whether \(n\) is a perfect square. However, the code is actually not checking \(n\) but \(m = 8b + 7\). We need to prove \(n\) is a perfect square if and only if \(m\) is a perfect square.

If part. If \(m = x^2\) is a perfect square, then \(n = 4^am = (2^ax)^2\) is also a perfect square.

OnlyIf part. If \(n = 4^am = y^2\) is a perfect square, then \((2^a / y)^2 = m\). So \(2^a / y = \sqrt{m}\). Since \(m\) is a positive integer, if \(m\) is not a perfect square then \(\sqrt{m}\) is irrational. But \(2^a / y\) is rational. This is a contradiction.


If \(n\) is not a perfect square then we further check whether it is a sum of two perfect squares. We can still check \(m\) instead of \(n\) since we can prove \(n\) is a sum of two perfect squares if and only if \(m\) is a sum of two perfect squares.

If part. If \(m = x^2 + y^2\) is a sum of two perfect squares, then \(n = 4^am = (2^ax)^2 + (2^ay)^2\) is also a sum of two perfect squares.

OnlyIf part. We first prove the following lemma:
If an even number \(4w\) is a sum of two perfect squares, then \(w\) is also a sum of two perfect squares.
Proof. Let \(4w = u^2 + v^2\). Then \(w = (u / 2)^2 + (v / 2)^2\). Since \(4w \equiv 0 \bmod 4\), it must be that \(u\) and \(v\) are both even:

Since \(4w\) is even, it must be that \(u\) and \(v\) are both odd or both even.

If \(u = 2s  1\) and \(v = 2t  1\) are both odd, then \((u^2 + v^2) \equiv (4s^2  4s + 1 + 4t^2  4t + 1) \equiv 2 \bmod 4\). This is a contradiction.
Therefore \(u\) and \(v\) are both even and \(u / 2\) and \(v / 2\) are both integers. So \(w\) is a sum of two perfect squares.
Repeated use of the lemma on \(n = 4^am\) will finish the proof.



If \(n\) is neither a perfect square nor a sum of two perfect squares, then the answer is 3.