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

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 $L=\{ 10, 100, 1000, 10000, 100000, ...\} $, 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 $N$, say $N=100$, and look at the intersection of your list with the first $N$ numbers. In our example using the list $L$ above and $N=100$ the intersection consists of 10 and 100. Now divide the size of the intersection, in our case 2, by the number $N$. So in our example we get 2/100. This fraction measures how big the intersection is compared to the set of the first $N$ numbers.

To see that the fractions for the list $L$ tend to zero, first notice that the numbers in the list are all powers of 10: $10=10^1$, $100=10^2$, $1000=10^3$, etcetera. If $N$ is an exact power of 10, say $N=10^ k$ for some $k$, then the size of the intersection is simply $k$, so the fraction is $k/10^ k.$ As $k$ gets larger and larger, the fractions $k/10^ k$ approach zero. If $N$ lies between two powers of 10, say $10^ k<N<10^{k+1},$ then the size of the intersection is still $k$, but since $N>10^ k,$ we have $k/N<k/10^ k,$ so the fraction for such a value of $N$ is less than the fraction for the previous power of 10. And since the sequence of fractions for powers of 10 tends to zero, this means that the sequence of fractions for all $N$ tends to zero too.

Now repeat this for larger and larger values of $N$. You’ll get a sequence of fractions, one for each $N$, each measuring the size of the intersection compared to the size of the set of the first $N$ numbers. So as $N$ gets larger and larger, what you get in the limit (if you do get something meaningful) will measure the size of the entire list $L$ compared to the entire set of natural numbers. In our case the sequence of fractions tends to 0 as $N$ gets larger and larger, reflecting the fact that the list $L$ 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 $N$ numbers is 1/2 if $N$ is even and $(N-1)/2N$ if $N$ is odd. As $N$ 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 $S$ of numbers. The least upper bound of $S$ is the smallest number that is greater than or equal to all the numbers in $S$ (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 $S$ (and it may be equal to minus infinity).

Now suppose you have a sequence of numbers $(a_ n)=a_1$, $a_2$, $a_3$, ... . 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, $a_1$, 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, $a_1$ and $a_2$ 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 $(a_ n).$

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.

Reply

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

By submitting this form, you accept the Mollom privacy policy.