The Abel Prize 2012

by Marianne Freiberger

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.

Comments

Tenth Person is not equal Tenth Abel Prize

Szemerédi wins the 10th Abel prize, but he is the 12th person to receive the Abel Prize (after Serre, Atiyah, Singer, Lax, Carleson, Srinivasa Varadhan, Thompson, Tits, Gromov, Tate and Milnor).

Arithmetic progression

"27, 54, 104, 208" huh?

Endre Application in manufacturing Technology

1. Endre arithmetic progression can be use as fraction index of compound and differential indexing in gear teeth cutting and will act as future computer using maglev operations in crank rotations using stepper motor technics will revolutionize CNC machines technology relevant to manufacturing technology.Thank you for the prize award which inspired me very much.
With a piezo electric technics we could be able to achieve any combinatorial outputs.
I would like to add my grain of salt to the ongoing discussion on Gowers’s idea that computers may eventually replace mathematicians in some future. I don’t know what computers will be in the future and they may be able to do miraculous things, as in science fiction. I love science fiction, but I do not want to discuss it here. I do not want to speculate about quantum computing either. I assume that future computers will remain Von Neuman machines for a long time to come. They will be faster, have a bigger memory and they will be programmed differently.
Experience shows that mathematical thinking is depending on the alternation of two kinds of activities. One is about developing a mental picture of the problem, an intuition of its nature. The other is about making a calculation, as in algebra or formal logic. The two activities are performed alternatively as in a dance. A calculation is guided by an intuition, and the intuition is confirmed or rejected by a calculation. Few mathematical progresses can be made by using intuitions or calculations alone. Computers are very good at computing and they can help us doing mathematics, like a pen and a piece of paper. But they have no intuition, no consciousness. They are mindless mechanical machines.
I claim that we do not understand the nature of consciousness. Of course, we are making progress in studying the brain. But artificial intelligence seems to show that the brain does not need to be conscious to perform its tasks. So why the brain should produces consciousness? Consciousness is the blind spot of modern science. This I don’t agree.
Consciousness of the brain is required to find out what is correct and what is wrong to let others live in happiness, which the artificial intelligence is lacking. Mainly we live on love and affection. This includes ESP powers and intuition required. Here enters the ashtama syddhis to make things out of nothing, the consciousness that makes things to be produced attaining everything by acoustic mantras which can be injected into computer partially as an experiment. Being consciousness brings out evolution of an evolution for higher thinking and achievement to attain the tranquility and happiness which should be the ultimate goal of happiness to merge with Nature god
The Atman carry the evolutionary information afterdeath. .Any handycaps of human beings is also carried with the Atman as information. A man having a paralyzed leg as they enter into a body as a medium produces paralytic symptoms as medium entry; all these experiences can not be got by artificial intelligence.
Sankaravelyudhan Nandakumar,Assistant Professor, R&D Wing Pneumatics and Hydraulics,MET Engineering College.Hubble Space research center member,Retired Chief Engineer,Thermal power plant.

Oops how embarrassing! Fixed

Oops how embarrassing! Fixed now!