LECTURE NOTES 4 FOR 254A

TERENCE TAO

1. Arithmetic progressions

In this weeks notes we begin a new topic - that of finding arithmetic progressions inside a reasonably dense set of integers. The basic question is the following: let k be a small integer (in practice, we only take k = 3 or k = 4), and let N be a very large integer. If A is a subset of {1, …, N}, how large does A have to be in order to ensure that it contains at least one proper arithmetic progression of length k? (In this set of notes all our arithmetic progressions shall be of rank 1; i.e. no generalized arithmetic progressions will be considered here). Of course we take k ≥ 3 since the k ≤ 2 cases are quite trivial.

One famous conjecture in this direction is Erdös’s conjecture that the primes contain infinitely many arithmetic progressions of arbitrary length. More generally, he conjectured that any subset A of the natural numbers with ∑_{n∈A} 1/n = ∞ should contain infinitely many progressions of arbitrary length. In the above language of subsets of {1, …, N}, this roughly corresponds to sets A of density ∼ 1/ log N (and in particular this is what happens to the primes, thanks to the prime number theorem). However, it is not yet known whether subsets of {1, …, N} of density ∼ 1/ log N must contain progressions of length k for large enough N, even when k = 3; the best result in this direction is by Bourgain, who showed that we have progressions of length 3 when the density is at least ∼ \sqrt{log log N}/\sqrt{log N}. We will prove this result in next week’s results. (Remark: In the special case of the primes, Van der Corput in 1935 proved the infinitude of arithmetic progressions of length 3, but this is because the primes have better distributional properties than a generic set of density 1/logN. The corresponding question about progressions of primes of length 4 is still open).

In this set of notes we prove a basic result in this area, known as Szemerédi’s theorem:

Theorem 1.1. Let 0 < δ ≤ 1 and k ≥ 3. Then there exists an N(δ, k) such that for any N > N(δ, k) and any subset A of {1, …, N} of cardinality |A| ≥ δN, there exists an proper arithmetic progression in A of length k.

Actually, we shall just prove this for k = 3 (this is due to Roth) and k = 4 (using an argument by Gowers). The k = 4 argument does eventually extend to general k, but the details are quite technical and will not be pursued here. The methods used will incorporate almost everything we have done in previous lecture notes.

2. Roth’s argument

We now prove Theorem 1.1 when k = 3. The idea is to induct downwardly on δ. Of course when δ = 1 the claim is trivial. Indeed, even when δ > 2/3 the claim is easy, for the set {a ∈ {1, …, N −2} : at least one of a, a+1, a+2 is not in A} has cardinality at least 3(1−δ)N, and so as soon as N is large enough that 3(1−δ)N < N − 2 we can find a ∈ {1, …, N} such that a, a + 1, a + 2 are all in A.

Of course, δ is a continuous parameter, not a discrete one, and so the induction has to be slightly careful - in particular, the step size of the induction should not be allowed to vanish to zero unexpectedly. Let P (δ) be the property that Theorem 1.1 holds for δ (and k = 3), thus we already have P (δ) for δ > 2/3. Our task is to show P (δ) is true for all δ > 0. To show this, the main inductive step is the following:

Proposition 2.1. For each 0 < δ < 1 there exists an ε = ε(δ) > 0 such that ε depends continuously on δ, and such that P (δ + ε) implies P (δ).

We now indicate why Proposition 2.1 implies Theorem 1.1 for k = 3. To see this, suppose for contradiction that P (δ) failed for some δ (and thus for all smaller δ). Let δ_{∗} be the supremum of all the δ for which P (δ) failed, so that P (δ) is true for δ_{∗} > δ and false for δ_{∗} < δ. But then by continuity and positivity of ε(δ) we can find a δ < δ_{∗} for which δ + ε(δ) > δ_{∗}, contradicting Proposition 2.1.

So it remains to prove Proposition 2.1. Fix δ: we let ε = ε(δ) > 0 be chosen later. By hypothesis, there exists an integer M_{0} such that for any M > M_{0} subset B of {1, …, M} of density |B| ≥ (δ + ε)M, that B contains a orioer arithmetic progression of length 3. Clearly, this also implies that for any proper arithmetic progression P of cardinality |P | ≥ M_{0}, and any subset B ⊆ P with |B| ≥ (δ +ε)|P |, that B must also contain an arithmetic progression of length 3. Our task is thus to show that for N large enough (depending on M, δ, ε) and any A in Z/NZ of density |A| ≥ δN, that A also contains a progression of length 3.

The idea is to introduce a dichotomy - either A contains a “compact factor” - a subprogression of Z/NZ of size at least M_{0} where the density of A increases from δ to δ + ε - in which case we can apply the inductive hypothesis. Otherwise, A is “mixing” - it has uniformly density δ+O(ε) even when restricted to subprogressions. In such cases we can use some theory of exponential sums to show that the Fourier coefficients of A are small, which by some Fourier analysis will easily deduce the existence of many arithmetic progressions. The intuition here is that in the mixing case, A behaves like a random subset of {1, …, N} of density δ (i.e. it is as if each element of {1, …, N} would be in A with probability δ independently), and for random sets it is clear that one has ∼ δ^{3}N^{2} arithmetic progressions (since there are ∼ N^{2} progressions overall, and each progression has probability ∼ δ^{3} of being contained in A).

(This terminology of compact factor and mixing is not completely accurate, but I use it by analogy with another, ergodic theory proof of Szemeredi’s theorem given by Furstenburg).

If there exists an arithmetic progression P ⊆ {1, …, N} of length at least M for which |A ∩ P | ≥ (δ + ε)|P |, then by the inductive hypothesis we know that A ∩ P, and hence A, contains a proper arithmetic progression of length 3. So, we may assume without loss of generality that

Assumption. We have

|A ∩ P | ≤ (δ + ε)|P |  (1)

for every proper arithmetic progression P ⊆ {1, …, N} of size |P | ≥ M. In particular, we know that |A| = (δ + O(ε))N.

This assumption means that A is very evenly distributed; for instance, if we partition {1, …, N} into ∼ k progressions of length ∼ N/k, then the δN elements of A are almost perfectly divided among those progressions. This will eventually show that the Fourier coefficients of χ_{A} are very small. But to do that, we must first place A inside a cyclic group, similarly to our treatment of Freiman’s theorem.

Let p be a prime between N and (1 − ε)N (which we can always choose for N large enough, thanks to the prime number theorem), and let A′ be the set A∩{1, …, p}, thought of as a subset of Z/pZ; observe that |A′| = (δ + O(ε))p. We know that |A′ ∩ P | ≤ (δ + ε)|P | for all sufficiently long progressions P in {1, …, p}. But this is not the same as all sufficiently long progressions in Z/pZ, because of wraparound issues; to make this distinction let us call a genuine arithmetic progression in Z/pZ, one which is still a genuine progression when Z/pZ is replaced with {1, …, p} in the obvious manner.

Fortunately, our density bound for genuine arithmetic progressions can easily be extended to (sufficiently long) Z/pZ arithmetic progressions, because very such progression can be decomposed into genuine arithmetic progressions:

Proposition 2.2. There exists an M_{1} = M_{1}(M, ε) such that one has

|A′ ∩ P | ≤ (δ + O(ε))|P |

for any proper arithmetic progression P in Z/pZ (not necessarily genuine) of length |P | ≥ M_{1}.

Proof Let r ≠ 0 be the spacing of a proper progression P in Z/pZ. Let us first consider the case when 0 < r ≪ p/M. Then we can partition P into the disjoint union of genuine arithmetic progressions of the same step size r, simply by making a cut every time the progression wraps around the end of {1, …, p}. Except possibly for the first and last progression, each of the genuine progressions has length at least M, and so the density of A in those genuine progressions is at most δ + ε by assumption. Adding up all these density estimates for those genuine progressions of length at least M, we obtain the bound

|A′ ∩ P | ≤ (δ + ε)|P | + 2M.

A similar bound obtains when 0 < −r ≪ p/M.

Now suppose that r is arbitrary. Consider the first O(M) multiples of r in Z/pZ. By the pigeonhole principle, two of them must be ≪ p/M apart, thus we can find a non-zero j = O(M) such that |jr mod p| ≪ p/M. We can then (if P is long enough) partition P into |j| disjoint progressions, all of length ∼ |P |/|j|, with step size jr mod p. Applying the previous estimate to all of these progressions and adding up, we obtain

|A′ ∩ P | ≤ (δ + ε)|P | + 2|j|M ≤ (δ + ε)|P | + O(M^{2}),

and the claim follows if |P | is large enough.

Let f(x) denote the function

f(x) := χ_{A′}(x) − |A′|/p

on Z/p/Z; in other words, f is the characteristic function of A′, normalized to have mean zero. Then from the previous proposition we see that

∑_{x∈P} f(x) ≲ ε|P |

for any arithmetic progression P of length ≥ M_{1}. In other words, f has mean at most O(ε) on any sufficiently long progression. To put it another way, we have an upper bound

f ∗ \frac{χ_{P}}{|P |}(x) ≲ ε

