Ramsey Theory

I.B. Leader

Michaelmas 2000

1 Monochromatic Systems

1.1 Ramsey’s Theorem

We write ℕ for the set {1, 2, 3, … } of positive integers. For any positive integer n, we write [n] = {1, 2, …, n}. For any set X, we denote the set {A ⊂ X : |A| = r} of subsets of X of size r by X^{(r)}.

By a k-colouring of ℕ^{(r)}, we mean a map c: ℕ^{(r)} → [k]. We say that a set M ⊂ ℕ is monochromatic for c if c|_{M^{(r)}} is constant.

Theorem 1 (Ramsey’s Theorem). Whenever ℕ^{(2)} is 2-coloured, there exists an infinite monochromatic set.

Proof. Pick a_{1} ∈ ℕ. There are infinitely many edges from a_{1}, so we can find an infinite set B_{1} ⊂ ℕ − {a_{1}} such that all edges from a_{1} to B_{1} are the same colour c_{1}.

Now choose a_{2} ∈ B_{1}. There are infinitely many edges from a_{2} to points in B_{1} − {a_{2}}, so we can find an infinite set B_{2} ⊂ B_{1} − {a_{2}} such that all edges from a_{2} to B_{2} are the same colour, c_{2}.

Continue inductively. We obtain a sequence a_{1}, a_{2}, a_{3}, … of distinct elements of ℕ, and a sequence c_{1}, c_{2}, c_{3} of colours such that the edge a_{i}a_{j} (i < j) has colour c_{i}. Plainly we must have c_{i_{1}} = c_{i_{2}} = c_{i_{3}} = ⋯ for some infinite subsequence. Then {a_{i_{1}}, a_{i_{2}}, a_{i_{3}}, …} is an infinite monochromatic set. The result follows.

Remarks. 1. The same proof shows that if ℕ^{(2)} is k-coloured then we get an infinite monochromatic set. Alternatively, we could view ‘1’ and ‘2 or 3 or … or k’ as a 2-colouring of ℕ^{(2)}, and then apply Theorem 1 and use induction on k.

2. An infinite monochromatic set is much more than having arbitrarily large finite monochromatic sets. For example, consider the colouring in which all edges within each of the sets {1, 2}, {3, 4, 5}, {6, 7, 8, 9}, {10, 11, 12, 13, 14}, {15, 16, 17, 18, 19, 20}, … are coloured blue and all other edges are coloured red. Here there is no infinite blue monochromatic set, but there are arbitrarily large finite monochromatic blue sets.

Example. Any sequence (x_{n})_{n∈ℕ} in a totally ordered set has a monotone subsequence: colour ℕ^{(2)} by giving ij (i < j) colour UP if x_{i} < x_{j} and colour DOWN otherwise; the result follows by Theorem 1.

Theorem 2. Whenever ℕ^{(r)} is 2-coloured, there exists an infinite monochromatic set.

Proof. The proof is by induction on r, the case r = 1 being trivial.

Suppose the result holds for r − 1. Given c: ℕ^{(r)} → [2], pick a_{1} ∈ ℕ. Define a 2-colouring c′ of (ℕ − {a_{1}})^{(r−1)} by c′(F) = c(F ∪ {a_{1}}) for all F ∈ (ℕ − {a_{1}})^{(r−1)}. By induction, there exists an infinite monochromatic set B_{1} ⊂ ℕ−{a_{1}} for c′; i.e. there exists a colour c_{1} such that c(F ∪{a_{1}}) = c_{1} for all F ∈ B_{1}^{(r−1)}.

Now choose a_{2} ∈ B_{1}. In exactly the same way, we get an infinite set B_{2} ⊂ B_{1} − {a_{2}} and a colour c_{2} such that c(F ∪{a_{2}}) = c_{2} for all F ∈ B_{2}^{(r−1)}.

Continue inductively: we obtain a sequence a_{1}, a_{2}, a_{3}, … of distinct elements of ℕ and colours c_{1}, c_{2}, c_{3}, … such that for any i_{1} < i_{2} < ⋯ < i_{r} we have c({a_{i_{1}}, a_{i_{2}}, …, a_{i_{r}}}) = c_{i_{1}}. But we must have c_{i_{1}} = c_{i_{2}} = c_{i_{3}} = ⋯ for some infinite subsequence. Then {a_{i_{1}}, a_{i_{2}}, a_{i_{3}}, … } is an infinite monochromatic set. The result follows.

Example. We saw that, given any (1, x_{1}), (2, x_{2}), (3, x_{3}), … in ℝ^{2} we could pick a subsequence inducing a monotone function. In fact we can insist that the induced function is convex or concave: colour ℕ^{(3)} by giving ijk (i < j < k) the colour convex or concave according as the corresponding points form a convex or concave triple. The result follows by Theorem 2.

We can deduce the finite form of Ramsey’s Theorem from Theorem 2.

Corollary 3. Let m, r ∈ ℕ. Then there exists n ∈ ℕ such that whenever [n]^{(r)} is 2-coloured there is a monochromatic set M ∈ [n]^{(m)}.

Proof. Suppose not. We construct a 2-colouring of ℕ^{(r)} without a monochromatic m-set, contradicting Theorem 2.

For each n ≥ r, we have a colouring c_{n}: [n]^{(r)} → [2] with no monochromatic m-set. There are only finitely many ways to colour [r]^{(r)} (two in fact) so infinitely many of c_{r}|[r]^{(r)}, c_{r+1}|[r]^{(r)}, c_{r+2}|[r]^{(r)}, … agree; say c_{i}|[r]^{(r)} = d_{r} for all i lying in some infinite set A_{1}, where d_{r} is some colouring of [r]^{(r)}. Among the c_{i} for i ∈ A_{1}, infinitely many must agree on [r+1]^{(r)}; say c_{i}|[r+1]^{(r)} = d_{r+1} for all i ∈ A_{2}, where d_{r+1} : [r + 1]^{(r)} → [2] and A_{2} ⊂ A_{1} is infinite.

Continue inductively: we obtain colourings d_{n}: [n]^{(r)} → [2] for n = r, r + 1, r + 2, … such that

(i) no d_{n} has a monochromatic m-set (as there is some k such that d_{n} = c_{k}|[n]^{(r)}); and

(ii) for all n, d_{n+1}|[n]^{(r)} = d_{n}.

Define a colouring c: ℕ^{(r)} → [2] by c(F) = d_{n}(F) for any n ≥ max F. This is well-defined by (ii), and has no monochromatic m-set by (i). So we have our contradiction. The result follows.

Remarks. 1. This proof gives no information about the minimal possible n(m, r). There are direct proofs which give upper bounds.

2. The above is a compactness proof: what we did was (essentially) show that {0, 1}^{ℕ} with the product topology (i.e. the topology derived from the metric d(f, g) = 1/ min{n : f(n) ≠ g(n)}) is compact.

Theorem 4 (The Canonical Ramsey Theorem). Whenever we have a colouring of ℕ^{(2)} with an arbitrary set of colours, there exists an inginite set M such that

(i) c is constant on M^{(2)}; or

(ii) c is injective on M^{(2)}; or

(iii) c(ij) = c(kl) iff i = k (for all i, j, k, l ∈ M with i < j and k < l); or

(iv) c(ij) = c(kl) iff j = l (for all i, j, k, l ∈ M with i < j and k < l).

Note that this theorem implies Theorem 1: if we have only a finite set of colours then (ii), (iii) and (iv) are impossible.

Proof. First 2-colour ℕ^{(4)} by giving ijkl (by which we mean henceforth i < j < k < l) colour YES if c(ij) = c(kl) and colour NO if c(ij) ≠ c(kl). By Ramsey for 4-sets, we have an infinite monochromatic set M. If M is coloured YES then M is monochromatic for c (for given any ij and kl in M^{(2)}, choose any m < n in M with m > i, j, k, l; then c(ij) = c(mn) = c(kl).) So in this case (i) holds.

Suppose then that M is coloured NO. Now 2-colour M^{(4)} by giving ijkl colour YES if c(il) = c(jk) and colour NO if c(il) ≠ c(jk). Again by Ramsey, there exists an infinite M′ ⊂ M monochromatic for this colouring. If M′ is YES, choose x_{1} < x_{2} < x_{3} < x_{4} < x_{5} < x_{6} in M′; then c(x_{2}x_{3}) = c(x_{1}x_{6}) = c(x_{4}x_{5}), a contradiction.

So M′ is colour NO. Now 2-colour M^{′(4)} by giving ijkl colour YES if c(ik) = c(jl) and colour NO is c(ik) ≠ c(jl). By Ramsey, we have an infinite monochromatic set M′′ ⊂ M′. If M′′ is colour YES then choose x_{1} < x_{2} < x_{3} < x_{4} < x_{5} < x_{6} in M′′; then c(x_{1}x_{3}) = c(x_{2}x_{5}) = c(x_{4}x_{6}), a contradiction.

So M′′ is colour NO. Now 2-colour M^{′′(3)} by giving ijk colour LEFT-SAME if c(ij) = c(ik) and colour LEFT-DIFF if c(ij) ≠ c(ik). We get an infinite M′′′ ⊂ M′′ monochromatic for this colouring. Then 2-colour M^{′′′(3)} by giving ijk colour RIGHT-SAME if c(ik) = c(jk) and colour RIGHT-DIFF if c(ik) ≠ c(jk). We get an infinite monochromatic M′′′′ ⊂ M′′′. Finally, 2colour M^{′′′′(3)} by giving ijk colour MID-SAME if c(ij) = c(jk) and colour MID-DIFF if c(ij) ≠ c(jk). We get an infinite monochromatic M′′′′′ ⊂ M′′′′.

If M′′′′′ is colour MID-SAME, choose x_{1} < x_{2} < x_{3} < x_{4} in M′′′′′; then c(x_{1}x_{2}) = c(x_{2}x_{3}) = c(x_{3}x_{4}), a contradiction. So M′′′′′ is MID-DIFF.

If M′′′′′ is LEFT-SAME and RIGHT-SAME then it would also be MID-SAME, a contradiction.

If M′′′′′ is LEFT-SAME and RIGHT-DIFF then (iii) holds.

If M′′′′′ is LEFT-DIFF and RIGHT-SAME then (iv) holds.

If M′′′′′ is LEFT-DIFF and RIGHT-DIFF then (ii) holds.

Remark. We could do it all in one colouring of ℕ^{(4)} by colouring x_{1}x_{2}x_{3}x_{4} with the partition of [4]^{(2)} induced by c on {x_{1}, x_{2}, x_{3}, x_{4}}. The number of colours would be the number of partitions of a set of size \binom{4}{2}. In the same way, we can show that if we arbitrarily colour ℕ^{(r)} we get an infinite M ⊂ ℕ and a set I ⊂ [r] such that for any x_{1}, x_{2}, …, x_{r}, y_{1}, y_{2}, …, y_{r} ∈ M^{(r)} we have

c(x_{1}, x_{2}, …, x_{r}) = c(y_{1}, y_{2}, …, y_{r}) ⟺ x_{i} = y_{i} for all i ∈ I.

So in Theorem 4, I = ∅ is (i), I = {1, 2} is (ii), I = {1} is (iii) and I = {2} is (iv). These 2^{r} colourings are called the canonical colourings of ℕ^{(r)}.

1.2 Van der Waerden’s Theorem

In this theorem we shall show:

whenever ℕ is 2-coloured, for all m ∈ ℕ there exists a monochromatic arithmetic progression of length m (i.e. a, a + d, a + 2d, …, a + (m − 1)d all the same colour).

By the familiar compactness argument, this is the same as:

for all m ∈ ℕ, there exists n ∈ ℕ such that whenever [n] is 2coloured, there exists a monochromatic arithmetic progression of length m.

In our proof (of the second form above), we use the following key idea: we show more generally that for all k, m ∈ ℕ, there exists n such that whenever [n] is k-coloured, there exists a monochromatic arithmetic progression of length m. We write W (m, k) for the smallest n if it exists. Note that proving a more general result by induction can actually be easier, because the induction hypothesis is correspondingly stronger.

Another idea we use is the following: let A_{1}, A_{2}, …, A_{r} be arithmetic progressions of length l—say A_{i} = {a_{i}, a_{i} + d_{i}, …, a_{i} + (l − 1)d_{i}}. We say that A_{1}, A_{2}, …, A_{r} are focussed at f if a_{i} + ld_{i} = f for all i; for example, {1, 4} and {5, 6} are focussed at 7. If in addition each A_{i} is monochromatic and no two are the same colour then we say that they are colour-focussed at f (for the given colouring).

Proposition 5. Let k ∈ ℕ. Then there exists n ∈ ℕ such that whenever [n] is k-coloured, there exists a monochromatic arithmetic progression of length 3.

Proof. We make the following claim:

For all r ≤ k, there exists n such that whenever [n] is k-coloured, EITHER there exists a monochromatic arithmetic progression of length 3 OR there exist r colour-focussed arithmetic progressions of length 2.

The result will follow immediately from this claim—just take r = k; then whatever colour the focus is, we get a monochromatic arithmetic progression of length 3.

We prove the claim by induction on r. Note that the case r = 1 is trivial— we may simply take n = k + 1. So assume that we are given n suitable for r − 1; we will show that (k^{2n} + 1)2n is suitable for r.

Given a k-colouring of [(k^{2n} + 1)2n] not containing a monochromatic arithmetic progression of length 3, break up [(k^{2n}+1)2n] into blocks of length 2n, namely B_{i} = [2n(i − 1) + 1, 2ni] for i = 1, 2, …, k^{2n} + 1. Inside each block, there are r − 1 colour-focussed arithmetic progressions of length 2 (by our choice of n), together with their focus (as the length of each block is 2n). Now there are k^{2n} possible ways to colour a block, so some two blocks, say B_{s} and B_{s+t}, are coloured identically. Say B_{s} contains {a_{i}, a_{i}+d_{i}}, 1 ≤ i ≤ r−1, colour-focussed at f. Then B_{s+t} contains {a_{i}+2nt, a_{i}+d_{i}+2nt}, 1 ≤ i ≤ r−1, colour-focussed at f + 2nt, with corresponding colours the same. But now {a_{i}, a_{i} + d_{i} + 2nt}, 1 ≤ i ≤ r − 1, are arithmetic progressions colour-focussed at f + 4nt. Also, {f, f + 2nt} is monochromatic of a different colour; so we have r arithmetic progressions of length 2 colour-focussed at f + 4nt. This completes the induction; the claim, and hence the result, follow.

Remarks. 1. The idea of looking at the number of ways to colour a block is called a product argument.

2. The above proof gives W (3, k) ≤ k^{k^{k^{·^{·^{·^{k^{4k}}}}}}} ^{}(k−1)}, a ‘tower-type’ bound.

Theorem 6 (Van der Waerden’s Theorem). Let m, k ∈ ℕ. Then there exists n ∈ ℕ such that whenever [n] is k-coloured, there exists a monochromatic arithmetic progression of length m.

Proof. The proof is by induction on m. The case m = 1 is trivial (for all k).

Now given m, we can assume as our induction hypothesis that W (m−1, k) exists for all k. We make the following claim:

For all r ≤ k, there exists n such that whenever [n] is k-coloured, there exists either a monochromatic arithmetic progression of length m or r colour-focussed arithmetic progressions of length m − 1.

The result will follow immediately from this claim—just put r = k and look at the focus.

The proof of the claim is by induction on r. For r = 1 we may simply take n = W (m − 1, k). So suppose r > 1. If n is suitable for r − 1, we will show that W (m − 1, k^{2n})2n is suitable for r.

Given a k-colouring of [W (m − 1, k^{2n})2n] with no monochromatic arithmetic progression of length m, we can break up [W (m − 1, k^{2n})2n] into W (m − 1, k^{2n}) blocks of length 2n, namely B_{1}, B_{2}, …, B_{W (m−1,k^{2n})} where B_{i} = [2n(i − 1) + 1, 2ni]. By definition of W (m − 1, k^{2n}), we can find blocks B_{s}, B_{s+t}, …, B_{s+(m−2)t} identically coloured.

Now B_{s} contains r − 1 colour-focussed arithmetic progressions of length m − 1, together with their focus, say A_{1}, A_{2}, …, A_{r−1} colour-focussed at f, where A_{i} = {a_{i}, a_{i} + d_{i}, …, a_{i} + (m − 2)d_{i}}. Now look at the arithmetic progression A′_{i} = {a_{i}, a_{i} + (d_{i} + 2nt), …, a_{i} + (m − 2)(d_{i} + 2nt)} for i = 1, 2, …, r − 1. Then A′_{1}, A′_{2}, …, A′_{r−1} are colour-focussed at f + (m − 1)2nt. But {f, f +2nt, …, f +(m−2)2nt} is monochromatic and a different colour.

This completes the induction. The claim, and hence the result, follow.

We define the Ackermann (or Grzegorczyk) hierarchy to be the sequence of functions f_{1}, f_{2}, …: ℕ → ℕ defined by

f_{1}(x) = 2x
f_{n+1}(x) = f_{n}^{(x)}(1) (n ≥ 1),

so

f_{2}(x) = 2^{x},
f_{3}(x) = 2^{2^{2^{·^{·^{·^{2}}}}}} ^{}x},
f_{4}(1) = 2, f_{4}(2) = 2^{2} = 4, f_{4}(3) = 2^{2^{2^{2}}} = 65536, ….

We say that a function f: ℕ → ℕ is of type n if there exist c and d with f(cx) ≤ f_{n}(x) ≤ f(dx) for all x. Our proof above gives a bound of type m on W (m, k), so our bound on W (m) = W (m, 2) grows faster than f_{n} for all n—this is often a feature of such double inductions. Shelah showed that

W (m, k) ≤ f_{4}(m+k). Gowers showed that W (m) ≤ 2^{2^{2^{2^{2^{2^{2^{m}}}}}}} . The best lower bound known is W (m) ≥ 2^{m}/8m.

Corollary 7. Whenever ℕ is k-coloured, some colour class contains arbitrarily long arithmetic progressions.

Remark. We cannot guarantee an infinitely long arithmetic progression. Either

(i) colour ℕ by colouring 1 red, then 2 and 3 blue, then 4, 5 and 6 red then 7, 8, 9 and 10 blue, and so on; or

(ii) enumerate the infinitely long arithmetic progressions as A_{1}, A_{2}, A_{3}, … (noting that there are only countably many). Choose x_{i}, y_{i} ∈ A_{i} with x_{i} ≠ y_{i} for all i and x_{i}, y_{i} < x_{i+1}, y_{i+1}. Colour each x_{i} red and each y_{i} blue.

