Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 10 (Ramsey Theory)

For $m=1$ the conclusion is immediate, so suppose $m\ge 2$ and index the terms of an arithmetic progression by $0,\dots ,m-1$. There are only finitely many equivalence relations on this index set. Consequently, recording which terms have equal colours produces a finite colouring of the positive parameter pairs $(a,d)$, even though the original colouring need not be finite.

We use the Gallai theorem for an integer lattice in this form: a finite colouring of the positive integer lattice contains a monochromatic homothetic copy of any prescribed finite integer pattern. Patterns with negative coordinates are allowed here by first translating them into the positive quadrant; the translation is absorbed into the base point of the resulting copy.

Consider the finite patternThe Gallai theorem for an integer lattice supplies integers $a_0,d_0$ and $q>0$ such that every point of $(a_0,d_0)+qF$ lies in the positive quadrant and has the same equality equivalence relation $E$. If $E$ has only singleton classes, any parameter pair in this copy gives an arithmetic progression whose colours are pairwise distinct, so the original colouring is injective on it.

Otherwise choose $r<s$ with $rEs$. For every $u,v\in \{0,\dots ,m-1\}$, the parameter pairhas relation $E$. Its terms at indices $r$ and $s$ are therefore equally coloured. But these terms simplify toThus $c(A_u)=c(B_v)$ for every $u,v$. Fixing $v=0$ proves that all $A_u$ have the same colour. Every $A_u$ is positive, because it is a term of one of the positive-parameter progressions above, and the common difference $q(s-r)$ is positive. Hence $(A_u{)}_{u=0}^{m-1}$ is a monochromatic arithmetic progression of length $m$.

The canonical arithmetic progression dichotomy is therefore constant or injective on an arithmetic progression of the prescribed length. The key point is that one equal-colour index pair has been made to vary independently over two complete progressions; a merely monochromatic block of parameter pairs would not by itself give this conclusion.

Van der Waerden theorem. Given positive integers $r,k$, there is a finite $W(r,k)$ such that every finite colouring of $\{1,\dots ,W(r,k)\}$ with at most $r$ colours has a monochromatic arithmetic progression of length $k$ and positive common difference. In particular, every finite colouring of the positive integers contains such progressions of every finite length.

Here is a colour-focusing proof of Van der Waerden theorem. We induct on $k$, simultaneously for all numbers of colours. The assertion for $k=1$ is immediate. Suppose $W(r,k)$ exists for every $r$, and fix $r$. We construct bounds $F_t$, for $1\le t\le r$, with this property: every colouring of $[F_t]$ either has a monochromatic progression of length $k+1$, or has $t$ progressions of length $k$, of distinct colours, which share a next point $f\in [F_t]$. Write those progressions aswith positive steps $d_i$ and all displayed points in $[F_t]$.

For $t=1$, put $L=W(r,k)$ and $F_1=2L$. A monochromatic progression of length $k$ in $[L]$ has its next point in $[2L]$, since its step is at most $L$; for $k=1$ choose step $1$. This establishes the initial focusing property.

Suppose $F_t=N$ has been constructed. Put $M=W(r^N,k)$ and $F_{t+1}=2NM$. Divide the first $NM$ integers into $M$ consecutive blocks of size $N$. Colour a block by its full colour profile, an $N$-tuple having at most $r^N$ possible values. The induction hypothesis on $k$ gives block indiceswith the same colour profile. For $k=1$ use any one block and $D=1$. Suppose that the whole interval has no monochromatic progression of length $k+1$. Its repeated profile has $t$ focused length-$k$ progressions with positions $f-h{d}_i$ and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$, since equality would complete a length-$(k+1)$ progression in the block.

