2
$\begingroup$

We are defining square factorization as representation a positive natural number as sum of squares of different positive, integer numbers. For example $5 = 1^2 +2^2$ and $5$ has no more representation. But one number can possess more representations, eg. $30$.

$$30 = 1^2 + 2^2 + 5^2 = 1^2 +2^2 + 3^2 + 4^2$$

Sometimes $n$ has no representation, eg. $8$. If square factorization for $n$ is impossible, we call $n$ indecomposable, so $8$ is indecomposable. Because it is a significant part of other proof I began to wonder, how can we know there is finite number of indecomposable numbers. Of course, it is well know fact, but I have still problem with proving that.

How to show that any number greater than $128$ can be written as sum of distinct squares — for all $n > 128$ square factorization exist?

$\endgroup$
5
$\begingroup$

First, you show that you can express all numbers $129$ though something convenient as a sum of distinct squares just by making a list. I will choose $4900$ and assume that we have a list that runs that high. We do the proof by strong induction. Assume that all numbers in the range $[129,k]$ can be expressed as a sum of distinct squares, where $k \ge 4900$. We shall show that $k+1$ can be so expressed. Let $m = \lfloor \sqrt {k+1} \rfloor -1$. We can express $k+1=m^2+p$, where $p \ge 129$, so it can be expressed as a sum of distinct squares. Since $p \lt m^2$, there is no conflict with the new square, and $k+1$ can be expressed as a sum of distinct squares. You could lower the bound of the specific list below $3600$ if you think harder about what square to subtract. I chose $3600$ because the spacing of squares attains $129$ at that point.

Added: the list you make can run only through $[129,297]$. We can be lazier in the first part with more work in the second. $297$ is a risk because $297=169+128$, so the largest square you can subtract and stay larger than $129$ is $144$ and the expression for $153$ could involve $144$. In fact $144+9=153$, but you can also do $100+49+4$. Starting with $298$ you can always subtract a square that leaves at least $129$ and is greater than half the starting number, so the strong induction goes through.

$\endgroup$

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.