E. SZEMERÉDI: “INTEGER SETS CONTAINING NO ARITHMETIC PROGRESSIONS”

AN EXPOSITION^{2} BY VSEVOLOD F. LEV

About the same time, Heath-Brown [H87] and Szemerédi [S90] published identically named papers where, improving Roth’ theorem on three-term arithmetic progressions, they established the following result.

Theorem 1 (Heath-Brown, Szemerédi). There is an absolute constant γ > 0 such that if N is a sufficiently large integer, and A ⊆ [1, N] is an integer set of density at least (log N)^{−γ}, then A contains a three-term arithmetic progression.

The proofs given by Heath-Brown and Szemerédi are related both ideologically and historically, but the relation is not easy to explain; see Heath-Brown’s Math-SciNet review on Szemerédi’s paper. It seems, anyway, that Szemerédi’s proof is more transparent, and most definitely so when compared to subsequent proofs due to Bourgain who managed to obtain even better values for the constant γ. Once this constant is mentioned, we notice that the actual value obtained below is ridiculously small; namely, γ = 2^{−20}. Szemerédi claims that using his approach one can get up to γ = 1/4, and Heath-Brown remarks that “it is clear that γ = 1/3 is the limit of the method”. The truth is, I would be very interested to learn exactly how the argument below is to be modified to produce values of γ, any close to the aforementioned 1/4 and 1/3.

Some modifications were introduced to Szemerédi’s method by Green [G], whose exposition of [S90] we mostly follow below, with minor technical simplifications and in modern-style notation, which we now introduce for the convenience of the reader and to make this write-up self-contained.

1. Fourier transform: the notation

The basic tool used is Fourier transform on the group ℤ_{N}. This involves working with this group itself and with the dual character group ℤ̂_{N}. We use normalized Haar measure (the “expectation measure”) for integration on ℤ_{N} and counting measure for integration on ℤ̂_{N}. Practically, this means, for instance, that the Fourier transform of a function f: ℤ_{N} → ℂ is defined by

2This is actually an exposition of an exposition; hence an exposition squared!

f̂(r) := E_{x∈ℤ_{N}}f(x) e_{N}(−rx),

the norms of this function by

∥f∥_{p}^{p} := E_{x∈ℤ_{N}}|f(x)|^{p}; p ≥ 1,

and its convolution with yet another function g: ℤ_{N} → ℂ by

(f ∗ g)(z) := E_{x∈ℤ_{N}}f(x)g(z − x),

whereas for two functions f̃, g̃: ℤ̂_{N} → ℂ the norms and convolution are

∥f̃∥_{p}^{p} := ∑_{r∈ℤ̂_{N}} |f̃(r)|^{p}; p ≥ 1

and

(f̃∗ g̃)(u) := ∑_{r∈ℤ̂_{N}} f̃(r)g̃(u − r),

respectively. (Our definition of the convolution is slightly non-standard in omitting the conjugate on the second operand. This little twist makes the things a bit lighter in our particular situation.) Thus, Fourier transform of a product satisfies

f̂ · g = f̂∗ ĝ,

the dual of which is

{ \atop f ∗ g} = f̂· ĝ.

Furthermore, the inversion formula takes the shape

f(x) = ∑_{r∈ℤ̂_{N}} f̂(r) e_{N}(rx); f: ℤ_{N} → ℂ

and Parseval’s identity is

∥f̂∥_{2} = ∥f∥_{2}.

Notice that for a fixed function f: ℤ_{N} → ℂ the norms ∥f∥_{p} increase as p grows, whereas for f̃: ℤ̂_{N} → ℂ the norms ∥f̃∥_{p} decay.

We also need Young’s inequality, which is as follows: if p, q, s ≥ 1 satisfy

\frac{1}{p} + \frac{1}{q} = 1 + \frac{1}{s},

then for any two functions f, g: ℤ_{N} → ℂ we have

||f ∗ g||_{s} ≤ ||f||_{p}||g||_{q},

and for any two functions f̃, g̃: ℤ̂_{N} → ℂ,

