GOWERS’ PROOF OF THE SZEMERÉDI THEOREM ON ARITHMETIC PROGRESSIONS OF LENGTH 4

TERENCE TAO

Abstract. I describe Gowers’s [4] recent proof of Szemerédi’s theorem on arithmetic progressions of length 4. This note arose out of discussions with Nets Katz.

1. Notation

Here and in the sequel, C will denote various large absolute constants, and c denotes various small absolute constants. N will be a large integer, and 0 < δ < 1 will be a parameter. We let ε = ε(δ) > 0 be a quantity depending continuously on δ to be chosen later.

[a, b] denotes the integers from a to b inclusive. Similarly define [a, b), etc. If E is a set, |E| denotes the cardinality of E.

We let Z_{N} denote the cyclic group of order N, which we identify with [0, N). Let M = M(N) be a slowly growing function of N to be chosen later such that

ε^{−C} ≪ M ≪ N^{c}; one could take for instance M = log(N), although one can get away with a much larger M actually. The exact choice of M is only important if one is interested in the dependence of N on δ).

For any function f on Z_{N}, define the Fourier transform f̂ by

f̂(n) := ∑_{m∈Z_{N}} f(m) exp(2πimn/N)

and define the Wiener norm ∥f∥_{A^{∞}} by

∥f∥_{A^{∞}} := ∥f̂∥_{l^{∞}(Z_{N})}.

We also define the modified A^{∞} norm ∥f∥Ȧ^{∞} by

∥f∥Ȧ^{∞} := ∥f̂∥_{l^{∞}(Z_{N} −{0})}.

These norms measure a certain uniformity of distribution, as should become clear in Section 4.

We use the notation o(X) to denote a quantity whose ratio with X tends to zero as ε → 0. We write Y ⪆ X if Y is not of the form o(X).

2. Introduction

A famous theorem of Szemerédi asserts that for any integer k, if N is sufficiently large depending on δ and k, then every set E ⊂ [0, N) with |E| ≥ δN must contain a non-trivial arithmetic progression of length k.

Recently Gowers [4] has given an elementary proof of this theorem in the case k = 4, in the spirit of an earlier argument of Roth in the k = 3 case. (The argument has also been extended to higher k). The purpose of this note is to give a short informal outline of the proof in [4].

1991 Mathematics Subject Classification. 42B15, 35L05.

I have decided to run Gowers’ argument in the contrapositive, so our steps are in the reverse order, and in the negative, of those in [4] (with the exception of Section 6). This may give a slightly different perspective on the arguments; it makes certain notations simpler, but it becomes a bit more difficult to uncover the exact dependence of N on δ this way.

For technical reasons we shall take N to be prime, although this does not make too much difference.

The proof proceeds by induction on δ. If 0.99 < δ < 1 the claim is easy to prove (in fact, any randomly chosen arithmetic progression in (0, N] of length 4 will have probability at least 0.96 of being completely contained in E).

Now suppose δ < 0.99. We shall assume that Szemerédi’s theorem has already been proven for δ+ε(δ), and show that this implies the theorem for δ. An induction argument then yields the whole result (to see this, consider the infimum of all δ for which Szemerédi’s theorem holds, and observe that this infimum must be zero or else a contradiction can be obtained).

Fix δ, let N be a prime which is sufficiently large depending on δ and ε, and let E ⊂ [0, N) be such that |E| ≥ δN. By refining E if necessary we may assume that

|E| = δN.  (1)

(Of course this requires δN to be an integer, but we ignore this technicality). We can assume that

|E ∩ P | ≤ (δ + 2ε)|P |  (2)

for all arithmetic progressions P ⊂ [0, N) of length at least M. This is because if E ∩ P had density > δ + 2ε on P, then one could rescale P to be an interval of length at least M. One can then apply the induction hypothesis to obtain the result (rounding to the nearest prime). This is the only place in the argument where we shall use the induction hypothesis.

Henceforth we shall now think of E as a subset of the abelian group Z_{N} rather than the interval [0, N). We then need to make a technical distinction between a genuine arithmetic progression and a Z_{N} arithmetic progression.