for any x (since we just replace P by x − P in the previous. It would be nice if we also could have a lower bound too:

|f ∗ \frac{χ_{P}}{|P |}(x)| ≲ ε

since this would be a very strong statement about f. However, we cannot quite deduce this from what we know; it asserts that on every sub-progression, that not only is |A′ ∩ P | have density at most δ + O(ε), it also has density at least δ − O(ε). Nevertheless, despite the fact that we cannot obtain this bound directly, we can obtain a usable substitute, namely

∥f ∗ \frac{χ_{P}}{|P |}(x)∥_{1} ≲ ε;

in other words, we don’t have uniform control on how negative f ∗ χ_{P} |P | can be, but we do have L^{1} control. The reason for this is very simple: since f has mean zero, we know that f ∗ \frac{χ_{P}}{|P |} also has mean zero, and in particular the positive and negative parts have equal L^{1} norm. But the positive part is uniformly O(ε), and hence O(ε) in L^{1} norm as well, thus the negative part is also.

This has some consequences for the Fourier transform of f:

Lemma 2.3. For any ξ ∈ Z/pZ, we have |f̂(ξ)| ≲ ε.

This statement is sometimes referred to as linear uniformity of f; f(x) is somewhat orthogonal to all functions of the form e^{2πixξ/p}, which have phases linear in x. For comparision, if A is chosen randomly, then one almost surely has |f̂(ξ)| ≲ p^{−1/2+} (see Q1). Thus this lemma asserts that sets which do not concentrate on arithmetic progressions have linear uniformity; for a partial converse, see Q3.

If we pretend that f is itself a phase function, f(x) = e^{2πiϕ(x)}, then the above lemma asserts that ϕ does not behave like a linear phase, i.e. ϕ(x) ≉ xξ/p + c for any ξ and constant c, where we are vague as to what the symbol ≈ means.

Proof The case ξ = 0 is trivial, so let us assume ξ ≠ 0. Since Z/pZ is a field, we can find r ≠ 0 such that rξ = 1 mod p. Let P be the progression {jr : 0 ≤ j < M_{1}}; by the preceding discussion we have

|f̂(ξ)|\frac{p}{|P |}|χ̂_{P} (ξ)| ≲ ε.

On the other hand, by construction we easily see that

χ̂_{P} (ξ) = \frac{1}{p} ∑_{j=0}^{M_{1}−1} e^{2πij/p} ∼ |P |/p

if p is sufficiently large depending on M_{1}. The claim follows.

Now armed with this Fourier information, we can finish the proof. We introduce the trilinear form T (f, g, h) for three functions on Z/pZ defined by

T (f, g, h) := ∫_{Z/pZ} ∫_{Z/pZ} f(x)g(x + r)h(x + 2r) dxdr.

Observe that the number of proper (but non-genuine) arithmetic progressions in A′ of length 3 is precisely

p^{2}T (χ_{A′}, χ_{A′}, χ_{A′}) − |A′|

(the −|A′| being there just to remove the trivial progressions of step 0; we count a, a + r, a + 2r as being a different progression from a + 2r, a + r, a). So we can find (non-genuine) progressions as soon as we prove an estimate of the form

T (χ_{A′}, χ_{A′}, χ_{A′}) ≫ δ/p.  (2)

Later on we will see how we need to modify this to obtain genuine progressions.

The basic estimate we need here is that T (f, g, h) is small if one of f, g, h has small Fourier coefficients:

Proposition 2.4. We have

|T (f, g, h)| ≤ ∥f∥_{2}∥g∥_{2}∥ĥ∥_{∞}

and similarly for permutations.

To get some intuition for this proposition, suppose that f(x) = e^{2πiϕ(x)}, g(x) = e^{2πiψ(x)}, and h(x) = e^{2πiη(x)}. Then the quantity T (f, g, h) is large if ϕ(a) + ψ(a + r) + η(a + 2r) behaves like a constant, i.e.

ϕ(a) + ψ(a + r) + η(a + 2r) ≈ c for most a, r

where we are vague about what ≈ and “for most” mean. This Proposition says that this type of phase cancellation can happen only when ϕ, ψ, and η all behave somewhat linearly - each of f, g, and h need to have one large Fourier coefficient in order to obtain the above type of estimate. In fact, the proof will show that the only way T (f, g, h) can be large is if there exists a ξ such that ϕ(a) ≈ aξ/p + c_{1}, ψ(a) ≈ −2aξ/p + c_{2}, and η(a) ≈ aξ/p + c_{3}. (See Q6.)

Proof We use the Fourier inversion formula to write

f(x) = ∑_{ξ_{1}∈Z/pZ} f̂(ξ_{1})e^{2πixξ_{1}/p}

g(x + r) = ∑_{ξ_{2}∈Z/pZ} ĝ(ξ_{2})e^{2πi(x+r)ξ_{2}/p}

h(x + 2r) = ∑_{ξ_{3}∈Z/pZ} ĥ(ξ_{3})e^{2πi(x+2r)ξ_{3}/p}

which allows us to write T (f, g, h) as

∑_{ξ_{1},ξ_{2},ξ_{3}∈Z/pZ} f̂(ξ_{1})ĝ(ξ_{2})ĥ(ξ_{3}) ∫_{Z/pZ} ∫_{Z/pZ} e^{2πi(xξ_{1}+(x+r)ξ_{2}+(x+2r)ξ_{3})/p} dxdr.

The inner r integral vanishes unless ξ_{2} + 2ξ_{3} = 0 mod p; the inner x integral vanishes unless ξ_{1} + ξ_{2} + ξ_{3} = 0 mod p. Thus the only non-zero contribution arises when ξ_{3} = ξ_{1} and ξ_{2} = −2ξ_{1}, thus

T (f, g, h) = ∑_{ξ∈Z/pZ} f̂(ξ)ĝ(−2ξ)ĥ(ξ).

The claim then follows by taking ĥ out in supremum, and applying Cauchy-Schwarz and Plancherel to what remains.

To apply this proposition, we write χ_{A′} = |A′|/p + f, and split T (χ_{A′}, χ_{A′}, χ_{A′}) accordingly into 8 terms. 7 of these can be estimated using the above proposition and lemma as O(δ^{2}ε) + O(δε^{2}) + O(ε^{3}), while the 8th is T (|A′|/p, |A′|/p, |A′|/p) = |A′|^{3}/p^{3}, which is roughly δ^{3}. Thus if we choose ε ≪ δ we obtain (2) as desired. This gives us a non-genuine arithmetic progression of length 3; in fact, it gives us ∼ δ^{3}p^{2} such progressions, which is consistent with the random case.

To upgrade this to a genuine arithmetic progression, we use a cutoff function. Let ψ be a bump function adapted to [p/3, 2p/3]. We will show that

T (ψχ_{A′}, ψχ_{A′}, ψχ_{A′}) ≫ δ/p;

this will show that A′ ∩ [p/3, 2p/3] contains an arithmetic progression, which must then necessarily be genuine. We split ψχ_{A′} = ψ|A′|/p + ψf. Observing that the Fourier transform of ψ is bounded and decays rapidly away from the origin, we see that ψf is also linearly uniform (its Fourier coefficients are also O(ε)). Also, T (ψ, ψ, ψ) ∼ c for some c > 0 independent of p, depending only on ψ. The claim follows. This concludes the proof of Roth’s theorem. □

We now remark on what the exact dependence of N(δ) is on δ, as predicted by the above proof. Let N(δ) be the smallest number for which the conclusion of Szemeredi’s theorem (with k = 3) holds for that valaue of δ. An inspection of the above argument shows that we can take ε = cδ for some absolute constants c, C, and can take N_{0} = CM^{C}δ^{−C}ε^{−C} for some other absolute constants C. If we assume that M ≥ δ^{−1} (which is quite reasonable, given it is difficult to find many sets in {1, …, M} of density δ if M < δ^{−1}, we can thus take N_{0} = CM^{C}. Thus the above argument gives a recursive bound of the form

N(δ) ≤ CN(δ + cδ)^{C}.

Also, we have N(δ) < 10 when δ > 0.9 (for instance), by the argument given for δ > 2/3. Putting these two together, we can obtain a bound of the form

N(δ) ≤ exp(exp(C/δ))

for some other absolute constant C; see Q2. Inverting this, we thus see that for any large N that every subset of {1, …, N} of density at least C/ log log N will contain a non-trivial arithmetic progression of length 3. Note that this is far too weak to address the question of what happens for the primes, which have a density of about 1/ log N; in the next week’s notes we will give some progress toward closing this gap.

Call a set A′ ⊆ Z/pZ linearly uniform if the function f = χ_{A′} − |A′|/p has small Fourier coefficients, say ∥f̂∥_{∞} ≲ ε. The above argument says that if A′ is linearly uniform and has density ∼ δ, then A′ contains ∼ δ^{3}p^{2} arithmetic progressions; roughly speaking, this is because the linear uniformity guarantees that the events a ∈ A′, a + r ∈ A′, and a + 2r ∈ A′ behave more or less “independently”. Note that if A′ had a high concentration in an arithmetic progression then we would not have this independence.

3. Gowers proof of Szemeredi’s theorem when k = 4.

Roth’s argument above appeared all the way back in 1953. One might think that it would be an easy manner to extend that k = 3 argument to, say, k = 4, but the first such proof had to wait until 1969 by Szemeredi, and required some very deep combinatorial results (in particular, Szemeredi’s uniformity lemma). Only in 1998 did Gowers finally extend the Fourier-analytic stile of Roth’s argument to k = 4, and then in 2001 to all k.

The main difficulty when k = 4 is the following. We can once again give the dichotomy between “compact factor” (where A ∩ P is denser than A) or “mixing” (when A is uniformly of density δ). The compact factor case is again easy by induction; the problem is how to use the mixing hypothesis. In theory, in this case one expects about δ^{4}p^{2} arithmetic progressions of length 4 in A′, which is of course much larger than the ∼ δp trivial arithmetic progressions when p is large. Unfortunately, in this case the Fourier argument is not as useful. If we introduce the quadrilinear form

Q(f, g, h, k) := ∫_{Z/pZ} ∫_{Z/pZ} f(x)g(x + r)h(x + 2r)k(x + 3r) dxdr

then the number of Z/pZ arithmetic progressions of length 4 in A′ is

p^{2}Q(χ_{A′}, χ_{A′}, χ_{A′}, χ_{A′}) − |A′|.

The main term is

p^{2}Q(|A′|/p, |A′|/p, |A′|/p, |A′|/p) ∼ δ^{4}p^{2}

as expected, and most of the other terms can be treated using Proposition 2.4 (because if there is at least one constant factor |A′|/p then one can collapse the quadrilinear form to a trilinear one, which can then be treated using some variant of Proposition 2.4). However, the term p^{2}Q(f, f, f, f) is more resistant to analysis. A Fourier argument shows that p^{2}Q(f, f, f, f) is equal to

p^{2} ∑_{ξ_{1},ξ_{2},ξ_{3},ξ_{4}∈Z/pZ:ξ_{1}+ξ_{2}+ξ_{3}+ξ_{4}=ξ_{2}+2ξ_{3}+3ξ_{4}=0} f̂(ξ_{1})f̂(ξ_{2})f̂(ξ_{3})f̂(ξ_{4}),

or equivalently

p^{2} ∑_{ξ_{3},ξ_{4}∈Z/pZ} f̂(ξ_{3} + 2ξ_{4})f̂(−2ξ_{3} − 3ξ_{4})f̂(ξ_{3})f̂(ξ_{4}).

Using the bounds ∥f̂∥_{l^{2}} ∼ δ^{1/2} and ∥f̂∥_{∞} ≲ ε, the best bound that one can obtain on expression term is O(δ^{2}p^{2}) (how? Use Cauchy-Schwarz on Z/pZ × Z/pZ, splitting the four factors into pairs of two), which dominates the main term.

The basic problem is that linear uniformity is not strong enough to control Q. However, if we strengthen linear uniformity to something called quadratic uniformity, then we will be in good shape. At this point it is not quite clear what quadratic uniformity should mean; in fact, the difficulty in even coming up with the correct notion here is one of the key stumbling blocks in the argument. (An obvious guess for quadratic uniformity is that the function f should be somewhat orthogonal, not just to linear phase functions, but also to quadratic phase functions as well; it turns out that this WILL imply the notion of quadratic uniformity which we will use, but only if we localize it to relatively short sub-progressions, and the implication is highly nontrivial, using both Freiman’s theorem and the Balog-Szemeredi theorem).

Let us first make some notation. Let us use o(1) to denote any quantity depending on ε which goes to zero as ε goes to 0, so in particular we can make o(1) much smaller than δ by choosing ε sufficiently small. We say that a statement P (k) is true for most k ∈ Z/pZ if the number of exceptional k for which P (k) false is only o(p).

We say that a function f on Z/pZ is linearly uniform if ∥f∥_{∞} ≲ 1, but ∥f̂∥_{∞} = o(1); as we saw earlier, this basically meant that f did not concentrate on any arithmetic progression. We say that f is quadratically uniform if ∥f∥_{∞} ≲ 1, and f(x + k)\overline{f}(x) is linearly uniform for most k ∈ Z/pZ. In other words (see Q5), f is quadratically uniform if

∑_{k∈Z/pZ} ∥{ \atop f(· + k)\overline{f}}∥_{∞} = o(p).

To understand this concept, let us first suppose that f is a phase function, i.e. f(x) = e^{2πiϕ(x)} for some real-valued ϕ; thus the condition ∥f∥_{∞} ≲ 1 is automatic. Saying that f is linearly uniform is the same as saying that the function e^{2πi(ϕ(x)−xξ/p)} has mean o(1) for all ξ; thus the function ϕ(x) is never “aligned” with any linear function xξ/p. Saying that f is quadratically uniform is the same as saying that for most k, the function ϕ(x + k) − ϕ(x) is linearly uniform; this is somewhat like saying that the “derivative” of ϕ never “behaves linearly”, and is thus a statement that ϕ “never behaves quadratically”. For instance, the function f(x) = e^{2πix^{2}/p} can easily be shown to be linearly uniform but not quadratically uniform (see Q4, Q7(a)).

Let’s say that a subset A′ of Z/pZ is quadratically uniform if the mean-zero function F = χ_{A′} −|A′|/p is quadratically uniform. We now claim that if A′ is quadratically uniform and has density ∼ δ, then it will contain ∼ δ^{4}p^{2} arithmetic progressions (i.e. the number predicted by a random argument). Roughly speaking, the reason why we need quadratic uniformity is that this is what it takes to make the events a ∈ A, a+r ∈ A, a+2r ∈ A, and a+3r ∈ A behave “independently”. For instance, take A to be the set

A = {x ∈ Z/pZ : e^{2πix^{2}/p} = 1 + O(δ)}.

Then A has density ∼ δ, and it turns out to be linearly uniform (for much the same reason that e^{2πix^{2}/p} is linearly uniform), but is not quadratically uniform; if a, a + r, a + 2r all lie in A, then there is a very high probability that a + 3r also lies in A, basically because of the identity

(a + 3r)^{2} = a^{2} − 3(a + r)^{2} + 3(a + 2r)^{2}.

Now we prove that quadratic uniformity implies ∼ δ^{4}p^{2} arithmetic progressions of length 4:

Lemma 3.1. Suppose χ_{A′} − |A′|/p is both linearly uniform and quadratically uniform. Then A′ contains ∼ δ^{4}p^{2} Z/pZ-progressions of length 4.

Proof We first recall the analysis from Roth’s argument: if f, g, h are bounded functions, and at least one of f, g, h are linearly uniform, then

∫_{Z/pZ} ∫_{Z/pZ} f(a)g(a + r)h(a + 2r) dadr = T (f, g, h) = o(1).  (3)

Also, since F is quadratically uniform, we know the function F (x + k)F (x) linearly uniform for most k. Applying (3) with f(x) = F (x+k)F (x), g(x) = F (x+2k)F (x), h(x) = F (x + 3k)F (x), we thus have

∫_{Z/pZ} ∫_{Z/pZ} F (a)F (a+k)F (a+r)F (a+2k+r)F (a+2r)F (a+3k+2r) dadr = o(1)

for most k. For those exceptional values of k, this integral is still bounded, of course. Thus we can integrate over all k and obtain

∫_{Z/pZ} ∫_{Z/pZ} ∫_{Z/pZ} F (a)F (a+k)F (a+r)F (a+2k+r)F (a+2r)F (a+3k+2r) dadrdk = o(1).

Replacing k by the variable s := r+k, and a by the variable b := a−r, this becomes

∫_{Z/pZ} ∫_{Z/pZ} ∫_{Z/pZ} F (b+r)F (b+s)F (b+2r)F (b+2s)F (b+3r)F (b+3r) dbdrds = o(1),

thus

∫_{Z/pZ} | ∫_{Z/pZ} F (b + r)F (b + 2r)F (b + 3r) dr|^{2}db = o(1),

In particular, by Cauchy-Schwarz we have Q(F, F, F, F) = o(1), which implies that Q(χ_{A′}, χ_{A′}, χ_{A′}, χ_{A′}) ∼ δ^{4} as desired (since we can split χ_{A′} = |A′|/p + F and use Proposition 2.4 and its variants (using the linear uniformity of A′) to control crossterms.

In light of this lemma, and the linear uniformity already obtained from Roth’s argument, it thus suffices to show

Proposition 3.2. Let A′ be a subset of Z/pZ of density δ + O(ε), which obeys the conclusions of Proposition 2.2 (i.e. A′ has uniform density on reasonably long arithmetic progressions). Then, if p is large enough, then A′ is quadratically uniform.

To prove this proposition, we will argue by contradiction. Let σ = o(1) be a quantity to be chosen later. Suppose that A′ is not quadratically uniform; this means that for at least σp values of k, we have a frequency ξ(k) such that

|{ \atop \overline{F (x)}F (x + k)}(ξ(k))| ≥ σ.  (4)

Let B be the set of all such k, and let Ω ∈ Z/pZ × Z/pZ be the graph

Ω := {(k, ξ(k))}.

One can think of Ω as the set of “resonant frequencies” of the two-variable function \overline{F (x)}F (x + k) (if we take Fourier transforms in x but not in k).

We now perform a number of somewhat mysterious Fourier manipulations to eventually discover some additive information about Ω. Before we proceed, let us give an intuitive argument. Suppose that F (x) = e^{2πiϕ(x)}. Then the estimate (4) says, essentially, that ϕ(x + k) − ϕ(x) ≈ ξ(k)x/p + c for “most” x and k. It turns out the only way this can work out is if ξ is roughly additive, i.e. Ω is in some sense somewhat closed under addition. Indeed, we heuristically expect ϕ to be linear, and ξ(k) should be something like the slope of ϕ, multiplied by k. (See Q7(b)).

For all k ∈ B, we expand (4), using the fact that F is real, to obtain

| ∫ F (x)F (x + k)e^{2πixξ(k)/p} dx| ≥ σ.

We square this to get

∫ ∫ F (x)F (y)F (x + k)F (y + k)e^{2πi(x−y)ξ(k)/p} dxdy ≥ σ^{2}.

Writing y = x + u, and writing G_{u}(x) := F (x)F (x + u), this becomes

∫ ∫ G_{u}(x)G_{u}(x + k)e^{−2πiuξ(k)/p} dxdu ≥ σ^{2}p^{.}

Integrating this over all k ∈ B, we obtain

∫ (∫ ∫ G_{u}(x)G_{u}(x + k)H_{u}(k) dxdk) du ≥ σ^{3}

where H_{u}(k) := χ_{B}(k)e^{−2πiuξ(k)/p}. But by Proposition 2.4, we have that

| ∫ ∫ G_{u}(x)G_{u}(x + k)H_{u}(k) dxdk| ≲ ∥Ĥ_{u}∥_{∞}

since G_{u} is bounded. Thus we have

∫ ∥Ĥ_{u}∥_{∞}du ≥ σ^{3}.

Thus we must have ∥Ĥ_{u}∥_{∞} ≳ σ^{C} for at least O(σ^{C}p) values of u. For all such u, we have ∑_{η∈Z/pZ} |Ĥ_{u}(η)|^{4} ≳ σ^{C}; thus we have

∫ ∑_{η∈Z/pZ} |Ĥ_{u}(η)|^{4}du ≥ σ^{C}.

Note however that

Ĥ_{u}(η) = ∫_{B} e^{−2πi(ηk+uξ(k))} dk = ∫_{Ω} e^{−2πi(k,ξ)·(η,u)} dkdξ = χ̂_{Ω}(η, u)

where we give Ω the product of normalized measure dk and counting measure dξ. Thus by Plancherel

∫ ∑_{η∈Z/pZ} |Ĥ_{u}(η)|^{4}du = ∥χ_{Ω} ∗ χ_{Ω}∥_{2}^{2} = p^{−3}|{a, b, c, d ∈ Ω : a + b = c + d}|.

Thus we have

|{a, b, c, d ∈ Ω : a + b = c + d}| ≳ σ^{C}p^{3} ≳ σ^{C}|Ω|^{3}.

In other words, Ω is partly closed under addition, in the language of last week’s notes. Thus by the Balog-Szemeredi theorem, there exists Ω′ ⊆ Ω with |Ω′| ≳ σ^{C}|Ω| such that Ω′ is totally closed under addition, |Ω′ + Ω′| ≲ σ^{C}|Ω′|. By Freiman’s theorem (adapted to Z/pZ × Z/pZ; this is not a torsion-free abelian group, but the argument still essentially extends), Ω′ is thus contained inside a proper generalized arithmetic progression P of rank C(σ) and size at most C(σ)p, thus in particular |Ω′| ≳ C(σ)|P |. But this progression P can be partitioned into one-dimensional progressions of size at least ≳ p^{c(σ)}; thus by the pigeonhole principle we can thus find a one-dimensional arithmetic progression Q of size at least ≳ p^{c(σ)} such that

|Ω ∩ Q| ≥ |Ω′ ∩ Q| ≳ c(σ)|Q|.

This progression Q takes the form

Q := {(k, ak + b : k ∈ R}

where R is an arithmetic progression in Z/pZ of size ≳ p^{c(σ)}, and a, b ∈ Z/pZ. Thus we have

|{ \atop \overline{F (x)}F (x + k)}(ak + b)| ≥ σ

for at least c(σ)|R| values of k ∈ R. In particular we have

∑_{k∈R} |{ \atop \overline{F (x)}F (x + k)}(ak + b)|^{2} ≥ c(σ)|R|.

To obtain a contradiction, it will thus suffice to show the following “localized, linearized” form of quadratic uniformity:

Proposition 3.3. Let A′ be a subset of Z/pZ of density δ + O(ε), which obeys the conclusions of Proposition 2.2 (i.e. A′ has uniform density on reasonably long arithmetic progressions). Then, if p is large enough, then

∑_{k∈R} |{ \atop \overline{F (x)}F (x + k)}(ak + b)|^{2} = o(|R|)

for all a, b ∈ Z/pZ and all arithmetic progressions R of size at least |R| ≥ M_{2} = M_{2}(M_{1}, δ, ε).

We now prove this in the next section to finish the proof of Gowers’ theorem.

4. Linearized quadratic uniformity

Let R be a reasonably long arithmetic progression, and let a, b be in Z/pZ. We now have to bound the expression

∑_{k∈R} |{ \atop \overline{F (x)}F (x + k)}(ak + b)|^{2}.  (5)

Since

{ \atop \overline{F (x)}F (x + k)}(ak + b) = ∫ \overline{F (x)}F (x + k)e^{−2πi(ak+b)x/p} dx

we can write

|{ \atop \overline{F (x)}F (x + k)}(ak+b)|^{2} = ∫ ∫ \overline{F (x)}F (y)F (x+k)\overline{F (y + k)}e^{−2πi(ak+b)(x−y)/p} dxdy.

Making the substitution y = x + u, we can thus rewrite (5) as

∫ \overline{F (x)} ∑_{k∈R} ∫ F (x + u)F (x + k)\overline{F (x + u + k)}e^{2πi(ak+b)u/p} du dx.

We need to show that this is o(|R|). It suffices to prove this uniformly in x, i.e. it suffices to show that

| ∑_{k∈R} ∫ F (x + u)F (x + k)\overline{F (x + u + k)}e^{2πi(ak+b)u/p} du| = o(|R|).

By translation invariance we may take x = 0:

| ∑_{k∈R} ∫ F (u)F (k)\overline{F (u + k)}e^{2πi(ak+b)u/p} du| = o(|R|).

Now for the key trick. The phase function (ak + b)u is bilinear in k and u. Thus we can write it (mod p) as

(ak + b)u = Q_{1}(u) + Q_{2}(k) + Q_{3}(u + k)

for some (inhomogeneous) quadratic polynomials Q_{1}, Q_{2}, Q_{3} with integer coefficients. Thus it will suffice to show

| ∫ ∫ F_{1}(u)F_{2}(k)F_{3}(u + k) dudk| = o(|R|/p),  (6)

where

F_{1}(u) := F (u)e^{2πiQ_{1}(u)/p}

F_{2}(k) := F (k)e^{2πiQ_{2}(k)/p}χ_{R}(k)
F_{3}(x) := \overline{F (x)}e^{2πiQ_{3}(x)/p}.

At this point we shall oversimplify the argument for sake of exposition, and clean up the oversimplification later.

The left-hand side of (6) is T (F_{1}, F_{2}, F_{3}), and F_{1} and F_{3} are clearly bounded in L^{2}. Thus by Proposition 2.4 it thus suffices to show that

∥F̂_{2}∥_{∞} = o(|R|/p),

or in other words

∑_{k∈R} F (k)e^{2πiQ_{2}(k)/p}e^{−2πiξk/p} = o(|R|).

The linear phase −ξk can be absorbed into the arbitrary quadratic phase Q_{2}, and so it suffices to show

Proposition 4.1. For any progression R of length at least M_{2}, and any quadratic polynomial Q(k) with integer coefficients, we have

∑_{k∈R} F (k)e^{2πiQ(k)/p} = o(|R|).

This is a much stronger version of Lemma 2.3, which dealt with linear phase functions instead of quadratic ones, and worked on all of Z/pZ instead of localizing to the relatively short interval R. As it turns out, this Proposition is not quite true (and so this proof is not quite rigorous), however we will indicate the fix needed for this proposition a bit later.

Proof (Informal) As mentioned above, we cannot quite prove this proposition using only the hypothesis we have, which is the upper bound

F ∗ \frac{χ_{P}}{|P |}(x) ≲ ε

for all x and all progressions P of length at least M_{1}. However, we can derive it if we assume that we can have the lower bound as well as the upper bound:

|F ∗ \frac{χ_{P}}{|P |}(x)| ≲ ε = o(1).  (7)

As mentioned earlier, we do not actually have this estimate, except in an L^{1}- averaged sense; so as it turns out we only get an L^{1}-averaged version of this proposition, but this turns out to be sufficient to close the argument. More on this later.

Anyway, suppose we have (7). The idea is to split R into sub-progressions, on which Q(k)/p is essentially constant (mod 1), more precisely

Lemma 4.2. If M_{2} is sufficiently large, then one can partition R as the disjoint union of progressions P_{1}, …, P_{K}, such that each progression P_{j} is of length between M_{1} and 2M_{1}, and such that e^{2πiQ(k)/p} is within o(1) of a constant c_{j} on each progression P_{j}.

Assuming this lemma and (7), we have

∑_{k∈P_{j}} F (k)e^{2πiQ(k)/p} = c ∑_{k∈P_{j}} F (k) + o(|P_{j}|) = co(|P_{j}|) + o(|P_{j}|) = o(|P_{j}|)

and the claim follows by summing over j.

It remains to prove the lemma. By applying a linear transformation we may assume that R = {1, 2, …, r} for some r ≥ M_{2}.

Now we write Q(k) = ak^{2} + bk + c. We need to partition R into progressions P_{j} for which Q/p is essentially constant mod p, or more precisely

∥\frac{ak^{2} + bk + c − C_{j}}{p} ∥ = o(1)

for all k ∈ P_{j}, where ∥x∥ denotes the distance from x to the nearest integer. Another way of saying this is that

∥\frac{a(k^{2} − (k′)^{2}) + b(k − k′)}{p}∥ = o(1)

for all k, k′ ∈ P_{j}.

We first observe from Weyl’s theorem on the distribution of squares^{1} that we can find 1 ≤ d ≤ C(M_{1}, ε) such that

∥\frac{ad^{2}}{p} ∥ = o(M_{1}^{−100}).

We can then partition R into progressions Q_{i} of length ∼ M_{1}^{10} and spacing d. Let Q_{i} = {k_{0} + jd : j = O(M_{1}^{10})} be one of these progressions. Then if k = k_{0} + jd and k′ = k_{0} + j′d, ten

∥\frac{a(k^{2} − (k′)^{2}) + b(k − k′)}{p}∥ = ∥\frac{a(j^{2} − (j′)^{2})d^{2}}{p} +\frac{(2ak_{0} + bd)(j − j′)}{p}∥ = ∥\frac{(2ak_{0} + bd)(j − j′)}{p}∥+o(1)

by choice of d. So now we use Kronecker’s theorem^{2} to find a number J = O(M_{1}^{5}) such that

∥\frac{(2ak_{0} + bd)}{p}J∥ = O(M_{1}^{−5}).

If we then divide Q_{i} into progressions P_{s} of length between M_{1} and M_{1}, and of spacing Jd, we thus have

∥\frac{(2ak_{0} + bd)(j − j′)}{p}∥ = O(M_{1}^{−4}) = o(1)

∥ \frac{ad^{2}}{p} ∥ ≲ D^{−1/8}.

1This theorem states that the integer parts of ∥αn^{2})_{n=1}^{∞} are uniformly distributed if α is irrational. There is a quantitative version of this which says that these integer parts are “approximately uniformly distributed” if α is not too close to a rational of small denominator. On the other hand, if α is close to a rational of small denominator, then αn^{2} is close to an integer quite often. We omit the precise treatment of Weyl’s theorem here due to lack of time; however Gowers [2] has shown that given any a ∈ Z/pZ and any integer D > 1, we can find 1 ≤ d ≤ D such that

2This is the same as Weyl’s theorem, but for αn instead of αn^{2}: specifically, given any α and any N, there exists 1 ≤ n ≤ N such that ∥αn∥ ≲ 1/N. Actually the argument here is quite simple, based on the pigeonhole principle; at least two of the multiples of α must be within 1/N of each other, so the difference will be within O(1/N) of the nearest integer.

for all k_{0} + jd, k_{0} + j′d ∈ P_{s} (so that (j − j′)/J = O(M_{1})) and the claim follows.

The problem with this Proposition, of course, is that assumes (7), when in fact we only have this bound on the average in an L^{1} sense. If one works one’s way through the above argument, this implies that we have the following weaker averaged version of the Proposition: if R is as above, and for each y ∈ Z/pZ we assign a quadratic polynomial Q_{y}, then we have

∫ | ∑_{k∈R+y} F (k)e^{2πiQ_{y}(k)/p}| dy = o(|R|).

It turns out that this is still enough to prove (6). The trick is to partition the u variable into translates of R, apply the preceding argument to each translate, and then average up. We omit the details.

5. Exercises

• Q1. Let p be a large prime and 0 < δ < 1. Let A be a random subset of Z/pZ, formed by letting each element of Z/pZ lie in A with an independent probability of δ.

(a) Show that the expected number of proper arithmetic progressions in A is exactly δ^{3}p(p − 1).

(b) Let f := χ_{A} − δ. Show that for any frequency ξ, we have

E(exp(\sqrt{p}Ref̂(ξ)) ≲ 1

where the implicit constant is allowed to depend on δ. Hint: write

\sqrt{p}Ref̂(ξ) = ∑_{j=1}^{p} p^{−1/2} cos(2πjξ/p)X_{j}

where the X_{j} are iid random variables which equal 1 − δ with probability δ, and −δ with probability 1−δ (so in particular X_{j}, and all products of distinct X_{j}, have mean zero). Now argue as in the dissociated set estimates in the last set of notes.

A similar estimate obtains if Ref̂ is replaced by −Ref̂ or ±Imf̂. Conclude that one has ∥f̂∥_{∞} ≲ p^{−1/2} log p with probability at least 1 − p^{−100}.

• Q2. Given the bounds

N(δ) ≤ CN(δ + cδ)^{C}.

Also, we have N(δ) < 10 when δ > 0.9, deduce a bound of the form

N(δ) ≤ exp(exp(Cδ))

for all 0 < δ ≤ 1. (Use induction. It may help to make the constants C more explicit to distinguish them from each other (i.e. use C_{1}, C_{2}, etc.)

• Q3. Let A be a subset of Z/pZ of density |A| = δp, and suppose that χ_{A} − δ is linearly uniform, thus |χ̂_{A}(ξ)| = o(1) for all ξ ≠ 0. Let P be a proper arithmetic progression in Z/pZ of size |P | ∼ p. Show that |A ∩ P | = (δ + o(1))|P |. Thus we have a partial converse to Roth’s argument (which derives linear uniformity from uniform density on moderately long progressions); given linear uniformity, we can derive uniform density on very long progressions. (Hint: by an affine transformation we may assume that P is an interval. Use Parseval to estimate ∫ (χ_{A} − δ)ψ, where ψ is a suitable bump function which is supported on P and equals 1 on most of P.

• Q4. Let p be an odd prime. Let f be the function f(x) := exp(2πix^{2}/p) on Z/pZ. Show that ∥f∥_{∞} = 1, that ∥f̂∥_{∞} = p^{−1/2}, but that for every k,

∥{ \atop f(· + k)\overline{f}}∥_{∞} = 1. Thus f is linearly uniform but not quadratically uniform.

• Q5. Let f(x) be any bounded function on Z/pZ, thus ∥f∥_{∞} ≲ 1. Show that the statement ∫_{Z/pZ} |f(x)| = o(1) is true if and only if f(x) = o(1) for most x ∈ Z/pZ.

• Q6. Let f(x), g(x), h(x) be maps from one abelian group Z to another Z′ such that we have the identity f(a) + g(a + r) + h(a + 2r) = c for all a, r ∈ Z and some fixed c ∈ Z′. Show that f and g and h are affine homomorphisms from Z to Z′ (e.g. f(x) = F (x) + k, where k ∈ Z′ and F is a genuine homomorphism from Z to Z′). Hint: first normalize so that f(0) = g(0) = h(0) = 0. (Why is this result analogous to Proposition 2.4?)

• Q7* (a). Let f(x), g(x), h(x), k(x) be maps from one abelian group Z to another Z′ such that we have the identity f(a) + g(a + r) + h(a + 2r) + k(a + 3r) = c for all a, r ∈ Z and some fixed c ∈ Z′. Show that for every k ∈ Z, the function f(x + k) − f(x) is an affine homomorphism from Z to Z′, thus f(x + k) − f(x) = ϕ(k)(x) + c(k), where ϕ(k) is a homomorphism from Z to Z′ and c(k) is an element of Z′. (Why is this result analogous to the statement that quadratic uniformity implies the expected number of arithmetic progressions of length 4?)

(b) Show that the map k → ϕ(k) is itself a homomorphism (from Z to Hom(Z, Z′)). Conclude that f is an affine quadratic form, i.e. f(x) = Q(x, x) + L(x) + C for some bilinear form Q : Z × Z → Z′, some linear form (i.e. homomorphism) L : Z → Z′, and some constant C ∈ Z′. Similarly for g, h, k. (Why is this result analogous to the claim that the set Ω of resonant frequencies is partly closed under addition?)

References

[1] T. Gowers, A new proof of Szemeredi’s theorem for arithmetic progressions of length 4, GAFA 8 (1998), 529-551.

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

[3] K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 245-252.

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

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

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

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