— 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:
Theorem 1 Let
be an increasing sequence of positive integers such that for all
we have
for some fixed
. Then the set
contains arbitrarily long arithmetic progressions.
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.
Theorem 4 (Pomerance’s theorem) Let
be a sequence in
such that
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
.
Lemma 8 For every
there exists
such that if
then there exists some
such that
.
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
.
To finish the proof we just need to count how many lines belong to . Assume without loss of generality that the first point of
,
. Observe that the slopes of the lines in
and that of
differ by
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
Pingback: Large subsets of discrete hypersurfaces in Z^d contain arbitrarily many collinear points | I Can't Believe It's Not Random!