Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 9 (Ramsey Theory)

For $a<b$, give the pair $\{a,b\}$ the color determined by $v_2(b-a)\mathrm{mod}2$, where $v_2$ is the 2-adic valuation: use red for even valuation and blue for odd valuation. This finite coloring works because the pairs $\{a,a+d\}$ and $\{a,a+2d\}$ have valuations $v_2(d)$ and $v_2(d)+1$. They therefore have opposite colors. In particular, no three-term arithmetic progression has all its pairs monochromatic.

For the second assertion, $m=1$ is immediate: every singleton is a blue complete arithmetic progression, since it has no pairs to check. Assume $m\ge 2$. If some $m$-term arithmetic progression has all its pairs blue, we are done. Otherwise, every such arithmetic progression contains a red pair. For each $(a,d)\in {\mathbb{N}}^2$, choose, say lexicographically, indices $0\le r<s<m$ for which $\{a+rd,a+sd\}$ is red, and color $(a,d)$ by this chosen pair $(r,s)$. This is a finite coloring with at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ colors.

We need a lattice pattern that works whichever pair becomes the common color. Fix, before applying the Gallai theorem for an integer lattice, the finite setTranslate $F$ into the positive quadrant and apply the Gallai theorem for an integer lattice to that translated pattern. Absorbing the translation into the base point gives integers $a_0,d_0$ and $q>0$ such that $(a_0,d_0)+qF\subseteq {\mathbb{N}}^2$ is monochromatic. Write $(r,s)$ for its common color. Since $(0,0)\in F$, the base point itself has positive coordinates.

For each $0\le i,j<m$, the parameter pointbelongs to that monochromatic copy and has chosen red pair $(r,s)$. Its red endpoints simplify toConsequently, puttinggives two $m$-term arithmetic progressions of positive common difference $q(s-r)$, with every cross-pair red. These arithmetic progressions really are disjoint: the parameter point corresponding to $i=m-1,j=0$ has positive second coordinate, so $d_0>q(m-1)$. HenceThis proves the arithmetic-progression bipartite Ramsey dichotomy, including the required disjointness.

Here is the matrix form of Rado's theorem. A matrix $A$ with entries in the rational numbers and columns $a_1,\dots ,a_n$ is a partition regular matrix if every finite coloring of the positive integers admits a vector $x\in {\mathbb{N}}^n$ whose coordinates are monochromatic and for which $Ax=0$. Its columns condition asks for an ordered partition into nonempty blocks $B_1,\dots ,B_s$, withRado's theorem states that these two conditions are equivalent. Coordinates need not be distinct; positivity is required for every coordinate.

First prove necessity using the finite separating-functional proof of the columns condition. Clearing denominators does not change either the kernel or the columns condition, so assume that $A$ has integer entries. For each pair of disjoint index sets $I,B\subseteq \{1,\dots ,n\}$, with $B$ nonempty, for which $b_B={\sum }_{i\in B}{a}_i$ is outside the rational linear span of the $I$-columns, choose an integer linear functional ${\ell }_{I,B}$ such thatSuch a linear functional exists: extend a basis over the rational numbers of the indicated linear span by $b_B$, prescribe values zero on the former basis and one on $b_B$, extend to a basis of the ambient vector space over the rational numbers, and then clear the functional's denominators. There are only finitely many pairs $(I,B)$. Choose a prime number $p$ larger than the absolute values of all their nonzero evaluations; if there are none, choose any prime number.

Color $x>0$ by its last nonzero digit coloring value, namelywhere $v_p$ is the P-adic valuation. By partition regularity, choose a positive solution $Ax=0$ all of whose coordinates have the same nonzero digit $u$. Group its indices into nonempty blocks $B_1,\dots ,B_s$ according to increasing distinct P-adic valuations ${\nu }_1<\cdots <{\nu }_s$.

Suppose that a block sum $b_j$ is outside the rational linear span of the earlier columns, and put $I=B_1\cup \cdots \cup B_{j-1}$, taking $I=\varnothing$ for $j=1$. Apply the selected linear functional ${\ell }_{I,B_j}$ to $Ax=0$. The earlier terms vanish exactly. Divide the remaining integer equality by $p^{{\nu }_j}$ and reduce modulo $p$. Later blocks vanish modulo $p$, while each coordinate in $B_j$ contributes its common digit $u$. We obtainwhich is impossible by the choice of $p$ and because $u\not\equiv 0(\mathrm{mod}p)$. Thus each block sum lies in the earlier linear span. For the first block, this span is zero, so $b_1=0$. This proves the columns condition.

