A friend sent me an interesting link and it inspired a question:
"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 firstname.lastname@example.org.
To unsubscribe from this group, send email to
For more options, visit this group at