Additive

and

Combinatorial Number Theory

———————————————————————————————————————

Contents

1 The Hales-Jewett Theorem  3

2 Roth’s Theorem  6

3 Weyl’s Inequality  10

4 Vinogradov’s Three Primes Theorem  15

5 The Geometry of Numbers  32

6 Freiman’s Theorem  40

7 Szemerédi’s Theorem  46

References  56

Notation  58

§1 The Hales-Jewett Theorem

The following theorem was proved in 1927 by van der Waerden [20], answering a conjecture of Schur:

Theorem 1.1. If the natural numbers are partitioned into two sets, then one set must contain arbitrarily long arithmetic progressions.

This result was proved before Ramsey’s Theorem, and led to a number of generalizations, with implications in Ramsey Theory. Theorem 1.1 can be rewritten as follows: for any pair of positive integers k, r, there exists an integer W = W (k, r) such that if [W] is r-coloured, then we may find a monochromatic k-term arithmetic progression.

In this section, an important theorem known as the Hales-Jewett Theorem [8] is proved. Consider the following notation. For x ∈ [k]^{N}, A ⊂ [N] and j ∈ [k] define

(x ⊕ jA)_{i} = \{ \begin{matrix}x_{i} & i ∉ A \\ j & i ∈ A \end{matrix}

A Hales-Jewett line is a set of the form {x ⊕ jA : 1 ≤ i ≤ k}, for some x ∈ [k]^{N} and A ⊂ [N], A ≠ ∅. The Hales-Jewett Theorem implies van der Waerden’s Theorem. To see this, represent points in the cube [k]^{N} by the coefficients in a base k expansion of non-negative integers less than k^{N}. Provided N is large enough, a monochromatic line exists, corresponding to a monochromatic arithmetic progression.

Hales-Jewett Theorem. Let k, r ∈ ℕ. Then there exists N such that if [k]^{N} is r-coloured, then it contains a monochromatic Hales-Jewett line. Proof. Let HJ(k, r) denote the smallest integer for which the theorem works. We must show HJ(k, r) is always finite. If k = 1 set N = 1. Suppose that N = HJ(i, r) has been found for each i < k and set i = k. Let N_{1} = HJ(k − 1, r2^{r−1}) and set

N_{i} = HJ(k − 1, r^{2^{r−i}k^{sr}})

for i = 1, 2, …, r, where s_{r} = ∑_{i<r} N_{i}. Let κ be an r-colouring of [k]^{∑ N_{i}} (which gives a colouring of [k]^{N_{1}} × ⋯ × [k]^{N_{r}} in the natural way). For x ∈ [k]^{N_{r}}, we find a colouring κ_{x} on [k]^{s_{r}} by sending (x_{1}, …, x_{r−1}) to κ(x_{1}, …, x_{r−1}, x). The number of such induced colourings κ_{x} is at most r^{k^{sr}} – the number of ways of colouring [k]^{s_{r}} with r colours. Let the distinct ones be κ_{i} : 1 ≤ i ≤ s. We therefore obtain an s-colouring of [k]^{N_{r}} where x is receives colour i if κ_{x} = κ_{i}. This induces an obvious s-colouring of [k − 1]^{N_{r}}, as [k − 1]^{N_{r}} ⊂ [k]^{N_{r}}. So, by definition of N_{r}, we can find z_{r} ∈ [k]^{N_{r}} and ∅ ≠ A_{r} ⊂ [N_{r}] such that κ_{z_{r}⊕jA_{r}} is the same function for 1 ≤ j ≤ k − 1. Set L_{r} = {z_{r} ⊕ jA_{r} : 1 ≤ j ≤ k}. Let κ_{x} be the colouring of [k]^{s_{r−1}} × L_{r} induced by κ with κ_{x}(x_{1}, x_{2}, …, x_{r−2}, z_{r} ⊕ jA_{r}) = κ(x_{1}, x_{2}, …, x_{r−2}, x, z_{r} ⊕ jA_{r}). The number of possible functions κ_{x} is now at most r^{2k^{s_{r−1}}}, where the factor of two appears since colourings don’t change as 1 ≤ j ≤ k − 1 By definition of N_{r−1}, we find z_{r−1}, A_{r−1} such that κ_{z_{r−1}⊕jA_{r−1}} is constant over j ∈ [k − 1] (as before). Continue this procedure until we have L_{1} × L_{2} × ⋯ L_{r} with κ(z_{1} ⊕ j_{1}A_{1}, …, z_{r} ⊕ j_{r}A_{r}), depending only on {i : j_{i} = i}. If we r-colour the sets ∅, {1}, {1, 2}, …, [r], we clearly find two of the same colour. Hence considering J = {i : j_{i} = k} in this range, there exist t and u such that the colour assigned under κ is the same when J = [t] as when J = [u]. If we let elements in any of the A_{i} : t < i ≤ u range from 1 to k, the colour assigned is still the same – we knew it wouldn’t change up to k − 1 and k is taken care of by definition of t and u. So, if

x = (z_{1} ⊕ kA_{1}, …, z_{t} ⊕ kA_{t}, z_{t+1} ⊕ 1A_{t+1}, …, z_{u} ⊕ 1A_{u}, …, z_{r} ⊕ 1A_{r})

and A = ⋃_{t<i≤u} A_{i}, then {x ⊕ jA : 1 ≤ j ≤ k} is a monochromatic line. □

This extends easily to a d-dimensional theorem. If we define a d-dimensional Hales-Jewett subspace of [k]^{N} to be a set of the form

{x ⊕ j_{1}A_{1} ⊕ j_{2}A_{2} ⊕ ⋯ ⊕ j_{d}A_{d} : 1 ≤ j_{i} ≤ k},

where A_{1}, A_{2}, …, A_{d} are disjoint and non-empty in [N], then for every k, r, d there exists an N such that, however [k]^{N} is r-coloured, there is a monochromatic d-dimensional Hales-Jewett subspace. Another way of viewing the Hales-Jewett theorem: if [N] is coloured with r colours, then there exist disjoint sets A_{0}, A_{1}, …, A_{k} such that A_{0}∪⋃_{i∈I} A_{i} are all monochromatic where I ⊂ [k]. The following remarkable inductive proof of the Hales-Jewett theorem is due to Shelah [14]:

Proof. Let M = HJ(k −1, r) and define N_{1} = r^{(k−1)^{M−1}} and N_{i} = r^{(k−1)^{M−i}}k^{N_{1}+...+N_{i−1}} for i = 2, 3, …, r. Let κ be an r-colouring of [k]^{N_{1}} × ⋯ × [k]^{N_{M}}. Given x ∈ [k]^{N_{M}}, let κ_{x} be the colouring of [k]^{N_{1}}×⋯×[k]^{N_{M−1}} induced by κ. There are at most rk^{N_{1}+...N_{M−1}} such colourings, so we can find two points x_{1} and x_{2} ,of the form (k − 1, …, k − 1, k, …, k), such that κ_{x_{1}} = κ_{x_{2}}. If the first m and first n co-ordinates of x_{1} and x_{2} are (k − 1), respectively, and A_{m} = (m, n], then κ_{z_{m}} ⊕jA_{m} is the same for j = k−1 and j = k, where z_{m} = x. Let L_{M} = {z_{M} ⊕ jA_{M} : 1 ≤ j ≤ k}. For each i, we have an induced colouring of [k]^{N_{1}} × ⋯ × [k]^{N_{i−1}} × L_{i+1} × ⋯ × L_{M}. There are at most r^{k^{N_{1}+...+N_{i−1}}}(k − 1)^{M−i} different colourings of this kind, so we find a line L_{i} ⊂ [k]^{N_{i}}, L_{i} = {z_{i} ⊕ jA_{i} : 1 ≤ j ≤ k} such that κ_{z_{i}⊕jA_{i}} is the same for j = k − 1, k. At the end of this process, we construct L_{1} × ⋯ × L_{M} so that κ, restricted to L_{1} × ⋯ × L_{M} does not vary over co-ordinate change from k − 1 to k. This completes the inductive step. □

This proof was a breakthrough in that it was the first to give primitive recursive bounds on the van der Waerden numbers. Erdős and Turán [4] hoped this could be achieved by finding, for each k ∈ ℕ, an o(N) function n_{k}(N) such that every subset of [N] of size at least n_{k}(N) contains an arithmetic progression of length k. We now look at this problem more closely.

§2 Roth’s Theorem

The following theorem was first proved by Szemerédi [17] using ingenious combinatorial techniques, and later by Fürstenburg [6], using methods in ergodic theory.

Szemerédi’s Theorem. Let A be a set of positive upper density in ℕ. Then A contains arbitrarily long arithmetic progressions.

Szemerédi actually proved more than this. Let n_{k}(N) denote the smallest integer such that any subset of n_{k}(N) elements taken from [N] contains an arithmetic progression of length k. Szemerédi established that n_{k}(N) = o(N) for each k, thus proving a conjecture of Erdős and Turán [4]. The proof used van der Waerden’s Theorem and Szemerédi’s Regularity Lemma, therefore the upper bound on the order of n_{k}(N) obtained can be no better than the bounds given by these theorems.

Roth [11] gave a remarkable analytic proof that n_{3}(N) = o(N) in 1954. Szemerédi proved it for the more difficult case k = 4 [16] which then generalized to the above theorem, for general k. We present the theorem of Roth here. The interest in this proof is that it gives a good lower bound on n_{3}(N) – n_{3}(N) ≤ cN/ log log N for some constant c > 0 – and that it offers the possibilty of generalization. Szemerédi’s Theorem was proved by markedly different techniques and Fürstenburg’s proof gives no bounds on the van der Waerden numbers.

Let n ∈ ℕ and f : ℤ_{N} → ℂ. The (discrete) Fourier transform f̂ of f is defined by f̂(r) = ∑_{s=0}^{N−1} f(s)ω^{rs}, where ω = exp(2πi/N). We define the convolution of f and g, f ∗ g by (f ∗ g)(r) = ∑_{t−u=r} f(t)\overline{g(u)}. The following properties are easily proved from the definition, and will be used throughout the material to follow. The first identity is known as Parseval’s Identity and the third will be called the convolution formula.

Lemma 2.2. The following properties hold for fourier transforms

\begin{matrix}(1) & ∑ |f̂(r)|^{2} = N ∑ |f(r)|^{2} \\ (2) & ∑ f̂(r) \overline{ĝ}(r) = N ∑ f(r) \overline{g}(r) \\ (3) & (f ∗ g)ˆ = f̂ \overline{ĝ} \\ (4) & N ∑ |(f ∗ g)(r)|^{2} = ∑ |f̂(r)|^{2}|ĝ(r)|^{2} \\ (5) & ∑ |f̂(r)|^{4} = N ∑_{a+b=c+d} f(a)f(b)\overline{f(c)f(d)} \end{matrix}

An arithmetic progression in ℤ is called a ℤ-arithmetic progression if it is an arithmetic progression when considered as a subset of ℤ.

Lemma 2.3. Let a, d ∈ ℤ_{N} with d ≠ 0 and let m ≤ N. Then the set A = {a, a + d, …, a + (m − 1)d} can be partitioned into fewer than 3m^{1/2} subsets, which are ℤarithmetic progressions. Proof. Let ℓ = ⌊m^{1/2}⌋ and consider the numbers {a, a + d, …, a + (m − 1)d}. At least two lie within N/ℓ of each other so there exists s ∈ [ℓ − 1] with −N/ℓ ≤ sd ≤ N/ℓ such that we split A into subprogressions, each with common difference sd. If P is one of them, then P can be partitioned into ℤ-arithmetic progressions, all but two of which have size at least ℓ ≥ m^{1/2}, as |sd| ≤ N/ℓ. So the whole set can be partitioned into at most m/m^{1/2} + 2s ≤ 3m^{1/2} ℤ-arithmetic progressions. □

The idea in the proof of Roth’s Theorem is that if a set A does not contain an arithmetic progression of length three, then Â has a large Fourier coefficient. This implies that A has an intersection with a long ℤ_{N}-arithmetic progression, where the density of A increases. As the density is bounded above by 1, and ℤ_{N}-arithmetic progressions are taken care of by the Lemma 2.3, this completes the argument, provided N is large enough.

Roth’s Theorem. There is a constant c > 0 such that for any N ∈ ℕ and A ⊂ [N] of size at least cN/ log log N, A contains an arithmetic progression of length three. Proof. In general, if X, Y and Z are subsets of ℤ_{N} with densities α, β, γ respectively, then the number of triples (x, y, z) ∈ X × Y × Z such that x + z = 2y (mod N) is N^{−1}|X||Y ||Z| + ∑_{r} X̂(r)Ŷ (−2r)Ẑ(r). Using Cauchy–Schwartz, the second term has modulus at most

N^{−1} max_{r≠0} |X̂(r)|(∑_{r} |Ŷ (−2r)|^{2})^{1/2}(∑_{r} |Ẑ(r)|^{2})^{1/2}.

Using Parseval’s Identity for Ŷ and Ẑ, this expression is βγN max_{r≠0} |X̂(r)|. Provided max |X̂(r)| ≤ \frac{1}{2}αβ^{1/2}γ^{1/2}z^{1/2}N, there are at least \frac{1}{2}αβγN^{2} triples of the required form as N^{−1}|X||Y ||Z| = αβγN^{2}. A non-trivial solution occurs if \frac{1}{2}αβγN^{2} > N. Now let A have density δ and B = \{a ∈ A : \frac{N}{3} < x < \frac{2N}{3} \}. We plan to show that A has a substantial intersection with, and higher density in, a long arithmetic progression P. If |B| ≤ δN/5, then A has density at least 6δ/5 in [0, N/3] or [2N/3, N), and we have the required arithmetic progression P, of length ⌊N/3⌋ or ⌊N/3⌋ + 1. Suppose |B| ≥ δN/5. Then there exists a non-trivial solution a + c = 2b with (a, b, c) ∈ A × B × B, or |Â(r)| ≥ δ^{2}N/10 for some r. In the first case, we have a ℤ-arithmetic progression of length three in A, as required. Partition the unit circle into M consecutive equal intervals I_{1}, I_{2}, …, I_{M} of diameter as close to δ^{2}/20 as possible. Define P_{j} = {x : ω^{−rx} ∈ I_{j}}. Then each P_{j} is an arithmetic progression in ℤ_{N} with common difference −r^{−1} (mod N) (the ℤ_{N} inverse of −r). Define f(x) = A(x) − δ. Then ∑ f(x) = 0 and f̂ = Â. So

δ^{2}N/10 ≤ |f̂(r)| = |∑_{x} f(x)ω^{−rx}| ≤ |∑_{j} ∑_{x∈P_{j}} f(x)ω^{−rx}| ≤ ∑_{j}| ∑_{x∈P_{j}} f(x)ω^{−rx}|.

Now fix j and let x_{j} ∈ P_{j}. Then

| ∑_{x∈P_{j}} f(x)ω^{−rx}| ≤ | ∑_{x∈P_{j}} f(x)ω^{−rx_{j}} | + | ∑_{x∈P_{j}} f(x)(ω^{−rx} − ω^{−rx_{j}} )|
≤ | ∑_{x∈P_{j}} f(x)| + ∑_{x∈P_{j}} \frac{δ^{2}}{20}
≤ | ∑_{x∈P_{j}} f(x)| + \frac{δ^{2}|P_{j}|}{20}.

Summing over j, we find \frac{δ^{2}N}{10} ≤ ∑_{j=1}^{M}|∑_{x∈P_{j}} f(x)| + \frac{δ^{2}}{20} ∑_{j=1}^{M} |P_{j}|. Since the last sum is N, we get ∑_{1}^{M}|∑_{P_{j}} f(x)| ≥ \frac{δ^{2}N}{20} . Recalling that ∑ f(x) = 0, we find ∑_{1}^{M}(|∑_{P_{j}} f(x)| + ∑_{P_{j}} f(x)) is at least \frac{δ^{2}N}{20} . So there exists j such that ∑_{x∈P_{j}} f(x) ≥ \frac{δ^{2}|P_{j}|}{40}. As A(x) = f(x) + δ, |A(x) ∩ P_{j}| ≥ δ(1 + δ/40)|P_{j}|. By Lemma 2.3, P_{j} may be partitioned into r ≤ 3|P_{j}|^{1/2} ℤ-arithmetic progressions Q_{1}, Q_{2}, …, Q_{r}. This gives

∑_{i=1}^{r} ∑_{x∈Q_{i}} f(x) ≥ \frac{δ^{2}|P_{j}|}{40}

and so there is k such that ∑_{Q_{k}} f(x) ≥ δ^{2}|Q_{k}|/80 and |Q_{k}| ≥ δ^{2}|P_{j}|/80r ≥ δ^{3}N^{1/2}/5000. In other words, A has density δ(1+δ/80) in the long arithmetic progression Q_{k}. We now repeat the argument on A ∩ Q_{k} in Q_{k}. As the density increases by a factor δ/80 each time, this procedure must stop in 160/δ steps. That is, A must contain an arithmetic progression of length three provided that δ ≥ 500/ log log N. □

Heath-Brown [9] and Szemerédi [18] have recently improved the denominator to (log N)^{−c}, for some constant c > 0.

§3 Weyl’s Inequality

Let f : ℕ → ℝ be a function and write {f(x)} for the fractional part of f(x). We say that f is uniformly distributed if for α ∈ (0, 1],

lim_{n→∞} |{m ≤ n : {f(m)} < α}| = α

Weyl [23] established that if f(x) is a polynomial that has at least one non-constant term with an irrational coefficient, then f is uniformly distributed. This theorem is proved using a fundamental inequality, known as Weyl’s Inequality, involving exponential sums. We shall prove this theorem with f(x) = αx^{k}: that is, {α, 2^{k}α, 3^{k}α, …} is equidistributed modulo 1. As a consequence, if α is a real number then for any ε > 0 there exists N such that N^{2}α is at distance at most ε from an integer.

We derive the appropriate inequality to prove this result by establishing estimates for exponential sums. The statements here are written for simplicity, rather than for finding optimal bounds. We begin with the following elementary lemma:

Lemma 3.1. Let α, β ∈ ℝ. Then for n ∈ ℕ,

|∑_{x=1}^{n} e(αx + β)| ≤ min{n, (2∥α∥)^{−1}}

where ∥α∥ is the distance from α to the nearest integer. Proof. The constant β does not affect the inequality. If α = 0, then the sum is n. If α ≠ 0, then the sum is e(α)(1 − e(αn))/(1 − e(α)). As sin z = \frac{1}{2i}(e^{iz} − e^{−iz}), this is at most | sin πα|^{−1}. Since | sin πα| ≥ 2∥α∥, the inequality follows. □

Lemma 3.2. Let m, r, Q ∈ ℕ with Q ≥ 2 and m ≤ r. Let θ_{1}, θ_{2}, …, θ_{m} be real numbers with ∥θ_{i} − θ_{j}∥ ≥ r^{−1} whenever i ≠ j. Then

∑_{i=1}^{m} min\{\frac{1}{∥θ_{i}∥}, Q\} ≤ 6 log Q(Q + r).

Proof. Without loss of generality, θ_{i} ∈ [−1/2, 1/2] and the contribution S^{+} to the sum from the non-negative θ_{i} is at least one half of the total. Suppose the positive θ_{i} are ordered: 0 < θ_{1} < θ_{2} < … < θ_{k}. Then

∑_{i=1}^{k} min\{\frac{1}{∥θ_{i}∥}, Q\} = ∑_{i=1}^{k} min\{θ_{i}^{−1}, Q\} ≤ ∑_{i=1}^{k} min\{r/(i − 1), Q\} = ∑_{i=0}^{⌊r/Q⌋} Q + ∑_{r/Q<i<k} r/i.

Estimating the last term with logarithms, S^{+} ≤ (1 + r/Q)Q + 2r(log k + log Q − log r) ≤ Q + r + 2r log Q. Therefore the sum is at most 2S^{+} ≤ 6 log Q(Q + r). □

The following lemma will be used in this and subsequent sections.

Lemma 3.3. Let q, Q, R ∈ ℕ, Q ≥ 2, and let α ∈ ℝ be chosen so that there exists a ∈ ℕ with (a, q) = 1 and |α − a/q| ≤ q^{−2}. Then

∑_{x=0}^{R} min\{\frac{1}{∥αx + β∥}, Q\} ≤ 48 log Q(Q + q + R + QR/q).

Proof. Let s, t ≥ 0 be natural numbers. Then ∥sα − tα∥ ≥ ∥(s − t)a/q∥ − |s − t|q^{−2}. If 0 < |s − t| ≤ q/2 then a(s − t) ≠ 0 (mod q), so is at least 1/q − q/2q^{2} = 1/2q. In the first case, suppose R < q/2 − 1. Then β, α + β, …, Rα + β are all (2q)^{−1}-separated (mod 1), so by Lemma 3.2 with r = 2q,

∑_{x=0}^{R} min\{\frac{1}{∥θ_{i}∥}, Q\} ≤ 6 log Q(Q + 2q).

In the second case, split the sum into segments of size at most q/2 – at most 4R/q segments in total. By Lemma 3.2, each contributes at most 6 log Q(Q + 2q). Therefore the sum is at most 24 log Q(QR/q + 2R). In both cases, we obtain the upper bound 48 log Q(Q + q + R + QR/q), as required. □

Theorem 3.4. Let q, Q ∈ ℕ, Q ≥ 2, let (a, q) = 1 and let α ∈ ℝ with |α − a/q| ≤ q^{−2}. Let ϕ(x) = x^{2} + cx + d. Then

|∑_{x=0}^{Q} e(αϕ(x))| ≤ 20 log Q(Q^{1/2} + q^{1/2} + Q/q^{1/2}).

Proof. Let ψ_{u}(y) = \frac{1}{2u}[ϕ(y + u) − ϕ(y)] = y + u/2 + c/2. Then

|∑_{x=0}^{Q} e(αϕ(x))|^{2} = ∑_{y=0} Q ∑_{x=0}^{Q} e(αϕ(x) − αϕ(y))
= ∑_{y=0}^{Q} ∑_{u=−y}^{Q−y} e(αϕ(y + u) − αϕ(y))
= ∑_{u=−Q}^{−1} ∑_{y=Q+u}^{Q} e(αϕ(y + u) − αϕ(y)) + ∑_{u=0}^{Q} ∑_{y=0}^{Q−u} e(αϕ(y + u) − αϕ(y))

= ∑_{u=−Q}^{Q} ∑_{y∈I_{u}} e(2αuψ_{u}(y))
≤ ∑_{u=−Q}^{Q}| ∑_{y∈I_{u}} e(2uαy + βu)|
≤ ∑_{u=−Q}^{Q} min{∥2uα∥^{−1}, Q}
≤ ∑_{u=−2Q}^{2Q} min{∥uα∥, Q}
≤ 48 log Q(Q + q + 2Q + 1 + Q(2Q + 1)/q)
≤ 200 log Q(Q + q + Q^{2}/q).

where I_{u} denotes the range of y-summation. This gives the desired bound. □

In the next results, we will write \underline{u}_{j} ≡ u_{1}, u_{2}, …, u_{j}, for convenience. The next lemma is the step required to prove Weyl’s Inequality.

Lemma 3.5. Let ϕ be a monic polynomial of degree k and let 0 ≤ j ≤ k − 1. Let f(α) = ∑_{x=1}^{Q} e(αϕ(x)). Then

|f(α)|^{2^{j}} ≤ (2Q)^{2^{j}−j−1} ∑_{u_{1}∈I_{1}} ∑_{u_{2}∈I_{2}} … ∑_{u_{j}∈I_{j}} | ∑_{y∈I_{\underline{u}_{j}}} e(αϕ_{\underline{u}_{j}}(y))|

where I_{1}, I_{2}, …, I_{j} are integer intervals, contained in (−Q, Q], such that I_{i} depends on u_{1}, u_{2}, …, u_{i−1}, I_{\underline{u}_{j}} is a sub-interval of [Q] and ϕ_{\underline{u}_{j}} is a polynomial of degree k − j with leading coefficient k!/(k − j)!. Proof. By induction on j. For j = 0, the result is clear. Now, as (∑ a_{i}) ≤ n ∑ a_{i}^{2},

|f(α)|^{2^{j+1}} ≤ (2Q)^{2^{j+1}−2j−2}(2Q)^{j}| ∑_{y∈I_{\underline{u}_{j}}} e(αϕ_{\underline{u}_{j}}(y))|^{2}
≤ ∑_{u_{j+1}∈I_{j+1}} · ∑_{y∈I_{\underline{u}_{j}}} e(α[ϕ_{\underline{u}_{j}}(y + u_{j+1}) − ϕ_{\underline{u}_{j}}(y)]),

where I_{j+1} is a subset of I_{\underline{u}_{j}} −I_{\underline{u}_{j}} ⊂ (−Q, Q] and I_{\underline{u}_{j+1}} ⊂ I_{\underline{u}_{j}}. Now ϕ_{\underline{u}_{j}}(y+u_{j+1})−ϕ_{\underline{u}_{j}}(y) = ϕ_{\underline{u}_{j+1}}(y) where ϕ_{\underline{u}_{j+1}}(y) has degree k − j − 1. The leading coefficient of ϕ_{\underline{u}_{j+1}}(y) is u_{j+1}(k − j) · k!/(k − j)! · u_{1}u_{2} … u_{j}. □

We now state and prove Weyl’s Inequality. Theorem 3.6 Let (a, q) = 1, α ∈ ℝ, |α − a/q| ≤ q^{−2}, k, Q ∈ ℕ, Q ≥ 2. Then

|∑_{x=1}^{Q} e(αϕ(x))| ≤ 100(log Q)^{k/2^{k−1}}Q(Q^{−1} + q^{−1} + qQ^{−k})^{1/(2^{k}−1)}.

Proof. Let k ≥ 2. Given n ∈ ℕ, there are at most (2 log_{2} n)^{2(k−1)} ways of writing n as a product of k − 1 integers. If m = k!Q^{k−1}, then

|f(α)|^{2^{k−1}} ≤ (2Q)^{2^{k−1}−k} · ∑_{u_{1},...,u_{k−1}}|∑_{y} e(αϕ_{\underline{u}_{k−1}}(y))|
≤ (2Q)^{2^{k−1}−k} · ∑_{\underline{u}_{k−1}}|∑_{y} e(αϕ_{\underline{u}_{k−1}}(y))|
≤ (2Q)^{2^{k−1}−k} · 2^{k−1}(log_{2} Q)^{k−1} ∑_{−m+1}^{m} min{Q, ∥αx∥^{−1}}
≤ (2Q)^{2^{k−1}−k} · 2^{k−1}(log_{2} Q)^{k−1} · 48 log Q(Q + 2k!Q^{k−1} + q + 2k!Q^{k}/q).

This is at most 100(log Q)^{k}Q^{2^{k−1}}(Q^{−1} + q^{−1} + qQ^{−k}). □ We briefly look at an important practical application of Weyl’s Inequality, which will lead to Weyl’s Theorem. Proposition 3.7. Let α ∈ ℝ, N ∈ ℕ. Then there exists q : 1 ≤ q ≤ N such that ∥αq∥ ≤ N^{−1}. Proof. Of the reals α, 2α, …, Nα, two lie within N^{−1} of each other (mod 1). Thus there exist s, t : s ≠ t with ∥(s − t)α∥ ≤ n^{−1}. Set q = |s − t|. □ Lemma 3.8. For n ∈ ℕ, the number of factors of n is at most n^{4/(log log n)}. Proof. Let 2 ≤ t ≤ n and write τ(n) for the number of divisors of n. Then

τ(n) = ∏_{{p^{a}|n \atop p^{a+1}|̸n}}(a + 1) ≤ ∏_{{p^{a}|n,p≤t \atop p^{a+1} |̸ n}}(a + 1) ∏_{{p^{a}|n,p>t \atop p^{a+1} |̸ n}} 2^{a}
≤ (1 + \frac{log n}{log 2})^{t}( ∏_{{p^{a}|n \atop p^{a+1} |̸ n}} p^{a})^{log 2/ log t}
≤ exp(t(2 + log log n) + log 2 · log n/ log t).

On choosing t = log n/(log log n)^{3}, we obtain the result. □

Lemma 3.9. Let A ⊂ ℤ_{N}, |A| = M, and suppose that A ∩ (−2L, 2L] ≠ ∅. Then there exists r such that 0 < r < (N/L)^{2} and |Â(r)| ≥ LM/2N. Proof. We have x, y ∈ I = (−L, L] implies x−y ∈ (−2L, 2L]. Therefore if (I∗I)(s) ≠ 0 then A(s) = 0. So ∑_{s}(I ∗I)(s)A(s) = 0 and ∑_{r} |Î|^{2}Â(r) = 0 implies ∑_{r≠0} |Î(r)|^{2}|Â(r)| ≥ |Î(0)||Â(0)| = 4L^{2}M. However |Î(r)| = |∑_{I} e(−rs)| ≤ min{∥r/N∥, 2L}. If −N/2 < r < N/2, then this is min{N/r, 2L}. Consequently

∑_{r≠0} |Î(r)|^{2}|Â(r)| ≤ max_{0<|r|≤(N/L)^{2}} |Â(r)| ∑_{r} |Î(r)|^{2} + M ∑_{|r|>(N/L)^{2}}(N/r)^{2}
≤ 2LN max_{0<r≤(N/L)^{2}} |Â(r)| + 3MN^{2}/(N/L)^{2}.

Therefore there exists r for which |Â(r)| ≥ LM/2N. □

The next theorem, due to Weyl [23], is a well-known consequence of Weyl’s Inequality:

Theorem 3.10. For every k ∈ ℕ there exists ε > 0 such that for all M sufficiently large and α ∈ ℝ, there exists q ≤ M such that ∥q^{k}α∥ ≤ 2M^{−ε}. Proof. Approximate α arbitrarily closely by a rational a/N with N prime. Without loss of generality, α = a/N. If the claim of the theorem is false, then A = {a, 2^{k}a, …, M^{k}a} and (−2L, 2L] are disjoint when L = ⌊NM^{−ε}⌋. Applying Lemma 3.9, we find r such that 0 < r ≤ (N/L)^{2} ≤ 2M^{2ε}, and such that |Â(r)| ≥ M^{1−ε}/2. Now |Â(r)| = |∑_{s=1}^{M} e(αrs^{k})|. Let q ≤ M with |αr − p/q| ≤ (qM)^{−1}. If q ≥ M^{2^{−k}}, applying Weyl’s inequality gives

|∑_{s=1}^{M} e(αrs^{k})|≤ M^{1+ε} · M^{−1/(2k2^{k−1})},

for M is sufficiently large. With ε = 1/(k2^{k+3}), this is a contradiction. If q ≤ M^{2^{−k}}, then ∥αqr∥ ≤ M^{−1}, by Proposition 3.7. But then ∥α(qr)^{k}∥ ≤ 2^{k}M^{−1/2}M^{2kε} ≤ 2M^{1−ε} for M sufficiently large. □

§4 Vinogradov’s Three-Primes Theorem

Vinogradov’s famous theorem asserts that every sufficiently large odd number is the sum of three primes. Together with Chen’s theorem (every sufficiently large even number is the sum of p and q, where p is prime and q is the product of at most two primes) this is one of the strongest results in the direction of Goldbach’s conjecture. In this section we shall see how to use exponential-sum estimates to prove Vinogradov’s theorem, and we shall also gain some insight into why Goldbach’s conjecture itself is out of reach.

We begin with some definitions and simple lemmas. Given n ∈ ℕ, let Λ(n) be log p if n = p^{k} with p prime, k ≥ 1 and zero otherwise. Let μ(n) = (−1)^{k} if n is a product of k distinct primes (interpreting this as 1 when n = 1) and zero otherwise. These functions are called von Mangoldt’s function and the Möbius function respectively.

Lemma 4.1. Let x ∈ ℕ. Then ∑_{d|x} Λ(d) = log x. Proof. Write x as a product of prime powers and it becomes obvious. □

Lemma 4.2. Let x ∈ ℕ. Then ∑_{d|x} μ(d) = 0 unless x = 1 in which case ∑_{d|x} μ(d) = 1. Proof. Let x ≥ 2 and write x = p_{1}^{a_{1}} … p_{k}^{a_{k}}. Then every subset A ⊂ [k] contributes (−1)^{|A|} to the sum ∑_{d|x} μ(d). But

∑_{A⊂[k]}(−1)^{|A|} = ∑_{j=0}^{k}(−1)^{j}\binom{k}{j} = (1 − 1)^{k} = 0.

(Another way of looking at the last calculation is that a randomly chosen subset of [k] has the same chance of being of even as of odd size.) □

Recall that d(x) is defined to be the number of divisors of x. We know from the previous section that d(x) is sometimes quite large. The next lemma shows that this does not happen all that often.

Lemma 4.3. Let n ∈ ℕ. Then ∑_{x≤n} d(x)^{2} ≤ 2n(log n)^{3}. Proof. This is surprisingly easy to prove. Indeed,

∑_{x≤n} d(x)^{2} = ∑_{x≤n} ∑ b|x ∑_{c|x} 1

= ∑_{b≤n} ∑_{c≤n} ∑_{y.lcm(a,b)≤n} 1
≤ ∑_{a≤n} ∑_{d≤n/a} ∑_{e≤n/ad} ∑_{y≤n/ade} 1
≤ ∑_{a≤n} ∑_{d≤n/a} ∑_{e≤n/ad} n/ade
≤ ∑_{a≤n} ∑_{d≤n/a}(n/ad)(log n + 1)
≤ ∑_{a≤n}(n/a)(log n + 1)^{2}
≤ n(log n + 1)^{3},

which proves the lemma. □

It is easy to check that the number of ways of writing n as the sum of three primes is ∫ F (α)^{3}e(−αn)dα, where F (α) is the function ∑_{p≤n} e(αp). Roughly speaking, our aim will be to estimate F (α) for every α, and use this estimate to prove that the integral is non-zero. As in the previous section, F (α) turns out to be small when α is not too close to a rational with small denominator. When it is close to such a rational, we shall use results about the distribution of primes in an arithmetic progression to estimate F (α) directly.

There are, however, certain advantages in weighting the primes so that their density is approximately constant through the interval. Since the density near m is (log m)^{−1}, the appropriate weight to give p is log p. Accordingly, we shall estimate the function f(α) = ∑_{p≤n} log pe(αp). The integral ∫ f(α)^{3}e(−αn)dα gives us the sum of (log p_{1})(log p_{2})(log p_{3}) over all triples (p_{1}, p_{2}, p_{3}) such that p_{1} + p_{2} + p_{3} = n, so for the purposes of Vinogradov’s theorem it is enough to prove that this integral is non-zero for large enough odd n.

Finally, even this function is not always the most convenient to estimate. The next lemma shows that we may replace it by g(α) = ∑_{x≤n} Λ(x)e(αx), with only a small error.

Lemma 4.4. |f(α) − g(α)| ≤ C\sqrt{n} for every α and some absolute constant C. Proof. g(α)−f(α) = ∑_{p^{k}≤n,k≥2} log pe(αp^{k}) which in modulus is at most (log_{2} n) ∑_{p≤\sqrt{n}} 1. By Chebyshev’s theorem the result follows. □

The next lemma is similar to the lemma we kept using during the proof of Weyl’s inequality, and follows from it. Since we are about to prove several results with the same hypotheses, let us state them once and for all before starting. Thus, a and q will be positive integers with (a, q) = 1 and α is a real number with |α − a/q| ≤ q^{−2}.

Lemma 4.5. Let Q, R be positive integers with q ≤ Q. Then

∑_{x=1}^{R} min{∥αx∥^{−1}, Qx^{−1}} ≤ 200 log Q log R(q + R + Qq^{−1}).

Proof. We know, from chapter 3, that the numbers 0, α, 2α, …, ⌊(q/2)⌋α are (2q)^{−1}- separated. Therefore,

∑_{x≤q/2} min{∥αx∥^{−1}, Qx^{−1}} ≤ 2 ∑_{x≤⌈q/4⌉} 2q/x ≤ 4q log q.

Given an integer i, let S_{i} be the sum ∑_{x=2^{i−1}}^{2^{i}−1} min{∥αx∥^{−1}, Qx^{−1}}. Then

S_{i} ≤ ∑_{x=2^{i−1}}^{2^{i}−1} min{∥αx∥^{−1}, Q/2^{i−1}}

which, by Lemma 3.3 of the last chapter, is at most 48 log Q(2^{−(i−1)}Q+2^{i−1} +q +Qq^{−1}). Summing over all i such that 2^{i} > q/2 and 2^{i−1} ≤ R, we obtain the desired result. □

We now prove an identity due to Vaughan [21], which will allow us to show that g(α) is small when α is not close to a rational with small denominator. This identity seems mysterious when it is just drawn out of a hat, but the mystery can be reduced with a few remarks.

We wish to show that g(α) = ∑_{x≤n} Λ(x)e(αx) is appreciably smaller than n when q is not too small (or too large). The function which is hard to understand is of course Λ, but we know that Λ has the nice property that ∑_{d|x} Λ(d) = log x, which is much more familiar. Therefore, we try to express g(α) as a sum of pieces of this form. As a first observation, we notice (or rather, it has been noticed) that

∑_{x≤n} ∑_{y≤n/x} Λ(x)e(αxy) = ∑_{u≤n} ∑_{x|u} Λ(x)e(αu).

This is very promising, because

∑_{x≤n} Λ(x)e(αx) = ∑_{x≤n} ∑_{y≤n/x} ∑_{d|y} μ(d)Λ(x)e(αxy)
= ∑_{d≤n} μ(d) ∑_{z≤n/d} ∑_{x≤n/zd} Λ(x)e(αdxz) ,

which is a ±1-combination of sums of the required form, and therefore seems to have a chance of being small.

Now it is clearly not easy to obtain a good estimate for the last quantity directly, because d takes n possible values and for each one we are not going to do better than a modulus of 1. It is therefore essential to restrict d. However, this introduces a new error term which must be shown to be small. Moreover, showing that this error term is small turns out not to be possible unless we also restrict x to be not too small. We now prove the identity by a process of trial and error, starting with the observations above.

Lemma 4.6. Let X = n^{2/5}. Then g(α) = ∑_{x≤n} Λ(x)e(αx) = S − T − U + O(n^{2/5}), where

S = ∑_{d≤X} μ(d) ∑_{z≤n/d} ∑_{x≤n/zd} Λ(x)e(αdxz) ,

T = ∑_{d≤X} μ(d) ∑_{z≤n/d} ∑_{x≤X,x≤n/zd} Λ(x)e(αdxz)

and

U = ∑_{X<u≤n} ∑_{d|u,d≤X} μ(d) ∑_{X<x≤n/u} Λ(x)e(αxu).

Proof. Let us write τ_{u} for ∑_{d|u,d≤X} μ(d). Then, by Lemma 4.2, we know that τ_{u} is 1 when u = 1 and 0 when 1 < u ≤ X. Therefore,

∑_{u≤n} τ_{u} ∑_{X<x≤n/u} Λ(x)e(αxu) = U + ∑_{X<x≤n} Λ(x)e(αx).

But, by Chebyshev’s theorem (as in the proof of Lemma 4.4),

∑_{X<x≤n} Λ(x)e(αx) = g(α) + O(n^{2/5}).

We also know that

∑_{u≤n} τ_{u} ∑_{X<x≤n/u} Λ(x)e(αxu) = ∑_{u≤n} ∑_{d|u,d≤X} μ(d) ∑_{X<x≤n/u} Λ(x)e(αxu)

= ∑_{d≤X} μ(d) ∑_{z≤n/d} ∑_{X<x≤n/dz} Λ(x)e(αxzd)
= S − T.

The identity follows. □

In the next three lemmas, we show that each of S, T and U is small. Notice that S is the sum we originally expected to be able to bound, and is therefore in a sense the important one, while T and U are error terms that we were unable to avoid introducing.

Lemma 4.7. |S| ≤ 80(log n)^{3}(q + X + n/q). Proof. Writing u for xz, we have

|S| = | ∑_{d≤X} μ(d) ∑_{u≤n/d} ∑_{x|u} Λ(x)e(αdu)| ≤ ∑_{d≤X}| ∑_{u≤n/d} log ue(αdu)|

by Lemma 4.1. But

| ∑_{u≤n/d} log ue(αdu)|  =  | ∑_{u≤n/d} ∫_{1}^{u} e(αdu) dt/t|
≤ ∫_{1}^{n/d}|∑_{t≤u≤n/d} e(αdu)| dt/t
≤ ∫_{1}^{n/d} min{∥αd∥^{−1}, n/d} dt/t
≤ log n min{∥αd∥^{−1}, n/d}.

Summing over d ≤ X and applying Lemma 4.5 (taking into account that log X = (2/5) log n) we obtain the bound claimed. □

Lemma 4.8. |T | ≤ 160(log n)^{3}(q + X^{2} + n/q). Proof. Interchanging the order of summation of z and x in the definition of T, and using the fact that |μ(d)| ≤ 1, we have

|T | ≤ ∑_{d≤X} ∑_{x≤X} Λ(x)| ∑_{z≤n/dx} e(αdxz)|.

Now let y = dx, and this becomes

∑_{y≤X^{2}} ∑_{x≤X,x|y} Λ(x)| ∑_{z≤n/y} e(αyz)|.

By Lemma 4.1, ∑_{x≤X,x|y} Λ(x) ≤ log y ≤ log n, so we can bound this above by

log n ∑_{k≤X^{2}} min{∥αy∥^{−1}, n/y}

which is at most the bound stated, by Lemma 4.5. □

Lemma 4.9. |U| ≤ 40(log n)^{4}(n^{1/2}q^{1/2} + n/X^{1/2} + nq^{−1/2}). Proof. Given a positive integer i, let U_{i} be the sum

∑_{u=2^{i−1}}^{2^{i}−1} |τ_{u}|| ∑_{X<x≤n/u} Λ(x)e(αxu)|.

Notice that U_{i} = 0 when 2^{i−1} ≥ n/X (because it is then impossible to satisfy the inequality X < x ≤ n/u), and that |U| is therefore at most the sum of all U_{i} over all i such that 2^{i} > X and 2^{i−1} < n/X. It is easy to check that there are at most log n such values of i. (The fact that 2^{i} is between roughly n^{2/5} and roughly n^{3/5} more than compensates for the replacement of log_{2} n by log n.) We shall estimate the U_{i} separately. By the Cauchy-Schwarz inequality,

U_{i}^{2} ≤ ( ∑_{u=2^{i−1}}^{2^{i}−1} |τ_{u}|^{2})( ∑_{u=2^{i−1}}^{2^{i}−1}| ∑_{X<x≤n/u} Λ(x)e(αxu)|^{2}).

Now |τ_{u}| is obviously at most d(u), so

∑_{u=2^{i−1}}^{2^{i}−1} |τ_{u}|^{2} ≤ ∑_{u=2^{i−1}}^{2^{i}−1} d(u)^{2}
≤ ∑_{u=1}^{2^{i}} d(u)^{2} ,

which is at most 2^{i}(log n)^{3}, by Lemma 4.3. As for the other bracket, if we expand out the modulus squared, we find that it equals

∑_{u=2^{i−1}}^{2^{i}−1} ∑_{X<x≤n/u} ∑_{X<y≤n/u} Λ(x)Λ(y)e(α(x − y)u).

Interchanging the sum over u with those over x and y, we find that this is at most

∑_{X<x≤n/2^{i−1}} ∑_{X<y≤n/2^{i−1}} Λ(x)Λ(y)|  ∑_{2^{i−1}≤u<2^{i},u≤min{n/x,n/y}} e(α(x − y)u)|

which is at most

∑_{X<x≤n/2^{i−1}} ∑_{X<y≤n/2^{i−1}} Λ(x)Λ(y) min{∥α(x − y)∥^{−1}, 2^{i−1}}.

Writing z for x−y and observing that each z occurs at most n/2^{i−1} times, we can bound this sum above by

(log n)^{2}(n/2^{i−1}) ∑_{n/2^{i−1}<z≤n/2^{i−1}} min{∥αz∥^{−1}, 2^{i−1}} ,

which, by Lemma 3.3 of the last chapter, is at most

(log n)^{2}.48 log n(q + n/2^{i−2} + 2^{i−1} + 2n/q).

Multiplying the two estimates together, we have shown that

U_{i}^{2} ≤ 96n(log n)^{6}(q + 4n/2^{i} + 2^{i−1} + 2n/q) ,

which implies, since n/2^{i} and 2^{i−1} are at most n/X, that

U_{i} ≤ 40(log n)^{3}(n^{1/2}q^{1/2} + n/X^{1/2} + nq^{−1/2}).

Since there are at most log n values of i such that U_{i} contributes to U, the result follows. □

Remarks. It may look complicated to split the sum into log n (or so) further pieces, but this was a good (and standard) thing to do because we were estimating something of the form ∑_{u} f(u)g(u), where f(u) appeared to be roughly proportional to u and g(u) roughly proportional to u^{−1}. So applying the Cauchy-Schwarz inequality straight away would have been disastrous. Note that the choice of X = n^{2/5} was made in order to minimize max{X^{2}, nX^{−1/2}}.

If we put together Lemmas 4.4 and 4.6 to 4.9 we obtain the following result.

Theorem 4.10. Let a, q be positive integers with (a, q) = 1 and let α be a real number such that |α − a/q| ≤ 1/q^{2}. Then ∑_{x≤n} Λ(x)e(αx) and ∑_{p≤n} log p e(αp) are both at most 50(log n)^{4}(n^{1/2}q^{1/2} + n^{4/5} + nq^{−1/2}), when n is sufficiently large.

We have now managed to show that f(α) is small, provided that q is not too small. The usual approach to the rest of the proof is to estimate f(α) when α is close to a rational with small denominator, using the Siegel-Walfisz theorem (see [19]), and then combine these results to obtain a fairly accurate estimate for ∫ f(α)^{3}e(−αn) dα (in particular, accurate enough to show that it is non-zero). In these notes, a different argument is used, which is believed to explain, in a more intuitive way, why the integral comes out to be positive. It has the added advantage that we do not actually need to estimate the integral at all accurately, although it is possible to work harder in order to do so.

The main idea is to work out exactly what is meant by the familiar idea that the primes are somehow randomly distributed. A minor problem to worry about first is that there are more small primes than large ones, but we have already dealt with that by weighting a prime p by log p. Now, in chapter 2, we thought of a subset A of {1, 2, …, n} as being random if the Fourier coefficients Â(r) were all much smaller than n, for non-zero r. However, it is clear that the primes are not random in this sense, because, for example, only one prime is a multiple of five.

Which constraints of this kind have an effect on Fourier coefficients? It is an easy exercise to show that congruence conditions mod q have an effect if and only if q is small. Motivated by this observation, we let p_{1}, …, p_{k} be the primes less than or equal to (log n)^{A}, in ascending order, and define Q to be the set of integers less than or equal to n that are not multiples of any p_{i}. Here, A is an absolute constant (in fact we shall choose A = 16), but there is some freedom in the argument, and we could have made p_{k} quite a bit larger. What we shall do in the rest of the section is show that the weighted primes behave like a random subset of Q.

It is not hard to work out how to interpret this statement. It means that the Fourier transforms f(α) = ∑_{p≤n} log p e(αp) and h(α) = ∑_{x∈Q} e(αx) are roughly proportional. This implies that integrals involving these functions are also roughly proportional, so that, roughly speaking, whatever is true for Q is true for the weighted primes as well. (That “roughly speaking” is important: a good exercise is to see why Lemma 4.20 below does not translate into a solution of the Goldbach conjecture.)

We begin by obtaining an estimate similar to Theorem 4.10 for the function h(α). The proof is much simpler, however.

Lemma 4.11. Suppose that (a, q) = 1 and |α − a/q| ≤ q^{−2}. Then

|h(α)| ≤ 100(log n)^{2}(n^{1/2} + q + nq^{−1} + n^{1−1/4A}).

Proof. Notice first that

h(α) = ∑_{s=0}^{k}(−1)^{s} ∑_{1≤i_{1}≤...≤i_{s}≤k} ∑_{y≤n/p_{i_{1}}...p_{is}} e(αp_{i_{1}} … p_{i_{s}}y).

The justification of this is similar to the proof of Lemma 4.2. If z ∈ Q then e(αz) is added when s = 0, and otherwise does not appear. If z ∉ Q then z = p_{j_{1}}^{a_{1}} … p_{j_{r}}^{a_{r}}w for some w ∈ Q, and a_{i} ≥ 1, and e(αz) is added (−1)^{|B|} times for every subset B of {j_{1}, dots, j_{r}}, giving a total contribution of zero. The inner sum is at most min{∥αp_{i_{1}} … p_{i_{s}}∥^{−1}, n/p_{i_{1}} … p_{i_{s}}}. Let t = log n/2A log log n and note that p_{k}^{t} ≤ \sqrt{n}. These estimates and the fundamental theorem of arithmetic imply that

|∑_{s=0}^{t}(−1)^{s} ∑_{1≤i_{1}≤...≤i_{s}≤k} ∑_{y≤n/p_{i_{1}}...p_{is}} e(αp_{i_{1}} … p_{i_{s}}y)|

is at most ∑_{x≤\sqrt{n}} min\{∥αx∥^{−1}, n/x\}, which, by Lemma 4.5, is at most 100(log n)^{2}(n^{1/2} + q + nq^{−1}). The rest of the sum is, in modulus, at most

∑_{s=t+1}^{k} ∑_{1≤i_{1}≤...≤i_{s}≤k} n ∏_{j=1}^{s} p_{i_{j}}^{−1} ,

which is at most

n ∑_{s=t+1}^{k}(s!)^{−1}(p_{1}^{−1} + … + p_{k}^{−1})^{s}.

It is well known (and follows from the prime number theorem) that p_{1}^{−1} + … + p_{k}^{−1} is about log log k, and so at most 2 log log log n, when n is sufficiently large. Approximating s! by (s/e)^{s}, we obtain an upper bound of 2n(2e log log log n/t)^{t}, since t ≥ 4e log log log n. It is not hard to check that this is at most n^{−1/4A} when n is sufficiently large. This, together with the first estimate, proves the lemma. □

We now turn to the “major-arcs” estimates, that is, estimates for f(α) and h(α) when α is close to a rational with small denominator. It turns out that such estimates are more or less equivalent to estimating ∑_{p∈X} log p and |X ∩ Q| for certain long arithmetic progressions X. In the case of the primes themselves, we shall appeal to known estimates of this type, as given in the next result, the Siegel-Walfisz theorem.

Siegel-Walfisz Theorem. Let A be a positive real number, let x be an integer, let q ≤ (log x)^{A} be another integer and let (a, q) = 1. Then

∑_{p≤x,p≡a (q)} log p = \frac{x}{ϕ(q)} + O(exp(−C\sqrt{log x})) ,

where C is a constant depending on A only.

Notice that from the Siegel-Walfisz Theorem it follows that, if q ≤ (log n)^{A}, and X is the arithmetic progression {a, a + q, …, a + (m − 1)q}, where (a, q) = 1 and 1 ≤ a ≤ n − (m − 1)q, then for any constant B, we have

∑_{p∈X} log p = \frac{mq}{ϕ(q)} + O(n/(log n)^{B}) ,

with the implied constant in the error term depending on A and B only.

We shall now obtain an estimate for |X ∩ Q|, when X is an arithmetic progression of the kind above.

Lemma 4.13. Let q ≤ (log n)^{A}, let X = {a, a + q, …, a + (m − 1)q} be a subset of [N] with m ≥ N^{1/2} and suppose that (q, a) = 1. Then

|X ∩ Q| = \frac{mq}{ϕ(q)} ∏_{i=1}^{k}(1 − p_{i}^{−1}) + O(mn^{−1/4A}).

Proof. Let x ∈ X be chosen uniformly at random, and for each i let X_{i} be the event p_{i}|x. Then the probability of X_{i} is p_{i}^{−1} + O(m^{−1}) if p_{i} |̸ q and O(m^{−1}) if p_{i}|q. More generally, for any choice 1 ≤ i_{1} ≤ … ≤ i_{s} ≤ k we have

Prob(X_{i_{1}} ∩ … ∩ X_{i_{s}}) = ∏_{j=1}^{s} ϵ_{i_{j}}/p_{i_{j}} + O(m^{−1}) ,

where ϵ_{i} = 1 if p_{i} |̸ q and 0 if p_{i}|q. It follows from this and the inclusion-exclusion formula that, for any t,

1 − Prob( ⋃_{i=1}^{k} X_{i}) = ∑_{s=0}^{t}(−1)^{s} ∑_{1≤i_{1}≤...≤i_{s}≤k} ∏_{j=1}^{s} ϵ_{i_{j}}/p_{i_{j}} + O(m^{−1}) ∑_{s=1}^{t} \binom{k}{s} .

Now

∏_{i=1}^{k}(1 − ϵ_{i}/p_{i}) = ∑_{s=0}^{k}(−1)^{s} ∑_{1≤i_{1}≤...≤i_{s}≤k} ∏_{j=1}^{s} ϵ_{i_{j}}/p_{i_{j}}

and

∑_{1≤i_{1}≤...≤i_{s}≤k} ∏_{j=1}^{s} ϵ_{i_{j}}/p_{i_{j}} ≤ (s!)^{−1}(p_{1}^{−1} + … + p_{k}^{−1})^{s}
≤ (4e log log log n/s)^{s}

when n is sufficiently large. If t ≥ 8e log log log n, then this quantity summed from t + 1 to k is at most (4e log log log n/t)^{t}. Furthermore, ∑_{s=1}^{t} \binom{k}{s} is easily seen to be at most k^{t}. It follows that

1 − Prob( ⋃_{i=1}^{k} X_{i}) = ∏_{i=1}^{k}(1 − ϵ_{i}/p_{i}) + O((log n)^{At} + (4e log log log n/t)^{t}).

Choosing t to be log n/2A log log n gives an error of at most O(n^{−1/4A}), as in the proof of Lemma 4.11. Note finally that

∏_{i=1}^{k}(1 − ϵ_{i}/p_{i}) = ∏_{i=1}^{k}(1 − 1/p_{i}) ∏_{p_{i}|q}(1 − 1/p_{i})^{−1}
= ∏_{i=1}^{k}(1 − 1/p_{i}) ∏_{p|q}(1 − 1/p)^{−1}
= \frac{q}{ϕ(q)} ∏_{i=1}^{k}(1 − p_{i}^{−1}).

Multiplying everything by m proves the lemma. □

Corollary 4.14. Let a, q, X be as in Lemma 4.13, let K = ∏_{i=1}^{k}(1 − p_{i}^{−1})^{−1} and let B be any positive constant. Then

K|X ∩ Q| − ∑_{p∈X} log p = O(n(log n)^{−B}).

Proof. This follows immediately from Lemma 4.13 and the remark following Lemma 4.12. (Strictly speaking one must consider what happens if (a, q) ≠ 1 but then it is easy to see that both K|X ∩ Q| and ∑_{p∈X} log p are very small.) □

Lemma 4.15. Let q ≤ (log n)^{A}, let (b, q) = 1 and let α be a real number such that |α − b/q| ≤ (log n)^{A}/qn. Let G be a function from {1, 2, …, n} to ℝ such that |G(x)| ≤ log n for every x and such that

| ∑_{x∈X} G(x)| = O(n(log n)^{−B})

for every arithmetic progression X = {a, a + q, …, a + (m − 1)q}, where B ≥ 4A + 2. Then

|∑_{x≤n} G(x)e(αx)| = O(n(log n)^{−A}).

Proof. Let β = α − b/q and let X be one of the arithmetic progressions of the above type. Notice that, if x, y ∈ X, then

|e(βx) − e(βy)| = |1 − e(β(x − y))| ≤ 2π|x − y||β| ≤ 2πm(log n)^{A}/n.

Therefore, letting x_{0} be an arbitrary element of X, we have

| ∑_{x∈X} G(x)e(αx)| = | ∑_{x∈X} G(x)e(bx/q)e(βx)|
≤ |e(ab/q) ∑_{x∈X} G(x)(e(βx) − e(β_{0}x))| + |e(ab/q)e(βx_{0}) ∑_{x∈X} G(x)|
= | ∑_{x∈X} G(x)(e(βx) − e(βx_{0}))| + | ∑_{x∈X} G(x)|
≤ (2πm(log n)^{A}/n)m log n + O(n(log n)^{−B})
= O((log n)^{A+1}m^{2}n^{−1} + n(log n)^{−B}).

But we can partition [n] into 2n/m_{0} arithmetic progressions of the form of X, with m ≤ m_{0} in each case. Therefore, choosing m_{0} = n(log n)^{−B/2} and summing over all these, we find that

|∑_{x≤n} G(x)e(αx)| = O(n(log n)^{A+1−B/2})

which proves the result. □

Recall that f(α) = ∑_{p≤n} log p e(αp). Let us define h_{1}(α) to be K ∑_{x∈Q} e(αx) = Kh(α).

Corollary 4.16. Let A = 16. Then, for every real number α, f(α) − h_{1}(α) = O(n(log n)^{−A/4}). Proof. Let α be a real number. Then we can find q ≤ n(log n)^{−A} and b with (b, q) = 1 such that |α − b/q| ≤ (log n)^{A}/nq. If q ≥ (log n)^{A}, then Theorem 4.10 implies that f(α) = O(n(log n)^{4−A/2}), while Lemma 4.11 (with an easy estimate for K) implies that h_{1}(α) = O(n(log n)^{3−A}), so the result holds. If on the other hand q ≤ (log n)^{A}, then set G(x) = log x − KQ(x) if x is prime, and −KQ(x) otherwise. Corollary 4.14 tells us that G satisfies the conditions for Lemma 4.15. But ∑_{x≤n} G(x)e(αx) = f(α) − h_{1}(α), so Lemma 4.15 gives us the result in this case. □

This is all we need for the three-primes theorem. However, it is perhaps of some interest to obtain an actual estimate for f(α) and h_{1}(α) when q is small, rather than merely showing that they are close. So the next two lemmas are here for interest only.

For notational convenience, when we write (a, q) = 1 in the next lemma we shall mean that a and q are coprime and that 1 ≤ a ≤ q.

Lemma 4.17. For every q, ∑_{(a,q)=1} e(a/q) = μ(q). Proof. If q = 1 then the result holds. If q is a prime, then

∑_{(a,q)=1)} e(a/q) = ∑_{1≤a<q} e(a/q) = 0 − 1 = −1.

If q = p^{k} with p prime and k ≥ 2, then

∑_{(a,q)=1} e(a/q) = ∑_{1≤a≤q} e(a/q) − ∑_{1≤b≤p^{k−1}} e(b/p^{k−1}) = 0 − 0 = 0.

Finally, if q and r are coprime, then

∑_{(a,q)=1} e(a/q) ∑_{(b,r)=1} e(b/r) = ∑_{(a,q)=1,(b,r)=1} e(ar + bq/qr).

But ar+bq runs through all residues mod qr, and (ar+bq, qr) = 1 if and only if (a, q) = 1 and (b, r) = 1. So the sum is ∑_{(a,qr)=1} e(a/qr). These properties of the left hand side force it to equal μ.

□

Now, given q ≤ (log n)^{A}, let us define a function H_{q} : [n] → ℝ by letting H_{q}(x) equal q/ϕ(q) if (x, q) = 1 and zero otherwise.

Lemma 4.18. Let q ≤ (log n)^{A}, let (b, q) = 1 and let α be a real number such that |α − b/q| ≤ (log n)^{A}/nq. Let β = α − b/q. Then

∑_{x≤n} H_{q}(x)e(αx) = \frac{μ(q)}{ϕ(q)} ∑_{x≤n} e(βx) + O((log n)^{2A}).

