Rado’s theorem and Deuber’s theorem

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 ${r\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ (as usual we will take ${[r]=\{1,\dots,r\}}$ ) there exist ${x,y\in{\mathbb N}}$ such that ${\chi(x)=\chi(y)=\chi(x+y)}$ .

Equivalently, for any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the equation ${x+y=z}$ .

Theorem (van der Waerden’s theorem) For any ${r,k\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ there exist ${x,y\in{\mathbb N}}$ such that ${\chi(x)=\chi(x+y)=\cdots=\chi(x+ky)}$ .

Equivalently, for any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the system ${x_{i+1}-x_i=x_i-x_{i-1}}$ for ${i=1,\dots,k-1}$ .

A common generalization of the two above theorems is Brauer’s theorem:

Theorem 1 (Brauer’s theorem) For any ${r,k\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ there exist ${x,y\in{\mathbb N}}$ such that ${\chi(x)=\chi(y)=\chi(x+y)=\cdots=\chi(x+ky)}$ .

Equivalently, for any finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the system ${x_{i+1}-x_i=x_0}$ for ${i=1,\dots,k-1}$ .

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 ${k=2}$ :

Theorem (Folkman’s theorem)For any ${r,k\in{\mathbb N}}$ and any function ${\chi:{\mathbb N}\rightarrow[r]}$ there exist ${x_1,\dots,x_k\in{\mathbb N}}$ and a color ${i\in[r]}$ such that

$\displaystyle \chi\left(\sum_{j\in\alpha}x_j\right)=i\qquad\forall\ \emptyset\neq\alpha\subset[k]$

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 ${{\mathbb N}}$ there exists a monochromatic solution to the system ${A\vec x=\vec 0}$ “. To see that, let ${m=2^k-k-1}$ be the number of subsets of ${[k]}$ with at least two elements. Take ${A_1}$ to be the ${m\times k}$ matrix which contains in each line the indicator function of a subset ${\alpha\subset[k]}$ with ${|\alpha|\geq2}$ . Then let ${A_2=-I_m}$ where ${I_m}$ is the ${m\times m}$ identity matrix. Finally let ${A}$ be the ${m\times(k+m)}$ concatenation of ${A_1}$ with ${A_2}$ . For instance, when ${k=3}$ we get

$\displaystyle A=\left[\begin{array}{cccccccc}1&1&0&|&-1&0&0&0\\ 1&0&1&|&0&-1&0&0\\ 0&1&1&|&0&0&-1&0\\ 1&1&1&|&0&0&0&-1\end{array}\right]$

More generally, given an homogeneous system of linear equations ${A\vec x=\vec 0}$ , where ${\vec x\in{\mathbb N}^d}$ , ${\vec 0\in{\mathbb Z}^k}$ and ${A}$ is a ${k\times d}$ matrix with integer coefficients, one can ask whether for any finite coloring of ${{\mathbb N}}$ there exists a vector ${\vec x\in{\mathbb N}^d}$ with all coordinates in one color and such that ${A\vec x=\vec 0}$ . The answer is provided by Rado’s theorem.

— 1. Rado’s theorem —

We first need a definition:

Definition 2 Let ${d,k\in{\mathbb N}}$ , let ${A}$ be a ${k\times d}$ matrix with integer coefficients and let ${c_1,\dots,c_d\in{\mathbb Z}^k}$ be the columns of ${A}$ . We say that ${A}$ satisfies the columns condition if, possibly after a permutation of the columns, there exist ${m\in{\mathbb N}}$ and integers ${0=d_0<d_1<d_2<\cdots<d_m<d_{m+1}=d}$ such that for every ${0\leq j\leq m}$ , the sum

$\displaystyle c_{d_j+1}+c_{d_j+2}+\cdots+c_{d_{j+1}}$

is in the linear span (over ${{\mathbb Q}}$ ) of the set ${\{c_i:i\leq d_j\}}$ (with the understanding that the only vector in the linear span of the empty set is ${\vec0}$ ).

Theorem 3 (Rado) Let ${A}$ be a matrix with integer coefficients. The following are equivalent:

(a) For every finite coloring of ${{\mathbb N}}$ there exists a monochromatic solution to the system ${A\vec x=\vec0}$ .
(b) ${A}$ 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 ${x+y=3z}$ . We now give the proof of the implication (a) ${\Rightarrow}$ (b), following this book. First we need a lemma on linear algebra:

Lemma 4 Let ${j,k\in{\mathbb N}}$ and let ${c_1,\dots,c_j\in{\mathbb Z}^k}$ such that ${c_1}$ is not a linear combination (over ${{\mathbb Q}}$ ) of the (possibly empty) set ${\{c_2,\dots,c_j\}}$ . Then there exists a finite set of primes ${F}$ such that for any prime ${p\notin F}$ and any ${n\in\{0,1,\dots\}}$ the vector ${p^nc_1}$ is not a linear combination of ${c_2,\dots,c_j}$ ${\bmod p^{n+1}}$ .

Proof: Let ${u\in{\mathbb Q}^j}$ be such that ${\langle u,c_i\rangle=0}$ for all ${i=2,3,\dots,j}$ but such that ${\langle u,c_1\rangle\neq0}$ (such ${u}$ exists because ${c_1}$ is not in the linear span of ${c_2,\dots,c_j}$ ). Multiplying ${u}$ by the common denominator of its entries if necessary we can assume that actually ${u\in{\mathbb Z}^j}$ . Let ${F}$ be the set of primes that divide ${\langle u,c_1\rangle}$ .

Now let ${p}$ be a prime for which there exists some ${n\geq0}$ such that ${p^nc_1}$ is a linear combination of ${c_2,\dots,c_j}$ ${\bmod p^{n+1}}$ . Then we can find ${a_2,\dots,a_j\in{\mathbb Z}}$ such that

$\displaystyle p^nc_1=a_2c_2+\cdots+a_jc_j\qquad\mod p^{n+1}$

Taking the inner product with ${u}$ we deduce that

$\displaystyle p^n\langle u,c_1\rangle=a_2\langle u,c_2\rangle+\cdots+a_j\langle u,c_j\rangle=0\qquad\mod p^{n+1}$

This implies that indeed ${p\in F}$ . $\Box$

We can now prove the implication (a) ${\Rightarrow}$ (b) of Theorem 3:

Proof: Let ${A}$ be a matrix which satisfies (a), let ${c_1,\dots,c_d}$ be the columns of ${A}$ . For any two disjoint subsets ${I,J\subset\{c_1,\dots,c_d\}}$ for which ${I}$ is nonempty, either ${\sum_{c\in I}c}$ is a linear combination of ${J}$ (over ${{\mathbb Q}}$ ) or we can apply Lemma 4 to find a finite set ${F_{I,J}}$ of primes satisfying the conclusion of that lemma. Let ${F}$ be the (finite) union of all ${F_{I,J}}$ . Take any prime number ${p\notin F}$ .

Let ${\pi:{\mathbb Z}\rightarrow{\mathbb Z}/(p{\mathbb Z})}$ be the canonical projection and consider the coloring ${\chi_p:{\mathbb N}\rightarrow\{1,\dots,p-1\}}$ defined recursively by

$\displaystyle \chi_p(x)=\left\{\begin{array}{cl}\pi(x)&\text{if }\pi(x)\neq0\\ \pi(x/p)&\text{otherwise}\end{array}\right.$

Let ${\vec x=(x_1,\dots,x_d)\in{\mathbb N}^d}$ be a monochromatic solution to ${A\vec x=\vec0}$ . Thus there exists some ${a\in\{1,\dots,p-1\}}$ such that ${x_i\equiv ap^{n_i}\mod p^{n_i+1}}$ for all ${i}$ and some ${n_i\in\{0,1,\dots\}}$ . Let ${m+1}$ be the cardinality of the set ${\{n_i:i=1,\dots,d\}}$ . After reordering the columns of ${A}$ , if necessary, we can find ${0=d_0<d_1<d_2<\cdots<d_m<d_{m+1}=d}$ such that

$\displaystyle n_i=\left\{\begin{array}{cc}b_0&d_0<i\leq d_1\\b_1&d_1<i\leq d_2\\ \vdots&\vdots\\ b_m&d_m<i\leq d_{m+1}\end{array}\right.$

for some ${b_0<b_1<\cdots<b_m}$ . Now let ${j\in\{0,\dots,m\}}$ . We need to prove that ${c_{d_j+1}+c_{d_j+2}+\cdots+c_{d_{j+1}}}$ is in the linear span (over ${{\mathbb Q}}$ ) of the set ${\{c_i:i\leq d_j\}}$ . We have

$\displaystyle 0=\sum_{i=1}^dx_ic_i\equiv \sum_{i=1}^{d_j}x_ic_i+a p^{b_j}\sum_{i=d_j+1}^{d_{j+1}}c_i\mod p^{b_j+1}$

and so

$\displaystyle p^{b_j}\sum_{i=d_j+1}^{d_{j+1}}c_i\equiv -\tilde a\sum_{i=1}^{d_j}x_ic_i\mod p^{b_j+1}$

where ${\tilde a\in{\mathbb Z}}$ is such that ${a\tilde a\equiv1\bmod p^{b_j+1}}$ (it exists because ${a}$ is coprime to ${p}$ and hence to ${p^{b_j+1}}$ ).

Since ${p\notin F}$ , it follows from the definition of ${F}$ that the previous display implies that indeed ${c_{d_j+1}+c_{d_j+2}+\cdots+c_{d_{j+1}}}$ is in the linear span (over ${{\mathbb Q}}$ ) of the set ${\{c_i:i\leq d_j\}}$ and this finishes the proof. $\Box$

Definition 5 A set ${B\subset{\mathbb N}}$ is called rich if for every ${d,k\in{\mathbb N}}$ and every ${d\times k}$ matrix ${A}$ which satisfies the columns condition there exists a vector ${\vec x\in B^d}$ such that ${A\vec x=\vec0}$ .

It follows from Rado’s theorem (it is in fact equivalent to the implication (b) ${\Rightarrow}$ (a) of Theorem 3) that for any finite partition (coloring) of ${{\mathbb N}}$ 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 ${x_{i+1}-x_i=x_i-x_{i-1}}$ for ${i=1,\dots,k-1}$ 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 ${m,p,c\in{\mathbb N}}$ and let ${F_p=\{-p,-p+1,\dots,p-1,p\}}$ . For each ${\vec s=(s_0,s_1,\dots,s_m)\in{\mathbb N}^{m+1}}$ , the ${(m,p,c)}$ -set generated by ${\vec s}$ is the set

$\displaystyle D(m,p,c;\vec s):=\left\{\begin{array}{lr}cs_0&\\is_0+cs_1,& i\in F_p\\i_0s_0+i_1s_1+cs_2,& i_0,i_1\in F_p\\ \vdots&\vdots\\i_0s_0+\cdots+i_{m-1}s_{m-1}+cs_m,&\qquad i_0,\dots,i_{m-1}\in F_p \end{array}\right\}$

Deuber’s main result was the following:

Theorem 7 Let ${m,p,c,r\in{\mathbb N}}$ . Then there exist ${M,P,C\in{\mathbb N}}$ such that for any finite partition of a ${(M,P,C)}$ -set there exists a monochromatic subset which is an ${(m,p,c)}$ -set.

The relation between ${(m,p,c)}$ -sets and Rado’s theorem is the following:

Proposition 8

For every ${d,k\in{\mathbb N}}$ and any ${k\times d}$ matrix ${A}$ satisfying the columns condition there exist ${m,p,c\in{\mathbb N}}$ such that for any ${(m,p,c)}$ -set ${B}$ there exists ${\vec x\in B^d}$ such that ${A\vec x=\vec0}$ .
For every ${m,p,c\in{\mathbb N}}$ there exist ${d,k\in{\mathbb N}}$ and a ${k\times d}$ matrix ${A}$ satisfying the columns condition such that for any ${\vec x=(x_1,\dots,x_d)\in{\mathbb N}^d}$ with ${A\vec x=0}$ there exists an ${(m,p,c)}$ -set contained in ${\{x_1,\dots,x_d\}}$ .

This proposition implies that a set ${B\subset{\mathbb N}}$ is rich if and only if for every ${m,p,c\in{\mathbb N}}$ there exists an ${(m,p,c)}$ -set contained in ${B}$ . 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) ${\Rightarrow}$ (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 ${m,d\in{\mathbb N}}$ and let ${A}$ be a ${k\times d}$ matrix with integer entries satisfying the columns condition. Let ${c_1,\dots,c_d}$ be the columns of ${A}$ and let ${m\in{\mathbb N}}$ and ${0=d_0<d_1<d_2<\cdots<d_md_j}$ and for every ${0\leq j\leq m}$ we have
$\displaystyle c_{d_j+1}+c_{d_j+2}+\cdots+c_{d_{j+1}}=\phi[1,j]c_i+\cdots+\phi[d_j,j]c_{d_j}$

Thus there exist a common denominator ${c\in{\mathbb N}}$ , so that ${c\phi[i,j]\in{\mathbb Z}}$ for all ${i,j}$ . Next let, for ${0\leq j\leq m}$

$\displaystyle \psi[i,j]=\left\{\begin{array}{cl}-c\phi[i,j]& if \quad 1\leq i\leq d_j\\ c& if \quad d_j+1\leq i\leq d_{j+1} \\ 0& if \quad i \geq d_{j+1}+1\end{array}\right.$

Then if ${\Psi}$ is the ${d\times(m+1)}$ matrix with entries ${\psi[i,j]}$ we have ${A\Psi=\vec0}$ . In particular, for any ${\vec s\in{\mathbb N}^{m+1}}$ , if we let ${\vec x=\Psi\vec s}$ , then ${A\vec x=0}$ .

Finally, take ${p}$ to be the maximum of ${|\psi[i,j]|}$ and let ${\vec s\in{\mathbb N}^{m+1}}$ be arbitrary. We claim that the entries of ${\Psi\vec s}$ are contained in the ${(m,p,c)}$ -set ${D(m,p,c;\vec s)}$ , and this will finish the proof. Indeed, let ${1\leq i\leq d}$ and find ${j}$ such that ${d_j<i\leq d_{j+1}}$ . Then the ${i}$ -th entry of ${\Psi\vec s}$ is

$\displaystyle cs_j+\psi[i,j+1]s_{j+1}+\cdots+\psi[i,m]s_m$

and since ${\psi[i,j+1],\dots,\psi[i,m]\in F_p}$ this proves the claim and finishes the proof.
Let ${m,p,c\in{\mathbb N}}$ be arbitrary. For each ${j\in\{1,\dots,m\}}$ and each of choice ${i_0,\dots,i_{j-1}\in F_p}$ consider the vector
$\displaystyle \ell(j;i_0,\dots,i_{j-1})=[i_0,\dots,i_{j-1},c,0,\dots,0]\in{\mathbb Z}^{m+1}$

Observe that, for a given ${\vec s\in{\mathbb N}^{m+1}}$ , the Deuber set ${D(m,p,c;\vec s)}$ can be written as

$\displaystyle D(m,p,c;\vec s)=\Big\{\big\langle \ell(j;i_0,\dots,i_{j-1}),\vec s\big\rangle:(j,i_0,\dots,i_{j-1})\in[m]\times F_p^j\Big\}$

Now let ${A_1}$ be the matrix with ${m+1}$ columns and lines ${\ell(j;i_0,\dots,i_{j-1})}$ ; observe that the entries of ${A_1\vec s}$ are exactly the elements of ${D(m,p,c;\vec s)}$ . The number of lines in ${A_1}$ is

$\displaystyle d:=1+(2p+1)+(2p+1)^2+\cdots+(2p+1)^m=\frac{(2p+1)^{m+1}-1}{2p}$

Next let ${A_2:=-cI_d}$ where ${I_d}$ is the ${d\times d}$ identity matrix and let ${A}$ be the ${d\times(d+m+1)}$ concatenation of ${A_1}$ and ${A_2}$ . Let ${\vec x\in{\mathbb N}^{d+m+1}}$ be such that ${A\vec x=\vec0}$ , write ${\vec x=(t_0,\dots,t_m,y_1,\dots,y_d)}$ and let ${\vec t=(t_0,\dots,t_m)\in{\mathbb N}^{m+1}}$ and ${\vec y=(y_1,\dots,y_d)}$ . We can rewrite ${A\vec x=\vec0}$ as ${A_1\vec t+A_2\vec y=\vec0}$ which is then equivalent to ${A_1\vec t=c\vec y}$ . A short induction now shows that each ${t_i}$ must be a multiple of ${c}$ , so we can write ${\vec t=c\vec s}$ for some ${\vec s\in{\mathbb N}^{m+1}}$ . Therefore, we conclude that ${A_1\vec s=\vec y}$ , so the entries of ${\vec x}$ contain and ${(m,p,c)}$ -set.

Finally we need to show that ${A}$ satisfies the columns condition. But according to Theorem 7, for any finite partition of ${{\mathbb N}}$ there exists ${\vec s\in{\mathbb N}^{m+1}}$ such that ${D(m,p,c;\vec s)}$ is monochromatic. Taking ${\vec y=A_1\vec s}$ and ${\vec x=(c\vec s,\vec y)\in{\mathbb N}^{d+m+1}}$ we deduce that ${A\vec x=0}$ . Since ${cs_i\in D(m,p,c;\vec s)}$ for each ${i=0,\dots,m}$ we conclude that all the entries of ${\vec x}$ are monochromatic. This shows that for any finite coloring of ${{\mathbb N}}$ there exists ${\vec x}$ with all entries in the same color such that ${A\vec x=0}$ . By Theorem 3 this implies that ${A}$ satisfies the columns condition, as desired.