The condition (2), combined with (1), implies that E is extremely uniformly distributed. Following the general philosophy of Roth, we now try to leverage this uniformity into some sort of statement about lack of bias with respect to various phases. For instance, we shall be able to show the uniformity estimate

∥χ_{E}∥Ȧ^{∞} = o(N).  (3)

This statement may be viewed as saying that χ_{E} is unbiased with respect to linear phase functions exp(2πimn/N). This can in fact be generalized to quadratic phase functions; indeed, we shall be able to prove the much stronger estimate

∑_{s∈Z_{N}} | ∑_{j∈E∩(P_{0}+s)} exp(2πiϕ_{s}(j)/N)| = o(N|P_{0}|)  (4)

for any Z_{N} arithmetic progression P_{0} of length |P_{0}| ≫ M^{C} and any non-constant quadratic functions ϕ_{0}, …, ϕ_{N−1} with integer co-efficients. (Note that when ϕ_{s} is linear, independent of s and the absolute vales are dropped, (4) collapses back into (3)). We shall derive (4) from (2), (1) in Section 3.

The estimate (4) is a very strong statement about the total lack of linear and quadratic bias for E. The next step is to convert this into a lack of linear bias for intersections of the form E ∩ (E + k). More precisely, we shall show

∑_{k∈Z_{N}} ∥χ_{E∩E+k}∥Ȧ^{∞} = o(N^{2}).  (5)

The deduction of (5) from (4) is non-trivial and goes through Freiman’s theorem and a quantitative the Balog-Szemerédi theorem. We shall perform this deduction in Sections 4-6.

Finally, in Section 7 we exploit the condition (5) (which Gowers terms quadratic uniformity) to show a very large number of arithmetic progressions of length 4 (in fact we shall obtain about δ^{4}N^{2} of these progressions, which is the number one would expect from the case when E is chosen randomly).

3. Eliminating quadratic bias

We now prove (4) (and thus (3)) from (1), (2). Fix the functions ϕ_{0}, …, ϕ_{N−1} and the Z_{N} arithmetic progression P_{0}.

We first note from (2) that

|E ∩ P | ≤ δ|P | + o(|P |)  (6)

for all Z_{N} arithmetic progressions P of length |P | ≫ M^{2}. This is because any Z_{N} arithmetic progression of length |P | can be partitioned into ∼ |P |/m genuine arithmetic progressions of length ∼ m for some m ≳ |P |^{1/2}. (The idea is to use Kronecker’s theorem to find a step size in the Z_{N} progression less than N/|P |^{1/2}).

We shall no longer use the hypothesis (2) in this section, and rely entirely on (6). The advantage of this is that our hypothesis are now invariant under automorphisms of Z_{N}. In particular, since N is prime we can reduce to the case when P_{0} is the arithmetic progression [0, r) for some M^{C} ≪ r ≤ N.

Let P_{1}, P_{2}, …, P_{n} be Z_{N} arithmetic progressions. We say that P_{1}, …, P_{n} evenly cover Z_{N} if the function ∑_{j=1}^{n} χ_{P_{j}} is constant on Z_{N}.

We now observe that for any collection of moderately long Z_{N} arithmetic progressions evenly covering Z_{N}, the set E has density ≈ δ on generic members of this collection. More precisely:

Lemma 3.1. Let P_{1}, …, P_{n} be Z_{N} arithmetic progressions of length ≫ M^{2} which evenly cover Z_{N}. Then we have

∑_{j=1}^{n} ||E ∩ P_{j}| − δ|P_{j}|| = o(∑_{j=1}^{n} |P_{j}|).  (7)

Proof From (6) we have

(|E ∩ P_{j}| − δ|P_{j}|)_{+} = o(|P_{j}|).

Summing in j we obtain

∑_{j=1}^{n}(|E ∩ P_{j}| − δ|P_{j}|)_{+} = o(∑_{j=1}^{n} |P_{j}|).

On the other hand, from (1) and the constancy of f := ∑_{j=1}^{n} χ_{P_{j}} we have

∑_{j=1}^{n} |E ∩ P_{j}| − δ|P_{j}| = ∑_{k∈E} f − δ ∑_{j=1}^{n} |P_{j}| = \frac{|E|}{N} ∑_{k=1}^{N} f − \frac{|E|}{N} ∑_{j=1}^{n} |P_{j}| = 0,

