Rado's Theorem

Section 4.4 Rado's Theorem

One must still have chaos in oneself to be able to give birth to a dancing star. — Friedrich Wilhelm Nietzsche, German philologist, philosopher, cultural critic, poet and composer, 1844 — 1900

Reminder: Schur's Theorem. If the set of positive integers \(\mathbb{N}\) is finitely coloured then there exist \(x,y,z\) having the same colour such that

\begin{equation*} x_1+x_2-x_3=0\text{.} \end{equation*}

Reminder: van der Waerden's Theorem. If the set of positive integers \(\mathbb{N}\) is finitely coloured then there exist \(x,y,z\) having the same colour such that

\begin{equation*} x_1+x_2-2x_3=0 \end{equation*}

Question 4.4.1.

Does every 2-colouring of natural numbers contain a monochromatic solution of the equation

\begin{equation*} x_1-2x_2=0? \end{equation*}

See Figure 4.4.2.

Figure 4.4.2. If \(\color{red}{x}\) then \(\color{blue}{2x}\text{.}\)

Question 4.4.3.

Does every finite colouring of positive integers contain a monochromatic solution of the equation

\begin{equation*} x_1-2x_2+3x_3=0? \end{equation*}

Proof.

We define a colouring \(c:\mathbb{N}\to \{1,2,\ldots,6\}\) in the following way:

\begin{equation*} \mbox{If } n=7^k\cdot (7\cdot l+i), \ i\in \{1,2,\ldots,6\}, k,l \geq 0, \mbox{ then } c(n)=i\text{.} \end{equation*}

See Figure 4.4.4. For example, in this colouring

\begin{equation*} c(5)=5, \ c(14)=2,\ c(25)=4, \mbox{ and } c(49)=1\text{.} \end{equation*}

Figure 4.4.4. A 6 colouring of \(\mathbb{N}\text{.}\)

Suppose that there is a \(c\)- monochromatic solution of the given equation. Hence suppose that there are

\begin{equation*} x_1=7^k(7l+i), \ x_2=7^s(7t+i), \ x_3=7^p(7q+i)\text{,} \end{equation*}

with \(i\in \{1,2,\cdots,6\}\) and \(k,l,s,t,p,q\geq 0\text{,}\) such that

\begin{equation*} x_1-2x_2+3x_3=0 \Leftrightarrow 7^k(7l+i)-2\cdot 7^s(7t+i)+3\cdot 7^p(7q+i)=0 \end{equation*}

or, which is the same,

\begin{equation*} (7^k-2\cdot 7^s+3\cdot 7^p)\cdot i=2\cdot 7^{s+1}\cdot t-7^{k+1}\cdot l-3\cdot 7^{p+1}\cdot q\text{.} \end{equation*}

Observe that there is one “extra” factor of \(7\) on the right hand side of the expression above. What happens if we divide the expression by \(7^r\text{,}\) where \(r=\min\{k,s,p\}\text{?}\) Will the right-hand side of the expression be divisible by 7? What about the left-hand side?

Question 4.4.5.

Under what conditions does a homogeneous linear equation

\begin{equation*} c_1x_1+c_2x_2+\cdots+c_nx_n=0, c_1,c_2,\ldots,c_n\in \mathbb{Z} \end{equation*}

have a monochromatic solution whenever \(\mathbb{N}\) is finitely coloured?

Definition 4.4.6.

We say that a homogeneous linear equation

\begin{equation*} c_1x_1+c_2x_2+\cdots+c_nx_n=0, c_1,c_2,\ldots,c_n\in \mathbb{Z} \end{equation*}

is partition regular over \(\mathbb{N}\) if it has a monochromatic solution whenever \(\mathbb{N}\) is finitely coloured.

Question 4.4.7.

Under what conditions is a homogeneous linear equation

\begin{equation*} c_1x_1+c_2x_2+\cdots+c_nx_n=0, c_1,c_2,\ldots,c_n\in \mathbb{Z} \end{equation*}

