Solution to Lagrange's Four Square Theorem with Fewest Terms

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.


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 $$

Tags:

Terminology

Number Theory

Sums Of Squares

Related

Bound for $\sum_{k=0}^{n}(-1)^k{3n\choose k}{n\choose k}$. Showing a system of equations has no integer solutions How are spin network edges related to anti-symmetric projectors on the Hilbert space of the fundamental rep of SU(2)? Does $\Phi_n(\alpha)=0$ in $\Bbb{F}_p$ for some $\alpha\in\mathbb{F}_p$ imply that $\mathrm{ord}_p(\alpha) = n$? Proving $\sum_{n=0}^\infty\frac{(-1)^n\Gamma(2n+a+1)}{\Gamma(2n+2)}=2^{-a/2}\Gamma(a)\sin(\frac{\pi}{4}a)$ Does parity matter for $\lim_{n\to \infty}\left(\ln 2 -\left(-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots -\frac{(-1)^n}{n}\right)\right)^n =\sqrt{e}$? Existence of curve of constant curvature connecting two points In a metric space a sequence with no converging subsequences is discrete (?) Reference for proof of Green's theorem Summation of $\sum_{n=0}^{\infty}a^nq^{n^2}$ How can I integrate $\int\frac{e^{2x}-1}{\sqrt{e^{3x}+e^x} } \mathop{dx}$? Is there a geometric analog of absolute value?

Recent Posts