§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 1. Let x ∈ ℕ. Then ∑_{d|x} Λ(d) = log x.

Proof. Write x as a product of prime powers and it becomes obvious. □

Lemma 2. Let x ∈ ℕ. Then ∑_{d|x} μ(d) equals zero unless x = 1 in which case it equals one.

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 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. |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 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 §3 that the numbers 0, α, 2α, …, ⌊(q/2)⌋α are (2q)^{−1}-separated. Therefore,

\begin{aligned}∑_{x⩽q/2} min\{∥αx∥^{−1}, Qx^{−1}\} & ⩽ 2 ∑_{x⩽⌈q/4⌉} 2q/x \\ & ⩽ 4q log q . \end{aligned}

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 2 of §3, 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, 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

\begin{aligned}∑_{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) , \end{aligned}

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. (In principle one might show that there was considerable cancellation, but then one would be back to trying to understand mysterious functions rather than writing g(α) as a clever combination of terms that can be estimated by elementary means.) 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. (This is the point that I did not appreciate until shortly after the lecture where I had problems with x = y. It results in the extra error term T, and the extra restriction X < x which helps to estimate U.) So it is likely that Vaughan arrived at the identity which we now prove by a process of trial and error, starting with the observations above.

Lemma 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 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),

∑_{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 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 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 5 (taking into account that log X = (2/5) log n) we obtain the bound claimed. □

Because I did not prove the next lemma in lectures, it is starred. However, it is no harder than the other ones.

Lemma 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 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 5. □

The next lemma is the correct version of the one I got stuck on in lectures. The extra ingredient needed is the bounding of x away from zero, which stops u from getting too large.

Lemma 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

\begin{aligned}∑_{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} , \end{aligned}

which is at most 2^{i}(log n)^{3}, by Lemma 3. (The factor 2 disappeared, because 2^{i} < 2n^{3/5}, so log(2^{i}) is actually a bit smaller than log n, but this is of course a desperately unimportant point.)

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 2 of §3, 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. In the lectures I used Lemma 5 of this section where I have just used Lemma 2 of §3. However, since z is roughly constant, it is clear that that could not have achieved anything. (I was imitating Nathanson, which was a mistake, and he appears not to notice that he has to take account of the case z = 0.) 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 and 6 to 9 we obtain the following result.

Theorem 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, 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, I use a different argument, which I believe explains 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 §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 20 below does not translate into a solution of the Goldbach conjecture.)

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

Lemma 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 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}, …, 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 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. Theorem 12. 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 Theorem 12 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 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 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 14. Let a, q, X be as in Lemma 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 13 and the remark following Lemma 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.) □

I have a more streamlined (and rigorous) presentation of the next part of the proof than I gave in lectures. But once again I stress that something very simple is going on, and the best way to understand this is to prove it for yourself. Lemma 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 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 10 implies that f(α) = O(n(log n)^{4−A/2}), while Lemma 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 14 tells us that G satisfies the conditions for Lemma 15. But ∑_{x⩽n} G(x)e(αx) = f(α) − h_{1}(α), so Lemma 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 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 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

\begin{aligned}∑_{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) . \end{aligned}

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 17. □

Corollary 19. Let α, b, q and β be as in Lemma 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 12 and Lemmas 13, 15 and 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 12 tells us that the conditions for Lemma 15 are satisfied. But this implies that f(α) = ∑_{x⩽n} H_{q}(x)e(αx) + O(n(log n)^{−A}). Then Lemma 18 gives us our estimate for f(α). The same argument works for h_{1}(α) if we use Lemma 13 instead of Theorem 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 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 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 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. □

On writing out the next corollary it occurs to me that I can’t have done it correctly in lectures, where I think I absent-mindedly estimated the number of ways of writing n as x + y + z with only x and y in Q.

Corollary 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 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 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.

Theorem 22. (Vinogradov) 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 enough for our purposes to show that ∫ f(α)^{3}e(−αn) dα ≠ 0. But, by Corollary 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. □