partition regular over \(\mathbb{N}\text{?}\)

Observation 4.4.8.

Equations \(x_1+x_2-x_3=0\) and \(x_1+x_2-2x_3=0\) are partition regular.
Equations \(x_1-2x_2=0\) and \(x_1-2x_2+3x_3=0\) are not partition regular.

Definition 4.4.9.

\(p\)-Primer. Let \(p\) be a prime. The \(p\)-primer is a \((p-1)\)-colouring of natural numbers obtained in the way demonstrated at the Figure 4.4.10.

Figure 4.4.10. The \(p\)-primer, a \((p-1)\)-colouring of \(\mathbb{N}\text{.}\)

Proposition 4.4.11.

Let integers \(c_1,c_2,\ldots, c_n\) be such that for any subset \(J\subseteq [n]\)

\begin{equation*} \sum _{i\in J}c_i\not=0\text{.} \end{equation*}

Then the equation \(c_1x_1+c_2x_2+\cdots+c_nx_n=0\) is NOT partition regular over \(\mathbb{N}\text{.}\)

Proof.

Let \(p\) be a prime such that

\begin{equation*} p>\sum _{i=1}^n|c_i| \end{equation*}

and let \(\chi:\mathbb{N}\to [p-1]\) be the \(p\)-primer.

Suppose that \(X=\{ x_1,x_2,\ldots, x_n\}\) is a \(p\)-primer monochromatic solution of the given equation. Then there are \(i\in \{1,\ldots,p-1\}\) and \(r_1,r_2,\ldots,r_n\geq 0\) such that

\begin{align*} x_1\amp =\amp \ldots i\underbrace{0\cdots0}_{r_1}\\ x_2\amp =\amp \ldots i\underbrace{0\cdots0}_{r_2}\\ \amp \vdots\amp\\ x_n\amp =\amp \ldots i\underbrace{0\cdots0}_{r_n}\text{.} \end{align*}

See Figure 4.4.12.

Figure 4.4.12. \(\ldots\) there is a monochromatic solution \(X=\{x_1,x_2,\ldots,x_n\}\text{.}\)

Let \(r=\min \{r_1,r_2, \ldots, r_n\}\) and \(J=\{j\in[1,n]:r_j=r \}\text{:}\)

\begin{equation*} \begin{array}{cccccccccc} \amp \amp \amp \amp \amp r+1\amp \amp \amp \\ \amp \amp \amp \amp \amp \downarrow\amp \amp \amp \\ x_1=\amp \ldots\amp \amp \amp \amp i\amp 0\amp \ldots\amp 0\\ x_2=\amp \ldots\amp \amp \amp i\amp 0\amp 0\amp \ldots\amp 0\\ x_3=\amp \ldots\amp i\amp 0\amp \ldots\amp 0\amp 0\amp \ldots\amp 0\\ \vdots\amp \amp \amp \amp \amp \amp \amp \amp \\ x_j=\amp \ldots\amp \amp \amp \amp i\amp 0\amp \ldots\amp 0\\ \vdots\amp \amp \amp \amp \amp \amp \amp \amp \\ x_n=\amp \ldots\amp \amp i\amp \ldots\amp 0\amp 0\amp \ldots\amp 0 \end{array} \end{equation*}

Divide

\begin{equation*} 0=\sum _{j\in J}c_jx_j+\sum_{j\in [n]\backslash J}c_jx_j =\sum _{j\in J}c_j\cdot p^r(pk_j+i)+\sum_{j\in [n]\backslash J}c_j\cdot p^{r_j}(pk_j+i) \end{equation*}

by \(p^r\) to obtain

\begin{equation*} i\sum_{j\in J}c_j+p\cdot A=0, \ A\not=0\text{.} \end{equation*}

Contradiction.

Therefore:

Proposition 4.4.13.