||f̃∗ g̃||_{s} ≤ \frac{1}{N} ||f̃||_{p}||g̃||_{q}.

The latter is particularly useful for estimating the norms of the Fourier transform of a product, as follows:

∥f̂ · g∥_{s} ≤ \frac{1}{N} ∥f̂∥_{p}∥ĝ∥_{q}.

2. From progression-free sets in [1, N] to biased sets in ℤ_{N}

The two major differences between Roth’s and Szemerédi’s methods is the way the latter passes back and forth between progression-free sets in [1, N] and those in ℤ_{N} (much fewer transitions is needed), and the fact that Szemerédi uses several large Fourier coefficients, instead of just one, as Roth does. We start with a somewhat informal explanation of the second point.

Let A ⊆ ℤ_{N} be a set of density α := E_{x∈ℤ_{N}}1_{A}(x), free of three-term progressions. We have then

∑_{r}(ˆ1_{A}(r))^{2} ˆ1_{A}(−2r) = N^{−1}α,

whence, writing f := 1_{A} − α for the balanced function of 1_{A} (so that f̂(r) = ˆ1_{A}(r) for r ≠ 0 and f̂(0) = 0), we have

− ∑_{r}(f̂(r))^{2}f̂(−2r) = (α^{2} − N^{−1}) α.  (1)

Using Parseval, we conclude that

(α^{2} − N^{−1}) α ≤ ∥f̂∥_{∞} · ∥f̂∥_{2}^{2} < α ∥f̂∥_{∞},

and hence there exists r ∈ ℤ_{N} with |f̂(r)| ≳ α^{2}; this is Roth. Using, instead, Hölder’s inequality in (1), we get

∥f̂∥_{3}^{3} ≥ (α^{2} − N^{−1}) α.  (2)

Applying Parseval’s identity one easily recovers Roth’s estimate

∥f̂∥_{∞} > α^{2} − N^{−1};

consequently, (2) is to be considered a stronger inequality.

With this discussion in mind, for c > 0 we say that a set A ⊆ ℤ_{N} is c-biased if its balanced function f satisfies

∥f̂∥_{3}^{3} ≥ cα^{3},

where α is the density of A.

4 INTEGER SETS CONTAINING NO PROGRESSIONS

Given an integer progression-free set A ⊆ [1, N], one cannot say right away that its canonical image in ℤ_{N} is c-biased for some fixed c > 0, as this image need not be progression-free. Szemerédi has shown, however, that there exists integer M ≈ N such that the image of A in ℤ_{M} has “fewer than expected” progressions. Green pursues another approach showing that, actually, the image of A in ℤ_{N} does have a bias; as he acknowledges, this approach is inspired by a paper of Bourgain. This is practically implemented in the following lemma.

Lemma 1. Let N be a positive integer and suppose that A ⊆ [1, N] is a progressionfree set of density α > 2^{5}N^{−1/2}. Then either there exists a progression in [1, N] of length at least 5N/12, on which A has density at least 1.08α, or the canonical image of A in ℤ_{N} is 2^{−14}-biased.

Proof. To simplify the notation and keep technical details to a minimum, suppose that N is divisible by 12. (In fact, if it is not divisible, then the constants in the statement of the lemma may need some minor adjustment.)

It is convenient to shift A to assume that it is a progression-free subset of the interval (−N/2, N/2]. Let I := (−N/12, N/12] (mod N) and let ν := 1_{I} ∗ 1_{I}; thus, ν(x) is the number of representations of x ∈ ℤ_{N} as a sum of two elements from I, normalized by dividing by N. In particular,

(i) ν(0) = ∥ν∥_{∞} < 1/6; (ii) if x ∈ I, then ν(x) ≥ 1/12; (iii) ν vanishes outside (−N/6, N/6] (mod N). Let 1_{A} denote the indicator function of the canonical image of A in ℤ_{N} (a slight

abuse of notation, not leading to any confusion). Writing f for the corresponding balanced function and letting g := 1_{A} · ν, we get

∑_{r} ˆ1_{A}(r)ĝ(r)ĝ(−2r) = E\begin{matrix}x,y,z∈ℤ_{N} \\ x+y=2z \end{matrix} ˆ1_{A}(x)ˆ1_{A}(y)ˆ1_{A}(z)ν(y)ν(z) ≤ α(36N)^{−1}; (3)

for, any arithmetic progression in ℤ_{N} with the midterm and one of the end-terms in (−N/6, N/6] is a genuine one, remaining a progression if considered a subset of (−N/2, N/2].

The contribution of the term with r = 0 to the left-hand side of (3) is large, unless A has unproportionally few elements in I. Indeed, assuming, say, |A ∩ I| ≥ 0.1αN, in view of (ii) we have

ĝ(0) = E_{x}1_{A}(x)ν(x) ≥ \frac{1}{12} E_{x}1_{A}(x)1_{I}(x) = \frac{1}{12N} |A ∩ I| ≥ 2^{−7}α,

INTEGER SETS CONTAINING NO PROGRESSIONS 5

which implies

ˆ1_{A}(0)(ĝ(0))^{2} ≥ 2^{−14}α^{3}.  (4)

However, if |A ∩ I| < 0.1αN, then one of the intervals (−N/2, −N/12] (mod N) and (N/12, N/2] (mod N) contains at least (9/20)αN elements of A, completing the proof in this case. Thus, we can assume that (4) holds, whence

∑_{r} |f̂(r)||ĝ(r)||ĝ(−2r)| ≥ (2^{−14}α^{2} − (36N)^{−1}) α > 2^{−15}α^{3}

by (3) and the assumption α > 2^{5}N^{−1/2}. Applying Hölder’s inequality we get

∥f̂∥_{3}∥ĝ∥_{3}^{2} > 2^{−15}α^{3},  (5)

whereas by Young’s inequality

∥ĝ∥_{3} = ∥{ \atop 1_{A} · ν}∥_{3} = ∥ˆ1_{A} ∗ ν̂∥_{3} ≤ ∥ˆ1_{A}∥_{3}∥ν̂∥_{1} = (α^{3} + ∥f̂∥_{3}^{3})^{1/3} ∥ν̂∥_{1}.  (6)

Furthermore, by the definition of ν we have ν̂ = (ˆ1_{I})^{2}, and therefore, using Parseval,

∥ν̂∥_{1} = ∥ˆ1_{I}∥_{2}^{2} = ∥1_{I}∥_{2}^{2} = \frac{1}{36}.  (7)

Combining (5), (6), and (7), we obtain

2^{−15}α^{3} < ∥f̂∥_{3} (α^{3} + ∥f̂∥_{3}^{3})^{2/3} 6^{−4}.

A simple computation now confirms the assertion: if ∥f̂∥_{3}^{3} < 2^{−14}α, then

2^{−15} < 2^{−14/3} (1 + 2^{−14})^{2/3} 6^{−4},

which is wrong. □

3. From bias to density increment

We say that a progression in ℤ_{N} is non-overlapping if its difference d, considered as a number in [1, N/2], and length L satisfy dL < N. Non-overlapping progressions are important as any such progression is a union of at most two genuine progressions.

The bridge between large Fourier coefficients and “rich” (non-overlapping) progressions is established by the following lemma.

Lemma 2. Let N > 1 be an integer and A ⊆ ℤ_{N} a non-empty set of density α, and let f denote the balanced function of A. Then for any subset R ⊆ ℤ̂_{N} \ {0} with |R| ≤ 2^{−4} log N there exists a non-overlapping arithmetic progression of length at least N^{1/(3|R|)}, on which A has density at least

α + \frac{1}{4α} ∑_{r∈R} |f̂(r)|^{2}.

Remark. As the proof shows, we could have replaced N^{1/(3|R|)} with something like \frac{1}{2π}N^{1/(|R|+1)}, dropping at the same time the assumption |R| ≤ 2^{−4} log N altogether. While this form of the lemma would be a a tiny bit stronger formally, the coefficient 1/2π and the exponent 1/(|R| + 1) are a mess to handle, and we prefer to get rid of them at an early stage.

