Four-Square 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 four-square theorem which states:
Every natural number can be represented as the sum of four integer squares.
In fact there is also a Legendre’s three-square 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 four-square theorem shows that the answer to any number \(n\) is no more than 4. Legendre’s three-square 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.
-
Only-If 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.
-
Only-If 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.
Acknowledgment
Legendre | Lagrange |
---|---|
![]() |
![]() |