5Sums and products*
III Ramsey Theory
5 Sums and products*
The goal of this final (non-examinable) chapter is to prove the following theorem:
Theorem
(Moreira, 2016)
.
If
N
is
k
-coloured, then there exists infinitely many
x, y such that {x, x + y, xy} is monochromatic.
This is a rather hard theorem, but the proof is completely elementary, and
just involves a very clever use of van der Waerden’s theorem. One of the main
ideas is to consider syndetic sets.
Definition
(Syndetic set)
.
We say
A
=
{a
1
< a
2
< ···} ⊆ N
is syndetic if it
has bounded gaps, i.e. a
i+1
− a
i
< b for all i.
It turns out these sets contain a lot of structure. What happens when we
finitely colour a syndetic set? Are we guaranteed to have a monochromatic
syndetic set? Let’s take the simplest syndetic set —
N
. Let’s say we 2-colour
N
.
Does one of the classes have to by syndetic? Of course not. For example, we
can look at this:
···
But this set obviously has some very nice structure. So we are motivated to
consider the following definition:
Definition
(Piecewise syndetic set)
.
We say
A ⊆ N
is piecewise syndetic if there
exists b > 0 such that A has gaps bounded by b on arbitrarily long intervals.
More explicitly, if we again write
A
=
{a
1
< a
2
< ···}
, then there exists
b
such that for all
N >
0, there is
i ∈ N
such that
a
k+1
−a
k
< b
for
k
=
i, ··· , i
+
N
.
We begin with two propositions which are standard results.
Proposition.
If
A
is piecewise syndetic and
A
=
X ∪ Y
, then one of
X
and
Y
is piecewise syndetic.
Proof.
We fix
b >
0 and the sequence of intervals
I
1
, I
2
, ···
with
|I
n
| ≥ n
such
that A has gaps ≤ b in each I
n
. We may, of course, wlog I
n
are disjoint.
Each element in
I
n
is either in
X
or not. We let
t
n
denote the largest
number of consecutive things in
I
n
that are in
X
. If
t
n
is unbounded, then
X
is
piecewise syndetic. If
t
n
≤ K
, then
Y
is piecewise syndetic, with gaps bounded
by (K + 1)b.
Of course, this can be iterated to any finite partition. There is nothing clever
so far.
Our next proposition is going to be a re-statement of van der Waerden’s
theorem in the world of piecewise syndetic sets.
Proposition.
Let
A ⊆ N
be piecewise syndetic. Then for all
m ∈ N
, there
exists d ∈ N such that the set
A
∗
= {x ∈ N : x, x + d, ··· , x + md ∈ A}.
is piecewise syndetic.
Proof.
Let’s in fact assume that
A
is syndetic, with gaps bounded by
b
. The
proof for a piecewise syndetic set is similar, but we have to pass to longer and
longer intervals, and then piece them back together.
We want to apply van der Waerden’s theorem. By definition,
N = A ∪ (A + 1) ∪ ··· ∪ (A + b).
Let c : N → {0, ··· , b} by given by
c(x) = min{i : x ∈ A + i}.
Then by van der Waerden, we can find some a
1
, d
1
such that
a
1
, a
1
+ d
1
, ··· , a
1
+ md
1
∈ A + i.
Of course, this is equivalent to
(a
1
− i), (a
1
+ i) + d
1
, ··· , (a
1
− i) + md
1
∈ A.
So we wlog i = 0.
But van der Waerden doesn’t require the whole set of
N
. We can split
N
into
huge blocks of size
W
(
m
+ 1
, b
+ 1), and then we run the same argument in each
of these blocks. So we find (a
1
, d
1
), (a
2
, d
2
), ··· such that
a
i
, a
i
+ d
i
, ··· , a
i
+ md
i
∈ A.
Moreover,
˜
A
=
{a
1
, a
2
, ···}
is syndetic with gaps bounded by
W
(
m
+ 1
, b
+ 1).
But we need a fixed d that works for everything.
We now observe that by construction, we must have
d
i
≤ W
(
m
+ 1
, b
+ 1)
for all
i
. So this induces a finite colouring on the
a
i
, where the colour of
a
i
is
just
d
i
. Now we are done by the previous proposition, which tells us one of the
partitions must be piecewise syndetic.
That was the preliminary work we had to do to prove the theorem. The
proof will look very magical, and things only start to make sense as we reach the
end. This is not a deficiency of the proof. There is some reason this problem
was open for more than 40 years.
The original proof (arxiv:1605.01469) is a bit less magical, and used concepts
from topological dynamics. Interested people can find the original paper to read.
However, we will sacrifice “deep understanding” for having a more elementary
proof that just uses van der Waerden.
Proof of theorem. Let N = C
1
∪ ··· ∪ C
r
. We build the following sequences:
(i) y
1
, y
2
, ··· ∈ N;
(ii) B
0
, B
1
, ··· and D
1
, D
2
, ··· which are piecewise syndetic sets;
(iii) t
0
, t
1
, ··· ∈ [r] which are colours.
We will pick these such that B
i
⊆ C
t
i
.
We first observe that one of the colour classes
C
i
is piecewise syndetic. We
pick
t
0
∈
[
r
] be such that
C
t
0
is piecewise syndetic, and pick
B
0
=
C
t
0
. We want
to apply the previous proposition to obtain
D
0
from
B
0
. We pick
m
= 2, and
then we can find a y
1
such that
D
1
= {z | z, z + y
1
∈ B
0
}
is piecewise syndetic.
We now want to get
B
1
. We notice that
y
1
D
1
is also piecewise syndetic, just
with a bigger gap. So there is a colour class
t
1
∈
[
r
] such that
y
1
D
1
∩ C
t
1
is
piecewise syndetic, and we let B
1
= y
1
D
1
∩ C
t
1
.
In general, having constructed
y
1
, ··· , y
i−1
;
B
0
, ··· , B
i−1
;
D
1
, ··· , D
i−1
and
t
0
, . . . , t
i−1
, we proceed in the following magical way:
We apply the previous proposition with the really large
m
=
y
2
1
y
2
2
···y
2
i−1
to
find y
i
∈ N such that the set
D
i
= {z | z, z + y
i
, ··· , z + (y
2
1
y
2
2
···y
2
i−1
)y
i
∈ B
i−1
}
is piecewise syndetic. The main thing is that we are not using all points in this
progression, but are just using some important points in there. In particular, we
use the fact that
z, z + y
i
, z + (y
2
j
···y
2
i−1
)y
i
∈ B
i−1
for all 1 ≤ j ≤ i − 1. It turns out these squares are important.
We have now picked
y
i
and
D
i
, but we still have to pick
B
i
. But this is just
the same as what we did. We know that
y
i
D
i
is piecewise syndetic. So we know
there is some t
i
∈ [r] such that B
i
= y
i
D
i
∩ C
t
i
is piecewise syndetic.
Let’s write down some properties of these
B
i
’s. Clearly,
B
i
⊆ C
t
i
, but we
can say much more. We know that
B
i
⊆ y
i
B
i−1
⊆ ··· ⊆ y
i
y
i−1
···y
j+1
B
j
.
Of course, there exists some t
j
, t
i
with j < i such that t
j
= t
i
. We set
y = y
i
y
i−1
···y
j+1
.
Let’s choose any z ∈ B
i
. Then we can find some x ∈ B
j
such that
z = xy,
We want to check that this gives us what we want. By construction, we have
x ∈ B
j
⊆ C
t
i
, xy = z ∈ B
i
⊆ C
t
i
.
So they have the same colour.
How do we figure out the colour of x + y? Consider
y(x + y) = z + y
2
∈ y
i
D
i
+ y
2
.
By definition, if a ∈ D
i
, then we know
a + (y
2
j+1
···y
2
i−1
)y
i
∈ B
i−1
.
So we have
D
i
⊆ B
i−1
− (y
2
j+1
···y
2
i+1
)y
i
⊆ y
j+1
···y
i−1
B
j
− (y
2
j+1
···y
2
i−1
)y
i
So it follows that
y(x + y) ⊆ y
i
(y
i−1
···y
j+1
)B
j
− y
2
+ y
2
= yB
j
.
So x + y ∈ B
j
⊆ C
t
j
= C
t
i
. So {x, x + y, xy} have the same colour.