Columns property

If $c_1,\dots ,c_n$ are the columns of a matrix, the matrix has the columns property when $[n]$ has an ordered partition $B_1\bigsqcup \cdots \bigsqcup B_s$ such thatand, for $j>1$, ${\sum }_{i\in B_j}{c}_i$ belongs to the linear span of the columns indexed by $B_1\cup \cdots \cup B_{j-1}$.

Rado's theorem states that a rational matrix is partition regular if and only if it has the columns property.

The positive-variable system $3x+y=3z$, $x-2y=w$ is partition regular. Its columns for $x,z,w$ sum to zero, and the remaining $y$ column lies in their rational span, satisfying the columns condition. Thus every finite colouring has monochromatic positive $x,y,z,w$ with $2y<x$. A triangular m-p-c set gives the explicit solution $x=3u$, $y=3v$, $z=3u+v$, $w=3u-6v$, with positivity guaranteed by membership in that set.

For nonzero rational coefficients $a_1,\dots ,a_n$, the equationis partition regular exactly when some nonempty subset of the coefficients has sum zero. This is the one-row form of the columns property.

Suppose nonzero integer coefficients have a nonempty zero-sum subset $I$, and fix $i_0\in I$. Put $s=|a_{i_0}|$ and $C={\sum }_{j\notin I}{a}_j$. A Brauer progression theorem configuration containing a sufficiently long monochromatic progression of step $d$ and the point $sd$ gives a positive solution: take every outside variable equal to $sd$, and the inside variables from the progression with offsets ${\lambda }_i$, where ${\lambda }_{i_0}=-\mathrm{sgn}(a_{i_0})C$ and the other offsets are zero. Shifting all inside offsets by the same integer keeps their weighted sum unchanged, because ${\sum }_{i\in I}{a}_i=0$. This removes negative offsets while preserving the equation.

For nonzero integer coefficients $a_i$, choose a prime number $p>{\sum }_i|a_i|$ and colour each positive integer by its nonzero leading residue after removing its power of $p$. In a monochromatic zero-sum solution, divide by the least occurring power of $p$. Reduction modulo $p$ then makes the sum of the coefficients attached to the least-valuation variables vanish modulo $p$. Its absolute value is less than $p$, so that sum vanishes as an integer. This gives the necessity direction of the one-equation partition regularity criterion without using the general Rado theorem.

A rational homogeneous equation ${\sum }_i{a}_i{x}_i=0$ has a monochromatic positive odd solution in every finite colouring of the odd integers exactly when its full coefficient sum is zero. Sufficiency uses a constant odd vector. For necessity, clear denominators and, if the total $S$ is nonzero, colour by odd residue classes modulo $2^K>|S|$. A common odd residue is invertible, so a solution would require $2^K\mid S$, impossible. This is stronger than the zero-sum-subset criterion for unrestricted partition regularity.

The necessity direction in Rado's theorem colors an integer using initial data from a P-adic valuation. Applying partition regularity and grouping the coordinates of a monochromatic solution by valuation yields the blocks in the columns property; reduction modulo successively higher powers of $p$ supplies the required linear dependences.

After clearing denominators in a matrix, for every disjoint pair of index sets $I,B$ with $B$ nonempty and ${\sum }_{i\in B}{a}_i$ outside the linear span of the $I$-columns, choose an integer linear functional vanishing on those columns but not on the indicated sum. Choose a prime number dividing none of the finitely many nonzero evaluations. The last nonzero digit coloring for this prime, applied to a monochromatic positive solution, groups coordinates into blocks by P-adic valuation. Applying the appropriate functional and reducing modulo the prime shows that each block sum lies in the linear span of all earlier columns. This proves necessity in Rado's theorem without an asymptotic limiting argument.

For a prime number $p$, write a positive integer as $x=p^{v_p(x)}u$ with $p\nmid u$. Its last nonzero base-$p$ digit is $u\mathrm{mod}p$, an element of $\{1,\dots ,p-1\}$. Assigning this digit as the color gives the last nonzero digit coloring used in the necessity proof of Rado's theorem.

An $(m,p,c)$-set has positive integer generators $z_1,\dots ,z_m$ chosen so that every expression below is positive, and consists of all their values:The required positivity is equivalent to $c{z}_j>p{\sum }_{s>j}{z}_s$ for each $j$; it is not defined by discarding nonpositive values from the displayed family.

Suppose the columns $a_i$ of a matrix over the rational numbers satisfy the columns condition with blocks $B_1,\dots ,B_s$. Choose rational coefficients ${\lambda }_{ij}$ such thatChoose a positive integer $c$ clearing all denominators and $p\ge \max |c{\lambda }_{ij}|$. For generators of any full positive M-p-c set, the coordinateslie in that set and satisfy $Ax=0$. Thus the monochromatic m-p-c set theorem supplies the sufficiency direction of Rado's theorem.

For every positive $m,p,c$, every finite coloring of the positive integers contains a monochromatic M-p-c set.

For every dimension $m$, every finite coloring of the positive integers contains $x_1,\dots ,x_m$ for which all nonempty sums of distinct $x_i$ have one color. This is the case $p=c=1$ of the monochromatic m-p-c set theorem.

Introduce a variable $z_I$ for every nonempty $I\subseteq [k]$ and the homogeneous equations $z_I-{\sum }_{i\in I}{z}_{\{i\}}=0$ for $|I|\ge 2$. In their matrix $A$, partition the columns by the displayed blocks. For each $j$, the vector with coordinate $1$ exactly when $j\in I$ lies in the kernel of a linear map of $A$. Its nonzero coordinates occur in $B_j$ and earlier blocks only; every coordinate in $B_j$ is one. Hence the first block's column sum is zero and every subsequent block sum is in the linear span of earlier columns. The columns condition holds, so Rado's theorem forces a positive monochromatic solution, and all nonempty finite sums of its singleton coordinates have the same colour.