Solution to Lagrange's Four Square Theorem with Fewest Terms

Question

Lagrange's four square theorem states that any natural number $n$ can be written as the sum of the square of 4 other integers. For most values of $n$, there are multiple square combinations that work. For example, $16=4^2$ and also $16=2^2 + 2^2 + 2^2 + 2^2$. Is there a name for the solution where first term is as large as possible, the second term is as large as possible (given the value of the first term), and so on? For 16, this would be the $4^2$ solution. I'd still want no more than 4 nonzero terms.

Has this solution been discussed anywhere? I like this solution because it's unique.

Also, would that solution be equivalent to the solution with the fewest nonzero terms?

If no name for this solution exists, what name would you suggest? Names that occur to me are the minimum entropy solution, or the maximum bias solution.

Answer 1

There are obstructions involving the prime 2 that should be considered. First, if a number is divisible by 8 then any expression as four squares will involve only even squares. So, if you begin with an number $n$ that is divisible by $8,$ keep dividing by $4$ until the result is no longer divisible by $8.$ So far, we have $ n = 4^k m$ with $m \neq 0 \pod 8.$

Next, any positive integer $w$ can be expressed as the sum of three squares unless $$ w = 4^v (8u + 7 ) $$ Note how quick it is to check this, keep dividing $w$ by $4$ until it is not divisible by $8,$ then just check the remainder when dividing that number by $8.$ If the remainder is not $7,$ the original $w$ is the sum of three squares.

Together, those give the right way to produce a greedy algorithm. Take $m = n/4^k.$ Find the integer part $B = \lfloor \sqrt m \rfloor.$ Take $a = B, B-1, B-2,...$ and test each $m - a^2$ until you reach a difference that really is the sum of three squares. Now calculate $m-a^2$ for the greedy sum of three squares. There are speed-up steps available here that involve primes other than $2...$ When you have $m=a^2 + b^2 + c^2 + d^2,$ you have $$ n = (2^ka)^2 + ( 2^kb)^2 + ( 2^kc)^2 + ( 2^k d)^2 $$

Answer 2

You can find the greedy four-square representation of a number as follows:

• Generate a list of the squares less than or equal to $n$. That is, for every integer $k$ with $k^2 \leq n$, we add $k$ to a list. Call the set of numbers in our list $S$.

• Now let $f(i, j)$ be a Boolean function whose value equals true if it is possible to express $i$ as a sum of exactly $j$ non-negative squares and false otherwise.

• The function $f$ satisfies the following: $f(i, j) = \bigvee_{k \in S} f(i - k, j - 1)$. In other words, if we can express $i - k$ as a sum of $j - 1$ nonnegative squares, then we can express $i$ as a sum of $j$ squares by simply adding $k$ to our representation. We also have the base cases $f(k, 1) = \text{true}$ for any $k \in S$.

Now you can use a dynamic programming algorithm to compute the values of $f$. If you iterate in backwards order and you maintain a predecessor function $p(i, j)$ whose value equals the state from which we transition from, then you can reconstruct solutions. By iterating backwards, you guarantee that the first term is maximal.