GILA 1: van der Waerden and all that

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.

Remember, the assertion we’re trying to prove is the following:

van der Waerden’s theorem (finitary version). For each c, k > 0, there exists an integer N(c, k) such that, if \{1, 2, \ldots, N(c, k)\} is colored with c colors, there is a (nontrivial) k-term arithmetic progression all of whose terms are the same color.

This can be seen to be equivalent to the infinitary version stated earlier in the post, by what Terry Tao calls the Arzela-Ascoli trick. The key is to proceed by induction on k; fix some k and assume the theorem for k_0 < k and any c as our inductive hypothesis. (As a base case, we can take k = 2, where the theorem follows immediately from the pigeonhole principle with N(c, 2) = c+1.)

The proof works by repeatedly considering “blocks” of integers and finding shorter arithmetic progressions in those blocks. For concreteness, we’ll take k = 5, c = 4; then we consider “blocks” of size 2N(4, 4), so that the first half of each block contains a monochromatic AP of length 4. (So, in particular, we can extend this AP to a length-5 AP within the block, although this AP isn’t guaranteed to be monochromatic.) We color two blocks the same if they’re colored the same pointwise; this induces a coloring with c_1 = 4^{2N(4,4)} colors on the integers. By the inductive hypothesis, then, there’s a 4-AP of blocks within the first N(4, c_1) blocks. We consider “meta-blocks” of size 2N(4, c_1), so that we can extend this AP to a length-5 AP, which again is not guaranteed to be monochromatic. In addition, the 4 blocks in this AP each must contain a length-4 monochromatic AP in the same relative position, which can be extended to a (not necessarily monochromatic) 4-. We continue this process until we get “meta-meta-…-meta-blocks,” with 3 (in general, c-1) “meta”s.

Now we introduce the following notation: P_{i, j, k, l} denotes the l-th element (of the AP) in the k-th block (of the AP of blocks) in the j-th meta-block (in the AP of meta-blocks) in the i-th meta-meta-block (in the AP of meta-meta-blocks). Now consider the five (in general, c+1) elements:

P_{1,1,1,1}, P_{1,1,1,5}, P_{1,1,5,5}, P_{1,5,5,5}, P_{5,5,5,5}.

By the pigeonhole principle, two of these elements must have the same color. For illustrative purposes, let’s suppose that they’re the second and fourth. Then it’s routine to check that

P_{1, 1,1,5}, P_{1,2,2,5}, P_{1,3,3,5}, P_{1,4,4,5}, P_{1,5,5,5}

is a monochromatic AP of length 5, and we’re done.

Essentially, what we do is circumvent the fact that we can’t ensure that the continuation of a short AP is monochromatic by using the pigeonhole principle to show that there exists a continuation that is monochromatic. (An aside: The above argument is exceedingly simple and beautiful, but it gives terrible bounds — they aren’t even primitive recursive! Saharon Shelah succeeded around 1987 in establishing a primitive recursive bound by a shockingly elementary argument, but the details don’t seem to be online — you can find Shelah’s proof in Jukna’s book and in GRS.)

So, can we modify this argument to obtain a proof of Szemeredi’s theorem, or Roth’s theorem at the very least? Well, the base case is fine, as long as we’re using Schnirelmann density and not naive asymptotic density. And, in fact, the whole iterated “blocking” construction goes through. But the argument falls apart once we get to the last step, where we apply the pigeonhole principle; we can’t be assured that an arbitrary \delta^{-1} elements chosen from a set of size >> \delta^{-1} will contain even one marked element, much less the two that we’d need! And any attempt to fix up the iterative argument will similarly fail, since we’re sampling too few elements to be able to talk about the density of the whole set.

(A second, more important, aside: Note that, if we consider our set to be “random,” then we can in fact fix the argument so that it works with high probability. If we could somehow show that the failure of our set to be sufficiently “random” would impose enough extra structure to find a long AP by some other method, this could work. This is an important observation to keep in the back of our minds as we move along, although it’s currently not at all clear how to make it work.)

So it’s a reasonably well-known bit of combinatorial folklore that the Cauchy-Schwarz inequality can be viewed as a “scaled-up,” quantitative version of the pigeonhole principle. So can we use Cauchy-Schwarz instead? Well, no, and for essentially the same reason: we just don’t have enough data to get good bounds on the density of the whole set from statistics about the elements that the van der Waerden construction gives us.

At this point, it’s probably reasonable to come to the conclusion that a simple modification of the direct combinatorial argument isn’t going to work. Fortunately for us, we have another trick up our sleeve, which the above aside about how a “random enough” set would let us use the vdW argument should have brought to mind. Let’s see if we can apply the probabilistic method.

The next post in the series should be up by the middle of next week.

Advertisements

Tags: , , , , ,

One Response to “GILA 1: van der Waerden and all that”

  1. GILA 2: The probabilistic approach « Portrait of the Mathematician Says:

    […] Portrait of the Mathematician Uninformed opinions on math and more « GILA 1: van der Waerden and all that […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: