A QUANTITATIVE ERGODIC THEORY PROOF OF SZEMERÉDI’S THEOREM (ABRIDGED)

TERENCE TAO

Abstract. A famous theorem of Szemerédi asserts that given any density δ and any k ≥ 3, any set of integers with density δ will contain infinitely many proper arithmetic progressions of length k. We give an elementary proof of this fact, abridging the version in [7].

1. Introduction

Let Z_{N} := Z/NZ be a cyclic group of prime order. If f : Z_{N} → R is a function, we define E(f|Z_{N}) := \frac{1}{N} ∑_{x∈Z_{N}} f(x) for the expectation of f, and similarly define E(f(x)|A) := \frac{1}{|A|} ∑_{x∈A} f(x) for any non-empty set A ⊂ Z_{N}. We let 1_{Ω} denote the indicator of a function A, and write P(Ω|Z_{N}) for E(1_{Ω}|Z_{N}), etc. We also adopt the following ergodic theory notation: if f : Z_{N} → R is a function, we define the shifts T^{n}f : Z_{N} → R for any n ∈ Z_{N} or n ∈ Z by T^{n}f(x) := f(x+n), and similarly define T^{n}Ω for any Ω ⊂ Z_{N} by T^{n}Ω := Ω − n, thus T^{n}1_{Ω} = 1_{T^{n}Ω}. We also need the usual L^{p} norms

∥f∥_{L^{∞}} := sup_{x∈Z_{N}} |f(x)|; ∥f∥_{L^{2}} := ⟨f, f⟩^{1/2} = E(|f|^{2})^{1/2}.

We say a function f : Z_{N} → C is bounded if ∥f∥_{L^{∞}} ≤ 1.

The objective of this note is to prove

Theorem 1.1 (Recurrence form of Szemerédi’s theorem). For any integer k ≥ 1, any large prime N ≥ 1, any 0 < δ ≤ 1, and any non-negative bounded function f : Z_{N} → R^{+} with

E(f|Z_{N}) ≥ δ  (1)

we have

E(∏_{j=0}^{k−1} T^{jr}f(x)|x, r ∈ Z_{N}) ≥ c(k, δ) > 0.  (2)

This is equivalent to the usual formulation [5] of Szemerédi’s theorem, as one can see from an argument of Varnavides [9]. Our argument shall be a “quantitative ergodic theory” argument, in contrast to the infinitary ergodic arguments of Furstenberg and later authors (see e.g. [1]). In particular we do not need the axiom of choice.

1991 Mathematics Subject Classification. ???

The proof proceeds by introducing two families of norms: the Gowers uniformity norms ∥f∥_{U^{k−1}} introduced in [3] (and studied further in [4], [2]) and a new family of norms, the uniform almost periodicity norms ∥f∥_{UAP^{k−2}} which turn out to be somewhat dual to the Gowers uniformity norms.

We shall define these norms rigorously in Sections 2 and 3 respectively. Assuming for now that they are well defined, we now state three key sub-theorems which we will use to imply Theorem 1.1. In Section 2 we will prove

Theorem 1.2 (Generalized Von Neumann theorem). [3] Let k ≥ 2, and let λ_{1}, …, λ_{k} be distinct elements of Z_{N}. Then for any bounded functions f_{1}, …, f_{k} : Z_{N} → C we have

|E(∏_{j=0}^{k−1} T^{λ_{j}r}f_{j}(x)|x, r ∈ Z_{N})| ≤ min_{1≤j≤k} ∥f_{j}∥_{U^{k−1}}.

In Section 8 we will prove

Theorem 1.3 (Almost periodic functions are recurrent). Let d ≥ 0 and k ≥ 1 be integers, and let f_{U^{⊥}}, f_{UAP} be non-negative bounded functions such that we have the estimates

∥f_{U^{⊥}} − f_{UAP} ∥_{L^{2}} ≤ \frac{δ^{2}}{1024k}  (3)
E(f_{U^{⊥}}|Z_{N}) ≥ δ  (4)
∥f_{UAP} ∥_{UAP^{d}} < M  (5)

for some 0 < δ, M < ∞. Then for all μ ∈ Z_{N} and N_{1} ≥ 1 we have

E(∏_{j=0}^{k−1} T^{μjr}f_{U^{⊥}}(x)|x ∈ Z_{N}; 0 ≤ r ≤ N_{1}) ≥ c_{0}(d, k, δ, M) > 0.  (6)

In Section 6 we will prove

Theorem 1.4 (Structure theorem). Let k ≥ 3, and let f be a non-negative bounded function obeying (1) for some δ > 0. Then we can find a positive number M = O_{k,δ}(1), a bounded function f_{U}, and non-negative bounded functions f_{U^{⊥}}, f_{UAP} such that we have the splitting f = f_{U} + f_{U^{⊥}}, the estimates (3), (4), (5) with d := k − 2, and the uniformity estimate

∥f_{U}∥_{U^{k−1}} ≤ 2^{−k}c_{0}(k − 2, k, δ, M)  (7)

where c_{0}(d, k, δ, M) is the quantity in (6).

Assuming these three theorems, we can now quickly conclude Theorem 1.1.

Proof [of Theorem 1.1] Let f, k, δ be as in Theorem 1.1. We may take k ≥ 3 since the cases k = 1, 2 are trivial. Let M, f_{U}, f_{U^{⊥}}, f_{UAP} be as in Theorem 1.4. We can then split the left-hand side of (2) as the sum of 2^{k} terms of the form E(∏_{j=0}^{k−1} T^{jr}f_{j}(x)|x, r ∈ Z_{N}), where each of the functions f_{0}, …, f_{k−1} is equal to either f_{U} or f_{U^{⊥}}. The term in which all the f_{j} are equal to f_{U^{⊥}} is at least c_{0}(k, δ, k − 2, M) by Theorem 1.3 (taking μ := 1 and N_{1} := N − 1. The other 2^{k} − 1 terms have magnitude at most ∥f_{U}∥_{U^{k−1}} ≤ 2^{−k}c_{0}(k, δ, k − 2, M) thanks to Theorem 1.2. Adding all this together we see that

E(∏_{j=0}^{k−1} T^{jr}f(x)|x, r ∈ Z_{N}) ≥ 2^{−k}c_{0}(k − 2, k, δ, M).

Since M = O_{k,δ}(1), the claim (2) follows.

It remains to define the U^{k−1} and UAP^{k−2} norms properly, and prove Theorems 1.2, 1.3, 1.4. This shall occupy the remainder of the paper.

2. Uniformity norms, and the generalized von Neumann theorem

In this section we define the Gowers uniformity norms U^{d} properly, and then prove Theorem 1.2.

Definition 2.1 (Gowers uniformity norms). [3] Let f : Z_{N} → R be a function. We define the d^{th} Gowers uniformity norm ∥f∥_{U^{d}} recursively by

∥f∥_{U^{1}} := |E(f|Z_{N})|; ∥f∥_{U^{d}} := E(∥fT^{h}f∥_{U^{d−1}}^{2^{d−1}}|h ∈ Z_{N})^{1/2^{d}} for d ≥ 2. (8)

One can easily verify by induction that the U^{d} norms are invariant under shifts, thus ∥T^{n}f∥_{U^{d}} = ∥f∥_{U^{d}}, and also invariant under dilations, thus if λ ∈ Z_{N}\0 and f_{λ}(x) := f(x/λ) then ∥f_{λ}∥_{U^{d}} = ∥f∥_{U^{d}}. For d ≥ 2 these norms are indeed genuine norms; see [3], [2], [4].

We can now prove the generalized von Neumann theorem.

Proof [of Theorem 1.2] We induct on k. When k = 2 we use the fact that (x, r) ↦ (x + λ_{1}r, x + λ_{2}r) is a bijection from Z_{N}^{2} to Z_{N}^{2} (recalling that N is prime) to conclude that

E(∏_{j=0}^{1} T^{λ_{j}r}f_{j}(x)|x, r ∈ Z_{N}) = E(f_{1}|Z_{N})E(f_{2}|Z_{N}),

and the claim follows from (8). Now suppose that k > 2 and the claim has already been proven for k − 1. By permuting the λ_{j} if necessary we may assume that the minimum of the ∥f_{j}∥_{U^{k−1}} is attained when j = 0. By making the scaling r ↦ λ_{0}r if necessary we may assume that λ_{0} = 1. By applying the expectation-preserving map T^{−λ_{k−1}r} (i.e. by subtracting λ_{k−1} from each of the λ_{j}) we may assume that λ_{k−1} is zero. The claim can now be written as

|E(f_{k−1}(x)E(∏_{j=0}^{k−2} T^{λ_{j}r}f_{j}(x)|r ∈ Z_{N})|x ∈ Z_{N})| ≤ ∥f_{0}∥_{U^{k−1}}.

By the Cauchy-Schwarz inequality and the boundedness of f_{k−1}, it suffices to prove that

|E(|E(∏_{j=0}^{k−2} T^{λ_{j}r}f_{j}(x)|r ∈ Z_{N})|^{2}|x ∈ Z_{N}) ≤ ∥f_{0}∥_{U^{k−1}}^{2}.

But we can expand the left-hand side to obtain

E(|E(∏_{j=0}^{k−2} T^{λ_{j}r}f_{j}(x)|r ∈ Z_{N})|^{2}|x ∈ Z_{N}) = E((∏_{j=0}^{k−2} T^{λ_{j}r}f_{j}(x))(∏_{j=0}^{k−2} T^{λ_{j}(r+h)}f_{j}(x))|x, h, r ∈ Z_{N})

= E(E(∏_{j=0}^{k−2} T^{λ_{j}r}(f_{j}T^{λ_{j}h})(x)|x, r ∈ Z_{N})|h ∈ Z_{N}).

On the other hand, from the induction hypothesis we have

|E(∏_{j=0}^{k−2} T^{λ_{j}r}(f_{j}T^{λ_{j}h})(x)|x, r ∈ Z_{N})| ≤ ∥f_{0}T^{λ_{0}h}f_{0}∥_{U^{k−2}} = ∥f_{0}T^{h}f_{0}∥_{U^{k−2}}

for all h ∈ Z_{N}. Combining these two facts together, we obtain

|E(|E(∏_{j=0}^{k−2} T^{λ_{j}r}f_{j}(x)|r ∈ Z_{N})|^{2}|x ∈ Z_{N}) ≤ E(∥f_{0}T^{h}f_{0}∥_{U^{k−2}}|h ∈ Z_{N})

and the claim follows from (8) and Hölder’s inequality.

3. Almost periodic functions

Having defined the Gowers uniformity norms U^{k−1} used for the generalized Von Neumann theorem, we now turn to defining the dual concept of the uniform almost periodicity norms UAP^{k−2} which we will need for both the recurrence theorem and structure theorems.

Definition 3.1 (Banach algebras). A space A of functions on Z_{N}, equipped with a norm ∥∥_{A} : A → R^{+}, is said to be a Banach algebra if A is a vector space, ∥∥_{A} is a norm (i.e. it is homogeneous, non-degenerate, and verifies the triangle invariant), and A is closed under pointwise product with ∥fg∥_{A} ≤ ∥f∥_{A}∥g∥_{A} for all f, g ∈ A; in particular we have

∥F ∥_{L^{∞}} ≤ ∥F ∥_{A} for all F ∈ A  (9)

We say that A is shift-invariant if ∥f∥_{A} = ∥T^{n}f∥_{A} for all n, and scale-invariant if ∥f_{λ}∥_{A} = ∥f∥_{A} for all λ ∈ Z_{N}\{0}.

Definition 3.2 (Uniform almost periodicity norms). If A is a shift-invariant Banach algebra of functions on Z_{N}, we define the space UAP [A] to be the space of all functions F for which the orbit {T^{n}F : n ∈ Z} has a representation of the form

T^{n}F = ME(c_{n,h}g_{h}) for all n ∈ Z_{N}  (10)

where M ≥ 0, H is a finite non-empty set, g = (g_{h})_{h∈H} is a collection of bounded functions, c = (c_{n,h})_{n∈Z_{N} ,h∈H} is a collection of functions in A with ∥c_{n,h}∥_{A} ≤ 1, and h is a random variable taking values in H. We define the norm ∥F ∥_{UAP [A]} to be the infimum of M over all possible representations of this form.

We first observe that the construction A ↦ UAP [A] maps shift-invariant Banach algebras to shift-invariant Banach algebras:

Proposition 3.3. If A is a shift-invariant Banach algebra, then so is UAP [A]. Furthermore UAP [A] contains A, and ∥f∥_{UAP [A]} ≤ ∥f∥_{A} for all f ∈ A. Finally, if A is scale-invariant then so is UAP [A].

Proof It is easy to see that UAP [A] is shift-invariant, conjugation-invariant, closed under scalar multiplication, preserves scale-invariance, and that the UAP [A] norm is non-negative and homogeneous. From (9) and (10) we see that ∥f∥_{L^{∞}} ≤ ∥f∥_{UAP [A]} for all f ∈ UAP [A], from which we deduce that the UAP [A] norm is nondegenerate. Also we easily verify that UAP [A] cotnains A with ∥f∥_{UAP [A]} ≤ ∥f∥_{A} for all f ∈ A. Next, we show that UAP [A] is closed under addition and that the UAP^{d} norm enjoys the triangle inequality. By homogeneity and nondegeneracy it suffices to show that the unit ball is convex, i.e. if F, F′ ∈ UAP [A] are such that ∥F ∥_{UAP [A]}, ∥F′∥_{UAP [A]} < 1 then (1 − θ)F + θF′ ∈ UAP [A] with ∥(1 − θ)F + θF′∥_{UAP [A]} < 1 for all 0 ≤ θ ≤ 1. By Definition 3.2 we can find non-empty finite sets H, H′, bounded functions (g_{h})_{h∈H} and (g′_{h′})_{h′∈H′}, and functions (c_{n,h})_{n∈Z_{N} ,h∈H} and (c′_{n,h′})_{n∈Z_{N} ,h′∈H′} with norm at most 1 in A and random variables h, h′ taking values in H and H′ respectively such that we have the representations

T^{n}F = E(c_{n,h}g_{h}); T^{n}F′ = E(c′_{n,h′}g′_{h′}|h′ ∈ H′) for all n ∈ Z_{N}.

By relabeling H′ if necessary we may assume that H and H′ are disjoint. In such a case we can concatenate (c_{n,h})_{n∈Z_{N} ,h∈H} and (c′_{n,h′})_{n∈Z_{N} ,h′∈H′} to a single function (c̃_{n,h̃})_{n∈Z_{N} ,h̃∈H∪H′} and similarly concatenate the g functions to (g̃_{n,h̃})_{h̃∈H∪H′}. If one then defines the random variable h̃ to equal h with probability (1 − θ) and h′ with probability θ (or more precisely, the probability distribution of h̃ is 1−θ times that of h plus θ times that of h′ then one sees from linearity of expectation that

T^{n}(F + F′) = E(c̃_{n,h̃}g̃h̃) for all n ∈ Z_{N}

and the claim follows. A similar argument (exploiting the hypothesis that A itself is a Banach algebra) shows that that the unit ball of UAP [A] is closed under multiplication.

Thanks to this proposition, we can define the UAP^{d} norms recursively for d ≥ 0, by setting UAP^{0} to be the trivial Banach algebra of all constant functions (equipped with the L^{∞} norm), and then setting UAP^{d} := UAP [AP^{d−1}] for all d ≥ 1. Thus UAP^{d} is a shift-invariant, scale-invariant Banach algebra for all d ≥ 0.

The following lemma is the key to Theorem 1.4.

Lemma 3.4 (Lack of Gowers-uniformity implies correlation with an AP function). Let f be a bounded function such that ∥f∥_{U^{k−1}} ≥ ε for some k − 1 ≥ 0 and ε > 0. Then there exists a bounded function F ∈ UAP^{k−2} with ∥F ∥_{UAP^{k−2}} ≤ 1 such that |⟨f, F ⟩| ≥ ε^{2^{k−1}}.

Proof We need the concept of a dual function from [2], [4]. For any function f : Z_{N} → R and any d ≥ 0, we recursively define the dual function of order d of f, denoted D_{d}(f), by setting D_{0}(f) := 1 and D_{d}(f) := E(D_{d−1}(fT^{h}f)T^{h}f|h ∈ Z_{N}) for all d ≥ 1. By induction one verifies the identity ⟨f, D_{d}(f)⟩ = ∥f∥_{U^{d}}^{2^{d}}. We thus set F := D_{k−1}(f). It is clear from induction that F is bounded; it remains to show that F has UAP^{k−2} norm less than 1. Indeed, we make the more general claim that

∥D_{d}(f)∥_{UAP^{d−1}} ≤ 1 for all bounded f and all d ≥ 1.

When d = 1 this is clear since D_{d}(f) is just the constant function E(f) in this case. Now suppose inductively that d ≥ 2 and the claim has already been proven for d − 1. Applying T^{n} to the definition of D_{d}(f) and making the change of variables h ← n + h we obtain

T^{n}D_{d}(f) := E(c_{n,h}g_{h}|h ∈ Z_{N}), where c_{n,h} := T^{n}D_{d−1}(fT^{h−n}f) and g_{h} := T^{h}f.

The functions g_{h} are clearly bounded. Since UAP^{d−2} is a shift-invariant Banach algebra, we see from inductive hypothesis that the functions c_{n,h} lie in UAP^{d−2} with norm at most 1, and the claim follows (thinking of h as an element of Z_{N} chosen uniformly at random).

4. σ-algebras of almost periodic functions

To prove both the recurrence theorem (Theorem 1.3) or the structure theorem (Theorem 1.4) it is convenient not just to work with almost periodic functions, but also with certain σ-algebras generated by them (in analogy with the ergodic theory arguments). Thus in this section we develop the theory of such σ-algebras.

Definition 4.1 (σ-algebras). Given any partition of Z_{N} into non-empty sets (or atoms), we can form the associated σ-algebra B to be the collection of arbitrary unions of these atoms (including the empty union ∅). If f : Z_{N} → R, we define the conditional expectation E(f|B) : Z_{N} → R by the formula

E(f|B)(x) := E(f(y)|y ∈ B(x)) for all x ∈ Z_{N},

where B(x) is the unique atom in B which contains x. We observe that E(f|B) is measurable in B, i.e. E(f|B) is constant on each of the atoms. If B, B′ are two σ-algebras, we use B ∨ B′ to denote the σ-algebra generated by B and B′ (i.e. the σ-algebra whose atoms are the intersections of atoms in B with atoms in B′).

We now show that each almost periodic function generates a well-behaved σ-algebra at every scale ε.

Proposition 4.2 (AP functions generate a compact σ-algebra). Let A be a Banach algebra, let G ∈ A be such that ∥G∥_{A} ≤ M for some M > 0, and let ε > 0. Then there exists a σ-algebra B_{ε}(G) = B_{ε}(G, A) consisting of at most O_{M,ε}(1) atoms, such that we have the following two properties:

• (G lies in its own σ-algebra) We have the approximation property

∥G − E(G|B_{ε}(G))∥_{L^{∞}} = O(ε).  (11)

Similarly if B_{ε}(G) is replaced by any finer σ-algebra.

• (Approximation by almost periodic functions) For any bounded non-negative function f which is measurable in B_{ε}(G), and any δ > 0, there exists a bounded non-negative function f_{UAP} ∈ UAP^{d} such that

∥f − f_{UAP} ∥_{L^{2}} ≤ δ; ∥f_{UAP} ∥_{UAP^{d}} = O_{M,ε,δ}(1).  (12)

Proof We shall prove this by constructing B_{ε}(G) using randomized level sets (or “generalized Bohr sets” of G), using some ideas from [2]. Let α ∈ S be a real number chosen uniformly at random from the unit interval [0, 1). We can then define the σ-algebra B_{ε,α}(G) to be the algebra whose atoms are the sets {G^{−1}([ε(n+α), ε(n+ 1 + α))) : n ∈ Z}. It will suffice to show that with positive probability this algebra B_{ε,α}(G) is a candidate for B_{ε}(G) (with the bounds in (11), (??) uniform in α).

The bound (11) is clear since G is constrained to lie in a square of diameter O(ε) on each atom of B_{ε} (and hence on each atom of any finer σ-algebra). Since ∥G∥_{L^{∞}} ≤ ∥G∥_{A} ≤ M, G takes values in a ball of radius O(M), and thus the number of atoms in B_{ε} is indeed O_{M,ε}(1) as claimed. Now we turn to the approximation property. It will suffice to prove that for each δ > 0 and every η > 0, the approximation property is true (with the bound in (??) allowed to depend on η) with probability at least 1 − O(η), since one can then set δ := 2^{−n} and η := δ/2 for n = 1, 2, … (for instance) and conclude the claim is true for all δ with positive probability.

Now fix δ, η. Since every bounded non-negative functions f is a convex combination of indicator functions of the form 1_{Ω} where Ω ∈ B_{ε,α}(G), and the number of such functions is O_{M,ε}(1) (since B_{ε,α}(G) only O_{M,ε}(1) atoms), it suffices (after shrinking η appropriately) to prove the claim for a single indicator function f := 1_{Ω}.

Fix Ω; we can then write f = 1_{Ω} = 1_{W} (ε^{−1}G − α) where W ⊂ R is some union of O_{X}(1) translates of the unit interval [0, 1).

Let 0 < σ ≪ 1 be a small number (it will eventually be much smaller than δ, η, or ε) to be chosen later. Let ∂W_{σ} be the σ-neighbourhood of the boundary ∂W of W. By Urysohn’s lemma combined with the Weierstrass approximation theorem (and the fact that G = O(M)) we can write

f = P (εG − α) + O(σ) + O(1)1_{∂W_{σ}}(ε^{−1}G − α)  (13)

for some polynomial P = P_{W,M,ε,σ}. Denote the first term on the right-hand side of (13) by f_{UAP}, then from UAP^{d} hypothesis on G and the Banach algebra nature of UAP^{d} we have

∥f_{UAP} ∥_{UAP^{d}} = O_{M,P} (1) = O_{M,ε,σ}(1).  (14)

Now consider the third term on the right-hand side of (13). Observe that

E(∥1_{∂W_{σ}}(εG − α)∥_{L^{2}}^{2}) = E(P(ε^{−1}G(x) − α ∈ ∂W_{σ})|x ∈ Z_{N})
≤ E(P(dist(ε^{−1}G(x) − α, Z) ≤ σ)|x ∈ Z_{N})
= E(2σ|x ∈ Z_{N})
= 2σ.

By Markov’s inequality and (13) we thus obtain ∥f − f_{UAP} ∥_{L^{2}} = O(σ) + O_{η}(σ^{1/2}) with probability at least 1 − η, and the claim (12) follows by setting σ sufficiently small depending on δ (and using (14)).

Henceforth we shall fix an assignment of a σ-algebra B_{ε}(G) = B_{ε}(G, d) with the above properties for each almost periodic function G ∈ UAP^{d} and each ε > 0. Note that while we did use a randomization argument here, it is possible to make such an assignment constructive, for instance by well-ordering all the σ-algebras of Z_{N} in some constructive way and then choosing the minimal algebra which obeys the above properties (with the exact choice of bounds in (??), etc. held fixed). Thus we do not require the axiom of choice at this step (or indeed at any step in this argument). For similar reasons we may ensure that this procedure is shift-invariant, in the sense that

T^{n}B_{ε}(G) = B_{ε}(T^{n}G) for all n ∈ Z_{N},  (15)

where T^{n}B := {T^{n}Ω : Ω ∈ B} is the σ-algebra B shifted backwards by n. This shift invariance amounts to making sure the same α is chosen for all the shifts T^{n}G of a fixed function G, which is easy enough to ensure since the constraints needed for α are independent of the choice of n.

The above Proposition pertained to a σ-algebra generated by a single almost periodic function, but we can easily extend it to algebras generated by multiple functions as follows.

Definition 4.3 (Compact σ-algebras). Let d ≥ 0 and X ≥ 0. A σ-algebra B is said to be compact of order d and complexity at most X if it has the form

B = B_{ε_{1}}(G_{1}) ∨ … ∨ B_{ε_{K}} (G_{K})  (16)

for some 0 ≤ K ≤ X, some ε_{1}, …, ε_{K} ≥ \frac{1}{X+1}, and some G_{1}, …, G_{K} ∈ UAP^{d−1} with norm ∥G_{j}∥_{UAP^{d}} ≤ X for all 1 ≤ j ≤ K. We define the d-complexity (or simply complexity) of a σ-algebra to be the minimal X for which one has the above representation, or ∞ if no such represenation exists. In particular, the trivial σalgebra B = {∅, Z_{N}} is compact of order d with complexity 0.

Proposition 4.4 (AP functions are dense in compact σ-algebras). Let d ≥ 0, X ≥ 0, and let B be a σ-algebra which is compact of order d and complexity at most X. Let f be a bounded non-negative function which is measurable with respect to B, and let δ > 0. Then we can find a bounded non-negative f_{UAP} ∈ UAP^{d} such that

∥f − f_{UAP} ∥_{L^{2}} ≤ δ; ∥f_{UAP} ∥_{UAP^{d}} = O_{d,δ,X}(1).  (17)

Proof We first verify the claim when f is the indicator function 1_{A} of an atom A of B. From Definition 4.3 we can expand B in the form (16), and hence we can write A = A_{1} ∩ … ∩ A_{K} where each A_{j} is an atom in B_{ε_{j}}(G_{j}). From Proposition 4.2 and the bounds on ε_{j}, G_{j}, K coming from Definition 4.3, we can find bounded non-negative functions f_{UAP,j} ∈ UAP^{d} for all 1 ≤ j ≤ K such that

∥1_{A_{j}} − f_{UAP,j}∥_{L^{2}} ≤ δ/K; ∥f_{UAP,j}∥_{L^{2}} = O_{d,δ/K,ε_{j},X}(1) = O_{d,δ,X}(1).

Since 1_{A_{j}} and f_{UAP,j} are both bounded and non-negative we have the elementary pointwise inequality

| ∏_{j=1}^{K} 1_{A_{j}} − ∏_{j=1}^{K} f_{UAP,j}| ≤ ∑_{j=1}^{K} |1_{A_{j}} − f_{UAP,j}|

and hence if we set f_{UAP} := ∏_{j=1}^{K} f_{UAP,j} then (17) follows from the triangle inequality and the Banach algebra nature of UAP^{d}. Since f_{UAP} is clearly bounded and non-negative, the claim follows.

Now suppose f is an arbitrary bounded non-negative function measurable with respect to B. Then we can write f = ∑_{A} c_{A}1_{A} where A ranges over the atoms of B and 0 ≤ c_{A} ≤ 1 are constants. Let σ = σ(d, δ, X) > 0 be a small number to be chosen later, then by the preceding discussion we can find bounded non-negative f_{UAP,A} ∈ UAP^{d} for all A such that

∥1_{A} − f_{UAP,A}∥_{L^{2}} ≤ σ; ∥f_{UAP,A}∥_{UAP^{d}} = O_{d,X,σ}(1).

If we then set f̃_{UAP} := ∑_{A} c_{A}f_{UAP,A} and observe from Proposition 4.2 that B contains at most O_{d,X}(1) atoms, we thus have

∥f − f̃_{UAP} ∥_{L^{2}} ≤ O_{d,X}(σ); ∥f̃_{UAP} ∥_{UAP^{d}} = O_{d,X,σ}(1).

We are however not done yet, because while f_{UAP} is non-negative, it is not bounded by 1; instead we have a bound of the form 0 ≤ f_{UAP} (x) ≤ O_{d,X}(1). To fix this we need a real-valued polynomial P (x) = P_{d,δ,X}(x) such that

|P (x) − max(x, 1)| ≤ δ/2 and 0 ≤ P (x) ≤ 1 for all x in the range of f_{UAP};

such a polyomial exists by the Weierstrass approximation theorem. If we then set f_{UAP} := P (f̃_{UAP}), then f_{UAP} is bounded and non-negative, and we have

∥f_{UAP} − max(f̃_{UAP} , 1)∥_{L^{2}} ≤ δ/2l ∥f_{UAP} ∥_{UAP^{d}} = O_{d,δ,X,σ}(1)

since UAP^{d} is a Banach algebra. On the other hand, since f is bounded above by 1, we have

∥f − max(f̃_{UAP} , 1)∥_{L^{2}} ≤ ∥f − f̃_{UAP} ∥_{L^{2}} ≤ O_{d,X}(σ),

and the claims then follow from the triangle inequality if σ is chosen sufficiently small depending on d, δ, X.

5. The energy incrementation argument

We now give a useful abstract induction on σ-algebra argument which is used to prove both Theorem 1.3 and Theorem 1.4.

Definition 5.1 (Energy). Given a m-tuple f = (f_{1}, …, f_{m}) of functions f_{j} : Z_{N} → R of functions and a σ-algebra B, we define the energy E_{f}(B) to be the quantity

E_{f}(B) := ∑_{j=1}^{m} ∥E(f_{j}|B)∥_{L^{2}}^{2}.  (18)

From Pythagoras’s theorem we observe that if B′ is finer than B, then E_{f}(B′) ≥ E_{f}(B′), and more precisely

∑_{j=1}^{m} ∥E(f_{j}|B′) − E(f_{j}|B)∥_{L^{2}}^{2} = E_{f}(B′) − E_{f}(B).  (19)

Lemma 5.2 (Abstract energy incrementation argument). Suppose there is a property P (M) which can depend on some parameter M > 0. Let d ≥ 0, and let f = (f_{1}, …, f_{m}) be a collection of m bounded functions.

Suppose also that we have an τ > 0 for which the following dichotomy holds: for any X, X′ > 0, and given any σ-algebra B which is compact of order d with complexity at most X, and any σ-algebra B′ which is finer than B and also compact of order d with complexity at most X′, then if the energy gap condition

E_{f}(B′) − E_{f}(B) ≤ τ^{2},  (20)

holds, then either P (M) is true for some M = O_{d,τ,X,X′}(1), or we can find a σ-algebra B′′ finer than B′ which is compact of order d with complexity at most O_{d,τ,X,X′}(1) such that we have the energy increment property

E_{f}(B′′) − E_{f}(B′) ≥ c(d, τ, X) > 0  (21)

for some positive quantity c(d, τ, X) > 0 which does not depend on X′. Then P (M) is true for some M = O_{m,d,τ} (1).

Remark 5.3. The point of this lemma is that it reduces the task of proving some property P (M), to the easier task of proving a dichotomy; either P can be proven, or we can increment the energy of a certain σ-algebra while keeping the complexity under control. It is crucial that τ does not depend on the complexities X, X′, and that the energy increment c(d, τ, X) depends only on the lower complexity X and not the higher complexity X′, otherwise this lemma fails.

Proof The proof proceeds by running the following double iteration algorithm, constructing a pair of σ-algebras B and B′, both compact of order d and with B′ finer than B, as follows.

Step 1 Initialize B to the trivial algebra B := {∅, Z_{N}}. Step 2 Initialize B′ to equal B (thus trivially verifying the energy gap condition

(20)). Let X denote the complexity of B. Step 3 Let X′ denote the complexity of B′. If P (M) is true for some M =

O_{d,τ,X,X′}(1) then we halt the algorithm. Otherwise, we must by hypothesis be able to locate a σ-algebra B′′ which is compact of order d with complexity at most O_{d,τ,X,X′}(1) with the energy increment property (21), and we continue on to Step 4.

Step 4 If E_{f}(B′′) − E_{f}(B) ≤ τ^{2}, then we replace B′ by B′′ (thus preserving (20)) and return to Step 3. Otherwise, we replace B by B′′ and return to Step 2.

Note that every time B′ is changed, the energy E_{f}(B′) increases by at least c(d, τ, X). Thus the algorithm can only iterate for at most O_{d,τ,X}(1) times before changing B. Since E_{f}(B) is trivially bounded by m, we see that B can only change at most O_{m,τ} (1) times. Combining these two observations we see that the entire algorithm must halt in O_{m,d,τ} (1) steps and all σ-algebras constructed by the algorithm have complexity at most O_{m,d,τ} (1). The claim follows.

6. Proof of the structure theorem

We now prove the structure theorem, Theorem 1.4. In view of the energy incrementation argument, it suffices to prove the following dichotomy:

Lemma 6.1 (Structure theorem dichotomy). Let k ≥ 3, and let f be a non-negative bounded function obeying (1) for some δ > 0. Let B ⊂ B′ be σ-algebras which are compact of order k − 2 with complexity at most X, X′ respectively, and and obey the energy gap condition (20) with τ := \frac{δ^{2}}{5000k}. Then at least one of the following must be true:

• (Success) We can find a positive number M = O_{k,δ,X}(1) a bounded function f_{U}, and non-negative bounded functions f_{U^{⊥}}, f_{UAP} such that we have the splitting f = f_{U} + f_{U^{⊥}} and the estimates (3), (4), (5) with d := k − 2, as well as the Gowers uniformity estimate (7).

• (Energy increment) We can find a σ-algebra B′′ finer than B′ which is compact of order d and complexity O_{k,δ,X,X′}(1) such that

E_{f}(B′′) − E_{f}(B′) ≥ c(k, δ, X) > 0  (22)

for some c(k, δ, X) > 0 independent of X′.

Indeed, Theorem 1.4 follows immediately by applying Lemma 6.1 to Lemma 5.2 (using m = 1 and using the bounded function f, and τ := \frac{δ^{2}}{5000k}).

Proof [of Lemma 6.1] Fix B, B′. Since E(f|B) is non-negative and bounded, and B is compact of order k − 2 with complexity O(X), We may apply Proposition 4.4 to find a non-negative bounded function f_{UAP} such that

∥E(f|B) − f_{UAP} ∥_{L^{2}} ≤ \frac{δ^{2}}{5000k}; ∥f_{UAP} ∥_{UAP^{k−2}} < M  (23)

for some M = O_{k,δ,X}(1), which we now fix. From (23) and Cauchy-Schwarz we observe that

|E(f|Z_{N}) − E(f_{UAP} |Z_{N})| = |E(E(f|B) − f_{UAP} |Z_{N})| ≤ \frac{δ^{2}}{5000k}

and in particular (by (1))

E(f_{UAP} |Z_{N}) ≥ δ/2.

Now split f = f_{U} + f_{U^{⊥}}, where f_{U^{⊥}} := E(f|B′) and f_{U} := f − E(f|B′). We have already proven the estimates (4), (5), while (3) follows from (20) (recall τ = \frac{δ^{2}}{5000k}), (19), (23), and the triangle inequality. If the estimate (7) held then we would now be done (in the “Success” half of the dichotomy), so suppose instead that (7) failed. By Lemma 3.4, we can thus find a function G with bounded UAP^{d−2} norm

|⟨f_{U}, G⟩| > c(k, δ, M) > 0  (24)

for some positive quantity c(k, δ, M). Now write B′′ := B′ ∨ B_{ε}(G), where ε = ε(k, δ, M) > 0 is to be chosen later. Observe the identity

⟨f_{U}, G⟩ = ⟨f − E(f|B′′), G − E(G|B′′)⟩ + ⟨E(f|B′′) − E(f|B′), E(G|B′′) − E(G|B′)⟩.

From (11) and the boundedness of f the first term on the RHS is O(ε). Thus if we choose ε sufficiently small depending on k, δ, M, we see from (24) that

|⟨E(f|B′) − E(f|B), E(G|B′) − E(G|B)⟩| ≥ \frac{1}{2}c(k, δ, M).

Since G is bounded, we thus see from Cauchy-Schwarz that

∥E(f|B′) − E(f|B)∥_{L^{2}} ≥ \frac{1}{4}c(k, δ, M) > 0.

But then (22) follows from (19). Finally, the complexity bound on B′′ follows from Definition 4.3, the complexity bound on B, and the choice of ε and M. We are thus in the “Energy increment” half of the dichotomy, and the lemma follows.

The proof of the structure theorem is now complete.

7. Compactness on atoms, and an application of van der Waerden’s theorem

To prove Szemerédi’s theorem, the only thing that now remains is to prove the recurrence theorem for almost periodic functions, Theorem 1.3. In this section we present a key Proposition used in that theorem.

Proposition 7.1 (Recurrence for conditionally almost periodic functions). Let B be a σ-algebra, let M > 0, let H be a finite non-empty set, and let for each n ∈ Z_{N} and h ∈ H let c_{n,h} be a bounded B-measurable function and let g_{h} be a bounded function. Let h be a random variable taking values in H, and define the functions F_{n} for all n ∈ Z_{N} by the formula

F_{n} := ME(c_{n,h}g_{h})  (25)

(compare with (10)). Let f_{U^{⊥}} be a bounded non-negative function, and for any δ > 0, λ ∈ Z_{N}, and k, k_{∗} ∈ Z_{+} let E_{λ}(k, δ, k_{∗}, B) ∈ B be the set

E_{λ}(k, δ, k_{∗}, B) := \{x ∈ Z_{N} : E(T^{λm}f_{U^{⊥}}|B)(x) ≥ δ/2 and E(|T^{λm}f_{U^{⊥}} − F_{λm}||B)(x) ≤ \frac{δ}{8k} for all 1 ≤ m ≤ k_{∗}\}.

(26)

Then for every δ > 0 and k ∈ Z_{+} there exists k_{∗} = k_{∗}(k, δ, M) such that

E(∏_{j=0}^{k−1} T^{μjr}f_{U^{⊥}}(x)|x ∈ Z_{N}, 1 ≤ r ≤ N_{0}) ≥ c(k, δ, M)E(P(E_{μλ}(k, δ, k_{∗}, B)|Z_{N})|1 ≤ λ ≤ N_{0}/k_{∗}) (27)

for all μ ∈ Z_{N} and N_{0} ≥ k_{∗}, and some c(k, δ) > 0.

Proof To prove (27) it suffices to prove the “localized” version

E(∏_{j=0}^{k−1} T^{μλ(a+js)}f_{U^{⊥}}(x)|x ∈ Z_{N}; 1 ≤ a, s ≤ k_{∗}/k) ≥ c(δ, k, k_{∗})P(E_{μλ}(k, δ, k_{∗}, B)|Z_{N}) (28)

for each 1 ≤ λ ≤ N_{0}/k_{∗}. Indeed, if (28) held then upon averaging in λ we obtain

E(E(∏_{j=0}^{k−1} T^{μλ(a+js)}f_{U^{⊥}}|Z_{N})|1 ≤ λ ≤ N_{0}/k_{∗}; 1 ≤ a, s ≤ k_{∗}/k) ≥ c(δ, k, k_{∗})E(P(E_{μλ}(k, δ, k_{∗}, B)|Z_{N})|1 ≤ λ ≤ N_{0}/k_{∗}).

The T^{μλa} can be factored out of the product and makes no difference to the expectation, thus it can be discarded. The a averaging then becomes redundant, and we obtain

E(E(∏_{j=0}^{k−1} T^{μλjs}f_{U^{⊥}}|Z_{N})|1 ≤ λ ≤ N_{0}/k_{∗}; 1 ≤ s ≤ k_{∗}/k) ≥ c(δ, k, k_{∗})E(P(E_{μλ}(k, δ, k_{∗}, B)|Z_{N})|1 ≤ λ ≤ N_{0}/k_{∗}).

The claim (27) then follows by observing that every 1 ≤ r ≤ N_{0} has at most O_{k_{∗},k}(1) representations of the form r = λ(a + js) with 1 ≤ λ ≤ N_{0}/k_{∗} and 1 ≤ a, s ≤ k_{∗}/k. (The dependence of k_{∗} is ultimately irrelevant since k_{∗} itself will ultimately depend on δ, k, M).

It remains to prove (28). Fix μ, λ. By absorbing μ into λ we may take μ = 1 (we will not use the upper or lower bound on λ). Since E_{λ}(k, δ, k_{∗}, B) is measurable in B, it is the union of atoms A ∈ B. It will suffice to prove the pointwise estimate

E(E(∏_{j=0}^{k−1} T^{λ(a+js)}f_{U^{⊥}}|A)|1 ≤ a, s ≤ k_{∗}/k) ≥ c(δ, k, k_{∗})

for each such atom, as the claim then follows by multiplying this formula by P(A|Z_{N}) and summing over all atoms in E_{λ}(k, δ, k_{∗}, B).

Now fix the atom A. Since the number of pairs (a, s) is O_{k,k_{∗}}(1), it suffices to locate a single pair (a, s) with 1 ≤ a, s ≤ k_{∗}/k such that

E(∏_{j=0}^{k−1} T^{λ(a+js)}f_{U^{⊥}}|A) ≥ c(δ, k)  (29)

for some c(δ, k) > 0.

We now pass from the shifts T^{λ(a+js)}f_{U^{⊥}} to the functions F_{λ(a+js)}. We claim that to prove (29) it would suffice to prove that

∥F_{λ(a+js)} − F_{λa}∥_{L^{2}(A)} ≤ \frac{δ}{8k} for all 0 ≤ j ≤ k − 1,  (30)

where L^{2}(A) is the Hilbert space given by the norm ∥F ∥_{L^{2}(A)} := E(|F |^{2}|A)^{1/2}. To see this claim, observe from Cauchy-Schwarz that (30) implies

E(|F_{λ(a+js)} − F_{λa}||A) ≤ \frac{δ}{8k} for all 0 ≤ j ≤ k − 1.

But from definition of E_{λ}(k, δ, k_{∗}, B), which contains the atom A, we also have

E(|F_{λ(a+js)} − T^{λ(a+js)}f_{U^{⊥}}||A) ≤ \frac{δ}{8k} for all 0 ≤ j ≤ k − 1.

From the triangle inequality we thus have

E(|T^{λ(a+js)}f − T^{λa}f_{U^{⊥}}||A) ≤ \frac{3δ}{8k} for all 0 ≤ j ≤ k − 1.

This in particular implies

E(1_{|T^{λ(a+js)}f_{U^{⊥}} −T^{λa}f_{U^{⊥}} |> \frac{4}{5} T^{λa}f}T^{λa}f) ≤ \frac{15δ}{32k} for all 0 ≤ j ≤ k − 1.

On the other hand, again by definition of E we have

E(T^{λa}f_{U^{⊥}}|A) ≥ δ/2.

Thus

E(1_{|T^{λ(a+js)}f_{U^{⊥}} −T^{λa}f_{U^{⊥}} |≤ \frac{4}{5} T^{λa}f for all 0≤j≤k−1}T^{λa}f_{U^{⊥}}) ≥ \frac{δ}{32k} .

By Hölder’s inequality and the non-negativity of f_{U^{⊥}} this implies that

E(1_{|T^{λ(a+js)}f_{U^{⊥}} −T^{λa}f_{U^{⊥}} |≤ \frac{4}{5} T^{λa}f_{U^{⊥}} for all 0≤j≤k−1}(T^{λa}f_{U^{⊥}})^{k}) ≥ (\frac{δ}{32k})^{k}.

The claim (29) then follows from the elementary pointwise inequality

∏_{j=0}^{k−1} T^{λ(a+js)}f_{U^{⊥}} ≥ \frac{1}{5^{k}} 1_{|T^{λ(a+js)}f_{U^{⊥}} −T^{λa}f_{U^{⊥}} |≤ \frac{4}{5} T^{λa}f_{U^{⊥}} for all 0≤j≤k−1}(T^{λa}f_{U^{⊥}})^{k}.

It remains to find a pair (a, s) obeying (30). Using (25) it suffices to find an (a, s) such that

∥E(c_{λ(a+js),h}g_{h}) − E(c_{λa,h}g_{h})∥_{L^{2}(A)} ≤ δ/8Mk for all 0 ≤ j ≤ k − 1. (31)

Note that as the c_{n,h} are measurable with respect to B, they are constant on A, and so without loss of generality we can treat them just as bounded complex numbers (this is the whole point of working on individual atoms in the first place). The g_{h} are not constant, but we can think of them as bounded functions on A.

To proceed further we need the following compactness property of averages of the form E(c_{h}g_{h}) in L^{2}(A).

Lemma 7.2 (Total boundedness property). There exists integers 1 ≤ m_{1}, …, m_{L} ≤ k_{∗} for some L ≤ C(k, M, δ) such that

inf_{1≤l≤L} ∥E(c_{λm,h}g_{h}) − E(c_{λm_{l},h}g_{h})∥_{L^{2}(A)} ≤ \frac{δ}{16Mk} for all 1 ≤ m ≤ k_{∗}.

Proof Let us write f_{m} := E(c_{m,h}g_{h})|_{A}. Use the greedy algorithm to find a maximal orthonormal system of functions v_{1}, v_{2}, …, v_{J} in L^{2}(A) such that sup_{1≤m≤k_{∗}} |⟨f_{m}, v_{j}⟩_{L^{2}(A)}| ≥ δ/64Mk for all 1 ≤ j ≤ J. Thus for each j there exists an m such that

|E(c_{λm,h}⟨g_{h}, v_{j}⟩_{L^{2}(A)})| = |⟨f_{m}, v_{j}⟩_{L^{2}(A)}| ≥ δ/64Mk.

Here we have crucially taken advantage of the fact that c_{λm,h} is constant on A. Since c_{λm,h} is bounded, we thus see from the Cauchy-Schwarz inequality that

E(|⟨g_{h}, v_{j}⟩_{L^{2}(A)}|^{2}) ≥ (\frac{δ}{64Mk})^{2}.

Summing this in j, we obtain

E(∑_{j=1}^{J} |⟨g_{h}, v_{j}⟩_{L^{2}(A)}|^{2}) ≥ (\frac{δ}{64Mk})^{2}J.

But from the boundedness of the g_{h}, the orthonormality of the v_{j}, and Bessel’s inequality, the left-hand side is at most 1. Thus J ≤ (\frac{64Mk}{δ})^{2} = O_{k,M,δ}(1).

Now observe from the construction of v_{1}, …, v_{J} and Hilbert space geometry that all the functions f_{m} will lie within δ/64Mk (in the L^{2}(A) metric) of the J-dimensional space spanned by the v_{1}, …, v_{j}. In particular, we see from the triangle inequality, the crude bound ∥f_{m}∥_{L^{2}(A)} ≤ 1 arising from our bounds on c_{n,h} and g_{h}, and finitedimensional geometry that there can be at most O_{k,δ,J}(1) = O_{k,M,δ}(1) functions f_{m_{1}}, …, f_{m_{L}} which are all separated from each other by at least δ/16Mk in the L^{2}(A) metric. The claim now follows by another greedy algorithm.

Using this lemma, we can introduce a colouring function c : {1, …, k_{∗}} → {1, …, L} by

c(m) := inf{1 ≤ l ≤ L : ∥E(c_{λm,h}g_{h}) − E(c_{λm_{l},h}g_{h})∥_{L^{2}(A)} ≤ δ/16Mk}.

By van der Waerden’s theorem [8], if k_{∗} = k_{∗}(k, L) = k_{∗}(k, δ, M) is chosen sufficiently large, then we can find 1 ≤ a, s ≤ k_{∗}/k such that the progression a, a + s, …, a + (k − 1)s is monochromatic. The claim (31) now follows from the triangle inequality. This concludes the proof of Proposition 7.1.

As a quick corollary of this Proposition we can now prove the d = 1 case, at least, of Theorem 1.3.

Proof [of Theorem 1.3 when d = 1] Let f_{U^{⊥}}, f_{UAP}, k, M, δ, ϵ be as in the Theorem. From (5) and Definition 3.2 we can find a finite non-empty set H, a collection of bounded constants (c_{n,h})_{n∈Z_{N};h∈H}, and bounded functions (g_{h})_{h∈H}, and a random variable h taking values in H such that we have the representation (25), where F_{n} := T^{n}f_{UAP}. We thus apply Proposition 7.1 with N_{0} := N_{1} and B set equal to the trivial σ-algebra B = {∅, Z_{N}}, since the c_{n,h} are all almost periodic of order 0 and hence constant. But by (26), we see that E_{λ}(k, δ, k_{∗}, B) is either the empty set or all of Z_{N}, with the latter occuring if

E(T^{λm}f_{U^{⊥}}|Z_{N}) ≥ δ/2 and E(|T^{λm}f − F_{λm}||Z_{N}) ≤ \frac{δ}{8k} for all 1 ≤ m ≤ k_{∗}.

But the latter condition is automatic from (4), while the latter follows from (3), Cauchy-Schwarz, and the choice of ϵ; note that the shift T^{λm} has no effect on the expectation E(|Z_{N}). Thus E_{λ}(k, δ, k_{∗}, B) = Z_{N} for all λ, and the claim (6) follows from (27).

8. Recurrence for almost periodic functions

We now conclude the proof of Theorem 1.3. We have already handled the d = 1 case (and hence the d = 0 case), so we may assume inductively that d ≥ 2 and and the claim has already been proven for d − 1. When μ = 0 the claim follows easily from (4) and the boundedness of f_{U^{⊥}}, so we may take μ ≠ 0. But then we may rescale by μ and set μ = 1.

By Lemma 5.2 it will suffice to establish

Proposition 8.1 (Recurrence theorem dichotomy). Let d ≥ 2, and suppose that Theorem 1.3 has already been proven for d − 1. Let k ≥ 1 be integers, and let M, δ > 0. All quantities in what follows can depend on d, δ, k, M (including the implicit bounds in O() notation), and we omit future dependence on these parameters. let f_{U^{⊥}}, f_{UAP} be non-negative bounded functions obeying the bounds (3), (4), (5). Write f := (f_{U^{⊥}}, |f_{U^{⊥}} − f_{UAP} |, |f_{U^{⊥}} − f_{UAP} |^{2}). Let B ⊂ B′ be σ-algebras which are compact of order k − 2 with complexity at most X, X′ respectively, and such that (20) holds for some small τ = τ > 0 independent of X, X′ to be chosen later. Then at least one of the following must be true:

• (Success) For all N_{1} ≥ 0 we have

E(∏_{j=0}^{k−1} T^{jr}f_{U^{⊥}}(x)|x ∈ Z_{N}, 0 ≤ r ≤ N_{1}) ≥ c(τ, X) > 0.  (32)

• (Energy increment) We can find a σ-algebra B′′ finer than B′ which is compact of order d and complexity O_{τ,X,X′}(1) such that

E_{f}(B′′) − E_{f}(B′) ≥ c(τ, X) > 0.  (33)

Proof By (5) and Definition 3.2 we can find a finite non-empty set H, a collection of bounded functions (c_{n,h})_{n∈Z_{N};h∈H} in UAP^{d−1} with ∥c_{n,h}∥_{UAP^{d−1}} ≤ 1, and bounded functions (g_{h})_{h∈H}, and a random variable h taking values in H such that we have the representation

T^{n}f_{UAP} = ME(c_{n,h}g_{h})  (34)

for all n ∈ Z_{N}. We cannot yet apply Proposition 7.1 since the c_{n,h} are not necessarily measurable with respect to B′; indeed there are too many of the c_{n,h} to safely add all of them to B′, which needs to have bounded complexity. Instead, we shall work using much smaller batches of c_{n,h} and then average at the end.

We will need a large integer N_{0} = N_{0}(τ, X) > 1 to be chosen later. If N_{1} ≤ N_{0} then the claim (32) follows easily from (4) just by considering the r = 0 component of the left-hand side, so we will assume N_{1} > N_{0}. We then observe that

E(∏_{j=0}^{k−1} T^{jr}f_{U^{⊥}}(x)|x ∈ Z_{N}; 0 ≤ r ≤ N_{1}) ≥ c(N_{0})E(E(∏_{j=0}^{k−1} T^{μjr}f_{U^{⊥}}(x)|x ∈ Z_{N}, 1 ≤ r ≤ N_{0})|1 ≤ μ ≤ N_{1}/N_{0}) (35)

because each 0 ≤ r ≤ N_{0} has at most O_{N_{0}}(1) representations of the form r = μr′ where 1 ≤ r′ ≤ N_{0} and 1 ≤ μ ≤ N_{1}/N_{0}.

Now fix a single 1 ≤ μ ≤ N_{1}/N_{0}, and consider the expression

E(∏_{j=0}^{k−1} T^{μjr}f_{U^{⊥}}(x)|x ∈ Z_{N}, 1 ≤ r ≤ N_{0}).  (36)

Observe that the exponents μjr now range in the relatively small set μ·{0, …, (k− 1)N_{0}}. This has localized the “n” index in (34) to a reasonably small set (one which is independent of N), but the “h” parameter is still ranging over a potentially unbounded set. To resolve this we need the following variant of Lemma 7.2.

Lemma 8.2 (Finite-rank approximation). Let μ ∈ Z_{N}. Then we can find h_{1}, …, h_{N_{0}^{100}} ∈ H (not necessarily distinct, and depending on μ) such that

∥E(c_{μm,h}g_{h}) − E(c_{μm,h_{j}}g_{h_{j}}|1 ≤ j ≤ D)∥_{L^{2}} ≤ O(N_{0}^{−40})  (37)

for all 0 ≤ m ≤ (k − 1)N_{0}.

Proof We use the second moment method. Set D := N_{0}^{100}, G_{h} := c_{μm,h}g_{h}, F := E(G_{h}), and let h_{1}, …, h_{D} be D independent samples of the random variable h. We will show that

E(∥F − E(G_{h_{j}}|1 ≤ j ≤ D)∥_{L^{2}}^{2}) ≤ 1/D

which will imply the claim with positive probability thanks to Chebyshev’s inequality. The left-hand side can be expanded as

∥F ∥_{L^{2}}^{2}−2E(F (x)E(G_{h_{j}}(x))|1 ≤ j ≤ D; x ∈ Z_{N})+E(E(G_{h_{j′} (x)}G_{h_{j}}(x))|1 ≤ j, j′ ≤ D; x ∈ Z_{N}).

The random variables G_{h_{j}}(x) have expectation F (x) and are pairwise independent, thus we can rewrite this as

∥F ∥_{L^{2}}^{2}−2∥F ∥_{L^{2}}^{2}+∥F ∥_{L^{2}}^{2}+E(δ_{j,j′}(E(G_{h_{j′}} (x)G_{h_{j}}(x))−|F (x)|^{2})|1 ≤ j, j′ ≤ D; x ∈ Z_{N})

where δ_{j,j′} is the Kronecker delta. But when j = j′, we have

E(G_{h_{j′}} (x)G_{h_{j}}(x)) − |F (x)|^{2} = E(|G_{h}(x)|^{2}|h ∈ H) − |E(G_{h}(x)|h ∈ H)|^{2} ≤ 1

and the claim follows.

Let h_{1}, …, h_{N_{0}^{100}} be as in the above Lemma. Then from (37) and (34) we see that

∥T^{μm}f_{UAP} − ME(c_{μm,h_{j}}g_{h_{j}}|1 ≤ j ≤ N_{0}^{100})∥_{L^{2}} ≤ O(N_{0}^{−40}) for all 0 ≤ m ≤ (k − 1)N_{0}. (38)

We have now modeled a reasonably large number of shifts of our almost periodic function f_{UAP} in terms of a controlled number of functions c_{μm,h_{j}}. Next, we define a new σ-algebra B′′ finer than B′ (and depending on μ, h_{1}, …, h_{N_{0}^{100}}) by

B′′ := (  ⋁_{−(k−1)N_{0}≤m≤(k−1)N_{0}} T^{μm}B′) ∨ (  ⋁_{0≤m≤(k−1)N_{0};1≤j≤N_{0}^{100}} B_{N_{0}^{−100}}(c_{μm,h_{j}}))

where B_{ε}(G) are the σ-algebras constructed by Proposition 4.2. Since the c_{μm,h_{j}} are in UAP^{d−1} with norm at most 1, and B′ was compact of order d − 1 and complexity at most X′, we see from (15) and Definition 4.3 that B′′ is also compact of order d − 1 and complexity at most O_{N_{0},X′}(1). Also, from (11) we have

∥c_{μm,h_{j}} − E(c_{μm,h_{j}}|B′′)∥_{L^{∞}} ≤ O(N_{0}^{−100}) for all 0 ≤ m ≤ (k − 1)N_{0}

and hence (since the g_{h_{j}} are bounded)

∥ME(c_{μm,h_{j}}g_{h_{j}}|1 ≤ j ≤ D) − ME(E(c_{μm,h_{j}}|B′′)g_{h_{j}}|1 ≤ j ≤ D)∥_{L^{2}} ≤ O(N_{0}^{−100}).

Combining this with (38) we see that

∥T^{μm}f_{UAP} − F_{μm}∥_{L^{2}} ≤ O_{M}(N_{0}^{−40}) for all 0 ≤ m ≤ (k − 1)N_{0},  (39)

where F_{n} is defined for n ∈ Z_{N} by the formula

F_{n} := ME(E(c_{n,h_{j}}|B′′)g_{h_{j}}|1 ≤ j ≤ D).  (40)

We may then apply Proposition 7.1 (with B replaced by B′′) to estimate the quantity

(36) as

(36) ≥ cE(P(E_{μλ}|Z_{N})|1 ≤ λ ≤ N_{0}/k_{∗})  (41)

where k_{∗} = O(1) and E_{μλ} = E_{μλ}(k, δ, k_{∗}, B′′) was defined in that Proposition; recall that we are suppressing all dependence on the quantities d, k, δ, M.

Our attention thus turns to obtaining lower bounds for the size of E_{μλ}. We first use

(39) to pass from F_{μm} back to T^{μm}f_{UAP} (modulo errors that can be made small by making D large). From (39) and Cauchy-Schwarz we have

E(E(|T^{μm}f_{UAP} −F_{μm}||B′′)|Z_{N}) = E(|T^{μm}f_{UAP} −F_{μm}||Z_{N}) ≤ O(N_{0}^{−40}) for all 0 ≤ m ≤ (k−1)N_{0},

so by Markov’s inequality

P(E(|T^{μm}f_{UAP} − F_{μm}||B′′) ≥ \frac{δ}{16k} |Z_{N}) ≤ O(N_{0}^{−40}) for all 0 ≤ m ≤ (k − 1)N_{0}.

In particular, from (26) and the triangle inequality we see (since k_{∗} = O(1)) that

P(E_{μλ}|Z_{N}) ≥ P(E′_{μλ}|Z_{N}) − O(N_{0}^{−30}),  (42)

where

E′_{μλ} := \{x ∈ Z_{N} : E(T^{μλm}f_{U^{⊥}}|B′′)(x) ≥ δ/2 and E(|T^{μλm}f_{U^{⊥}}−T^{μλm}f_{UAP} ||B′′)(x) ≤ \frac{δ}{16k} for all 1 ≤ m ≤ k_{∗}\}.

The next step is to pull the shifts T^{μλm} out of the B′′ expectations. To do this we use the following observation.

Lemma 8.3 (Effective shift invariance of B′′). Suppose that −(k − 1)N_{0} ≤ m ≤ (k − 1)N_{0} is such that

∥E(T^{μm}f_{U^{⊥}}|B′′) − T^{μm}E(f_{U^{⊥}}|B′′)∥_{L^{2}} ≥ N_{0}^{−100}

or

∥E(T^{μm}|f_{U^{⊥}} − f_{UAP} |^{2}|B′′) − T^{μm}E(|f_{U^{⊥}} − f_{UAP} |^{2}|B′′)∥_{L^{2}} ≥ N_{0}^{−100}.

Then we are in the energy increment half of the dichotomy of Proposition 8.1.

Proof We prove just the first claim, as the second is analogous. Observe that E(T^{μm}f_{U^{⊥}}|B′′) = T^{μm}E(f_{U^{⊥}}|T^{−μm}B′′), and so

∥E(f_{U^{⊥}}|T^{−μm}B′′) − E(f_{U^{⊥}}|B′′)∥_{L^{2}} ≥ N_{0}^{−100}.

By the triangle inequality, we thus have

∥E(f_{U^{⊥}}|B̃) − E(f_{U^{⊥}}|B′)∥_{L^{2}} ≥ \frac{1}{2}N_{0}^{−100}

where B̃ is either B′′ or T^{−μm}. But by construction B̃ finer than B′, and we can use (19) to obtain an energy increment (33), as desired.

In light of this lemma, we may assume that

∥E(T^{n}f_{U^{⊥}}|B′′)−T^{n}E(f_{U^{⊥}}|B′′)∥_{L^{2}}, ∥E(T^{n}|f_{U^{⊥}}−f_{UAP} |^{2}|B′′)−T^{n}E(|f_{U^{⊥}}−f_{UAP} |^{2}|B′′)∥_{L^{2}} ≤ N_{0}^{−100}

QUANTITATIVE ERGODIC PROOF OF SZEMERÉDI’S THEOREM 19

for all n ∈ Z_{N}. In particular we have

P(|E(T^{μm}f_{U^{⊥}}|B′′)(x) − T^{μm}E(f_{U^{⊥}}|B′′)(x)| ≥ δ/4) ≤ O(N_{0}^{−100}) and

P(|E(|T^{μm}f_{U^{⊥}}−T^{μm}f_{UAP} ||B′′)(x)−T^{μm}E(|f_{U^{⊥}}−f_{UAP} ||B′′)(x)| ≥ \frac{δ}{32k}) ≤ O(N_{0}^{−50})

for all 0 ≤ m ≤ (k − 1)N_{0}. This allows us to estimate (since k_{∗} = O(1))

P(E′_{μλ}|Z_{N}) ≥ P(E′′_{μλ}|Z_{N}) − O(N_{0}^{−50}),  (43)

where

E′′_{μλ} := \{x ∈ Z_{N} : T^{μλm}E(f_{U^{⊥}}|B′′)(x) ≥ 3δ/4 and T^{μλm}E(|f_{U^{⊥}}−f_{UAP} ||B′′)(x) ≤ \frac{δ}{32k} for all 1 ≤ m ≤ k_{∗}\}.

Observe that E′′_{μλ} = ⋂_{1≤m≤k_{∗}} T^{μλm}E_{0} where

E_{0} := \{E(f_{U^{⊥}}|B′′) ≥ 3δ/4 and E(|f_{U^{⊥}} − f_{UAP} ||B′′) ≤ \frac{δ}{32k} \}.

Combining this with (43), (42), (41) we obtain

(36) ≥ cE( ∏_{m=1}^{k_{∗}} T^{μλm}1_{E_{0}}(x)|x ∈ Z_{N}; 1 ≤ λ ≤ N_{0}/k_{∗}) − O(N_{0}^{−30}).  (44)

We now pass from E_{0} to the slightly modified set E_{0} ∩ E_{1}, where

E_{1} := \{E(f_{U^{⊥}}|B) ≥ 7δ/8 and E(|f_{U^{⊥}} − f_{UAP} ||B) ≤ \frac{δ}{64k} \}.

Lemma 8.4. Either we have

P(E_{1}\E_{0}) ≤ O(τ^{2}); P(E_{0} ∩ E_{1}) ≥ δ/32

or we are in the energy increment half of the dichotomy. Proof We may assume without loss of generality that E_{f}(B′′) − E_{f}(B′) ≤ τ^{2} since otherwise we would be in the energy increment half of the dichotomy. From (20),

(19) and the definition of f we thus have E(|E(f_{U^{⊥}}|B′′) − E(f_{U^{⊥}}|B′)|^{2}|Z_{N}) ≤ 2τ^{2}

and

E(|E(|f_{U^{⊥}} − f_{UAP} ||B′′) − E(|f_{U^{⊥}} − f_{UAP} ||B′)|^{2}|Z_{N}) ≤ 2τ^{2}

In particular by Chebyshev’s inequality we have

P(|E(f_{U^{⊥}}|B′′) − E(f_{U^{⊥}}|B′)| ≥ \frac{δ}{8}) ≤ O(τ^{2})

and

P(|E(|f_{U^{⊥}} − f_{UAP} ||B′′) − E(|f_{U^{⊥}} − f_{UAP} ||B′)| ≥ \frac{δ}{64k} |Z_{N}) ≤ O(τ^{2})

and the first claim follows from the definitions of E_{0} and E_{1}. Now we prove the second claim. From (4) we have

E(E(f_{U^{⊥}}|B)|Z_{N}) = E(f_{U^{⊥}}|Z_{N}) ≥ δ

and hence (by the boundedness of E(f_{U^{⊥}}|B′′))

P(E(f_{U^{⊥}}|B) ≥ 7δ/8|Z_{N}) ≥ δ/8 while from (3) and Cauchy-Schwarz we have

E(E(|f_{U^{⊥}} − f_{UAP} ||B′′)|Z_{N}) = E(|f_{U^{⊥}} − f_{UAP} ||Z_{N}) ≤ ∥f_{U^{⊥}} − f_{UAP} ∥_{L^{2}} ≤ \frac{δ^{2}}{1024k}

and hence by Chebyshev’s inequality

P(E(|f_{U^{⊥}} − f_{UAP} ||B′′) > \frac{δ}{64k} |Z_{N}) ≤ δ/16.

By definition of E_{0}, we thus have P(E_{0}|Z_{N}) ≥ δ/16, and the second claim of the lemma thus follows from the first if τ is chosen sufficiently small.

We may of course assume that we are not in the energy increment half of the dichotomy, in which case Lemma 8.4 implies that ∥1_{E_{0}∩E_{1}} − 1_{E_{1}}∥_{L^{2}} = O(τ). Since E_{1} ∈ B and B is compact of order d − 1 and complexity at most X, we can apply Proposition 4.4 to find a bounded nonnegative function f̃_{UAP} ∈ UAP^{d−1} with

∥1_{E_{1}} − f̃_{UAP} ∥_{L^{2}} = O(τ); ∥f̃_{UAP} ∥_{UAP^{d−1}} ≤ O_{X,τ} (1).

By Lemma 8.4 we can apply the induction hypothesis with f_{U^{⊥}} replaced by 1_{E_{0}∩E_{1}}, (if τ is sufficiently small), to obtain

E( ∏_{m=1}^{k_{∗}} T^{μλm}1_{E_{0}}(x)|x ∈ Z_{N}; 1 ≤ λ ≤ N_{0}/k_{∗}) ≥ c(τ, X)

and so if we choose N_{0} sufficiently large depending on τ, X, we see from (44) that (36) ≥ c(τ, X). The claim (32) now follows from (35), and the proof of the Proposition is complete.

The proof of Szemerédi’s theorem is now complete.

References

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

[2] B.J. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, preprint.

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

[4] B. Host, B. Kra, Non-conventional ergodic averages and nilmanifolds, to appear in Ann. Math.

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

[6] E. Szemerédi, Regular partitions of graphs, in “Proc. Colloque Inter. CNRS” (J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau, eds.) (1978), 399–401.

[7] T. Tao, A quantitative ergodic theory proof of Szemerédi’s theorem, preprint.

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

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

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

E-mail address: tao@math.ucla.edu
URL: http://www.math.ucla.edu/∼tao