1. Introduction

Ramsey theory is concerned with a certain class of theorems, in which a sufficiently large object is somehow colored into finitely many components (but with no control as to exactly how the object is colored, other than specifying the number of colors used), and it is then shown that one of these components must necessarily contain a certain type of structure. The prototypical such result is the pigeonhole principle, which asserts that if a set of km + 1 elements is colored into m different colors, then regardless of how the coloring is chosen, there must be a subset of k + 1 elements which is monochromatic; indeed much of Ramsey theory can be viewed as applications and generalizations of this pigeonhole principle. Ramsey theorems can be very powerful, as they assume very little information on the coloring to be studied; however, they do suffer an important limitation, which is that one usually does not know which color will contain the resulting structure. Thus they are primarily used in situations in which one would be content with locating the desired structure in any color.

In Ramsey’s original work on the subject (and in many follow-up works), the object to be colored was the edges of a graph; this theory has found many applications in fields as diverse as Banach space theory, convex geometry, and complexity theory. However, for our purposes we shall be more interested in the narrower topic of additive Ramsey theory, which is concerned with colorings of subsets of an additive group (and in particular colorings of finite sets of integers). As such we will not attempt a broad survey of the field (avoiding for instance the deeper study of Ramsey theory on infinite sets); for this we refer the reader to the excellent textbook of [9].

Let us set out our notation for colorings.

Definition 1.1. Let A is an arbitrary set, and m ≥ 1 be an integer. A m-coloring (or finite coloring, if m is unspecified) of A is just a function c : A → C to some finite set of colors C of cardinality |C| = m. We say that a subset A′ of A is monochromatic with color c if c(n) = c for all n ∈ A.

Remark 1.2. The exact choice of color set C is usually not relevant, in the sense that given any bijection ϕ : C → C′, one could replace the coloring function c by ϕ∘c while leaving the theory essentially unchanged. The situation here is analogous to that of information theory of a random variable, in which only the level sets of the random variable (or equivalently, the sigma algebra it generates) is relevant.

Most of the theorems of this chapter will be of the following general type: given an integer m, and some collection of “structures” S_{1}, …, S_{n}, then every sufficiently large m-colored set A will contain a monochromatic object “isomorphic to” one of the S_{i}. Such types of results are sometimes called Ramsey theorems. These Ramsey theorems will typically be proven by induction, either on the number of colors or the number (or complexity) of the structures; we shall also use easier Ramsey theorems to deduce more difficult ones. Because of the heavily inductive nature of many of the proofs, the quantitative bounds we obtain (i.e. how large A has to be depending on m and the structures S_{1}, …, S_{n}) are often quite poor, for instance many of the bounds grow as fast as the Ackermann function or worse. It is of interest to find better bounds for many of these problems; we shall describe some progress on this for two special Ramsey theorems, the van der Waerden and Hales-Jewett theorems.

2. Ramsey’s theorem and Schur’s theorem

We begin with Ramsey’s original theorem. We say that an undirected graph G is complete if every pair of distinct vertices v, w ∈ G is connected by exactly one edge.

Theorem 2.1 (Ramsey’s theorem for two colors). [15] Let n, m ≥ 1 be integers, and let G = (V, E) be a complete graph with at least \binom{n+m−2}{n−1} := \frac{(n+m−2)!}{(n−1)!(m−1)!} vertices. Then for any two-coloring c : E → {blue, red} of the edge set E, with color set blue and red (say), there either exists a blue-monochromatic complete subgraph G_{blue} with n vertices, or a red-monochromatic complete subgraph G_{red} with m vertices.

Example 2.2. Any two-colouring of a complete graph with six or more vertices into red and blue edges will contain either a blue triangle or a red triangle.

Proof We shall induct on the quantity n + m. When n + m = 2 (i.e. n = m = 1) the claim is vacuously true. Now suppose that n+m > 2 and the claim has already been proven for all smaller values of n + m. If n = 1 then the claim is again vacuously (with R(1, m) = 1), and similarly when m = 1. Thus we shall assume n, m ≥ 2.

Let G = (V, E) be a complete graph with at least \binom{n+m−2}{n−1} vertices, and let v ∈ V be an arbitrary vertex. This vertex is adjacent to at least

\binom{n + m − 2}{n − 1} − 1 = \binom{n + m − 3}{n − 2} + \binom{n + m − 3}{n − 1} − 1

many edges, each of which is either blue or red. Thus by the pigeonhole principle, either v is adjacent to at least \binom{n+m−3}{n−2} blue edges, or is adjacent to at least \binom{n+m−3}{n−1} red edges. Suppose first that we are in the former case. Then we can find a complete subgraph G′ of G with at least \binom{n+m−3}{n−2} edges such that every vertex of G′ is connected to v by a blue edge. By the inductive hypothesis (with (n, m) replaced by (n−1, m)), G′ either contains a blue-monochromatic complete subgraph G′_{blue} with n − 1 vertices, or a red-monochromatic complete subgraph G′_{red} with m vertices. In the latter case we are already done by taking G_{red} := G_{red}, and in the latter case we can find a blue-monochromatic complete subgraph G_{blue} of G with n vertices by adjoining v to G′_{blue} (and adding in all the edges connecting v and G′_{blue}, which are all blue by construction. This disposes of the case when v is adjacent to at least \binom{n+m−3}{n−2} blue edges; the case when v is connected to at least \binom{n+m−3}{n−1} red edges is proven similarly (now using the inductive hypothesis at (n, m − 1) instead of (n − 1, m)).

Remark 2.3. The bound \binom{n+m−2}{n−1} is sharp for very small values of n and m, but can be improved for larger values of n and m, although computing the precise constants is very difficult (for instance, when n = m = 5 the best constant is only known to be somewhere between 43 and 49 inclusive). On the other hand, lower bounds are known (see exercises).

One can iterate this theorem to arbitrary number of colors:

Corollary 2.4 (Ramsey’s theorem for many colors). [15] Given any positive integers n_{1}, …, n_{m}, there exists a number R(n_{1}, …, n_{m}; m) such that given any complete graph G = (V, E) with at least R(n_{1}, …, n_{m}; m) vertices, and any m-coloring c : E → {c_{1}, …, c_{m}} of the edges, there exists a 1 ≤ j ≤ m and a c_{j}-monochromatic complete subgraph G_{j} of G with n_{j} vertices.

Proof We induct on m. The case m = 1 is trivial, and the case m = 2 is just Theorem 2.1. Now suppose inductively that m > 2 and the claim has already been proven for all smaller values of m. We set

R(n_{1}, …, n_{m}; m) := R(R(n_{1}, …, n_{m−1}; m − 1), n_{m}; 2).

Let c be a coloring of K_{R(n_{1},... ,n_{m};m)} into m colors c_{1}, …, c_{m}. We define a coarsened coloring c/ ∼ by identifying the first c_{1}, …, c_{m−1} colors into a single equivalence class {c_{1}, …, c_{m−1}}, while leaving the last color c_{m} in a singleton equivalence class {c_{m}}. By the inductive hypothesis, we see that with respect to the coarsened coloring c/ ∼, either G contains a {c_{m}}-monochromatic complete subgraph G_{m} with n_{m} elements, or G contains {c_{1}, …, c_{m−1}}-monochromatic complete subgraph G_{1,... ,m−1} with R(n_{1}, …, n_{m−1}; m − 1) elements. In the first case we are done; in the second case we are done by applying the induction hypothesis once again, this time to the complete grpaph G_{1,... ,m−1}. This closes the induction and completes the proof.

We now give an immediate application of Ramsey’s theorem to an arithmetic setting.

Theorem 2.5 (Schur’s theorem). [17] If m, k are positive integers, there exists a positive integer N = N(m, k) such that, given any m-coloring c : [1, N] → C of [1, N], there exists a monochromatic subset of [1, N] of the form {x_{1}, …, x_{k}, x_{1} + …+x_{k}}. In fact we can choose N := R(k +1, …, k +1; m)−1, using the notation of Corollary 2.4.

Remarks 2.6. Define a sum-free set to be any set A such that (A + A) ∩ A = ∅. Schur’s theorem (in the k = 2 case) is then equivalent to the assertion that the set [1, N] cannot be covered by m sum-free sets if N is sufficiently large depending on m; in particular, the integers cannot be partitioned into any finite number of sumfree sets. Even when k = 2, the value of N given by the above arguments grows double-exponentially in m (see exercises); this is not best possible. For instance, it is known that given any 2-coloring of [1, N], there exist at least \frac{1}{22}N^{2} − \frac{7}{22}N monochromatic triples of the form (x, y, x + y), and that this bound is sharp [16],

[18] (see also [8]).

Proof Let G be the complete graph on the N + 1 vertices [1, N + 1], and define a colouring c̃ : E(G) → C by setting c̃({a, b}) := c(|a − b|) for any edge {a, b}. By Corollary 2.4, the graph G must contain a complete subgraph G′ of k + 1 vertices which is monochromatic with respect to c̃. If we list the vertices of G′ in order as v_{0} < v_{1} < … < v_{k}, then the quantities c(v_{i} − v_{j}) for i > j are all equal to each other. The claim then follows by setting x_{j} := v_{j} − v_{j−1}.

• Using Schur’s theorem, show that if the positive integers Z^{+} are finitely colored and k ≥ 1 is arbitrary, then there exist infinitely many monochromatic sets in Z^{+} of the form {x_{1}, …, x_{k}, x_{1} + … + x_{k}}. (Hint: Schur’s theorem can easily produce one such set; now color all the elements of that set by new colors and repeat). Conversely, show that if the previous claim is true, then it implies Schur’s theorem.

• Show that if the positive integers Z^{+} are finitely colored then there exist infinitely many distinct integers x and y such that {x, y, x + y} are monochromatic. (Hint: refine the coloring so that x and 2x always have different colors). A more challenging problem is to establish a similar result for general k, i.e. to find infinitely many distinct x_{1}, …, x_{k} such that {x_{1}, …, x_{k}, x_{1} + … + x_{k}} is monochromatic.

• Show that if the positive integers Z^{+} are finitely colored and k ≥ 1 are arbitrary, then there exist infinitely many monochromatic sets of the form {x_{1}, …, x_{k}, x_{1} … x_{k}}. Thus Schur’s theorem can be adapted to products instead of sums. However, nothing is known about the situation when one has both sums and products; for instance, it is not even known that if one finitely colors the positive integers that one can find even a single monochromatic set of the form {x + y, xy} for some positive integers x, y (not both equal to 1).

• Show that the quantity N(m, k) in Schur’s theorem can be taken to be C^{k^{m}} for some absolute constant C > 1.

• [4] Show that if n ≥ 3 and N ≤ 2^{n/2} then there exists a two-coloring of the complete graph on N vertices which does not contain a monochromatic complete subgraph of n vertices. (Hint: color the graph randomly, giving each edge one of the two colors with equal and independent probability, and then use linearity of expectation). Remark: This result, proven in 1947 by Erd¨’os [4], marks the first significant application of the probabilistic method to combinatorics.

3. Van der Waerden’s theorem

We now give van der Waerden’s theorem, which is a similar statement to Schur’s theorem but asks for a monochromatic arithmetic progression {a, a+r, …, a+(k − 1)r} rather than a set of the form {x_{1}, …, x_{k}, x_{1} + … + x_{k}}.

Theorem 3.1 (Van der Waerden’s theorem). [20] For any integers k, m ≥ 1 there exists an integer N = N(k, m) ≥ 1 such that given any proper arithmetic progression P of length at least N (in an arbitrary additive group Z), and any m-coloring c : P → C of P, there exists a monochromatic proper arithmetic subprogression P′ of P of length |P′| = k.

Remark 3.2. Note that one can take P = [1, N], which gives this theorem the flavor of Schur’s theorem. On the other hand, Schur’s theorem does not generalize to an arbitrary proper arithmetic progression P, simply because P may not contain any sets of the form {x_{1}, …, x_{k}, x_{1} + … + x_{k}} at all (i.e. kP may be disjoint from P).

Proof We shall use a double induction. The outer induction is on the k variable. The base case k = 1 is trivial, so suppose k ≥ 2 and the claim has already been proven for k−1; thus for every m there exists a positive integer N(k−1, m) such that any m-colouring of a proper arithmetic progression of length at least N(k − 1, m) contains a monochromatic proper arithmetic progression of length k − 1.

To proceed further we need the “color focusing technique”. This technique rests on the concept of a polychromatic fan, which we now define.

Definition 3.3. Let c : P → C be a m-colouring, let k ≥ 1, d ≥ 0, and a ∈ P. We define a fan of radius k, degree d, and base point a to be a d-tuple F = (a + [0, k) · r_{1}, …, a + [0, k) · r_{d}) of proper arithmetic progressions in P of length k and base point a, and refer to the arithmetic progressions a + [1, k) · r_{1}, 1 ≤ i ≤ d as the spokes of the fan. We say that a fan is weakly polychromatic if its d spokes are all monochromatic with distinct colours, and strongly polychromatic if its d spokes and its origin are all monochromatic with distinct colors. In other words, F is strongly polychromatic there exist distinct colours c_{0}, c_{1}, …, c_{d} ∈ C such that c(a) = c_{0}, and c(a + jr_{i}) = c_{i} for all 1 ≤ i ≤ d and 1 ≤ j ≤ k, and similarly for weakly polychromatic except that c_{0} is allowed to equal one of the other c_{j}. We refer to the d + 1-tuple c(F) := (c_{0}, …, c_{d}) as the colors of the polychromatic fan. We also define the notion of a translation x + F of a fan F by an element x of the ambient group, formed by translating the origin and each of the spokes of F by x.

Let us now make two simple (and one somewhat less simple) observations about polychromatic fans, which we leave to the reader to verify.

• (i) If F is a weakly polychromatic fan of radius k, then either F is strongly polychromatic (if the origin has a distinct color from all of its spokes), or F contains a monochromatic arithmetic progression of length k + 1 if the origin is the same color as one of its spokes).

• (ii) A strongly polychromatic fan cannot have degree m (simply because that would require m + 1 or more colors).

• (iii) If F = (a + [0, k) · r_{1}, …, a + [0, k) · r_{d}) is a fan of radius k and degree d, and a_{0}, r ∈ Z are such that the k − 1 fans a_{0} + jr + F, 1 ≤ j ≤ k − 1 and the origin {a_{0} + a} all lie in P and are disjoint from each other, and furthermore the fans a_{0} + jr + F are all strongly polychromatic with the same colors c(a_{0} + jr + F) = c, then the fan F̃ := (a_{0} + a + [0, k) · r, a_{0} + a + [0, k) · (r + r_{1}), …, a_{0} + a + [0, k) · (r + r_{d})) also lies in P and is a weakly polychromatic fan of radius k and degree d + 1. In other words, arithmetic progressions of strongly polychromatic fans contain a weakly polychromatic fan of one higher degree.

We now combine these three observations to close the outer inductive step. To do this we need an inner inductive step, which is formalized in the following lemma.

Lemma 3.4. For any d ≥ 0 there exists a positive integer Ñ(k − 1, m, d) such that any m-colouring of a proper arithmetic progression P of length at least Ñ(k−1, m, d) contains either a monochromatic progression of length k, or a strongly polychromatic fan of radius k and degree d.

Proof We shall need another induction, this time on the d variable. The base case d = 0 is trivial. Assume now that d > 1 and the claim has already been proven for d − 1. We define Ñ = Ñ(k − 1, m, d) by the formula Ñ := 2N_{1}N_{2}, where N_{1} := Ñ(k − 1, m, d − 1) and N_{2} := N(k − 1, m^{d}N_{1}^{d}), which are guaranteed to be finite by the inner and outer inductive hypotheses respectively, and let c : P → C be an m-colouring of some proper arithmetic progression P of length at least [1, Ñ]. Without loss of generality we may take P to have length exactly [1, Ñ], e.g. P = a_{0} + [1, Ñ] · v.

The key observation is that we can partition this arithmetic progression P = a_{0} + [1, Ñ] · v into 2N_{2} disjoint arithmetic progressions bN_{1}v + P_{0} for b ∈ [0, 2N_{2}), where P_{0} := a_{0} + [1, N_{1}] · v. Each subprogression bN_{1}v + P_{0} is a proper arithmetic progression of length N_{1}, and so by the inductive hypothesis each bN_{1}v+P_{0} contains either a monochromatic arithmetic progression of length k, or a strongly polychromatic fan bN_{1}v + F (b) in bN_{1}v + P_{0} of radius k and degree d − 1. If there is at least one b in which the former case applies, we are done, so suppose that the latter case applies for every b. This implies that for every b ∈ [1, 2N_{2}) there exists a fan F (b) in P_{0} of radius k and degree d − 1 such that the translated fan bN_{1}v + F (b) is strongly polychromatic. Since P_{0} has length N_{1}, a simple counting argument shows that the number of fans of radius k and degree d − 1 in P_{0} is at most N_{1}^{d}, and the possible colors c(bN_{1}v + F (b)) of a strongly polychromatic fan is at most m^{d}. Thus the map b ↦ (F (b), c(bN_{1}v + F (b))) can be viewed as a m^{d}N_{1}^{d}-coloring of the interval [1, 2N_{2}). If we restrict this coloring to the upper half [N_{2}, 2N_{2}) of this interval and apply the outer inductive hypothesis, we thus see that [N_{2}, 2N_{2}) contains a proper arithmetic progression of length k − 1 which is monochromatic with respect to this coloring. In other words, there exist integers b_{0} + s, …, b_{0} + (k − 1)s ∈ [N_{2}, 2N_{2}) with s_{0} ≠ 0, a fan F = (a + [0, k) · r_{1}, …, a + [0, k) · r_{d}) in P_{0}, and a d-tuple c = (c_{0}, …, c_{d−1}) of colors such that the shifted fans (b_{0} + js)v + F are strongly polychromatic for all 1 ≤ j ≤ k − 1 with colors c. Note that by reversing the progression (b_{0} + s, …, b_{0} + (k − 1)s_{0}) if necessary we may assume that s is positive. In particular this means that s ∈ [0, N_{2}) and b_{0} ∈ [0, 2N_{2}). In particular a_{0} + b_{0}v ∈ b_{0}v + P_{0} ⊂ P. By observation (iii), the new fan

F̃ := (a + b_{0}v + [0, k) · sv, a + b_{0}v + [0, k) · (sv + r_{1}), …, a_{0} + b_{0}v + [0, k) · (sv + r_{d}))

is thus a weakly polychromatic fan in P. By observation (i), this means that F̃ is either strongly polychromatic, or contains a monochromatic arithmetic progression of length k, and in either case we are done.

If we apply this Lemma with d = m and N(k, m) := Ñ(k − 1, m, m), and then use observation (ii), Theorem 3.1 follows.

Remark 3.5. The bounds on N(k, m) obtained by this method are extremely large (of Ackermann type). A better bound (of primitive recursive type) was obtained by Shelah [19] as a corollary of his proof of the Hales-Jewett theorem, see Section 5. An even better bound is

N(k, m) ≤ 2 ↑ 2 ↑ m ↑ 2 ↑ 2 ↑ k + 9,

where x ↑ y = x^{y} denotes exponentiation; this bound was obtained by Gowers [6] as a corollary of his proof of Szemerédi’s theorem.

• Show that in order to prove van der Waerden’s theorem, it suffices to do so in the two-color case m = 2. (Hint: use an argument similar to that used to deduce Corollary 2.4 from Theorem 2.1).

• Using van der Waerden’s theorem, show that if the positive integers Z^{+} are finitely colored, then there exists a color c such that the set {n ∈ Z^{+} : c(n) = c} contains arbitrarily long proper arithmetic progressions. Conversely, show that if the previous claim is true, then it implies Van der Waerden’s theorem.

• Using van der Waerden’s theorem, show that if N is sufficiently large depending on k and m, and c : [1, N] → C is any m-coloring of [1, N], then [1, N] will contain at least c(k, m)N^{2} monochromatic progressions of length k. (Hint: apply van der Waerden’s theorem to each of the the progressions of length N(k, m) in [1, N] and then average. This argument is essentially due to Varnavides [21]).

• Let p be a prime number, and let F_{2^{p}} be the finite field with 2^{p} elements; one can think of this finite field as a p-dimensional vector space over the finite field F_{2}.

(a) Let x be an element of F_{2^{p}} not equal to 0 or 1. Show that the elements 1, x, x^{2}, …, x^{p−1} are linearly independent over F_{2}. (Hint: Let d be the least integer such that 1, x, x^{2}, …, x^{d} are linearly dependent. Show that these vectors in F_{2^{p}} generate a subfield G of F_{2^{p}} of cardinality 2^{d}. Now view F_{2^{p}} as a vector space over G and exploit the hypothesis that p is prime).

(b) Let x be a primitive element of the multiplicative group F_{2^{p}}\{0}, thus x^{a} ≠ 1 for all 1 ≤ a < 2^{p} − 1. Let V be any hyperplane in F_{2^{p}} (which may or may not pass through the origin 0). Show that for any proper arithmetic progression {a, a + r, …, a + (p − 1)r} in [1, 2^{p}], the set x^{a}, x^{a+r}, …, x^{a+(p−1)r} cannot all be contained in V. (Hint: if V contains the origin, use (a). If V does not contain the origin, consider the minimal polynomial P of x^{r}, i.e. the irreducible polynomial over F_{2} of minimal degree such that P (x^{r}) = 0. By using a homomorphism from F_{2^{p}} to F_{2} that maps V to 1, show that P (1) = 0, so that P has a factor of x − 1, contradicting irreducibility).

(c) Conclude that there exists a 2-colouring of [1, 2^{p}] which contains no progressions of length p. (This construction can be refined slightly, to replace 2^{p} with p2^{p}; see [3].

4. Rado’s theorem

The theorems of Schur and van der Waerden are in fact special cases of a more general theorem, called Rado’s theorem, to which we now turn.

Definition 4.1. Let I be a finite index set, and let Z^{I} := {(n^{(i)})_{i∈I} : n_{i} ∈ Z for all i ∈ I} be the additive group of I-tuples of integers; we identify Z^{{1,... ,k}} with Z^{k} in the usual manner. If n = (n^{(i)})_{i∈I} ∈ Z^{I} is such a I-tuple, and c : [1, N] → C is an m-coloring of [1, N], we say that n is monochromatic with respect to c if the set {n^{(i)} : i ∈ I} is a monochromatic subset of [1, N]. (For instance, a diagonal element (n)_{i∈I} is automatically monochromatic). If Γ is a sublattice of Z^{I}, we say that Γ has the partition-regular property for every integer m ≥ 1 there exists an N such that for every m-coloring c : [1, N] → C of [1, N] there exists at least one vector n ∈ Γ of Γ which is monochromatic with respect to c.

Examples 4.2. Schur’s theorem can be rephrased as the statement that the rank k lattice {(x_{1}, …, x_{k}, x_{1}+…+x_{k}) : x_{1}, …, x_{k} ∈ Z} ⊂ Z^{k+1} has the partition-regular property for any k. Van der Waerden’s theorem would imply the statement that the rank 2 lattice {(a, a + r, …, a + (k − 1)r) : a, k ∈ Z} ⊂ Z^{k} has the partition-regular property for any k, but this statement is in fact trivial since (a, a+r, …, a+(k−1)r) is automatically monochromatic when r = 0. On the other hand, we shall shortly show that the lattice {(a, a + r, …, a + (k − 1)r, r) : a, k ∈ Z} ⊂ Z^{k+1} has the partition-regular property, which implies van der Waerden’s theorem (since r is now constrained to lie in [1, N] and thus will not be zero).

The problem of determining when a lattice Γ enjoys the partition-regular property is answered by Rado’s theorem. To state this theorem requires some notation. If I be a finite index set and J is a subset of I, we define the vector e_{J} ∈ Z^{I} by e_{J} := (1_{i∈J})_{i∈I}, or in other words e_{J}^{(i)} = 1 when i ∈ J and e_{J}^{(i)} = 0 when i ≠ J. In particular we can define the basis vectors e_{j} for any j ∈ I by setting e_{j} := e_{{j}}. We recall that ⟨X⟩ denotes the additive group generated by the elements of X, thus for instance Z^{I} = ⟨{e_{i} : i ∈ I}⟩.

Theorem 4.3 (Rado’s theorem). [14] Let Γ be a lattice in Z^{I}. Then the following are equivalent:

• (i) Γ has the partition-regular property.

• (ii) There exists a partition I = I_{1} ∪ … ∪ I_{s} of I into disjoint non-empty sets, and vectors v_{1}, …, v_{s} ∈ Γ such that

v_{q} ∈ b_{q}e_{I_{q}} + ⟨{e_{i} : i ∈ I_{1} ∪ … ∪ I_{q−1}}⟩

for all 1 ≤ q ≤ s and some non-zero integer b_{q} (thus for instance v_{1} is an non-zero integer multiple of e_{I_{1}}, while v_{2} is a non-zero integer multiple of e_{I_{2}} plus an arbitrary integer combination of basis elements in {e_{i} : i ∈ I_{1}}, v_{3} is a non-zero integer multiple of e_{I_{3}} plus an arbitrary integer combination of basis elements in {e_{i} : i ∈ I_{1} ∪ I_{2}}, and so forth).

Examples 4.4. For the lattice {(x_{1}, …, x_{k}, x_{1} + … + x_{k}) : x_{1}, …, x_{k} ∈ Z} corresponding to Schur’s theorem, we can take I_{1} := {1, k +1}, I_{2} := {2}, …, I_{k} := {k} and v_{q} := e_{q}+e_{k+1} for 1 ≤ r ≤ k. For the lattice {(a, a+r, …, a+(k−1)r, r) : a, k ∈ Z} discussed earlier in relation to van der Waerden’s theorem, take I_{1} := {1, …, k}, I_{2} := {k +1}, v_{1} := e_{1} +…+e_{k}, v_{2} = e_{2} +2e_{3} +…+(k −1)e_{k} +e_{k+1}. On the other hand, we can use Rado’s theorem to show that the lattice {(3x, 3y, x+y) : x, y ∈ Z} does not have the partition regular property.

Proof We begin by proving that (i) implies (ii). We first perform a simple trick to eliminate all the “torsion” from the problem. Let V be the Q-subspace of Q^{I} which is generated by the lattice Γ, then Γ is a lattice of full rank in V. In particular, Z^{I}∩V ⊃ Γ is also a lattice of full rank in V, and hence the quotient group (Z^{I}∩V)/Γ is finite. In particular, (Z^{I} ∩V)/Γ is a t-torsion group for some t > 0, which implies that t · (Z^{I} ∩ V) ⊂ Γ. To prove that Γ obeys (ii) it thus suffices to show that Z^{I} ∩ V obeys (ii), since the claim then follows by multiplying all the v_{q} by the integer t. On the other hand, since Γ obeys the partition-regular property, the larger lattice Z^{I} ∩ V also clearly obeys this property. Thus without loss of generality we may in fact reduce to the case when Γ = Z^{I} ∩ V.

Let p be a large prime number (depending on V) to be chosen later. We p − 1-color the positive integers c : Z^{+} → (Z/p·Z)\{0} by the invertible elements in Z/p·Z, by defining c(p^{m}n) := n mod p for all integers m ≥ 0 and all integers n ≥ 1 coprime to p. Since Γ has the partition-regular property, we see that there must exist a vector (v^{(i)})_{i∈I} ∈ Γ which is monochromatic for some color c ∈ (Z/p · Z)\{0}, thus for each i ∈ I we may write v^{(i)} = p^{m^{(i)}}n^{(i)} for some n^{(i)} = c mod p and m^{(i)} ≥ 0. Let 0 ≤ M_{1} < M_{2} < … < M_{s} denote all the elements of {m^{(i)} : i ∈ I} arranged in increasing order, and for each 1 ≤ q ≤ s let I_{q} := {i ∈ I : m^{(i)} = M_{q}}. Then the I_{q} clearly partition I.

To conclude (ii), we need to show that for each 1 ≤ q ≤ s, the vector e_{I_{q}} lies in the span of V and {e_{i} : i ∈ I_{1} ∪ … ∪ I_{q−1}}, since one can then use linear algebra (over the rationals Q) and clear denominators to find v_{q}. Fix 1 ≤ q ≤ s, and suppose for contradiction that e_{I_{q}} was not in this span. Then by duality, there exists a vector w_{q} ∈ Q^{I} which was orthogonal to V and all of the {e_{i} : i ∈ I_{1} ∪ … ∪ I_{q−1}}, but which was not orthogonal to e_{I_{q}}. By multiplying w_{q} by an integer we may take w_{q} ∈ Z^{I}. Note that w_{q} depends only on I_{1}, …, I_{q−1}, which are subsets of I, and so w_{q} can be bounded by a quantity depending only on V and I (and hence independent of p).

Since w_{q} is orthogonal to V, it is in particular orthogonal to v. Thus

∑_{i∈I} p^{m^{(i)}}n^{(i)}w_{q}^{(i)} = 0.

Since w_{q} is orthogonal to {e_{i} : i ∈ I_{1} ∪ … ∪ I_{q−1}}, the contribution of the i ∈ I_{1} ∪ … ∪ I_{q} to the above sum vanishes. If we then work modulo p^{M_{q}+1} and use the fact that all the n^{(i)} are equal to c mod p, we obtain

∑_{i∈I_{q}} p^{M_{q}}cw_{q}^{(i)} = 0 mod p^{M_{q}+1}

Since c is invertible mod p, we thus have

∑_{i∈I_{q}} w_{q}^{(i)} = 0 mod p

Since the w_{q} are bounded independently of p, if we take p large enough we thus conclude that

∑_{i∈I_{q}} w_{q}^{(i)} = 0

which contradicts the hypothesis that w_{q} is orthogonal to e_{I_{q}}. This concludes the proof of (ii).

Finally, we prove that (ii) implies (i). Let B be the product of all the b_{j}. Let A be an integer so large that all the co-ordinates of v_{1}, …, v_{s} have magnitude less than A. Let m ≥ 1 be an arbitrary integer. We shall need a sequence

1 ≪ N_{ms} ≪ … ≪ N_{1} ≪ N_{0}

of extremely large numbers to be chosen later; N_{ms} will be assumed sufficiently large depending on A, B, s, m, while N_{ms−1} will be assumed sufficiently large depending on A, B, s, m, N_{ms}, and so forth, with N_{0} being extremely large, depending on all other variables. (The precise dependence can be quantified by using van der Waerden’s theorem, but we will not do so here for brevity).

Let c : [1, N_{0}] → C be an m-coloring of c. Our task is to locate a monochromatic vector of Γ. We first need an auxiliary sequence of progressions.

Lemma 4.5. There exists a monochromatic proper arithmetic progression P_{j} = a_{j}+[−N_{j}, N_{j}]·r_{j} in [1, N_{ms+1}] for each 1 ≤ j ≤ ms, such that for every 1 ≤ j ≤ ms, the numbers r_{j}, a_{j} are multiples of Br_{j−1} and obey the bounds

|r_{j}|, |a_{j}| ≤ C(N_{j}, m)B|r_{j−1}|  (1)

for some constant C(N_{j}, m) depending only on N_{j} and m. Here we adopt the convention that r_{0} := 1.

Proof Let 1 ≤ j ≤ ms, and assume inductively that the progressions P_{1}, …, P_{j−1} have already been chosen obeying the desired properties (this hypothesis is vacuous for j = 1). We apply van der Waerden’s theorem to the progression [1, C(N_{j}, m)] · Br_{j−1}, which will be contained in [1, N_{0}] if N_{0} is large enough depending on N_{1}, …, N_{j}, B and m (here we use (1) recursively to control r_{j−1}). If C(N_{j}, m) is large enough, van der Waerden’s theorem allows us to locate a monochromatic proper arithmetic progression P_{j} = a_{j} + [−N_{j}, N_{j}] · r_{j} in [1, C(N_{j}, Br_{j−1})]. By construction we see that a_{j}, r_{j} are multiples of Br_{j−1} and obey the bounds (1), and the claim follows.

Each of the ms progressions P_{j} = a_{j} +[−N_{j}, N_{j}]·r_{j} constructed by the above lemma is monochromatic with some color c_{j}. Since there are at most m colors, we thus see from the pigeonhole principle that we can find integers 1 ≤ j_{1} ≤ … ≤ j_{s} ≤ ms such that the progressions P_{j_{1}}, …, P_{j_{s}} all have the same color, say c. Now consider the vector v ∈ Γ defined by

v = ∑_{q=1}^{s} \frac{a_{j_{q}}}{b_{q}} v_{q}.

Note that b_{q} divides B, which in turn divides a_{j_{q}}, so v is indeed an integer combination of the v_{r} and thus lives in Γ.

Consider the i^{th} component v^{(i)} of v for some index i ∈ I. Since I is partitioned into I_{1}, …, I_{s}, we have i ∈ I_{q_{0}} for some 1 ≤ q_{0} ≤ s. By the properties of v_{q}, we thus see that

v^{(i)} = a_{j_{q_{0}}} + ∑_{q=q_{0}+1}^{s} \frac{a_{j_{q}}}{b_{q}} v_{q}^{(i)}.

By construction of the v_{q}, every term in the sum is a multiple of r_{j_{q_{0}}} . By (1) (bounding a_{j_{q}} by O(A)) we then have

v^{(i)} = a_{j_{q_{0}}} + O(C(N_{j_{q_{0}} +1}, …, N_{ms}, B, A, m, s))r_{j_{q_{0}}} .

If we choose N_{j_{q_{0}}} sufficiently large depending on the parameters N_{j_{q_{0}} +1}, …, N_{ms}, B, A, m, s, we thus have v^{(i)} ∈ a_{j_{q_{0}}} + [−N_{j_{q_{0}}} , N_{j_{q_{0}}} ] · r_{j_{q_{0}}} = P_{j_{q_{0}}} , and in particular v^{(i)} has color c. Since i was arbitrary, we see that v is monochromatic as desired.

For further discussion of issues related to partition regularity and Rado’s theorem, see [12].

• (Rado’s theorem, original formulation) Let A be an n × m matrix whose entries are all rational, and let C_{1}, …, C_{m} be the m columns of A (thought of as elements of Q^{n}). We say that A obeys the columns property if the set [1, m] can be partitioned as I_{1} ∪ … ∪ I_{s}, where for each I_{j}, the column vector ∑_{i∈I_{j}} C_{i} is a linear combination of the columns {C_{m} : m ∈ I_{1} ∪ … ∪ I_{j−1}} (so in particular ∑_{i∈I_{1}} C_{i} = 0). Show that the lattice Γ := {x ∈ Z^{n} : Ax = 0} has the partition-regular property if and only if A has the columns property. (Remark: if the columns property fails, then this formulation of Rado’s theorem implies that there is some coloring of the integers for which Γ has no monochromatic vector; however, Rado’s Boundedness Conjecture [14] asserts that one choose this coloring so that the number of colors depends only on n and m, and not on the specific entries of the matrix A. This conjecture remains open.)

• Let a_{1}, …, a_{n} be non-zero integers. Show that a necessary and sufficient condition in order that every coloring of the positive integers admits a monochromatic set {x_{1}, …, x_{n}} such that a_{1}x_{1} + … + a_{n}x_{n} = 0 is that there exists some non-empty set I ⊂ [1, N] such that ∑_{i∈I} a_{i} = 0.

• (Consistency Theorem) Show if two lattices Γ and Γ′ have the partitionregular property, then their direct sum Γ ⊕ Γ′ also has the partition regularity property. (This is easy to prove using Rado’s theorem, but quite difficult without it!).

• Suppose one colors the positive integers Z^{+} into finitely many colors. Show that there exists a color c such that for every lattice Γ with the partitionregular property, there exists a vector v ∈ Γ which is monochromatic with the specified color c. The point here is that the color c is independent of Γ, otherwise the claim is a tautology. (Hint: Assume for contradiction that for each color c there was a lattice which had no monochromatic vector of that color. Then obtain a contradiction from the Consistency theorem).

• (Folkman’s theorem) [5] Show that if one colors the positive integers Z^{+} into finitely many colors, then for any m ≥ 1 there exists infinitely many vectors v = (v_{1}, …, v_{m}) ∈ Z_{+}^{m} such that the set [0, 1]^{m} · v\0 = {∑_{i∈I} v_{i} : I ⊂ [1, m], I ≠ ∅} is monochromatic. (In fact one can take m to be infinite; this is Hindman’s theorem [11] and is somewhat more difficult to prove; see [9] for further discussion).

5. The Hales-Jewett theorem

The van der Waerden theorem can be generalized to many dimensions, as follows:

Theorem 5.1 (Gallai’s theorem). Let k ≥ 1, d ≥ 1, m ≥ 1, and let v_{1}, …, v_{k} be elements of Z^{d}. Then there exists an N = N(k, d, m, v_{1}, …, v_{k}) such that for every m-coloring of the cube [1, N]^{d} ⊂ Z^{d}, there exists a monochromatic set of the form {x + rv_{1}, …, x + rv_{k}} for some x ∈ Z^{d} and some non-zero integer r.

Note that van der Waerden’s theorem is a special case of this theorem where d = 1 and v_{j} = j. This theorem can be proven by modifying the proof of van der Waerden’s theorem (see e.g. [9]), but we shall prove it as a special case of an even more general theorem, the Hales-Jewett theorem [10]. This theorem can be stated in a purely combinatorial form (indeed, can be viewed as the combinatorial essence of the van der Waerden and Gallai theorems, in which the arithmetic structure is completely removed). However, it will be convenient to write it in the language of additive groups.

Definition 5.2. Let Z be an additive group, and let I be an index set. We let Z^{I} be the additive group Z^{I} = {(x^{(i)})_{i∈I} : x^{(i)} ∈ Z for all i ∈ I}. If x ∈ Z^{I} and J ⊂ I, we say that x vanishes on I if x^{(i)} = 0 for all i ∈ J. Given any n ∈ Z^{I} and x ∈ Z, we define the product n · x ∈ Z^{I} by the formula (n · x)^{(i)} := n · x^{(i)}. Given any non-empty J ⊂ I and A ⊂ Z, we define the sets

A · e_{J} := {a · e_{J} : a ∈ A},

where e_{J} = (1_{i∈J})_{i∈I} ∈ Z^{I} is as in the previous section. If J_{1}, …, J_{d} are disjoint subsets of I and x_{0} ∈ Z^{I} which vanishes on J_{1}∪…∪J_{d}, we define the d-dimensional combinatorial affine space over A with active co-ordinates J_{1}, …, J_{d} and origin x_{0} to be the set

x_{0} + ∑_{j=1}^{d} A · e_{J_{j}} = {x_{0} + ∑_{j=1}^{d} a_{j} · e_{J_{j}} : a_{1}, …, a_{d} ∈ A}.

In other words, x ∈ x_{0} +∑_{j=1}^{d} A·e_{J_{j}} if and only if the function i ↦ x^{(i)} is constant

on each J_{j}, and agrees with the function i ↦ x_{0}^{(i)} outside of J_{1} ∪ … ∪ J_{d}. In the d = 1 case we refer to a combinatorial affine space x_{0} + A · e_{J} as a combinatorial line.

Remark 5.3. It is convenient to think of A as an alphabet, and A^{I} as words of length |I| whose letters lie in the alphabet A. (Elements of Z^{I} are then more exotic words, whose letters can be additional symbols such as 0). Combinatorial lines and affine spaces then correspond to words with certain “wildcards”. For instance, if A = {a, b, c} and |I| = 7, then a typical element of A^{I} might be baacbab. A typical combinatorial line would be the collection of all words of the form baxcbxb, where x ranges in A, or in other words ba0cb0b + A · 0010010. A typical combinatorial affine space would be the collection of all words of the form baxcyxy, where x, y range independently in A.

Theorem 5.4 (Hales-Jewett theorem). [10] Let r ≥ 1, and m ≥ 1, and let A be a finite subset of an additive group Z. Then there exists an integer n = n(|A|, m, r) ≥ 1 such that given any set I of cardinality n, and any m-coloring of the set A^{I} ⊂ Z^{I}, the set A^{I} contains a monochromatic r-dimensional combinatorial affine subspace over A.

Remark 5.5. The additive structure of Z is in fact irrelevant. If one takes an arbitrary bijection ϕ : A → A′ mapping A to another finite subset A′ of another additive group Z′, and maps A^{I} to (A′)^{I} correspondingly, one can easily verify that combinatorial affine spaces map to combinatorial affine spaces and so the substance of the Hales-Jewett theorem is unchanged (see exercises).

This theorem implies both the van der Waerden theorem and Gallai’s theorem (see exercises). We shall give two proofs: the original proof, which adapts the color focusing method used in previous sections, and a proof of Shelah, which gives a superior bound on N than the color focusing proof for the Hales-Jewett theorem (and hence for the van der Waerden and Gallai theorems).

5.6. The color focusing proof. We begin with the color focusing proof, which will be very similar to the proof of van der Waerden’s theorem. The first step is to reduce to the case r = 1, i.e. to reduce to proving

Theorem 5.7 (One-dimensional Hales-Jewett theorem). Let m ≥ 1, and let A be a finite subset of an additive group Z. Then there exists an integer n = n(|A|, m) ≥ 1 such that given any set I with n elements, and any m-coloring of the set A^{I} ⊂ Z^{I}, the set A^{I} contains a monochromatic combinatorial line x_{0} + A · e_{J}.

To see how the one-dimensional Hales-Jewett theorem implies the general case, we take n = rn′ for some large integer M, and observe that A^{I} is isomorphic to (A^{r})^{I′} for some I′ with n′ elements. We now apply the one-dimensional Hales-Jewett theorem with Z replaced by Z^{r}, A replaced by A^{d}, and I replaced by I′, to conclude that (if n and hence n′ is sufficiently large) that (A^{r})^{I′} contains a monochromatic combinatorial affine line x_{0}+A^{r} ·e_{J′} over A^{d} for some J′ ⊂ I′, and some x_{0} ∈ (Z^{r})^{I′} which vanishes on J′. But if one then uses the isomorphism between (A^{r})^{I′} and A^{I}, we can view this combinatorial affine line over A^{r} as a d-dimensional combinatorial affine space over A, and the general Hales-Jewett theorem follows.

It remains to prove Theorem 5.7. As in the proof of van der Waerden’s theorem, there will be two induction loops. The outer induction will be on the size of A (which is analogous to the k parameter in van der Waerden’s theorem). The base case |A| = 1 is trivial. The case |A| = 2 is also very easy, since in this case onen can check that any two points in A^{I} form a combinatorial line, and so the claim follows immediately from the pigeonhole principle once one takes N to be large enough. So now let us assume^{1}. |A| ≥ 3 and the claim has already been proven for smaller values of A. Since we may apply arbitrary bijections to A, let us assume that A contains 0, and write A^{∗} := A−{0}, thus we assume Theorem 5.7 is already proven for A^{∗} (we refer to this as the outer induction hypothesis).

Once again, we need the notion of a polychromatic fan.

Definition 5.8. Given any combinatorial line l = x_{l} + A · e_{J_{l}} in A^{I}, we refer to x_{l} as the origin of the line and J_{l} as the active co-ordinates, and l^{∗} := l\{x_{l}} as the spoke of the line (note that this is a combinatorial line over A^{∗}). Given any d ≥ 1, we define a fan of degree d to be an d-tuple F = (x_{F} + A · e_{J_{1}}, …, x_{F} + A · e_{J_{d}}) of combinatorial lines with common origin x_{F} (which must then vanish on J_{1} ∪ …∪J_{d}); we assume the sets J_{1}, …, J_{d} of active co-ordinates to be distinct but not necessarily disjoint. We say that the fan is weakly polychromatic if all the spokes x_{F} + A^{∗} · e_{J_{j}}, 1 ≤ j ≤ d are monochromatic with distinct colors c_{j}, and strongly polychromatic if in addition the origin has a color c_{0} distinct from c_{1}, …, c_{d}. In these cases we refer to the d + 1-tuple c(F) := (c_{0}, c_{1}, …, c_{d}) as the colors of the fan.

Once again, we make two simple, and one slightly less simple, observations about polychromatic fans:

• (i) A weakly polychromatic fan is either strongly polychromatic, or contains a monochromatic combinatorial line.

• (ii) A strongly polychromatic fan cannot have degree m.

• (iii) Let I′ ⊂ I, and let F = (x_{F} + A · e_{J_{1}}, …, x_{F} + A · e_{J_{d}}) be a fan of degree d in A^{I′}. We write Z^{I} as the direct sum Z^{I} = Z^{I′} ⊕ Z^{I\I′}, and similarly A^{I} = A^{I′} ⊕ A^{I\I′}. Suppose that there is a line x_{0} + A · e_{J_{0}} ∈ A^{I\I′} such that the fans x_{0} + a · e_{J_{0}} ⊕ F are all strongly polychromatic with the same colors c(x_{0} + a · e_{J_{0}} ⊕ F) = c for all a ∈ A^{∗}. Then the fan

F̃ := (x_{0} ⊕ x_{F} + A · e_{J_{0}}, x_{0} ⊕ x_{F} + A · e_{J_{0}∪J_{1}}, …, x_{0} ⊕ x_{F} + A · e_{J_{0}∪J_{d}})

is a weakly polychromatic fan of degree d + 1 in A^{I}.

We can now give the analogue of Lemma 3.4:

Lemma 5.9. For any d ≥ 0 there exists a positive integer ñ(|A_{∗}|, m, d) such that given any set I of cardinality ñ(|A_{∗}|, m, d) and any m-colouring of A^{I}, the set A^{I} contains either a monochromatic combinatorial line, or a strongly polychromatic fan of degree d.

1Actually, the following argument also works in the |A| = 2 case, but collapses to a very tortuous rephrasing of the above pigeonhole argument.

Proof As before, we shall induct on the d variable. The base case d = 0 is trivial. Assume now that d > 1 and the claim has already been proven for d − 1 (this is the inner induction hypothesis). We define ñ = ñ(|A_{∗}|, m, d) by the formula ñ := n_{1} + n_{2}, where n_{1} := ñ(|A_{∗}|, m, d − 1) and n_{2} := n(|A_{∗}|, m^{d}|A|^{dn_{1}}), which are guaranteed to be finite by the inner and outer inductive hypotheses respectively, and let c : A^{I} → C be an m-colouring of A^{I}, where I is an index set of cardinality ñ.

We partition I = I_{2} ∪ I_{1} where I_{1} has n_{1} elements and I_{2} has n_{2} elements; this induces a decomposition Z^{I} ≡ Z^{I_{2}} ⊕ Z^{I_{1}}. For each b ∈ A^{I_{2}}, the set b ⊕ A^{I_{1}} is clearly isomorphic to A^{I_{1}}, and so by the inner induction hypothesis we see that each such set b ⊕ A^{I_{1}} either contains a monochromatic combinatorial line, or a strongly polychromatic fan b ⊕ F (b) of degree d − 1 and colors c(b ⊕ F (b)). If there is at least one b ∈ A^{I_{2}} for which the former case applies then we are done, so suppose that the latter case applies for every b ∈ A^{I_{2}}. The number of possible fans F (b) is at most |A|^{dn_{1}}, and the number of possible colors c(b) is at most m^{d}, hence the map b ↦ (F (b), c(b ⊕ F (b))) is a m^{d}|A|^{dn_{1}}-coloring of A^{I_{2}}. By the outer induction hypothesis, we can thus find a combinatorial line l in A^{I_{2}} which is monochromatic with respect to this coloring, hence there is a fan F of degree d−1 in A^{I_{1}} and colors c ∈ C^{d} such that for every b ∈ l the fans b ⊕ F are strongly polychromatic with colors c. By observation (iii) this implies that A^{I} contains a weakly polychromatic fan of order d, and then by observation (i) the lemma follows.

If we apply this Lemma with d = m and n(|F |, m) := ñ(|F_{∗}|, m, m), and then use observation (ii), Theorem 5.7 follows. This concludes the color focusing proof of the Hales-Jewett theorem.

5.10. Shelah’s proof. Now we present Shelah’s proof [19] of the Hales-Jewett theorem, which proceeds along somewhat different lines and will give a better bound. There are a number of differences between this proof and the previous one. Firstly, one does not reduce to the one-dimensional case r = 1, but rather retains r as a free parameter to aid in closing the induction step. Secondly, instead of using a double inductive argument (which ultimately leads to bounds of Ackermann type), one uses only a single induction, inducting on the cardinality of the set A. Finally, whereas the Hales-Jewett proof requires one to continually expand the color set (which is one reason for the Ackermann-type bounds), Shelah’s argument never changes the color set C, except in one part of the argument in which all the constants are well under control. These differences will give a final bound for n(|A|, m) which is primitive recursive rather than Ackermann type, although it is still somewhat large (see exercises).

We turn now to the details. As discussed above we shall induct on A. The case |A| = 1 is trivial, so let us assume inductively that |A| ≥ 2 (note now that r is not necessarily 1, the case |A| = 2 is not particularly easy!), and that the claim has already been proven for smaller A. In particular we can choose two distinct elements y and z of A, we can assume that the Hales-Jewett theorem has already been proven for the set A^{∗} := A\{z}.

The color focusing proof relied crucially on the concept of a polychromatic fan, which was basically a tool to convert results on monochromatic lines over A^{∗} to results on monochromatic lines over A. The analogous concept here shall be that of yz-insensitive affine spaces, which we shall use to convert results on monochromatic lines over A\{z} to results on monochromatic lines over A.

Definition 5.11. Let c : A^{I} → C be a m-coloring, and let V = x_{0} + A · e_{J_{1}} + … + A · e_{J_{r}} be an r-dimensional combinatorial affine space over A. If J_{i}, 1 ≤ i ≤ r is one of the sets of active co-ordinates, we say that J_{i} is yz-insensitive if we have

c(x + y · e_{J_{i}}) = c(x + z · e_{J_{i}}) for all x ∈ x_{0} + ∑_{1≤i′≤r:i′≠i} A · e_{J_{i}}.

We say that V is yz-insensitive of order d for some 0 ≤ d ≤ r if there are at least d sets J_{i_{1}}, …, J_{i_{d}} of yz-insensitive sets of active co-ordinates. If d = r we say that V is fully yz-insensitive.

The analogue of Lemma 5.9 is

Lemma 5.12. Let n_{0}, n_{1}, n_{2} ≥ 0. Then if n is a sufficiently large integer (depending on n_{0}, n_{1}, n_{2}, m, |A|), every n_{0} + n-dimensional combinatorial affine space V in A^{I} which is yz-insensitive of order n_{0}, contains an n_{0} + n_{1} + n_{2}-dimensional combinatorial affine space V′ which is yz-insensitive of order n_{0} + n_{1}.

Let us assume this Lemma for the moment and conclude the proof of the Hales-Jewett theorem.

The space A^{I} is a |I|-dimensional combinatorial affine space which is yz-insensitive of order 0. Thus if we apply the above lemma with (n_{0}, n_{1}, n_{2}) = (0, ñ, 0), where ñ = n(|A_{∗}|, m) is known to be finite by the induction hypothesis, we can find a ñ-dimensional combinatorial affine space V′ = x_{0} + A · e_{J_{1}} + … + A · e_{Jñ} ⊂ A^{I} which is fully yz-insensitive. We can define a bijection π : Añ → V′ by the formula

π(a_{1}, …, añ)) := x_{0} + a_{1} · e_{J_{1}} + … + añ · e_{Jñ}.

