Here is a problem that made me go “wow…what??” when I first saw it.
Prove that every positive integer can be written as the sum of not more than 53 fourth powers of integers.
The problem appears in The USSR Olympiad Problem Book by Shklarsky, Chentzov and Yaglom. What surprised me was the appearance of 53. Well, it turns out that there is nothing sacred about 53. In fact, the number 53 can be replaced by 19, but then the proof would not be elementary (in fact, the latter fact was only established in 1986). One can ask more general question, that is, for a given positive integer , whether every positive integer can be written as a sum of -th powers of positive integers where is some absolute constant (only depending on ). This is called the Waring’s problem, and answer turns out to be yes. Without getting too ambitious, let’s go back to the problem (53 fourth powers).
Here is solution to the problem outlined in the book. We will kind of cheat and use the fact that every positive integer can be written as sum of 4 squares. This is known as Lagrange’s four square theorem. Now, we observe the following identity
which is easily checked by expanding and simplifying. Applying the identity to all pairs made from , we get
Since every positive integer can be written as sum of 4 squares, the identity above implies that six times any positive integer squared can be written as sum of twelve 4th powers of integers. (Some of the expressions in the brackets may be zero; for example when ; that is why we can also say that six times any perfect square can be written as sum of not more than twelve 4th powers of integers).
Now, every positive integer can be written as where . Write as sum of 4 squares, say . Then we have
By the observation made above, each of the , , , can be written as sum of not more than twelve 4th powers of integers. This accounts for terms. But we need to take care of the remainder as well. But since can be one of the 5 possible choices (0,1,2,3,4 or 5), we will just write
and thus, to represent , we need at most 4th powers of integers. .