Today I Learned

June 12th

Today I learned about representing numbers as sums of distinct squares, from a bunch of places. We start with a relatively standard result, which comes from here .

There are a few ways to approach this, but it feels best motivated to just be greedy and pay for the consequences later. The idea is to continually pick up the largest square we can, and these squares should be distinct if the square is on the same scale as what we're subtracting it from. Here's our exact extraction.

Take $k=\floor{\sqrt{n-129}} \gt 0$ as large as possible. Then we note $k^2\le n-129 \lt (k+1)^2$ by construction, so we see\[\frac n2 \lt \frac{(k+1)^2+129}2.\]It suffices to show that $k^2$ is greater than or equal to this, which is an inequality only involving $k$ and therefore solvable. Rearranging, we need\[129\le2k^2-(k+1)^2=k^2-2k-1.\]So what we need is then equivalent to $(k-1)^2\ge131,$ or $k\ge1+\sqrt{131},$ for which $k\ge13$ is enough. However, our bound $13^2+129$ safely guarantees exactly $\floor{\sqrt{n-129}}\ge13.$ This finishes. $\blacksquare$

So our greedy algorithm is to continually pick the largest square we can but keeping the current total above $128.$ Then eventually we will hit some value below $298,$ but we can just check all numbers manually between $129$ and $297 \lt 298.$ For this second justification, a computer program verifies this for us; here is my code.

Anyways, to rigorize our greedy algorithm, we use a strong induction. Our base cases are the positive integers $n$ from $129$ to $297.$ Now, suppose $n\ge298$ and every positive integer smaller than $n$ but at least $129$ can be written as the sum of distinct squares. The lemma gives us a $k$ such that\[n \gt n-k^2 \gt 129,\]so $n-k^2$ can be written as the sum of distinct squares, say $n-k^2=\sum_{\ell=1}^ma_\ell^2.$ However, we now claim that $k^2$ cannot be found among the $\left\{a_\ell^2\right\}_{\ell=1}^m$: indeed, one of those squares $a_\bullet^2$ satisfies\[a_\bullet^2\le\sum_{\ell=1}^ma_\ell^2=n-k^2 \lt \frac n2\]because $k^2 \gt n/2$ from the lemma. However, $k^2 \gt n/2,$ so we must have $a_\bullet\ne k^2.$ Thus,\[n=k^2+\sum_{\ell=1}^ma_\ell^2\]is a valid decomposition of $n$ into distinct squares. $\blacksquare$

Some remarks in order. First off, it might feel unsatisfying that we have to check the cases from $129$ to $298,$ but I don't really see a way around this. At least this elementary method more or less requires some brute force computation; in other words, I don't think we can push this to "sufficiently large $n$'' and avoid the casework.

Secondly, the interesting questions are not really about what we can do if given arbitrarily many squares. Indeed, the main trick in the above proof with the greedy algorithm is only possible because we can continually add on more squares to get larger numbers. There is no hope for this approach if we limit the number of squares.

Thirdly, the proof actually gives us a somewhat explicit bound on the number of distinct squares we need to represent $n,$ though it isn't close to sharp. We begin by refining the lemma.

The proof of this is identical to the previous lemma. Take $k=\floor{\sqrt{n-129}}$ so that $k^2\le n-129 \lt (k+1)^2.$ It follows\[(1-\varepsilon)n \lt (1-\varepsilon)\left((k+1)^2+129\right).\]To be assured that $k^2 \gt (1-\varepsilon)n,$ it suffices for $k^2$ to exceed the right-hand side here. That is, we want\[(1-\varepsilon)\left(k^2+2k+130\right)\le k^2,\]which rearranges into\[130(1-\varepsilon)\le\varepsilon k^2-(1-\varepsilon)\cdot 2k.\]The right-hand side will eventually grow arbitrarily large because the $\varepsilon k^2$ term dominates, we so can be sure that this holds for sufficiently large $k.$ But $k=\floor{\sqrt{n-129}}$ means that this will also hold for sufficiently large $n$ giving sufficiently large $k.$ This finishes $\blacksquare$

Observe that the proof above used $\varepsilon=1/2,$ but we had no good reason to prefer this constant other than that it made the proof actually function by having $n-k^2\le n/2.$ Using a smaller $\varepsilon$ will also work just fine, though it increases the number of needed base cases.

Fix some small $\varepsilon \gt 0$ to use with the previous lemma, and extract our $N.$ We essentially do the same greedy algorithm from before but keep track of the number of squares in the induction.

For our base cases, the computer program from earlier can verify that the largest number of distinct squares needed to represent any integer from $129$ to $N$ is some finite number, say $M.$ Setting $C=M+\log_\varepsilon N,$ for example, guarantees the bound holds for our base cases.

The inductive step is also pretty much the same. Fix $m \gt N$ and suppose that all positive integers $n$ below $m$ but above $129$ can be written as the sum of $-\log_\varepsilon(n)+C$ squares. Again, we can use the lemma to extract some $k$ for which\[(1-\varepsilon)m \lt k^2\le m-129.\]In particular, the number $m-k^2\ge129$ can be written as the sum of at most $-\log_\varepsilon\left(m-k^2\right)+C\le-\log_\varepsilon(\varepsilon m)+C=-\log_\varepsilon(m)+C-1$ distinct squares.

All of these squares are bounded above $m-k^2\le\varepsilon m\le m/2,$ which $k^2$ exceeds, so indeed $k^2$ is distinct from any square in this representation, and we may safely add it back in while keeping all squares distinct. This totals to at most $\log_\varepsilon(m)-C-1+1=\log_\varepsilon(m)+C$ total squares. $\blacksquare$

The statement of the previous proposition is written to be easier to prove, but we can just remark that $-\log_\varepsilon(n)=\frac1{-\log\varepsilon}\cdot\log n.$ As $\varepsilon\to0,$ we have $\log\varepsilon\to-\infty,$ so $\frac1{-\log\varepsilon}\to0,$ so we can refine our statement to the following.

The given $\varepsilon$ can be used to solve for some $\delta$ such that $\frac1{-\log\delta}=\varepsilon.$ Explicitly, we have $\delta:=\exp\left(-\varepsilon^{-1}\right).$ Now, for sufficiently small $\varepsilon,$ we can guarantee $\delta\in(0,1/2]$ because $\varepsilon\to0^+$ sends $\delta\to0^+.$ In this case the previous proposition applies to $\delta,$ and we get the conclusion. $\blacksquare$

Thus, we get that the number of distinct squares required to decompose is something like $o(\log n)$ without having to do any really fancy number theory; after all, the hard part was combinatorics. However, I am obligated to mention that the Hardy-Littlewood circle method can show that five distinct squares is enough to get all but finitely many positive integers. I do not know this proof.