SZEMERÉDI’S PROOF OF SZEMERÉDI’S THEOREM

TERENCE TAO

Abstract. We present Szemerédi’s original proof of Szemerédi’s theorem.

1. Introduction

The purpose of this note is to present Szemerédi’s original proof of Szemerédi’s theorem:

Theorem 1.1 (Szemeredi’s theorem). [3] Let A be a subset of Z with positive upper density

lim sup_{N→∞} \frac{|A ∩ [−N, N]|}{|[−N, N]|} = δ > 0

and fix k ≥ 3. Then A contains at least one proper arithmetic progression a, a + r, …, a + (k − 1)r of length k and r > 0.

We have restricted to the case k ≥ 3 since the cases k < 3 are trivial. Once one obtains one progression, it is an easy matter to in fact obtain infinitely many progressions (e.g. by deleting the progression that we locate from A - which does not affect the upper density - and then starting over).

It is well known that Szemerédi’s proof relies in such ingredients as Szemerédi’s regularity lemma, which essentially allows one to approximate an arbitrary large graph by an object of bounded complexity, as well as van der Waerden’s theorem, which allows one to locate a monochromatic arithmetic progression of length k in any coloring of a sufficiently large arithmetic progression. The proof also relies on another fact, which is that most pairs of integers can be connected by a progression of length k (specifically, given 1 ≤ j < j′ ≤ r and n, m ∈ Z, there often exists a progression a, a + r, …, a + (k − 1)r with a + jr = n and a + j′r = m). This particular property (needed for the regularity lemma to be useful) is not true for generalizations of Szemeredi’s theorem, such as multidimensional, Hales-Jewett, or polynomial analogues, and so it is not clear at this point whether Szemerédi’s argument could extend to cover these cases (unless perhaps one replaces the regularity lemma with a hypergraph analogue).

Let us close this introduction with a simple lemma, which basically asserts that Szemerédi’s theorem is easy if the density is sufficiently large.

Lemma 1.2. Let k ≥ 3, and let P = {b, b + s, …, b + (l − 1)s} be a progression of some length l ≥ 10k. Let A be a subset of P such that |A| ≥ (1 − \frac{1}{10k})|P |. Then A contains at least one proper arithmetic progression a, a + r, …, a + (k − 1)r of length k with r > 0.

Proof This is an easy counting argument. The number of progressions of the form a, a + r, …, a + (k − 1)r in P with r > 0 is basically \frac{1}{2k} |P |^{2}, whereas for each 0 ≤ i < k and b ∈ P the number of such progressions with a + ir = b is at most \frac{1}{k} |P |. Thus for each i, the number of progression with a + ir ∉ A is at most \frac{1}{10k^{2}} |P |^{2}, so summing over all i we see that there must be at least one progression with a + ir ∈ A for all 0 ≤ i < k.

2. Progressions

We recall the concept of a generalized arithmetic progression, or progression for short.

Definition 2.1. If N^{(d)} = (N_{1}, …, N_{d}) is a d-tuple of positive integers for some d > 0, we form the discrete box

[0, N^{(d)}) := [0, N_{1})×…×[0, N_{d}) = {(n_{1}, …, n_{d}) ∈ Z^{d} : 0 ≤ n_{i} < N_{i} for all 1 ≤ i ≤ d}.

A progression P of rank d and dimensions N^{(d)} = (N_{1}, …, N_{d}) is any subset of Z of the form

P = a+[0, N^{(d)})·v = {a+n·v : n ∈ [0, N^{(d)})} = {a+∑_{i=1}^{d} n_{i}v_{i} : 0 ≤ n_{i} < N_{i} for all 1 ≤ i ≤ d},

where v = (v_{1}, …, v_{d}) ∈ Z^{d} is a vector. If the map n ↦ n · v is one-to-one on [0, N^{(d)}) we say that P is proper (this is equivalent to the statement that |P | = N_{1} … N_{d}. For 0 ≤ n_{d} < N_{d}, we define the n_{d}^{th} component P_{n_{d}} of P to be

P_{n_{d}} = {a + ∑_{i=1}^{d} n_{i}v_{i} : 0 ≤ n_{i} < N_{i} for all 1 ≤ i ≤ d − 1},

thus each P_{n_{d}} is a progression of rank d − 1 and dimensions (N_{1}, …, N_{d−1}). We can iterate this definition, defining P_{n_{d},n_{d−1}}, etc.

For Szemerédi’s argument we need a couple more notions associated to that of a progression. We first recursively define what it means for a progression to be increasing.

Definition 2.2. A progression of rank 0 is always increasing. If d > 0, a progression P of rank d is said to be increasing if each component P_{n_{d}} is increasing, and if whenever 0 ≤ n_{d} < n′_{d} < N_{d}, every element of P_{n′_{d}} is larger than every element of P_{n_{d}}.

Note that increasing progressions are automatically proper. In our analysis we shall deal almost exclusively with increasing progressions.

Now we define the notion of a color of a increasing progression (with respect to a fixed set A).

Definition 2.3. Let 2^{[0,N^{(d)})} be the power set of [0, N^{(d)}), i.e. the set of all subsets of [0, N^{(d)}). The color c(P) ∈ 2^{[0,N^{(d)})} of an increasing progression P = a+[0, N^{(d)})· v is defined to be the set

c(P) := {n ∈ [0, N^{(d)}) : a + n · v ∈ A}.

We say that P is black if c(P) is the empty set.

Note that the color c(P) of a progression determines the colors c(P_{0}), …, c(P_{N_{d}−1}) of its components, and conversely. Generally speaking, we wish to avoid the black color whenever we can, and work instead with “saturated” colors which are as “bright as possible” (roughly speaking, they contain as many points as possible; the precise definition is more recursive than this).

To prove Szemerédi’s theorem (Theorem 1.1), our strategy shall be to first work in a progression of large rank and even larger dimensions which contains lots of “saturated” colors, and then trade in this rank and saturation for an increasingly “perfect” progression, ultimately ending up with a progression of length k which is contained entirely in A. We begin by describing a certain recursive procedure that will set up for us such a large rank progression.

3. Asymptotic upper color density

Let us fix some dimensions N^{(d)} = (N_{1}, …, N_{d}). The increasing progressions of dimensions [0, N^{(d)}) can take any color within 2^{[0,N^{(d)})}; let us suppose that we have some subset Σ_{N^{(d)}} ⊂ 2^{[0,N^{(d)})} of these colors, which we refer to as the saturated colors (roughly speaking, they are the “brightest” colors which can occur in progressions of dimensions [0, N^{(d)}), and will be quite far away from being black). For this discussion the exact definition of saturation is not relevant. Given any increasing progression P of dimensions (N_{1}, …, N_{d+1}) for some N_{d+1}, define the saturation 0 ≤ σ_{N^{(d)}}(P) ≤ 1 of P to be the quantity

σ_{N^{(d)}}(P) := \frac{1}{N_{d+1}} |\{0 ≤ j < N_{d+1} : c(P_{j}) ∈ Σ_{N^{(d)}}\}|,

i.e. σ_{N^{(d)}}(P) is the proportion of components of P whose color is saturated. Note that this quantity depends only on the color c(P) of P and not on P itself. We then define the upper saturation numbers

\overline{σ_{N^{(d)}}}(N_{d+1}) := sup_{P} σ_{N^{(d)}}(P),

where P ranges over all increasing progressions of dimensions (N_{1}, …, N_{d+1}), and the asymptotic upper saturation

\overline{σ_{N^{(d)}}}(∞) := lim sup_{N_{d+1}} \overline{σ_{N^{(d)}}}(N_{d+1}).

This limit superior is in fact a limit:

Lemma 3.1. If we define the quantity

μ_{d}(M) := |\overline{σ_{N^{(d)}}}(M) − \overline{σ_{N^{(d)}}}(∞)|,

then

lim_{M→∞} μ_{d}(M) = 0.  (1)

Proof Let ε > 0 be arbitrary. It will suffice to show that

\overline{σ_{N^{(d)}}}(M) ≥ \overline{σ_{N^{(d)}}}(∞) − O(ε)

for M sufficiently large depending on ε. But we can find M′ ≫ M arbitrarily large such that

\overline{σ_{N^{(d)}}}(M′) = \overline{σ_{N^{(d)}}}(∞) − O(ε),

and thus we can find an increasing progression P of dimensions (N_{1}, …, N_{d}, M′) such that

σ_{N^{(d)}}(P) = \overline{σ_{N^{(d)}}}(∞) − O(ε).

By truncating P by a little bit we may assume M′ is a multiple of M (the error term in doing so is negligible if M′ is large enough depending on M). But then by subdividing P into M′/M blocks of dimension (N_{1}, …, N_{d}, M) and using the pigeonhole principle, we can find a progression P′ of dimension (N_{1}, …, N_{d}, M) such that

σ_{N^{(d)}}(P′) = \overline{σ_{N^{(d)}}}(∞) − O(ε).

and the claim follows.

Let us dispose of an easy case when μ_{d} actually does reach zero:

Lemma 3.2. If \overline{σ_{N^{(d)}}}(∞) ≥ 1/2 and μ_{d}(M) < c(k, N_{1}, …, N_{d}, M) for some sufficiently small c(k, N_{1}, …, N_{d}, M) > 0 and black is not a saturated color, then we can find a progression of length k in A.

Proof Suppose that μ_{d}(M) < c = c(k, N_{1}, …, N_{d}, M). By (1), we can find an arbitrarily large M′ such that μ_{d}(MM′) < μ_{d}(M). In particular we can find a increasing progression P of rank d + 1 and dimensions (N_{1}, …, N_{d}, MM′) with

σ_{N^{(d)}}(P) ≥ \overline{σ_{N^{(d)}}}(∞) − μ_{d}(M).

We now view P instead as a progression Q of rank d+2 and dimensions (N_{1}, …, N_{d}, M, M′), and observe that

\frac{1}{M′} ∑_{n=0}^{M′−1} σ_{N^{(d)}}(Q_{n}) = σ_{N^{(d)}}(P) ≥ \overline{σ_{N^{(d)}}}(∞) − μ_{d}(M)

and thus

\frac{1}{M′} ∑_{n=0}^{M′−1}(σ_{N^{(d)}}(Q_{n}) − \overline{σ_{N^{(d)}}}(∞)) > −μ_{d}(M)

On the other hand, we have

σ_{N^{(d)}}(Q_{n}) ≤ \overline{σ_{N^{(d)}}}(M) ≤ \overline{σ_{N^{(d)}}}(∞) + μ_{d}(M)

and hence

\frac{1}{M′} ∑_{n=0}^{M′−1}(σ_{N^{(d)}}(Q_{n}) − \overline{σ_{N^{(d)}}}(∞))_{+} ≤ μ_{d}(M)

and hence

\frac{1}{M′} ∑_{n=0}^{M′−1} |σ_{N^{(d)}}(Q_{n}) − \overline{σ_{N^{(d)}}}(∞)| ≤ 3μ_{d}(M).

By Chebyshev, we see in particular that

|\{0 ≤ n ≤ M′ − 1 : |σ_{N^{(d)}}(Q_{n}) − \overline{σ_{N^{(d)}}}(∞)| ≥ \sqrt{μ_{d}(M)}\}| ≤ 3\sqrt{μ_{d}(M)}M′.

By the pigeonhole principle, we can thus find an interval [M′′, M′′ + 1/10\sqrt{μ_{d}(M)}] in [0, M′) such that

|σ_{N^{(d)}}(Q_{n}) − \overline{σ_{N^{(d)}}}(∞)| < \sqrt{μ_{d}(M)} for all n ∈ [M′′, M′′ + 1/10\sqrt{μ_{d}(M)}].

Since \overline{σ_{N^{(d)}}}(∞) ≥ 1/2 and μ_{d}(M) is small, we see in particular that Q_{n} contains at least one saturated component and in particular is not black.

The number of possible colors of Q_{n} is at most 2^{N_{1}...N_{d}M}. Thus, if c is sufficiently small (and hence 1/10\sqrt{μ_{d}(M)} sufficiently large) depending on k and 2^{N_{1}...N_{d}M}, we see from van der Waerden’s theorem that we can find an increasing progression n, …, n + (k − 1)r inside [M′′, M′′ + 1/10\sqrt{μ_{d}(M)}] such that all the progressions Q_{n}, …, Q_{n+(k−1)r} have the same color, which is not black by the preceding discussion. In particular inside Q_{n} ∪ … ∪ Q_{n+(k−1)r} we can find an increasing arithmetic progression of length k, and we are done. k as desired.

We will assume that the asymptotic upper saturation is quite large, say

\overline{σ_{N^{(d)}}}(∞) ≥ 1 − ε_{d} ≥ 1 − 1/100k  (2)

for some small 0 ≤ ε_{d} < 1/100k. This means that we can find arbitrarily large rank d + 1 increasing progressions which are almost entirely saturated (up to an exceptional set of density at most ε_{d}). In particular we see that Σ_{N^{(d)}} is non-empty.

Given any saturated color c ∈ Σ_{N^{(d)}}, we may define the color density

δ_{c}(P) := \frac{1}{N_{d+1}} |\{0 ≤ j < N_{d+1} : c(P_{j}) = c\}|

of any increasing progression P of dimensions (N_{1}, …, N_{d+1}) (again note that this depends only on the color c(P) of P, and not on P itself), as well as the upper color density numbers

\overline{δ_{c}}(N_{d+1}) := sup_{P:|σ_{N^{(d)}} (P)−\overline{σ_{N^{(d)}}} (∞)|≤\sqrt{μ_{d}(N_{d+1})}} δ_{c}(P).  (3)

Note that we have restricted the supremum to progressions P which are quite saturated; this set is nonempty by definition of σ_{N^{(d)}}(N_{d+1}) and μ_{d}(N_{d+1}). We now define the asymptotic upper color density

\overline{δ_{c}}(∞) := lim sup_{N_{d+1}→∞} \overline{δ_{c}}(N_{d+1}).  (4)

Since

\overline{σ_{N^{(d)}}}(∞) ≤ ∑_{c∈Σ_{N^{(d)}}} \overline{δ_{c}}(∞)

we see from the pigeonhole principle and (2) that there exists a color c_{d} ∈ Σ_{N^{(d)}} (depending of course on N^{(d)} and Σ_{N^{(d)}}) such that

\overline{δ_{c_{d}}}(∞) ≥ \frac{1 − ε_{d}}{|Σ_{N^{(d)}}|} ≥ \frac{1}{2|2^{[0,N^{(d)})}|}.  (5)

Let us fix this color c_{d}, and refer to it as a perfect color (the notation is essentially from [3]); one can think of this color as the most “popular” of the saturated colors. In practice, we will be able to ensure that this color is not black (either by choosing it specifically (in the d = 0 case), or by assuming inductively that all the saturated colors are non-black). The condition (5) ensures that the perfect color is attained quite often; while the denominator |2^{[0,N^{(d)})}| on the right-hand side of (5) looks quite large, we shall eventually choose N_{d+1} (and related quantities) much larger than this, to the extent that this denominator ends up being negligible.

Let us now pick a small 0 < ε_{d+1} < 1/100k (which will in practice be much smaller than ε_{d} or \overline{δ_{c_{d}}}(∞)). By (1), (4), we can find arbitrarily large N_{d+1} such that

|\overline{δ_{c_{d}}}(N_{d+1}) − \overline{δ_{c_{d}}}(∞)| ≤ ε_{d+1}^{8}  (6)

and

μ_{d}(N_{d+1}) ≤ ε_{d+1}^{8}.  (7)

Suppose we choose such a N_{d+1}. We then form the dimensions N^{(d+1)} := (N_{1}, …, N_{d}, N_{d+1}). If P is an increasing progression of dimensions N^{(d+1)}, we say that c(P) is saturated if

|σ_{N^{(d)}}(P) − \overline{σ_{N^{(d)}}}(∞)| ≤ \sqrt{μ_{d}(N_{d+1})}  (8)

and

|δ_{c_{d}}(P) − \overline{δ_{c_{d}}}(∞)| ≤ ε_{d+1}.  (9)

Note that this definition is well-defined as the quantities σ_{N^{(d)}}(P) and δ_{c_{d}}(P) depend only on the color c(P) of P and not of P itself. Informally, a progression of rank d + 1 is saturated if almost all of its components are saturated, and as many of its components as possible have the perfect color. We can thus define a set Σ_{N^{(d+1)}} ⊆ 2^{[0,N^{(d+1)})} of saturated colors, which in turn induces an asymptotic upper saturation \overline{σ_{N^{(d+1)}}} as before. We observe also that (8), (2), (7) implies that

σ_{N^{(d)}}(P) ≥ 1 − 2ε_{d+1}  (10)

(for instance).

Lemma 3.3. We have

\overline{σ_{N^{(d+1)}}}(∞) ≥ 1 − ε_{d+1}.

(In other words, (2) holds for rank d + 1).

Proof Let κ > 0 and M > 0 be arbitrary. It will suffice to show that there exists an N_{d+2} ≥ M and a increasing progression P of rank d + 2 and dimensions (N_{1}, …, N_{d+2}) such that

σ_{N^{(d+1)}}(P) ≥ 1 − ε_{d+1}.  (11)

By (1), (4), we can find M′ ≥ N_{d+1} max(M, \frac{1}{μ_{d}(N_{d+1})^{2}} ) so large that

\overline{σ_{N^{(d)}}}(M′) = \overline{σ_{N^{(d)}}}(∞) + O(μ_{d}(N_{d+1})^{2})  (12)

and then an increasing progression Q of rank d+1 and dimensions (N_{1}, …, N_{d}, M′) such that

δ_{c_{d}}(Q) = \overline{δ_{c_{d}}}(∞) + O(μ_{d}(N_{d+1}))  (13)

and

σ_{N^{(d)}}(Q) = \overline{σ_{N^{(d)}}}(∞) + O(μ_{d}(N_{d+1})).

By shrinking Q a little bit we may assume that M′ is a multiple of N_{d+1} (the error incurred by this is at most O(N_{d+1}/M′) = O(μ_{d}(N_{d+1})ε_{d+1})), say M′ = N_{d+1}N_{d+2}. We can then view Q not as an increasing progression of rank d + 1 and dimensions (N_{1}, …, N_{d}, M′), but rather as an increasing progression (which we shall call P to distinguish it from Q, even though as sets of integers they are identical) of rank d + 2 and dimensions (N_{1}, …, N_{d}, N_{d+1}, N_{d+2}). Since

σ_{N^{(d)}}(Q) = \frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2})} σ_{N^{(d)}}(P_{n_{d+2}})

we thus have

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2})}(σ_{N^{(d)}}(P_{n_{d+2}}) − \overline{σ_{N^{(d)}}}(∞)) = O(μ_{d}(N_{d+1})).

But from definition of μ_{d}(N_{d+1}) we have

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2})}(σ_{N^{(d)}}(P_{n_{d+2}}) − \overline{σ_{N^{(d)}}}(∞))_{+} ≤ μ_{d}(N_{d+1})

and hence

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2})} |σ_{N^{(d)}}(P_{n_{d+2}}) − \overline{σ_{N^{(d)}}}(∞)| = O(μ_{d}(N_{d+1})).

By Chebyshev’s inequality and (7) we thus have

|\{n_{d+2} ∈ [0, N_{d+2}) : |σ_{N^{(d)}}(P_{n_{d+2}}) − σ_{N^{(d)}}(∞)| ≥ \sqrt{μ_{d}(N_{d+1})}\}| ≤ O(ε_{d+1}^{4})N_{d+2}. (14)

Now we argue using δ_{c_{d}} instead of σ_{N^{(d)}}. From (13), (7) we have

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2})}(δ_{c_{d}}(P_{n_{d+2}}) − δ_{c_{d}}(∞)) = O(ε_{d+1}^{8}),

so by (14)

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2}):|σ_{N^{(d)}} (P_{n_{d+2}} )−σ_{N^{(d)}} (∞)|<\sqrt{μ_{d}(N_{d+1})}}(δ_{c_{d}}(P_{n_{d+2}})−δ_{c_{d}}(∞)) = O(ε_{d+1}^{4}).

But by (6) we have

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2}):|σ_{N^{(d)}} (P_{n_{d+2}} )−σ_{N^{(d)}} (∞)|<\sqrt{μ_{d}(N_{d+1})}}(δ_{c_{d}}(P_{n_{d+2}})−δ_{c_{d}}(∞))_{+} = O(ε_{d+1}^{8})

and so

\frac{1}{N_{d+2}} ∑_{n_{d+2}∈[0,N_{d+2}):|σ_{N^{(d)}} (P_{n_{d+2}} )−σ_{N^{(d)}} (∞)|<\sqrt{μ_{d}(N_{d+1})}} |δ_{c_{d}}(P_{n_{d+2}})−δ_{c_{d}}(∞)| = O(ε_{d+1}^{4})

and so by Chebyshev

|\{n_{d+2} ∈ [0, N_{d+2}) : |σ_{N^{(d)}}(P_{n_{d+2}})−σ_{N^{(d)}}(∞)| < \sqrt{μ_{d}(N_{d+1})}; |δ_{c_{d}}(P_{n_{d+2}})−δ_{c_{d}}(∞)| ≥ ε_{d+1}\}| = O(ε_{d+1}^{3})N_{d+2}.

Combining this with (14) and the definition of saturation we see that

|{n_{d+2} ∈ [0, N_{d+2}) : P_{n_{d+2}} is not saturated}| = O(ε_{d+1}^{3})N_{d+2}

and hence (11) follows.

This lemma will allow us to iteratively construct a sequence N_{1} ≪ N_{2} ≪ … of integers, with the associated dimensions N^{(d)} := (N_{1}, …, N_{d}), a set Σ_{N^{(d)}} ⊂ 2^{[0,N^{(d)})} of saturated colors, and a collection of perfect colors c_{d} ∈ Σ_{N^{(d)}} for each d; we shall formalize this construction in the next section.

4. Setting up the dimensions

We shall need a growth function F_{0} : R^{+} → R^{+}, depending on k and δ to be chosen later. One should think of this function as a rapidly increasing function, such as F_{0}(n) := 2^{2^{2^{kn/δ}}}, though in practice we shall need a much faster function than this (it has to grow faster than the bounds one obtains from both the Szemeredi regularity lemma and the van der Waerden theorem). It will be important that our bounds will not depend on this extremely rapidly growing function. We will however make the (very mild) assumption that F_{0}(n) grows faster than n, e.g. F_{0}(n) ≥ 2^{n}.

As mentioned in the previous section, we wish to construct a sequence N_{1} ≪ N_{2} ≪ … of integers as well as appropriate notions of saturated color and perfect color for each d ≥ 0 (actually, at the end of the day we will only need this for d ≤ 2^{k}). We will also obtain error estimates of the form (2) for some 0 < ε_{d} < 1/100k, as well as lower bounds on the asymptotic perfect color density.

4.1. The d = 0 constructions. We begin with the d = 0 case. Here N^{(0)} = () is the empty tuple, and progressions of rank 0 are just singleton sets of integers. Such singletons are either black (if they are not contained in A) or white (if they are contained in A), giving two colors. We declare both of them to be saturated (thus Σ_{N^{(0)}} := 2^{[0,N^{(0)})} = {black, white}) and we declare c_{0} := white to be the perfect color.

Since every color is saturated, we have \overline{σ_{N^{(0)}}}(∞) = 1 and so if we set ε_{0} := 0 then (2) is satisfied.

δ_{N^{(0)},c_{0}}([−N, N]) = \frac{|A ∩ [−N, N]|}{|[−N, N]|}

and A has upper density at least δ, we see that

δ_{c_{0}} ≥ δ.  (15)

4.2. The general case. Now we assume inductively that the quantities N^{(d)}, ε_{d}, Σ_{N^{(d)}}, c_{d} have already been constructed for some d ≥ 0, and turn now to the construction for d + 1.

Using (1), (4), we can find a length

L_{d+1} ≥ F_{0}(N_{1} … N_{d})  (16)

such that

|\overline{δ_{c_{d}}}(L_{d+1}) − \overline{δ_{c_{d}}}(∞)| ≤ 1/F_{0}(N_{1} … N_{d})  (17)

and

|μ_{d}(L_{d+1})| ≤ 1/F_{0}(N_{1} … N_{d})^{2}.  (18)

We then define a small number 0 < ε_{d+1} ≪ 1 defined as

ε_{d+1} := (100kF_{0}(L_{d+1}))^{−100k}  (19)

(so in particular ε_{d+1} < 1/100k), and then using (4) again we can find a length

N_{d+1} ≥ F_{0}(1/ε_{d+1})  (20)

such that (6), (7) hold. We then use this length N_{d+1} to construct the dimensions N^{(d+1)} := (N_{1}, …, N_{d+1}), and then define the saturated color set Σ_{N^{(d+1)}} and the perfect color c_{d+1} as in the previous section. We can then iterate this construction indefinitely to create N^{(d)}, ε_{d}, Σ_{N^{(d)}}, c_{d} for all d.

Note that the quantities L_{d+1}, 1/ε_{d+1}, N_{d+1} are widely separated in magnitude, indeed we have

… ≪ N_{d} ≪ L_{d+1} ≪ 1/ε_{d+1} ≪ N_{d+1} ≪ L_{d+2} ≪ …

where A ≪ B denotes the statement that B ≥ F_{0}(A). The fact that F_{0} is extremely rapidly growing will mean that any reasonable quantity involving variables to the left of this hierarchy will be dominated by any reasonable quantity involving variables to the right of this hierarchy. The parameter L_{d+1} is an intermediate dimension which is huge compared to N_{d} but miniscule compared to N_{d+1}; the point is that when we are working in a progression of dimensions N^{(d+1)} we shall be easily able to introduce a free parameter ranging over an interval of length L_{d+1} (or even F_{0}(L_{d+1}), which would be pretty useless if we stayed in rank d + 1, but if we then drop rank to d, this additional parameter becomes extremely useful - roughly speaking, it (combined with the Szemerédi regularity lemma and the van der Waerden theorem, and the fact that L_{d+1} has upper perfect color density close to the asymptotic limit) can be used to upgrade the existence of progressions of length i to progressions of length i + 1 (although this “uses” up our parameter and we have to go create it again). Thus we shall be able to “spend” the large rank in our progressions, one rank at a time, to eventually obtain progressions of length k. This strategy may appear extremely convoluted, but it in fact appears to be the minimally complex strategy that would combine all these ingredients to yield a successful proof (and avoid all the difficulties associated with the bounds for the regularity lemma and van der Waerden theorem being incredibly poor).

We now observe that none of the perfect colors c_{d} are black. For d = 0 this is clear from construction. For d = 1, we see from (19) that

ε_{1} < δ/2

if F_{0} is chosen to sufficiently large depending on δ, and so from (9) we see that δ_{c_{0}}(P) > 0 whenever P is a rank 1 saturated increasing progression. This implies that all the saturated colors in Σ_{N^{(1)}} are non-black, and in particular the perfect color c_{1} is not black.

Now suppose inductively that c_{d} is known to be non-black for some d ≥ 1. From (19) we certainly have

ε_{d+1} < \frac{1}{4|2^{[0,N^{(d)})}|}

if F_{0} is chosen sufficiently large, and so by (5), (9) we see that δ_{c_{d}}(P) > 0 whenever P is a rank d + 1 saturated increasing progression, thus as before we see that all the saturated colors in Σ_{N^{(d+1)}} are non-black, and in particular the perfect color c_{d+1} is also non-black.

Since none of the saturated colors in Σ_{N^{(d)}} are black for d ≥ 1, we see from Lemma 3.2 that we may assume

μ_{d}(L_{d+1}) > c(k, N_{1}, …, N_{d}, L_{d+1}).  (21)

Note from the above construction that we have in fact shown

ε_{d+1} < \frac{1}{2}δ_{c_{d}}(∞)

and hence

\frac{1}{2}δ_{c_{d}}(∞) ≤ δ_{c_{d}}(P) ≤ 2δ_{c_{d}}(∞)  (22)

whenever P is a rank d + 1 saturated increasing progression.

If d ≥ 0, 0 ≤ i ≤ k, and P is an increasing progression of dimensions (N_{1}, …, N_{d}, k+ 1), we say that P is perfect of order i if the first i components P_{0}, …, P_{i−1} all have the perfect color c_{d}. Clearly all increasing progressions of dimension (N_{1}, …, N_{d}, k + 1) are perfect of order 0; in order to prove Theorem 1.1 we will seek to find progressions which are perfect of order k and have dimension k + 1 (actually we can eventually obtain progressions which are perfect of order k and have dimension (N_{1}, …, N_{d}, k + 1) for any k).

We mentioned earlier that our basic strategy is to start with a large rank progression, and spend those ranks in order to improve the order i of perfection. We now turn to setting up the notation required to execute this strategy.

5. Homogeneous progressions, and well-arranged sequences of progressions

Let d ≥ 1, and let P be a rank d+1 increasing progression of dimensions (N_{1}, …, N_{d}, k+ 1). Thus P consists of k + 1 components P_{0}, …, P_{k} which are rank d increasing progressions of dimensions (N_{1}, …, N_{d}), and each component P_{j} in turn consists of N_{d} components P_{j,0}, …, P_{j,N_{d}−1} which are rank d − 1 increasing progressions of dimensions (N_{1}, …, N_{d−1}).

Let us say that P is completely saturated if each of its k + 1 components P_{0}, …, P_{k} are saturated. By (10) this means that

\frac{1}{N_{d}} |\{0 ≤ n_{d} < N_{d} : P_{j,n_{d}} is saturated\}| ≥ 1 − 2ε_{d−1} for all 0 ≤ j ≤ k

and from (22) we similarly have

\frac{1}{N_{d}} |\{0 ≤ n_{d} < N_{d} : P_{j,n_{d}} has the perfect color c_{d−1}\}| = δ_{c_{d−1}}(∞) + O(ε_{d}) for all 0 ≤ j ≤ k.

(23)

If m_{d}, m_{d}+r, …, m_{d}+(k−1)r is a progression of integers in [0, N_{d}) (not necessarily increasing or proper), we can define the associated subprogression P_{(m_{d},r)} ⊂ P of P to be the set

P_{(m_{d},r)} = P_{0,m_{d}} ∪ P_{1,m_{d}+r} ∪ … ∪ P_{k−1,m_{d}+kr};

observe that this is a rank d increasing progression of dimensions (N_{1}, …, N_{d−1}, k+ 1).

We shall need the counting functions

f_{P,i,j}(n_{d}) := |{P_{(m_{d},r)} ⊂ P : P_{(m_{d},r)} is perfect of order i and m_{d} + jr = n_{d}}|

defined for all 0 ≤ i ≤ j ≤ k and n_{d} ∈ [0, N_{d}); thus f_{P,i,j}(n_{d}) counts the number of subprogressions P_{(m_{d},r)} which are perfect of order i and contain the specific component P_{j,n_{d}}. Thus, for instance, the existence of a subprogression which is perfect of order i is equivalent to f_{P,i,j}(n_{d}) being non-zero for some j and some n_{d}. This quantity is clearly decreasing in i, f_{P,i+1,j}(n_{d}) ≤ f_{P,i,j}(n_{d}), and is easy to compute when i = 0:

Lemma 5.1. If n_{d} ∈ [0, N_{d}) and 0 ≤ j ≤ k, then we have the upper bound

f_{P,0,j}(n_{d}) ≤ N_{d}.  (24)

If in addition n_{d} lies in the middle third [N_{d}/3, 2N_{d}/3) of [0, N_{d}), then we can complement this upper bound with the lower bound

f_{P,0,j}(n_{d})\frac{1}{10k} N_{d}.

Proof The estimate (24) just reflects the fact that once n_{d} is fixed, one can specify the progression P_{(m_{d},r)} by fixing m_{d} +j′r for some j′ ≠ j, but this ranges in [0, N_{d}). The lower bound follows for instancce by observing that any |r| ≤ 1/20k will generate a progression P_{(m_{d},r)} ⊂ P with m_{d} + jr = n_{d}, which is then automatically perfect of order 0.

Recall from (23) that the proportion of components P_{j,n_{d}} which have the perfect color is roughly δ_{c_{d−1}}(∞), or in other words the probability that a randomly chosen component is perfectly colored is roughly δ_{c_{d−1}}(∞). If the perfectly colored components were distributed “independently of each other”, then probabilistic heuristics would then suggest that f_{P,i,j}(n_{d}) ≈ δ_{c_{d−1}(∞)}^{i}f_{P,0,j}(n_{d}), and so in particular for n_{d} in the middle third [N_{d}/3, 2N_{d}/3) one would expect f_{P,i,j}(n_{d}) to be roughly of the order of δ_{c_{d−1}(∞)}^{i}N_{d} for most n_{d}. Now, a priori there is no reason why one should expect this property (which is broadly analogous to the concepts of “weak mixing” used in the Furstenberg proof of Szemerédi’s theorem, “Gowers uniformity” in the Gowers’ proof, or “ε-regularity” in the proof of the Szemerédi regularity lemma) should be hold for a typical progression P. If however we have a long sequence of such progressions P which are arranged in a special way (we will make this concept more precise later), it will turn out that this type of property will in fact hold for at least one progression in a sequence, by means of the Szemerédi regularity lemma combined with van der Waerden’s theorem. This observation is crucial in letting us induct on the parameter i and create increasingly perfect progressions.

We must first formalize the notion of what it means for f_{P,i,j}(n_{d}) to be roughly of the order of δ_{c_{d−1}(∞)}^{i}N_{d} for most n_{d}. This will be done using the concept of a homogeneous progression (again, the notation is from [3]).

Definition 5.2. Let d ≥ 1, let 0 ≤ i ≤ k, and let P be a rank d + 1 increasing progression of dimensions (N_{1}, …, N_{d}, k + 1). We say that P is homogeneous of order i if it obeys the following two properties:

• P is completely saturated (i.e. each of the k + 1 components P_{0}, …, P_{k} is saturated); and

• For all i ≤ j ≤ k, we have

|{n_{d} ∈ [0, N_{d}) : f_{P,i,j}(n_{d}) > (100k)^{i}δ_{c_{d−1}}(∞)^{i}N_{d}}| ≤ iε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d} (25)

and

|{n_{d} ∈ [N_{d}/3, 2N_{d}/3) : f_{P,i,j}(n_{d}) < (100k)^{−i−1}δ_{c_{d−1}}(∞)^{i}N_{d}}| ≤ iε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d}. (26)

Thus for almost all n_{d} in [0, N_{d}), and especially in the middle third [N_{d}/3, 2N_{d}/3), the counting function f_{P,i,j}(n_{d}) is fairly close to its expected value of δ_{c_{d−1}(∞)}^{i}N_{d} (the factors of (100k)^{±i} are extremely negligible compared to the very huge numbers and very small being manipulated here).

Thus for instance, any progression P of dimensions (N_{1}, …, N_{d}, k+1) which is completely saturated will automatically be homogeneous of order 0, thanks to Lemma 5.1. It will be of interest to obtain progressions which are homogeneous of as high an order i as possible, as this will imply (by (26)) that there are many subprogressions P_{(m_{d},r)} which are perfect of order i (this is the place where we drop a rank). Furthermore, we will later show (by means of the van der Waerden theorem and the Szemerédi regularity lemma) that given a sufficiently long sequence of progressions P which are homogeneous of order i and are arranged in a special way, one of them will be homogeneous of order i+1. The combination of these two facts (by a simple induction argument) will eventually give us progressions which are perfect of any order 0 ≤ i ≤ k, which in particular will give Proposition ??.

To make this argument rigorous we need to pin down what we mean by a sequence of progressions P being “arranged in a special way”. We shall do this via the following somewhat technical definition (which is forced on us by the inductive argument we shall use).

Definition 5.3. Let d ≥ 1, let Ω ⊂ [0, k]. We define a well-arranged sequence of progressions P [] of rank d+1 and parameterization Ω to be an assigment P [(λ_{j})_{j∈Ω}] of a rank d + 1 increasing progression of dimensions (N_{1}, …, N_{d}, k + 1) to each Ωtuple (λ_{j})_{j∈Ω} ∈ [0, F_{0}(L_{d}))^{Ω} (which we refer to as the parameters of the sequence) such that

• (i) (Complete saturation property) For each (λ_{j})_{j∈Ω} ∈ [0, L_{d})^{Ω}, the progression P [(λ_{j})_{j∈Ω}] is completely saturated.

• (ii) (Independence property) For any 0 ≤ i′ ≤ k, the color c(P [(λ_{j})_{j∈Ω}]_{i′}) ∈ 2^{[0,N^{(d)})} of the i′ component of P [(λ_{j})_{j∈Ω}] is determined entirely by those λ_{j} for which j ≤ i′; to put this another way, the parameter λ_{j} influences the colors of the j, …, k components of P [(λ_{j})_{j∈Ω}] but has no effect on the colors of the 0, …, j − 1 components.

• (iii) (Arithmetic structure) For each j_{0} ∈ Ω, if we fix all of the λ_{j} indices except for the λ_{j_{0}} index, then the components P [(λ_{j})_{j∈Ω}]_{j_{0}}, as λ_{j_{0}} ranges from 0 to L_{d} − 1, form an increasing rank d progression of dimensions (N_{1}, …, N_{d−1}, L_{d}).

Note that in the case Ω = ∅, then there are no free praameters, and any completely saturated rank d+1 progression P of dimensions (N_{1}, …, N_{d}, k+1) is automatically well-arranged. The independence assumptions (ii) are necessary in order for us to manipulate the parameters λ_{j}, j ∈ Ω more or less independently; the arithmetic structure assumptions (iii) are needed in order for us to apply van der Waerden’s theorem at a key juncture.

The proof of Proposition ?? centers around the following two key propositions, which correspond roughly to Lemma 6 and Lemma 5 from [3].

Proposition 5.4. [3, Lemma 6] Let d ≥ 2, 0 ≤ i ≤ k, and let Ω ⊂ [i, k] be such that i ∉ Ω (i.e. Ω ⊂ [i + 1, k]). Suppose that we have a well-arranged sequence of progressions P [] of rank d + 1 and parameterization Ω such that every progression P [(λ_{j})_{j∈Ω}] in this sequence is homogeneous of order i. Then there exists another well-arranged sequence of progressions Q[] of rank d and parameterization Ω ∪ {i}.

Proposition 5.5. [3, Lemma 5] Let d ≥ 1, 0 ≤ i ≤ k, and let Ω ⊂ [i, k) be such that i ∈ Ω. Suppose that we have a well-arranged sequence of progressions P [] of rank d + 1 and parameterization Ω such that every progression P [(λ_{j})_{j∈Ω}] in this sequence is homogeneous of order i. Then there exists another well-arranged sequence of progressions Q[] of rank d + 1 and parameterization Ω\{i}, such that every progression Q[(λ_{j})_{j∈Ω\{i}}] in this sequence is homogeneous of order i + 1.

Proposition 5.4 allows us to convert homogeneity of order i to an additional parameterization, by the λ_{i} parameter, at the cost of dropping one rank; Proposition 5.5 allows us to spend such a λ_{i} parameter to upgrade homogeneity of order i to homogeneity of order i + 1, keeping the rank constant. These two propositions will be proven in the next two sections. Assuming them for the moment, the two propositions combine to form the following key fact, which is essentially Fact 12 from [3]:

Corollary 5.6. [3, Fact 12] Let 0 ≤ i ≤ k, d ≥ 2^{i}, and let Ω ⊂ [i, k]. Suppose that we have a well-arranged sequence of progressions P [] of rank d + 1 and parameterization Ω. Then there exists another well-arranged sequence of progression Q[] of rank d − 2^{i} + 2 and parameterization Ω such that every progression Q[(λ_{j})_{j∈Ω}] in this sequence is homogeneous of order i.

Proof We prove this by induction on i. The claim is trivial for i = 0 since, by property (i) of a well-arranged sequence, each P [(λ_{j})_{j∈Ω}] is completely saturated and hence homogeneous of order 0, so we may simply take Q := P.

Now suppose that 1 ≤ i ≤ k, and the claim has already been proven for i−1. Let P [] be a well-arranged sequence of progressions P [] of rank d + 1 and parameterization Ω for some Ω ⊂ [i, k]. By the induction hypothesis, we can find a well-arranged sequence of progressions P′[] of rank d − 2^{i−1} + 2 and parameterization Ω such that each P′[(λ_{j})_{j∈Ω}] in this sequence is homogeneous of order i − 1. If we then apply Proposition 5.4 to this sequence, we obtain another well-arranged sequence of progressions P′′[] of rank d−2^{i−1} +1 and parameterization Ω∪{i−1}. Applying the induction hypothesis again, we can then find another well-arranged sequence of progressions P′′′[] of rank d−2^{i} +2 and parameterization Ω∪{i−1}, such that each P′[(λ_{j})_{j∈Ω}] in this sequence is homogeneous of order i − 1. Applying Proposition 5.5, we finally obtain a well-arranged sequence of progressions Q[] of rank d − 2^{i} + 2 and parameterization Ω, such that every progression Q[(λ_{j})_{j∈Ω}] in this sequence is homogeneous of order i, thus closing the induction.

We can now prove Theorem 1.1, as follows.

Proof [Proof of Theorem 1.1] Let d := 2^{k}. From (2) we know that

\overline{σ_{N^{(d)}}}(∞) ≥ 1 − 1/100k

and hence there exists some L ≥ 100k and some increasing progression P of rank d + 1 and dimensions (N_{1}, …, N_{d}, L) such that

σ_{N^{(d)}}(P) ≥ 1 − 1/100k,

i.e. all the components P_{0}, …, P_{L−1} of P are saturated with at most L/100k exceptions. Applying Lemma 1.2, we can thus find an increasing subprogression P′ = P_{l} ∪ P_{l+r}, … ∪ P_{l+kr} which is completely saturated. This progression P′ has rank d + 1 and dimensions (N_{1}, …, N_{d}, k + 1); since it is completely saturated, it can be viewed as a well-arranged sequence P′ = P′[] of rank d + 1 parameterized by the empty set Ω = ∅. Applying Corollary 5.6 with i = k and Ω = ∅ we can thus find a completely saturated increasing progression Q′ of rank 2 and dimensions (N_{1}, k + 1) which is homogeneous of degree k. From (26) we thus see that there exists an n_{1} ∈ [N_{1}/3, 2N_{1}/3) such that f_{Q′,k,k}(n_{1}) > 0, which implies in particular that there exists an increasing progression R of length k + 1 which is perfect of order k, i.e. the first k elements of this progression lie in A, as desired.

The only thing left to do is prove Propositions 5.4 and 5.5.

6. Proof of Proposition 5.4

We now prove Proposition 5.4, which is the more elementary of the two propositions (it does not require either the van der Waerden theorem or the Szemerédi regularity lemma); the principal difficulty is to ensure that ensure that all the relevant components of the various progressions involved are saturated.

Fix P, i, Ω. If m_{d}, m_{d} + r, …, m_{d} + kr is a progression of integers in [0, N_{d}), let us call the pair (m_{d}, r) perfect of order i if the subprogression P [(λ_{j})_{j∈Ω}]_{(m_{d},r)} is perfect of order i for some (λ_{j})_{j∈Ω} ∈ [0, F_{0}(L_{d−1}))^{Ω}; we have truncated the range of the parameters λ_{j} from [0, F_{0}(L_{d})) to the much smaller (and hence more tractable) range of [0, F_{0}(L_{d−1})) as we shall eventually drop rank by 1 . Actually, the choice of the λ_{j} is irrelevant since the concept of perfection will only depend on the color of first i components P [(λ_{j})_{j∈Ω}]_{0,m_{d}}, …, P [(λ_{j})_{j∈Ω}]_{i−1,m_{d}+(i−1)r}, whereas by the hypothesis Ω ⊂ [i, k] and and by the independence property (ii) of a well-arranged sequence, the colors of the first i components do not depend on any of the parameters λ_{j} for j ∈ Ω. Let us call the pair (m_{d}, r) totally saturated if the subprogression P [(λ_{j})_{j∈Ω}]_{(m_{d},r)} is completely saturated for every (λ_{j})_{j∈Ω} ∈ [0, F_{0}(L_{d−1}))^{Ω}. Unlike the concept of perfection of order i, the parameters λ_{j} do play a non-trivial role in this concept, as the concept of saturation involves the colors of all k+1 components of P [(λ_{j})_{j∈Ω}]_{(m_{d},r)}. However, since all the P [(λ_{j})_{j∈Ω}] are completely saturated (by property (i) of a well-arranged sequence), the estimate (10) asserts that almost all components P [(λ_{j})_{j∈Ω}]_{i′,n_{d}} will be saturated:

\frac{1}{N_{d}} |\{n_{d} ∈ [0, N_{d}) : P [(λ_{j})_{j∈Ω}]_{i′,n_{d}} is not saturated\}| ≤ 2ε_{d−1} for all (λ_{j})_{j∈Ω} ∈ [0, F_{0}(L_{d−1}))^{Ω}, 0 ≤ i′ ≤ k.

This basically means that the property of being completely saturated is easy to attain. This, combined with (26) makes the following lemma fairly reasonable:

Lemma 6.1. Call an element n_{d} ∈ [N_{d}/3, 2N_{d}/3) good if there exists a progression m_{d}, …, m_{d} + kr in [0, N_{d}) with m_{d} + ir = n_{d} such that (m_{d}, r) is both perfect of order i and totally saturated. Then most elements of [N_{d}/3, 2N_{d}/3) are good, or more precisely

|\{n_{d} ∈ [N_{d}/3, 2N_{d}/3) : n_{d} is not good\}| ≤ \frac{1}{100kF_{0}(L_{d−1})}N_{d}.

Proof This will be a simple counting argument. There will be a slight technical difficulty in that some of the error terms have size equal to some power of ε_{d−1}, which is is somewhat large compared to the factors of δ_{c_{d−1}}(∞) which appear in (26), but by counting things carefully (and taking advantage of the upper bound

(25) as well as the lower bound (26)) the factors of δ_{c_{d−1}}(∞) will eventually cancel each other out harmlessly.

First of all, observe from (26) that

|{n_{d} ∈ [N_{d}/3, 2N_{d}/3) : |{(m_{d}, r) perfect of order i : m_{d} + ir = n_{d}}| < (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}N_{d}}|

< iε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d}.

Also, since Ω ⊂ [i + 1, k], the component P [(λ_{j})_{j∈Ω}]_{i,n_{d}} does not depend on (λ_{j}), so by (27)

|{n_{d} ∈ [N_{d}/3, 2N_{d}/3) : P [(λ_{j})_{j∈Ω}]_{i,n_{d}} is not saturated for some (λ_{j})_{j∈Ω} ∈ [0, L_{d−1})^{Ω}}| ≤ 2ε_{d−1}N_{d}.

Both these terms are acceptable by (19). Thus it will suffice to prove that

|X| ≤ \frac{1}{200kF_{0}(L_{d−1})}N_{d}

(for instance), where X is the set of those n_{d} ∈ [N_{d}/3, 2N_{d}/3) such that n_{d} is not good, but

|{(m_{d}, r) perfect of order i : m_{d} + ir = n_{d}}| ≥ (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}N_{d} (28)

and such that P [(λ_{j})_{j∈Ω}]_{i,n_{d}} is saturated for all (λ_{j})_{j∈Ω} ∈ [0, F_{0}(L_{d−1}))^{Ω}.

Now suppose that n_{d} ∈ X. From (28) we have (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}N_{d} pairs (m_{d}, r) m_{d} + jr = n_{d} and (m_{d}, r) perfect of order i. Since n_{d} is not good, we know that for each such pair (m_{d}, r), at least one Ω-tuple (λ_{j})_{j∈Ω} ∈ [0, F_{0}(L_{d−1}))^{Ω} exists such that P [(λ_{j})_{j∈Ω}] is not totally saturated. Since (m_{d}, r) is perfect of order i, we know that the first i+1 components P [(λ_{j})_{j∈Ω}]_{0}, …, P [(λ_{j})_{j∈Ω}]_{i,m_{d}+ir} are already saturated, so we must have P [(λ_{j})_{j∈Ω}]_{i′,m_{d}+i′r} unsaturated for some i < i′ ≤ k. Thus

∑_{(m_{d},r) perfect of order i:m_{d}+jr=n_{d}} ∑_{(λ_{j})_{j∈Ω}∈[0,L_{d−1})^{Ω}} ∑_{i<i′≤k}
1_{P [(λ_{j})_{j∈Ω}]_{i′,m_{d}+i′r} unsaturated} ≥ (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}N_{d}.

Summing over all n_{d} ∈ X, we obtain

∑_{(m_{d},r) perfect of order i} ∑_{(λ_{j})_{j∈Ω}∈[0,L_{d−1})^{Ω}} ∑_{i<i′≤k} 1_{P [(λ_{j})_{j∈Ω}]_{i′,m_{d}+i′r} unsaturated} ≥ (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}|X|N_{d}.

The number of possible (λ_{j})_{j∈Ω} is at most F_{0}(L_{d−1})^{k+1}, and the number of i′ is at most k, so by the pigeonhole principle we can find a (λ_{j})_{j∈Ω} and i < i′ ≤ k such that

∑_{(m_{d},r) perfect of order i} 1_{P [(λ_{j})_{j∈Ω}]_{i′,m_{d}+i′r} unsaturated} ≥ \frac{1}{kF_{0}(L_{d−1})^{k+1}} (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}|X|N_{d}.

We rearrange this using the substitution n′_{d} := m_{d} + i′r as

∑_{n′_{d}∈[0,N_{d}):P [(λ_{j})_{j∈Ω}]_{i′,n′_{d}} unsaturated} |{(m_{d}, r) perfect of order i : m_{d} + i′r = n′_{d}}|

≥ \frac{1}{kF_{0}(L_{d−1})^{k+1}} (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}|X|N_{d}

or (by definition of f)

∑_{n′_{d}∈[0,N_{d}):P [(λ_{j})_{j∈Ω}]_{i′,n′_{d}} unsaturated} f_{P [(λ_{j})_{j∈Ω}],i,i′}(n′_{d}) ≥ \frac{1}{kF_{0}(L_{d−1})^{k+1}} (100k)^{−i−1}δ_{c_{d−1}(∞)}^{i}|X|N_{d}.

(29)

On the other hand, from (25) and (24) we have

∑_{n′_{d}∈[0,N_{d}):f_{P [(λ_{j})_{j∈Ω}],i,i′} (n_{d})>(100k)^{i}δ_{c_{d−1}(∞)}^{i}N_{d}} f_{P [(λ_{j})_{j∈Ω}],i,i′}(n′_{d}) ≤ iε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d}^{2}

while from (27) we have

∑_{n′_{d}∈[0,N_{d}):f_{P [(λ_{j})_{j∈Ω}],i,i′} (n_{d})≤(100k)^{i}δ_{c_{d−1}(∞)}^{i}N_{d};P [(λ_{j})_{j∈Ω}]_{i′,n′_{d}} unsaturated} f_{P [(λ_{j})_{j∈Ω}],i,i′}(n′_{d})

≤ (100k)^{i}δ_{c_{d−1}(∞)}^{i}N_{d} × 2ε_{d−1}N_{d}

so on adding we have

∑_{n′_{d}∈[0,N_{d}):P [(λ_{j})_{j∈Ω}]_{i′,n′_{d}} unsaturated} f_{P [(λ_{j})_{j∈Ω}],i,i′}(n′_{d}) ≤ 4(100k)^{i}δ_{c_{d−1}(∞)}^{i}ε_{d−1}N_{d}^{2}

(since ε_{d−1} and δ_{c_{d−1}(∞)} are at most 1). Combining this with (29) we obtain the bound

|X| ≤ 4k(100k)^{2i+1}L_{d−1}^{k+1}ε_{d−1}N_{d};

the claim then follows by (19) (and the trivial bound i ≤ k).

Combining this lemma with Lemma 1.2, we can find an increasing arithmetic progression {n_{d} + λ_{i}s : λ_{i} ∈ [0, F_{0}(L_{d}))} of length F_{0}(L_{d}) in [N_{d}/3, 2N_{d}/3), all of whose elements are good. Thus for each λ_{i} ∈ [0, F_{0}(L_{d})), there exists a progression m_{d}(λ_{i}), …, m_{d}(λ_{i})+kr(λ_{i}) in [0, N_{d}) such that m_{d}(λ_{i})+ir(λ_{i}) = n_{d} +λ_{i}s which is perfect of order i and which is totally saturated. Thus if we define the progressions Q[(λ_{j})_{j∈Ω∪{i}}] for any (λ_{j})_{j∈Ω∪{i}} ∈ [0, F_{0}(L_{d}))^{Ω∪{i}} by the formula

Q[(λ_{j})_{j∈Ω∪{i}}] = ⋃_{i′=0}^{k} P [(λ_{j})_{j∈Ω}]_{i′,m_{d}(λ_{i})+i′r(λ_{i})}

we see that Q[(λ_{j})_{j∈Ω∪{i}}] is a progression of rank d and dimensions (N_{1}, …, N_{d−1}, k+ 1) which is completely saturated and perfect of order i. In particular, the color of the first i components of Q[(λ_{j})_{j∈Ω∪{i}}] are the perfect color c_{d−1}, which clearly does not depend on any of the λ_{j} including λ_{i}. As for the remaining components, the independence properties of these components from the λ_{i} follow from the corresponding independene properties of the corresponding components of P [(λ_{j})_{j∈Ω}] (note that the quantities m_{d}(λ_{i}) and r(λ_{i}) do not depend on any of the λ_{j} for any j ∈ Ω). Also if we fix all the λ_{j} for j ∈ Ω, then

Q[(λ_{j})_{j∈Ω∪{i}}]_{i} = P [(λ_{j})_{j∈Ω}]_{i,m_{d}(λ_{i})+ir(λ_{i})} = P [(λ_{j})_{j∈Ω}]_{i,n_{d}+λ_{i}s}

which forms an increasing arithmetic progression in λ_{i}. The analogous arithmetic structural properties for the other parameters λ_{j} again follow from the corresponding properties for P. Thus we have constructed a well-arranged sequence of progressions Q[] of rank d and parameterization Ω ∪ {i}, as desired.

7. Proof of Proposition 5.5

We now turn to Proposition 5.5, which is the harder of the two propositions. The main task is to prove the Proposition in the case Ω = {i}, in which case we let Q simply be one of the elements of the sequence. In other words, we will showl

Proposition 7.1. Let d ≥ 1 and 0 ≤ i ≤ k Suppose that we have a well-arranged sequence of progressions P [] of rank d + 1 and parameterization {i} such that P [λ_{i}] is homogeneous of order i for all λ_{i} ∈ [0, F_{0}(L_{d})]. Then there exists λ_{i} ∈ [0, F_{0}(L_{d})] such that P [λ_{i}] is homogeneous of order i + 1.

This proposition clearly gives Proposition 5.5 in the case Ω = {i}. To handle the general case, when Ω contains elements other than i, we simply fix all the variables λ_{j} for j ∈ Ω\{i} and apply the above proposition to locate a λ_{i} such that P [(λ_{j})_{j∈Ω}] is homogeneous of order i + 1. Note that the concept of being homogeneous of order i + 1 depends only on the colors of the first i + 1 components of the progression under consideration, which by the independence property (ii) of a well-arranged sequence, does not depend on any of the λ_{j} for j ∈ Ω\{i}. Thus we can choose λ_{i} independently of all the other λ_{j} in such a way that P [(λ_{j})_{j∈Ω}] is always homogeneous of order i + 1. We can then define Q[] by restricting P to this value of λ_{i}, thus i.e.

Q[(λ_{j})_{j∈Ω\{i}}] := P [(λ_{j})_{j∈Ω}].

The complete saturation, independence, and arithmetic structure properties of Q then trivially follow from those of P, and the claim follows.

It remains to prove Proposition 7.1. Let us first state what we are trying to achieve. From (25), (26) we already have

|{n_{d} ∈ [0, N_{d}) : f_{P [λ_{i}],i,j}(n_{d}) > (100k)^{i}δ_{c_{d−1}}(∞)^{i}N_{d}}| ≤ iε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d}(30)

and

|{n_{d} ∈ [N_{d}/3, 2N_{d}/3) : f_{P [λ_{i}],i,j}(n_{d}) < (100k)^{−i−1}δ_{c_{d−1}}(∞)^{i}N_{d}}| ≤ iε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d} (31)

for all λ_{i} ∈ [0, F_{0}(L_{d})] (in fact the left-hand sides here are independent of λ_{i} thanks to the independence property of well-arranged sequences) and all i ≤ j ≤ k, and we are trying to find a single λ_{i} ∈ [0, F_{0}(L_{d})] such that

|{n_{d} ∈ [0, N_{d}) : f_{P [λ_{i}],i+1,j}(n_{d}) > (100k)^{i+1}δ_{c_{d−1}}(∞)^{i+1}N_{d}}| ≤ (i+1)ε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d}

|{n_{d} ∈ [N_{d}/3, 2N_{d}/3) : f_{P [λ_{i}],i+1,j}(n_{d}) < (100k)^{−i−2}δ_{c_{d−1}}(∞)^{i}N_{d}}| ≤ (i+1)ε_{d−1}δ_{c_{d−1}}(∞)^{k+1}N_{d} for all i < j ≤ k (One does not need to verify that P [λ_{i}] is completely saturated, as this is given to us by the hypothesis that P [λ_{i}] is already homogeneous of order i). We introduce the small quantity^{1}

ϵ := ε_{d−1}^{100k}δ_{c_{d−1}}(∞)^{100k}  (32)

and observe that to prove our claim it will suffice to find a single λ_{i} ∈ [0, F_{0}(L_{d})] such that

f_{P [λ_{i}],i+1,j}(n_{d}) = δ_{c_{d−1}}(∞)f_{P [λ_{i}],i,j}(n_{d}) + O_{k}(ϵN_{d}) for all i < j ≤ k (33)

for all but O_{k}(ϵ)N_{d} many values of n_{d} ∈ [0, N_{d}). To explain why one could hope for such a statement, let us rephrase the task in terms of graph theory. We temporarily fix i < j ≤ k, and introduce a bipartite graph G_{ij}, connecting the interval A_{i} := [0, N_{d}) to another copy of the interval A_{j} := [0, N_{d}) (which strictly speaking we should label differently to emphasize the bipartite nature of the graph, but let us ignore this technicality), thus the edge set E(G_{ij}) can be thought of as a subset of A_{i} × A_{j}. This graph is defined as follows: we connect an element a_{i} ∈ A_{i} with an element a_{j} ∈ A_{j} by an edge if we can find a progression m_{d}, m_{d} + s, …, m_{d} + ks in [0, N_{d}) which is perfect of order i (i.e. all the components P [λ_{i}]_{i′,m_{d}+i′s} have the perfect color for all 0 ≤ i′ < i; note that the choice of λ_{i} is not relevant here by the independence property of well-arranged sequences), and such that m_{d} +is = a_{i} and m_{d} + js = a_{j}. Note that each pair (a_{i}, a_{j}) is associated to at most one progression m_{d}, …, m_{d}+ks and so the graph has no multiplicity. For each λ_{i}, we let A_{i}[λ_{i}] ⊂ A_{i} be the set of those a_{i} ∈ A_{i} for which P [λ_{i}]_{i,a_{i}} has the perfect color. Unraveling the definitions, we see that

• f_{P [λ_{i}],i,j}(a_{j}) (which does not depend on λ_{i}) is precisely the number of edges

in G_{ij} connecting an element of A_{i} to a_{j}; and

1At this point it is useful to note the relative magnitudes here are basically

1/ε_{d−1} ≪ N_{d−1} ≪ 1/δ_{c_{d−1}}(∞) ≪ 1/ϵ ≪ L_{d} ≪ F_{0}(L_{d}) ≪ 1/ε_{d} ≪ N_{d} thanks to (16), (19), (20), (5); actually, the quantity 1/δ_{c_{d−1}}(∞) could be unexpectedly smaller than what (5) would suggest, but that will help us, not hurt us. As discussed earlier, the basic point is that L_{d} and F_{0}(L_{d}) are much smaller than N_{d}, but much larger than 1/ϵ or any quantity subscripted by d − 1.

• f_{P [λ_{i}],i+1,j}(a_{j}) is precisely the number of edges in G_{ij} connecting an element

of A_{i}[λ_{i}] to a_{j}.

Furthermore, since P [λ_{i}] is completely saturated, the progression P [λ_{i}]_{i} obeys (9) (with one smaller rank), and hence

|A_{i}[λ_{i}]| = (\overline{δ_{c_{d−1}}}(∞) + O(ε_{d}))N_{d},  (34)

i.e. A_{i}[λ_{i}] has density roughly \overline{δ_{c_{d−1}}}(∞) in A_{i}. In particular we would also expect f_{P [λ_{i}],i+1,j}(a_{j}) to be roughly \overline{δ_{c_{d−1}}}(∞) times as large as f_{P [λ_{i}],i,j}(a_{j}), which is (33).

Unfortunately we are not done yet, because the graph G_{ij} and the set A_{i}[λ_{i}] could “conspire” to create multiplicities f_{P [λ_{i}],i+1,j}(a_{j}) which are quite different from what one would expect given the multiplicities of G_{ij} and the density of A_{i}[λ_{i}]. Indeed, for any individual λ_{i}, one could easily make (33) fail. However, it will turn out (from an application of the Szemerédi regularity lemma) that in order to make

(33) fail, one must make the relative density A_{i}[λ_{i}] on some component A_{i}^{m;ij} of A_{i} to be anomalously large or anomalously small. If one does this for each λ_{i}, then using van der Waerden’s theorem we will eventually be able to make a single component A_{i}^{m;ij} consistently anomalous (either anomalously large or anomalously small) for all λ_{i} in a long progression (of length L_{d} now rather than F_{0}(L_{d})). But then by some density counting arguments we will be able obtain a contradiction from these facts, (34), and the fact (from (17)) that progressions of L_{d} cannot have too large a color density.

We turn to the details. We begin by counting the number of edges in G_{ij}.

Lemma 7.2. The number |E(G_{ij})| of edges in G_{ij} obeys the estimates

(100k)^{−i−2}δ_{c_{d−1}}(∞)^{i}N_{d}^{2} ≤ |E(G_{ij})| ≤ (100k)^{i+1}δ_{c_{d−1}}(∞)^{i}N_{d}^{2}.

In other words, up to factors depending only on k, the edge density of G_{ij} is comparable to δ_{c_{d−1}}(∞)^{i}.

Proof Observe that

|E(G_{ij})| = ∑_{a_{j}∈[0,N_{d})} f_{P [λ_{i}],i,j}(a_{j}).

Applying (30) and the crude bound f_{P [λ_{i}],i,j}(a_{j}) ≤ N to handle the exceptional set, we obtain the desired upper bound. For the lower bound, we trivially bound

|E(G_{ij})| ≥ (100k)^{−i−1}δ_{c_{d−1}}(∞)^{i}N_{d}|{a_{j} ∈ [N_{d}/3, 2N_{d}/3) : f_{P [λ_{i}],i,j}(n_{d}) ≥ (100k)^{−i−1}δ_{c_{d−1}}(∞)^{i}N_{d}}|

and use (31).

Now we use the Szemerédi regularity lemma. We shall use the modern version of this lemma (see e.g. my expository note [5], or many other references in the literature), rather than the original one in [3]. For any non-empty subsets A′_{i} ⊆ A_{i}, A′_{j} ⊆ A_{j}, define the density 0 ≤ d(A′_{i}, A′_{j}) ≤ 1 of this pair to be the quantity

d(A′_{i}, A′_{j}) := \frac{|E(G_{ij}) ∩ (A′_{i} × A′_{j})|}{|A′_{i} × A′_{j}|}.

We say that a pair A′_{i}, A′_{j} is ϵ^{2}-regular if we have

|E(G_{ij}) ∩ (A′′_{i} × A′′_{j})| = d(A′_{i}, A′_{j})|A′′_{i} × A′′_{j}| + O(ϵ^{2})|A′_{i} × A′_{j}|

for all subsets A′′_{i} ⊆ A′_{i}, A′′_{j} ⊆ A′_{j}. The Szemerédi regularity lemma asserts that there is a constant C(ϵ) depending only on ϵ, and partitions^{2}

A_{l} = A_{l}^{1;ij} ∪ … ∪ A_{l}^{M_{ij};ij} ∪ A_{l}^{error;ij} for l = i, j

with M_{ij} ≤ C(ϵ) and |A_{l}^{M_{ij};ij}| = O(ϵ)N_{d} and |A_{l}^{m;ij}| ∼ N_{d}/M_{ij} for m ∈ [1, M_{ij}), such that all but O(ϵ^{4}M_{ij}^{2}) pairs (A_{i}^{m;ij}, A_{j}^{m′;ij}) are ϵ^{2}-regular. Actually, we can

refine the last statement a bit, to say that for every m′, the pair (A_{i}^{m;ij}, A_{j}^{m′;ij}) is epsilon regular for all but O(ϵ^{2}M_{ij}) values of m, since the values of m′ which do not obey such a property can be safely absorbed into the exceptional set (and then one has to reduce M_{ij} accordingly, e.g. by removing the corresponding values of m into an exceptional set also).

Let us fix this decomposition. The point of this decomposition is that if a_{i} ∈ A_{i}^{m;ij} and a_{j} ∈ A_{j}^{m′;ij}, then one should behave as if a_{i} were connected to a_{j} in

G with “probability” d(A_{i}^{m;ij}, A_{j}^{m′;ij}). In particular, one now expects to have the approximation

f_{P [λ_{i}],i+1,j}(a_{j}) ≈ \overline{f}_{P [λ_{i}],i+1,j}(a_{j})

where

\overline{f}_{P [λ_{i}],i+1,j}(a_{j}) := ∑_{m,m′∈[1,M_{ij}]} d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}] ∩ A_{i}^{m;ij}|1_{a_{j}∈A_{j}^{m′;ij}}. (35)

Similarly one expects

f_{P [λ_{i}],i,j}(a_{j}) ≈ \overline{f}_{P [λ_{i}],i,j}(a_{j})

where

\overline{f}_{P [λ_{i}],i,j}(a_{j}) := ∑_{m,m′∈[1,M_{ij}]} d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}^{m;ij}|1_{a_{j}∈A_{j}^{m′;ij}}.  (36)

The point is that the dependence of \overline{f}_{P [λ_{i}],i+1,j} on λ_{i} is much more controllable than the original function f_{P [λ_{i}],i+1,j}(a_{j}), as one only needs to control the M_{ij} numbers |A_{i}[λ_{i}] ∩ A_{i}^{m;ij}|. The functions f_{P [λ_{i}],i,j}(a_{j}), \overline{f}_{P [λ_{i}],i,j}(a_{j}), of course, do not depend on λ_{i} at all.

Let us first verify that f_{P [λ_{i}],i+1,j} and \overline{f}_{P [λ_{i}],i+1,j} are in fact quite close (and similarly with i + 1 replaced by i).

Proposition 7.3. We have

f_{P [λ_{i}],i+1,j}(a_{j}) = \overline{f}_{P [λ_{i}],i+1,j}(a_{j}) + O(ϵN_{d})  (37)

for all a_{j} ∈ [0, N_{d}) with at most O(ϵN_{d}) exceptions. Similarly we have

f_{P [λ_{i}],i,j}(a_{j}) = \overline{f}_{P [λ_{i}],i,j}(a_{j}) + O(ϵN_{d})  (38)

2The notation here is unfortunately a bit heavy, but we have to keep track of the dependence on j as the definition of homogeneity will eventually require us to let j range over all values in (i, k]. However for the next few paragraphs one can suppress the dependence on j.

for all a_{j} ∈ [0, N_{d}) with at most O(ϵN_{d}) exceptions.

Proof We just prove (37), as the proof of (38) is the same. The entire case a_{j} ∈ A_{j}^{error;ij} can be placed in the exceptional set, so now let us assume that

a_{j} ∈ A_{j}^{m′;ij} for some m′; for this fixed value of m′ we will show that (37) holds for

all a_{j} ∈ A_{j}^{m′;ij} with at most O(ϵN_{d}/M_{ij}) exceptions.

For a_{j} ∈ A_{j}^{m′;ij}, we have

f_{P [λ_{i}],i+1,j}(a_{j}) = ∑_{m∈[1,M_{ij}]} |{a_{i} ∈ A_{i}^{m;ij} : (a_{i}, a_{j}) ∈ E(G)}|+|{a_{i} ∈ A_{i}^{error;ij} : (a_{i}, a_{j}) ∈ E(G)}|

and

\overline{f}_{P [λ_{i}],i+1,j}(a_{j}) = ∑_{m∈[1,M_{ij}]} d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}] ∩ A_{i}^{m;ij}|.

The error term |{a_{i} ∈ A_{i}^{error;ij} : (a_{i}, a_{j}) ∈ E(G)}| is O(|A_{i}^{error;ij}|) = O(ϵN_{d}), so it will suffice to show that

∑_{m∈[1,M_{ij}]}(|{a_{i} ∈ A_{i}^{m;ij} : (a_{i}, a_{j}) ∈ E(G)}|−d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}]∩A_{i}^{m;ij}|) = O(ϵN_{d})

with at most O(ϵN_{d}/M_{ij}) exceptions. By Chebyshev’s inequality, it will suffice to show that

∑_{a_{j}∈A_{j}^{m′;ij}} | ∑_{m∈[1,M_{ij}]}(|{a_{i} ∈ A_{i}^{m;ij} : (a_{i}, a_{j}) ∈ E(G)}|−d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}]∩A_{i}^{m;ij}|)| = O(ϵ^{2}N_{d}^{2}/M_{ij}).

The contribution of those m for which (A_{i}^{m;ij}, A_{j}^{m′;ij}) is not ϵ^{2}-regular is acceptable since each such m contributes at most O(N_{d}^{2}/M_{ij}^{2}) and there are only O(ϵ^{2}M_{ij}) such m. So we can restrict to the ϵ^{2}-regular pairs. By the triangle inequality, it then will suffice to show that

∑_{a_{j}∈A_{j}^{m′;ij}} ||{a_{i} ∈ A_{i}^{m;ij} : (a_{i}, a_{j}) ∈ E(G)}|−d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}]∩A_{i}^{m;ij}|)| = O(ϵ^{2}N_{d}^{2}/M_{ij}^{2})

whenever (A_{i}^{m;ij}, A_{j}^{m′;ij}) is ϵ^{2}-regular. Without the absolute values, the summand has mean zero, so it suffices to show that

∑_{a_{j}∈X} |{a_{i} ∈ A_{i}^{m;ij} : (a_{i}, a_{j}) ∈ E(G)}|−d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}]∩A_{i}^{m;ij}| = O(ϵ^{2}N_{d}^{2}/M_{ij}^{2})

uniformly for all subsets X of A_{j}^{m′;ij}. But the left-hand side is the same as

|E(G) ∩ ((A_{i}[λ_{i}] ∩ A_{i}^{m;ij}) × X)|d(A_{i}^{m;ij}, A_{j}^{m′;ij})|A_{i}[λ_{i}] ∩ A_{i}^{m;ij}||X| = O(ϵ^{2}N_{d}^{2}/M_{ij}^{2})

and the claim now follows by ϵ^{2}-regularity.

In light of (37), (38), we see that in order to prove (33) it will suffice to find a λ_{i} ∈ [0, F_{0}(L_{d})) such that

\overline{f_{P [λ_{i}],i+1,j}(a_{j})} = δ_{c_{d−1}}(∞)\overline{f_{P [λ_{i}],i,j}}(a_{j}) + O_{k}(ϵN_{d}) for all i < j ≤ k, a_{j} ∈ [0, N_{d}).

On the other hand, from (35), (36), and the triangle inequality we have

|\overline{f_{P [λ_{i}],i+1,j}(a_{j})} − δ_{c_{d−1}}(∞)\overline{f_{P [λ_{i}],i,j}}(a_{j})| ≤ sup_{m′∈[1,M_{ij}]} ∑_{m∈[1,M_{ij}]} d(A_{i}^{m;ij}, A_{j}^{m′;ij})

||A_{i}[λ_{i}] ∩ A_{i}^{m;ij}| − δ_{c_{d−1}}(∞)||A_{i}^{m;ij}||

≤ M_{ij} sup_{m,m′∈[1,M_{ij}]} ||A_{i}[λ_{i}] ∩ A_{i}^{m;ij}| − δ_{c_{d−1}}(∞)||A_{i}^{m;ij}||

and so it suffices to find a λ_{i} ∈ [0, F_{0}(L_{d})) such that

|A_{i}[λ_{i}] ∩ A_{i}^{m;ij}| = δ_{c_{d−1}}(∞)||A_{i}^{m;ij}| + O_{k}(ϵN_{d}/M_{ij}) for all i < j ≤ k; m ∈ [1, M_{ij}].

The point here is that the free parameter a_{j}, which ranged over an enormous set (of size N_{d}, which is larger than all the other quantities currently in play, and in particular is significantly larger than the number of possible λ_{i} at our disposal, which is F_{0}(L_{d})) has now been replaced by the parameters m, m′, which range over a much smaller set (of size M_{ij}, which as it depends ultimately on ε_{d−1} and δ_{c_{d−1}}(∞) will in particular be quite small compared to F_{0}(L_{d})). This makes our task far easier to perform (we now are trying to locate a solution to a problem which has many more degrees of freedom than constraints, whereas previously the situation was reversed). This is the power of the Szemerédi regularity lemma: to reduce a complicated object (a graph on many vertices) to a simpler one (a probabilistic graph on a much smaller set of vertices).

We still have to locate λ_{i}. Suppose for contradiction that this was not possible. Then for each λ_{i} in [0, F_{0}(L_{d})), there exists 1 < j ≤ k, m ∈ [1, M_{ij}], and a sign ± such that A_{i}[λ_{i}] has anomalous density in A_{i}^{m;ij}:

± (|A_{i}[λ_{i}] ∩ A_{i}^{m;ij}| − δ_{c_{d−1}}(∞)||A_{i}^{m;ij}|) ≥ ϵN_{d}/M_{ij}.  (39)

At present the quantities j, m, ± depend on λ_{i}. However, we now invoke our second powerful tool, the van der Waerden theorem, to eliminate this dependence (while still retaining arithmetic structure on the λ_{i}). From the Szemerédi regularity lemma we had M_{ij} ≤ C(ϵ). Combining this with (32), (16), (20) we have the number of triplets (j, m, ±) is bounded by

≤ 2kC(ϵ) = C(ε_{d−1}, δ_{c_{d−1}}(∞)) = C(N_{d−1}) ≪ L_{d}

(if F_{0} is sufficiently fast) and so the map λ_{i} → (j, m, ±) colors the interval [0, F_{0}(L_{d})) into at most L_{d} colors. By the van der Waerden theorem we can thus find (if F_{0} is sufficiently fast growing^{3}) an increasing arithmetic progression R in [0, F_{0}(L_{d})) of length L_{d} and fixed j, m, ± such that (39) holds for all λ_{i} ∈ R; thus we have a consistently anomalous density in this progression R. We now use some density counting arguments to obtain a contradiction from this and (17).

3This step is the step that causes F_{0} to grow extremely fast; even the Szemerédi regularity lemma only demands tower-type growth of F_{0}, whereas the best elementary bound on van der Waerden’s theorem, due to Shelah, is a triply iterated tower. This in turn leads to very poor final bounds on Szemerédi’s theorem. The bound of Gowers gives much better bounds here - double exponential, to be precise - but it would be rather perverse to use Gowers’ bound here, since the argument in [2] gives Szemerédi’s theorem directly.

Summing (39) for all λ_{i} ∈ R (and taking full advantage of the consistency of the parameters j, m, ±) we see that

| ∑_{λ_{i}∈R} |A_{i}[λ_{i}] ∩ A_{i}^{m;ij}| − δ_{c_{d−1}}(∞)||A_{i}^{m;ij}|L_{d}| ≥ ϵL_{d}N_{d}/M_{ij}.  (40)

On the other hand, by applying (34) for all λ_{i} ∈ R and summing to obtain

∑_{λ_{i}∈R} |A_{i}[λ_{i}]| = (\overline{δ_{c_{d−1}}}(∞) + O(ε_{d}))L_{d}N_{d}.  (41)

To obtain a contradiction we need to somehow restrict (41) to A_{i}^{m;ij}. As we shall see, this will be possible thanks to the control (17) on the perfect color density at scale L_{d}.

We turn to the details. We rearrange the left-hand side to obtain

∑_{a_{i}∈[0,N_{d})} |\{λ_{i} ∈ R : P [λ_{i}]_{i,a_{i}} has the perfect color\}| = (\overline{δ_{c_{d−1}}}(∞) + O(ε_{d}))L_{d}N_{d}.

Note that the progression Q_{a_{i}} := ⋃_{λ_{i}∈R} P [λ_{i}]_{i,a_{i}} is an increasing progression of rank d and dimensions (N_{1}, …, N_{d−1}, L_{d}). Thus we can rearrange the left-hand side again to obtain

∑_{a_{i}∈[0,N_{d})} δ_{c_{d−1}}(Q_{a_{i}}) = (\overline{δ_{c_{d−1}}}(∞) + O(ε_{d}))N_{d}.

We now apply

Lemma 7.4. We have

∑_{a_{i}∈[0,N_{d})}(δ_{c_{d−1}}(Q_{a_{i}}) − \overline{δ_{c_{d−1}}}(∞))_{+} = O(\frac{1}{F_{0}(N_{1} … N_{d−1})})N_{d}

Proof There are two contributions, depending on whether Q_{a_{i}} obeys the condition

|σ_{N^{(d−1)}}(Q_{a_{i}}) − \overline{σ_{N^{(d−1)}}}(∞)| ≤ \sqrt{μ_{d−1}(L_{d})}

or not. If it does, then by (3) we have

δ_{c_{d−1}}(Q_{a_{i}}) ≤ \overline{δ_{c_{d−1}}}(L_{d})

and this contirbution will be acceptable from (17). In the other case, we bound the summand crudely by 1, and reduce to showing that

|\{a_{i} ∈ [0, N_{d}) : |σ_{N^{(d−1)}}(Q_{a_{i}})−\overline{σ_{N^{(d−1)}}}(∞)| > \sqrt{μ_{d−1}(L_{d})}\}| = O(\frac{1}{F_{0}(N_{1} … N_{d−1})})N_{d}.

To see this, we first observe from (8), (7) and the saturation of the P [λ_{i}]_{i} that

|\{a_{i} ∈ [0, N_{d}) : P [λ_{i}]_{i,a_{i}} is saturated\}| = (\overline{σ_{N^{(d−1)}}}(∞) + O(ε_{d}^{4}))N_{d}

for all λ_{i} ∈ R; averaging this in λ_{i} and rearranging the left-hand side we obtain

∑_{a_{i}∈[0,N_{d})} σ_{N^{(d−1)}}(Q_{a_{i}}) = (\overline{σ_{N^{(d−1)}}}(∞) + O(ε_{d}^{4}))N_{d}

and thus

∑_{a_{i}∈[0,N_{d})}(σ_{N^{(d−1)}}(Q_{a_{i}}) − \overline{σ_{N^{(d−1)}}}(∞)) = O(ε_{d}^{4})N_{d}.

But from definition of μ_{d−1}(L_{d}) we have

∑_{a_{i}∈[0,N_{d})}(σ_{N^{(d−1)}}(Q_{a_{i}}) − \overline{σ_{N^{(d−1)}}}(∞))_{+} = O(μ_{d−1}(L_{d}))N_{d}

so by (21)

∑_{a_{i}∈[0,N_{d})} |σ_{N^{(d−1)}}(Q_{a_{i}}) − \overline{σ_{N^{(d−1)}}}(∞)| = O(μ_{d−1}(L_{d}))N_{d}

and the claim now follows from Chebyshev and (18).

From this Lemma and the preceding estimate we have (from (19), (16))

∑_{a_{i}∈[0,N_{d})} |δ_{c_{d−1}}(Q_{a_{i}}) − \overline{δ_{c_{d−1}}}(∞)| = O(\frac{1}{F_{0}(N_{1} … N_{d−1})})N_{d}.

In particular we have

∑_{a_{i}∈A_{i}^{m;ij}} |δ_{c_{d−1}}(Q_{a_{i}}) − \overline{δ_{c_{d−1}}}(∞)| = O(\frac{1}{F_{0}(N_{1} … N_{d−1})})N_{d}

and hence

∑_{a_{i}∈A_{i}^{m;ij}} δ_{c_{d−1}}(Q_{a_{i}}) = \overline{δ_{c_{d−1}}}(∞)|A_{i}^{m;ij}| + O(\frac{1}{F_{0}(N_{1} … N_{d−1})})N_{d}.

We now reverse our previous manipulations, to obtain

∑_{a_{i}∈A_{i}^{m;ij}} |\{λ_{i} ∈ R : P [λ_{i}]_{i,a_{i}} has the perfect color\}| = \overline{δ_{c_{d−1}}}(∞)|A_{i}^{m;ij}|+O(\frac{1}{F_{0}(N_{1} … N_{d−1})})L_{d}N_{d}

whichrearrangesasbeforeto ∑_{λ_{i}∈R} |A_{i}[λ_{i}]∩A_{i}^{m;ij}| = \overline{δ_{c_{d−1}}}(∞)|A_{i}^{m;ij}|+O(\frac{1}{F_{0}(N_{1} … N_{d−1})})L_{d}N_{d}.

Comparing this with (40) we obtain

ϵ/M_{ij} = O(\frac{1}{F_{0}(N_{1} … N_{d−1})})

which is a contradiction if F_{0} grows quickly enough, because ϵ/M_{ij} can be bounded below by a quantity depending on ϵ, which in turn depends on ε_{d−1} and \overline{δ_{c_{d−1}}}(∞), which in turn is bounded by N_{1} … N_{d−1} thanks to (5) (and (20)). This finally completes the proof of Proposition 5.5 and hence of Szemerédi’s theorem.

References

[1] H. Furstenberg, Recurrence in Ergodic theory and Combinatorial Number Theory, Princeton University Press, Princeton NJ 1981.

[2] T. Gowers, A new proof of Szemerédi’s theorem, GAFA 11 (2001), 465-588.

[3] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 299–345.

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

[5] T. Tao, An information theoretic proof of Szemerédi’s regularity lemma, unpublished.

26 TERENCE TAO

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

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