An important function that arises from Waring’s problem is the the following. For any , let be the least such that, for all sufficiently large (how large can depend on and ) there exist positive integers such that
Waring’s problem itself says that actually exists for all . In other words, past some (possible very large) integer, all integers are the sum of at most some constant number of th powers. The classical case is Lagrange’s theorem, which states that . In fact, we can make the stronger statement that all integers, not just the large ones, are the sum of at most four squares.
In this post, I’ll give a nice bound for (and hence, in particular, actually exists). I’ll be following section 21.2 of Hardy and Wright.
In what follows, will always denote an integer congruent to 1 modulo 6. Define
For large we have — a quick computation shows that this is true for , for example. It follows that if we define the interval then these overlap, and so for these intervals overlap. In particular, every is in one of these intervals.
It suffices to show, therefore, that if for some fixed then we can write as the sum of at most cubes.
Let , , and be the smallest positive integers such that
In particular, note that is the sum of 5 cubes. Furthermore,
Similarly, . Hence is a multiple of , so we can write
for some . If were some constant, we could stop here having shown that , but unfortunately could be increasing with , and hence , so a further reduction is required.
Here we use the fact mentioned above, that . Hence we can write . Plugging this into the above and doing some elementary algebra proves the identity
We have written as the sum of 13 cubes, and all that remains is to check that these are positive cubes — this follows from the fact that , so here is where we needed . The proof is complete.
A couple of final notes:
1) By checking all by hand, or by being clever first and then checking by hand, it can be shown that in fact every integer is the sum of at most 13 cubes.
2) The right answer is . This can be proved in a way similar to the above if we assumed that every integer which is not of the form is actually the sum of three squares. This is true, but difficult.