Proof. For a progression P ⊆ ℤ_{N}, let μ_{P} := 1_{P} /E_{x}1_{P} (x) denote the “normalized measure” on P. We have (1_{A} ∗ μ_{P})(z) = |A ∩ (z − P)|/|P |, and accordingly, we want to choose P so that ∥1_{A} ∗ μ_{P} ∥_{∞} is large.

Not surprisingly, our starting point is the quantity ∥1_{A} ∗ μ_{P} ∥_{2}^{2} which, on the one hand, is equal to

∥{ \atop 1_{A} ∗ μ_{P}} ∥_{2}^{2} = ∥ˆ1_{A} · μ̂_{P} ∥_{2}^{2},

and on the other hand, satisfies

∥1_{A} ∗ μ_{P} ∥_{2}^{2} ≤ ∥1_{A} ∗ μ_{P} ∥_{1} ∥1_{A} ∗ μ_{P} ∥_{∞} = α∥1_{A} ∗ μ_{P} ∥_{∞},

the last step following from

∥1_{A} ∗ μ_{P} ∥_{1} = E_{z}E_{x}1_{A}(x)μ_{P} (z − x) = E_{x}1_{A}(x) · E_{y}μ_{P} (y) = α.

Thus,

∥1_{A} ∗ μ_{P} ∥_{∞} ≥ α^{−1} ∥ˆ1_{A} · μ̂_{P} ∥_{2}^{2}.  (8)

In order to ensure that ∥ˆ1_{A} · μ̂_{P} ∥_{2} is large, we choose P so that μ̂_{P} is large on every element of R. Since

μ̂_{P} (r) = E_{x}μ_{P} (x)(e_{N}(−rx) − 1) + 1,  (9)

we select the difference d of P so that it is “nearly orthogonal” to every r ∈ R, and take P to consist of small multiples of d.

More precisely, by a well-known application of the box principle, there exists d ∈ ℤ_{N} \ {0} such that for every r ∈ R ∪ {1}, the distance from dr to 0 in ℤ_{N} is at most N^{1−1/(|R|+1)}, and we set P := {kd: |k| ≤ N^{1/(|R|+1)}/4π}. The purpose of requesting d to be “nearly orthogonal” to 1 is that this enforces that P be non-overlapping, as follows immediately from our definition of a non-overlapping progression.

By the choice of P, for each r ∈ R and x ∈ P we have

| e_{N}(−rx) − 1| < 2πN^{−1/(|R|+1)} · N^{1/(|R|+1)}/4π ≤ 1/2,

whence |μ̂_{P} (r)| > 1/2 by (9). Consequently, taking into account that μ̂(0) = 1, we have

∥ˆ1_{A} · μ̂_{P} ∥_{2}^{2} ≥ α^{2} + \frac{1}{4} ∑_{r∈R} |f̂(r)|^{2};

combined with (8), this gives the desired estimate. It remains to observe that the length of P is

2 ⌊N^{1/(|R|+1)}/4π⌋ + 1 ≥ \frac{1}{4π} N^{1/(|R|+1)} > N^{1/(3|R|)}.

□

We now leave the ground of Fourier analysis and enter the area of combinatorics (or just elementary mathematics). Accordingly, we switch to the appropriate notation.

Suppose that A ⊆ [1, N] is a progression-free set and let f be the balanced function of the canonical image of A in ℤ_{N}. For j ∈ [1, N − 1] denote by δ_{j} the jth largest value of the sequence {|f̂(z)|/f̂(0)}_{r∈ℤ_{N} \{0}}; thus, δ_{j} ∈ [0, 1] for each j ∈ [1, N − 1], and by Parseval,

∑_{j=1}^{N−1} δ_{j}^{2} < α^{−1}.  (10)

Furthermore, Lemma 1 shows that

∑_{j=1}^{N−1} δ_{j}^{3} ≥ c,  (11)

with c = 2^{−14}, unless A is extremely sparse or there is a long progression on which the density of A increases. On the other hand, Lemma 2 shows that in order to ensure the existence of a sufficiently long progression on which the density increases, one needs to find a small q ≥ 1 such that δ_{1}^{2} + ⋯ + δ_{q}^{2} is large. Deriving an assertion of this sort from (10) and (11) is the subject of our next lemma.

