Nineteen fourth powers, and then sixteen

Nine cubes for two numbers followed Waring’s problem one power up from squares. Every number is a sum of four squares, by Lagrange’s theorem of 1770; every number is a sum of nine cubes, but only 23 and 239 actually need nine, and beyond a modest bound eight suffice, then seven, and perhaps far fewer. The same year as Lagrange’s theorem, Edward Waring stated without proof that every number is a sum of at most nine cubes and at most nineteen fourth powers, and so on for higher powers.

The fourth powers are where the picture becomes clean enough to compute completely. There are only two numbers that matter: $g(4)$, the most fourth powers any number needs, and $G(4)$, the most needed by infinitely many numbers. Both are now known — $g(4) = 19$ and $G(4) = 16$ — and the gap between them is filled by a finite list of stragglers that a computer can find in a second.

Waring’s question at every power #

Waring’s problem asks the same question at every power, and the answers at successive powers have very different characters. For first powers it is trivial: every number is a sum of ones. For squares, two squares suffice only for the numbers whose primes of the form $4k + 3$ appear to even powers — almost no number, in the sense of density — three squares suffice for everything except Legendre’s $4^a(8b + 7)$, and four squares suffice for everything, by Lagrange. The four-squares theorem has a proof through the identity that multiplies sums of four squares and through the quaternion integers, and it is a statement about all numbers at once: $g(2) = G(2) = 4$, with infinitely many numbers needing four.

For cubes the two numbers separate. Every number is a sum of nine cubes, but only 23 and 239 need nine; $g(3) = 9$ while $G(3)$, the count needed by infinitely many, is somewhere from 4 to 7 and unknown. Even the question of which numbers are sums of three cubes, positive or negative, is open — thirty-three needed a search through numbers with sixteen digits.

For fourth powers the two numbers separate again, $g(4) = 19$ against $G(4) = 16$, but this time both are known, and the reason is the congruence modulo 16. It forces the lower bound for $G(4)$ exactly, and once the lower bound is exact the analytic methods only have to prove an upper bound that matches it. For no higher power is that true: modulo the corresponding power of 2 or 3, fifth and higher powers take values that leave the congruence lower bound below what the analysis can reach, and $G(k)$ is unknown for every $k \ge 5$.

Squares have a further refinement that fourth powers lack. A sum of squares with coefficients, $ax^2 + by^2 + cz^2 + dw^2$, can be asked which numbers it represents, and Conway and Schneeberger’s theorem says that such a form represents every positive number as soon as it represents the nine numbers 1, 2, 3, 5, 6, 7, 10, 14 and 15. A finite check settles an infinite question. The fourth-power problem has the same flavour at its edge — a finite computation below a bound, a theorem above it — but its finite part is the hard part only because the analytic part could not reach low enough.

Counting every number to ten million #

The fourth powers below ten million are $1, 16, 81, 256, 625, 1296, \ldots, 56^4 = 9{,}834{,}496$, fifty-six of them. The fewest needed to make $n$ satisfies a one-line recursion: it is one more than the fewest needed to make $n - k^4$, minimised over every fourth power $k^4 \le n$. Filling in a table from $n = 1$ upwards takes fifty-six comparisons per number and about a second for all ten million, and the table records, for every $n$, both the count and a fourth power to subtract first, so that a shortest decomposition can be read back.

The hero draws the first sixteen thousand numbers. Most need between five and fifteen. A few need more, and they are all small: the band never rises above sixteen anywhere to the right of 13,792.

The table is a small instance of dynamic programming, and its cost is set by memory as much as by time: one byte per number for the count and one for the first fourth power to subtract, twenty megabytes for ten million numbers. Reading a decomposition back costs one step per piece, so the shortest decompositions of any number in range are available at once. The same table gives every count at the same time; nothing about the nineteens, the seventeens or the sixteens needs a separate search.

Why 79 needs nineteen #

Every fourth power leaves remainder 0 or 1 on division by 16. An even number to the fourth power is a multiple of 16, and an odd one is 1 more than a multiple of 16, since $(2j + 1)^4 = 1 + 8j(j+1)(2j^2 + 2j + 1)$ and $j(j+1)$ is even. So a sum of $s$ fourth powers leaves a remainder of at most $s$ when it is less than 16, and a number leaving remainder $r$ needs at least $r$ fourth powers.

The number 79 leaves remainder 15, so it needs at least fifteen fourth powers, of which at least fifteen must be odd and so at least 1; and since 79 is less than 81 the only fourth powers available are 1 and 16. Fifteen ones leave 64, which is four sixteens, and that is nineteen pieces; using fewer ones would need the remaining remainder to come from odd fourth powers larger than 1, of which there are none below 81. The same argument gives 159, 239, 319, 399, 479 and 559, each 80 more than the last, each needing nineteen: $79 + 80k$ for $k = 0$ to 6, until $k = 7$ reaches 639, where 625 becomes available and the count drops.

That nineteen is the true maximum for every number is much harder. Ramachandran Balasubramanian, Jean-Marc Deshouillers and François Dress proved $g(4) = 19$ in 1986, completing a programme that had reduced the problem to checking a finite range by computer and then shrinking that range with analytic estimates until the two met.

How many need each count #

Below ten million, 56 numbers are themselves fourth powers, 1,467 are sums of two, 24,173 of three, and from five to fifteen the counts are each in the hundreds of thousands to over a million. Then the counts collapse: 1,178 numbers need sixteen, 65 need seventeen, 24 need eighteen and 7 need nineteen. The distribution is not a smooth hump with a tail; it has a wall at sixteen, beyond which only finitely many numbers lie.

The flat stretch from nine to fifteen, each count close to a sixteenth of ten million, is the remainder argument again. Numbers leaving remainder 9 need at least nine fourth powers, those leaving 10 need ten, and so on up to 15, and for large numbers the lower bound is almost always enough.

Between nine and ten million, every number with remainder 9 or more needs exactly as many fourth powers as its remainder — the figure finds no exception in more than four hundred thousand numbers — and the lower bound is never beaten for any remainder. For remainder 8 the share is 99.89 per cent. For smaller remainders the bound leaves more room and the count is usually larger: a number leaving remainder 3 needs exactly three fourth powers less than half a per cent of the time, because three ones and a multiple of sixteen made from very few even fourth powers is a rare coincidence. The shape of the curve is the shape of the problem: for large remainders the ones are forced and the rest is easy, and for small ones the rest is the hard part.

The stragglers #

The last number to need nineteen is 559, the last to need eighteen is 1,248 and the last to need seventeen is 13,792. Each is a number for which neither the remainder nor the size gives enough room.

The number 1,248 is a multiple of sixteen, so the remainder argument asks nothing of it; it needs eighteen because it is just too small to use 1,296 = $6^4$ and too awkward to be filled by $4^4 = 256$ and $3^4 = 81$ without many ones. Its best decomposition is two 256s, nine 81s and seven ones. The number 13,792 is also a multiple of sixteen. Its best uses $9^4 = 6{,}561$, three $7^4 = 2{,}401$, one sixteen and twelve ones, seventeen pieces; nothing with sixteen works. Above it, every number in the table needs sixteen or fewer.

The stragglers thin out in a recognisable way. The seven nineteens are evenly spaced, 80 apart, by the argument above. The twenty-four eighteens all lie below 1,250 and the sixty-five seventeens below 13,800, and the remainders tell their story: of the eighteens, 22 leave remainder 14 or 15 on division by 16 and only 2 are multiples of 16; of the seventeens, 46 leave 13, 14 or 15 and 19 are multiples of 16. Most stragglers are numbers forced to spend thirteen or more ones and too small to use the large fourth powers that would let the rest be covered cheaply; the multiples of sixteen among them, 1,248 and 13,792 included, are the ones where the even part itself is awkward. As $n$ grows, the supply of usable fourth powers grows like $n^{1/4}$, the number of ways to combine a few of them grows faster still, and the forced ones stop being expensive. The last stragglers are the numbers at which that supply finally becomes enough.

That 13,792 is the last number needing seventeen for ever is a theorem, not a table. Jean-Marc Deshouillers, François Hennecart and Bernard Landreau showed in 2000 that every number from 13,793 to $10^{245}$ is a sum of sixteen fourth powers, by a computation organised around the residues modulo powers of 2 and 5; Deshouillers, Koichi Kawada and Trevor Wooley proved in 2005, by the circle method, that every number beyond a bound well below $10^{245}$ is too. The ranges overlap, and together they settle the matter.

How the large numbers are handled #

The table handles every number to ten million by brute force; the theorem that nothing beyond 13,792 needs seventeen handles all the rest by the circle method of Hardy, Littlewood and Ramanujan. The method counts the representations of $n$ as a sum of $s$ fourth powers as an integral of the $s$-th power of a generating function round a circle, the same device that gave the size of the partition numbers its exact asymptotic formula. The integral splits into arcs near fractions with small denominators, which give a main term growing like $n^{s/4 - 1}$ times a product of local factors — one for each prime, measuring how many representations exist modulo powers of that prime — and the remaining arcs, which must be shown to contribute less.

The local factor at the prime 2 is where the congruence modulo 16 reappears: it is nought for numbers like $31 \cdot 16^m$ when $s \le 15$, and positive for every number when $s = 16$. That is why sixteen is the threshold the analysis aims at. Davenport proved in 1939 that the remaining arcs are small enough, for sixteen fourth powers and every sufficiently large $n$. Making “sufficiently large” explicit, and small enough to meet a computation coming up from below, took until 2005 — and the computation from below is the one that also found 13,792 to be the last exception.

Sixteen, for ever #

The remainder modulo 16 also explains why sixteen can never be improved. Take $31 \cdot 16^m$. Any representation of it as a sum of fewer than sixteen fourth powers has fewer than sixteen odd terms; working modulo 16, the number of odd terms must then be 0, since $31 \cdot 16^m$ is a multiple of 16 and the odd terms each contribute 1. So every term is even, and dividing every term by 16 gives a representation of $31 \cdot 16^{m-1}$ with the same number of terms. Descending to $m = 0$ gives a representation of 31 with fewer than sixteen fourth powers, which is impossible: 31 leaves remainder 15 and is less than 81, so it needs fifteen ones and one sixteen. So $31 \cdot 16^m$ needs sixteen for every $m$, infinitely many numbers need sixteen, and $G(4) \ge 16$. Harold Davenport proved in 1939 that every sufficiently large number needs at most sixteen, so $G(4) = 16$ exactly — the only exponent beyond squares for which $G$ is known.

The numbers needing sixteen do not die away. From a thousand onwards each decade contains about three hundred of them — 241, 299, 287 and 304 in the decades from $10^3$ to $10^7$ — so their share of all numbers falls tenfold with each decade, but their count does not. Only one per decade or none is of the form $31 \cdot 16^m$; the rest are other numbers for which no arrangement of the available fourth powers does better than sixteen.

Beyond ten million, theorems take over #

The theorems beyond ten million. The table is exact to ten million and says nothing beyond it. That nothing above 13,792 needs seventeen, that nothing anywhere needs twenty, and that infinitely many numbers need sixteen are proved, by the arguments described, not computed.

Which representation. The decompositions drawn are one shortest representation each, the one the table’s recorded first step leads to. Most numbers have many shortest representations, and the counting of representations — how many ways $n$ is a sum of $s$ fourth powers — is a separate and deep subject, where the circle method gives asymptotic formulas once $s$ is large enough.

Why three hundred per decade. The steady count of numbers needing sixteen is measured, not explained here. Most of them are small multiples of powers of 16 with awkward odd parts, and a full account would follow the 2-adic structure of the problem, as the 2000 computation did.

Sixteen is forced by congruence only for special numbers. Most numbers needing sixteen in the table are not of the form $31 \cdot 16^m$ and are not forced to sixteen by any single congruence; they need sixteen because of a combination of their remainder and their size. Only the family $31 \cdot 16^m$ is forced for ever by the argument above, and it alone is what makes $G(4)$ at least sixteen. Whether every number needing sixteen beyond some point is of a special 2-adic shape is a question the table suggests and does not settle, and one the circle method, which describes typical numbers rather than exceptional ones, is not designed to answer.

Still open: what lies between squares and fourth powers #

For squares, $G(2) = g(2) = 4$, and the numbers needing four are exactly those of Legendre’s form $4^a(8b + 7)$, a statement as clean as anything in number theory. For fourth powers $G(4) = 16$ and $g(4) = 19$, with a finite list of exceptions between. For cubes, the case in between, $g(3) = 9$ is known, but $G(3)$ is only known to lie between 4 and 7: the infinitely-often value has resisted for nearly a century. Linnik proved $G(3) \le 7$ in 1943, and large computations suggest that every sufficiently large number is a sum of four cubes. Why the fourth powers are tractable and the cubes are not is visible in this essay’s second figure: modulo 16 the fourth powers take only two values and their obstruction is exact, while cubes modulo every number take too many values for any congruence to force a large count. Without a congruence to supply the answer, $G(3)$ must be found by analysis alone, and analysis has so far reached only seven.