Proof. Let us write X_{a} for the set of integers less than or equal to n and congruent to a mod q. If (a, q) ≠ 1, then clearly ∑_{x∈X_{a}} H_{q}(x)e(αx) = 0. On the other hand, if (a, q) = 1, then

∑_{x∈X_{a}} H_{q}(x)e(αx) = \frac{q}{ϕ(q)} ∑_{x∈X_{a}} e(bx/q)e(βx)
= \frac{q}{ϕ(q)}e(ab/q) ∑_{x∈X_{a}} e(βx).

Now, if a_{1}, a_{2} ≤ q, then

| ∑_{x∈X_{a_{1}}} e(βx) − ∑_{x∈X_{a_{2}}} e(βx)| ≤ 1 + | ∑_{x∈X_{a_{1}}} e(βx)||1 − e(β(a_{1} − a_{2}))|.

Since |a_{1} − a_{2}| ≤ q, we know that 1 − e(β(a_{1} − a_{2})) = O((log n)^{A}/n), so this shows that, for every a,

∑_{x∈X_{a}} e(βx) = q^{−1} ∑_{x≤n} e(βx) + O((log n)^{A}).

(In words, the numbers ∑_{x∈X_{a}} e(βx) are all approximately equal, and therefore all approximately equal to their average.) It follows that

