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.

## Comments

## Arithmetic progression

"27, 54, 104, 208" huh?

## Oops how embarrassing! Fixed

Oops how embarrassing! Fixed now!

## 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.

## 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).