The composition c ∘ π is thus a coloring of Añ, which in turn induces a coloring of (A^{∗})ñ. By the induction hypothesis, (A^{∗})ñ, then contains a monochromatic (with respect to c ∘ π) combinatorial subspace y_{0} + A^{∗} · e_{K_{1}} + … + A^{∗} · e_{K_{r}} for some disjoint non-empty subsets K_{1}, …, K_{r} of [1, ñ]. This implies that the set

π(y_{0} + A^{∗} · e_{K_{1}} + … + A^{∗} · e_{K_{r}}) ⊆ V′

is monochromatic with respect to c. But since V is fully yz-insensitive, we thus see that

π(y_{0} + A · e_{K_{1}} + … + A · e_{K_{r}})

is also monochromatic with respect to c. But this is a r-dimensional combinatorial affine space over A in A^{I}, and we are done.

It remains to prove Lemma 5.12. The key idea is already contained in the case (n_{0}, n_{1}, n_{2}) = (0, 1, 0), which we isolate as follows:

Lemma 5.13. Let n ≥ m. Then every n-dimensional combinatorial affine space V in A^{I} will contain a combinatorial line which is fully yz-insensitive.

Proof We expand

V = x_{0} + A · e_{J_{1}} + … + A · e_{J_{n}}

and then isolate the elements v_{0}, …, v_{n} ∈ V by defining