∑_{0≤a<q} ∑_{x∈X_{a}} H_{q}(x)e(αx) = \frac{q}{ϕ(q)} ∑_{(a,q)=1} e(ab/q)(q^{−1} ∑_{x≤n} e(βx) + O(log n)^{A}).

Since (b, q) = 1, the result follows from Lemma 4.17. □

Corollary 4.19. Let α, b, q and β be as in Lemma 4.18. Then f(α) and h_{1}(α) are both equal to (μ(q)/ϕ(q)) ∑_{x≤n} e(βx) + O(n(log n)^{−A}).

Proof. This follows easily from Theorem 4.12 and Lemmas 4.13, 4.15 and 4.18. Let P (x) be the function log x if x is prime and zero otherwise. Setting G(x) = P (x)−H_{q}(x), Theorem 4.12 tells us that the conditions for Lemma 4.15 are satisfied. But this implies that f(α) = ∑_{x≤n} H_{q}(x)e(αx) + O(n(log n)^{−A}). Then Lemma 4.18 gives us our estimate for f(α). The same argument works for h_{1}(α) if we use Lemma 4.13 instead of Theorem 4.12. □

After that diversion, let us now finish the proof of the three-primes theorem. There are two steps to the proof. First, we show that every sufficiently large odd integer is the sum of three elements of Q (or fake primes) in many ways, using the Brun sieve once again. Then we deduce, from the fact that f and h_{1} are uniformly close, that the same is true of the genuine primes.

Lemma 4.20. Let m be an integer. Then the number of ways of writing m = x+y with x and y both in Q is at least m ∏_{i=1}^{k}(1 − r_{i}/p_{i}) + O(m^{−1}n^{1/2} + mn^{−1/4A}), where r_{i} = 1 if p_{i}|m and 2 otherwise. Proof. Choose x randomly and uniformly from the set [m]. For each i let X_{i} be the event that p_{i}|x or p_{i}|m − x. As in the proof of Lemma 4.13, it is easy to show that Prob(X_{i}) = r_{i}/p_{i} +O(m^{−1}). (The point about the r_{i} is that the events p_{i}|x and p_{i}|m−x are the same if p_{i}|m and mutually exclusive otherwise.) More generally, it is not hard to show that

Prob(X_{i_{1}} ∩ … ∩ X_{i_{s}}) = ∏_{j=1}^{s} \frac{r_{i_{j}}}{P_{i_{j}}} + O(m^{−1}).

Therefore, by the inclusion-exclusion formula,

1 − Prob( ⋃_{i=1}^{k} X_{i}) = ∑_{s=0}^{t}(−1)^{s} ∑_{1≤i_{1}≤...≤i_{s}≤k} ∏_{j=1}^{s} r_{i_{j}}/p_{i_{j}} + O(m^{−1}) ∑_{s=1}^{t} \binom{k}{s} .

But

∏_{i=1}^{k}(1 − r_{i}/p_{i}) = ∑_{s=0}^{k}(−1)^{s} ∑_{1≤i_{1}≤...≤i_{s}≤k} ∏_{j=1}^{s} r_{i_{j}}/p_{i_{j}}

and

∑_{1≤i_{1}≤...≤i_{s}≤k} ∏_{j=1}^{s} r_{i_{j}}/p_{i_{j}} ≤ (s!)^{−1}(2p_{1}^{−1} + … + 2p_{k}^{−1})^{s}

≤ (8e log log log n/s)^{s}.

As in the proof of Lemma 4.13, it follows that

1 − Prob( ⋃_{i=1}^{k} X_{i}) = ∏_{i=1}^{k}(1 − r_{i}/p_{i}) + O(m^{−1}(log n)^{At} + (8e log log log n/t)^{t})

for any t ≥ 16e log log log n. Choosing t to be log n/2A log log n implies the lemma. □

Corollary 4.21. If n is sufficiently large and odd, then the number of ways of writing n as the sum of three elements of Q is at least (n^{2}/16)K^{−1} ∏_{i=2}^{k}(1 − 2p_{i}^{−1}). Proof. Note first that Lemma 4.13 implies that the number of elements of Q less than or equal to n/2 is at least K^{−1}n/4 (when n is sufficiently large). For every odd z ≤ n/2, the number of ways of writing n − z as the sum of two elements of Q is, by Lemma 4.20, at least (n/4) ∏_{i=2}^{k}(1 − 2/p_{i}). The result follows. □

It is possible to be much more careful and work out the number of ways of writing n as the sum of three elements of Q to within a factor 1 + o(1), but we do not need this.

Vinogradov’s Three-Primes Theorem. Every sufficiently large odd integer is the sum of three primes. Proof. Note first that (16K)^{−1} ∏_{i=2}^{k}(1 − 2p_{i}^{−1}) is easily shown to be at least (log n)^{−1} when n is sufficiently large, so the number of ways of writing n as the sum of three elements of Q is at least n^{2}/ log n. On the other hand, it is also ∫ h(α)^{3}e(−αn) dα, so we certainly have ∫ h_{1}(α)^{3}e(−αn) dα ≥ n^{2}/ log n. As we commented at the beginning, it is sufficient for our purposes to establish that ∫ f(α)^{3}e(−αn) dα ≠ 0. But, by Corollary 4.16,

|∫ f(α)^{3}e(−αn) dα − ∫ h_{1}(α)^{3}e(−αn) dα|
= O(n(log n)^{−A/4}) ∫ |f(α)^{2} + f(α)h_{1}(α) + h_{1}(α)^{2}| dα
= O(n(log n)^{−A/4}) ∫ |f(α)|^{2} + |h_{1}(α)|^{2} dα
= O(n(log n)^{−A/4}) (∑_{p≤n}(log p)^{2} + K^{2}|Q|)
= O(n^{2} log n(log n)^{−A/4}).

Since we chose A to be 16, this and our estimate for the integral with h_{1} are enough to prove the theorem. □

§5 The Geometry of Numbers

A lattice in ℝ^{n} is a subgroup generated by n linearly independent vectors. A basis for a lattice Λ is a linearly independent set in Λ that generates Λ.

Lemma 5.1. Let Λ be a lattice and let x_{1}, x_{2}, …, x_{n} and y_{1}, y_{2}, …, y_{n} be distinct bases of Λ. Let α : x_{i} ↦ y_{i} be linear. Then det(α) = 1. Proof. Each y_{i} is an integer combination of x_{i} so both α and α^{−1} are non-singular and have integer determinants. □

Let Λ be a lattice with basis x_{1}, x_{2}, …, x_{n}. The fundamental parallellopiped of Λ with respect to x_{1}, x_{2}, …, x_{n} is the set P = {a_{1}x_{1} + a_{2}x_{2} + … + a_{n}x_{n} : 0 ≤ a_{i} < 1}. Note that the sets x + P, x ∈ Λ are disjoint and their union is ℝ^{n}. The determinant det(Λ) of Λ is the volume of P, which is well-defined by the Lemma 5.1. Alternatively, det(Λ) is |det(A)|, where A = (x_{1}, x_{2}, …, x_{n}) and the x_{i} are column vectors with respect to the canonical basis for ℝ^{n}. A convex body is a bounded convex open subset of ℝ^{n}.

Lemma 5.2. Let Λ be a lattice and suppose that K is a convex body in ℝ^{n}. Then vol(K) = lim_{t→∞} |Λ ∩ tK|det(Λ)/t^{n}. Proof. Let Q be a translate of a fundamental parallellopiped P of Λ. Then tQ contains exactly t^{n} points in Λ if t is an integer. However, |Λ ∩ tQ| lies between ⌊t⌋^{n} and ⌈t⌉^{n}. Therefore the result is true for all sets of the form z + ρP with z ∈ ℝ^{n} and ρ > 0. As K is convex, it can be approximated by finite unions of such sets. □

A sublattice of a lattice Λ in ℝ^{n} is a subgroup M ⊂ Λ which is also a lattice.

Lemma 5.3. Let Λ be a lattice and let M be a sublattice of Λ. Then the index of M as a subgroup of Λ is det(M)/det(Λ). Proof. Let P be a fundamental parallellopiped for M. Then every vector x ∈ ℝ^{n} can be written uniquely as y + z, where y ∈ M and z ∈ P. Therefore every x ∈ Λ can be written uniquely as y + z with y ∈ M and z ∈ Λ. So the index of M is |P ∩ Λ|. If t is an integer, |tP ∩ Λ| = t^{n}|P ∩ Λ|. Thus volP = |P ∩ Λ|det(Λ), by Lemma 5.2, and it follows that det(M) = |P ∩ Λ|det(Λ). □

Blichfeldt’s Lemma. Let K ⊂ ℝ^{n} be a measurable set, Λ a lattice and suppose vol(K) > det(Λ). Then K − K contains a non-zero lattice point. Proof. Let x_{1}, x_{2}, …, x_{n} be a basis for Λ and let Q = {a_{1}x_{1}+…+a_{n}x_{n} : −1 ≤ a_{i} < 1}. Then vol(K) = 2^{n}det(Λ) and Q contains 2^{n} points of Λ. Provided M is sufficiently large, vol(K ∩ MQ) is still greater than det(Λ). So K ⊂ MQ. Let N be an integer, chosen such that (1 + M/N)^{n} < vol(K)/det(Λ). If the lemma were false, then the sets x + K, x ∈ Λ ∩ NQ are disjoint. The union of these sets is contained in (M + N)Q and has volume (2N)^{n}vol(K), since there are (2N)^{n} lattice points in Q. Therefore (2N)^{n}vol(K) ≤ (2(N + M))^{n}det(Λ). By the choice of M, this is a contradiction. □

Minkowski’s First Theorem. Let Λ be a lattice and let K a centrally symmetric convex body with vol(K) > 2^{n}det(Λ). Then K contains a non-zero point of Λ. Proof. As K is convex and centrally symmetric, K = \frac{1}{2}K − \frac{1}{2}K. However, vol\frac{1}{2}K > det(Λ), so the result follows by Blichfeldt’s Lemma. □

Let Λ be a lattice, let K be a centrally symmetric convex body. Define 0 < λ_{1} ≤ λ_{2} ≤ … ≤ λ_{n} by λ_{k} = inf{λ : λK contains k linearly independent vectors in Λ}. The numbers λ_{1}, λ_{2}, …, λ_{n} are called the successive minima of K with respect to Λ. Note that we can find vectors b_{1}, b_{2}, …, b_{k} ∈ ℝ^{n} such that b_{k} ∈ λ_{k}\overline{K} ∩ Λ for each k ≤ n. These b_{i} actually form a basis for Λ.

Minkowski’s Second Theorem. Let Λ be a lattice and let K be a convex body. Suppose 0 < λ_{1} ≤ λ_{2} ≤ … ≤ λ_{n} are the successive minima of K with respect to Λ. Then λ_{1}λ_{2} … λ_{n}vol(K) ≤ 2^{n}det(Λ). Proof. Let b_{1}, b_{2}, …, b_{n} be a basis as defined above. Set V_{1} = {0} and, for each i, set V_{i} = ⟨b_{1}, b_{2}, …, b_{i−1}⟩ and W_{i} = ⟨b_{i}, b_{i+1}, …, b_{n}⟩. Define a map c_{i} : iK → K by setting c_{i}(x) equal to the centre of gravity of (x + V_{i}) ∩ K. We note that c_{i} is continuous (K is open) and c_{i}(x) does not depend on the first i−1 co-ordinates of x. Also c_{i}(x)−x ∈ V_{i} and so if c_{i}(x)_{j} is the jth co-ordinate of c_{i}(x) with respect to b_{1}, b_{2}, …, b_{n}, then c_{i}(x)_{j} = x_{j} for j ≥ i. Now define ϕ(x) = ∑_{i=1}^{n}(λ_{i} − λ_{i−1})c_{i}(x), with λ_{0} = 0. Then, expanding ϕ(x),

ϕ(x) = ∑_{i=1}^{n}(λ_{i} − λ_{i−1}) ∑_{j=1}^{n} c_{i}(x)_{j}b_{j}