Theorem 8 (Strengthened Van der Waerden). Let m, k ∈ ℕ. Whenever ℕ is k-coloured, there is an arithmetic progression of length m that, together with its common difference, is monochromatic(i.e. there exist a, a+d, a + 2d, …, a + (n − 1)d and d all the same colour).

Proof. The proof is by induction on k; the case k = 1 is trivial.

Given n suitable for k − 1 (i.e. such that whenever [n] is (k − 1)-coloured there exists a monochromatic arithmetic-progression-with-common-difference of length n), we will show that W (n(m − 1) + k) is suitable for k. Indeed, given a k-colouring of [W (n(m − 1) + 1, k)], there exists a monochromatic arithmetic progression of length n(m − 1) + 1, say a, a + d, a + 2d, …, a + n(m − 1)d. If d or 2d or … or nd is the same colour as this arithmetic progression we are done. If not, we have {d, 2d, …, nd} (k − 1)-coloured, so we are done by induction.

Remark. The case m = 2 is known as Schur’s Theorem: whenever ℕ is k-coloured, we can solve x + y = z in one colour class. We can also prove Schur’s Theorem from Ramsey’s Theorem: given a k-colouring c of ℕ, define a k-colouring c′ of [n]^{(2)} (n large) by c′(ij) = c(|j − i|). By Ramsey, there exists a monochromatic triangle; i.e. there exist u < v < w with c′(uv) = c′(vw) = c′(wu). So c(v − u) = c(w − v) = c(w − u), and since (v − u) + (w − v) = (w − u) we are done.

1.3 The Hales-Jewett Theorem

Let X be a finite set. A subset L of X^{n} (‘the n-dimensional cube on alphabet X’) is called a line (or combinatorial line) if there exists a non-empty set I = {i_{1}, i_{2}, …, i_{r}} ⊂ [n] and a_{i} ∈ X for each i ∉ I such that

L = {x ∈ X^{n} : x_{i} = a_{i} for i ∉ I and x_{i_{1}} = x_{i_{2}} = ⋯ = x_{i_{r}}}.

We call I the set of active coordinates for L. For example, in [3]^{2} the lines are:

• {(1, 1), (2, 1), (3, 1)}, {(1, 2), (2, 2), (3, 2)}, and {(1, 3), (2, 3), (3, 3)} with I = {1};

• {(1, 1), (1, 2), (1, 3)}, {(2, 1), (2, 2), (2, 3)} and {(3, 1), (3, 2), (3, 3)} with I = {2}; and

• {(1, 1), (2, 2), (3, 3)} with I = {1, 2}.

Note that the definition of a line does not depend on the ground set X.

Theorem 9 (The Hales-Jewett Theorem). Let m, k ∈ ℕ. Then there exists n ∈ ℕ such that whenever [m]^{n} is k-coloured there exists a monochromatic line.

Remarks. 1. The smallest such n is denoted by HJ(m, k).

2. The Hales-Jewett Theorem implies Van der Waerden’s Theorem— we need only embed a Hales-Jewett cube of sufficiently high dimension linearly into ℕ, and so that the embedding is injective on lines. For example, given a k-colouring c of ℕ, induce a k-colouring c′ of [m]^{n} (n large) by c′((x_{1}, x_{2}, …, x_{n})) = c(x_{1} + x_{2} + ⋯ + x_{n}). By Hales-Jewett, there is a monochromatic line, and this corresponds to a monochromatic arithmetic progression of length m in ℕ. So we should regard the Hales-Jewett theorem as an abstract version of Van der Waerden’s Theorem.

If L is a line in [m]^{n} write L^{−} and L^{+} for its first and last points (in the ordering on [m]^{n} given by x ≤ y if x_{i} ≤ y_{i} for all i). Lines L_{1}, L_{2}, …, L_{k} are focussed at f if L_{i}^{+} = f for all i. They are colour-focussed (for a given colouring) if in addition each L_{i} − {L_{i}^{+}} is monochromatic, no two the same colour.

Proof (of Theorem 9). By induction on m; the case m = 1 is trivial.

Given m > 1, we may assume that HJ(m − 1, k) exists for all k. We make the following claim:

For all r ≤ k, there exists n such that whenever [m]^{n} is k-coloured, there exists EITHER a monochromatic line OR r colour-focussed lines.

The result will follow immediately from this claim—put r = k and look at the focus.

The proof of the claim is by induction on r. For r = 1 we may take n = HJ(m − 1, k).

Given n suitable for r, we shall show that n + HJ(m − 1, k^{m^{n}}) is suitable for r + 1. Write n′ = HJ(m − 1, k^{m^{n}}).

Given a k-colouring of [m]^{n+n′} with no monochromatic line, identify m^{n+n′} with [m]^{n} × [m]^{n′}. There are k^{m^{n}} ways to colour a copy of [m]^{n}. So by our choice of n′, we have a line L in [m]^{n′}, say with active coordinate set I, such that for all a ∈ [m]^{n} and all b, b′ ∈ L−{L^{+}}, we have c(a, b) = c(a, b′) = c′(a), say. Now by definition of n, there exist r colour-focussed lines for c′, say L_{1}, L_{2}, …, L_{r}, with acrive coordinate sets I_{1}, I_{2}, …, I_{r} respectively, and focus f. But now let L′_{i} be the line through the point (L_{i}^{−}, L^{−}) with active coordinate set I_{i} ∪ I (i = 1, 2, …, r). Then L′_{1}, L′_{2}, …, L′_{r} are colour-focussed at (f, L^{+}). And the line through (f, L^{−}) with active coordinate set I gives us r + 1 colour-focussed lines. Thus our induction is complete and the claim, and hence the result, follow.

A d-dimensional subspace or d-parameter set S in X^{n} is a set of the following form: there exist disjoint non-empty sets I_{1}, I_{2}, …, I_{d} ⊂ [n] and a_{i} ∈ X for each i ∈ [n] − (I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{d}) such that

S = \{x ∈ X^{n} : \begin{matrix}x_{i} = a_{i} for all i ∈ [n] − (I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{d}) \\ x_{i} = x_{j} whenever i, j ∈ I_{l} for some l \end{matrix} \} .

For example in X^{3}, {(a, b, 2) : a, b ∈ X} and {(a, a, b) : a, b ∈ X} are 2parameter sets.

Theorem 10 (The Extended Hales-Jewett Theorem). Let m, k, d ∈ ℕ. Then there exists n ∈ ℕ such that whenever [m]^{n} is k-coloured, there exists a monochromatic d-parameter set.

Proof. Regard X^{dn} as (X^{d})^{n}—a cube on alphabet X^{d}. Clearly any line in this (on alphabet X^{d}) is a d-parameter set on alphabet X, so we can take n = dHJ(n^{d}, k).

1.4 Gallai’s Theorem

Let S ⊂ ℕ^{d} be a finite set. A homothetic copy of S is any set of the form a + λS where a ∈ ℕ^{d} and λ ∈ ℕ. For example, in ℕ^{1}, a homothetic copy of {1, 2, …, m} is precisely an arithmetic progression of length m.

Theorem 11 (Gallai’s Theorem). For any finite S ⊂ ℕ^{d} and any kcolouring of ℕ^{d}, there exists a monochromatic homothetic copy of S.

Proof. Let S = {S(1), S(2), …, S(m)}. Given a k-colouring c of ℕ^{d}, define a k-colouring c′ of [m]^{n} (n large) by c′(x) = c(∑_{i} S(x_{i})). By Hales-Jewett, there is a monochromatic line, giving a monochromatic homothetic copy of S (with λ the number of active coordinates).

Remarks. 1. Or by a product argument and focussing.

2. For S = {(x, y) : x, y ∈ {0, 1}}, Gallai’s Theorem tells us that there exists a monochromatic square. Could we have used 2-parameter Hales-Jewett instead?—No, this would only give us a rectangle.

2 Partition Regular Equations

2.1 Partition Regularity

Let A be an m × n matrix with rational entries. We say that A is partition regular (PR) (over ℕ) if whenever ℕ is finitely coloured, there is always a monochromatic x ∈ ℕ^{n} with Ax = 0.

Examples. 1. Schur states that the matrix (1 1 −1) is PR.

2. Strengthened Van der Waerden states that the matrix

( \begin{matrix}1 & 1 & −1 & 0 & … & 0 \\ 1 & 2 & 0 & −1 & … & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & m & 0 & 0 & … & −1 \end{matrix} )

is PR.

We also talk about ‘the equation Ax = 0’ being PR.

Not every matrix is PR: for example, (2 −1) is not PR; for we can 2colour x ∈ ℕ by the parity of max{i : 2^{i}|x}. Note that A is PR if and only if λA is PR for any λ ∈ ℚ − {0}, so we could restrict our attention to integer matrices if we wished.

Let A have columns c^{(1)}, c^{(2)}, …, c^{(n)} ∈ ℚ^{m}, so

A = ( \begin{matrix}↑ & ↑ & & ↑ \\ c^{(1)} & c^{(2)} & … & c^{(n)} \\ ↓ & ↓ & & ↓ \end{matrix} ) .

We say that A has the columns property if there is a partition B_{1}∪B_{2}∪⋯∪B_{r} of [n] such that

(i) ∑_{i∈B_{1}} c^{(i)} = 0; and

(ii) ∑_{i∈B_{s}} c^{(i)} ∈ ⟨c^{(j)} : j ∈ B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{s−1}⟩ for s = 2, 3, …, r

where ⟨⟩ denotes linear span over ℝ. (Note that we could have equally said ‘over ℚ’ here: if a rational vector is a real linear combination of some rational vectors then it is also a rational combination of them.)

Examples. 1. The matrix (1 1 −1) has the columns property: take B_{1} = {1, 3} and B_{2} = {2}.

2. The matrix

( \begin{matrix}1 & −1 & 3 \\ 2 & −2 & a \\ 4 & −4 & b \end{matrix} )

has the columns property if and only if (a, b) = (6, 12).

3. The matrix A = (a_{1} a_{2} … a_{n}) has the columns property if and only if either A = 0 or some non-empty subset of the non-zero a_{i} sums to zero.

We shall prove:

Rado’s Theorem. A rational matrix A is PR if and only if A has the columns property.

One strength of this result is that it shows that partition regularity, which does not at first appear to be checkable in finite time, in fact is checkable in finite time.

First we show that Rado’s Theorem is true for one equation. We may assume without loss of generality that a_{1}, a_{2}, …, a_{n} ≠ 0; then we must show

(a_{1} a_{2} … a_{n}) is PR ⟺ ∑_{i∈I} a_{i} = 0 for some non-empty I ⊂ [n].

Let p be prime. For x ∈ ℕ, let d^{p}(x) be the last non-zero digit in the base p expansion of x, i.e. if x = d_{r}p^{r} + d_{r−1}p^{r−1} + ⋯ + d_{1}p + d_{0}, 0 ≤ d_{i} ≤ p − 1 for all i, then d^{p}(x) = d_{L(x)} where L(x) = min{i : d_{i} ≠ 0}. For example, if x = 1002047000 in base p then L(x) = 3 and d^{p}(x) = 7.

Proposition 12. Let a_{1}, a_{2}, …, a_{n} be non-zero rationals such that the matrix (a_{1} a_{2} … a_{n}) is PR. Then ∑_{i∈I} a_{i} = 0 for some non-empty I ⊂ [n].

Proof. We may assume without loss of generality that a_{1}, a_{2}, …, a_{n} ∈ ℤ. Fix a prime p with p > ∑_{i=1}^{n} |a_{i}|, and define a (p − 1)-colouring of ℕ by giving x the colour d^{p}(x). We know that ∑_{i∈I} a_{i}x_{i} = 0 for some x_{1}, x_{2}, …, x_{n} all of the same colour, d, say. Let L = min{L(x_{i}) : 1 ≤ i ≤ n} and let I = {i : L(x_{i}) = L}. Considering ∑_{i∈I} a_{i}x_{i} = 0 performed in base p, we have ∑_{i∈I} da_{i} ≡ 0 (mod p) and so ∑_{i∈I} a_{i} ≡ 0 (mod p). But p > ∑_{i=1}^{n} |a_{i}| and so ∑_{i∈I} a_{i} = 0.

Remark. Or: for each prime p we get a set I with ∑_{i∈I} a_{i} ≡ 0 (mod p), so some fixed set I has ∑_{i∈I} a_{i} ≡ 0 (mod p) for infinitely many p, whence ∑_{i∈I} a_{i} = 0.

Lemma 13. Let λ ∈ ℚ. Then whenever ℕ is finitely coloured, there exist monochromatic x, y and z with x + λy = z.

Proof. (cf the proof of Theorem 8.) If λ = 0 we are done; if λ < 0 we may rewrite our equation as z − λy = x. So we may assume without loss of generality that λ > 0; say λ = r/s with r, s ∈ ℕ.

So we need to prove that for all k, there exists an n such that, whenever [n] is k-coloured, there exist monochromatic x, y and z with x + (r/s)y = z. We shall prove this by induction on k.

For k = 1, take n = max{s, r + 1} and (x, y, z) = (1, s, r + 1).

Suppose k > 1. Given n suitable for k−1, we shall show that W (nr+1, k) is suitable for k. Indeed, given a k-colouring of [W (nr + 1, k)] we have a monochromatic arithmetic progression of length nr + 1, say a, a + d, …, a+nrd, all of colour c. Look at ds, 2ds, …, nds. If, say, ids has colour c then we are done, as a+(r/s)ids = a+idr and (a, ids, a+idr) is a monochromatic triple with colour c. So we may assume the set {ds, 2ds, …, nds} is (k − 1)- coloured, and we are done by induction. The claim, and hence the result, follow.

Theorem 14 (Rado’s Theorem for single equations). Let a_{1}, a_{2}, …, a_{n} be non-zero rationals. Then (a_{1} a_{2} … a_{n}) is PR if and only in ∑_{i∈I} a_{i} = 0 for some non-empty I ⊂ [n].

Proof. ⇒ is Proposition 12.

⇐ Given a finite colouring of ℕ, fix i_{0} ∈ I. For suitable monochromatic x, y and z, we shall set

x_{i} = \{ \begin{matrix}x & if i = i_{0} \\ y & if i ∉ I \\ z & if i ∈ I − \{i_{0}\} \end{matrix} .

We require that ∑ a_{i}x_{i} = 0, i.e. that

a_{i_{0}}x + ( ∑_{i∈I−{i_{0}}} a_{i})z + ( ∑_{i∉I} a_{i})y = 0,

i.e.

a_{i_{0}}x − a_{i_{0}}z + ( ∑_{i∉I} a_{i})y = 0,

i.e.

x + \frac{( ∑_{i∉I} a_{i})}{a_{i_{0}}}y − z = 0,

and such x, y and z do indeed exist by Lemma 13.

Proposition 15. Let A be any matrix with entries in ℚ. If A is PR then it must have the columns property.

Proof. We may assume without loss of generality that all the entries of A are integers. Let the columns of A be c^{(1)}, c^{(2)}, …, c^{(n)}. For any prime p, colour ℕ with the d^{p} colouring. By assumption, there exists a monochromatic x ∈ ℤ^{n} with Ax = 0, i.e. x_{1}c^{(1)} + x_{2}c^{(2)} + ⋯ + x_{n}c^{(n)} = 0. Say all the x_{i} have colour d.

We have a partition B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{r} of [n] given by

L(x_{i}) = L(x_{j}) ⟹ i, j ∈ B_{s} for some s;
L(x_{i}) < L(x_{j}) ⟹ i ∈ B_{s}, j ∈ B_{t} for some s < t.

For infinitely many primes p, say all p ∈ P, we get the same B_{1}, B_{2}, …, B_{r}. Considering ∑ x_{i}c^{(i)} = 0 performed in base p, we have

(i) ∑_{i∈B_{1}} dc^{(i)} ≡ 0 (mod p), where by u ≡ v (mod p) with u, v ∈ ℤ^{n} we mean u_{j} ≡ v_{j} (mod p) for all j; and

(ii) for all s ≥ 2, ∑_{i∈B_{s}} p^{t}dc^{(i)} + ∑_{i∈B_{1}∪···∪B_{s−1}} x_{i}c^{(i)} ≡ 0 (mod p^{t+1}) for some t.

From (i), and as d is invertible, we have ∑_{i∈B_{1}} c^{(i)} ≡ 0 (mod p) for infinitely many p, and so ∑_{i∈B_{1}} c^{(i)} = 0.

From (ii), for all s ≥ 2 we have

p^{t} ∑_{i∈B_{s}} c^{(i)} + ∑_{i∈B_{1}∪···∪B_{s−1}} y_{i}c^{(i)} ≡ 0 (mod p^{t+1})

(where y_{i} = d^{−1}x_{i} (mod p^{t+1})).

We now show that ∑_{i∈B_{s}} c^{(i)} ∈ ⟨c^{(i)} : i ∈ B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{s−1}⟩. Suppose not. Then there exists u ∈ ℤ^{m} with u · c^{(i)} = 0 for all i ∈ B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{s−1} but with u · (∑_{i∈B_{s}} c^{(i)}) ≠ 0. So p^{t}u · (∑_{i∈B_{s}} c^{(i)}) ≡ 0 (mod p^{t+1}), i.e. u · (∑_{i∈B_{s}} c^{(i)}) ≡ 0 (mod p) for infinitely many p, a contradiction.

Let m, p, c ∈ ℕ. A set S ⊂ ℕ is an (m, p, c)-set with generators x_{1}, x_{2}, …, x_{m} ∈ ℕ if

S = { ∑_{i=1}^{m} λ_{i}x_{i} : ∃j with λ_{i} = 0 ∀i < j, λ_{j} = c, λ_{i} ∈ {−p, −p+1, …, p} ∀i > j}.

So S consists of all numbers in the lists:

cx_{1} + λ_{2}x_{2} + λ_{3}x_{3} + ⋯ + λ_{m}x_{m} (|λ_{i}| ≤ p ∀i ≥ 2)
cx_{2} + λ_{3}x_{3} + ⋯ + λ_{m}x_{m} (|λ_{i}| ≤ p ∀i ≥ 3)
⋮
cx_{m−1} + λ_{m}x_{m} (|λ_{m}| ≤ p)
cx_{m}.

Examples. 1. A (2, p, 1)-set is an arithmetic progression of length 2p + 1 together with its common difference.

2. A (2, 2, 3)-set is an arithmetic progression of length 5, with middle term divisible by 3, together with thrice its common difference.

Theorem 16. Let m, p, c ∈ ℕ and suppose ℕ is finitely coloured. Then there exists a monochromatic (m, p, c)-set.

Proof. Let μ = k(m − 1) + 1.

Given a k-colouring of B_{0} = [n] with n large, look at

A_{1} = \{c, 2c, …, ⌊\frac{n}{c}⌋ c\}^{1}.

By Van der Waerden, there is a monochromatic arithmetic progression inside A, say

P_{1} = {cx_{1} − n_{1}d_{1}, cx_{1} − (n_{1} − 1)d_{1}, …, cx_{1}, …, cx_{1} + n_{1}d_{1}}

where n_{1} is large and P_{1} has colour k_{1}, say. Now we restrict attention to

B_{1} = \{d_{1}, 2d_{1}, …, \frac{n_{1}}{(μ − 1)p}d_{1}\} .

Note that for any integers λ_{2}, λ_{3}, …, λ_{μ} ∈ [−p, p] and b_{2}, b_{3}, …, b_{μ} ∈ B_{1}, we have

cx_{1} + λ_{2}b_{2} + λ_{3}b_{3} + ⋯ + λ_{μ}b_{μ} ∈ P_{1},

so in particular all sums of this form have colour k_{1}.

Now look at

A_{2} = \{cd_{1}, 2cd_{1}, …, \frac{n_{1}}{(μ − 1)pc}d_{1}\} .

By Van der Waerden, there is a monochromatic arithmetic progression inside A_{2}, say

P_{2} = {cx_{2} − n_{2}d_{2}, cx_{2} − (n_{2} − 1)d_{2}, …, cx_{2}, …, cx_{2} + n_{2}d_{2}},

where n_{2} is large and P_{2} has colour k_{2}, say. Now we restrict attention to

B_{2} = \{d_{2}, 2d_{2}, …, \frac{n_{2}}{(μ − 2)p}d_{2}\} .

Note that for any integers λ_{3}, λ_{4}, …, λ_{μ} ∈ [p, −p], and b_{3}, b_{4}, …, b_{μ} ∈ B_{2}, we have

cx_{2} + λ_{3}b_{3} + λ_{4}b_{4} + ⋯ + λ_{μ}b_{μ} ∈ P_{2},

so in particular all sums of this form have colour k_{2}.

1Henceforth we shall omit the symbols ‘⌊’ and ‘⌋’ in expressions such as this; they should be understood where necessary.

Now look at A_{3} = . . ..

Keep going μ times: we obtain x_{1}, x_{2}, …, x_{μ} such that each row of the (μ, p, c)-set generated by x_{1}, x_{2}, …, x_{μ} is monochromatic. But since μ = k(m − 1) + 1, some m of these rows are the same colour, and we are done.

Remark. For x_{1}, x_{2}, …, x_{m} ∈ ℕ, let

FS(x_{1}, x_{2}, …, x_{m}) = { ∑_{i∈I} x_{i} : ∅ ≠ I ⊂ [m]}.

Then Theorem 16 for (m, 1, 1)-sets implies:

Whenever ℕ is finitely coloured, there exist x_{1}, x_{2}, …, x_{m} with FS(x_{1}, x_{2}, …, x_{m}) monochromatic.

This result is variously known as the finite sums theorem, Folkman’s Theorem or Sanders’s Theorem.

Similarly, we can guarantee a monochromatic

FP(x_{1}, x_{2}, …, x_{m}) = { ∏_{i∈I} x_{i} : ∅ ≠ I ⊂ [m]}

by looking at {2^{n} : n ∈ ℕ}.

Lemma 17. If A has the columns property then there exist m, p, c ∈ ℕ such that every (m, p, c)-set contains a solution to Ax = 0, i.e. we can solve Ax = 0 with all x_{i} in the (m, p, c)-set.

Proof. Let A have columns c^{(1)}, c^{(2)}, …, c^{(n)}. As A has the columns property, we have a partition B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{r} of [n] such that

(i) ∑_{i∈B_{1}} c^{(i)} = 0; and
(ii) ∑_{i∈B_{s}} c^{(i)} ∈ ⟨c^{(j)} : j ∈ B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{s−1}⟩ for all s ≥ 2.

Suppose

∑_{i∈B_{s}} c^{(i)} = ∑_{i∈B_{1}∪B_{2}∪···∪B_{s−1}} q_{is}c^{(i)}.

Then for each s we have

∑_{i∈[n]} d_{is}c^{(i)} = 0

where

d_{is} = \{ \begin{matrix}0 & if i ∉ B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{s} \\ 1 & if i ∈ B_{s} \\ −q_{is} & if i ∈ B_{1} ∪ B_{2} ∪ ⋯ ∪ B_{s−1} \end{matrix} .

Given x_{1}, x_{2}, …, x_{r} ∈ ℕ, put y_{i} = ∑_{s=1}^{r} d_{is}x_{s} for i = 1, 2, …, n. Then

∑_{i=1}^{n} y_{i}c^{(i)} = ∑_{i=1}^{n} ∑_{s=1}^{r} d_{is}x_{s}c^{(i)} = ∑_{s=1}^{r} x_{s} ∑_{i=1}^{n} d_{is}c^{(i)} = 0.

So Ay = 0. Now we are done, for we may take m = r, take c to be the least common multiple of the denominators of the q_{i}, and take p to be c times the maximum of the numerators of the q_{i}. Then cy is in the (m, p, c)-set generated by x_{1}, x_{2}, …, x_{n} and A(cy) = 0.

Theorem 18 (Rado’s Theorem). Let A be a rational matrix. Then A is partition regular if and only if A has the columns property.

Proof. ⇐ is Proposition 15.

⇒ follows from Theorem 16 and Lemma 17.

Corollary 19 (The Consistency Theorem). If A and B are partition regular then the matrix \binom{A 0}{0 B} is also partition regular. In other words, if we can guarantee to solve Ax = 0 in some colour class and By = 0 in some colour class then we can guarantee to solve both in the same colour class.

Remark. This is not obvious by considerations of partition regularity alone.

Corollary 20. Whenever ℕ is finitely coloured, some colour class contains solutions to all PR equations.

Proof. Suppose not. Then we have ℕ = D_{1} ∪ D_{2} ∪ ⋯ ∪ D_{k}, and, for each i, a PR matrix A_{i} such that D_{i} does not contain a solution of A_{i}x = 0. Then consider the matrix

( \begin{matrix}A_{1} \\ & A_{2} \\ & & . & . & . \\ & & & & & A_{k} \end{matrix} ) .

This is PR, by the Consistency Theorem, but no D_{i} contains a solution to it, a contradiction.

We say that D_{i} ⊂ ℕ is partition regular if it contains a solution to every PR equation. So Corollary 20 says that if ℕ = D_{1} ∪ D_{2} ∪ ⋯ ∪ D_{k} then some D_{i} is PR. Rado conjectured, and Deuber proved, that if D is PR and D = D_{1} ∪ D_{2} ∪ ⋯ ∪ D_{k} then some D_{i} is PR.

2.2 Filters and Ultrafilters

A filter on ℕ is a non-empty collection F ⊂ P(ℕ) such that (i) ∅ ∉ F; (ii) if A ∈ F and B ⊃ A then B ∈ F (‘F is an up-set’); and (iii) if A, B ∈ F then A ∩ B ∈ F (‘F is closed under finite intersections’). Intuitively, we think of the sets of our filter as being the ‘large’ subsets of ℕ. Examples. The following are filters

(i) {A ⊂ ℕ : 1, 2 ∈ A}; (ii) {A ⊂ ℕ : A^{c} finite}, ‘the cofinite filter’; (iii) {A ⊂ ℕ : E − A finite} where E is the set of even numbers. An ultrafilter is a maximal filter. For any x ∈ ℕ, the set {A ⊂ ℕ : x ∈ A} is an ultrafilter, the principal ultrafilter at x. Proposition 21. A filter F is an ultrafilter if and only if for all A ⊂ ℕ, either A ∈ F or A^{c} ∈ F. Proof. ⇐ This is obvious since we cannot add A to F if we already have A^{c}. ⇒ Suppose F is an ultrafilter and A, A^{c} ∉ F. Then we must have B ∈ F with B ∩ A = ∅ (for otherwise F′ = {C ⊂ ℕ : C ⊃ A ∩ B for some B ∈ F} is a filter containing F). Similarly, we must have C ∈ F with C ∩ A^{c} = ∅. But then B ∩ C = ∅, a contradiction. Note. If A ∈ U, an ultrafilter, and A = B ∪ C, then B ∈ U or C ∈ U (for otherwise B^{c}, C^{c} ∈ U by Proposition 21 whence A^{c} = B^{c} ∩ C^{c} ∈ U, a contradiction). Proposition 22. Every filter is contained in an ultrafilter. Proof. By Zorn’s Lemma, it is sufficient to check that every non-empty chain {F_{i} : i ∈ I} has an upper bound. Indeed, put F = ∪_{i∈I}F_{i}. Then

(i) ∅ ∈ F;

(ii) if A ∈ F and B ⊃ A then A ∈ F_{i} for some i, so B ∈ F_{i} and so

B ∈ F;

(iii) if A, B ∈ F then A, B ∈ F_{i} for some i (as the F_{i} form a chain), so

A ∩ B ∈ F_{i} and so A ∩ B ∈ F.

Remarks. 1. Any ultrafilter extending the cofinite filter is non-principal. Also, if U is non-principal then U contains all cofinite sets; for if A ∈ U for some finite A then {x} ∈ U for some x ∈ A by our note above.

2. The Axiom of Choice is needed in some form to get non-principal ultrafilters.

The set of all ultrafilters on ℕ is denoted βℕ. We define a topology on βℕ by taking as a base all sets of the form

C_{A} = {U ∈ βℕ : A ∈ U}, A ⊂ ℕ.

This is a base: it is sufficient to check that ⋃ C_{A} = βℕ and that the intersection of any two of the C_{A} is another set of the putative base. Plainly ⋃ C_{A} = βℕ, and C_{A} ∩ C_{B} = C_{A∩B} as A, B ∈ U if and only if A ∩ B ∈ U. Thus open sets are of the form

⋃_{i∈I} C_{A_{i}} = {U : A_{i} ∈ U for some i ∈ I}.

Note that βℕ − C_{A} = C_{A^{c}}. So closed sets are of the form

⋂_{i∈I} C_{A_{i}} = {U : A_{i} ∈ U for all i ∈ I}.

We have ℕ inside βℕ (identifying n ∈ ℕ with the principal ultrafilter ñ at n). Each point of ℕ is isolated: C_{{n}} = {ñ}. Also, ℕ is dense in βℕ—every non-empty open set in βℕ meets ℕ as ñ ∈ C_{A} whenever n ∈ A.

Theorem 23. βℕ is a compact Hausdorff space.

Proof. Hausdorff: Given U ≠ V, we have some A ∈ U with A ∉ V. But then A^{c} ∈ V and so U ∈ C_{A} and V ∈ C_{A^{c}}. Compact: Given closed sets (F_{i})_{i∈I} with the finite intersections property (i.e. all finite intersections are non-empty), we need to show that ⋂_{i∈I} F_{i} ≠ ∅. Assume without loss of generality that each F_{i} is basic, i.e. that F_{i} = C_{A_{i}} for some A_{i} ⊂ ℕ.

We first observe that the sets (A_{i})_{i∈I} also have the finite intersections property. For we have C_{A_{i_{1}}} ∩ C_{A_{i_{2}}} ∩ ⋯ ∩ C_{A_{in}} = C_{A_{i_{1}}∩A_{i_{2}}···∩A_{in}} and so A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{n}} ≠ ∅.

So we can define a filter F generated by the A_{i}:

F = {A ⊂ ℕ : A ⊃ A_{i_{1}} ∩ A_{i_{2}} ∩ ⋯ ∩ A_{i_{n}} for some i_{1}, i_{2}, …, i_{n} ∈ I}.

Let U be an ultrafilter extending F. Then A_{i} ∈ U for all i, so u ∈ C_{A_{i}} for all i, and so ∩_{i∈I}C_{A_{i}} ≠ ∅ as desired.

Remarks. 1. If we view an ultrafilter as a function from P(ℕ) → {0, 1} then we have βℕ ⊂ {0, 1}^{P(ℕ)}. We can check that the topology on βℕ is the restriction of the product topology, and also that βℕ is a closed subset of {0, 1}^{P(ℕ)}—so compact by Tychonov.

2. βℕ is the largest compact Hausdorff space in which ℕ is dense—it is called the Stone-Čech compactification of ℕ. Let U be an ultrafilter and p a statement. We write ∀_{U}x p(x) to mean {x : p(x)} ∈ U, and say that p(x) holds ‘for most x’ or ‘for U-most x’. For example,

(i) for U non-principal, ∀_{U}x x > 4;

(ii) for U = ñ we have ∀_{U}x p(x) ⟺ p(n).

Proposition 24. Let U be an ultrafilter and p and q statements. Then

(i) ∀_{U}x (p(x) AND q(x)) ⟺ (∀_{U}x p(x)) AND (∀_{U}x q(x))
(ii) ∀_{U}x (p(X) OR q(x)) ⟺ (∀_{U}x p(x)) OR (∀_{U}x q(x))
(iii) if ∀_{U}x p(x) does not hold then ∀_{U}x (NOT p(x)).

Proof. Let A = {x : p(x)} and let B = {x : q(x)}. Then

(i) A ∩ B ∈ U if and only if A ∈ U and B ∈ U;
(ii) A ∪ B ∈ U if and only if A ∈ U or B ∈ U;
(iii) if ∀_{U}x p(x) is false then A ∉ U and so A^{c} ∈ U.

Note. ∀_{U}x ∀_{V}y p(x, y) need not be the same as ∀_{V}y ∀_{U}x p(x, y)—even if U = V. For example, if U is non principal then ∀_{U}x ∀_{U}y x < y is true, but ∀_{U}y ∀_{U}x x < y is false.

For U, V ∈ βℕ, define

U + V = {A ⊂ ℕ : ∀_{U}x ∀_{U}y x + y ∈ A}
= {A ⊂ ℕ : {x ∈ ℕ : {y : x + y ∈ A} ∈ V} ∈ U}.

Proposition 25. So defined, + is a well-defined map from βℕ × βℕ → βℕ. It is associative and left-continuous.

Proof. First, we show that U + V is an ultrafilter. Clearly ∅ ∉ U + V, and if A ∈ U + V and B ⊃ A then B ∈ U + V. Suppose now that A, B ∈ U + V, i.e.

(∀_{U}x ∀_{V}y x + y ∈ A) AND (∀_{U}x ∀_{V}y x + y ∈ B).

Then by proposition 24 (i),

∀_{U}x ((∀_{V}y x + y ∈ A) AND (∀_{V}y x + y ∈ B))

whence in turn

∀_{U}x ∀_{V}y (x + y ∈ A AND x + y ∈ B),

i.e.

∀_{U}x ∀_{V}y (x + y ∈ A ∩ B),

i.e.

A ∩ B ∈ U + V

as required. Finally, suppose that A ∉ U + V. Then

{x : ∀_{V}y x + y ∈ A} ∉ U

so by Proposition 24 (iii),

∀_{U}x (NOT (∀_{V}y x + y ∈ A))

whence in turn

∀_{U}x ∀_{V}y (NOT x + y ∈ A),

i.e.

∀_{U}x ∀_{V}y (x + y ∈ A^{c})

and so

A^{c} ∈ U + V.

So we have shown that U + V is an ultrafilter.

We next observe that +: βℕ × βℕ → βℕ is associative. Indeed, for any U, V, W ∈ βℕ,

U + (V + W) = {A ⊂ ℕ : ∀_{U}x ∀_{V+W}t x + t ∈ A}
= {A ⊂ ℕ : ∀_{U}x {t : x + t ∈ A} ∈ V + W}
= {A ⊂ ℕ : ∀_{U}x ∀_{V}y ∀_{W}z y + z ∈ {t : x + t ∈ A}}
= {A ⊂ ℕ : ∀_{U}x ∀_{V}y ∀_{W}z x + y + z ∈ A}
= (U + V) + W.

Finally, we show that + is left-continuous, i.e. that for fixed V, the map U ↦ U + V is continuous. So fix V and an open set C_{A} in our base for βℕ. Then

U + V ∈ C_{A} ⟺ A ∈ U + V
⟺ {x : ∀_{V}y x + y ∈ A} ∈ U
⟺ U ∈ C_{{x:∀_{V}y x+y∈A}},

so + is indeed left-continuous.

Fact. The operation + is neither commutative nor right-continuous.

We seek an idempotent ultrafilter, i.e. some U ∈ βℕ such that U + U = U. (Note that any such U must be non-principal, as ñ + ñ = ˜2n.)

Lemma 26 (The Idempotent Lemma). Suppose X is a non-empty compact Hausdorff topological space and +: X × X → X is an associative and left-continuous binary operation. Then there is an element x ∈ X such that x + x = x.

Proof. Consider S = {Y ⊂ X : Y compact and nonempty, Y + Y ⊂ Y } (where by Y + Y we mean {y + y′ : y, y′ ∈ Y }).

We first show that S has a minimal element. Clearly X ∈ S, so S ≠ ∅, so by Zorn’s Lemma it is sufficient to show that if {Y_{i} : i ∈ I} is a chain in S then Y = ∩_{i∈I}Y_{i} ∈ S. Since in a compact Hausdorff space a set is compact precisely if it is closed, we see that Y is compact; also Y ≠ ∅ since the Y_{i} are closed sets having the finite intersection property in the compact space X. Also, for y, y′ ∈ Y we have y, y′ ∈ Y_{i} for all i, so y + y′ ∈ Y_{i} + Y_{i} ⊂ Y_{i} for all i and so y + y′ ∈ Y. Thus Y ∈ S, proving our claim.

Let Y be a minimal element of S and fix x ∈ Y. We will show that x + x = x.

We begin by showing that Y +x ∈ S. We see that Y +x is non-empty and compact, since it is the continuous image of a compact set by left-continuity of +. Also, by associativity of +, (Y +x)+(Y +x) = (Y +x+Y)+x ⊂ Y +x. This shows that Y + x ⊂ Y.

Now, we know Y + x ⊂ Y, so we must have Y + x = Y by minimality of Y. Hence there exists y ∈ Y with y + x = x. Put Z = {y ∈ Y : y + x = x}.

We now show that Z ∈ S. By our remarks above, Z is non-empty. Note that {x} is compact, and so closed in the compact Hausdorff subspace Y of X. So Z, which is the inverse image in Y of the set {x} under the continuous map y ↦ y + x is closed, and so compact. Also, for y, y′ ∈ Z, we have by associativity of + that (y + y′) + x = y + (y′ + x) = y + x = x, and so y + y′ ∈ Z. This shows that Z ∈ S.

But Z ⊂ Y and so Z = Y. In particular, x ∈ Z and so x + x = x as desired.

Remark. Hence Y + x = {x} and so Y = {x}.

Corollary 27. There exists U ∈ βℕ such that U + U = U.

Theorem 28 (Hindman’s Theorem). Whenever ℕ is finitely coloured, there exist x_{1}, x_{2}, x_{3}, … with FS(x_{1}, x_{2}, x_{3}, …) monochromatic.

Proof. Given ℕ = A_{1} ∪A_{2} ∪⋯∪A_{k}, choose an idempotent U ∈ βℕ. We have A_{i} ∈ U for some i; write A = A_{i}. (Intuitively, we think of A as the largest colour class.) So ∀_{U}y y ∈ A. Also, as U is idempotent, ∀_{U}x∀_{U}y x + y ∈ A. So ∀_{U}x∀_{U}y FS(x, y) ⊂ A by Proposition 24. Pick x_{1} with ∀_{U}y FS(x_{1}, y) ⊂ A.

Now suppose inductively that we have found x_{1}, x_{2}, …, x_{n} such that ∀_{U}y FS(x_{1}, x_{2}, …, x_{n}, y) ⊂ A. For each z ∈ FS(x_{1}, x_{2}, …, x_{n}, y) we have ∀_{U}y z + y ∈ A and so ∀_{U}x∀_{U}y z + x + y ∈ A. Thus by Proposition 24, ∀_{U}x∀_{U}y FS(x_{1}, x_{2}, …, x_{n}, x, y) ⊂ A. Let x_{n+1} be such an x.

The result follows by induction.

3 Infinite Ramsey Theory

For infinite M ⊂ ℕ, write M^{(ω)} for the collection {L ⊂ M : L infinite} of all infinite subsets of M. Motivated by Theorem 2, we ask: if we finitely colour ℕ^{(ω)}, is there an infinite monochromatic set (i.e. does there exist M ∈ ℕ^{(ω)} such that all L ∈ M^{(ω)} have the same colour)?

Proposition 29. There is a 2-colouring of ℕ^{(ω)} without an infinite monochromatic set.

Proof. We construct a 2-colouring c such that for all M ∈ ℕ^{(ω)} and all x ∈ M we have c(M − {x}) ≠ c(M)—this is clearly sufficient to prove the proposition.

Define a relation ∼ on ℕ^{(ω)} by L ∼ M ⟺ |LΔM| < ∞. This is clearly an equivalence relation. Let the equivalence classes be {E_{i} : i ∈ I}, and for each i choose M_{i} ∈ E_{i}. Now define c(M) to be RED if |MΔM_{i}| is even for some i ∈ I and to be BLUE if |MΔM_{i}| is odd for some i ∈ I. It is easy to check that this colouring has the required property.

Note that in the above proof we used AC.

A 2-colouring of ℕ^{(ω)} corresponds to a partition ℕ^{(ω)} = Y ∪ Y^{c} for some Y ⊂ ℕ^{(ω)}. A collection Y ⊂ ℕ^{(ω)} is called Ramsey if there exists M ∈ ℕ^{(ω)} with M^{(ω)} ⊂ Y or M^{(ω)} ⊂ Y^{c}. So Proposition 29 says that ‘not all sets are Ramsey’.

We can induce the subspace topology on ℕ^{(ω)} ⊂ P(ℕ), where we identify P(ℕ) with {0, 1}^{ℕ} with the product topology. So a basic open neighbourhood of M ∈ ℕ^{(ω)} is {L ∈ ℕ^{(ω)} : L ∩ [n] = M ∩ [n]} for some n. Writing M^{(<ω)} for the collection {A ⊂ M : A finite} of finite subsets of M, we have a base of open sets for ℕ^{(ω)}:

{M ∈ ℕ^{(ω)} : A an initial segment of M}, A ∈ ℕ^{(<ω)}.

Equivalently, we have a metric

d(L, M) = \{ \begin{matrix}0 & if L = M \\ 1/ min(LΔM) & if L ≠ M \end{matrix} .

We call this the τ-topology or usual topology or product topology on ℕ^{(ω)}. For A ∈ ℕ^{(<ω)} and M ∈ ℕ^{(ω)}, write

(A, M)^{(ω)} = {L ∈ ℕ^{(ω)} : A is an initial segment of L and L − A ⊂ M}.

(We think of this as the collection of sets which ‘start as A and carry on inside M’.)

For fixed Y ⊂ ℕ^{(ω)}, we say that M accepts A (into Y) if (A, M)^{(ω)} ⊂ Y, and that M rejects A if no L ∈ M^{(ω)} accepts A.

Notes. 1. If M accepts A then every L ∈ M^{(ω)} accepts A as well. 2. If M rejects A then every L ∈ M^{(ω)} rejects A as well.

3. If M accepts A and A ⊂ B ⊂ A ∪ M, then M accepts B as long as max A ≤ min M.

4. M need not accept or reject A.

Lemma 30 (The Galvin-Prikry Lemma). Given Y ⊂ ℕ^{(ω)}, there exists a set M ∈ ℕ^{(ω)} such that either

(i) M accepts ∅ into Y; or

(ii) M rejects all of its finite subsets.

Proof. Suppose no M ∈ ℕ^{(ω)} accepts ∅, i.e. that ℕ rejects ∅. We shall inductively construct infinite subsets M_{1} ⊃ M_{2} ⊃ M_{3} ⊃ ⋯ of ℕ and a_{1}, a_{2}, a_{3}, … ∈ ℕ with a_{i} ∈ M_{i} for all i and such that M_{i} rejects all subsets of {a_{1}, a_{2}, …, a_{i−1}}. Then we shall be done, for {a_{1}, a_{2}, a_{3}, … } rejects all its finite subsets.

Take M_{1} = ℕ. Having chosen M_{1} ⊃ M_{2} ⊃ ⋯ ⊃ M_{k} and a_{1}, a_{2}, …, a_{k−1} as above, we seek a_{k} ∈ M_{k} and M_{k+1} ⊂ M_{k} such that M_{k+1} rejects all finite subsets of {a_{1}, a_{2}, …, a_{k}}.

Suppose this is impossible. Fix b_{1} ∈ M_{k} with b_{1} > a_{i} for 1 ≤ i ≤ k − 1. We cannot take a_{k} = b_{1} and M_{k+1} = M_{K} so some N_{1} ∈ M_{k}^{(ω)} accepts some subset S of {a_{1}, a_{2}, …, a_{k−1}, b_{1}}. And S must be of the form E_{1} ∪ {b_{1}} as M_{k} rejects all subsets of {a_{1}, a_{2}, …, a_{k−1}}. Now pick b_{2} ∈ N_{1} with b_{2} > b_{1} and try a_{k} = b_{2} and M_{k+1} + N_{1}. We get N_{2} ∈ N_{1}^{(ω)} accepting a subset of {a_{1}, a_{2}, …, a_{k−1}, b_{2}}—say N_{2} = E_{2} ∪ {b_{2}}. Keep going: we get M_{k} ⊃ N_{1} ⊃ N_{2} ⊃ ⋯ and b_{1} < b_{2} < b_{3} < ⋯ (b_{1} ∈ N_{i−1}), together with E_{1}, E_{2}, E_{3}, … ⊂ {a_{1}, a_{2}, …, a_{k−1}} such that E_{n} ∪ {b_{n}} is accepted by N_{n} for all n. Passing to a subsequence if necessary, we may assume without loss of generality that E_{n} = E for all n. Then E is accepted by {b_{1}, b_{2}, b_{3}, … }, contradicting the definition of M_{k}.

Theorem 31. If Y is open then Y is Ramsey.

Proof. By Galvin-Prikry, there exists M ∈ ℕ^{(ω)} with either

(i) M accepting ∅; or

(ii) M rejecting all its finite subsets.

If (i) then we have M^{(ω)} ⊂ Y.

If (ii) then we will show M^{(ω)} ⊂ Y^{c}. Indeed, suppose we have L ∈ M^{(ω)} with L ∈ Y. Since Y is open, we must have (A, ℕ)^{(ω)} ⊂ Y for some initial segment A of L. So in particular, we have (A, M)^{(ω)} ⊂ Y, i.e. M accepts A, a contradiction.

Remark. A collection Y is Ramsey if and only if Y^{c} is Ramsey, so Theorem 31 also says that ‘closed sets are Ramsey’.

The ⋆-topology or Ellentuck topology or Mathias topology on ℕ^{(ω)} has basic open sets (A, M)^{(ω)} for A ∈ ℕ^{(<ω)} and M ∈ ℕ^{(ω)}. This is a base for a topology on ℕ^{(ω)}:

• ℕ^{(ω)} = (∅, N)^{(ω)} so the union of our putative basic sets is indeed ℕ^{(ω)};

• if (A, M)^{(ω)} and (A′, M′)^{(ω)} are basic sets then (A, M)^{(ω)} ∩ (A′, M′)^{(ω)} is either (A ∪ A′, M ∩ M′)^{(ω)} or ∅.

Note that the ⋆-topology is stronger (i.e. has more open sets) than the usual topology.

Theorem 32. If Y is ⋆-open then Y is Ramsey.

Proof. Choose M ∈ ℕ^{(ω)} as given by Galvin-Prikry.

(i) If M accepts ∅ then M^{(ω)} ⊂ Y.

(ii) If M rejects all its finite subsets then we shall show that M^{(ω)} ⊂ Y^{c}. Indeed, suppose L ∈ M^{(ω)} with L ∈ Y. Since Y is ⋆-open, we must have (A, L)^{(ω)} ⊂ Y for some initial segment A of L. So L accepts A, contradicting ‘M rejects A’.

We say Y ⊂ ℕ^{(ω)} is completely Ramsey if for all A ∈ ℕ^{(<ω)} and all M ∈ ℕ^{(ω)} there is some L ∈ M^{(ω)} such that (A, L)^{(ω)} is contained in either Y or Y^{c}.

This is a stronger property than being Ramsey. For example, let Y be the non-Ramsey set from Proposition 29 and set

Y′ = Y ∪ {M ∈ ℕ^{(ω)} : 1 ∉ M}.

Then certainly Y′ is Ramsey, as {2, 3, 4, … }^{(ω)} ⊂ Y^{c}. But Y′ is not completely Ramsey; A = {1} and M = ℕ yield no L as desired.

Theorem 33. If Y is ⋆-open then Y is completely Ramsey.

Proof. Given A ∈ ℕ^{(<ω)} and M ∈ ℕ^{(ω)}, we seek L ∈ M^{(ω)} with (A, L)^{(ω)} contained in Y or Y^{c}. Now view (A, M)^{(ω)} as a copy of ℕ^{(ω)} as follows. We may assume without loss of generality that max A < min M. Write M = {m_{1}, m_{2}, m_{3}, … }, where m_{1} < m_{2} < m_{3} < ⋯, and define a function f: ℕ^{(ω)} → (A, M)^{(ω)} by N ↦ A ∪ {M_{i} : i ∈ N}. Clearly f is a homeomorphism in the ⋆-topology.

Let Y′ = {N ∈ ℕ^{(ω)} : f(N) ∈ Y }. Then Y′ is ⋆-open since Y is ⋆-open. So by Theorem 32, there exists L ∈ ℕ^{(ω)} with L^{(ω)} contained in either Y or Y^{c}. Thus {f(N) : N ∈ L^{(ω)}} is contained in either Y or Y^{c}, i.e. (A, f(L))^{(ω)} is contained in either Y or Y^{c}.

So we know that, in the ⋆-topology, all ‘locally big’ (i.e. open) sets are completely Ramsey. Now we consider ‘locally small’ (i.e. nowhere dense) sets.

Given a space X, we say that A ⊂ X is nowhere dense if A is not dense in any non-empty open subset, equivalently if for any non-empty open O, there is a non-empty open O′ ⊂ O such that O′ ∩ A = ∅, equivalently if Ā has empty interior. For example, ℕ is nowhere dense in ℝ.

Proposition 34. A set Y ⊂ ℕ^{(ω)} is ⋆-nowhere-dense if and only if for all a ∈ ℕ^{(<ω)} and all M ∈ ℕ^{(ω)}, there is some L ∈ M^{(ω)} with (A, L)^{(ω)} ⊂ Y^{c}.

Proof. The first statement says that inside (A, M)^{(ω)} there is some (B, L)^{(ω)} missing Y while the second says that inside (A, M)^{(ω)} there is some (A, L)^{(ω)} missing Y. So it is immediate that the second statement implies the first.

So suppose that Y is ⋆-nowhere-dense. Then Ȳ has non-empty interior and so Ȳ is ⋆-nowhere-dense (since ¯ Ȳ = Ȳ). But Ȳ is completely Ramsey by Theorem 33 and so inside (A, M)^{(ω)} there exists some (A, L)^{(ω)} contained in either Ȳ or (Ȳ)^{c}. But int Ȳ = ∅ so (A, L)^{(ω)} ⊂ (Ȳ)^{c} and so (A, L)^{(ω)} ⊂ Y^{c} as required.

A subset A of a topological space X is called meagre or of first category if A = ⋃_{n=1}^{∞} A_{n} with each A_{n} nowhere dense. For example, ℚ is meagre in ℝ.

We can usually think of meagre sets as being small: for example, the Baire Category Theorem states that if X is a non-empty complete metric space and A is a meagre subset of X then A ≠ X.

Theorem 35. Let Y be ⋆-meagre. Then for all A ∈ ℕ^{(<ω)} and all M ∈ ℕ^{(ω)}, there is some L ∈ M^{(ω)} such that (A, L)^{(ω)} ⊂ Y^{c}. In particular, Y is ⋆-nowhere-dense.

Proof. Suppose we are given A ∈ ℕ^{(<ω)} and M ∈ ℕ^{(ω)}. Write Y = ⋃_{n−1}^{∞} Y_{n} with each Y_{n} ⋆-nowhere-dense.

By Proposition 34, we have M_{1} ∈ M^{(ω)} with (A, M_{1})^{(ω)} ⊂ Y_{1}^{c}. Choose x_{1} ∈ M_{1} with x_{1} > max A.

Again by Proposition 34, we have M′_{2} ∈ M_{1}^{(ω)} with (A, M′_{2})^{(ω)} ⊂ Y_{2}^{c} and then M_{2} ∈ M_{2}^{′(ω)} with (A∪{x_{1}}, M_{2})^{(ω)} ⊂ Y_{2}^{c}. Choose x_{2} ∈ M_{2} with x_{2} > x_{1}.

Applying Proposition 34 four times, once for each subset of {x_{1}, x_{2}}, we get M_{3} ∈ M_{2}^{(ω)} such that each of the sets (A, M_{3})^{(ω)}, (A ∪ {x_{1}}, M_{3})^{(ω)}, (A ∪ {x_{2}}, M_{3})^{(ω)} and (A ∪ {x_{1}, x_{2}}, M_{3})^{(ω)} is contained in Y_{3}^{c}.

Keep going: we obtain M ⊃ M_{1} ⊃ M_{2} ⊃ ⋯ and max A < x_{1} < x_{2} < ⋯ with x_{n} ∈ M_{n} for all n and (A ∪ F, M_{n})^{(ω)} ⊂ Y_{n}^{c} for all F ⊂ {x_{1}, x_{2}, … x_{n}}. Then (A, {x_{1}, x_{2}, … })^{(ω)} ⊂ Y_{n}^{c} for all n and so (A, {x_{1}, x_{2}, … })^{(ω)} ⊂ Y^{c}.

A set A in a topological space is a Baire set, or has the property of Baire, if A = OΔM for some open O and meagre M. We can think of A as being ‘nearly open’.

Notes. 1. If A is open then A is Baire.

2. If A is closed then A is Baire, since A = int AΔ(A − int A), where A − int A is nowhere dense as it is closed and contains no non-empty open set.

The Baire sets form a σ-algebra:

(i) X is Baire.

(ii) If Y is Baire, say Y = OΔM, then

Y^{c} = O^{c}ΔM
= (O′ΔM′)ΔM  (since O^{c} is closed, and using note (ii) above)
= O′Δ(M′ΔM)

so Y^{c} is Baire.

(iii) If the sets Y_{1}, Y_{2}, Y_{3}, … are Baire, say Y_{i} = O_{i}ΔM_{i}, then their union ⋃_{n=1}^{∞} Y_{n} = (⋃_{n=1}^{∞} O_{n})ΔM for some M ⊂ ⋃_{n=1}^{∞} M_{n} and so ⋃_{n=1}^{∞} Y_{n} is Baire.

Since we noted above that open sets are Baire, it follows that any Borel set is Baire.

Theorem 36. A collection Y is completely Ramsey if and only if it is ⋆-Baire.

Proof. ⇐ Suppose Y is ⋆-Baire, so Y = W ΔZ with W open and Z meagre.

Given (A, M)^{(ω)}, we have L ∈ M^{(ω)} with (A, L)^{(ω)} contained in either W or W^{c} (by Theorem 33) and N ∈ L^{(ω)} with (A, N)^{(ω)} ⊂ Z^{c} (by Theorem 35). So either

(A, N)^{(ω)} ⊂ W ∩ Z^{c} ⊂ Y

or

(A, N)^{(ω)} ⊂ W^{c} ∩ Z^{c} ⊂ Y^{c}

and Y is completely Ramsey as required.

⇒ Suppose conversely that Y is completely Ramsey. We can write Y = int Y Δ(Y − int Y). so it will be sufficient for us to show that Y − int Y is ⋆-nowhere-dense; we show in particular that given any base set (A, M)^{(ω)} in the ⋆-topology, there is a non-empty open set inside it which is disjoint from Y − int Y —indeed, we have L ∈ M^{(ω)} with (A, L)^{(ω)} contained in either Y or Y^{c}.

If (A, L)^{(ω)} ⊂ Y then (A, L)^{(ω)} is disjoint from Y − int Y.

If (A, L)^{(ω)} ⊂ Y^{c} then again (A, L)^{(ω)} is disjoint from Y − int Y.

So Y is ⋆-Baire, as required.

Thus any ⋆-Borel set is completely Ramsey, and so certainly any τ-Borel set is Ramsey.

Note. Without Theorem 35, we would have shown that Y is completely Ramsey if and only if Y is the symmetric difference of an open set and a nowhere dense set, and we would not have known that the completely Ramsey sets form a σ-algebra.

Typeset in L^{A}TEX 2ε by Paul A. Russell.