For sufficiency, assume the columns condition and choose rational coefficients ${\lambda }_{ij}$, for $i\in B_1\cup \cdots \cup B_{j-1}$, such thatChoose a positive integer $c$ clearing all these coefficients' denominators and a positive integer $p$ with $p\ge |c{\lambda }_{ij}|$ for every coefficient. Use the permitted monochromatic m-p-c set theorem, in the suffix convention for an m-p-c set, to obtain positive generators $z_1,\dots ,z_s$ such that the full setis positive and monochromatic. The positivity of the full m-p-c set is important: we do not discard expressions that happen to be negative. For $i\in B_h$, setAll these coordinates belong to $D$, so they are positive and monochromatic. On collecting coefficients of each $z_j$, their matrix product isThis explicit Rado solution inside an m-p-c set proves sufficiency and completes the proof of Rado's theorem.

To deduce the Finite sums theorem directly from the columns condition, introduce one positive variable $y_F$ for each nonempty $F\subseteq \{1,\dots ,k\}$ and imposeFor $k=1$ there are no equations and any positive integer works. For $k\ge 2$, write $a_F$ for the column belonging to $y_F$. Partition the columns into blocks $B_j=\{F:\min F=j\}$ in the order $j=1,\dots ,k$. Consider the row indexed by a set $H$ with $|H|\ge 2$. The sum of the columns in $B_j$ has row valueFor $j=1$ this is always zero. For $j>1$ it equals one exactly for those $H$ with $\min H<j$ and $j\in H$. Each such $a_H$ is the negative coordinate vector in row $H$, and it belongs to an earlier block. Thereforewhich verifies the columns condition, rather than assuming the desired Finite sums theorem. Apply Rado's theorem to this system. Its monochromatic positive solution satisfies $y_F={\sum }_{i\in F}{x}_i$ with $x_i=y_{\{i\}}$, and hence

Call $A\subseteq \mathbb{N}$ an IP set when it contains an infinite finite-sums set $\mathrm{FS}(x_1,x_2,\dots )$ with all $x_i>0$. We first need the relative consequence of the Hindman theorem: a finite union can be an IP set only if one of its constituents is an IP set. This does not follow by simply applying the theorem to a coloring of all integers, because its monochromatic finite-sums set might lie outside the given set.

Here is a reduction that proves the partition regularity of IP sets. Suppose $\mathrm{FS}(x_i)\subseteq A$ and $A$ is finitely colored. Index the generators by $i\ge 0$. For $n>0$, let $S(n)$ be the set of positions of the nonzero digits in its binary expansion, and color $n$ by the color of ${\sum }_{i\in S(n)}{x}_i$. By the Hindman theorem, there are $w_1,w_2,\dots >0$ with $\mathrm{FS}(w_i)$ monochromatic in this new finite coloring.

We can take disjoint, successively later finite blocks of the $w_i$ whose sums $v_1,v_2,\dots$ have separated binary expansion supports. Start with $v_1=w_1$. Having chosen finitely many blocks, take $K$ larger than every binary position used in their sums. On a fresh tail of the $w_i$, consider $2^K+1$ partial sums, including the zero partial sum. Two have the same residue class modulo $2^K$, by the pigeonhole principle. Their positive difference is a consecutive block sum $v_{j+1}$ divisible by $2^K$. Discard all indices up to that block's end and repeat. Thus every bit of $v_{j+1}$ is above every bit in the preceding block sums.

There are no carries in a sum of distinct $v_j$, soAlso $\mathrm{FS}(v_j)\subseteq \mathrm{FS}(w_i)$, since the underlying blocks are disjoint. Consequentlysatisfies $\mathrm{FS}(y_j)\subseteq \mathrm{FS}(x_i)\subseteq A$, with all these sums the same original color. This proves the relative assertion. In particular, if $A_1\cup \cdots \cup A_r$ contains an infinite finite-sums set, color its points by the first constituent containing them and apply this argument; one $A_j$ is an IP set.

Let $\mathcal{I}$ be the family of sets that are not IP sets. It is closed under subsets and, by the preceding argument, under finite unions. It contains every finite set, since positive successive partial sums of an infinite sequence are unbounded. It does not contain $\mathbb{N}$. Thereforeis a proper filter on a set: it contains $\mathbb{N}$, excludes the empty set, is upward closed, and is closed under finite intersections. Its members are exactly the IP-star sets, the sets meeting every IP set. Indeed, failure to meet an IP set is equivalent to having an IP complement. This identifies the sets that must belong to the required ultrafilter.

Apply the ultrafilter lemma to extend the IP-star filter $\mathcal{F}$ to an ultrafilter $\mathcal{U}$. For completeness, Zorn lemma applies to its proper filter extensions ordered by inclusion, because the union of a chain is still a proper filter on a set. A maximal extension decides every set $A$: if $A$ cannot be adjoined while keeping the filter proper, some filter member is disjoint from $A$, forcing $A^c$ into the filter. This is the defining ultrafilter property.

If $A\in \mathcal{U}$ were not an IP set, then $A^c\in \mathcal{F}\subseteq \mathcal{U}$, contradicting properness. Hence every member of $\mathcal{U}$ contains an infinite finite-sums set. Conversely, any ultrafilter with finite-sums members must contain every IP-star set, since it cannot contain such a set's non-IP complement. Thus this construction captures precisely the forced filter, without making an unnecessary claim about idempotence.

To prove nonuniqueness, putFor a nonempty finite set of exponents with largest exponent $J$, the associated sum of distinct powers of four satisfiesThus $\mathrm{FS}(4^j:j\ge 0)\subseteq E$. Doubling the inequality givesso $\mathrm{FS}(2\cdot 4^j:j\ge 0)\subseteq E^c$. These alternating dyadic intervals contain disjoint IP sets.

Every member of $\mathcal{F}$ meets $E$ and also $E^c$, because it meets every IP set. A finite intersection of members of $\mathcal{F}$ is again a member, so both $\mathcal{F}\cup \{E\}$ and $\mathcal{F}\cup \{E^c\}$ have the finite intersection property. Extend the proper filters they generate to ultrafilters ${\mathcal{U}}_0$ and ${\mathcal{U}}_1$. Each extends $\mathcal{F}$, so the previous argument makes each an ultrafilter with finite-sums members. But $E\in {\mathcal{U}}_0$ and $E^c\in {\mathcal{U}}_1$, so

