From: Fred Galvin
Subject: Re: Van Der Waerden numbers?
Date: Tue, 7 Dec 1999 17:21:01 -0600
Newsgroups: sci.math
Keywords: partitions of consecutive numbers contain arithmetic progressions
On Tue, 7 Dec 1999, Achava Nakhash, the Loving Snake wrote:
> I have recently gotten hold of a wonderful book called "Three
> Pearls of Number Theory" by Khinchin. For those who don't know of this
> book, it contains a proof of Van Der Waerden's theorem about arithmitic
> progressions in finite partitions of the integers, a proof that the
> Schnirelmann density of the sum of two sequences of the type
> Schnirelmann cared about is greater than or equal to the sum of the
> Schnirelmann density of each sequence as long as that sum is less than
> or equal to 1, and a proof of the Waring conjecture that for every n
> there is a k such that every positive whole number is a sum of at most k
> n'th powers. None of these proofs requires any technical baggage at
> all. They are all about incredible cleverness, mathematical induction,
> and the pigeon-hole principle (schubfachschluss, whatever).
> Along the way to proving the Van Der Waerden theorem, we see that
> the big VDW actually showed that for any k and l (suitably restricted)
> there is an n(k, l) such that given a sequence of consecutive integers
> of at least length n(k, l) and any partition of this sequence into k or
> fewer components, at least one of the components contains an arithmetic
> progression of length l. This leads immediately to the usual statement
> that any finite partition of the integers contains arbitrarily long
> arithmetic progressions in at least one of the components.
> So what is my question already? We have a whole zoo of researchers
> attempting to figure out Ramsey numbers, also called party numbers,
> etc. Why does Ramsey get all the press, all the acclaim, all the
> activity? Has anybody researched the Van Der Waerden numbers n(k, l)?
> Inquiring minds want to know. So would I.
Yes, they sure have researched the Van der Waerden numbers. Not as much as
Ramsey numbers, because Van der Waerden numbers are harder and grow
faster. Recommended reading: Ronald L. Graham, Bruce L. Rothschild, and
Joel H. Spencer, _Ramsey Theory_, SECOND EDITION, Wiley, 1990, ISBN
0-471-50046-1. The main difference between the first and second editions
is in the discussion of Van der Waerden numbers: the second edition
includes Shelah's proof of Van der Waerden's theorem, which is both
stronger (gives better upper bounds on the numbers) and simpler than the
old proof which you read in Khinchin's book.
==============================================================================
From: Simon Kristensen
Subject: Re: Van Der Waerden numbers?
Date: 08 Dec 1999 11:08:23 +0100
Newsgroups: sci.math
Fred Galvin writes:
[previous article quoted in full --djr]
Also, Van der Waerdens Theorem was generalized by E. Szemeredi to a
density version: Given an integer k and a delta>0 there exists an N =
N(k, delta) such that any subset of {1, ...,N} of cardinality at least
delta N contains an arithmetic progression of length k.
It's an easy exercise to see that this result implies Van der Waerdens
theorem. Some work has gone into finding a bound on N in this
case. For some recent results, you might want to look at
Gowers, W. T.: A new proof of Szemerédi's theorem for arithmetic
progressions of length four. Geom. Funct. Anal. 8 (1998), no. 3,
529--551.
Or another paper by Gowers available on
http://www.mathematik.uni-bielefeld.de/documenta/xvol-icm/Fields/Fields.html
Best regards,
Simon Kristensen
--
Simon Kristensen; Residence Universitaire Les Flamboyants;
Studio no. 268; 8, rue Jean-Henri Schnitzler;
67000 Strasbourg; France;
e-mail: simonkr@iname.com