Lemma 3. Suppose that N ≥ 2 is an integer and α, c are positive real numbers with α ≥ 8c^{−2/3}(log N)^{−1/5}. If 1 ≥ δ_{1} ≥ ⋯ ≥ δ_{N−1} ≥ 0 satisfy (10) and (11), then there exists an integer 1 ≤ q ≤ 2^{−4} log N such that

∑_{j=1}^{q} δ_{j}^{2} ≥ \frac{1}{4} c^{2/3}q^{1/5}.

Proof. If δ_{q} ≤ \frac{1}{2} c^{1/3}q^{−2/5} were true for each q ∈ [1, N − 1], then we would have

∑_{j=1}^{N−1} δ_{j}^{3} ≤ \frac{1}{8} c ζ(6/5) < c,

contradicting (11). It follows that there exists q ∈ [1, N − 1] with

δ_{q} > \frac{1}{2} c^{1/3}q^{−2/5}.

This gives

∑_{j=1}^{q} δ_{j}^{2} ≥ qδ_{q}^{2} ≥ \frac{1}{4} c^{2/3}q^{1/5},

and the condition q ≤ 2^{−4} log N follows automatically from this estimate and (10):

q < (4c^{−2/3}α^{−1})^{5} < 2^{−4} log N.

□

Remark. How can we guarantee in Lemma 3 the existence of 1 ≤ q ≤ 2^{−4} log N if N is small? Working out the answer is instructive!

4. The iteration step

We record the following immediate corollary of Lemmas 2 and 3.

Corollary 1. Let N ≥ 21 be an integer and suppose that A ⊆ ℤ_{N} is a c-biased set of density α ≥ 8c^{−2/3}(log N)^{−1/5}. Then there exists an integer q ≥ 1 and a non-overlapping progression of length at least N^{1/3q} on which A has density at least (1 + c^{2/3}q^{1/5}/16)α.

Now we pass from non-overlapping to genuine progressions.

Lemma 4. If η, α > 0 and a set A ⊆ ℤ_{N} has density at least (1 + η)α on a nonoverlapping progression P, then there is a genuine progression P′ of length at least ηα|P |/2 on which A has density at least (1 + η/2)α.

Proof. Suppose that P = P_{1} ∪ P_{2}, where P_{1} and P_{2} are genuine progressions. If |P_{1}| ≤ ηα|P |/2, then |A∩P_{2}| ≥ (1+η/2)α|P | which, of course, implies |P_{2}| > ηα|P |/2; thus, we can set P′ := P_{2} in this case. Similarly, if |P_{2}| ≤ ηα|P |/2, then we can set P′ := P_{1}. Finally, if both P_{1} and P_{2} have length at least ηα|P |/2, then we can define P′ to be the progression P_{i} on which A has higher density. □

Combining Corollary 1 and Lemma 4 we obtain

Corollary 2. Let N ≥ 2 be an integer and suppose that A ⊆ ℤ_{N} is a c-biased set of density α ≥ 8c^{−2/3}(log N)^{−1/5}. Then there exists an integer q ≥ 1 and a genuine progression of length at least 2^{−5}c^{2/3}q^{1/5}αN^{1/3q} on which A has density at least (1 + 2^{−5}c^{2/3}q^{1/5})α.

Combining the last corollary with Lemma 1 and observing that if N ≥ 2^{20}, then 8c^{−2/3}(log N)^{−1/5} > 2^{5}N^{−1/2}, we obtain

INTEGER SETS CONTAINING NO PROGRESSIONS 9

Proposition 1. Let N ≥ 2^{20} be an integer and suppose that A ⊆ [1, N] is a progression-free set of density α ≥ 8c^{−2/3}(log N)^{−1/5}, where c = 2^{−14}. Then at least one of the following holds:

(i) there exists a progression in [1, N] of length at least 5N/12, on which A has density at least 1.08α;

