Hi Folks,

    A friend sent me an interesting link and it inspired a question:


*Szemeredi's Theorem*

"The most famous result of Szemeredi is his proof in 1975 in the area of additive number theory of what is now called Szemeredi's theorem. This theorem, Gowers points out, is one of the highlights of 20th century mathematics and also forms the basis of a lot of very recent research. The theorem, which is actually a proof of a decades-old conjecture of Erdos and Pal Turan and has to do with "arithmetic progression", can be simply stated. But Szemeredi's proof of it was both elementary in the above sense and extremely complicated.

From school mathematics one knows what an arithmetic progression is: it is a sequence of numbers with a constant difference between consecutive numbers in the sequence. An arithmetic progression is determined by its length, difference and initial value. For example, the sequence 12, 19, 26, 33, 40, 47 is an arithmetic progression of length 6, difference 7 and initial value 12. The sequence of integers (or a sub-sequence of it) is also an arithmetic progression with difference 1. In 1921, Pierre Joseph Henry Baudet, a Dutch mathematician, conjectured the following: _" If one divides the natural numbers 1, 2, 3,... ad infinitum into a certain random number of boxes, then there is always at least one box which contains an arithmetic progression of arbitrary length."_

The conjecture was proved in 1927 by another Dutch mathematician, Bartel Leendert van der Waerden. The Erdos-Turan Conjecture is actually a stronger version of this. The theorem is best described in lay terms as a one-player game, as Gowers did in his presentation. Suppose one is asked to choose as many numbers between 1 and 10,000 as one can but ensuring that from the numbers chosen one cannot construct an arithmetic progression of length 5. Suppose the numbers chosen included 96, 239, 382, 525 and 668, one would have lost the game because this is 5-term arithmetic progression with difference 143. One will, of course, eventually lose this game because if one keeps going like this for long enough one would have chosen all the numbers between 1 and 10,000 which will include many 5-term arithmetic progressions.

But Szemeredi's theorem makes a stronger statement. Even if one employed the best strategy to avoid a 5-term progression, one would lose long before one got anywhere close to choosing the entire set. In more precise mathematical language, if k is the length of the progression that one is trying to avoid and n is the size of the set of numbers, which is large, the largest number of numbers one can choose without including any k-term progression is a very small fraction of n. The point of the theorem is that, for a given k, there is always some n (which may be huge but it exists) such that if we played the game with n numbers, we will lose by the time we have chosen a tiny fraction of them. Another way of understanding this simply is by colouring natural numbers using only two colours, say red and blue. However, we choose to colour the numbers, it will be seen that a 3-term arithmetic progression can be avoided only up to 8 consecutive integers. A natural number sequence of length 8, coloured as RBRBBRBR for example, does not have a 3-term progression with the same colour. But already with 9 integers, a 3-term progression becomes inevitable."


Given this explanation: If a string of natural numbers is equivalent to a arithmetic progression and is of arbitrary length, does it then follow that all possible strings exist and that at least one is equivalent to a UTM having some particular output?



"I have sworn upon the altar of God, eternal hostility against every form of tyranny 
over the mind of man."
  --  Thomas Jefferson

You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to