and the claim follows by summing the above two estimates.

To obtain (4) from Lemma 3.1 we exploit the fact that the functions ϕ_{s} are essentially constant along moderately long arithmetic progressions. More precisely, we have

Lemma 3.2. For every s ∈ Z_{N}, we can partition P_{0} +s = [0, r)+s into arithmetic progressions P_{s,1}, …, P_{s,n_{s}} of length |P_{s,j}| ≫ M^{2} such that for each 1 ≤ j ≤ n_{s}, the function e^{2πiϕ_{s}(·)/N} is within o(1) of a constant on P_{s,n_{s}}.

Let us assume this Lemma for the moment and complete the proof of (4).

The progressions P_{0} + s evenly cover Z_{N} as s ranges over Z_{N}. From Lemma 3.2 we thus see that the progressions P_{s,j} evenly cover Z_{N} as s ranges over Z_{N} and j ranges from 1 to n_{s}. From Lemma 3.1 we thus have

∑_{s=1}^{N} ∑_{j=1}^{n_{s}} ||E ∩ P_{s,j}| − δ|P_{s,j}|| = o(∑_{s=1}^{N} ∑_{j=1}^{n_{s}} |P_{s,j}|).  (8)

To exploit this we use Lemma 3.2 to obtain

∑_{k∈E∩P_{s,j}} e^{2πiϕ_{s}(k)/N} = \frac{|E ∩ P_{s,j}|}{|P_{s,j}|} ∑_{k∈P_{s,j}} e^{2πiϕ_{s}(k)/N} + o(|P_{s,j}|),

which implies that

∑_{k∈E∩P_{s,j}} e^{2πiϕ_{s}(k)/N} = δ ∑_{k∈P_{s,j}} e^{2πiϕ_{s}(k)/N} + +o(||E ∩ P_{s,j}| − δ|P_{s,j}||) + o(|P_{s,j}|).

Summing this in j, s and using (8) we obtain

∑_{s∈Z_{N}} ∑_{k∈E∩(P_{0}+s)} e^{2πiϕ_{s}(k)/N} = δ ∑_{s∈Z_{N}} ∑_{k∈[0,r)+s} e^{2πiϕ_{s}(k)/N} + o(∑_{s=1}^{N} ∑_{j=1}^{n_{s}} |P_{s,j}|).

From standard exponential sum estimates and the non-constancy of ϕ_{s} we observe that

∑_{k∈[0,r)+s} e^{2πiϕ_{s}(k)/N} = o(|P_{s}|)

and the desired bound (4) follows.

It remains to prove Lemma 3.2. Fix s; by translation invariance we may take s = 0.

It suffices to partition [0, r) into Z_{N} arithmetic progressions P_{0,j} of length ∼ r^{c} for some small c such that

∥\frac{ϕ_{0}(k′) − ϕ_{0}(k)}{N}∥ = o(1)

for all k, k′ ∈ P_{0,j}. Letting d_{j} denote the step size of P_{0,j}, and k_{j} denote the initial element of P_{0,j}, it suffices to obtain the estimate

∥\frac{ϕ_{0}(k_{j} + ad_{j}) − ϕ_{0}(k_{j})}{N}∥ = o(1)

for all |a| ≲ r^{c}.

Write ϕ_{0} as

ϕ_{0}(k) =: A_{2}k^{2} + A_{1}k + A_{0}

for some A, B, C ∈ Z^{N}. We expand the previous condition as

∥\frac{a^{2}A_{2}d_{j}^{2}}{N} + \frac{(2A_{2}k_{j} + A_{1})d_{j}a}{N}∥ = o(1).

Since |a| ≲ r^{c}, it thus suffices to obtain the conditions

∥\frac{A_{1}d_{j}^{2}}{N} ∥, ∥\frac{(2A_{2}k_{j} + A_{1})d_{j}}{N} ∥ = O(r^{−3c}).  (9)

By a quantitative version of Weyl’s theorem (on the uniform distribution of the fractional parts of αn^{2}) we can find a d = O(r^{Cc}) such that