Write $X=[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, and $[M{]}^{\omega }$ for all infinite subsets of an infinite $M$. A family $Y\subseteq X$ is a Ramsey set of infinite subsets if for every infinite $M$ there is an infinite $L\subseteq M$ with either $[L{]}^{\omega }\subseteq Y$ or $[L{]}^{\omega }\cap Y=\varnothing$.

A non-Ramsey set of infinite subsets is obtained by finite-symmetric-difference parity colouring. Declare $A\sim B$ when their symmetric difference is finite, and use the axiom of choice to select a representative $R$ for each equivalence class. PutFor every infinite $L$, both $L$ and $L\setminus \{\min L\}$ belong to $[L{]}^{\omega }$ and have the same representative. Toggling one element changes the parity of the finite symmetric difference, so these two sets have opposite colors. Thus no $[L{]}^{\omega }$ is homogeneous, and $Y$ is not a Ramsey set of infinite subsets. Only finite differences are counted; no parity is being assigned to an infinite cardinal.

We use the Ellentuck topology for the star notation. Its basic neighborhoods arewhere $s$ is a finite stem (the initial segment of each member of the neighborhood) and every element of the infinite reservoir $A$ exceeds $\max s$; the empty stem is allowed. A star-nowhere dense set $N$ has star-closure with empty star-interior; a star-meagre set is a countable union of star-nowhere dense sets.

We need the following stem-preserving open-set conclusion: a star-open set $G$ has, in every $[s,A]$, an infinite $B\subseteq A$ such that $[s,B]\subseteq G$ or $[s,B]\cap G=\varnothing$. Here is the fusion proof for open Ellentuck sets, so that the precise form being used is explicit. A reservoir $T$ accepts a finite extension $t$ of $s$ when $[t,T]\subseteq G$, and rejects it when no infinite subreservoir accepts it. Every reservoir can be thinned to decide a prescribed stem: take an accepting subreservoir if one exists, and otherwise it already rejects. Acceptance and rejection are hereditary under further infinite thinning.

First thin $A$ to decide $s$. If it accepts, we have finished. Otherwise, choose successive points $b_0<b_1<\cdots$, thinning the unused tail after each selection to decide every stem $s\cup t$ with $t$ a subset of the finitely many points already selected. Each stage requires only finitely many decisions. The final set $B$ therefore decides every such finite extension, using the tail above its largest point. It rejects $s$.

For any rejected stem $s\cup t$, only finitely many possible next points $b$ of $B$ have accepting tails for $s\cup t\cup \{b\}$. Otherwise collect infinitely many such points into $C$. Every member of $[s\cup t,C]$ starts with some such $b$, and its remaining points lie in the accepting tail above $b$. Hence $[s\cup t,C]\subseteq G$, contradicting rejection. A second selection now gives $C\subseteq B$ all of whose finite extensions of $s$ are rejected: at each stage avoid the finitely many forbidden next points for each subset of the chosen prefix. Previous rejections persist on thinning. If $Z\in [s,C]\cap G$, star-openness gives an initial stem $s\cup t$ of $Z$ and an infinite tail of $Z$ whose entire neighborhood lies in $G$. This is an accepting subreservoir for a stem we made rejected, a contradiction. Thus $[s,C]\cap G=\varnothing$, proving the needed open-set conclusion.

Apply this conclusion to $G=X\setminus {\overline{N}}^{\ast }$ when $N$ is star-nowhere dense. This $G$ is star-open and star-dense. The alternative $[s,B]\cap G=\varnothing$ would give a nonempty star-open set inside ${\overline{N}}^{\ast }$, contradicting empty interior. Consequently every star-nowhere dense set can be avoided without extending the finite stem.

Now let $N={\bigcup }_{j\ge 0}{N}_j$, each $N_j$ star-nowhere dense, and fix $[s,A]$. Construct $b_0<b_1<\cdots$ with nested infinite unused reservoirs. At stage $j$, let $P_j=\{b_0,\dots ,b_{j-1}\}$. For every $t\subseteq P_j$, in turn, thin the current reservoir using the preceding avoidance property untilThere are only finitely many such $t$, and subsequent thinning preserves all previous avoidances. Choose $b_j=\min C_j$ and retain the part of $C_j$ above $b_j$ for the next stage. Put $B=\{b_j:j\ge 0\}$. For any $Z\in [s,B]$ and any $j$, the finite part $t=(Z\setminus s)\cap P_j$ is one of the stems tested at stage $j$, and the rest of $Z\setminus (s\cup t)$ lies in $C_j$. Hence $Z\in [s\cup t,C_j]$ and $Z\notin N_j$. This proves $[s,B]\cap N=\varnothing$.

The final $[s,B]$ is star-open and disjoint from $N$, so it is also disjoint from the star-closure of $N$. Every basic neighborhood therefore has a nonempty open refinement missing that closure. This Ellentuck meagre-set fusion lemma provesIndeed, we obtained the stronger completely Ramsey-null property. Testing all subsets of the selected prefix was essential; testing just the entire prefix would not cover every infinite subset of $B$.

Take $\tau$ to be the ordinary topology on infinite subsets, whose basic cylinders $[s]$ fix a finite initial segment. LetThis is a dense countable family of cofinite infinite subsets. It is countable because finite complements form a countable family. Each singleton is $\tau$-closed: distinct increasing enumerations differ at some finite coordinate, which separates them by cylinders. No singleton has interior, since every cylinder admits more than one infinite continuation. Thus every singleton is $\tau$-nowhere dense, and $D$ is $\tau$-meagre.

On the other hand, every cylinder $[s]$ contains the cofinite set $s\cup \{n:n>\max s\}$, with $\max \varnothing =0$. Hence $D$ is $\tau$-dense, its closure is all of $X$, and

The paper does not define its symbol $\tau$. If the course instead uses it for the Ramsey cone topology, with basic neighborhoods $[A{]}^{\omega }$ and no finite stem, use $X$ itself as the example. For $D_j=\{Z:\min Z=j\}$, its cone-closure is $\{Z:j\in Z\}$: every cone neighborhood of a set containing $j$ contains an infinite subset of minimum $j$, while a cone based on a set omitting $j$ misses $D_j$. This closure has empty interior, because every infinite reservoir can be thinned to omit $j$. Thus every $D_j$ is cone-nowhere dense, and $X={\bigcup }_{j\ge 1}{D}_j$ is cone-meagre but is not cone-nowhere dense. This supplies the requested example under either convention, without conflating the two topologies.

For $n\ge 1$, let $C_n=\{Z\in X:n\notin Z\}$. The presence or absence of $n$ is determined by a sufficiently long finite initial segment, so $C_n$ and its complement are open sets in the ordinary topology on infinite subsets. The Ellentuck topology is finer, hence each $C_n$ is star-clopen and in particular star-closed. Their union isEvery basic star-neighborhood $[s,A]$ of $\mathbb{N}$ has $s=\{1,\dots ,k\}$ for some $k\ge 0$, and its reservoir $A$ contains every integer greater than $k$. Choosing $n>k$ gives $\mathbb{N}\setminus \{n\}\in [s,A]\cap C_n$. Thus $\mathbb{N}$ is in the star-closure of the union, but not in the union itself. Therefore