Set $j_{\ast }=j_0+kD$ and $F=N(j_{\ast }-1)+f$. The index $j_{\ast }$ is at most $2M$, so this focus is in the full interval. For $1\le h\le k$, the pointis in one of the chosen blocks and has colour $q_i$. Also $F-hND$ is at position $f$ in that block and has colour $q$. We have produced $t+1$ focused length-$k$ progressions of distinct colours. This proves the recursive focusing property. At $t=r$, the focus itself must have one of the $r$ colours, so one of the progressions extends to length $k+1$. Thus $W(r,k+1)=F_r$ is a valid bound, completing the mathematical induction and the requested proof.

To obtain the equation criterion, we first prove the small strengthening of Van der Waerden theorem that we need. For any positive integers $r,s,L$, there is a finite bound forcing a monochromatic configurationThis is the Brauer progression theorem, and the following argument proves it from the theorem just established. Induct on $r$. One colour is immediate. Given a bound $M$ for $r-1$ colours with the same $s,L$, let $T=W(r,(L-1)M+1)$ and colour an interval at least as long as $\max (T,sMT)$. Find a monochromatic progression $a,a+d,\dots ,a+(L-1)Md$ in $[T]$, of colour $q$; take $d=1$ if this progression has one term. If some $jsd$, $1\le j\le M$, has colour $q$, its first $L$ suitably spaced terms $a,a+jd,\dots ,a+(L-1)jd$ and the point $s(jd)$ give the configuration. Otherwise the colouring of the indices $1,\dots ,M$ obtained from $j\mapsto c(jsd)$ uses at most $r-1$ colours. The induction hypothesis supplies indices $se,b,b+e,\dots ,b+(L-1)e$ of one colour. Multiplication by $sd$ gives the desired configuration with step $esd$. This completes the strengthening without assuming any Rado theorem.

Multiply the rational coefficients by a common positive denominator, so that all $a_i$ are nonzero integers; this does not alter the equation or partition regularity. By definition, the row is partition regular when every finite colouring admits positive monochromatic $x_1,\dots ,x_n$ satisfying ${\sum }_i{a}_i{x}_i=0$. The variables need not be distinct.

For necessity, choose a prime number $p>{\sum }_i|a_i|$. Write each positive $x$ uniquely as $p^{v_p(x)}u$, with $p\nmid u$, and colour $x$ by $u\mathrm{mod}p$. This is a finite colouring with $p-1$ colours. If a monochromatic solution exists, let $v={\min }_i{v}_p(x_i)$ and $I=\{i:v_p(x_i)=v\}$. Dividing the equation by $p^v$ and reducing modulo $p$ giveswhere $u_0\ne 0(\mathrm{mod}p)$ is the common colour. Thus ${\sum }_{i\in I}{a}_i\equiv 0(\mathrm{mod}p)$. Its absolute value is strictly less than $p$, so ${\sum }_{i\in I}{a}_i=0$. The index set $I$ is nonempty. This proves the leading-residue obstruction to partition regularity.

Conversely, suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. If $I$ is all indices, taking every variable equal to any one positive integer already gives a monochromatic solution. Otherwise fix $i_0\in I$, put $s=|a_{i_0}|$, $C={\sum }_{j\notin I}{a}_j$, and define integer offsetsLet $u={\min }_{i\in I}{\lambda }_i$ and choose $L=1+{\max }_{i\in I}{\lambda }_i-u$. The proved Brauer progression theorem gives a monochromatic configuration consisting of $sd$ and a length-$L$ progression starting at $b$. SetAll variables are positive and of one colour. Their weighted sum isThis explicitly gives a Brauer configuration for a one-row zero-sum equation. We concludeBoth directions have been proved independently of the general Rado theorem.

We take $\mathbb{N}=\{1,2,\dots \}$. An ultrafilter $p$ on $\mathbb{N}$ is a proper filter on a set which decides every subset: it contains $\mathbb{N}$ but not $\varnothing$, is closed under finite intersections and passage to supersets, and contains exactly one of $A$ and $\mathbb{N}\setminus A$ for every $A\subseteq \mathbb{N}$. A principal ultrafilter has the form ${\delta }_n=\{A:n\in A\}$; all other ultrafilters are nonprincipal ultrafilters.

To prove existence, start with the cofinite filter and order its proper filter extensions by inclusion. The union of a chain is again a proper filter on a set: the finitely many sets involved in an intersection all belong to one member of the chain, and no member contains the empty set. Thus Zorn's lemma supplies a maximal proper filter $p$. If $A\notin p$, adjoining $A$ must make the generated filter improper; equivalently, some $B\in p$ has $A\cap B=\varnothing$. Then $B\subseteq \mathbb{N}\setminus A$, so $\mathbb{N}\setminus A\in p$. This proves that $p$ is an ultrafilter. It contains the complement of every finite set and hence no finite set. In particular, it contains no singleton and is nonprincipal.

The Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ is the set of all ultrafilters with basic open setsWe have $\hat{A}\cap \hat{B}=\widehat{A\cap B}$ and $\beta \mathbb{N}\setminus \hat{A}=\widehat{\mathbb{N}\setminus A}$, so these basic sets define a topology and are clopen sets. If $p\ne q$, choose $A\in p\setminus q$. The disjoint basic neighbourhoods $\hat{A}$ and $\widehat{\mathbb{N}\setminus A}$ separate them. Thus the space is Hausdorff.

For compactness, it suffices to show every basic open cover has a finite subcover, since an arbitrary open cover can be refined by basic open sets. Suppose $\{\widehat{A_i}:i\in I\}$ has no finite subcover. The complements $\mathbb{N}\setminus A_i$ have the finite intersection property: if a finite intersection were empty, the corresponding finite family of $\widehat{A_i}$ would cover every ultrafilter. Their generated proper filter on a set extends to an ultrafilter, by the same Zorn's lemma argument. This ultrafilter contains every $\mathbb{N}\setminus A_i$, and therefore belongs to none of the alleged cover members, a contradiction. We have proved that $\beta \mathbb{N}$ is a compact Hausdorff space. The map $n\mapsto {\delta }_n$ embeds the discrete natural numbers densely: any nonempty $\hat{A}$ contains ${\delta }_n$ for some $n\in A$.

For addition on the Stone-Čech compactification of the natural numbers, defineand putThe map $D_q$ preserves intersections and complements, because translation does and $q$ is an ultrafilter. It also sends $\mathbb{N}$ to $\mathbb{N}$ and the empty set to itself. Consequently the displayed rule defines an ultrafilter $p+q$. On principal points it satisfies ${\delta }_n+{\delta }_m={\delta }_{n+m}$, so it extends ordinary addition.

Write $({\forall }^{p}n)\phi (n)$ to mean that $\{n:\phi (n)\}\in p$. The ultrafilter addition rule is then an iterated quantifier, with its order fixed. Expansion givesOrdinary addition is an associative operation, and the quantifiers are in the same order on both lines. Thus $\boxed{(p+q)+r=p+(q+r)}$. This argument does not interchange ultrafilter quantifiers and does not assert that this extended addition is commutative.

For fixed $q$, the translation $R_q:p\mapsto p+q$ hasa basic clopen set. Therefore addition is continuous in its left variable. This is the left-continuity convention used here: right translations are continuous, giving a left-topological semigroup. Continuity in both variables jointly is not part of the assertion.

Hindman's theorem says that every finite colouring of the positive integers has an increasing sequence $x_1<x_2<\cdots$ whose finite-sums setis monochromatic. Assume, as permitted, that the addition just defined has an idempotent ultrafilter $p$, so $p+p=p$. This ultrafilter is nonprincipal: a principal ${\delta }_n$ would satisfy ${\delta }_n+{\delta }_n={\delta }_{2n}\ne {\delta }_n$ for positive $n$. Hence every member of $p$ is infinite and every cofinite set belongs to $p$.

