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

2 Answers 2

6
$\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$
4
$\begingroup$

I actually did this for fun when I was 17 (and it was mostly fun, though a bit of a grind). The way I did it was to realise that, for numbers 0 mod 4, I only needed to test up to 512, because anything after that could be written as 4 times the solution for the quarter of that number (for example, if 129 = 100 + 25 + 4, then 516 = 400 + 100 + 16). After that, numbers 1 mod 4 need to be tested up to 517 (take any solution that can be quadrupled and add 1), numbers 2 mod 4 need to be tested up to 526 (add 9 and 1), and numbers 3 mod 4 need to be tested up to 551 (add 25, 9 and 1). The grindy part was testing all those numbers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .