— 1. Introduction —
Van der Waerden’s theorem (to which I gave two proofs in previous posts on this blog) states that if one colors the positive integers with finitely many colors, then one can always find a monochromatic arithmetic progression of arbitrary length.
It is not too hard to show that this result is equivalent to the following:
Proof: Let and notice that covers all of (here, as usual, we use the convention that whenever is a set and and integer). Thus by the van der Waerden theorem one of the shifts contains arbitrarily long arithmetic progressions. Since a shift of an arithmetic progression is still an arithmetic progression we conclude that contains arbitrarily long arithmetic progressions.
The proof that Theorem 1 implies van der Waerden’s theorem is a little bit more complicated and I will omit it. Now there are many ways in which one can extend this theorem. The most well known extension is Szemerédi’s theorem, which states that a set with positive upper density contains arbitrarily long arithmetic progressions. Recall that the upper density of a set is defined as
Since in a finite coloring of one of the colors must have positive density, it follows that van der Waerden’s theorem is an easy corollary of Szemerédi’s theorem. Another way to see this is to reformulate Szemerédi’s theorem:
Theorem 2 Let be an increasing sequence of positive integers such that
Then contains arbitrarily long arithmetic progressions.
This means that if the averaged difference between consecutive terms of the sequence is uniformly bounded, then contains arbitrarily long arithmetic progressions. Of course the sum in this formulation is telescopic, but below it will be clear why I formulated the result this way.
Other extensions include multidimensional extensions. For instance, we have the multidimensional Szemerédi theorem (due to Furstenberg and Katznelson) which we formulate here for 2 dimensions.
Theorem 3 Let be such that
Then for every there exists and such that .
Another direction in which one can move to higher dimensions is the following: Let be a sequence in such that
then does contain arbitrarily long arithmetic progressions? And what if impose the stronger condition that for some fixed and every ? It turns out that the answer is negative, although this is not at all obvious. The counterexample works for and is due to Justin (see this paper), and an easier construction was found by Dekking, with no four terms in an arithmetic progression.
The next question is whether one can obtain arbitrarily many collinear points. The answer is true and is due to Pomerance.
Then has arbitrarily many collinear points.
To see why one can not ask for infinitely many collinear points, consider a sequence which roughly follows the path of a parabola.
In this scenario, the analog of van der Waerden’s theorem was discovered by Ramsey and Gerver:
Theorem 5 Let be a sequence in and assume that there exists such that for all . Then has arbitrarily many collinear points.
As a corollary of Theorem 4 we get:
Corollary 6 Let be a sequence of positive integers such that the set has positive density. Then for every there are collinear points of the .
Proof: Let . Then
The result now follows directly from Theorem 4
Another related result of Pomerance says that the conclusion of this corollary remains true when one replaces with the set of prime numbers (the analogous extension of Szemerédi’s theorem is the famous Green-Tao theorem). In the rest of this post I will outline Pomerance’s proof of theorem 4
— 2. Proof of Pomerance’s theorem —
To prove theorem 4 it is more convenient to work with finite sequences. We will use to denote the length of the sequence and hence we work with sequences of the form . We denote
to be the average step of this finite sequence. We will fix and we prove the result for each separately. Thus, from now on we will omit any reference to in the notation. We define to be the set of sequences of length without collinear points. By we denote the minimum average step a sequence of length can have an still avoid collinear points. Also let be the minimum average step an arbitrarily long sequence can have and still avoid collinear points.
The theorem is equivalent to say that . Assume, for the sake of contradiction that it is finite. Thus for each and let
denote the sequences of length without collinear points which have average step close to the minimum possible . We will consider sequences as stretched as possible, and among those we will consider the sequences as steep as possible. Then for such sequences it turns out that most points belong to a thin rectangle around the line connecting and , which allow us to deduce the result from a pigeonhole principle argument.
Let be the average length of (counting cancelations), let be the maximum average length of a sequence in (or if is empty), let the maximum average length of arbitrarily long sequences in and let be the maximal average length of arbitrarily long sequences without collinear points which have average step arbitrarily close to the minimum possible .
Let be the set of sequences of length with average step very close to the minimum possible and average length very close to the maximum possible . Let denote the line segment connecting and and let
where is the usual metric in , denote the maximum distance between a point from the middle half of the sequence and the segment , normalized by the length of .
Lemma 7 For every there exists and such that for every and we have .
Now let , let denote the slope of (and make if is vertical or degenerates to a point). Let be the maximum slope of a sequence in (or if is empty), let the maximum slope of arbitrarily long sequences in and let .
We will now give a proof of Theorem 4 using this lemma.
Proof: Let be sequences of positive integers, with and such that
Such sequences exist by Dirichlet approximation theorem. Apply Lemma 8 with and let (with ) and be given by the lemma, so that . Now let be the set of lines with slope which contain lattice points and pass within of the segment . Since we deduce that the union of the lines in contains points of .
Thus if then the (absolute value of) the coordinate of the intersection of with the -axis (in other words, the -intersect of ) is no bigger than
Using (1) (and observing that and hence ) we can now bound that distance by
Since two lines with the same slope and the same -intersect are the same, we conclude that
It follows from the pigeonhole principle that at least one of the lines in contains at least
and since we will eventually have more than collinear points from