Exactly one cell $A$ of the finite colour partition belongs to $p$. Define its star set bySince $A\in p+p$, we have $D_p(A)\in p$ and therefore $A^{\ast }\in p$. Moreover, for each $n\in A^{\ast }$, the set $A-n$ belongs to $p$. Idempotence gives $D_p(A-n)\in p$, and translation of the defining formula showsThis proves the idempotent-ultrafilter star-set lemma rather than merely invoking it.

Choose $x_1\in A^{\ast }$. Suppose $x_1<\cdots <x_k$ have been chosen with every nonempty finite sum in $A^{\ast }$. Choose $x_{k+1}$ fromThis is a finite intersection of members of the ultrafilter $p$, and so it is nonempty. The new sums are $x_{k+1}$ and $s+x_{k+1}$; all lie in $A^{\ast }$ by the choice. Mathematical induction yields an increasing infinite sequence withThus the assumed idempotent gives the full Hindman theorem, with distinct increasing generators and all their nonempty finite sums of one colour.

Write $[A{]}^{\omega }$ for the infinite subsets of an infinite $A\subseteq \mathbb{N}$. A Ramsey set of infinite subsets is a family $E\subseteq [\mathbb{N}{]}^{\omega }$ such that each infinite ground set $A$ has an infinite subset $B$ withThe convention asking only for one such homogeneous cone is weaker; the proof below establishes the displayed property and, in fact, the stronger completely Ramsey set property.

For a finite stem $s$ and an infinite reservoir $A$ lying above every element of $s$, putThese sets form the basic open neighbourhoods of the Ellentuck topology, or star topology. Here $s$ is an initial segment of every member of $[s,A]$. A star-Borel set means a member of the sigma-algebra generated by these open sets. A family is completely Ramsey if every $[s,A]$ has a homogeneous refinement $[s,B]$ with $B\subseteq A$ infinite and the same stem $s$. We prove this for every star-Borel set, beginning with open sets.

Fix a star-open family $O$ and a basic neighbourhood $[s,A]$. An infinite reservoir $T$ above a finite stem $t$ accepts $t$ if $[t,T]\subseteq O$. It rejects $t$ if no infinite subset of $T$ accepts $t$. A reservoir decides $t$ if it accepts or rejects it. Any reservoir has a refinement deciding a prescribed stem: take an accepting refinement if there is one, and otherwise the current reservoir rejects. Both kinds of decision persist under infinite thinning.

First refine $A$ to decide $s$. If the decision is acceptance, the required homogeneous neighbourhood has already been found. Suppose it is rejection. We use deciding all finite stems by fusion to selectfrom nested infinite reservoirs. After selecting $b_n$, successively thin the remaining reservoir to decide every stem $s\cup a$ with $a\subseteq \{b_1,\dots ,b_n\}$. There are only finitely many such $a$, so every stage can be completed. Choose $b_{n+1}$ from that thinned reservoir and repeat. Let $B=\{b_1,b_2,\dots \}$. For every finite $a\subseteq B$, the taildecides $s\cup a$; for $a=\varnothing$, use all of $B$. Indeed, the stem was decided at the stage when its largest point was selected, and its final tail is a subset of the reservoir retained at that stage. The empty stem remains rejected by the initial decision.

The crucial finite-obstruction fact is that a rejected stem has only finitely many accepting one-point extensions. More precisely, suppose $B/a$ rejects $s\cup a$. If infinitely many $b\in B/a$ had $B/b$ accepting $s\cup a\cup \{b\}$, collect those $b$ into an infinite $C$. Any $X\in [C{]}^{\omega }$ has a least point $b$, and its remaining tail lies in $B/b$. Acceptance at $b$ would then imply $s\cup a\cup X\in O$. Thus $C$ would accept $s\cup a$, contradicting rejection. This proves the finitely many accepting extensions of a rejected stem assertion with the reservoirs specified.

Thin $B$ a second time. Having selected a finite prefix of $C$, maintain that every stem $s\cup a$ with $a$ a subset of that prefix is rejected relative to its tail in $B$. Each such stem has finitely many forbidden next points leading to acceptance. Choose the next point of $C$ above the prefix and outside the union of these finitely many finite forbidden sets. The deciding property of $B$ then makes every newly created stem rejected. Starting with the rejected empty extension gives an infinite $C\subseteq B$ all of whose finite extensions of $s$ are rejected.

We claim $[s,C]\cap O=\varnothing$. Otherwise take $Y\in [s,C]\cap O$. Star-openness supplies a basic neighbourhood inside $O$ containing $Y$. Extend its finite stem along $Y$ until it contains $s$; the new stem has the form $s\cup a$ for a finite initial segment $a$ of $Y\setminus s$. The remaining infinite tail of $Y$ is a subset of $B/a$ and accepts that stem, contradicting rejection. This proves the fusion proof for open Ellentuck sets: every star-open set is completely Ramsey.

Next call $N$ completely Ramsey-null if every $[s,A]$ has a same-stem refinement disjoint from $N$. Every star-nowhere dense set is completely Ramsey-null. Indeed, the complement $D$ of its star-closure is star-open and dense. Apply the just-proved open-set result inside $[s,A]$. The homogeneous alternative disjoint from $D$ would be a nonempty open set contained in the closure of a nowhere-dense set, which is impossible. Hence some $[s,B]$ lies entirely in $D$ and avoids $N$.

Countable unions of completely Ramsey-null sets are again completely Ramsey-null. Here is the full Ellentuck meagre-set fusion lemma. Given $N_1,N_2,\dots$ and $[s,A]$, construct selected prefixes $P_j=\{b_1,\dots ,b_j\}$ and nested unused infinite reservoirs. At stage $j$, refine the reservoir, still lying above $\max P_j$, to arrangeEach constraint can be imposed by complete Ramsey-nullness, with all earlier constraints preserved by thinning; there are finitely many constraints. Choose $b_{j+1}\in T_j$ and retain the tail above it for the next stage. Start with $P_0=\varnothing$ and the reservoir $A$.

Let $B=\{b_1,b_2,\dots \}$. If $Y\in [s,B]$ and $i$ is fixed, take any $j\ge i-1$ and put $a=(Y\setminus s)\cap P_j$. Every remaining point of $Y\setminus s$ lies in $T_j$, so $Y\in [s\cup a,T_j]$ and $Y\notin N_i$. ThereforeThis construction handles all subsets of a selected prefix, not merely the full prefix: members of $[s,B]$ may skip arbitrarily many selected points. Since a meagre set is a countable union of nowhere-dense sets, every star-meagre set is completely Ramsey-null.

It remains to pass from star-open sets to star-Borel sets. Let $\mathcal{C}$ consist of the families $E$ expressible aswhere $O$ is star-open and $M$ is star-meagre. We verify directly that $\mathcal{C}$ is a sigma-algebra. It contains every open set. Countable unions remain in $\mathcal{C}$, becauseand a countable union of meagre sets is meagre. For complements, replace $O^c$ by the open set $\mathrm{int}(O^c)$. The omitted part is $\overline{O}\setminus O$, the boundary of the open set $O$, which is closed and nowhere dense: a nonempty open subset of $\overline{O}$ must meet $O$, so it cannot lie in this boundary. Thusa meagre set. Subsets of meagre sets are meagre as well, since taking a subset preserves nowhere denseness. These observations prove the claimed sigma-algebra property. Hence every star-Borel set belongs to $\mathcal{C}$.

Finally, for $E△O\subseteq M$ and any $[s,A]$, first use complete Ramsey-nullness to obtain $[s,B]$ avoiding $M$. On that neighbourhood $E$ and $O$ coincide. Apply the open-set result to $O$ within $[s,B]$ to get a homogeneous $[s,C]$. ThereforeTaking $s=\varnothing$ gives the requested homogeneous infinite-subset cone inside any given infinite ground set. Every closure, interior, open set and meagreness used in this proof refers to the Ellentuck topology; substituting the coarser ordinary topology at an intermediate step would change the assertion.