= ∑_{j=1}^{n} b_{j}[∑_{i=1}^{j} c_{i}(x)_{j}(λ_{i} − λ_{i−1})]
= ∑_{j=1}^{n} b_{j}[∑_{i=1}^{j} x_{j}(λ_{j} − λ_{j−1}) + ∑_{i=j+1}^{n} c_{i}(x)_{j}(λ_{i} − λ_{i−1})]
= ∑_{j=1}^{n} b_{j}(λ_{j}x_{j} + ϕ_{j}(x_{j+1}, …, x_{n}),

where ϕ_{j} is some continuous function. The next claim is that volϕ(K) = λ_{1}λ_{2} … λ_{n}vol(K). First note that ϕ(x)_{n} = λ_{n}x_{n}. For fixed t, let K(t) denote the cross section {x ∈ K : x_{n} = t} of K. Then ϕ restricted to K(t) can be represented by a formula

ϕ(∑_{i=1}^{n−1} x_{i}b_{i} + tb_{n}) = λ_{n}tb_{n} + ∑_{j=1}^{n−1} b_{j}(λ_{j}x_{j} + ψ_{j}(x_{j+1}, …, x_{n−1})

as t is fixed, so by induction vol(ϕ(K(t))) = vol{y ∈ ϕ(K) : y_{n} = λ_{n}t} = λ_{1}λ_{2} … λ_{n−1}. Applying Fubini’s theorem, the theorem is proved. □

For further reading on Minkowski’s Theorems, see [15].

Let r_{1}, r_{2}, …, r_{k} ∈ ℤ_{n} and δ > 0. Then the Bohr neighbourhood B(r_{1}, r_{2}, …, r_{k}; δ) is the set {s ∈ ℤ_{n} : |r_{i}s| ≤ δN, i = 1, 2, …, k} where |r_{i}s| is the distance from r_{i}s to the nearest multiple of N. A d-dimensional arithmetic progression is a subset of ℤ or ℤ_{N} of the form {x_{0} + ∑_{i=1}^{d} a_{i}x_{i} : 0 ≤ a_{i} < s_{i}}. It is proper if the numbers ∑_{i=1}^{d} a_{i}x_{i} are all distinct. It will be seen, in §6, that Bohr neighbourhoods can be used as a step in finding arithmetic progressions, using Fourier transforms.

Theorem 5.7. Let r_{1}, r_{2}, …, r_{k} ∈ ℤ_{N} and 0 < δ < 1/2. Then the Bohr neighbourhood B(r_{1}, …, r_{k}, δ) contains a proper k-dimensional arithmetic progression of cardinality at least (δ/k)^{k}N. Proof. We have s ∈ B(r_{1}, r_{2}, …, r_{k}; δ) if and only if (r_{1}s, r_{2}s, …, r_{k}s) lies within ℓ_{∞}^{k}- distance δN of a point in Nℤ^{k}. Or, equivalently, (r_{1}s, r_{2}s, …, r_{k}s) + Nℤ^{k} contains a point x with ∥x∥_{∞} ≤ δN. Let Λ be the lattice generated by Nℤ^{k} and (r_{1}, r_{2}, …, r_{k}). The index of Nℤ^{k} is clearly N^{k}, and it has index N in Λ. Therefore Λ has index N^{k−1} in ℤ^{k}, implying det(Λ) = N^{k−1} by Lemma 5.3. Let K = {(a_{1}, a_{2}, …, a_{k}) : −1 < a_{i} < 1}; we apply Minkowski’s Second Theorem to K and Λ, to obtain a basis b_{1}, b_{2}, …, b_{k} of ℝ^{k} with b_{i} ∈ Λ and b_{i} having ∥b∥_{∞} = λ_{i}, where λ_{1}λ_{2} … λ_{k}vol(K) ≤ det(Λ) · 2^{k}. Therefore λ_{1}λ_{2} … λ_{k} ≤ N^{k−1}. Now notice that if a_{1}, a_{2}, …, a_{k} are integers with |a_{i}| ≤ δN/kλ_{i}, then ∥∑ a_{i}b_{i}∥ ≤ ∑(δN/λ_{i}k) · λ_{i} = δN. However b_{i} is a vector of the form (r_{1}s_{i}, r_{2}s_{i}, …, r_{k}s_{i}). So |∑ a_{i}s_{i}r_{j}| ≤ δN, j = 1, 2, …, k. Let P be the k-dimensional arithmetic progression {∑_{i=1}^{k} a_{i}s_{i} : |a_{i}| ≤ δN/kλ_{i}}. As the vectors b_{1}, b_{2}, …, b_{k} are independent and ∥∑ a_{i}b_{i}∥ ≤ δN, P is proper – no two terms are equal (mod N). The number of integers a_{i} in the interval [−δN/kλ_{i}, δN/kλ_{i}] is at least δN/kλ_{i}, therefore |P | ≥ ∏ δN/kλ_{i} = (δ/k)^{k}N^{k} · (λ_{1}λ_{2} … λ_{k})^{−1} ≥ (δ/k)^{k}N. □

A layered graph is a graph G with vertex set comprising a disjoint union V_{0} ∪V_{1} ∪…∪V_{n} of sets such that each edge lies between V_{i} and V_{i+1} for some i ∈ [0, n − 1]. It will often be convenient to have an implicit orientation of the edges, from V_{i} to V_{i+1} for each i. A layered graph G is called a Plünnecke Graph if it satisfies the following two conditions:

(1) For u ∈ V_{i−1}, v ∈ V_{i} and distinct w_{1}, w_{2}, …, w_{k} ∈ V_{i+1} with uv, vw_{i} ∈

E(G), i = 1, 2, …, k then there exist distinct v_{1}, v_{2}, …, v_{k} ∈ V_{i} such
that uv_{i} and v_{i}w_{i} ∈ E(G).
(2) For distinct u_{1}, u_{2}, …, u_{k} ∈ V_{i−1}, v ∈ V_{i} and w ∈ V_{i+1}, u_{i}v, v_{i}w ∈ E(G)
there exist distinct v_{1}, v_{2} …, v_{k} such that u_{i}v_{i−1}, v_{i}w ∈ E(G).

[figure: u; v; w; w; w; w; w; w; v; v; v; u; 1; 2; k; 1; 2; k; k; 2; 1]

Given two layered graphs G, H with vertex sets V_{0} ∪ V_{1} ∪ … ∪ V_{n} and W_{0} ∪ W_{1} … ∪ W_{n}, the product graph G × H has vertex set V_{0} × W_{0} ∪ V_{1} × W_{1} ∪ ⋯ ∪ V_{n} × W_{n}) and (v, w) joined to (v′, w′) if and only if vv′ ∈ E(G) or ww′ ∈ E(G). It is easily seen that G × H is a Plünnecke Graph if G and H are. The ith magnification ratio D_{i}(G) of a layered graph G with vertex set V_{0} ∪ V_{1} ∪ … ∪ V_{n} is defined to be

min\{\frac{|Im_{i}(Z)|}{|Z|} : Z ⊂ V_{0}, Z ≠ ∅\}

where Im_{i}(Z) = {y ∈ V_{i} : there is a directed path from some z ∈ Z to y}.

Lemma 5.8. Let G, H be layered graphs. Then D_{i}(G × H) = D_{i}(G)D_{i}(H). Proof. Suppose G, H have vertex sets V_{0} ∪ V_{1} ∪ … ∪ V_{n} and W_{0} ∪ W_{1} ∪ … ∪ W_{n} respectively. Let Y ⊂ V_{0}, Z ⊂ W_{0} satisfy |Im_{i}(Y)|/|Y | = D_{i}(G) and |Im_{i}(Z)|/|Z| = D_{i}(H). Then (v, w) ∈ Im_{i}(Y × Z) if and only if there are paths from some y ∈ Y to v and some z ∈ Z to w – equivalently (v, w) ∈ Im_{i}(Y) × Im_{i}(Z). Therefore D_{i}(G × H) ≤ D_{i}(G)D_{i}(H). Conversely, if F is a layered graph with vertex set P ∪ Q ∪ R and D(P, Q), D(Q, R) and D(P, R) are the magnification ratios in the layered subgraphs between P, Q, Q, R and P, R respectively, then D(P, R) ≥ D(P, Q)D(Q, R). Define layered graph F and vertex sets P, Q and R as follows: let P = V_{0} × W_{0}, Q = V_{0} × W_{i} and R = V_{i} × W_{i}. Join (v, w) ∈ V_{0} × W_{0} to (v′, w′) ∈ V_{0} × W_{i} in F if v = v′ and w′ ∈ Im_{i}({w}). Similarly, join (v, w) ∈ V_{0} × W_{i} to (v′, w′) ∈ V_{i} × W_{i} if w = w′ and v′ ∈ Im_{i}({v}). Then there exists a path from (v, w) ∈ P to (v′, w′) ∈ Q if and only if there exists a path from (v, w) to (v′, w′) in G × H. Hence D(P, R) = D_{i}(G × H). We next show that D(P, Q) = D_{i}(H). If C ⊂ W_{0} with |Im_{i}(C)|/|C| = D_{i}(H), let v ∈ V_{0} and C′ = {v} × C. This shows D(P, Q) ≤ D_{i}(H). Conversely, let C ⊂ P = V_{0} × W_{0}. For each x ∈ V_{0}, let C_{x} = {y : (x, y) ∈ C}. Then |Im_{Q}(C_{x})|/|C_{x}| ≥ D_{i}(H) hence D(P, Q) = D_{i}(H) – note that C_{x} and Im_{Q}(C_{x}) are disjoint and non-empty and C is arbitary. Similarly D(Q, R) = D_{i}(G). Therefore D_{i}(G)D_{i}(H) ≤ D_{i}(G × H). □

Menger’s Theorem. Let G be a graph and let a, b ∈ V (G). Then the maximum number of internally disjoint a-b paths equals the size of a smallest set of vertices separating a from b.

Lemma 5.10. Let G be a Plünnecke Graph, on V_{0} ∪ V_{1} ∪ … ∪ V_{n}, such that D_{n}(G) ≥ 1. Then there are |V_{0}| disjoint paths from V_{0} to V_{n} and, in particular, D_{i} ≥ 1 for all i ≤ n.

Proof. Add a vertex a joined to all of V_{0} and a vertex b joined to all of V_{h}. Let m be the maximum number of disjoint a-b paths. There exists a set S = {s_{1}, s_{2}, …, s_{m}} of size m separating a from b, by Menger’s Theorem. Set S_{i} = S ∩ V_{i}. Choose S such that M = ∑_{s} iS_{i}(s) is a minimum. We claim that S ⊂ V_{0} ∪ V_{n}. Suppose this is false; there exists i : 1 ≤ i < n such that S ∩ V_{i} = {s_{1}, s_{2}, …, s_{q}} ≠ ∅. Let P_{1}, P_{2}, …, P_{m} be disjoint paths from V_{0} to V_{n}. Each P_{i} contains exactly one s_{i}, by the minimality of m. Let s_{i}^{−} and s_{i}^{+} denote the predecessor and successor of s_{i} on the path containing s_{i}, oriented from V_{0} to V_{n}, 1 ≤ i ≤ q. By the minimality of M, we cannot replace any elements of S with predecessors on the paths. So we find a path P from V_{0} to V_{n} that misses {s_{1}^{−}, s_{2}^{−}, …, s_{q}^{−}, s_{q+1}, …, s_{m}}. This path must intersect S, as S is a separating set. Let {r} = P ∩ V_{i−1}. Then the next vertex of P must be s_{i} for some i : 1 ≤ i ≤ q. We claim that every path from {s_{1}^{−}, s_{2}^{−}, …, s_{q}^{−}, r} to s_{1}^{+}, s_{2}^{+}, …, s_{q}^{+} passes through the vertices s_{1}, s_{2}, …, s_{q}. Suppose that this claim is false. If there exists a path Q from s_{i}^{−} to s_{j}^{+} missing s_{1}, s_{2}, …, s_{q}, then the path comprises the segment of P_{i} to s_{i}^{−}, the segment of Q to s_{j}^{+} and the segment of P_{j} onwards, misses S. This contradicts the fact that S is a separating set. Therefore the graph induced by {s_{1}^{−}, …, s_{q}^{−}, r}, {s_{1}, …, s_{q}} and {s_{1}^{+}, …, s_{q}^{+}} is a Plünnecke Graph. In this subgraph, let d^{+}(x) and d^{−}(X) be the in- and out-degrees of x. Since s_{i}^{−} is joined to s_{i}, d^{+}(s_{i}^{−}) ≥ d^{+}(s_{i}). Similarly, d^{−}(s_{i}) ≥ d^{−}(s_{i}^{+}). Also ∑_{i=1}^{q} d^{+}(s_{i}) = ∑_{i=1}^{q} d^{−}(s_{i}^{+}) by counting edges, and d^{+}(r) + ∑ d^{+}(s_{i}^{−}) = ∑ d^{−}(s_{i}). Since d^{+}(r) > 0, we have a contradiction. Therefore S ⊂ V_{0} ∪ V_{n} and, by minimality, S = (V_{0} ∩ S) ∪ (Im_{n}(V_{0}\S) and |S| = |V_{0} ∩ S| + |Im_{n}(V_{0}\S)| ≥ |V_{0} ∩ S| + |V_{0}\S| = |V_{0}|.

Plünnecke’s Theorem. Let G be a Plünnecke Graph on V_{0} ∪ V_{1} ∪ … ∪ V_{n}. Then D_{1} ≥ D_{2}^{1/2} ≥ … ≥ D_{n}^{1/n}. Proof. It is enough to show D_{i}^{1/i} ≥ D_{n}^{1/n} for i < n. When D_{n} = 1, this holds. Suppose D_{n} < 1. Choose a positive integer r; then D_{n}(G^{r}) = D_{n}^{r}, by Lemma 5.8. Given an integer m, we can find a set {b_{1}, b_{2}, …, b_{m}} ⊂ ℤ such that all sums b_{j_{1}} + b_{j_{2}} + … + b_{j_{i}}, with i ≤ m and j_{1} ≤ … ≤ j_{i}, are distinct. The number of these sums, given i, is \binom{m+i−1}{i} – between m^{i}/i! and m^{i}. Let B = {b_{1}, b_{2}, ⋯ b_{m}}, A = {0} and H_{m} be the natural layered graph with layers A, A + B, …, A + nB. Let m be minimal such that m^{n}D_{n}^{r}/m! ≥ 1. Then m = ⌈(n!D_{n}^{−r})^{1/n}⌉ ≤ (n!D_{n}^{−r})^{1/n} + 1. By the choice of m, D_{m}(G^{r} × H_{m}) ≥ 1 so by Lemma 5.10, D_{i}(G^{r} × H_{m}) ≥ 1, and D_{i}(G)^{r} · D_{i}(H_{m}) ≥ 1. However, D_{i}(H_{m}) ≤ m^{i} so

D_{i} = D_{i}(G) ≥ m^{−i/r} ≥ [(n!D_{n}^{−r})^{1/n}]^{−i/r} → D_{n}^{i/n}.

This completes the proof when D_{n} < 1. If D_{n} > 1, consider the reverse I_{n} of H_{n} – vertex sets A + nB, A + (n − 1)B, …, A + B, A. Then D_{n}(I_{m}) ≥ \binom{m+n−1}{m}^{−1} and

D_{i}(I_{m}) ≤ \binom{m + n − i − 1}{m − i} · \binom{m + n − 1}{m}^{−1} ≤ n!m^{n−i}/m^{n} = n!m^{−i}.

Let r be a positive integer and m maximal such that D_{n}^{r}m^{−n} ≥ 1. Then m = ⌊D_{n}^{−r/n}⌋ ≥ D_{n}^{r/n} − 1. Then D_{n}(G^{r} × I_{m}) ≥ 1 so D_{i}(G^{r} × I_{m}) ≥ 1. However D_{i}(G^{r} × I_{m}) ≤ D_{i}^{r}n!m^{−i} so D_{i}^{r} ≥ m^{i}n!^{−1} implying D_{i} ≥ [(D_{n}^{r/n} − 1)^{i}n!^{−1}]^{1/r} → D_{n}^{i/n}, as required. □

Corollary 5.12. Let A and B be non-empty subsets of ℤ_{N} such that |A + iB| ≤ C|A|. For h ≥ i, there is a ∅ ≠ A′ ⊂ A such that |A′ + hB| ≤ C^{h/i}|A′|. Proof. Let G be the natural Plünnecke Graph. If the result were false, then D_{h}(G) > C^{h/i} so D_{i}(G) > C which implies that |A′ + iB| > C|A|, a contradiction. □

Corollary 5.13. If A is a non-empty subset of ℤ and |A+A| ≤ C|A|, then |kA| ≤ C^{k}|A| for each k ≥ 3. Proof. Take i = 1 and B = A in the preceding Corollary. This implies that there exists a non-empty A′ ⊂ A such that |A′ + kA| ≤ C^{k}|A′| ≤ C^{k}|A|, but |A′ + kA| ≥ |kA|, so the result is proved. □

Lemma 5.14. Let U, V, W ⊂ ℤ. Then |U||V − W | ≤ |U + V ||U + W |. Proof. Define, for x ∈ V −W, ϕ(u, x) = (u+v(x), u+w(x)) where v(x) ∈ V, w(x) ∈ W satisfy v(x) − w(x) = x. Then ϕ is an injection U × (V − W) → (U + V) × (U + W). □

Theorem 5.15. Let A, B ⊂ ℤ such that |A + B| ≤ C|A| and let k and l be natural numbers with l ≥ k. Then |kB − lB| ≤ C^{k+l}|A|. Proof. Suppose l ≥ k ≥ 1. By Corollary 5.12, there exists A′ ⊂ A with |A′ + kB| ≤ C^{k}|A′|. Again there exists A′′ ⊂ A′ with |A′′ + lB| ≤ C^{l}|A′′|. Using Lemma 5.14, |A′′||kB − lB| ≤ |A′′ + kB||A′′ + lB| ≤ C^{k+l}|A′||A′′| and the result follows on dividing by |A′′|. □

In the next chapter, we will see the use of Theorem 5.15. In essence, the arithmetic properties of kA for large k are easier to deal with than when k is small. Theorem 5.15 also allows one to deal with distinct set sums A + B by converting the problem to a single set difference problem kB − lB.

§6 Freiman’s Theorem

Freiman’s Theorem [5] describes the structure of a set A under the condition that A + A has size close to that of A. We define a generalised arithmetic progression to be a sum P of ordinary arithmetic progressions (see Theorem 5.7). If P is a subset of a small generalised arithmetic progression then |P +P | is close to |P |. Freiman’s Theorem states the converse: if |P + P | is close to P then P must be contained in a small generalized arithmetic progression.

We now proceed to the proof of Freiman’s Theorem, using a remarkable and ingenious approach due to Ruzsa [12].

Let A ⊂ ℤ_{s} or A ⊂ ℤ and B ⊂ ℤ_{t}. Then ϕ : A → B is called a (Freiman) khomomorphism if whenever x_{1} + x_{2} + … + x_{k} = y_{1} + y_{2} + … + y_{k}, with x_{i}, y_{i} ∈ A, ∑ ϕ(x_{i}) = ∑ ϕ(y_{i}). In addition, ϕ is called a k-isomorphism if ϕ is invertible and ϕ and ϕ^{−1} are k-homomorphisms.

Note that ϕ is a k-homomorphism if the map ψ : (x_{1}, …, x_{k}) ↦ ∑ ϕ(x_{i}) induced by ϕ is a well defined map kA → kB, and a k-isomorphism if ψ is a bijection. Our interest will be in 2-isomorphisms, as these preserve arithmetic progressions – a set 2-isomorphic to an arithmetic progression is clearly an arithmetic progression. We use the following notation: if ϕ : A → B and A′ ⊂ A, then ϕ|_{A′} denotes the restriction of ϕ to A′.

Lemma 6.1. Let A ⊂ ℤ and suppose |kA−kA| ≤ C|A|. Then, for any prime N > C|A|, there exists A′ ⊂ A with |A′| ≥ |A|/k that is k-isomorphic to a subset of ℤ_{N}. Proof. We may suppose A ⊂ ℕ and select a prime p > k max A. Then the quotient map ϕ_{1} : ℤ → ℤ_{p} is a homomorphism of all orders, and ϕ_{1}|_{A} is a k-isomorphism. Now let q be a random element of [p − 1] and define ϕ_{2} : ℤ_{p} → ℤ_{p} by ϕ_{2}(x) = qx. Then ϕ_{2} is an isomorphism of all orders, and hence a k-isomorphism. Let ϕ_{3}(x) = x where ϕ_{3} : ℤ_{p} → ℤ. Then for any j, ϕ_{3}|_{I_{j}} is a k-isomorphism where

I_{j} = \{x ∈ ℤ_{p} : \frac{j − 1}{k}p ≤ x < \frac{j}{k} p − 1\}.

For, if ∑_{i=1}^{k} x_{i} = ∑_{i=1}^{k} y_{i} (mod p) with x_{i}, y_{i} ∈ I_{j}, then ∑_{i=1}^{k} x_{i} = ∑_{i=1}^{k} y_{i} in ℤ. By the pigeonhole principle, there exist A′ ⊂ A with |A′| ≥ |A|/k (depending on q) and ϕ_{2}ϕ_{1}[A′] ⊂ I_{j} for some j. Restricted to A′, ϕ_{3}ϕ_{2}ϕ_{1} is a k-homomorphism. Finally, let ϕ_{4} be the quotient map (a k-homomorphism) ℤ → ℤ_{N}. Then with ϕ = ϕ_{4}ϕ_{3}ϕ_{2}ϕ_{1}, ϕ(x) = qx (mod p) (mod N) and ϕ|_{A′} is a k-homomorphism, as it is the composition of k-homomorphisms.

The only way ϕ|_{A′} is not a k-isomorphism is if there are a_{1}, a_{2}, …, a_{k}, a′_{1}, a′_{2}, …, a′_{k} ∈ A′ such that ∑_{i=1}^{k} ϕ(a_{i}) = ∑_{i=1}^{k} ϕ(a′_{i}) but ∑_{i=1}^{k} ϕ(a_{i}) ≠ ∑_{i=1}^{k} ϕ(a′_{i}). Now ∑_{i} a_{i} ≠ ∑_{i} a′_{i} implies ∑_{i} a_{i} ≠ ∑_{i} a′_{i} (mod p) so we have q(∑_{i} a_{i} − ∑_{i} a′_{i}) (mod p) is a multiple of N. The probability of this event is at most |kA − kA|/N < 1 since |kA − kA| ≤ C|A| and N > C|A|. So for some q, ϕ|_{A′} is a k-isomorphism. □

The next theorem, due to Bogolyubov [3], shows that we may find long arithmetic progressions with small dimension in 2A − 2A. The proof is surprisingly simple.

Theorem 6.2 Let A ⊂ ℤ_{N} with |A| ≥ αN. Then 2A − 2A contains an arithmetic progression of length at least (α^{2}/4)^{α^{−2}}N and dimension at most α^{−2}. Proof. Let g(x) be the number of ways of writing x = (a−b)−(c−d) with a, b, c, d ∈ A. That is, g = (A ∗ A) ∗ (A ∗ A) and x ∈ 2A − 2A if and only if g(x) ≠ 0. Now g(x) = N^{−1} ∑_{r} |Â(r)|^{4}ω^{rx}, by Lemma 2.2 (3). Let K = {r ≠ 0 : Â(r) ≥ α^{3/2}N}. Then

∑_{{r≠0 \atop r∉K}} |Â(r)|^{4} ≤ max_{{r≠0 \atop r∉K}} |Â(r)|^{2} ∑_{r} |Â(r)|^{2} < α^{3}N^{2} · αN^{2} = α^{4}N^{4}.

Therefore, if x is such that Re(ω^{rx}) ≥ 0 for all r ∈ K, then

Re(∑_{r} |Â(r)|^{4}ω^{rx}) > |Â(0)|^{4} − α^{4}N^{4} = 0.

Therefore g(x) ≠ 0 and 2A−2A contains the Bohr neighbourhood B(K; 1/4) – Re(ω^{rs}) ≥ 0 if and only if −N/4 ≤ rs ≤ N/4. Now ∑_{r∈K} |Â(r)|^{2} ≥ kα^{3}N^{2} and ∑_{r∈K} |Â(r)|^{2} ≤ αN^{2}. By Theorem 5.7, 2A − 2A contains the required arithmetic progression. □

We now present Ruzsa’s proof of Freiman’s Theorem.

Freiman’s Theorem. Let A ⊂ ℤ_{N} be a set such that |A + A| ≤ C|A|. Then A is contained in a d-dimensional arithmetic progression P of cardinality at most k|A| where d and k depend on C only. Proof. By Theorem 5.15, |8A − 8A| ≤ C^{16}|A|. By Lemma 6.1, A contains a subset A′ of cardinality at least |A|/8 which is 8-isomorphic to a a set B ⊂ ℤ_{N} with C^{16}|A| < N ≤ 2C^{16}|A|, where N is prime and C|A| < N ≤ 2C|A|, using Bertrand’s Postulate. So |B| = αN with α ≥ (16C^{16})^{−1}. By Theorem 6.2, 2B − 2B contains an arithmetic progression of dimension at most α^{−2} and cardinality at least (α^{2}/4)^{α^{−2}}N ≥ (α^{2}/4)^{α^{−2}}|A|. Since B is 8-isomorphic to A′, 2B −2B is 2-isomorphic to 2A′ −2A′. Any set 2-isomorphic to a ddimensional arithmetic progression is a d-dimensional arithmetic progression. Therefore 2A′−2A′, and hence 2A−2A, contains an arithmetic progression Q of dimension at most α^{−2} and cardinality γ|A|, where γ ≥ (α^{2}/4)^{α^{−2}}. Now let X = {x_{1}, x_{2}, …, x_{k}} ⊂ A be maximal such that x, y ∈ X, x ≠ y imply x−y ∈ Q−Q. Equivalently, all the sets x+Q are disjoint, so X+Q = |X||Q|. Since X is maximal, A ⊂ X+(Q−Q) and X is contained in the k-dimensional arithmetic progression R = {∑_{i=1}^{k} a_{i}x_{i} : 0 ≤ a_{i} ≤ 1}. Clearly |R| ≤ 2^{k}. Therefore A is contained in the arithmetic progression R + (Q − Q), of dimension at most α^{−2}+k. We know that X +(Q−Q) ⊂ A+(4A−4A) = A+2A−2A+2A−2A, and that X + Q ⊂ A + 2A − 2A = 3A − 2A. So |X + Q| ≤ |3A − 2A| ≤ C^{5}|A|, by Theorem 5.15. So k ≤ C^{5}|A|/|Q| ≤ C^{5}γ^{−1}. Finally, |Q − Q| ≤ 2^{α^{−2}}|Q|, by d-dimensionality. So A is contained in an arithmetic progression of dimension at most α^{−2}C^{5}γ^{−1}, and cardinality at most 2^{k}2^{α^{−2}}|Q| ≤ 2^{k}2^{α^{−2}}|2A − 2A| ≤ kC^{4}2^{α^{−2}}|A|. □

The constants from this theorem can be chosen to be d = exp(C^{α}) and k = expexp(C^{β}), where α, β > 0 are absolute constants. Using a refinement of the same approach, a better result can be obtained for set differences of the same set (see [2]):

Theorem 6.4. Let C be a positive real number. Suppose A is a set of integers satisfying |A − A| ≤ C|A| and |A| ≥ \frac{⌊C⌋⌊C+1⌋}{2(⌊C+1⌋−C)}. Then A is a subset of an arithmetic progression of dimension at most ⌊C − 1⌋ and cardinality at most expexp(C^{γ}) where γ > 0 is an absolute constant.

It is likely that a result with very much the same constants is true for A + A. These theorems can be generalized to theorems about abelian groups [4], [13]. We now turn to results concerning difference sets, which will eventually aid in finding four-term arithmetic progressions in the next chapter.

Lemma 6.5. Let A_{1}, A_{2}, …, A_{m} be subsets of [N], α > 0 and suppose that ∑_{i=1}^{m} |A_{i}| ≥ αmN. Then there exists B ⊂ [m], of cardinality at least α^{5}m/2, such that for at least ninety percent of pairs (i, j) ∈ B × B, |A_{i} ∩ A_{j}| ≥ α^{2}N/2. Proof. Let x_{1}, x_{2}, …, x_{5} be chosen randomly and independently from [N]. Let B = {i : {x_{1}, x_{2}, …, x_{5}} ⊂ A}. Then Prob[i ∈ B] = (|A_{i}|/N)^{5} and thus the expected size of B is ∑_{i=1}^{m}(|A_{i}|/N)^{5} ≥ m(∑ |A_{i}|/mN)^{5} ≥ α^{5}m, by Jensen’s Inequality. By Cauchy-Schwartz, E[|B|^{2}] ≥ α^{10}m^{2}. If |A_{i} ∩ A_{j}| ≤ α^{2}N/2, then Prob[i ∈ B, j ∈ B] < α^{10}/32. So if C = {i, j ∈ B × B : |A_{i} ∩ A_{j}| < α^{2}N/2}, then E[|C|] < α^{10}m^{2}/32. It follows that the expected value of E[|B|^{2} − 16|C|] > α^{10}m^{2}/2. Hence there exist x_{1}, x_{2}, …, x_{5} such that |B|^{2} > α^{10}m^{2}/2 and |B|^{2} ≥ 16|C|. □

The following theorem is due to Balog and Szemerédi [1]:

Theorem 6.6. Let A be a subset of an abelian group. Suppose α > 0 and that there are at least α|A|^{3} quadruples (a, b, c, d) ∈ A × A × A × A such that a − b = c − d. Then A contains a subset A′ such that |A′| ≥ c|A| and |A′ − A′| ≤ C|A| where c and C depend on α only. Proof. Set |A| = n. Let f(x) = (A ∗ A)(x), the number of ways of writing x = a − b with a, b ∈ A. Then ∑_{x} f(x) = n^{2}, ∑_{x} f(x)^{2} ≥ αn^{3} and max f(x) ≤ n. It follows that f(x) ≥ αn/2 for at least αn/2 values of x: otherwise let B = {x : f(x) < αn/2} and note ∑_{B} f(x)^{2} < max_{B} f(x) ∑_{B} f(x) < αn^{3}/2 which implies ∑_{x} f(x)^{2} < αn^{3}. Let x be called a popular difference if f(x) ≥ αn/2. Define a graph G with vertex set A and edge set {ab : a−b is a popular difference} – note that f is symmetric. There are at least α^{2}n^{2}/8 edges in G, by the first part of the proof. Let Γ(a) denote the open neighbourhood of a vertex a in G. Then ∑_{a∈A} |Γ(a)| ≥ α^{2}n^{2}/4 so, by the preceding lemma, we can find B ⊂ A of cardinality at least α^{10}n/2^{11} such that |Γ(a) ∩ Γ(b)| ≥ α^{4}n/32 for at least ninety percent of pairs (a, b) ∈ B × B. Define a new graph H with vertex set B and edge set {ab : |Γ(a) ∩ Γ(b)| ≥ α^{4}n/32}. Since the average degree in H is at least 9|B|/10, at least 4|B|/5 vertices have degree at least 4|B|/5. Let A′ be the set of all such vertices; this will be the desired set. Let a, b ∈ A′. There are at least 3|B|/5 numbers c ∈ B such that ac and bc are edges of H, by definition of A′. If ac is an edge of H, then |Γ(a) ∩ Γ(c)| ≥ α^{4}n/32, so there are at least α^{4}n/32 numbers d such that ad and cd are edges of G, and similarly for bc. If ad is an edge of G then there are at least αn/2 pairs (x, y) ∈ A × A such that y − x = d − a so a + y − x = d, and similarly for other edges of G. Therefore there are at least

\frac{3}{5} · \frac{α^{10}}{2^{11}} n · (\frac{α^{4}n}{32})^{2}(\frac{αn}{2})^{4}

distinct octuples (x_{1}, y_{1}, x_{2}, y_{2}, …, x_{4}, y_{4}) ∈ ∏_{i=1}^{8} A such that a + y_{1} − x_{1} + y_{2} − x_{2} + y_{3} − x_{3}+y_{4}−x_{4} = b. If we choose a different pair (a′, b′) ∈ A′×A′ such that b′−a′ ≠ b−a, then the corresponding set of octuples is disjoint. Using the above inequality, |A′ − A′| ≤ n^{8} and so |A′ − A′| ≤ 2^{26}α^{−22}n. Setting c = α^{10}/(5 · 2^{9}) and C = 2^{26}α^{−22} completes the proof. □

Corollary 6.7. Let A ⊂ ℤ^{k} with |A| = m and such that the number of quadruples (a, b, c, d) ∈ A × A × A × A, with a − b = c − d, is at least cm^{3}. Then there exists an arithmetic progression P of cardinality at most Cm and dimension at most d such that |A ∩ Q| ≥ cm, where C and d depend only on c. Proof. This follows directly from the preceding result and Freiman’s Theorem. □

This corollary, or rather a derivative of it, will be very useful in studying four-term arithmetic progressions in the next chapter. In fact, this result is equivalent to Freiman’s Theorem.

Any integer quadruple (a, b, c, d) such that a − b = c − d is called an additive quadruple. For a function ϕ : B → ℤ_{N}, where B ⊂ ℤ_{N}, we say (a, b, c, d) ∈ B × B × B × B is an additive quadruple of ϕ if (a, b, c, d) is an additive quadruple and (ϕ(a), ϕ(b), ϕ(c), ϕ(d)) is an additive quadruple. If B ⊂ ℤ^{d}, then (A ∗ A)(x) is the number of representations of x as y − z. Therefore the number of quadruples (a, b, c, d) ∈ A × A × A × A with a − b = c − d is ∥A ∗ A∥_{2}^{2}. The result we shall use in the next chapter is the following:

Corollary 6.8. Let B ⊂ ℤ_{N} be a set of cardinality βN, and let ϕ : B → ℤ_{N} be a function with at least αN^{3} additive quadruples. Then there exist constant γ and η, depending only on β and c, a ℤ_{N}-arithmetic progression P of cardinality at least N^{γ} and a linear function ψ : P → ℤ_{N} such that ψ(s) = ϕ(s) for at least η|P | values of s ∈ P. Proof. Let Γ denote the graph of ϕ in ℤ × ℤ. By Theorem 6.6, there are constants c and C, depending only on α, and a set A′ ⊂ A of cardinality at least c|A| such that |A′ − A′| ≤ C|A|. A result of Ruzsa shows that if A is any set with |A − A| ≤ C|A|, then there exists a ℤ-arithmetic progression Q of dimension at most 2^{18}C^{32} and size at least (2^{20}C^{32})^{−2^{18}C^{32}}|A|, such that |A ∩ Q| ≥ C^{−5}2^{−d}|Q|. Applying this result to A′, we get a d-dimensional ℤ-arithmetic progression Q of cardinality at most CN, with |Γ∩Q| ≥ cN, where d, c, C depend on α and β only. If Q = Q_{1} +Q_{2} +…+Q_{d}, then at least one P_{i} has cardinality at least (CN)^{1/d} ≥ (cN)^{1/d}, so Q can be partitioned into one-dimensional arithmetic progressions of cardinality at least (cN)^{1/d}. Therefore there is an arithmetic progression R ⊂ ℤ × ℤ, of cardinality at least (cN)^{1/d} such that |R ∩ Γ| ≥ cC^{−1}|R|. As Γ is the graph of a function, R is not vertical unless |R ∩ Γ| = 1 in which case the result is proved. So there exists an arithmetic progression P ⊂ ℤ of the same size as R and a linear function ψ such that Γ contains at least cC^{−1}|P | pairs (s, ψ(s)). Reducing modulo N gives the required result. □

Following Ruzsa’s proof of Freiman’s Theorem, we may take γ = α^{K} and η = exp(−α^{−K}), where K > 0 is an absolute constant.

§7 Szemerédi’s Theorem

To prove Szemerédi’s Theorem [16] for four term arithmetic progressions, following Gowers [7], a two case argument: we consider first sets which behave roughly like random sets, and then those which do not. Then, if a set does not behave in the first sense above, it can be restricted to an arithmetic progression, of reasonable length, in which its density increases. This argument applies a finite number of times as the density is bounded above by 1. Notice the similarities in approach with the proof of Roth’s Theorem. The difference is that a stronger condition, namely quadratic uniformity is required for random-like behaviour with regards to four term arithmetic progressions. The difficult part is finding an arithmetic progression of reasonable length in which the density increases.

We now define the concept of quadratic uniformity. Let f : ℤ_{N} → {z ∈ ℂ : |z| ≤ 1} and α > 0. Then f is α-uniform if ∑_{r} |f̂(r)|^{4} ≤ αN^{4}. If A ⊂ ℤ_{N}, |A| = δN and f(x) = A(x) − δ, then A is α-uniform if f is α-uniform – A is α-uniform if ∑_{r} |Â(r)|^{4} ≤ (δ^{4} + α)N^{4}. The concept of α-uniformity is not quite strong enough, in terms of containing the expected number of arithmetic progressions of length four. We say f is quadratically α-uniform if

∑_{k} ∑_{r} |Δ̂(f; k)(r)|^{4} ≤ αN^{5}

where Δ(f; k)(x) = f(x)\overline{f(x − k)}. We generally define

Δ(f; k_{1}, k_{2}, …, k_{r}) = Δ(Δ(f; k_{1}, k_{2}, …, k_{r−1}); k_{r}).

This is independent of the order of the k_{i}. Also

∑_{k} ∑_{r} |Δ̂(f; k)(r)|^{4} = N ∑_{x,k,l,m} Δ(f; k)(x)\overline{Δ(f; k)(x − ℓ)}\overline{Δ(f; k)(x − m)}Δ(f; k)(x − l − m)
= ∑_{x,k,l,m} Δ(f; k, l, m)(x)
= N ∑_{k,l}|∑_{x} Δ(f; k, l)(x)|^{2}.

In this chapter, D will denote the unit disc in the complex plane.

Lemma 7.1 Let f : ℤ_{N} → 𝔻. Then f is α-uniform if and only if for any function g : ℤ → ℂ,

∑_{k}|∑_{s} f(s)\overline{g(s − k)}|^{2} ≤ \sqrt{α}N^{2}∥g∥_{2}^{2}.

Also, f is α-uniform if max_{r} |f̂(r)| ≤ α^{1/2}N. Proof. For the first part, we know that

∑_{k}|∑_{s} f(s)\overline{g(s − k)}|^{2} = ∑_{k} |f ∗ g)k)|^{2}
= N^{−1} ∑_{r} |(f ∗ g)ˆ (r)|^{2}
= N^{−1} ∑_{r} |f̂(r)|^{2}|ĝ(r)|^{2}
≤ (∑_{r} |f̂(r)|^{4})^{1/2}(∑_{r} |ĝ(r)|^{4})^{1/2},

