Posts Tagged ‘van der Waerden’

GILA 1: van der Waerden and all that

August 22, 2009

I’m beginning my GILA series announced on Thursday with a short exposition of van der Waerden’s theorem, and an attempt to extend its proof to the density version (at least in the k=3 case). Before I start, I should mention something I neglected in the last post: that this series is as much for my benefit as for that of any “interested lay audience” out there. Someone like Terry Tao could undoubtedly do a better series of this type (and, indeed, I’ll be leaning heavily on my borrowed copy of Tao and Van Vu’s Additive Combinatorics throughout) but they haven’t, so I’ll try. However, there are certain to be a number of embarrassing mistakes, unjustified statements, lines of thinking left unresolved, etc., throughout (indeed, an anonymous commenter noted two in the introductory post!), and I encourage readers to point them out in the comments.

So, on to van der Waerden’s theorem. van der Waerden’s theorem is one of the early jewels of Ramsey theory (actually predating Ramsey’s article by a couple of years) and can be viewed as a weaker version of Szemeredi’s theorem. It states simply that, for any integers c, k > 0, if you color the positive integers with c colors, then there exists a monochromatic k-term arithmetic progression.

Khinchin, in his wonderful book which unfortunately appears to be out of print (at least in English), gives some history of the problem:

All to whom this question [the theorem in the c = 2 case] was put regarded the problem at first sight as quite simple; its solution in the affirmative appeared to be almost self-evident. The first attempts to solve it, however, led to nought… [T]his problem, provoking in its resistance, soon became the object of general mathematical interest… I made [van der Waerden’s] acquaintance, and learned the solution from him personally. It was elementary, but not simple by any means. The problem turned out to be deep; the appearance of simplicity was deceptive.

This last clause is particularly wonderful, describing as it does not only van der Waerden’s theorem but Ramsey theory and perhaps even combinatorics in general.

The usual proof (given in story-form by Zeilberger here) is not van der Waerden’s, however, but comes from Khinchin, attributed by him to a M.A. Lukomskaya in Minsk. It is a masterpiece, using nothing but a very clever inductive argument and some application of the pigeonhole principle. For the sake of self-containedness, I’ll sketch the argument below the fold.