v_{j} := x_{0} + ∑_{1≤i≤j} y · e_{J_{i}} + ∑_{j<i≤n} z · e_{J_{n}}.

(For instance, if V = A^{5}, then v_{0}, v_{1}, v_{2}, v_{3}, v_{4}, v_{5} would be the words zzzzz, yzzzz, yyzzz, yyyzz, yyyyz, yyyyy). Since n ≥ m, we see from the pigeonhole principle that there must exist 1 ≤ j < j′ ≤ n such that v_{j} and v_{j′} have the same color. But this is the same as saying that the combinatorial line

x_{0} + ∑_{1≤i≤j} y · e_{J_{i}} + A · e_{J_{j+1}∪...∪J_{j′}} + ∑_{j′<i≤n} z · e_{J_{n}}

is fully yz-insensitive.

Now we can prove the general case of Lemma 5.12. We induct on n_{1}. The case n_{1} = 0 is trivial (by taking V′ := V). Now suppose that n_{1} > 0 and the claim has already been proven for n_{1} −1. Thus, in particular, we can find an integer n_{∗} (depending on n_{0}, n_{1}, n_{2}, m, |A|) such that every n_{0}+1+n_{∗}-dimensional combinatorial affine space V′′ which is yz-insensitive of order n_{0} + 1, contains an n_{0} + n_{1} + n_{2}-dimensional combinatorial affine space V′ which is yz-insensitive of order n_{0} +n_{1}. Thus in order to conclude the Lemma, it suffices to show that if n is large enough (depending on n_{0}, n_{∗}, m, |A|), that every n_{0} + n-dimensional combinatorial affine space V which is yz-insensitive of order n_{0} will contain an n_{0} + 1 + n_{∗}-dimensional combinatorial affine space V′′ which is yz-insensitive of order n_{0} + 1.

We may of course take n > n_{∗}. Let us expand

V = x_{0} + ∑_{1≤i≤n_{0}} A · e_{J_{i}} + ∑_{1≤j≤n_{∗}} A · e_{K_{j}} + ∑_{1≤k≤n−n_{∗}} A · e_{L_{k}}

with J_{1}, …, J_{n_{0}} as the yz-insensitive co-ordinates. We rewrite this as

V = V_{0} + W_{0} + π(A^{n})

where V_{0} is the n_{0}-dimensional combinatorial affine space V_{0} := x_{0}+∑_{1≤i≤n_{0}} A·e_{J_{i}}, W_{0} is the n_{∗}-dimensional combinatorial affine space W_{0} := ∑_{1≤j≤n_{∗}} A · e_{K_{j}}, and π : A^{n−n_{∗}} → ∑_{1≤j≤n} A · e_{K_{j}} is the bijection

π(a_{1}, …, a_{n−n_{∗}}) := ∑_{1≤k≤n−n_{∗}} a_{j} · e_{L_{k}}.

We now introduce a m^{|A|^{n_{0}+n∗}} -coloring of A^{n}, defining a coloring c̃ : A^{n} → C^{V_{0}×W} by the formula

c̃(a) := (c(b + c + π(a)))_{b∈V_{0};c∈W} .

If n − n_{∗} is greater than or equal to m^{|A|^{n_{0}+n∗}}, then we can apply Lemma 5.13 and locate a fully yz-insensitive combinatorial line w_{0} + A · e_{M} ⊆ A^{n−n_{∗}}, thus

c(b + c + π(w_{0} + y · e_{M})) = c(b + c + π(w_{0} + z · e_{M})) for all b ∈ V_{0}, c ∈ W_{0}. (2)

Now we introduce the n_{0} + 1 + n_{∗}-dimensional combinatorial affine space

V′′ := V_{0} + W_{0} + π(w_{0} + A · e_{M}) ⊆ V,

which has as sets of active co-ordinates J_{1}, …, J_{n_{0}}, K_{1}, …, K_{n_{∗}}, and ⋃_{k∈M} L_{k}. The sets J_{1}, …, J_{n_{0}} are already known to be yz-insensitive, and (2) shows that the set ⋃_{k∈M} L_{k} is also yz-insensitive. Thus V′′ is yz-insensitive of order n_{0} + 1 as desired. This closes the inductive step for Lemma 5.12, which concludes Shelah’s proof of the Hales-Jewett theorem.

Remark 5.14. Shelah’s bounds for the Hales-Jewett theorem have recently been improved in the context of the van der Waerden theorem (see [6]) and Gallai’s theorem (see [7], [13]). In the k = 3 cases of these theorems, even better bounds are known.

• Verify the claims in Remark 5.5.

• Let F be a finite field, and let d, m ≥ 1. Using the Hales-Jewett theorem, show that there exists an integer N = N(d, m, |F |) ≥ 1 such that given any m-coloring of F^{N}, the space F^{N} contains a monochromatic d-dimensional affine subspace over the field F (i.e. a translate of a space linearly isomorphic to F^{d}). (The point here is that one can convert combinatorial affine subspaces into ordinary affine subspaces in the sense of linear algebra).

• Show that in order to prove Gallai’s theorem, it suffices to do so in the case when k = d and v_{1}, …, v_{d} is the standard basis of Z^{d}.

• Use the Hales-Jewett theorem to prove the van der Waerden and Gallai theorems. (Hint: if one has a coloring c : a + [0, N) · v → C of some proper progression, then one can also define a coloring c̃ : [0, k)^{n} → C whenever k^{n} ≤ N by the formula

c̃(j_{1}, …, j_{n}) := c(a + (∑_{i=0}^{n−1} j_{i}k^{i}) · v).

Apply the one-dimensional Hales-Jewett theorem to c̃ to conclude the van der Waerden theorem for c. A similar argument yields the Gallai theorem from the multi-dimensional Hales-Jewett theorem).

• Show that in order to prove the Hales-Jewett theorem, it suffices to do so in the two-color, one-dimensional case m = 2, r = 1.

• [19] Let ↑ denote exponentiation x ↑ y := x^{y}, let ↑↑ denote tower exponen-

tiation

x ↑↑ y = x ↑ x ↑ … ↑ x

with x appearing y times on the right-hand side, and let ↑↑↑ denote iterated tower exponentiation

x ↑↑↑ y = x ↑↑ x ↑↑ … ↑↑ x.

Show that Shelah’s argument gives a bound of the form

n(|A|, 2, 1) ≤ 2 ↑↑↑ (C|F |)

for some absolute constant C. Note that while this bound is rather large, it is still substantially smaller than the bounds one would obtain from the color-focusing argument, which are not primitive recursive.

6. Polynomial analogues

The above additive Ramsey theorems were of “linear” type, in the sense that the monochromatic arithmetic structures one wished to find depended linearly (or in the case of the Hales-Jewett theorem, “combinatorially linearly”) on certain parameters. Recently there has been some interest in extending such results to “polynomial” type arithmetic structures. A typical result in this area is the following.

Theorem 6.1 (Polynomial van der Waerden theorem). [1] Let P_{1}, …, P_{k} : Z → Z be polynomials of one variable which are integer-valued on the integers, and which vanish at the origin (i.e. P_{j}(0) = 0 for all 1 ≤ j ≤ k). Then for any m ≥ 1 there exists a positive integer N = N(P_{1}, …, P_{k}; m) such that given any m-coloring of [1, N], there exists a monochromatic subset of [1, N] of the form {a+P_{1}(r), …, a+ P_{k}(r)} for some integers a, r ∈ Z with r non-zero.

Observe that by specializing to the linear case P_{j}(n) := jn one recovers the ordinary van der Waerden theorem.

The original proof of this theorem by Bergelson and Leibman [1] was topological. Recently Walters [22] has given a combinatorial proof of this theorem. As one might imagine, the proof proceeds by nested induction and color focusing techniques, and uses the ordinary van der Waerden theorem as a base case. The induction is in fact rather exotic, relying on a certain partial ordering on the space of tuples (P_{1}, …, P_{k}) of polynomials (this type of induction is known as polynomial ergodic theory induction, or PET induction). We will not detail the full argument here, but (following [22]) just give the first non-trivial case of the polynomial van der Waerden theorem beyond the linear case, and leave the construction of the general case to the exercises. More specifically, we shall show^{2}

Theorem 6.2. For any m ≥ 1 there exists a positive integer N = N(m) such that given any m-coloring c : [1, N] → C of [1, N], there exists a monochromatic subset of [1, N] of the form {a, a + r^{2}} for some integers a, r ∈ Z with r non-zero.

Proof We use the color focusing technique. For any integer a and any d ≥ 1, define a fan of degree d and origin a to be a d + 1-tuple of numbers of the form F = (a, a + r_{1}^{2}, …, a + r_{d}^{2}) where r_{1}, …, r_{d} are non-zero integers. If F is contained in [1, N], we define the colors c(F) ∈ C^{d+1} of this fan to be the d + 1-tuple c(F) := (c(a), c(a + r_{1}^{2}), …, c(a + r_{d}^{2})). We say that this fan is weakly polychromatic if the colors c(a + r_{1}^{2}), …, c(a + r_{d}^{2}) are all distinct, and strongly polychromatic if in fact all the d + 1 colors in c(F) are distinct.

Once again, we make two simple, and one somewhat less simple, observations about polychromatic fans.

