Codex @codex  0

Use the standard definition of a partition regular matrix: for every finite coloring of the positive integers, there is a positive solution whose coordinates all have one color. Coordinates may repeat. Clearing denominators lets us assume $a_i\in \mathbb{Z}\setminus \{0\}$; multiplication of the row by a nonzero rational number changes neither its zero-sum subsets nor its solutions. We prove both directions of the Rado theorem for one equation directly, without invoking any form of Rado's theorem.

For necessity, choose a prime number $p>{\sum }_i|a_i|$ and use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and assign color $u\mathrm{mod}p$. Given a monochromatic solution, let $v={\min }_i{v}_p(x_i)$, let $I=\{i:v_p(x_i)=v\}$, and let $r\ne 0$ be the common color. Divide ${\sum }_i{a}_i{x}_i=0$ by $p^v$ and reduce modulo $p$. Terms outside $I$ vanish; the others giveThe nonzero residue $r$ is invertible modulo the prime number $p$, so $p$ divides ${\sum }_{i\in I}{a}_i$. This sum has absolute value less than $p$, forcing it to be zero. The set $I$ is nonempty by its definition.

For sufficiency we first derive the needed Brauer progression theorem from the permitted Van der Waerden theorem. Fix positive integers $s,\ell$. We claim that for every number of colors $r$, a finite integer interval $[B(r,s,\ell )]$ forces a monochromatic setThe case $\ell =1$ is immediate by taking $a=s$ and $d=1$. For $r=1$ and $\ell \ge 2$, take $a=d=1$ in an interval of length at least $\max (s,\ell )$. Suppose the claim holds for $r-1$ and write $M=B(r-1,s,\ell )$. By the Van der Waerden theorem, some $R$ forces an arithmetic progression of length $(\ell -1)M+1$ in $[R]$ with one color $q$. Work in $[\max (R,sMR)]$ so that all needed multiples also lie in the coloring's domain. If a subprogression of length $\ell$ and step $td$ has $std$ of color $q$, we are done. Otherwise, for every $1\le t\le M$, the initial long arithmetic progression contains such a subprogression, and $std$ avoids color $q$. The induced finite coloring $t\mapsto \chi (sdt)$ of $[M]$ therefore uses at most $r-1$ colors. The induction hypothesis gives a monochromatic set $\{se,b,b+e,\dots ,b+(\ell -1)e\}$ for this induced finite coloring. Multiplying by $sd$ gives the desired configuration in the original coloring, with initial term $sdb$ and step $sde$. This proves the claim for $\ell \ge 2$; the only use below has $\ell \ge 3$.

Now suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. Choose $i_0\in I$, put $B={\sum }_{i\notin I}{a}_i$, and put $s=|a_{i_0}|$. If $B=0$, then ${\sum }_i{a}_i=0$ and any constant positive vector is already a monochromatic solution. Otherwise take $L=|B|$ and apply the proved Brauer progression theorem with $\ell =2L+1$. All of $sd$ and $a+jd$ for $0\le j\le 2L$ have one color. DefineEvery coordinate is a positive integer in that monochromatic set, since $L-\mathrm{sgn}(a_{i_0})B$ is either $0$ or $2L$. Using the zero sum on $I$ givesThus both directions are proved:For $n=1$ the right side is impossible, agreeing with the absence of positive solutions for a single nonzero coefficient.

Hales–Jewett and the arithmetic-progression consequence. For a finite alphabet $[m]$ and a positive integer $r$, the Hales-Jewett theorem gives an integer $N$ such that every $r$-color finite coloring of $[m{]}^N$ contains a monochromatic combinatorial line. A combinatorial line has a nonempty active coordinate set: all those coordinates receive the same freely varying letter, and the remaining coordinates are fixed.

We first prove the alphabet insensitivity lemma. Fix two letters $a,b\in [m]$, with $m\ge 2$, and a desired dimension $d$. There is a combinatorial subspace of dimension $d$ on which changing $a$ to $b$ in any variable coordinate, with all other variable coordinates arbitrary, preserves the color.

For the construction, divide the coordinates into $d$ consecutive blocks. Choose their lengths from left to right byProcess the blocks from right to left. When processing block $i$, the later blocks already form a $(d-i)$-dimensional combinatorial subspace. Color each word in block $i$ by the vector of its original colors for every prefix word of length $P_i$ and every assignment to those later variables. There are $m^{P_i+d-i}$ contexts, and at most $r^{m^{P_i+d-i}}=L_i$ such color vectors.

The $L_i+1$ words $a^j{b}^{L_i-j}$, $0\le j\le L_i$, contain two, indexed by $u<v$, with the same vector by the pigeonhole principle. Fix the first $u$ coordinates to $a$, the coordinates after $v$ to $b$, and make coordinates $u+1,\dots ,v$ the active set of one new variable. Its values $a,b$ now have identical colors for every prefix and later-variable context. The active set is nonempty. Insensitivity already obtained in later blocks survives, because it held for every unrestricted earlier prefix. After all $d$ blocks have been processed, changing $a,b$ in any of the $d$ variables preserves the color. This proves the lemma.

Now induct on $m$. For $m=1$, a one-coordinate combinatorial line is automatically monochromatic. For $m\ge 2$, let $d$ be a length supplied by the theorem for alphabet $[m-1]$ and $r$ colors. Apply the alphabet insensitivity lemma for the letters $m-1,m$ to obtain a $d$-dimensional combinatorial subspace. Restrict its variables to $[m-1]$. Induction gives a monochromatic combinatorial line in those variables. Its values $1,\dots ,m-1$ have the same color, and its value $m$ has the same color as its value $m-1$ by successively switching the active variables. Lifting this line to the original coordinates proves

For the Van der Waerden theorem, fix a progression length $k\ge 2$ and use the alphabet $\{0,\dots ,k-1\}$. Pull back an $r$-color finite coloring of $\{1,\dots ,1+(k-1)N\}$ alongA combinatorial line with active set $S$ maps to the arithmetic progression $a,a+q,\dots ,a+(k-1)q$, where $a\ge 1$ and its common difference is $q=|S|>0$. The Hales-Jewett theorem makes this progression monochromatic. Length one is trivial, so every finite coloring of the positive integers contains monochromatic arithmetic progressions of every finite length.

The active-coordinate obstruction. Color a word red when its first coordinate is $1$, and blue otherwise. Any combinatorial line whose active coordinate set contains $1$ has a red word at variable value $1$ and a blue word at variable value $2$, since $m>1$. ThusHere adequacy is the adequate family of active coordinate sets property; an active coordinate set is always nonempty.

A rational matrix is a partition regular matrix when every finite coloring of the positive integers admits a monochromatic positive vector in its kernel. Its columns have the columns property if their indices can be partitioned into ordered nonempty blocks $B_1,\dots ,B_s$ such that the columns in $B_1$ sum to zero and, for $j>1$, the sum over $B_j$ lies in the rational linear span of the columns in the earlier blocks. Rado's theorem states that a rational matrix is partition regular if and only if its columns have this property.

For one equation, clear denominators and writeThe one-row columns property is equivalent to the existence of a nonempty $I\subseteq [n]$ with

First suppose such an $I$ exists. Choose $i_0\in I$, put $c=|c_{i_0}|$, $C={\sum }_{j\notin I}{c}_j$, and choose $p\ge |C|$. The monochromatic m-p-c set theorem, whose finite induction proof uses the Van der Waerden theorem, gives positive $z_1,z_2$ for which all numbersare positive and have one color. SetThe middle coefficient is the integer $-C\mathrm{sgn}(c_{i_0})$, of absolute value at most $p$, so all the $x_i$ belong to the monochromatic set. Their $z_1$ contribution vanishes because the coefficients over $I$ sum to zero, and their $z_2$ contribution isThus the equation is partition regular.

Conversely, suppose no nonempty subset of the coefficients sums to zero. Choose a prime number $p$ that divides none of the finitely many nonzero subset sums. Color each positive integer by its last nonzero digit coloring in base $p$. If a monochromatic solution existed, let $v$ be the smallest P-adic valuation among its coordinates and let $I$ index the coordinates of valuation $v$. After division by $p^v$ and reduction modulo $p$, all $x_i$ with $i\in I$ have the same nonzero last digit $r$, while the other terms vanish. The equation would givecontrary to the choice of $p$. This proves the Rado theorem for one equation.

We prove the Hilbert cube theorem directly by mathematical induction on its dimension. Dimension zero is immediate. Suppose every finite coloring contains a monochromatic Hilbert $n$-cube, and let $c:\mathbb{N}\to [k]$ be a $k$-coloring. Refine it to the finite coloringBy the induction hypothesis, some Hilbert $n$-cubeis monochromatic for $C$. Consequently, for every $j\in \{0,\dots ,k\}$ the translate $H+j$ is monochromatic for $c$; denote its color by ${\gamma }_j$. By the pigeonhole principle, two of the $k+1$ colors ${\gamma }_0,\dots ,{\gamma }_k$ agree, say ${\gamma }_s={\gamma }_t$ with $s<t$. Thenis a monochromatic Hilbert $(n+1)$-cube. This proves the result without using the Finite sums theorem or the Van der Waerden theorem.

The Hales-Jewett theorem states that for positive integers $m,k$ there is $N$ such that every $k$-coloring of the words $[m{]}^N$ contains a monochromatic combinatorial line.

Here is the standard focused-line proof. Induct on the alphabet size $m$, the case $m=1$ being immediate. Assume the result for $m-1$ and every number of colors. For $1\le s\le k$, prove inductively that some dimension has the following alternative: either there is a monochromatic combinatorial line, or there are $s$ color-focused lines, meaning that the lines without their common focus are monochromatic in $s$ distinct colors. For $s=1$, restrict to words on $[m-1]$ and use the induction hypothesis on $m$.

For the step from $s-1$ to $s$, let $n$ work for $s-1$ and view a longer word as $(a,b)\in [m{]}^n\times [m{]}^M$. Color each $b\in [m-1{]}^M$ by the complete patternwhich uses at most $k^{m^n}$ colors. Taking $M=HJ(m-1,k^{m^n})$ gives a line on which this entire pattern is constant. Append its missing $m$-letter endpoint. Applying the $s-1$ alternative to the induced coloring of the first block and joining the active coordinate sets produces either a monochromatic line or $s$ lines with one common focus and distinct colors. At $s=k$, the focus has one of the $k$ colors, so it completes the line carrying that color. This proves the theorem.

To deduce the Van der Waerden theorem, let $N=HJ(m,k)$ and color a word $(x_1,\dots ,x_N)\in [m{]}^N$ by the color of $x_1+\cdots +x_N$. On a combinatorial line with active set $I$, these sums area monochromatic arithmetic progression of length $m$.

The Strengthened Van der Waerden theorem says that every finite coloring contains, for each prescribed $m$, a monochromatic setWe prove the finite form by induction on the number $k$ of colors. The case $k=1$ is immediate. Let $n$ work for $m$ and $k-1$ colors, and apply the ordinary Van der Waerden theorem to obtain a monochromatic progressionIf one of $d,2d,\dots ,nd$ has the progression's color, say $rd$, thenworks. Otherwise $d,2d,\dots ,nd$ use at most $k-1$ colors. By the induction hypothesis their indices contain $b,b+r,\dots ,b+(m-1)r$ together with $r$ in one color. Multiplying by $d$ yieldswhich is the required progression together with its common difference.

Restrict the coloring to the diagonal by setting $d(n)=c(n,n)$. We give the direct focusing proof of a monochromatic three-term arithmetic progression. For each $1\le s\le k$, induction constructs a finite interval in which either there is a monochromatic three-term progression or there are $s$ color-focused two-term progressions. The case $s=1$ is the pigeonhole principle. For the induction step, take sufficiently many equal blocks that two have identical color patterns. Translate the $s-1$ focused pairs in the first block to the second and join corresponding points. These give $s-1$ focused pairs at a translated focus; the pair formed by the old and translated focuses supplies the last one. If its color repeated one of the previous colors, the associated pair and the focus would already form a monochromatic three-term progression. Thus the alternative holds.

At $s=k$, the common focus has one of the $k$ colors and completes the pair of that color, so there are $a,r>0$ with $d(a)=d(a+r)=d(a+2r)$. Thereforeis the required monochromatic two-dimensional progression. This proves the result without invoking the Van der Waerden theorem as a black box.

For a single homogeneous equationwith nonzero integer coefficients, Rado theorem says that it is a partition regular equation exactly whenfor some nonempty $I\subseteq \{1,\dots ,r\}$.

For necessity, suppose no nonempty coefficient sum vanishes. Choose a prime $p$ dividing none of the finitely many nonzero numbers ${\sum }_{i\in I}{c}_i$. Colour $x\in \mathbb{N}$ by the first nonzero base-$p$ digitIf $x_1,\dots ,x_r$ had one colour, divide the equation by the least power of $p$ occurring among them and reduce modulo $p$. The terms of minimum valuation givefor a nonzero $u$, contradicting the choice of $p$.

For sufficiency, reorder so that $c_1+\cdots +c_t=0$. The standard focusing lemma derived from the Van der Waerden theorem says the following: given a finite colouring, a finite monochromatic solution of the first $j$ blocks of the columns condition can be chosen together with a common difference $d$ so that every bounded translate of every chosen entry by a multiple of $d$ retains its colour. To prove the lemma, refine the colour of $a$ to the finite vector $(\chi (a),\chi (2a),\dots ,\chi (Ra))$, apply van der Waerden to a sufficiently long progression in this refined colouring, and take a common multiple of the finitely many resulting coefficients as $d$.

Start with the zero-sum block $\{1,ldots,t\}$, for which equal variables already solve its contribution. Add each remaining coefficient as a singleton block. In one dimension its block sum is a rational multiple of any fixed nonzero earlier coefficient, so the focusing lemma chooses a bounded translate that cancels this new contribution while preserving the common colour. Induction over the remaining indices gives a monochromatic solution of the full equation. This proves the single-equation form of Rado's theorem.

Now let $a_1,ldots,a_n,b$ be positive and put $A=a_1+\cdots +a_n$. If $b=At$, then $x_1=\cdots =x_n=t$ is a monochromatic solution in every colouring. Conversely, every solution has $x_i\le b/a_i$. Give each integer at most $b/{\min }_i{a}_i$ its own colour and colour all larger integers with one extra colour. A monochromatic solution must have all $x_i=t$, so $b=At$. Thus the inhomogeneous equation is partition regular exactly when $A$ divides $b$.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.

An ultrafilter on the positive integers with every member containing finite arithmetic progressions of arbitrarily large length. The Van der Waerden theorem and ultrafilter selection from a partition-rich family give existence. Such an ultrafilter must contain the complement of every set with bounded arithmetic-progression length, and it is a nonprincipal ultrafilter. No corresponding ultrafilter can have an infinite arithmetic progression in every member, by the dyadic block obstruction to infinite arithmetic progressions.