by the Cauchy-Schwartz inequality, and Lemma 2.2. Since (∑_{r} |ĝ(r)|^{4})^{1/2} ≤ ∑_{r} |ĝ(r)|^{2}, if f is α-uniform then the inequality in f and g above must hold. For the second part, we use the fact that ∑_{r} |f̂(r)|^{4} ≤ max_{r} |f̂(r)|^{2} ∑_{r} |f̂(r)|^{2}, and Parseval’s Identity from Lemma 2.2 to obtain ∑_{r} |f̂(r)|^{2} ≤ N^{2} and the result follows. □

The first few results lead to showing that quadratically α-uniform sets do contain fourterm arithmetic progressions. We begin by proving a number of technical lemmas concerning α-uniformity. The following lemma shows that a quadratically uniform set is also uniform.

Lemma 7.2. If f is quadratically α-uniform, then f is α^{1/2}-uniform.

Proof. (∑_{r} |f̂(r)|^{4})^{2} = (N ∑_{x,k,l} f(x)\overline{f(x − k)}\overline{f(x − l)}f(x − k − l))^{2}

= N^{2}(∑_{x,k,l} Δ(f; k, l)(x))^{2}
≤ N^{4} ∑_{k,l}|∑_{x} Δ(f; k, l)(x)|^{2}
= N^{3} ∑_{k,r} |Δ̂(f; k)(r)|^{4} ≤ αN^{8}. □

Lemma 7.3. Let f_{1}, f_{2}, f_{3} : ℤ_{N} → 𝔻. Suppose that f_{3} is α-uniform. Then we have |∑_{a,d} f_{1}(a)f_{2}(a + d)f_{3}(a + 2d)| ≤ α^{1/4}N^{2}.

Proof. If S = ∑_{a,d} f_{1}(a)f_{2}(a + d)f_{3}(a + 2d) then

|S| = | ∑_{a+c=2b} f_{1}(a)f_{2}(b)f_{3}(c)|
= |N^{−1} ∑_{r} f̂_{1}(r)f̂_{2}(−2r)f̂_{3}(r)|
≤ N^{−1} max_{r} f̂_{3}(r) · (∑_{r} |f̂_{1}(r)|^{2})^{1/2} · (∑_{r} |f̂_{2}(r)|^{2})^{1/2}
≤ N^{−1} · α^{1/4}N · N^{2} = α^{1/4}N^{2}. □

Lemma 7.4. Let f_{1}, f_{2}, f_{3}, f_{4} : ℤ_{N} → 𝔻 and α > 0. Suppose f_{4} is quadratically α-uniform. Then |∑_{a,d} f_{1}(a)f_{2}(a + d)f_{3}(a + 2d)f_{4}(a + 3d)| ≤ α^{1/8}N^{2}. Proof. Let S be the sum we are estimating. Then

|S|^{2} ≤ N ∑_{a}|∑_{d} f_{1}(a)f_{2}(a + d)f_{3}(a + 2d)f_{4}(a + 3d)|^{2}
≤ N ∑_{a}|∑_{d} f_{2}(a + d)f_{3}(a + 2d)f_{4}(a + 3d)|^{2}
≤ ∑_{a} ∑_{d,e} f_{2}(a + d)\overline{f_{2}(a + e)}f_{3}(a + 2d)\overline{f_{3}(a + 2e)}f_{4}(a + 3e)\overline{f_{4}(a + 3e)}
= N ∑_{a} ∑_{d,k} Δ(f_{2}; k)(a + d)Δ(f_{3}; 2k)(a + 2d)Δ(f_{3}; 3k)(a + 3d)
= N ∑_{a} ∑_{d,k} Δ(f_{2}; k)(a)Δ(f_{3}; 2k)(a + 2d)Δ(f_{3}; 3k)(a + 3d).

Since f_{4} is quadratically α-uniform, there are α(k), k ∈ ℤ_{N} such that for each k, Δ(f_{4}; k) is α(k)-uniform and N^{−1} ∑_{k} α(k) = α. By Lemma 7.3, the above expression is at most

N ∑_{k} α(3k)^{1/4}N^{2} = N ∑_{k} α(k)α(k)^{1/4}N^{2}
≤ Nα^{1/4}NN^{2} = α^{1/4}N^{4}. □

Theorem 7.5. Let A_{1}, A_{2}, A_{3}, A_{4} ⊂ ℤ_{N} with |A_{i}| = δ_{i}N. Suppose that A_{3} is α^{1/2}- uniform and A_{4} is quadratically α-uniform. Then ∑_{a,d} A_{1}(a)A_{2}(a + d)A_{3}(a + 2d)A_{4}(a + 3d) − δ_{1}δ_{2}δ_{3}δ_{4}N^{2} ≤ 12α^{1/8}N^{2}. Proof. Set f_{i}(x) = A_{i}(x) − δ_{i}. Replace the A_{i}(·) with f_{i}(·) + δ_{i} in the sum we wish to estimate. The sum splits into sixteen parts. We think of δ_{i} as constant functions and apply the two preceding lemmas. If we choose f_{4} in applying Lemma 7.4, then the sum is at most α^{1/8}N^{2}. If we do not choose f_{4}, but choose f_{3}, then the sum is at most (α^{1/2})^{1/4}N^{2} = α^{1/8}N^{2}, by Lemma 7.3. If neither f_{3} nor f_{4} is chosen, we use the identity

∑_{a,d} g_{1}(a)g_{2}(a + d) = ∑_{a,b} g_{1}(a)g_{2}(b) = (∑_{a} g_{1}(a))(∑_{b} g_{2}(b)).

This shows that all of the remaining terms are zero, apart from the constant term, which is ∑_{a,d} δ_{1}δ_{2}δ_{3}δ_{4} = N^{2}δ_{1}δ_{2}δ_{3}δ_{4}. This completes the proof of Theorem 7.5. □

Corollary 7.6. Let A ⊂ [N], |A| = δN where δ > 0. Suppose that A is quadratically α-uniform. If α ≤ δ^{32}/2^{88} and N ≥ 200/δ^{4}, then A contains an arithmetic progression of length four or we can find a subprogression where A has density at least \frac{9}{8}δ. Proof. Let A_{1} = A_{2} = A ∩ [2N/5, 3N/5] and A_{3} = A_{4} = A. If |A| ≤ δ/10, we have A ∩ [0, 2N/5] or A ∩ [3N/5, N) of cardinality at least δ(9N/20). By Theorem 7.5, A_{1} × A_{2} × ⋯ × A_{4} contains at least (δ^{4}/100 − 12α^{1/8})N^{2} ℤ_{N} arithmetic progressions of length four. Provided this is greater than N, we have a ℤ-arithmetic progression – all ℤ_{N} arithmetic progressions in A_{1} × A_{2} × A_{3} × A_{4} are ℤ-arithmetic progressions. □

We now turn to the case where f is not quadratically uniform. If A is the corresponding set of density δ, then we plan to show that A intersects a ℤ-arithmetic progression P ⊂ {1, 2, …, N} of size at least N^{d} and such that |A ∩ P | ≥ (δ + ε)|P | where ε and d depend only on α and δ.

Lemma 7.7. Suppose that f is not quadratically α-uniform. Then there exists a set B, of cardinality at least αN/2, and a function ϕ : B → ℤ_{N} such that

∑_{k∈B} |Δ̂(f; k)(ϕ(k))|^{2} ≥ (α/2)^{2}N^{3}.

Proof. Since f is not quadratically α-uniform, ∑_{k} ∑_{r} |Δ̂(f; k)(r)|^{4} > αN^{5}. So there must be more than αN/2 values of k for which ∑_{r} |Δ̂(f; k)(r)|^{4} ≤ αN^{3}/2. So there are more than αN/2 values of k such that max_{r} |Δ̂(f; k)(r)| ≥ (α/2)^{1/2}N, by the second part of Lemma 7.1. Therefore there exists a set B, of cardinality at least αN/2, and a function ϕ such that |Δ̂(f; k)(r)| ≥ (α/2)^{1/2}N for all k ∈ B. Summing this over k ∈ B gives the required result. □

Recall the definition of an additive quadruple, given in the last part of the last chapter.

Lemma 7.8. Suppose that f : ℤ_{N} → 𝔻, B ⊂ ℤ_{N} and ϕ : ℤ_{N} is a function such that, for some α > 0,

∑_{k∈B} |Δ̂(f; k)(ϕ(k))|^{2} ≥ αN^{3}.

Then there exist at least α^{4}N^{3} quadruples (a, b, c, d) ∈ B×B×B×B such that a+b = c+d and ϕ(a) + ϕ(b) = ϕ(c) + ϕ(d). Proof. Expanding the left hand side of the inequality, we get:

∑_{k∈B} |Δ̂(f; k)(ϕ(k))|^{2} ≥ (α/2)^{2}N^{3}

⇒ ∑_{k∈B} ∑_{s,t} f(s)\overline{f(s − k)f(t)}f(t − k)ω^{−ϕ(k)(s−t)} ≥ αN^{3}
⇒ ∑_{k∈B} ∑_{s,u} f(s)\overline{f(s − k)f(s − u)}f(s − k − u)ω^{−ϕ(k)u} ≥ αN^{3}
⇒ ∑_{u,s}| ∑_{k∈B} \overline{f(s − k)}f(s − k − u)ω^{−ϕ(k)u}|≥ αN^{3}
⇒ ∑_{u,s}| ∑_{k∈B} \overline{f(s − k)}f(s − k − u)ω^{−ϕ(k)u}|^{2}≥ α^{2}N^{4}.

Let γ(u) satisfy ∑_{s}|∑_{B} \overline{f(s − k)}f(s − k − u)ω^{−ϕ(k)u}|^{2}= γ(u)N^{3}. Using the first part of Lemma 7.1, we deduce that B(k)ω^{ϕ(k)u} is not γ(u)^{2}-uniform, and therefore (by definition) ∑_{r}|∑_{B} ω^{ϕ(k)u−rk}|^{4} ≥ γ(u)^{2}N^{4}. By the above inequalities, ∑_{u} γ(u) ≥ α^{2}N so ∑_{u} γ(u)^{2} ≥ α^{4}N. Therefore

