# Reply to comment

## The Abel Prize 2012

When did you first realise that you like numbers? Was it when you were first learning your times tables and saw all those number patterns and rhythms unfold in front of your eyes? If yes, then you'll be happy to hear that this year's Abel Prize, one of the highest honours in mathematics, has been awarded to a man whose most famous result answers a simple question related to those humble number sequences.

Endre Szemerédi, Abel laureate 2012.

Endre Szemerédi received the prize last week for his "fundamental contributions to discrete mathematics and theoretical computer science." The honour, which carries a cash sum of over £650,000, was awarded to him for a huge body of work, comprising over 200 academic papers. But in the laudations of Szemerédi's work one result has stood out, partly because of the mathematical advances it involved, but also because the question it answers is beautifully easy to understand.

The result is now known as *Szemerédi's theorem* and
it involves something very similar to times
tables. A times table is a sequence of numbers. The table for 2
is 2, 4, 6, 8, ..., the one for 3 is 3, 6, 9, 12, ..., and the one for
27 is 27, 54, 81, 108 ... . One thing all times tables have in
common, by virtue of being times tables, is that the distance between
two subsequent numbers is always the same. For the 2 times table it's
2, for the 3 times table it's 3 and for the 27 table it's 27. A number
sequence with this property is called an *arithmetic
progression*. You also get an arithmetic progression if you shift
a times table along. For example, you can shift the 2 times table
along by 5 to get 7, 9, 11, 13, .., or you could shift the 3 times
table by 11 to get 14, 17, 20, 23,... . These are examples of
infinitely long arithmetic progressions, but you can also chop them
off at some point to get finite
ones like 15, 20, 25, 30. This is a progression of length 4.

If you like thinking about these things then one question you'll
hit upon pretty quickly is this. Suppose you're given some list of natural
numbers. It'll definitely contain arithmetic progressions of length 1
(that's just a single number)
and 2 (any two numbers in the list). But how long is the longest arithmetic progression it contains? Can you perhaps find arithmetic progressions of *any* length within the list?

If your list is finite, then of course you can’t find arithmetic progressions of any length within it. But what if the list is infinite? Intuitively it’s clear that if the difference between subsequent numbers in your list grows quickly, as is the case with the list , then it’ll be harder to find long arithmetic progressions within it because these require numbers to be regularly spaced. Such a fast-growing sequence, if you consider it as a whole, is pretty sparse within the set of all natural numbers: you have to travel longer and longer distances on the number line before you hit the next number on your list.

There’s a clever way of measuring how sparsely (or densely) a list of numbers is distributed among the other natural numbers. Start by picking your favourite natural number , say , and look at the intersection of your list with the first numbers. In our example using the list above and the intersection consists of 10 and 100. Now divide the size of the intersection, in our case 2, by the number . So in our example we get 2/100. This fraction measures how big the intersection is compared to the set of the first numbers.

Now repeat this for larger and larger values of . You’ll get a sequence of fractions, one for each , each measuring the size of the intersection compared to the size of the set of the first numbers. So as gets larger and larger, what you get in the limit (if you do get something meaningful) will measure the size of the entire list compared to the entire set of natural numbers. In our case the sequence of fractions tends to 0 as gets larger and larger, reflecting the fact that the list is sparse within the set of all natural numbers. (See the box on the left for details.) We define zero to be the *upper density* of our list of numbers.

But what if we look at the opposite extreme, a list in which the distance between subsequent numbers is fixed, for example the 2 times table? Using the same procedure we see that the intersection of the list with the first numbers is 1/2 if is even and if is odd. As gets larger and larger this sequence tends to 1/2, so in this case the upper density is 1/2. This makes sense intuitively, as the even numbers comprise "half" of the natural numbers. If you do the same for the 3 times table you get an upper density of 1/3 and if you do it for the 4 times table you get an upper density of 1/4, etcetera.

It’s possible to work out the upper density for *any* list of numbers in a similar way. The sequence of fractions you get may not always tend to a neat limit, as it did in our examples. But in that case the upper density is defined using another type of limit, called the *limit superior*, which always exists.

### The limit superior

Suppose you have a set of numbers. The *least upper bound* of is the smallest number that is greater than or equal to all the numbers in (and it may be equal to infinity). The *greatest lower bound* is the greatest number that is smaller than or equal to all the numbers in (and it may be equal to minus infinity).

Now suppose you have a sequence of numbers , , , ... . The *limit superior* is defined as follows. First find the least upper bound of the sequence as a whole. Then chop off the first number, , and find the least upper bound of the remaining terms. This might be smaller than the least upper bound of the entire sequence, but it cannot be bigger. Now chop off the first two terms, and and again find the least upper bound of the remaining sequence. Keep going, chopping of the first three, four, five, etc terms. You will get a sequence of least upper bounds in which each number will either be the same or smaller than the previous one. The greatest lower bound of this sequence is defined to be the limit superior of the sequence

The limit superior always exists (though it may be equal to minus or plus infinity). And if the sequence has a limit in the ordinary sense, then this limit and the limit superior agree.

So what can the upper density tell us about the length of arithmetic
progressions contained in a given list? In 1953 the mathematician Klaus
Friedrich Roth proved that a list which has a positive, that is
non-zero, upper density always contains arithmetic progressions of
length three, and in 1969 Endre Szemerédi himself proved that it always
contains progressions of length four. Not very impressive you might
think - these progressions are pretty short - but even these results
took considerable effort. Then in 1975 came the breakthrough now known
as *Szemerédi's theorem*. Szemerédi proved that lists of numbers
with a positive upper density always contains arithmetic progressions of
*any* length.

This tallies with what we have found for the 2 times table, which does have positive upper density. The times table is itself an infinitely long arithmetic progression, so clearly *Szemerédi's theorem* is true: you can find an arithmetic progression of length, say 2,356, simply by chopping off the 2 times table at appropriate points.
Other lists with positive upper density may not contain infinitely long arithmetic progressions, but by *Szemerédi's theorem* you can be sure that they contain finite progressions of any length you like.

*Szemerédi's theorem* itself doesn't have any direct applications in
the real world, though anyone with a love for numbers can probably
appreciate its fascination. It's one of those results, of which there
are many particularly in number theory, which are tantalisingly easy
to state, but very difficult to prove. But the mathematics that was
developed to prove it had consequences way beyond the theorem
itself. An example is a result called *Szemerédi's regularity
lemma*, a stepping stone needed to prove
the theorem. It has turned out to be a powerful mathematical tool in other areas of
mathematics and has been used in the effort
to build computers that can learn from experience. There is an
excellent introduction to the regularity lemma, as well as Szemerédi's
theorem and his other work, written by Tim
Gowers on the Abel Prize website, so we won't go into it here.

*Szemerédi's theorem* also had far reaching consequences within
mathematics. It was used by Terence Tao and Ben Green to prove that
the list of primes contains arithmetic progressions of any length. In 2006 Tao
won the Fields Medal,
another high honour in mathematics, for a body of work including this result.

Szemerédi is the tenth person to receive the Abel Prize, which was established in 2003 in memory of the Norwegian mathematician Niels Henrik Abel. It's awarded annually by the Norwegian Academy of Science and Letters and makes up for the fact that there isn't a Nobel Prize in mathematics. Szemerédi will receive is prize from King Harald of Norway in May.

You can read about previous Abel Prize laureates on *Plus* and also listen to an interview with Ragni Piene, the chair of the Abel Prize committee.