7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Interesting idea (+1) We could call it the "greedy-representation" $\endgroup$ – Peter Jun 30 at 17:12
  • $\begingroup$ Good name! It has a minimal number of words, which is appropriate! $\endgroup$ – user3433489 Jun 30 at 17:19
  • 1
    $\begingroup$ $\ 88\ $ has the representations $ \ (6,6,4,0)\ $ and $\ (8,4,2,2)\ $. Here we would choose the longer representation. $\endgroup$ – Peter Jun 30 at 17:20
  • 3
    $\begingroup$ The greedy representation might typically use more than four nonzero squares, e.g. $88 = 9^2 + 2^2 + 1^2 + 1^2 + 1^2$. Is that what you mean, or are you requiring only four squares? $\endgroup$ – Robert Israel Jun 30 at 17:42
  • 1
    $\begingroup$ Good point. I'd still want four nonzero squares at the most. I'll include that in the question. $\endgroup$ – user3433489 Jun 30 at 17:48
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer! $\endgroup$ – user3433489 Jun 30 at 20:42
  • $\begingroup$ @user3433489 suggest you implement both methods offered, then check speed by finding your greedy representations for all numbers up to some large bound (after printing out the first few hundred and confirming that everything works.) As I briefly indicated, there are tests that can tell you that a number is not the sum of two squares, so some part of that may be included. $\endgroup$ – Will Jagy Jun 30 at 20:51
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! I like the generality of your answer, but the other answer takes advantage of number-theory speed-ups. $\endgroup$ – user3433489 Jun 30 at 21:48
  • $\begingroup$ No problem. Actually, I agree that @Will Jagy's answer is better than mine :). Happy I could help. $\endgroup$ – Ekesh Kumar Jun 30 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.