∥\frac{A_{1}d^{2}}{N} ∥ = o(r^{−100c}).

A formal proof of this fact proceeds using standard exponential sums techniques, and can be found in [4].

Fix this d, and partition [0, r) into arithmetic progressions P^{1}, … of step d and length ∼ r^{5c}. For each such progression P^{t} let k_{t} be an element of P^{t}. By Kronecker’s theorem we can find an integer m_{t} = O(r^{3c}) such that

∥∥\frac{(2A_{1}k_{t} + A_{2})m_{t}d}{N}∥ = O(r^{−3c}).

We now partition each P^{t} into arithmetic progressions P_{0,j} of step m_{t}d and length ∼ r^{5c}/m_{t} ≫ M^{2}. The first condition of (9) is clear. To verify the latter we observe that

k_{j} = k_{t} + ud

for some integer u = O(r^{5c}), and thus

∥\frac{(2A_{1}k_{j} + A_{2})m_{t}d}{N}∥ = ∥\frac{(2A_{1}k_{t} + A_{2})m_{t}d}{N}∥ + O(r^{5c}r^{3c}∥\frac{A_{1}d^{2}}{N}) = O(r^{−3c})

as desired.

4. Some Fourier analysis

We now pause to develop some very useful Fourier analytic tools.

Lemma 4.1. For any a, b, c ∈ Z_{N} − {0} we have

∑_{k,l,m∈Z_{N}:ak+bl+cm=0} f_{1}(k)f_{2}(l)f_{3}(m) ≤ ∥f_{1}∥_{2}∥f_{2}∥_{2}∥f_{3}∥_{A^{∞}}.  (10)

Similarly for permutations.

In practice we will use very crude bounds for the l^{2} norms of f_{1}, f_{2}; all of our efforts shall concentrate on making the A^{∞} norm of f_{3} small. Proof We can rewrite the left-hand side of (10) as

\frac{1}{N} ∑_{n∈Z_{N}} f̂_{1}(an)f̂_{2}(bn)f̂_{3}(cn)

which can then be estimated using Cauchy-Schwarz by

\frac{1}{N} ∥f̂_{1}∥_{2}∥f̂_{2}∥_{2}∥f_{3}∥_{A^{∞}}.

The claim then follows from Plancherel’s theorem.

Note that

∥f∥Ȧ^{∞} = ∥f − E(f)∥_{A^{∞}}  (11)

where E(f) := \frac{1}{N} ∑_{m∈Z_{N}} f(m) is the mean of f.

From Lemma 4.1, (11) and the identity

∑_{k,l,m∈Z_{N}:ak+bl+cm=0}(f_{1}(k) − E(f_{1}))(f_{2}(l) − E(f_{2}))(f_{3}(m) − E(f_{3}))

= ( ∑_{k,l,m∈Z_{N}:ak+bl+cm=0} f_{1}(k)f_{2}(l)f_{3}(m)) − N^{2}E(f_{1})E(f_{2})E(f_{3})

we thus have

Corollary 4.2. For any a, b, c ∈ Z_{N} − {0} we have

∑_{k,l,m∈Z_{N}:ak+bl+cm=0} f_{1}(k)f_{2}(l)f_{3}(m) = N^{2}E(f_{1})E(f_{2})E(f_{3}) + O(∥f_{1}∥_{2}∥f_{2}∥_{2}∥f_{3}∥_{A^{∞}}). (12)

Similarly for permutations.

To control the size of Fourier co-efficients we shall rely on the auto-correlation identity

|χ̂_{A}(n)|^{2} = ∑_{u∈Z_{N}} ∑_{s∈A∩A+u} exp(2πiun/N)  (13)

for all sets A ⊂ Z_{N} and n ∈ Z_{N}.

5. Averaged quadratic uniformity on progressions

Henceforth we assume that (4) holds for all P_{0} and ϕ_{s}. The task of this section and the next is to derive (5) from this information.

The first step shall be to obtain an localized version of (5), where the frequency variable depends affinely on the position k. More precisely, we have

Lemma 5.1. For any Z_{N} arithmetic progression P of length M^{C} ≪ |P | = o(N) and (λ, μ) ∈ Z_{N} × Z_{N} − {(0, 0)} we have

∑_{k∈P} |χ̂_{E∩E+k}(λk + μ)|^{2} = o(N^{2}|P |).  (14)

In the next two sections we bootstrap (14) to (5). Proof First suppose that λ = 0. By a rescaling (using the fact that N is prime) we may assume that the progression P is of the form P = a + [0, r) for some a, r. It then suffices to show that

∑_{m∈Z_{N}} ψ(m/r)|χ̂_{E∩E+a+m}(μ)|^{2} = o(N^{2}r)

for some suitable real even bump function ψ. We can rewrite the left-hand side as

N^{−2} ∑_{n,n′∈Z_{N}} rψ̂(r(n − n′)/N)χ̂_{E+a}(n)χ̂_{E}(μ − n)\overline{χ̂_{E+a}(n′)χ̂_{E}(μ − n′)},

where ψ̂ is the Fourier transform of ψ on R. From (3) we have

χ̂_{E+a}(n′)χ̂_{E}(μ − n′) = o(N^{2})

and so it suffices to show that

∑_{n,n′∈Z_{N}} |ψ̂(r(n − n′)/N)||χ̂_{E+a}(n)||χ̂_{E}(μ − n)| = O(N^{2}).

But this follows from Schur’s test, Plancherel, and the rapid decay of ψ̂. Now suppose λ ≠ 0. From (13) we can write the left-hand side of (14) as

| ∑_{k∈P} ∑_{u∈Z_{N}} ∑_{s∈E∩(E+k)∩(E+u)∩(E+k+u)} exp(2πiu(λk + μ)/N).

Using the identity

∑_{u∈Z_{N}} f(u) = \frac{1}{|P |} ∑_{u∈Z_{N}} ∑_{l∈P} f(u + l)

and rearranging, we may expand this as

\frac{1}{|P |}| ∑_{s∈E} ∑_{u∈Z_{N}} exp(2πiu(λk+μ)/N) ∑_{k,l∈Z_{N}} χ_{E−s∩P} (k)χ_{E−s−u∩P} (l)χ_{E−s−u}(k+l) exp(2πil(λk+μ)/N)|,

which we may estimate by

\frac{1}{|P |} ∑_{s,u∈Z_{N}} | ∑_{k,l∈Z_{N}} χ_{E−s∩P} (k)χ_{E−s−u∩P} (l)χ_{E−s−u}(k + l) exp(2πil(λk + μ)/N)|.

We can write

l(λk + μ) =: ϕ_{1}(k) + ϕ_{2}(l) + ϕ_{3}(k + l) ( mod N)

for some non-affine quadratic functions ϕ_{1}, ϕ_{2}, ϕ_{3}. Thus we can write the previous as

\frac{1}{|P |} ∑_{s,u∈Z_{N}} | ∑_{k,l∈Z_{N}} f_{1,s}(k)f_{2,s−u}(l)f_{3,s−u}(k + l)|

where

f_{1,s}(k) := exp(2πiϕ_{1}(k)/N)χ_{E−s∩P} (k)
f_{2,s−u}(l) := exp(2πiϕ_{2}(l)/N)χ_{E−s−u∩P} (l)
f_{3,s−u}(k + l) := exp(2πiϕ_{3}(k + l)/N)χ_{E−s−u∩(P +P)}(k + l).

From (10) we may estimate the previous by

≲ \frac{1}{|P |} ∑_{s∈E} ∑_{u∈Z_{N}} |P |∥f_{1,s}∥_{A^{∞}} = ∑_{s∈E} ∥f_{1,s}∥_{A^{∞}}.

It thus suffices to show that

∑_{s∈Z_{N}} ∑_{m∈Z_{N}} f_{1,j}(m) exp(2πimn(s)/N) = o(N|P |).  (15)

for all choices of function n : Z_{N} → Z_{N}.

Fix the function n. We expand the left-hand side of (15) as

∑_{s∈Z_{N}} ∑_{m∈P ∩E−s} exp(2πi\frac{ϕ_{1}(m) + mn(s)}{N}).

Making the substitution j := m + s, this becomes

∑_{s∈Z_{N}} ∑_{m∈E∩P +s} exp(2πi\frac{ϕ_{1}(j − s) + (j − s)n(s)}{N}).

Since ϕ_{1}(· − s) + (· − s)n(s) is a non-constant quadratic for every s, the claim then follows from (4).

6. Obtaining quadratic uniformity

We can now prove (5). Suppose for contradiction that (5) failed. Then we can find a set B ⊂ Z_{N} of size |B| ≈ N such that

∥χ_{E∩E+k}∥Ȧ^{∞} ≈ N

for all k ∈ B. We can therefore find a function ϕ : B → Z_{N} − {0} such that

|χ̂_{E∩E+k}(ϕ(k))| ≈ N  (16)

for all k ∈ B.

Fix B, ϕ, and let Ω denote the graph of ϕ:

Ω := {(k, ϕ(k)) : k ∈ B}.

At first glance, Ω seems like a fairly arbitrary subset of Z_{N} × Z_{N} of cardinality ≈ N. However, it has considerable arithmetic structure:

Lemma 6.1. We have

#{(a, b, c, d) ∈ Ω^{4} : a + b = c + d} ≈ N^{3}.

Proof We square both sides of (16) using (13) to obtain

∑_{u∈Z_{N}} ∑_{s∈E∩E+k∩E+u∩E+k+u} exp(2πiuϕ(k)/N) ≈ N^{2}.

Summing in k and re-arranging, we obtain

∑_{u∈Z_{N}} ∑_{s,k∈Z_{N}} χ_{E∩E+u}(s)χ_{E∩E+u}(s − k)χ_{B}(k) exp(2πiuϕ(k)/N) ≈ N^{3}.

By (10) we thus have

∑_{u∈Z_{N}} N∥χ_{B}(·) exp(2πiuϕ(·)/N)∥_{A^{∞}} ≈ N^{3}.

We can re-arrange this as

∑_{u∈Z_{N}} sup_{m∈Z_{N}} |χ̂_{Ω}(m, u)| ≈ N^{2}.

From Hölder we thus have

∑_{u∈Z_{N}} sup_{m∈Z_{N}} |χ̂_{Ω}(m, u)|^{4} ≈ N^{5}

and hence

∑_{u,m∈Z_{N}} |χ̂_{Ω}(m, u)|^{4} ≈ N^{5}

which by Plancherel becomes

∥χ_{Ω} ∗ χ_{Ω}∥_{2}^{2} ≈ N^{3}

as desired.

Note that the conclusion of Lemma 6.1 would easily follow from Cauchy-Schwarz if the sum-set was small: |Ω + Ω| ≈ N. The converse of this statement is not exactly true, but there is a substitute, essentially a quantitative version of the Balog-Szemerédi theorem [1], which asserts that we can find a subset Ω′ ⊂ Ω with |Ω′| ≈ |Ω| ≈ N such that

|Ω′ + Ω′| ≈ N.

See [4], [2], or [5]. One can then apply Freiman’s theorem [3], [6] to conclude that Ω′ is contained in a multi-dimensional Z_{N} × Z_{N} arithmetic progression of dimension ≈ 1 and cardinality ≈ N. From this, we see that Ω must have a large intersection with some one-dimensional Z_{N} × Z_{N} arithmetic progression Q of length N^{c_{ε}} for some 0 < c_{ε} ≪ 1, i.e. that

|Ω ∩ Q| ≈ |Q|.

Since Ω is a graph, Q cannot be a vertical line segment. Since N is prime, Q must then be a graph of a affine function on a Z_{N} arithmetic progression P_{0} of length N^{c_{ε}}:

Q = {(k, λk + μ) : k ∈ P_{0}}.

Since ϕ is non-zero, μ cannot be zero. But this and (16) contradict Lemma 5.1 (if M grows sufficiently slowly with N).

7. Counting arithmetic progressions

We now suppose that (5) holds. We need to show that E contains ∼ δ^{4}N^{2} genuine arithmetic progressions of length 4. It suffices to show that

∑_{a,r∈Z_{N}} χ_{E′}(a)χ_{E′}(a + r)χ_{E}(a + 2r)χ_{E}(a + 3r) ∼ δ^{4}N^{2}

where E′ = E ∩ [0.4N, 0.6N], since the r = 0 contribution is negligible if N is sufficiently large.

From (2) we see that |E − E′| ≤ (δ + 2ε)0.8N, which with (1) implies that |E′| = δ′N for some δ′ ∼ δ. Thus it suffices to show that (if ε is sufficiently small depending on δ)

∑_{a∈E′}(f(a) − δ′δ^{2}N) = o(N^{2})

where

f(a) := ∑_{r∈Z_{N}} χ_{E′}(a + r)χ_{E}(a + 2r)χ_{E}(a + 3r).

By Cauchy-Schwarz it thus suffices to show that

∑_{a∈Z_{N}}(f(a) − δ′δ^{2}N)^{2} = o(N^{3}).  (17)

We now invoke

Lemma 7.1. For any F ⊂ Z_{N}, we have

∑_{u∈Z_{N}} ||F ∩ E + u| − δ|F || = o(N^{2}).  (18)

Proof It suffices to show

∑_{u∈A}(|F ∩ E + u| − δ|F |) = o(N^{2})

for arbitrary A, F ⊂ Z_{N}. We rewrite this as

∑_{u,k∈Z_{N}} χ_{A}(u)χ_{F} (k)(χ_{E}(k − u) − δ) = δ|F |N + o(N^{2}).

But from (1), (11), (3) we have

∥χ_{E} − δ∥_{A^{∞}} = ∥χ_{E}∥Ȧ^{∞} = o(N),

and the claim follows from (12).

From this and the substitution b := a + r we have

∑_{a∈Z_{N}}(f(a) − δ′δ^{2}N) = ∑_{b∈E′}(|2E ∩ E + b| − δ^{2}N) = o(N^{2}),

so by some algebra (17) will follow from

∑_{a∈Z_{N}} f(a)^{2} = δ′^{2}δ^{4}N^{3} + o(N^{3}).

Since

f(a)^{2} = ∑_{u∈Z_{N}} ∑_{r∈Z_{N}} χ_{E′∩E′+u}(a + r)χ_{E∩E+u}(a + 2r)χ_{E∩E+u}(a + 3r)

it suffices (after making the substitution b := a + r) to show that

∑_{u∈Z_{N}} ∑_{b,r∈Z_{N}} χ_{E′∩E′+u}(b)χ_{E∩E+u}(b + r)χ_{E∩E+u}(b + 2r) = δ′^{2}δ^{4}N^{3} + o(N^{3}).

By (12), the left-hand side is

∑_{u∈Z_{N}} N^{−1}|E′ ∩ E′ + u||E ∩ E + u||E ∩ E + u| + O(N∥χ_{E∩E+u}∥Ȧ^{∞}).

By (5) it thus suffices to show that

∑_{u∈Z_{N}} |E′ ∩ E′ + u||E ∩ E + u|^{2} = δ′^{2}δ^{4}N^{4} + o(N^{4}).

On the other hand, we have

∑_{u∈Z_{N}} |E′ ∩ E′ + u|(δ^{2}N)^{2} = δ^{4}N^{2}|E′|^{2} = δ′^{2}δ^{4}N^{4}.

The claim then follows from (18) with F := E, (1), and the crude estimates |E′ ∩ E′ + u|, |E ∩ E + u| = O(N).

References

[1] A. Balog, E. Szemerédi, A statistical theorem of set addition, Combinatorica 14 (1994), 263–268.

[2] J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities, Geom. Funct. Anal. 9 (1999), no. 2, 256–282.

[3] G. A. Freiman, Foundations of a structural theory of set addition , Translations of Mathematical Monographs 37, Amer. Math. Soc., Providence, 1973.

[4] T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, to appear in GAFA.

[5] N. Katz, I. Łaba, T. Tao, An improved bound for the Minkowski dimension of Besicovitch sets in R^{3}, to appear, Annals of Math.

[6] I. Rusza, Generalized arithmetic progressions and sumsets, Acta. Math. Hungar. 65 (1994), 379–388.

[7] E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta. Math. Acad. Sci. Hungar. 20 (1969), 89–104.

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

Department of Mathematics, UCLA, Los Angeles, CA 90024

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