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

## Advertising

http://www.flonnet.com/stories/20120420290709800.htm *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?`

-- Onward! Stephen "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 everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.