In this post I talk about (and prove) a fundamental theorem of Rado in Ramsey’s theory. I will prove “half” of the theorem and will postpone the second part of the proof to a future post.
To better appreciate Rado’s theorem, I will start by listing some of it’s consequences:
Theorem (Schur’s theorem) For any
and any function
(as usual we will take
) there exist
such that
.
Equivalently, for any finite coloring of
there exists a monochromatic solution to the equation
.
Theorem (van der Waerden’s theorem) For any
and any function
there exist
such that
.
Equivalently, for any finite coloring of
there exists a monochromatic solution to the system
for
.
A common generalization of the two above theorems is Brauer’s theorem:
Theorem 1 (Brauer’s theorem) For any
and any function
there exist
such that
.
Equivalently, for any finite coloring of
there exists a monochromatic solution to the system
for
.
Another consequence of Rado’s theorem is the following result, sometimes called Folkman’s theorem, which contains Schur’s theorem as a special case when :
Theorem (Folkman’s theorem)For any
and any function
there exist
and a color
such that
While it’s not as immediate as the previous theorems, one can also formulate Folkman’s theorem in the form “For any finite coloring of there exists a monochromatic solution to the system
“. To see that, let
be the number of subsets of
with at least two elements. Take
to be the
matrix which contains in each line the indicator function of a subset
with
. Then let
where
is the
identity matrix. Finally let
be the
concatenation of
with
. For instance, when
we get
More generally, given an homogeneous system of linear equations , where
,
and
is a
matrix with integer coefficients, one can ask whether for any finite coloring of
there exists a vector
with all coordinates in one color and such that
. The answer is provided by Rado’s theorem.
— 1. Rado’s theorem —
We first need a definition:
Definition 2 Let
, let
be a
matrix with integer coefficients and let
be the columns of
. We say that
satisfies the columns condition if, possibly after a permutation of the columns, there exist
and integers
such that for every
, the sum
is in the linear span (over
) of the set
(with the understanding that the only vector in the linear span of the empty set is
).
Theorem 3 (Rado) Let
be a matrix with integer coefficients. The following are equivalent:
- (a) For every finite coloring of
there exists a monochromatic solution to the system
.
- (b)
satisfies the columns condition.
Not only Rado’s theorem contains any previously know linear partition theorem, it classifies all such results. Thus, for instance, we know that for some coloring there is no monochromatic solution to the equation . We now give the proof of the implication (a)
(b), following this book. First we need a lemma on linear algebra:
Lemma 4 Let
and let
such that
is not a linear combination (over
) of the (possibly empty) set
. Then there exists a finite set of primes
such that for any prime
and any
the vector
is not a linear combination of
![]()
.
Proof: Let be such that
for all
but such that
(such
exists because
is not in the linear span of
). Multiplying
by the common denominator of its entries if necessary we can assume that actually
. Let
be the set of primes that divide
.
Now let be a prime for which there exists some
such that
is a linear combination of
. Then we can find
such that
Taking the inner product with we deduce that
This implies that indeed .
We can now prove the implication (a)(b) of Theorem 3:
Proof: Let be a matrix which satisfies (a), let
be the columns of
. For any two disjoint subsets
for which
is nonempty, either
is a linear combination of
(over
) or we can apply Lemma 4 to find a finite set
of primes satisfying the conclusion of that lemma. Let
be the (finite) union of all
. Take any prime number
.
Let be the canonical projection and consider the coloring
defined recursively by
Let be a monochromatic solution to
. Thus there exists some
such that
for all
and some
. Let
be the cardinality of the set
. After reordering the columns of
, if necessary, we can find
such that
for some . Now let
. We need to prove that
is in the linear span (over
) of the set
. We have
and so
where is such that
(it exists because
is coprime to
and hence to
).
Since , it follows from the definition of
that the previous display implies that indeed
is in the linear span (over
) of the set
and this finishes the proof.
Definition 5 A set
is called rich if for every
and every
matrix
which satisfies the columns condition there exists a vector
such that
.
It follows from Rado’s theorem (it is in fact equivalent to the implication (b)(a) of Theorem 3) that for any finite partition (coloring) of
one of the cells is rich. Rado asked whether for any finite partition of a rich set, one of the cells is rich. This conjecture was finally settle by Rado’s student Deuber. In his work, Deuber gave a new proof of Rado’s Theorem, and in fact a new formulation.
— 2. Deuber’s Theorem —
For each of the first four theorems stated in this post (Schur, van der Waerden, Brauer and Folkman) I presented two (equivalent) formulations. The second formulation in each case uses the language of systems of equations, so it fits more directly with Rado’s theorem language, but for those applications it is more natural to work directly with the configurations, as in the first formulation of each theorem (for instance it takes a few seconds to recognize a solution of the system for
as an arithmetic progression).
Deuber’s idea was to use the more intuitive description of the configurations present in the first formulation of each theorem above. With this in mind he gave the following definition:
Definition 6 Let
and let
. For each
, the
-set generated by
is the set
Deuber’s main result was the following:
Theorem 7 Let
. Then there exist
such that for any finite partition of a
-set there exists a monochromatic subset which is an
-set.
The relation between -sets and Rado’s theorem is the following:
- For every
and any
matrix
satisfying the columns condition there exist
such that for any
-set
there exists
such that
.
- For every
there exist
and a
matrix
satisfying the columns condition such that for any
with
there exists an
-set contained in
.
This proposition implies that a set is rich if and only if for every
there exists an
-set contained in
. Thus Theorem 7 implies that a finite partition of a rich set is still rich, as conjectured by Rado. Moreover, Deuber’s theorem implies the direction (b)
(a) of Theorem 3. I will give a proof of Deuber’s theorem (and hence of the remainder of Rado’s theorem) in a future post.
Proof:
- Let
and let
be a
matrix with integer entries satisfying the columns condition. Let
be the columns of
and let
and
and for every
we have
Thus there exist a common denominator
, so that
for all
. Next let, for
Then if
is the
matrix with entries
we have
. In particular, for any
, if we let
, then
.
Finally, take
to be the maximum of
and let
be arbitrary. We claim that the entries of
are contained in the
-set
, and this will finish the proof. Indeed, let
and find
such that
. Then the
-th entry of
is
and since
this proves the claim and finishes the proof.
- Let
be arbitrary. For each
and each of choice
consider the vector
Observe that, for a given
, the Deuber set
can be written as
Now let
be the matrix with
columns and lines
; observe that the entries of
are exactly the elements of
. The number of lines in
is
Next let
where
is the
identity matrix and let
be the
concatenation of
and
. Let
be such that
, write
and let
and
. We can rewrite
as
which is then equivalent to
. A short induction now shows that each
must be a multiple of
, so we can write
for some
. Therefore, we conclude that
, so the entries of
contain and
-set.
Finally we need to show that
satisfies the columns condition. But according to Theorem 7, for any finite partition of
there exists
such that
is monochromatic. Taking
and
we deduce that
. Since
for each
we conclude that all the entries of
are monochromatic. This shows that for any finite coloring of
there exists
with all entries in the same color such that
. By Theorem 3 this implies that
satisfies the columns condition, as desired.
Pingback: A proof of Deuber’s theorem using Hales-Jewett | I Can't Believe It's Not Random!
Pingback: New polynomial and multidimensional extensions of classical partition results | I Can't Believe It's Not Random!