2This particular result can also be proven by Fourier-analytic methods, and such methods give far superior quantitative bounds. However, it is not yet known how to extend such methods to more general situations; even the task of locating monochromatic subsets of the form {a, a+r^{2}, a+2r^{2}} for non-zero r seems beyond the reach of current Fourier methods, although one can still modify the color focusing argument below to obtain such sets.

• (i) A weakly polychromatic fan is either strongly polychromatic, or contains a monochromatic set of the form {a, a + r^{2}} for some non-zero r.

• (ii) A strongly polychromatic fan cannot have degree m.

• (iii) Let F = (a, a + r_{1}^{2}, …, a + r_{d}^{2}) be a fan of degree d contained in an interval [1, N_{1}] for some N_{1} ≥ 3, and suppose that there is a proper arithmetic progression P = b + [−L, L] · v ⊂ Z for some integers b, L, v with L, v ≥ N_{1} such that the point b + a − v^{2} and the translated fans x + F for x ∈ P are all contained in [1, N] and are disjoint from each other. Assume furthermore that the translated fans x + F are all strongly polychromatic with the same colors, thus c(x + F) = c for all x ∈ P. Then

(b + a − v^{2}, (b + a − v^{2}) + v^{2}, (b + a − v^{2}) + (v + r_{1})^{2}, …, (b + a − v^{2}) + (v + r_{d})^{2})

is a fan of degree d + 1 contained in [1, N] and is weakly polychromatic. (The point is that the integer b + a − v^{2} + (v + r_{j})^{2} lies in the fan x + F for x := b + 2r_{j}v, and |r_{j}| is bounded by \sqrt{N_{1}} and hence by L/2. The condition v ≥ N_{1} ensures that none of v, v + r_{1}, …, v + r_{d} can vanish).

The analogue of Lemma 3.4 is

Lemma 6.3. For any d ≥ 0 there exists a positive integer Ñ(m, d) such that any mcolouring of [1, Ñ(m, d)] contains either a monochromatic set of the form {a, a+r^{2}} for some non-zero r, or a strongly polychromatic fan of degree d.

Proof Once again, we induct on d. When d = 0 the claim is trivial, so suppose d > 0 and the claim has already been proven for d − 1. We now set N_{1} := max(Ñ(m, d − 1), 3), and Ñ(m, d) := N_{1}N_{2} where N_{1} is a very large integer (depending on N_{1}, m, d) to be chosen later. Then we can split the interval [1, Ñ(m, d)] into N_{2} translates N_{1}b + [1, N_{1}], where b ∈ [0, N_{2}). For each such translate N_{1}b+[1, N_{1}], we can apply the induction hypothesis (translated by N_{1}b) to conclude that N_{1}b + [1, N_{1}] contains either a monochromatic set of the form {a, a + r^{2}} for some non-zero r, or a strongly polychromatic fan bN_{1} +F (b) in bN_{1} +[1, N_{1}] degree d−1 with some colors c(b). If there is at least one b in which the former case applies, we are done, so suppose that the latter case applies for every b. The number of fans F (b) can be crudely bounded by N_{1}^{d}, and the number of colors by m^{d}, and so the map b ↦ (F (b), c(bN_{1} + F (b))) is a m^{d}N_{1}^{d}-coloring of the interval [1, N_{2}), and in particular of the smaller interval (N_{2} − \sqrt{N_{2}}, N_{2}). If N_{2} is large enough depending on m, d, N_{1}, we may apply the ordinary van der Waerden theorem (Theorem 3.1) to conclude the existence of a proper arithmetic progression b + [−2N_{1}, 2N_{1}] · v in (N_{2} − \sqrt{N_{2}}, N_{2}) with respect to this coloring. This implies that there exists a fan F = (a, a + r_{1}^{2}, …, a + r_{d}^{2}) of degree d − 1 in [1, N_{1}] and colors c ∈ C^{d} such that for every x ∈ bN_{1} + [−2N_{1}, 2N_{1}] · vN_{1}, the translated fan x + F is strongly polychromatic with colors c. Also observe from construction that |v| < \sqrt{N_{2}} and so the point bN_{1} +a−(vN_{1})^{2} is positive and hence lies in [1, Ñ(m, d)]. Furthermore, since vN_{1} ≥ N_{1} it is clear that the translated fans x + F, x ∈ bN_{1} + [−2N_{1}, 2N_{1}] · vN_{1} are disjoint from each other and from bN_{1} + a − (vN_{1})^{2}. By observation (iii) we thus can locate a new fan F̃ in [1, Ñ(m, d)] which is weakly polychromatic of degree d, and hence by observation (i) we are done.

We can now conclude Theorem 6.2 by setting d := m and appealing to observation (ii), as in the proof of van der Waerden’s theorem (or the color focusing proof of the Hales-Jewett theorem).

Just as Van der Waerden’s theorem can be extended to higher dimensions as Gallai’s theorem, so too can the polynomial van der Waerden theorem:

Theorem 6.4 (Polynomial Gallai theorem). [1] Let k ≥ 1, d ≥ 1, m ≥ 1, and let P_{1}, …, P_{k} : Z → Z^{d} be R^{d}-valued polynomials (i.e. d-tuples of ordinary polynomials) which take values in Z^{d} on the integers, and which vanish at the origin. Then there exists an N = N(k, d, m, P_{1}, …, P_{k}) such that for every mcoloring of the cube [1, N]^{d} ⊂ Z^{d}, there exists a monochromatic set of the form {x + P_{1}(r), …, x + P_{k}(r)} for some x ∈ Z^{d} and some non-zero integer r.

We will not prove this theorem here. However, as in the linear case, these theorems are in turn consequences of a polynomial Hales-Jewett theorem. This theorem however takes a certain amount of work just to state it properly. As before, we shall phrase this theorem in the language of additive groups Z, but now in addition to the usual operations of addition and multiplication by integers on such a group Z, we now also need the notion of a tensor product and tensor extensions of polynomials.

Definition 6.5. If Z and Z′ are additive groups, we define the tensor product Z ⊗ Z′ to be the additive group formed by arbitrary integer-linear combinations of tensor products x ⊗ y with x ∈ Z, y ∈ Z′, quotiented by the constraints

x ⊗ (y + y′) = x ⊗ y + x ⊗ y′
(x + x′) ⊗ y = x ⊗ y + x′ ⊗ y
x ⊗ 0 = 0 ⊗ y = 0

for all x, x′ ∈ Z and y, y′ ∈ Z′. As (Z ⊗ Z′) ⊗ Z′′ and Z ⊗ (Z′ ⊗ Z′′) are canonically isomorphic, we shall treat the tensor product as an associative relation, thus we equate (x ⊗ y) ⊗ z and x ⊗ (y ⊗ z) for all x ∈ Z, y ∈ Z′, z ∈ Z′′. We define the n^{th} tensor power Z^{⊗n} of an additive group for n ≥ 0 recursively by setting Z^{⊗0} := Z, Z^{⊗1} := Z, and Z^{⊗n} := Z ⊗ Z^{⊗n−1} for n > 1. Similarly, given any x ∈ Z, we define x^{⊗n} ∈ Z^{⊗n} recursively by x^{⊗0} := 1, x^{⊗1} = x, and x^{⊗n} := x ⊗ x^{⊗n−1}. for all x ∈ Z.

We observe that for any index set I, the additive group (Z^{I})^{⊗n} is canonically isomorphic to Z^{I^{n}}, and we shall identify the two.

Theorem 6.6 (Polynomial Hales-Jewett theorem). [2] Let d, m ≥ 1, and let A_{1}, …, A_{d} be finite nonempty subsets of additive groups Z_{1}, …, Z_{d}. Then there exists an integer n = n(|A_{1}|, …, |A_{d}|, m, d) ≥ 1 such that given any set I with n elements, and any m-coloring of the set

X := A_{1}^{I} ⊕ … ⊕ A_{d}^{I^{d}} ⊂ Z_{1}^{I} ⊕ … ⊕ Z_{d}^{I^{d}},

the set X contains a monochromatic set of the form

(x_{1} ⊕ … ⊕ x_{d}) + A_{1} · e_{J} + A_{2} · e_{J}^{⊗2} + … + A_{d} · e_{J}^{⊗d}

for some non-empty J ⊂ I and some x_{j} ∈ Z_{j}^{I^{j}} for each 1 ≤ j ≤ d, such that x_{j} vanishes on J^{j} for each 1 ≤ j ≤ d.

Remark 6.7. This theorem is a “one-dimensional” theorem in the sense that it corresponds to the d = 1 case of Theorem 5.4 (i.e. to Theorem 5.7), although this terminology is dangerous since there are multiple concepts of dimension here. A “higher-dimensional” analogue of this theorem is certainly available, but we leave its formulation to the reader. This theorem implies the polynomial Gallai and van der Waerden theorems, as well as the Hales-Jewett theorem (see exercises) and thus can be viewed as a “grand unification” of all of these theorems.

This theorem was originally proven by topological means in [2], but a combinatorial proof was given in [22]. We will not prove it here, but only prove a special case which corresponds to Theorem 6.2:

Theorem 6.8. Let m ≥ 1, and let A = {0, 1} be a two-element subset of Z. Then there exists an integer n = n(m) ≥ 1 such that given any set I with n elements,and any m-coloring of A^{I^{2}}, the set A^{I^{2}} contains a monochromatic set of the form x_{2} + A · e_{J}^{⊗2} for some non-empty J ⊂ I and some x_{2} ∈ Z^{I^{2}} which vanishes on J^{2}.

Proof This proof will be very similar to that of Theorem 6.2, indeed one can use this theorem to imply Theorem 6.2 directly (Exercise (6)).

Once again we use the color focusing technique. For any x ∈ Z^{I^{2}} and any d ≥ 1, define a fan of degree d and origin x in Z^{I^{2}} to be a d + 1-tuple of elements in Z^{I^{2}} of the form F = (x, x + e_{J_{1}} ⊗ e_{J_{1}}, …, x + e_{J_{d}} ⊗ e_{J_{d}}) where J_{1}, …, J_{d} are nonempty subsets of I (not necessarily disjoint). If F is contained in {0, 1}^{I^{2}}, we define the colors c(F) ∈ C^{d+1} of this fan to be the d + 1-tuple c(F) := (c(x), c(x + e_{J_{1}} ⊗ e_{J_{1}}), …, c(x+e_{J_{d}} ⊗e_{J_{d}})). We say that this fan is weakly polychromatic if the colors c(x + e_{J_{1}} ⊗ e_{J_{1}}), …, c(x + e_{J_{d}} ⊗ e_{J_{d}}) are all distinct, and strongly polychromatic if in fact all the d + 1 colors in c(F) are distinct.

