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 2Let , let be a matrix with integer coefficients and let be the columns of . We say that satisfies thecolumns conditionif, possibly after a permutation of the columns, there exist and integers such that for every , the sumis 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 4Let 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 5A set is calledrichif 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 6Let and let . For each , the-set generated byis the set

Deuber’s main result was the following:

Theorem 7Let . 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!