= Solution
\b[Rado's criterion.] Let $A$ be a <matrix> over the <rational numbers>, with columns $a_1,\ldots,a_q$. A <partition regular matrix> is one for which every <finite coloring> of the <positive integers> gives a <monochromatic> positive vector $x\in\mathbb N^q$ with $Ax=0$; repeated coordinates are allowed. The <columns condition> is the existence of an ordered <set partition> $B_1,\ldots,B_s$ of $[q]$ into nonempty blocks such that
$$
\sum_{i\in B_1}a_i=0,\qquad
\sum_{i\in B_j}a_i\in\operatorname{span}_{\mathbb Q}\{a_i:i\in B_1\cup\cdots\cup B_{j-1}\}\quad(j>1).
$$
<Rado's theorem> states
$$
\boxed{A\text{ is partition regular if and only if it satisfies the columns condition}.}
$$
\b[Necessity.] Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne\varnothing$, for which $v_B=\sum_{i\in B}a_i$ is outside the <linear span> of the $I$-columns, choose an integer <linear functional> $\phi_{I,B}$ that vanishes on those columns and satisfies $\phi_{I,B}(v_B)\ne0$. Such a functional exists by extending a <basis> of the span to one also containing $v_B$, defining a functional on that <basis>, and clearing its rational denominators.
There are only finitely many such pairs. Choose a <prime number> $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the <last nonzero digit coloring>: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\bmod p\in\{1,\ldots,p-1\}$. Since $A$ is a <partition regular matrix>, this coloring supplies a <monochromatic> positive solution, so all its unit parts have a common nonzero residue $d$.
Group the coordinates by increasing <P-adic valuation>, obtaining blocks $B_1,\ldots,B_s$ with valuations $e_1<\cdots<e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the <linear span> of the earlier columns, with earlier index set $I$. Apply $\phi_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block gives
$$
0\equiv d\,\phi_{I,B_j}(v_{B_j})\pmod p,
$$
contrary to the choice of $p$. Thus every block sum lies in the earlier <linear span>, and for the first block this means it is zero. This proves the <columns condition> by the <finite separating-functional proof of the columns condition>.
\b[Sufficiency.] Suppose the <columns condition> holds. For $j>1$, choose rational coefficients $\lambda_{ij}$, indexed by earlier columns, such that
$$
\sum_{i\in B_j}a_i+\sum_{i\in B_1\cup\cdots\cup B_{j-1}}\lambda_{ij}a_i=0.
$$
Take a positive integer $c$ clearing their denominators and $p\geq1$ bounding all $|c\lambda_{ij}|$. We use the allowed <monochromatic m-p-c set theorem> with $s$ levels. Its <M-p-c set> is the full set
$$
D=\bigcup_{h=1}^s\left\{cz_h+\sum_{j>h}\mu_jz_j:\mu_j\in\mathbb Z,\ |\mu_j|\leq p\right\},
$$
where the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, set
$$
x_i=cz_h+\sum_{j>h}c\lambda_{ij}z_j.
$$
All these numbers lie in the <monochromatic> set $D$. The coefficient of $z_j$ in $Ax$ is
$$
c\left(\sum_{i\in B_j}a_i+\sum_{i\in B_1\cup\cdots\cup B_{j-1}}\lambda_{ij}a_i\right)=0,
$$
with the first coefficient zero by $\sum_{i\in B_1}a_i=0$. Hence $Ax=0$. This <Rado solution inside an m-p-c set> proves sufficiency.
\b[The equality-or-inequality dichotomy.] If every <finite coloring> gives a <monochromatic> solution with $x_1=x_2$, the first alternative holds. Otherwise fix a <finite coloring> $\chi$ admitting no such solution. Given any other <finite coloring> $\psi$, use the <refinement of a finite coloring> $n\mapsto(\chi(n),\psi(n))$. Since $A$ is a <partition regular matrix>, it supplies a solution <monochromatic> for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the <partition regularity dichotomy under an extra constraint>; the alternatives are not asserted to be mutually exclusive.
\b[Both restrictions can fail.] The Schur <matrix>
$$
A=(1\ \ 1\ \ {-1})
$$
is a <partition regular matrix>: blocks $\{1,3\}$ and $\{2\}$ satisfy the <columns condition>. Color $n$ by $v_2(n)\bmod2$, using the <2-adic valuation>. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be <monochromatic>. This exhibits failure of the equality restriction.
Conversely, $A=(1\ \ {-1})$ satisfies the <columns condition> in one block. Every solution has $x_1=x_2$, so even the constant one-color <finite coloring> admits no unequal-coordinate solution. Consequently
$$
\boxed{\text{equality can be impossible for one coloring, and inequality can be impossible for every coloring}.}
$$
Back to article page