Once again, we need three obervations about polychromatic fans:

• (i) A weakly polychromatic fan is either strongly polychromatic, or contains a monochromatic set of the form {a, a + e_{J} ⊗ e_{J}} for some non-empty J.

• (ii) A strongly polychromatic fan cannot have degree m.

• (iii) Let I′ ⊂ I, and let F = (x, x + e_{J_{1}} ⊗ e_{J_{1}}, …, x + e_{J_{d}} ⊗ e_{J_{d}}) be a fan of degree d contained in {0, 1}^{(I′)^{2}}. Suppose there is a set

l ⊂ {0, 1}^{I^{2}\(I′)^{2}} ≡ {0, 1}^{I′×(I\I′)} ⊕ {0, 1}^{(I\I′)×I′} ⊕ {0, 1}^{(I\I′)×(I\I′)}

of the form

l = {(x_{0} + a ⊗ e_{J_{0}}) ⊕ (x_{0}^{∗} + e_{J_{0}} ⊗ a) ⊕ e_{I\I′} ⊗ e_{I\I′} : a ∈ {0, 1}^{I′}}

where J_{0} is a non-empty subset of I\I′, and x_{0} is an element of {0, 1}^{I′×(I\I′)} which vanishes on I′ × J_{0}, and x_{0}^{∗} ∈ {0, 1}^{I\I′×I′} is the transpose respectively. Suppose further that the fans F ⊕ b for b ∈ l (which we think of as subsets of {0, 1}^{I^{2}}) are strongly polychromatic with the same colors

c(F ⊕ b) = c for all b ∈ l. Then the fan

F̃ := (x_{1}, x_{1} + e_{J_{0}} ⊗ e_{J_{0}}, x_{1} + e_{J_{0}∪J_{1}} ⊗ e_{J_{0}∪J_{1}}, …, x + e_{J_{0}∪J_{d}} ⊗ e_{J_{0}∪J_{d}})

is a weakly polychromatic fan of degree d + 1 in {0, 1}^{I^{2}}, where

x_{1} := x ⊕ x_{0} ⊕ x_{0}^{∗} ⊕ (e_{I\I′} ⊗ e_{I\I′} − e_{J_{0}} ⊗ e_{J_{0}}).

The analogue of Lemma 3.4 is

Lemma 6.9. For any d ≥ 0 there exists a positive integer ñ(m, d) such that given any set I of cardinality ñ(m, d) and any m-colouring of {0, 1}^{I^{2}}, the set {0, 1}^{I^{2}} contains either a monochromatic set of the form {a, a+e_{J} ⊗e_{J}} for some non-empty J ⊂ I, or a strongly polychromatic fan of degree d.

Proof As before, we shall induct on the d variable. The base case d = 0 is trivial. Assume now that d > 1 and the claim has already been proven for d − 1. We define ñ = ñ(m, d) by the formula ñ := n_{1} + n_{2}, where n_{1} := ñ(m, d − 1) and n_{2} is an extremely large number (depending on n_{1}, m, d) to be chosen later (using the ordinary Hales-Jewett theorem). We partition I = I_{2} ∪ I_{1} where I_{1} has n_{1} elements and I_{2} has n_{2} elements; this induces a decomposition

{0, 1}^{I^{2}} ≡ {0, 1}^{I_{1}^{2}} ⊗ {0, 1}^{I_{1}×I_{2}} ⊕ {0, 1}^{I_{2}×I_{1}} ⊕ {0, 1}^{I_{2}^{2}}.

For each b ∈ {0, 1}^{I_{1}×I_{2}}, the set

{0, 1}^{I_{1}^{2}} ⊕ b ⊕ b^{∗} ⊕ e_{I_{2}} ⊗ e_{I_{2}}

is isomorphic to {0, 1}^{I_{1}^{2}}, and so by the inner induction hypothesis we see that each such set either contains a monochromatic combinatorial line, or a strongly polychromatic fan F (b) ⊕ b ⊕ b^{∗} ⊕ e_{I_{2}} ⊗ e_{I_{2}} of degree d − 1 and colors c(F (b) ⊕ b ⊕ b^{∗}⊕e_{I_{2}} ⊗e_{I_{2}}). If there is at least one b ∈ {0, 1}^{I_{1}×I_{2}} for which the former case applies then we are done, so suppose that the latter case applies for every b ∈ {0, 1}^{I_{1}×I_{2}}. The number of possible fans F (b) is at most 2^{dn_{1}}, and the number of possible colors c(b) is at most m^{d}, hence the map b ↦ (F (b), c(F (b)⊕b⊕b^{∗}⊕e_{I_{2}} ⊗e_{I_{2}})) is a m^{d}2^{dn_{1}}- coloring of {0, 1}^{I_{1}×I_{2}}. We view {0, 1}^{I_{1}×I_{2}} as A^{I_{2}}, where I := {0, 1}^{I_{1}}. Applying the ordinary one-dimensional Hales-Jewett theorem (Theorem 5.7), we can thus find a combinatorial line l ⊂ A^{I_{2}} over A with active co-ordinates J_{0} ⊂ I_{2}, which is monochromatic with respect to this coloring, hence there is a fan F of degree d − 1 in {0, 1}^{I_{2}} and colors c ∈ C^{d} such that for every b ∈ l the fans F ⊕ b ⊕ b^{∗} ⊕ e_{I_{2}} ⊗ e_{I_{2}} are strongly polychromatic with colors c. By observation (iii) this implies that A^{I} contains a weakly polychromatic fan of order d, and then by observation (i) the lemma follows.

As in all the other color focusing proofs we now conclude Theorem 6.8 by setting d := m and appealing to observation (ii).

• Show that the substance of the polynomial Hales-Jewett theorem is unchanged if we apply an arbitrary bijection A_{j} → A′_{j} from the sets A_{j} ∈ Z_{j} to any other sets A′_{j} ∈ Z′_{j} in another abelian group Z′_{j} for each 1 ≤ j ≤ d; thus the additive structure of the Z_{j} is irrelevant for this theorem.

• Show that the polynomial van der Waerden theorem implies a slight strengthening of that theorem in which r is necessarily positive.

• Show that Theorem 6.8 implies Theorem 6.2.

• Show that the polynomial Hales-Jewett theorem implies the ordinary Hales-Jewett theorem, the polynomial van der Waerden theorem, and the polynomial Gallai theorem.

• For each integer k ≥ 1, let P_{k} be the binomial coefficient polynomials

P_{k}(n) := \frac{n(n − 1) … (n − k + 1)}{k!}.

Show that each of the P_{k} maps the integers to the integers, and vanish at the origin. Conversely, show that if P is any polynomial which maps the integers to the integers and vanishes at the origin, then P can be written uniquely as a finite linear combination of the P_{k} for k ≥ 1. (Hint: induct on the degree of P, and consider the partial difference polynomial P (n + 1) − P (n)).

• [22] Given any collection P = (P_{j})_{j∈J} of polynomials of one variable of degree at most D indexed by a finite set J which all vanish at the origin, define an equivalence relation P_{i} ∼ P_{j} if P_{i} and P_{j} have the same degree and P_{i} − P_{j} has lower degree, and define the weight vector N(P) = (N_{1}, …, N_{D}) ∈ Z^{D} by defining N_{d} to be the number of equivalence classes in P corresponding to polynomials of degree d (thus for instance the zero polynomial has no impact on this weight vector). We well-order these weight vectors lexicographically, declaring (N_{1}, …, N_{D}) < (M_{1}, …, M_{D}) if there is some 1 ≤ d_{0} ≤ D such that M_{d_{0}} > N_{d_{0}} and M_{d} = N_{d} for all d_{0} < d ≤ D. For any integer h and j ∈ J, let Q_{j,h} denote the polynomial Q_{j,h}(n) := P_{j}(n + h) − P_{j}(h) − P_{i}(n). Show that for any finite set H of integers, the collection (Q_{j,h})_{j∈J,h∈H} has a weight vector less than that of P. Using this fact, modify the proof of Theorem 6.2 (setting up an outer induction loop, inducting on the weight vector; this is known as polynomial ergodic theorem induction, or PET induction for short) to prove the polynomial van der Waerden theorem.

References

[1] V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden’s and Szemerédi’s theorems, J. Amer. Math. Soc. 9 (1996), 725–753.

[2] V. Bergelson and A. Leibman, Set polynomials and polynomial extension of the Hales Jewett theorem, ???

[3] E.P. Berlekamp, A construction for partitions which avoid long arithmetic progressions, Canad. Math. Bull. 11 (1968), 409–414.

[4] P. Erdös, Some remarks on the theory of graphs, Bull. Am. Math. Soc. 53 (1947), 292–294.

[5] J. Folkman, On the representation of integers as sums of distinct terms from a fixed sequence, Canadian J. Math. 18 (1966), 643–655.

[6] T. Gowers, A new proof of Szemeredi’s theorem, GAFA 11 (2001), 465-588.

[7] T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, preprint.

[8] R. Graham, V. Rödl, A. Rucinski, On Schur properties of random subsets of integers, J. Numb. Theory 61 (1996), 388–408.

[9] R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1980).

[10] A.W. Hales, R.I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.

[11] N. Hindman, Finite sums from sequences within cells of a partition of N, J. Combin. Theory Ser. A. 17 (1974), 1–11.

[12] N. Hindman, I. Leader, D. Strauss, Open problems in partition regularity, Combinatorics, Probability and Computing 12 (2003), 571–583.

[13] B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, preprint.

[14] R. Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), 424–480.

[15] F.P.Ramsey. On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264–285.

[16] A. Robertson, D. Zeilberger, A 2-coloring of [1, N] can have (1/22)N^{2}+O(N) monochromatic Schur triples, but not less!, Electron. J. Combin. 5(1) (1998), R19.

[17] I. Schur, Uber die Kongruenz x^{m} +y^{m} = z^{m}(modp), Jber. Deutsch. Math.-Verein. 25 (1916), 114–116.

[18] T. Schoen, The number of monochromatic Schur triples, European J. Combin. 20 (1999), 855–866.

[19] S. Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683–697.

[20] B.L. Van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. 15 (1927), 212–216.

[21] P. Varnavides, On certain sets of positive density, J. London Math. Soc. 39 (1959), 358–360.

[22] M. Walters, Combinatorial proofs of the polynomial van der Waerden theorem and the polynomial Hales-Jewett theorem, J. Lond. Math. Soc. 61 (2000), 1–12.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu