We have seen in previous notes that the operation of forming a Dirichlet series
or twisted Dirichlet series
is an incredibly useful tool for questions in multiplicative number theory. Such series can be viewed as a multiplicative Fourier transform, since the functions and are multiplicative characters.
Similarly, it turns out that the operation of forming an additive Fourier series
where lies on the (additive) unit circle and is the standard additive character, is an incredibly useful tool for additive number theory, particularly when studying additive problems involving three or more variables taking values in sets such as the primes; the deployment of this tool is generally known as the Hardy-Littlewood circle method. (In the analytic number theory literature, the minus sign in the phase is traditionally omitted, and what is denoted by here would be referred to instead by , or just .) We list some of the most classical problems in this area:
- (Even Goldbach conjecture) Is it true that every even natural number greater than two can be expressed as the sum of two primes?
- (Odd Goldbach conjecture) Is it true that every odd natural number greater than five can be expressed as the sum of three primes?
- (Waring problem) For each natural number , what is the least natural number such that every natural number can be expressed as the sum of or fewer powers?
- (Asymptotic Waring problem) For each natural number , what is the least natural number such that every sufficiently large natural number can be expressed as the sum of or fewer powers?
- (Partition function problem) For any natural number , let denote the number of representations of of the form where and are natural numbers. What is the asymptotic behaviour of as ?
The Waring problem and its asymptotic version will not be discussed further here, save to note that the Vinogradov mean value theorem (Theorem 13 from Notes 5) and its variants are particularly useful for getting good bounds on ; see for instance the ICM article of Wooley for recent progress on these problems. Similarly, the partition function problem was the original motivation of Hardy and Littlewood in introducing the circle method, but we will not discuss it further here; see e.g. Chapter 20 of Iwaniec-Kowalski for a treatment.
Instead, we will focus our attention on the odd Goldbach conjecture as our model problem. (The even Goldbach conjecture, which involves only two variables instead of three, is unfortunately not amenable to a circle method approach for a variety of reasons, unless the statement is replaced with something weaker, such as an averaged statement; see this previous blog post for further discussion. On the other hand, the methods here can obtain weaker versions of the even Goldbach conjecture, such as showing that “almost all” even numbers are the sum of two primes; see Exercise 34 below.) In particular, we will establish the following celebrated theorem of Vinogradov:
Recently, the restriction that be sufficiently large was replaced by Helfgott with , thus establishing the odd Goldbach conjecture in full. This argument followed the same basic approach as Vinogradov (based on the circle method), but with various estimates replaced by “log-free” versions (analogous to the log-free zero-density theorems in Notes 7), combined with careful numerical optimisation of constants and also some numerical work on the even Goldbach problem and on the generalised Riemann hypothesis. We refer the reader to Helfgott’s text for details.
We will in fact show the more precise statement:
The implied constants are ineffective.
We dropped the hypothesis that is odd in Theorem 2, but note that vanishes when is even. For odd , we have
Unfortunately, due to the ineffectivity of the constants in Theorem 2 (a consequence of the reliance on the Siegel-Walfisz theorem in the proof of that theorem), one cannot quantify explicitly what “sufficiently large” means in Theorem 1 directly from Theorem 2. However, there is a modification of this theorem which gives effective bounds; see Exercise 32 below.
Exercise 4 Obtain a heuristic derivation of the main term using the modified Cramér model (Section 1 of Supplement 4).
To prove Theorem 2, we consider the more general problem of estimating sums of the form
for various integers and functions , which we will take to be finitely supported to avoid issues of convergence.
Suppose that are supported on ; for simplicity, let us first assume the pointwise bound for all . (This simple case will not cover the case in Theorem 2, when are truncated versions of the von Mangoldt function , but will serve as a warmup to that case.) Then we have the trivial upper bound
A basic observation is that this upper bound is attainable if all “pretend” to behave like the same additive character for some . For instance, if , then we have when , and then it is not difficult to show that
The key to the success of the circle method lies in the converse of the above statement: the only way that the trivial upper bound (2) comes close to being sharp is when all correlate with the same character , or in other words are simultaneously large. This converse is largely captured by the following two identities:
The traditional approach to using the circle method to compute sums such as proceeds by invoking (3) to express this sum as an integral over the unit circle, then dividing the unit circle into “major arcs” where are large but computable with high precision, and “minor arcs” where one has estimates to ensure that are small in both and senses. For functions of number-theoretic significance, such as truncated von Mangoldt functions, the “major arcs” typically consist of those that are close to a rational number with not too large, and the “minor arcs” consist of the remaining portions of the circle. One then obtains lower bounds on the contributions of the major arcs, and upper bounds on the contribution of the minor arcs, in order to get good lower bounds on .
This traditional approach is covered in many places, such as this text of Vaughan. We will emphasise in this set of notes a slightly different perspective on the circle method, coming from recent developments in additive combinatorics; this approach does not quite give the sharpest quantitative estimates, but it allows for easier generalisation to more combinatorial contexts, for instance when replacing the primes by dense subsets of the primes, or replacing the equation with some other equation or system of equations.
From Exercise 5 and Hölder’s inequality, we immediately obtain
Similarly for permutations of the .
In the case when are supported on and bounded by , this corollary tells us that we have is whenever one has uniformly in , and similarly for permutations of . From this and the triangle inequality, we obtain the following conclusion: if is supported on and bounded by , and is Fourier-approximated by another function supported on and bounded by in the sense that
Thus, one possible strategy for estimating the sum is, one can effectively replace (or “model”) by a simpler function which Fourier-approximates in the sense that the exponential sums agree up to error . For instance:
Exercise 7 Let be a natural number, and let be a random subset of , chosen so that each has an independent probability of of lying in .
- (i) If and , show that with probability as , one has uniformly in . (Hint: for any fixed , this can be accomplished with quite a good probability (e.g. ) using a concentration of measure inequality, such as Hoeffding’s inequality. To obtain the uniformity in , round to the nearest multiple of (say) and apply the union bound).
- (ii) Show that with probability , one has representations of the form with (with treated as an ordered triple, rather than an unordered one).
In the case when is something like the truncated von Mangoldt function , the quantity is of size rather than . This costs us a logarithmic factor in the above analysis, however we can still conclude that we have the approximation (4) whenever is another sequence with such that one has the improved Fourier approximation
uniformly in . (Later on we will obtain a “log-free” version of this implication in which one does not need to gain a factor of in the error term.)
This suggests a strategy for proving Vinogradov’s theorem: find an approximant to some suitable truncation of the von Mangoldt function (e.g. or ) which obeys the Fourier approximation property (5), and such that the expression is easily computable. It turns out that there are a number of good options for such an approximant . One of the quickest ways to obtain such an approximation (which is used in Chapter 19 of Iwaniec and Kowalski) is to start with the standard identity , that is to say
Thus, for instance, if , the approximant would be taken to be
in which case we would take
The function is somewhat similar to the continuous Selberg sieve weights studied in Notes 4, with the main difference being that we did not square the divisor sum as we will not need to take to be non-negative. As long as is not too large, one can use some sieve-like computations to compute expressions like quite accurately. The approximation (5) can be justified by using a nice estimate of Davenport that exemplifies the Mobius pseudorandomness heuristic from Supplement 4:
uniformly for all . The implied constants are ineffective.
This estimate will be proven by splitting into two cases. In the “major arc” case when is close to a rational with small (of size or so), this estimate will be a consequence of the Siegel-Walfisz theorem ( from Notes 2); it is the application of this theorem that is responsible for the ineffective constants. In the remaining “minor arc” case, one proceeds by using a combinatorial identity (such as Vaughan’s identity) to express the sum in terms of bilinear sums of the form , and use the Cauchy-Schwarz inequality and the minor arc nature of to obtain a gain in this case. This will all be done below the fold. We will also use (a rigorous version of) the approximation (6) (or (7)) to establish Vinogradov’s theorem.
for some that is not too large compared to . The methods used to establish Theorem 8 can also establish a Fourier approximation that makes (8) precise, and which can yield an alternate proof of Vinogradov’s theorem; this will be done below the fold.
Exercise 9 Show that the right-hand side of (8) can be rewritten as
Then, show the inequalities
and conclude that
(Hint: for the latter estimate, use Theorem 27 of Notes 1.)
The coefficients in the above exercise are quite similar to optimised Selberg sieve coefficients (see Section 2 of Notes 4).
Another approximation to , related to the modified Cramér random model (see Model 10 of Supplement 4) is
for as above and coprime to . These approximations (closely related to a device known as the “-trick”) are not as quantitatively accurate as the previous approximations, but can still suffice to establish Vinogradov’s theorem, and also to count many other linear patterns in the primes or subsets of the primes (particularly if one injects some additional tools from additive combinatorics, and specifically the inverse conjecture for the Gowers uniformity norms); see this paper of Ben Green and myself for more discussion (and this more recent paper of Shao for an analysis of this approach in the context of Vinogradov-type theorems). The following exercise expresses the approximation (9) in a form similar to the previous approximation (8):
Exercise 10 With as above, show that
for all natural numbers .
— 1. Exponential sums over primes: the minor arc case —
We begin by developing some simple rigorous instances of the following general heuristic principle (cf. Section 3 of Supplement 4):
Principle 11 (Equidistribution principle) An exponential sum (such as a linear sum or a bilinear sum involving a “structured” phase function should exhibit some non-trivial cancellation, unless there is an “obvious” algebraic reason why such cancellation may not occur (e.g. is approximately periodic with small period, or approximately decouples into a sum ).
There are some quite sophisticated versions of this principle in the literature, such as Ratner’s theorems on equidistribution of unipotent flows, discussed in this previous blog post. There are yet further precise instances of this principle which are conjectured to be true, but for which this remains unproven (e.g. regarding incomplete Weil sums in finite fields). Here, though, we will focus only on the simplest manifestations of this principle, in which is a linear or bilinear phase. Rigorous versions of this special case of the above principle will be very useful in estimating exponential sums such as
in “minor arc” situations in which is not too close to a rational number of small denominator. The remaining “major arc” case when is close to such a rational number has to be handled by the complementary methods of multiplicative number theory, which we turn to later in this section.
For pedagogical reasons we shall develop versions of this principle that are in contrapositive form, starting with a hypothesis that a significant bias in an exponential sum is present, and deducing algebraic structure as a consequence. This leads to estimates that are not fully optimal from a quantitative viewpoint, but I believe they give a good qualitative illustration of the phenomena being exploited here.
We begin with the simplest instance of Principle 11, namely regarding unweighted linear sums of linear phases:
- (i) If
Then , where denotes the distance from (any representative of) to the nearest integer.
- (ii) More generally, if
for some monotone function , then .
Proof: From the geometric series formula we have
and the claim (i) follows. To prove (ii), we write and observe from summation by parts that
while from monotonicity we have
and the claim then follows from (i) and the pigeonhole principle.
Now we move to bilinear sums. We first need an elementary lemma:
or else there is a natural number such that
One can obtain somewhat sharper estimates here by using the classical theory of continued fractions and Bohr sets, as in this previous blog post, but we will not need these refinements here.
Proof: We may assume that and , since we are done otherwise. Then there are at least two with , and by the pigeonhole principle we can find in with and . By the triangle inequality, we conclude that there exists at least one natural number for which
If then we are done, so suppose that . Suppose that are elements of such that and . Writing for some , we have
By hypothesis, ; note that as and we also have . This implies that and thus . We then have
We conclude that for fixed with , there are at most elements of such that . Iterating this with a greedy algorithm, we see that the number of with is at most ; since , this implies that
and the claim follows.
Now we can control bilinear sums of the form
- (i) (Type I estimate) If is real-valued and monotone and
then either , or there exists such that .
- (ii) (Type II estimate) If
then either , or there exists such that .
The hypotheses of (i) and (ii) should be compared with the trivial bounds
arising from the triangle inequality and the Cauchy-Schwarz inequality.
Proof: We begin with (i). By the triangle inequality, we have
The summand in is bounded by . We conclude that
for at least choices of (this is easiest to see by arguing by contradiction). Applying Lemma 12(ii), we conclude that
for at least choices of . Applying Lemma 13, we conclude that one of , , or there exists a natural number such that . This gives (i) except when . In this case, we return to (12), which holds for at least one natural number , and set .
Now we prove (ii). By the triangle inequality, we have
and hence by the Cauchy-Schwarz inequality
The left-hand side expands as
from the triangle inequality, the estimate and symmetry we conclude that
for at least one choice of . Fix this . Since , we thus have
for choices of . Applying Lemma 12(i), we conclude that
for choices of . Applying Lemma 13, we obtain the claim.
The following exercise demonstrates the sharpness of the above theorem, at least with regards to the bound on .
Exercise 15 Let be a rational number with , let , and let be multiples of .
- (i) If for a sufficiently small absolute constant , show that .
- (ii) If is even, and for a sufficiently small absolute constant , show that .
- (i) Suppose that for some interval of length at most . Show that there exists a natural number such that . (Hint: induct on and use the van der Corput inequality (Proposition 7 of Notes 5).
- (ii) Suppose that for some interval contained in . Show that there exists a natural number such that for all (note this claim is trivial for ). (Hint: use downwards induction on , adjusting as one goes along, and split up into somewhat short arithmetic progressions of various spacings in order to turn the top degree components of into essentially constant phases.)
- (iii) Use these bounds to give an alternate proof of Exercise 8 of Notes 5.
Exercise 17 (Quantitative multidimensional Weyl exponential sum estimates) Let be a polynomial in variables with coefficients for some . Let and . Suppose that
Show that either one has for some , or else there exists a natural number such that for all . (Note: this is a rather tricky exercise, and is only recommended for students who have mastered the arguments needed to solve the one-dimensional version of this exercise from Exercise 16. A solution is given in this blog post.)
Recall that in the proof of the Bombieri-Vinogradov theorem (see Notes 3), sums such as or were handled by using combinatorial identities such as Vaughan’s identity to split or into combinations of Type I or Type II convolutions. The same strategy can be applied here:
Then either , or there exists a natural number such that .
The exponent in the bound can be made explicit (and fairly small) if desired, but this exponent is not of critical importance in applications. The losses of in this proposition are undesirable (though affordable, for the purposes of proving results such as Vinogradov’s theorem); these losses have been reduced over the years, and finally eliminated entirely in the recent work of Helfgott.
Proof: We will prove this under the hypothesis (13); the argument for (14) is similar and is left as an exercise. By removing the portion of in , and shrinking slightly, we may assume without loss of generality that .
We recall the Vaughan identity
valid for any ; see Lemma 18 of Notes 3. We select . By the triangle inequality, one of the assertions
where are restrictions of , to dyadic intervals , respectively. Note that the location of then forces , and the support of forces , so that . Applying Theorem 14(i), we conclude that either (and hence ), or else there is such that , and we are done.
Similarly, if (17) holds, we again apply dyadic decomposition to arrive at (19), where are now restrictions of and to and . As before, we have , and now and so . Note from the identity that is bounded pointwise by . Repeating the previous argument then gives one of the required conclusions.
Finally, we consider the “Type II” scenario in which (18) holds. We again dyadically decompose and arrive at (19), where and are now the restrictions of and (say) to and , so that , , and . As before we can bound pointwise by . Applying Theorem 14(ii), we conclude that either , or else there exists such that , and we again obtain one of the desired conclusions.
— 2. Exponential sums over primes: the major arc case —
Proposition 18 provides guarantees that exponential sums such as are much smaller than , unless is itself small, or if is close to a rational number of small denominator. We now analyse this latter case. In contrast with the minor arc analysis, the implied constants will usually be ineffective.
The situation is simplest in the case of the Möbius function:
The implied constants are ineffective.
Proof: By splitting into residue classes modulo , it suffices to show that
for all . Writing , and removing a factor of , it suffices to show that
where is the representative of that is closest to the origin, so that .
and so by the triangle inequality it suffices to show that
for all . But this follows from the Siegel-Walfisz theorem for the Möbius function (Exercise 66 of Notes 2).
Arguing as in the proof of Lemma 12(ii), we also obtain the corollary
for any monotone function , with ineffective constants.
Now we turn to the analogous situation for the von Mangoldt function . Here we expect to have a non-trivial main term in the major arc case: for instance, the prime number theorem tells us that should be approximately the length of when . There are several ways to describe the behaviour of . One way is to use the approximation
discussed in the introduction:
for all . The implied constants are ineffective.
Proof: As discussed in the introduction, we have
so the left-hand side of (22) can be rearranged as
since , we have , and the claim now follows from summing in (and increasing appropriately).
Exercise 23 Show that Proposition 22 continues to hold if is replaced by the function
or more generally by
where is a bounded function such that for and for . (Hint: use a suitable linear combination of the identities and .)
Alternatively, we can try to replicate the proof of Proposition 21 directly, keeping track of the main terms that are now present in the Siegel-Walfisz theorem. This gives a quite explicit approximation for in major arc cases:
The implied constants are ineffective.
Proof: We may assume that and , as the claim follows from the triangle inequality and the prime number theorem otherwise. For similar reasons we can also assume that is sufficiently large depending on .
As in the proof of Proposition 24, we decompose into residue classes mod to write
If is not coprime to , then one easily verifies that
and the contribution of these cases is thus acceptable. Thus, up to negligible errors, we may restrict to be coprime to . Writing , we thus may replace by
Applying (20), we can write
Applying the Siegel-Walfisz theorem (Exercise 64 of Notes 2), we can replace here by , up to an acceptable error. Applying (20) again, we have now replaced by
which we can rewrite as
From Möbius inversion one has
so we can rewrite the previous expression as
For with , we see from the hypotheses that , and so by Lemma 12(i). The contribution of all is then , which is acceptable since . So, up to acceptable errors, we may replace by . We can write , and the claim now follows from Exercise 11 of Notes 1 and a change of variables.
Exercise 25 Assuming the generalised Riemann hypothesis, obtain the significantly stronger estimate
of Proposition 24, with the implied constants now effective and with the Gauss sum defined in equation (11) of Supplement 2. If there is no such primitive Dirichlet character, show that the above estimate continues to hold with the exceptional term deleted.
Informally, the above exercise suggests that one should add an additional correction term to the model for when there is an exceptional zero.
We can now formalise the approximation (8):
Show that for any interval , we have
for all , with ineffective constants.
Exercise 28 Let , and let be such that . Write .
- (i) Show that
for all and , with an ineffective constant.
- (ii) Suppose now that and . Let be coprime to , and let . Show that
for all and .
Proposition 24 suggests that the exponential sum should be of size about when is close to and is fairly small, and is large. However, the arguments in Proposition 18 only give an upper bound of instead (ignoring logarithmic factors). There is a good reason for this discrepancy, though. The proof of Proposition 24 relied on the Siegel-Walfisz theorem, which in turn relied on Siegel’s theorem. As discussed in Notes 2, the bounds arising from this theorem are ineffective – we do not have any control on how the implied constant in the estimate in Proposition 24 depends on . In contrast, the upper bounds in Proposition 18 are completely effective. Furthermore, these bounds are close to sharp in the hypothetical scenario of a Landau-Siegel zero:
Exercise 29 Let be a sufficiently small (effective) absolute constant. Suppose there is a non-principal character of conductor with an exceptional zero . Let be such that and . Show that
for every .
This exercise indicates that apart from the factors of , any substantial improvements to Proposition 18 will first require some progress on the notorious Landau-Siegel zero problem. It also indicates that if a Landau-Siegel zero is present, then one way to proceed is to simply incorporate the effect of that zero into the estimates (so that the computations for major arc exponential sums would acquire an additional main term coming from the exceptional zero), and try to establish results like Vinogradov’s theorem separately in this case (similar to how things were handled for Linnik’s theorem, see Notes 7), by using something like Exercise 26 in place of Proposition 24.
— 3. Vinogradov’s theorem —
We now have a number of routes to establishing Theorem 2. Let be a large number. We wish to compute the expression
where (say) and where is a fixed smooth function supported on such that for . From Exercise 23 we have
(with ineffective constants) for any . Also, by bounding by the divisor function on we have the bounds
so from several applications of Corollary 6 (splitting as the sum of and ) we have
for any (again with ineffective constants).
Now we compute . Using (23), we may rearrange this expression as
The inner sum can be estimated by covering the parameter space by squares of sidelength (the least common multiple of ) as
where is the proportion of residue classes in the plane with . Since , the contribution of the error term is certainly acceptable, so
Thus to prove Theorem 2, it suffices to establish the asymptotic
From the Chinese remainder theorem we see that is multiplicative in the sense that when is coprime to , so to evaluate this quantity for squarefree it suffices to do so when for a single prime . This is easily done:
except when , in which case one has
for some smooth, rapidly decreasing . This lets us write the left-hand side of (24) as
where (by Exercise 30)
From Mertens’ theorem we see that
so from the rapid decrease of we may restrict to be bounded in magnitude by accepting a negligible error of . Using
for , we can write
By Taylor expansion, we have
(say) uniformly for , and so the logarithm of the product is a bounded holomorphic function in this region. From Taylor expansion we thus have
when , where is some polynomial (depending on ) with vanishing constant term. From (1) we see that
Similarly we have
for , where is another polynomial depending on with vanishing constant term. We can thus write (26) (up to errors of ) as
where is a polynomial depending on with vanishing constant term. By the rapid decrease of we may then remove the constraints on , and reduce (24) to showing that
which on expanding and Fubini’s theorem reduces to showing that
for . But from multiplying (25) by and then differentiating times at , we see that
One can of course use other approximations to to establish Vinogradov’s theorem. The following exercise gives one such route:
Exercise 31 Use Exercise 27 to obtain the asymptotic
for any with ineffective constants. Then show that
and give an alternate derivation of Theorem 2.
for any with effective constants if there is a real primitive Dirichlet character of modulus and modulus and an exceptional with for some sufficiently small and for some sufficiently large depending on , with the term being deleted if no such exceptional character exists. Use this to establish Theorem 1 with an effective bound on how sufficiently large has to be.
Exercise 33 Let . Show that
for any , where
Conclude that the number of length three arithmetic progressions contained in the primes up to is for any . (This result is due to van der Corput.)
Exercise 34 (Even Goldbach conjecture for most ) Let , and let be as in (23).
- (i) Show that for any and any function bounded in magnitude by .
- (ii) For any , show that
for any , where
- (iii) Show that for any , one has
for all but at most of the numbers .
- (iv) Show that all but at most of the even numbers in are expressible as the sum of two primes.