# Waring's problem for beginners

This is an introduction to Waring's problem, designed for non-mathematicians.  Clicking on a link should give you a very short definition of that term, or a link to a biography of that mathematician.  There is a shorter version of this introduction for people in a hurry.  You can find it here.  (That said, I hope that the longer version will actually be easier to understand!)

Can we write 10 as a sum of four squares?  Yes: 10 = 9 + 1 + 0 + 0 = 32 + 12 + 0 + 0.  In fact, we can do it in more than one way (10 = 4 + 4 + 1 + 1 = 22 + 22 + 12 + 12), but let's not worry about that for now.

Can we write 123456789 as a sum of four squares?  Yes.  For example, 123456789 = 123454321 + 2304 + 100 + 64 = 111112 + 482 + 102 + 82.  That wasn't quite so easy, but with the help of a pocket calculator it didn't take me long.

But what happens if I ask this question about lots of numbers?  Indeed, can we write any positive whole number as a sum of four squares?  Even if my calculator were big enough to cope with numbers like 10000000000000000000000000000000000000000 (which it isn't), I still couldn't use it to answer this question, because there are infinitely many positive whole numbers, so I simply can't check them all one at a time!

This is where mathematics (rather than simple arithmetic) comes in.  I'm not going to describe the proof here, not because it's enormously difficult, but because I'm trying to keep this reasonably short.  But I'll state the result properly.

Lagrange's Theorem: Every positive whole number is a sum of four squares.

Now that we know (or at least are going to believe) this, where do we go next?  Here are two possible directions.

1. Do we need four squares, or can we actually write every positive whole number as a sum of three squares?  Or perhaps two squares?  (I should say that I'm muddling the chronology here: Fermat thought about sums of two squares before Lagrange thought about his problem.)

It's not very difficult to think of numbers that aren't sums of three squares.  For example, 7 isn't.  (This is easy to check!)  And in fact there are infinitely many numbers that aren't sums of three squares.  It turns out that one can characterise the numbers that can be written as a sum of two squares, and the numbers that can be written as a sum of three squares.  That is, one can find some nice condition that will tell you whether the answer is yes or no — and it's not just “Is it a sum of two squares?”!  For example, an odd prime number is a sum of two squares if and only if it leaves a remainder 1 when divided by 4.

2. What happens if we replace squares by cubes?  Or higher powers?  This is where Waring's problem comes in.  Waring claimed (without offering a proof) that every positive whole number is a sum of nine cubes, or nineteen fourth powers, and so on.  (You're not expected to be able to spot a pattern in the numbers of summands needed (4, 9, 19) — I think that he must have come up with them by experimenting.)  Here is a more precise statement of the problem.

Waring's problem: Take any whole number k that is greater than or equal to 2.  Show that there is some number s (that is allowed to depend on k) so that every positive whole number is a sum of s kth powers.

For example, we know that we can take s = 4 when k = 2 (this is Lagrange's theorem).  It is also known that every positive whole number is a sum of nine cubes, so when k = 3 we may take s = 9.  Note, however, that to solve Waring's problem as I've stated it, it is not necessary to give an explicit s, only to show that one exists.  Finding the smallest s that works is much harder than just finding some value that works (although it is definitely an interesting problem).

This problem was first solved by Hilbert.  A few years later, Hardy and Littlewood proved that for any k there is an s so that every sufficiently large whole number is a sum of s kth powers — and moreover they gave an approximate formula for the number of ways in which each whole number is a sum of s kth powers.  This formula gives better and better answers for larger and larger numbers.

Their proof used a technique now called the Hardy-Littlewood circle method (or just the circle method).  I'm not going to write about it here (because doing so would make this a lot longer, although it's very interesting!), but I do want to draw attention to one potentially surprising feature of the proof.  This is that it uses approximation — not perhaps something that one would expect in a proof of a result about whole numbers!

Here is a very crude outline.  Hardy and Littlewood were able to write down an expression (an integral) for the number of ways to write a whole number N as a sum of s kth powers.  Since this is a number of ways to do something, it must be 0 or a positive whole number.  They were then able to estimate that quantity, using various techniques, and showed that if they chose a suitable s and if N is large enough, then the number of ways to write N as a sum of kth powers is positive — and so, since it must be a whole number, is at least 1.  That is, they could find an s (depending on k) so that if N is big enough, then there is indeed some way to express it as a sum of s kth powers.

So that's a brief introduction to Waring's problem!

A sum of four squares: For example, 10 is a sum of four squares: 10 = 9 + 1 + 0 + 0 = 32 + 12 + 02 + 02.

Square numbers: 12 = 1 × 1 = 1, 22 = 2 × 2 = 4, 32 = 3 × 3 = 9, 42 = 4 × 4 = 16, ….  Here, we'll also include 02 = 0 × 0 = 0.

Prime number: A prime number is one that is divisible only by itself and 1.  The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.  Mathematicians choose to define 1 not to be prime, because that turns out to be more convenient than defining it to be prime.  The only even prime number is 2, because every even number is divisible by 2, and so any even number larger than 2 can be divided by a number other than itself and 1.

Cubes: 13 = 1 × 1 × 1 = 1, 23 = 2 × 2 × 2 = 8, 33 = 3 × 3 × 3 = 27, 43 = 4 × 4 × 4 = 64, ….  Again, we'll include 03 = 0 × 0 × 0 = 0.

kth powers: 1k = 1, 2k, 3k, 4k, …, and we'll include 0k = 0 too.

Every sufficiently large positive integer: From some point on (e.g. 10, or 1000000, or 100000000000000, or whatever), every whole number.  This requirement is a consequence of the method that Hardy and Littlewood used, but it is also quite natural.  It may be that there are a few small numbers that need many kth powers, but every whole number after a certain point on only requires relatively few.  This sort of condition is a common feature of results in this area.