Let the equation \(c_1x_1+c_2x_2+\cdots+c_nx_n=0\) be partition regular over \(\mathbb{N}\text{.}\) Then there is \(J\subseteq [n]\) such that

\begin{equation*} \sum _{i\in J}c_i=0\text{.} \end{equation*}

Lemma 4.4.14.

Let \(q\in \mathbb{Q}\) and \(k\in \mathbb{N}\text{.}\) Every \(k\)-colouring of natural numbers contains a monochromatic solution of the equation \(x+qy=z\text{.}\)

Proof.

\(q=0\text{:}\)
\(q\lt 0\text{:}\)
\(q>0\text{:}\) Let \(r,s\in \mathbb{N}\) be such that \(\displaystyle q=\frac{r}{s}\text{.}\)
1. We prove by induction on \(k\) that for any \(k\in \mathbb{N}\) there is \(n\in \mathbb{N}\) such that any \(k\)-colouring of \([n]\) contains a monochromatic solution of the equation \(x+qy=z\text{.}\)
2. If \(k=1\text{,}\) take \(n=\max\{s,r+1\}\) and \(x=1\text{,}\) \(y=s\text{,}\) and \(z=r+1\text{.}\)
3. Suppose that \(k\geq 1\) and \(n\in\mathbb{N}\) are such that any \(k\)-colouring of \([n]\) contains a monochromatic solution of the equation \(x+qy=z\text{.}\) See Figure 4.4.15.
  
  Figure 4.4.15. Let \(w(nr+1,k+1)\) be a van der Waerden number, i.e., the least positive integer such that any \((k+1)\)-colouring of \([1,w(nr+1,k+1)]\) contains a monochromatic \(nr+1\) arithmetic progression.
4. Case 1. See Figure 4.4.16.
  
  Figure 4.4.16. Take \(x=a\text{,}\) \(y=ids\text{,}\) and \(z=a+ird\text{.}\)
5. Case 2. See Figure 4.4.17.
  
  Figure 4.4.17. The set \(S=\{ds,2ds,\ldots,nds\}\) is \(k\)-coloured.

Proposition 4.4.18.

If the set of non-zero integers \(\{c_1,c_2,\ldots,c_n\}\) is such that

\begin{equation*} \sum _{i\in J}c_i=0 \end{equation*}

for some \(J\subseteq [n]\text{,}\) then the equation \(c_1x_1+c_2x_2+\cdots+c_nx_n=0\) is partition regular over \(\mathbb{N}\text{.}\)

Proof.

Let \(\chi\) be a finite colouring of \(\mathbb{N}\text{.}\) Let \(i_0\in J\) and let \(\{x,y,z\}\) be a \(\chi\)-monochromatic solution of the equation

\begin{equation*} x+\frac{\sum_{i\not\in J}c_i}{c_{i_0}}y=z \end{equation*}

Let

\begin{equation*} x_i=\left\{ \begin{array}{ll} x\amp \mbox{if } i=i_0\\ y\amp \mbox{if } i\not\in J\\ z\amp \mbox{if } i\in J\backslash \{i_0\}. \end{array} \right. \end{equation*}

Then

\begin{align*} c_1x_1+c_2x_2+\cdots+c_nx_n\amp =\amp \sum_{i\in J}c_ix_j+\sum_{i\not\in J}c_ix_j\\ \amp =\amp c_{i_0}x_{i_0}+\sum_{i\in J\backslash \{i_0\}}c_ix_j+\sum_{i\not\in J}c_ix_j\\ \amp =\amp \end{align*}

Theorem 4.4.19.

Rado's Theorem. The equation \(c_1x_1+c_2x_2+\cdots+c_nx_n=0\) is partition regular over \(\mathbb{N}\) if and only if there is \(J\subseteq [n]\) such that

\begin{equation*} \sum _{i\in J}c_i=0\text{.} \end{equation*}

Resources.