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

  1. 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)\).

  2. 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.

  3. 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.

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

Acknowledgment

Legendre.jpg Lagrange_portrait.jpg