(ii) there exists an integer q ≥ 1 and a progression in [1, N] of length at least 2^{−5}c^{2/3}q^{1/5}αN^{1/3q} on which A has density at least (1 + 2^{−5}c^{2/3}q^{1/5})α.

Indeed, one can drop case (i) of Proposition 1, which is absorbed by case (ii) for q = 1. Along with the observation that 8c^{−2/3} < 2^{13} and 2^{−5}c^{2/3} > 2^{−15}, this results in

Proposition 1′. Let N ≥ 2^{20} be an integer and suppose that A ⊆ [1, N] is a progression-free set of density α ≥ 2^{13}(log N)^{−1/5}. Then there exist an integer q ≥ 1 and a progression in [1, N] of length at least 2^{−15}q^{1/5}αN^{1/3q} on which A has density at least (1 + 2^{−15}q^{1/5})α.

Deriving the desired result is now a matter of simple induction.

Theorem 2. There exists an absolute constant C such that if N is a positive integer and A ⊆ [1, N] has density at least C(log N)^{−γ}, where γ = 2^{−20}, then A contains an arithmetic progression.

Proof. Induction by N. For N < 2^{20} the assertion is true, provided C is large enough; suppose that N ≥ 2^{20} and that A ⊆ [1, N] is a progression-free set of density α ≥ C(log N)^{−γ}. By Proposition 1′, there are integer q ≥ 1 and M ≥ 2^{−15}q^{1/5}αN^{1/3q} such that [1, M] contains a progression-free set of density at least (1 + 2^{−15}q^{1/5})α. A straightforward verification shows that, under our assumptions, we have 2^{−15}q^{1/5}αN^{1/3q} > N^{1/4q}. Consequently, applying the induction hypothesis (Why is M < N? An exercise for the reader!), we get

(1 + 2^{−15}q^{1/5})α < C(log M)^{−γ} ≤ C (\frac{1}{4q} log N)^{−γ} ,

whence

1 + 2^{−15}q^{1/5} < (4q)^{γ}.

It is easy to see, however, that this is wrong: say, if q ≥ 2^{96} then

2^{−15}q^{1/5} > 2^{−16}q^{1/6}(4q)^{γ} ≥ (4q)^{γ},

and if q < 2^{96}, then

(4q)^{γ} = e^{γ log(4q)} < 1 + 2γ(log 4q) < 1 + 2^{−15}q^{1/5}.

□

5. Analysis and heuristic

What is the best value for γ one could hope to get from this approach? Let A be a progression-free subset of [1, N] of density α. If, by a miracle, we were able to conclude that A is actually sum-free when considered as a subset of ℤ_{N}, this would imply that A is 1-biased. Lemma 2 in the ideal world would say that, whenever R ⊆ ℤ̂_{N} \ {0}, there is a genuine progression in ℤ_{N} of length at least N^{1/|R|} on which A has density at least (1 + ∑_{r∈R} |f̂(r)|^{2})α. Lemma 3 would grant the existence of q ≥ 1 such that ∑_{j=1}^{q} δ_{j} ≥ q^{1/3}. (We couldn’t expect more: say, if δ_{j} = j^{−1/3}, then both (10) and (11) hold; for the latter, recall that c = 1.) As a result, we would find a (genuine) progression of length at least N^{1/q}, on which A has density at least (1 + q^{1/3})α. Now what we need for the induction step to go through with some constant γ is that

(log N^{1/q})^{−γ} < (1 + q^{1/3})(log N)^{−γ},

which essentially means γ < 1/3. This, most likely, is the heuristic behind Heath-Brown’s claim that 1/3 is the limit of the method.

Why in practice we were unable to get any close to γ = 1/3? There is one major point where where accuracy is wastefully lost: switching between progression-free sets in integers and those in cyclic groups. Perhaps, an improvement is possible if one employs Fourier analysis on integers?

References

[G] B. Green, Progressions of length 3 following Szemerédi, Unpublished exposition.

[H87] D.R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. (2) 35 (1987), 385–394.

[S90] E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hung. 56 (1990), 155–158.