∑_{u} ∑_{r}| ∑_{k∈B} ω^{ϕ(k)u−rk}|^{4} ≥ α^{4}N^{5}.

Expanding the left hand side we find that:

∑_{u,r} ∑_{a,b,c,d∈B} ω^{(ϕ(a)+ϕ(b)−ϕ(c)−ϕ(d))u}ω^{−r(a+b−c−d)} ≥ α^{4}N^{5}.

However, the left side is N^{2} times the number of quadruples (a, b, c, d) ∈ B × B × B × B for which a + b = c + d and ϕ(a) + ϕ(b) = ϕ(c) + ϕ(d). □

We recall the definition of additive quadruples for a function ϕ, from the end of chapter six.

Lemma 7.9. Suppose that ϕ : ℤ_{N} → ℤ_{N} has at least αN^{3} additive quadruples. Then there exist η, γ, depending only on α, and an arithmetic progression P of length at least N^{γ} such that for some λ and μ,

∑_{k∈P} |Δ̂(f; k)(λk + μ)|^{2} ≥ ηN^{2}|P |.

Proof. This follows from Corollary 6.8 with γ = α^{K} and η = exp(−α^{−K}). □

Lemma 7.10. Let f : ℤ_{N} → 𝔻. Let η > 0 and P ⊂ ℤ_{N} be an ℤ_{N}-arithmetic progression such that, with λ, μ ∈ ℤ_{N},

∑_{k∈P} |Δ(f; k)ˆ (2λk + μ)|^{2} ≥ η|P |N^{2}

Then, for |P | ≤ N^{1/2}, there exists a partition of ℤ_{N} into translates P_{1}, P_{2}, …, P_{M} of P or P with an endpoint removed, such that for each i we can find r_{i} ∈ ℤ_{N} such that

∑_{i}| ∑_{x∈P_{i}} f(x)ω^{−λx^{2}−r_{i}x}| ≥ η|P |N/2.

Proof. ∑_{k∈P} |∑_{x} f(x)\overline{f(x − k)}ω^{−(2λk+μ)x}| ≥ η|P |N^{2}

⇒ ∑_{k∈P} ∑_{x} ∑_{y} f(x)\overline{f(x − k)}\overline{f(y)}f(y − k)ω^{−(2λk+μ)(x−y)} ≥ η|P |N^{2}
⇒ ∑_{k∈P} ∑_{x} ∑_{u} f(x)\overline{f(x − k)}\overline{f(x − u)}f(x − k − u)ω^{−(2λk+μ)u} ≥ η|P |N^{2}.

Every u ∈ ℤ_{N} can be written in exactly |P | ways as v + l with v ∈ ℤ_{N} and l ∈ P, therefore,

∑_{k∈P} ∑_{l∈P} ∑_{x} ∑_{v} f(x)\overline{f(x − k)}\overline{f(x − v − l)}f(x − v − k − l)ω^{−(2λk+μ)(v+l)} ≥ η|P |^{2}N^{2}.

Hence we can find v ∈ ℤ_{N} such that

|∑_{k∈P} ∑_{l∈P} ∑_{x} f(x)\overline{f(x − k)}\overline{g(x − l)}g(x − k − l)ω^{−(2λvk+μv+2λkl+μl)}| ≥ η|P |^{2}N

where g(x) = f(x − v). Now with 2λvk = 2λv(x − l − (x − k − l)), μl = μ(x − (x − l)) and 2λkl = λ(x^{2} − (x − k)^{2} − (x − l)^{2} + (x − k − l)^{2}),

|∑_{k∈P} ∑_{l∈P} ∑_{x} h_{1}(x)\overline{h_{2}(x − k)}\overline{h_{3}(x − l)}h_{4}(x − k − l)| ≥ η|P |^{2}N

where h_{1}(x) = f(x)ω^{−λx^{2}−μx}, h_{2}(x) = f(x)ω^{−λx^{2}}, h_{3}(x) = g(x)ω^{−λx^{2}+(2λv−μ)x} and h_{4}(x) = g(x)ω^{−λx^{2}+2λvx}. This implies that

∑_{x}|∑_{k∈P} ∑_{l∈P} h_{1}(x)\overline{h_{2}(x − k)}\overline{h_{3}(x − l)}h_{4}(x − k − l)| ≥ η|P |^{2}N.

For each x, define η(x) by |∑_{k∈P} ∑_{l∈P} \overline{h_{2}(x − k)}\overline{h_{3}(x − l)}h_{4}(x − k − l)| = η(x)|P |^{2}. Then

N^{−1} |∑_{r} ∑_{k∈P} ∑_{l∈P} ∑_{m∈P +P} \overline{h_{2}(x − k)}\overline{h_{3}(x − l)}h_{4}(x − m)ω^{r(k+l−m)}| ≥ η(x)|P |^{2}
⇒ ∑_{r}|∑_{k∈P} h_{2}(x − k)ω^{−rk}| · |∑_{l∈P} h_{3}(x − l)ω^{−rl}| · | ∑_{m∈P +P} h_{4}(x − m)ω^{−rm}| ≥ η(x)|P |^{2}N.

However ∑_{r}|∑_{l∈P} h_{3}(x − l)ω^{−rl}|^{2} = N ∑_{l∈P} |h_{3}(x − l)|^{2} ≤ N|P | and similarly for h_{4}. Applying Cauchy-Schwartz,

max_{r}|∑_{k∈P} h_{2}(x − k)ω^{−rk}| · 2^{1/2}N|P | ≥ η(x)|P |^{2}N.

So there exists r_{x} such that |∑_{k∈P} h_{2}(x − k)ω^{r_{x}k}| ≥ η|P |2^{−1/2}. That is,

|∑_{k∈P} f(x − k)ω^{−λ(x−k)^{2}+r_{x}(x−k)}| ≥ η(x)|P |2^{−1/2}.

Summing over all x, we obtain ∑_{x}|∑_{y∈x−P} f(y)ω^{−λy^{2}+r_{x}y}| ≥ η|P |N2^{−1/2}. An easy averaging argument then shows that we can partition ℤ_{N} into translates of copies of P (or P with an endpoint removed), which we call P_{1}, P_{2}, ⋯, P_{M} with

∑_{i}| ∑_{y∈P_{i}} f(y)ω^{−λy^{2}−r_{i}y}| ≥ ηN|P |/2.

The division by 2^{1/2} is to ensure that the P_{i} differ in length by at most 1. □

Let ϕ : ℤ_{N} → ℤ_{N} be a function. We define, for S ⊂ ℤ_{n}, diamϕ(S) = max{ϕ(x) − ϕ(y) : x, y ∈ S}.

Lemma 7.11. Let m, r, l ∈ [N] and let P be a ℤ_{N}-arithmetic progression of length m. Let ϕ : ℤ_{N} → ℤ_{N} be a linear function. Then, provided that l ≤ (m/r)^{1/3}, P can be partitioned into subprogressions P_{i}, i ≥ 1 of lengths l or l−1, such that diamϕ(P_{i}) ≤ N/r for each i.

Proof. Without loss of generality, suppose P = [0, m−1]. By the pigeonhole principle, there exists d ≤ rl such that |ϕ(d) − ϕ(0)| ≤ N/rl. Set Q = {x, x + d, …, x + (l − 1)d}. Then |ϕ(x+ld)−ϕ(x)| ≤ l|ϕ(d)−ϕ(0)| ≤ N/r so diamϕ(Q) ≤ N/r. As each congruence class modulo d has size at least m/d ≥ m/rl ≥ l^{2}, we can split P into copies P_{i} of Q, differing in length by at most one. □

In the next lemma, we apply Weyl’s Theorem (Theorem 3.10):

Lemma 7.12. Let m ∈ [N]. and let ϕ : ℤ_{N} → ℤ_{N} be a quadratic function and let P be a ℤ_{N}-arithmetic progression of length m. Then for any l ≤ m^{1/18.128}, P can be partitioned into subprogressions P_{i}, i ≥ 1, of lengths l or l − 1, with diamϕ(P_{i}) ≤ Cm^{−1/6.128}N. Proof. Suppose ϕ(x) = ax^{2} + bx + c and P = [m]. Choose d ≤ m^{1/2} such that, modulo N, |ad^{2}| ≤ m^{−1/128}N: this is possible, by Theorem 3.10 with k = 2. Let t ≤ m^{1/3.128} and Q_{i} = {x, x + d, …, x + (t − 1)d}. Then ϕ(x + td) − ϕ(x) = (2axd + bd)t + ad^{2}t^{2}. We note that |ad^{2}t^{2}| ≤ Cm^{−1/3.128}N modulo N. Applying Lemma 7.11 to Q_{i}, with r = m^{1/6.128}, for l ≤ m^{1/18.128}, Q_{i} can be partitioned into subprogressions R_{ij} of sizes l or l − 1 with diamϕ(R_{ij}) ≤ N/r = Cm^{−1/6.128}N. Considering a partition of P into Q_{i}s, the R_{ij} form the required arithmetic progressions. □

Lemma 7.13. Let ϕ : ℤ_{N} → ℤ_{N} be a quadratic polynomial and r ≤ N. Then there exists m ≤ Cr^{1−1/18.128} such that [0, r −1] can be partitioned into arithmetic progressions P_{1}, P_{2}, …, P_{m}, of lengths differing by at most 1, and such that, if f : ℤ_{N} → 𝔻 is any function with

|∑_{x=0}^{r−1} f(x)ω^{−ϕ(x)}| ≥ ηr,

then

∑_{j=1}^{m}| ∑_{x∈P_{j}} f(x)| ≥ ηr/2.

Proof. By Lemma 7.12, we find P_{1}, P_{2}, …, P_{m} such that diamϕ(P_{i}) ≤ CNr^{−1/6.128}. Provided N is sufficiently large, this is at most ηN/4π. By the triangle inequality,

∑_{j=1}^{m}| ∑_{x∈P_{j}} f(x)ω^{−ϕ(x)}| ≥ ηr.

Let x_{j} ∈ P_{j}. The estimate on the diameter of ϕ(P_{i}) implies that |ω^{−ϕ(x)} − ω^{−ϕ(x_{j}}| ≤ η/2 for all x ∈ P_{j}. So

∑_{j=1}^{m}| ∑_{x∈P_{j}} f(x)| = ∑_{j=1}^{m}| ∑_{x∈P_{j}} f(x)ω^{−ϕ(x_{j})}|
≥ ∑_{j=1}^{m}| ∑_{x∈P_{j}} f(x)ω^{−ϕ(x)}| − ∑_{j=1}^{m}(η/2)|P_{j}| ≥ ηr/2.

This completes the proof. □

Szemerédi’s Theorem. There exists an absolute constant c > 0 such that if A ⊂ [N], |A| = δN and δ ≥ (log log log N)^{c}, then A contains an arithmetic progression of length four. Proof. Regard A as a subset of ℤ_{N}. If A is quadratically α = δ^{32}/2^{88}-uniform, then the theorem is proved, by Corollary 7.6. Let f(x) = A(x) − δ and suppose f is not quadratically α-uniform. By Lemma 7.7, there exists a set B of cardinality at least αN/2 and a function ϕ : B → ℤ_{N} such that

∑_{k∈B} |Δ̂(f; k)(ϕ(k))| ≥ (α/2)^{2}N^{3}.

By Lemma 7.8, ϕ has at least (α/2)^{8}N^{3} additive quadruples and so, by Lemma 7.9, there exists an arithmetic progression P with |P | ≥ N^{γ} and

∑_{k∈P} |Δ(f; k)ˆ (2λk + μ)|^{2} ≥ η|P |N^{2}

By Ruzsa’s proof of Freiman’s Theorem, we may choose γ = α^{K} and η ≥ exp(−α^{−K}) where K > 0 is an absolute constant. By Lemma 7.10, we then have

∑_{i}| ∑_{x∈P_{i}} f(x)ω^{−λx^{2}−r_{i}x}| ≥ η|P |N/2,

where the P_{i} are as in Lemma 7.10. Apply Lemma 7.13 in each P_{i} to obtain further progressions P_{ij}, of cardinalities differing by at most 1, and with average lengths C|P |^{1/18.128} (for some constant C > 0) and such that

∑_{i} ∑_{j=1}^{m}| ∑_{x∈P_{ij}} f(x)| ≥ ηN|P |/4.

A consequence of Lemma 7.12 is that we can insist that the P_{ij} are ℤ-arithmetic progressions, except that (by Lemma 2.3) the average length of P_{ij} is C|P |^{1/2.18.128}, where C > 0 is a constant and no P_{ij} has more than twice this length. Relabel the P_{ij}s as Q_{1}, Q_{2}, …, Q_{M}, where M = N^{−γ/2.18.128} and the Q_{i} have average length N^{γ/2.18.128}. As ∑ f(x) = 0, we have

∑_{i}(| ∑_{x∈Q_{i}} f(x)| + ∑_{x∈Q_{i}} f(x)) ≥ ηN/4.

The contribution of Q_{i} with |Q_{i}| ≤ \sqrt{N/M} is at most 2N/\sqrt{M} ≤ ηN/8, therefore there exists Q_{i} such that |Q_{i}| ≥ \sqrt{N/M} such that | ∑_{x∈Q_{i}} f(x)| + ∑_{x∈Q_{i}} f(x) ≥ η|Q_{i}|/8. This implies that ∑_{x∈Q_{i}} f(x) ≥ η|Q_{i}|/16. So we have shown that there exists an arithmetic progression Q, of length at least \sqrt{N/M} ≥ N^{γ/4.18.128} = N^{δ^{c}} such that |A ∩ Q| ≥ (δ + exp[−δ^{c}])|Q|, where c > 0 is a constant. Rewriting this in terms of δ, a four-term arithmetic progression must be found when δ ≥ (log log log N)^{−c} for some c > 0. □

References

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

[2] Y. Bilu, Structure of sets with small sumset, Structure Theory of Set Addition, Astérisque 258 (1999) 77–108.

[3] N. N. Bogolyubov, Zap. Kafedry Mat. Fizi. 4 (1939) 185.

[4] P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936) 261–264.

[5] G. R. Freiman, Foundations of a Structural Theory of Set Addition, Translations of Mathematical Monographs 37, Amer. Math. Soc., Providence, R. I., USA.

[6] H. Fürstenburg, Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256.

[7] W. T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998) (3) 529–551.

[8] A. W. Hales, R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.

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

[10] N. M. Korobov, Exponential Sums and their Applications, Mathematics and its Applications 80, Kluwer, (1992).

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

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

[13] I. Ruzsa, An analog of Freiman’s Theorem for abelian groups, Structure Theory of Set Addition, Astérisque 258 (1999) 323–326.

[14] S. Shelah, Primitive recursive bounds for van der Waerden Numbers, J. Amer. Math. Soc. 1(3) (1988) 683–697.

[15] C. F. Siegel, Lectures on Geometric Number Theory,

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

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

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

[19] G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cam. Studies in Advanced Math. 46 Cam. Univ. Press (1995).

[20] B. L. van der Waerden, Beweis einer Baudetschen vermutung, Nieuw Arch. Wisk. 15 (1927), 212–216.

[21] R. C. Vaughan, The Hardy-Littlewood Method, 2nd Ed. Cam. Tracts in Math. 125 Cam. Univ. Press (1997).

[22] I. M. Vinogradov, The method of trigonometrical sums in the theory of numbers, Trav. Inst. Math. Steklof 23 (1947).

[23] H. Weyl, Über die Gleichverteilung von Zahlen mod Eins, Math. Annalen 77 (1913), 313–352.

Notation

A  general integer set
A + B  sum set {a + b : a ∈ A, b ∈ B}
∥α∥  distance from α to the nearest integer
{α}  fractional part of α
A^{∗}  set of subset sums {∑ ε_{i}a_{i} : ε_{i} ∈ {0, 1}, a_{i} ∈ A}
B(K, δ)  Bohr neighbourhood
ℂ  field of complex numbers
c(q)  min{c : |A| ≥ c, A ⊂ ℤ_{q} ⇒ A^{∗} = ℤ_{q}}
c, C  constant
Γ  graph of a function
Γ(a)  neighbourhood of a vertex a
d  dimension of arithmetic progression
𝔻  unit disc in ℂ
D_{i}(G)  ith magnification ratio
det(Λ)  determinant of lattice Λ
Δ(f; k)(r) f(r)\overline{f(r − k)}
e(α)  exp(2πiα)
E  expectation
δ  density
f ∗ g  convolution
f̂  fourier transform of f
∥g∥_{2}  ℓ^{2}-norm of function g
G × H  product of layered graphs
HJ(k, r) Hales-Jewett numbers
i, j, k  counting variables
Im_{i}(Y)  image of Y in ith layer

kA  k-fold sum A + A + … + A of A
K  convex body or absolute constant
K(t)  tth cross-section of body K
Λ(x)  von Mangoldt’s function
(m, n] integers greater than m and less than or equal n
μ(x)  Möbius function
n_{k}(N) number of elements required in [N] for a k-term progression
N  large integer
[N]  {1, 2, …, N}
ℕ  natural numbers
Prob  probability
ℝ  real numbers
τ(n)  divisor function
vol(K) volume of K
W (k, r) van der Waerden numbers
x ⊕ jA Hales-Jewett line
ℤ  set of integers
ω^{r}  exp(2πir/N)