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