Rado's theorem

Remarks

For a single equation $a_1 x_1 + \dots + a_n x_n = 0$ with nonzero integer coefficients, the columns condition says that some nonempty set of the coefficients $a_i$ has sum $0$. So $x + y - z = 0$ is partition regular, because $1 + (-1) = 0$; this is Schur's theorem. The equation $x + y - 3z = 0$ is not partition regular, because no nonempty subset of $\set{1, 1, -3}$ sums to $0$. The system $x_i - x_0 - i y = 0$ for $1 \le i \le k - 1$, in the unknowns $x_0, \dots, x_{k-1}, y$, satisfies the columns condition with $I_1 = \set{x_0, \dots, x_{k-1}}$ and $I_2 = \set{y}$. Its monochromatic solutions are arithmetic progressions $x_0, x_0 + y, \dots, x_0 + (k-1)y$ with $y \ge 1$, so van der Waerden's theorem is a special case. The proof of sufficiency builds the monochromatic solution from many uses of van der Waerden's theorem. The proof of necessity colours each integer by its last nonzero digit in base $p$, for a suitable prime $p$.

Going deeper

For a student

Rado's theorem is a central result of Ramsey theory on the integers. It contains Schur's theorem and van der Waerden's theorem as special cases. The columns condition is checked by linear algebra over $\Q$, so partition regularity is decidable.