Planet Musings

Suppose one is given a -tuple of distinct integers for some , arranged in increasing order. When is it possible to find infinitely many translates of which consists entirely of primes? The case is just Euclid’s theorem on the infinitude of primes, but the case is already open in general, with the case being the notorious twin prime conjecture.

On the other hand, there are some tuples for which one can easily answer the above question in the negative. For instance, the only translate of that consists entirely of primes is , basically because each translate of must contain an even number, and the only even prime is . More generally, if there is a prime such that meets each of the residue classes , then every translate of contains at least one multiple of ; since is the only multiple of that is prime, this shows that there are only finitely many translates of that consist entirely of primes.

To avoid this obstruction, let us call a -tuple admissible if it avoids at least one residue class for each prime . It is easy to check for admissibility in practice, since a -tuple is automatically admissible in every prime larger than , so one only needs to check a finite number of primes in order to decide on the admissibility of a given tuple. For instance, or are admissible, but is not (because it covers all the residue classes modulo ). We then have the famous Hardy-Littlewood prime tuples conjecture:

Conjecture 1 (Prime tuples conjecture, qualitative form) If is an admissible -tuple, then there exists infinitely many translates of that consist entirely of primes.

This conjecture is extremely difficult (containing the twin prime conjecture, for instance, as a special case), and in fact there is no explicitly known example of an admissible -tuple with for which we can verify this conjecture (although, thanks to the recent work of Zhang, we know that satisfies the conclusion of the prime tuples conjecture for some , even if we can’t yet say what the precise value of is).

Actually, Hardy and Littlewood conjectured a more precise version of Conjecture 1. Given an admissible -tuple , and for each prime , let denote the number of residue classes modulo that meets; thus we have for all by admissibility, and also for all . We then define the singular series associated to by the formula

where is the set of primes; by the previous discussion we see that the infinite product in converges to a finite non-zero number.

We will also need some asymptotic notation (in the spirit of “cheap nonstandard analysis“). We will need a parameter that one should think of going to infinity. Some mathematical objects (such as and ) will be independent of and referred to as fixed; but unless otherwise specified we allow all mathematical objects under consideration to depend on . If and are two such quantities, we say that if one has for some fixed , and if one has for some function of (and of any fixed parameters present) that goes to zero as (for each choice of fixed parameters).

Conjecture 2 (Prime tuples conjecture, quantitative form) Let be a fixed natural number, and let be a fixed admissible -tuple. Then the number of natural numbers such that consists entirely of primes is .

Thus, for instance, if Conjecture 2 holds, then the number of twin primes less than should equal , where is the twin prime constant

As this conjecture is stronger than Conjecture 1, it is of course open. However there are a number of partial results on this conjecture. For instance, this conjecture is known to be true if one introduces some additional averaging in ; see for instance this previous post. From the methods of sieve theory, one can obtain an upper bound of for the number of with all prime, where depends only on . Sieve theory can also give analogues of Conjecture 2 if the primes are replaced by a suitable notion of almost prime (or more precisely, by a weight function concentrated on almost primes).

Another type of partial result towards Conjectures 1, 2 come from the results of Goldston-Pintz-Yildirim, Motohashi-Pintz, and of Zhang. Following the notation of this recent paper of Pintz, for each , let denote the following assertion (DHL stands for “Dickson-Hardy-Littlewood”):

Conjecture 3 () Let be a fixed admissible -tuple. Then there are infinitely many translates of which contain at least two primes.

This conjecture gets harder as gets smaller. Note for instance that would imply all the cases of Conjecture 1, including the twin prime conjecture. More generally, if one knew for some , then one would immediately conclude that there are an infinite number of pairs of consecutive primes of separation at most , where is the minimal diameter amongst all admissible -tuples . Values of for small can be found at this link (with denoted in that page). For large , the best upper bounds on have been found by using admissible -tuples of the form

where denotes the prime and is a parameter to be optimised over (in practice it is an order of magnitude or two smaller than ); see this blog post for details. The upshot is that one can bound for large by a quantity slightly smaller than (and the large sieve inequality shows that this is sharp up to a factor of two, see e.g. this previous post for more discussion).

In a key breakthrough, Goldston, Pintz, and Yildirim were able to establish the following conditional result a few years ago:

Theorem 4 (Goldston-Pintz-Yildirim) Suppose that the Elliott-Halberstam conjecture is true for some . Then is true for some finite . In particular, this establishes an infinite number of pairs of consecutive primes of separation .

The dependence of constants between and given by the Goldston-Pintz-Yildirim argument is basically of the form . (UPDATE: as recently observed by Farkas, Pintz, and Revesz, this relationship can be improved to .)

Unfortunately, the Elliott-Halberstam conjecture (which we will state properly below) is only known for , an important result known as the Bombieri-Vinogradov theorem. If one uses the Bombieri-Vinogradov theorem instead of the Elliott-Halberstam conjecture, Goldston, Pintz, and Yildirim were still able to show the highly non-trivial result that there were infinitely many pairs of consecutive primes with (actually they showed more than this; see e.g. this survey of Soundararajan for details).

Actually, the full strength of the Elliott-Halberstam conjecture is not needed for these results. There is a technical specialisation of the Elliott-Halberstam conjecture which does not presently have a commonly accepted name; I will call it the Motohashi-Pintz-Zhang conjecture in this post, where is a parameter. We will define this conjecture more precisely later, but let us remark for now that is a consequence of .

We then have the following two theorems. Firstly, we have the following strengthening of Theorem 4:

Theorem 5 (Motohashi-Pintz-Zhang) Suppose that is true for some . Then is true for some .

A version of this result (with a slightly different formulation of ) appears in this paper of Motohashi and Pintz, and in the paper of Zhang, Theorem 5 is proven for the concrete values and . We will supply a self-contained proof of Theorem 5 below the fold, the constants upon those in Zhang’s paper (in particular, for , we can take as low as , with further improvements on the way). As with Theorem 4, we have an inverse quadratic relationship .

In his paper, Zhang obtained for the first time an unconditional advance on :

Theorem 6 (Zhang) is true for all .

This is a deep result, building upon the work of Fouvry-Iwaniec, Friedlander-Iwaniec and Bombieri-Friedlander-Iwaniec which established results of a similar nature to but simpler in some key respects. We will not discuss this result further here, except to say that they rely on the (higher-dimensional case of the) Weil conjectures, which were famously proven by Deligne using methods from l-adic cohomology. Also, it was believed among at least some experts that the methods of Bombieri, Fouvry, Friedlander, and Iwaniec were not quite strong enough to obtain results of the form , making Theorem 6 a particularly impressive achievement.

Combining Theorem 6 with Theorem 5 we obtain for some finite ; Zhang obtains this for but as detailed below, this can be lowered to . This in turn gives infinitely many pairs of consecutive primes of separation at most . Zhang gives a simple argument that bounds by , giving his famous result that there are infinitely many pairs of primes of separation at most ; by being a bit more careful (as discussed in this post) one can lower the upper bound on to , and if one instead uses the newer value for one can instead use the bound . (Many thanks to Scott Morrison for these numerics.) UPDATE: These values are now obsolete; see this web page for the latest bounds.

In this post we would like to give a self-contained proof of both Theorem 4 and Theorem 5, which are both sieve-theoretic results that are mainly elementary in nature. (But, as stated earlier, we will not discuss the deepest new result in Zhang’s paper, namely Theorem 6.) Our presentation will deviate a little bit from the traditional sieve-theoretic approach in a few places. Firstly, there is a portion of the argument that is traditionally handled using contour integration and properties of the Riemann zeta function; we will present a “cheaper” approach (which Ben Green and I used in our papers, e.g. in this one) using Fourier analysis, with the only property used about the zeta function being the elementary fact that blows up like as one approaches from the right. To deal with the contribution of small primes (which is the source of the singular series ), it will be convenient to use the “-trick” (introduced in this paper of mine with Ben), passing to a single residue class mod (where is the product of all the small primes) to end up in a situation in which all small primes have been “turned off” which leads to better pseudorandomness properties (for instance, once one eliminates all multiples of small primes, almost all pairs of remaining numbers will be coprime).

— 1. The -trick —

In this section we introduce the “-trick”, which is a simple but useful device that automatically takes care of local factors arising from small primes, such as the singular series . The price one pays for this trick is that the explicit decay rates in various terms can be rather poor, but for the applications here, we will not need to know any information on these decay rates and so the -trick may be freely applied.

Let be a natural number, which should be thought of as either fixed and large, or as a very slowly growing function of . Actually, the two viewpoints are basically equivalent for the purposes of asymptotic analysis (at least at the qualitative level of decay rates), thanks to the following basic principle:

Lemma 7 (Overspill principle) Let be a quantity depending on and . Then the following are equivalent:

• (i) For every fixed there exists a fixed such that

  

  for all fixed .

• (ii) We have

  

  whenever is a function of going to infinity that is sufficiently slowly growing. (In other words, there exists a function going to infinity with the property that whenever is a natural number-valued function of is such that as and for all sufficiently large .)

This principle is closely related to the overspill principle from nonstandard analysis, though we will not explicitly adopt a nonstandard perspective here. It is also similar in spirit to the diagonalisation trick used to prove the Arzela-Ascoli theorem.

Proof: We first show that (i) implies (ii). By (i), we see that for every natural number , we can find a real number with the property that

whenever , , and are such that . By increasing the as necessary we may assume that they are increasing and go to infinity as . If we then define to equal the largest natural number for which , or equal to if no such number exists, then one easily veifies that whenever goes to infinity and is bounded by for sufficiently large .

Now we show that (ii) implies (i). Suppose for contradiction that (i) failed, then we can find a fixed with the property that for any natural number , there exist such that for arbitrarily large . We can select the to be increasing to infinity, and then we can find a sequence increasing to infinity such that for all ; by increasing as necessary, we can also ensure that for all and . If we then define to be when , and for , we see that whenever , contradicting (ii).

Henceforth we will usually think of as a sufficiently slowly growing function of , although we will on occasion take advantage of Lemma 7 to switch to thinking of as a large fixed quantity instead. In either case, we should think of as exceeding the size of fixed quantities such as or , at least in the limit where is large; in particular, for a fixed -tuple , we will have

if is large enough. A particular consequence of the growing nature of is that

as this follows from the absolutely convergent nature of the sum and hence also . As a consequence of this, once we “turn off” all the primes less than , any errors in our sieve-theoretic analysis which are quadratic or higher in can be essentially ignored, which will be very convenient for us. In a similar vein, for any fixed -tuple , one has

which allows one to truncate the singular series:

In order to “turn off” all the small primes, we introduce the quantity , defined as the product of all the primes up to (i.e. the primorial of ):

As is going to infinity, is going to infinity also (but as slowly as we please). The idea of the -trick is to search for prime patterns in a single residue class , which as mentioned earlier will “turn off” all the primes less than in the sieve-theoretic analysis.

Using (4) and the Chinese remainder theorem, we may thus approximate the singular series as

where is the Euler totient function of , and is the set of residue classes such that all of the shifts are coprime to . Note that if consists purely of primes and is sufficiently large, then must lie in one of the residue classes in . Thus we can count tuples with all prime by working in each residue class in separately. We conclude that Conjecture 2 is equivalent to the following “-tricked version” in which the singular series is no longer present (or, more precisely, has been replaced by some natural normalisation factors depending on , such as ):

Conjecture 8 (Prime tuples conjecture, W-tricked quantitative form) Let be a fixed natural number, and let be a fixed admissible -tuple. Assume is a sufficiently slowly growing function of . Then for any residue class in , the number of natural numbers with such that consists entirely of primes is .

where is a multiplicative function, the sieve level (also denoted in some literature) is a fixed power of (such as or ), is the Möbius function, is a fixed smooth compactly supported function, is a (possibly half-infinite) interval in , and is the set of square-free numbers that are products of distinct primes in . (Actually, in applications won’t quite be smooth, but instead have some high order of differentiability (e.g. times continuously differentiable for some ), but we can extend the analysis of smooth to sufficiently differentiable by various standard limiting or approximation arguments which we will not dwell on here.) We will also need to control the more complicated variant

where are also smooth compactly supported functions. In practice, the interval will be something like , , . In particular, thanks to the -trick we will be able to turn off all the primes up to , so that only contains primes larger than , allowing us to take advantage of bounds such as (2).

Once is restricted to , the quantity is determined entirely by the values of the multiplicative function at primes in :

In applications, will have the size bound

for all and some fixed positive (note that we allow the implied constants in the notation to depend on quantities such as ); we refer to as the dimension of the multiplicative function . Henceforth we assume that has a fixed dimension . We remark that we could unify the treatment of and in what follows by allowing multiplicative functions of negative dimension, but we will avoid doing so here. In our applications will be an integer; one could also generalise much of the discussion below to the fractional dimension case, but we will not need to do so here.

Traditionally the above expressions are handled by complex analysis, starting with Perron’s formula. We will instead take a slightly different Fourier-analytic approach. We perform a Fourier expansion of the smooth compactly supported function to obtain a representation

for some Schwartz function ; in particular, is rapidly decreasing. (Strictly speaking, is the Fourier transform of shifted in the complex domain by , rather than the true Fourier transform of , but we will ignore this distinction for the purposes of this discussion.) In particular we have

Proof: We begin with the bounds on . From (6) we have

for (which forces , so there is no issue with the singularity of the logarithm) and thus

Since

we see on taking logarithms that

and thus

The bounds on then follow from the rapid decrease of . The bounds for and are proven similarly.

From (6) and the restriction of to quantities larger than , we see that

and

and

where is the restricted Euler product

which is well-defined for at least (and this is the only region of for which we will need ).

We now specialise to the model case , in which case

where is the Riemann zeta function. Using the basic (and easily proven) asymptotic for near

for , if is sufficiently slowly growing (this can be seen by first working with a fixed large and then using Lemma 7). Note that because of the above truncation, we do not need any deeper bounds on than what one can obtain from the simple pole at ; in particular no zero-free regions near the line are needed here. (This is ultimately because of the smooth nature of , which is sufficient for the applications in this post; if one wanted rougher cutoff functions here then the situation is closer to that of the prime number theorem, and non-trivial zero-free regions would be required.)

We conclude in the case that

and

and

using the rapid decrease of , we thus have

and

and

We can rewrite these expressions in terms of instead of . Using the Gamma function identity

and (7) we see that

whilst from differentiating (7) times at the origin (after first dividing by ) we see that

Combining these two methods, we also see that

We have thus obtained the following asymptotics:

Proposition 10 (Asymptotics without prime truncation) Suppose that , and that has dimension for some fixed natural number . Then we have

and

and

These asymptotics will suffice for the treatment of the Goldston-Pintz-Yildirim theorem (Theorem 4). For the Motohashi-Pintz-Zhang theorem (Theorem 5) we will also need to deal with truncated intervals , such as ; we will discuss how to deal with these truncations later.

— 3. The Goldston-Yildirim-Pintz theorem —

We are now ready to state and prove the Goldston-Yildirim-Pintz theorem. We first need to state the Elliott-Halberstam conjecture properly.

Let be the von Mangoldt function, thus equals when is equal to a prime or a power of that prime, and equal to zero otherwise. The prime number theorem in arithmetic progressions tells us that

for any fixed arithmetic progression with coprime to . In particular,

where are the residue classes mod that are coprime to . By invoking the Siegel-Walfisz theorem one can obtain the improvement

for any fixed (though, annoyingly, the implied constant here is only ineffectively bounded with current methods; see this previous post for further discussion).

The above error term is only useful when is fixed (or is of logarithmic size in ). For larger values of , it is very difficult to get good error terms for each separately, unless one assumes powerful hypotheses such as the generalised Riemann hypothesis. However, it is possible to obtain good control on the error term if one averages in . More precisely, for any , let denote the following assertion:

Conjecture 11 () One has

for all fixed .

This should be compared with the asymptotic for some absolute constant , as can be deduced for instance from Proposition 10. The Elliott-Halberstam conjecture is the assertion that holds for all . This remains open, but the important Bombieri-Vinogradov theorem establishes for all . Remarkably, the threshold is also the limit of what one can establish if one directly invokes the generalised Riemann hypothesis, so the Bombieri-Vinogradov theorem is often referred to as an assertion that the generalised Riemann hypothesis (or at least the Siegel-Walfisz theorem) holds “on the average”, which is often good enough for sieve-theoretic purposes.

We may replace the von Mangoldt function with the slight variant , defined to equal when is a prime and zero otherwise. Using this replacement, as well as the prime number theorem (with error term), it is not difficult to show that is equivalent to the estimate

Now we establish Theorem 4. Suppose that holds for some fixed , let be sufficiently large depending on but otherwise fixed, and let be a fixed admissible -tuple. We would like to show that there are infinitely many such that contains at least two primes. We will begin with the -trick, restricting to a residue class with (note that is non-empty because is admissible).

The general strategy will be as follows. We will introduce a weight function that obeys the upper bound

and lower bound

for all and some fixed , where is a fixed power of (we will eventually take ). (The factors of , , and on the right-hand side are natural normalisations coming from sieve theory and the reader should not pay too much attention to them.) Informally, (9) says that has some normalised density at most , and then (10) roughly speaking asserts that relative to the weight , has a probability of at least of being prime. If we sum (10) for all and then subtract off copies of (9), we conclude that

In particular, if we have the crucial inequality

we conclude that

It thus suffices to find a weight function obeying the required properties (9), (10) with parameters obeying the key inequality (11). It is thus of interest to make as large a power of as possible, and to minimise the ratio between and . It is in the former task that the Elliott-Halberstam hypothesis will be crucial.

The key is to find a good choice of , and the selection of this weight is arguably the main contribution of Goldston, Pintz, and Yildirim, who use a carefully modified version of the Selberg sieve. Following (a slight modification of) the Goldston-Pintz-Yildirim argument, we will take a weight of the form , where

where is a smooth non-negative function supported on to be chosen later, , and is the polynomial

Clearly is non-negative. Now we consider the task of estimating the left-hand side of (9). Expanding out using (12) and interchanging summations, we can expand this expression as

The constraint is equivalent to requiring that for each prime dividing , lies in one of the residue classes for . By choice of , , so all the are distinct, and so we are constraining to lie in one of residue classes modulo for each ; together with the constraint and the Chinese remainder theorem, we are thus constraining to residue classes modulo , where is the number of prime factors of . We thus have

Note from the support of that may be constrained to be at most , so that is at most . We can thus express the left-hand side of (9) as the main term

plus an error

By Proposition 10, the error term is . So if we set

then the error term will certainly give a negligible contribution to (9) with plenty of room to spare. (But when we come to the more difficult sum (10), we will have much less room – only a superlogarithmic amount of room, in fact.) To show (9), it thus suffices to show that

But by Proposition 10 (applied to the -dimensional multiplicative function ) and the support of , this bound holds with equal to the quantity

Now we turn to (10). Fix . Repeating the arguments for (9), we may expand the left-hand side of (9) as

Now we consider the inner sum

As discussed earlier, the conditions and split into residue classes . However, if for one of the primes dividing , then must vanish (since is much less than ). So there are actually only residue classes for which is coprime to . We thus have

where denotes the quantity

Remark 1 There is an inefficiency here; the supremum in (13) is over all primitive residue classes , but actually one only needs to take the supremum over the residue classes for which , where . This inefficiency is not exploitable if we insist on using the Elliott-Halberstam conjecture as the starting hypothesis, but will be used in the arguments of the next section in which a more lightweight hypothesis is utilised.

The left-hand side of (10) is thus equal to the main term

plus an error term

We first deal with the error term. Since is in and is bounded by on the support of this function, and each has representations of the form , we can bound this expression by

On the other hand, from Proposition 10 and the trivial bound we have

while from (8) (and here we crucially use the choice of ) one easily verifies that

for any fixed . By the Cauchy-Schwarz inequality we see that the error term to (10) is negligible (assuming sufficiently slowly growing of course). Meanwhile, the main term can be rewritten as

where is the -dimensional multiplicative function

Applying Proposition 10, we obtain (10) with

To obtain the crucial inequality (11), we thus need to locate a smooth non-negative function supported on obeying the inequality

In principle one can use calculus of variations to optimise the choice of here (it will be the ground state of a certain one-dimensional Schrödinger operator), but one can already get a fairly good result here by a specific choice of that is amenable for computations, namely a polynomial of the form for and some integer , with vanishing for and smoothly truncated to somehow at negative values of . Strictly speaking, this is not admissible here because it is not infinitely smooth at , being only times continuously differentiable instead, but one can regularise this function to be smooth without significantly affecting either side of (14), so we will go ahead and test (14) with this function and leave the regularisation details to the reader. The inequality then becomes (after cancelling some factors)

Using the Beta function identity

we have

and

and the preceding equation now becomes

Actually, the same inequality is also applicable when is real instead of integer, using Gamma functions in place of factorials; we leave the details to the interested reader. We can then optimise in by setting , arriving at the inequality

But as long as , this inequality is satisfiable for any larger than . This concludes the proof of Theorem 4.

Remark 2 One can obtain slightly better dependencies of in terms of by using more general functions for than the monomials , for instance one can take linear combinations of such functions. See the paper of Goldston, Pintz, and Yildirim for details. Unfortunately, as noted in this survey of Soundararajan, one has the general inequality

which defeats any attempt to directly use this method using only the Bombieri-Vinogradov result that holds for all . We show (17) in the case when is large. Write , then (17) simplifies to

The right-hand side simplifies after some integration by parts to

Subtracting off from both sides, one is left with

From the fundamental theorem of calculus and Cauchy-Schwarz, one has the bound

Using this bound for close to and dominating by for far from , we obtain the claim (at least if is large enough). There is some slack in this argument; it would be of interest to calculate exactly what the best constants are in (17), so that one can obtain the optimal relationship between and .

To get around this obstruction (17) in the uncondiional setting when one only has for , Goldston, Pintz, and Yildirim also considered sums of the form in which was now outside (but close to) . While the bounds here were significantly inferior to those in (10), they were still sufficient to prove a variant of the inequality (11) to get reasonably small gaps between primes.

— 4. The Motohashi-Pintz-Zhang theorem —

We now modify the above argument to give Theorem 5. Our treatment here is different from that of Zhang in that it employs the method of Buchstab iteration; a related argument also appears in the paper of Motohashi and Pintz. This arrangement of the argument leads to a more efficient dependence of on than in the paper of Zhang. (The argument of Motohashi and Pintz is a bit more complicated and uses a slightly different formulation of the base conjecture , but the final bounds are similar to those given here, albeit with non-explicit constants in the notation.)

The main idea here is to truncate the interval of relevant primes from to for some small . Somewhat remarkably, it turns out that this apparently severe truncation does not affect the sums (9), (10) here as long as is large (which is going to be the case in practice, with being comparable to ). The intuition is that was already concentrated on those for which had about factors, and it is too “expensive” for one of these factors to as large as or more, as it forces many of the other factors to be smaller than they “want” to be. The advantage of truncating the set of primes this way is that the version of the Elliott-Halberstam conjecture needed also acquires the same truncation, which gives that version a certain “well-factored” form (in the spirit of the work of Bombieri, Fouvry, Friedlander, and Iwaniec) which is essential in being able to establish that conjecture unconditionally for some suitably small .

To make this more precise, we first formalise the conjecture for mentioned earlier.

Conjecture 12 () Let be a fixed -tuple (not necessarily admissible) for some fixed , and let be a primitive residue class. Then

for any fixed , where and is the quantity

and

This is the -tricked formulation of the conjecture as (implicitly) stated in Zhang’s paper, which did not have the restriction present (and with the interval enlarged from to , and was required to be admissible). However the two formulations are morally equivalent (and Zhang’s arguments establish Theorem 6 with as stated). From the prime number theorem in arithmetic progressions (with error term) together with Proposition 10 we observe that we may replace (18) here by the slight variant

It is also not difficult to deduce from after using a Cauchy-Schwarz argument to dispose of the residue classes in the above sum (cf. the treatment of the error term in (10) in the previous section); we leave the details to the interested reader. Note however that whilst demands control over all primitive residue classes in a given modulus , the conjecture only requires control of a much smaller number of residue classes (roughly polylogarithmic in number, on average). Thus is simpler than , though it is still far from trivial.

We now begin the proof of Theorem 5. Let be such that holds, and let be a sufficiently large quantity depending on but which is otherwise fixed. As before, it suffices to locate a non-negative sieve weight that obeys the estimates (9), (10) for parameters that obey the key inequality (11), and with smooth and supported on . The choice of weight is almost the same as before; it is also given as a square with given by (12), but now the interval is truncated to instead of . Also, in this argument we take

We now establish (9). By repeating the previous arguments, the left-hand side of (9) is equal to a main term

plus an error term which continues to be acceptable (indeed, the error term is slightly smaller than in the previous case due to the truncated nature of ). At this point in the previous section we applied Proposition 10, but that proposition was only available for the untruncated interval instead of the truncated interval . One could try to adapt the proof of that proposition to the truncated case, but then one is faced with the problem of controlling the truncated zeta function . While one can eventually get some reasonable asymptotics for this function, it seems to be more efficient to eschew Fourier analysis and work entirely in “physical space” by the following partial Möbius inversion argument. Write , thus . Observe that for any , the quantity equals when lies in and vanishes otherwise. Hence, for any function of and supported on squarefree numbers we have the partial Mobius inversion formula

and so the main term (20) can be expressed as

We first dispose of the contribution to (21) when share a common prime factor for some . For any fixed , we can bound this contribution by

Factorising the inner two sums as an Euler product, this becomes

[UPDATE: The above argument is not quite correct; a corrected (and improved) version is given at this newer post.] The product is by e.g. Mertens’ theorem, while . So the contribution of this case is negligible.

If do not share a common factor for any , then we can factor as . Rearranging this portion of (21) and then reinserting the case when have a common factor for some , we may write (21) up to negligible errors as

Note that we can restrict to be at most as otherwise the factors vanish. The inner sum

is now of the form that can be treated by Proposition 10, and takes the form

Here we make the technical remark that the translates of by shifts between and are uniformly controlled in smooth norms, which means that the error here is uniform in the choices of .

Let us first deal with the contribution of the error term. This is bounded by

The inner sum factorises as

which by Mertens’ theorem is (albeit with a rather large implied constant!), so this error is negligible for the purposes of (9). Indeed, (9) is now reduced to the inequality

Note that the factor increases very rapidly with when is large, which basically means that any non-trivial shift of the factors to the left by or will cause the integral in (22) to decrease dramatically. Since all the in are either equal to or bounded below by , this will cause the term to dominate in the regime when is large (or more precisely ), which is the case in applications.

At this point, in order to perform the computations cleanly, we will mimic the arguments from the previous section and take the explicit choice

for some integer and (and some smooth continuation to for negative , and so

for positive . (Again, this function is not quite smooth at , but this issue can be dealt with by an infinitesimal regularisation argument which we omit here.) The left-hand side of (22) now becomes

The integral here is a little bit more complicated than a beta integral. To estimate it, we use the beta function identity to observe that

and

and hence by Cauchy-Schwarz

This Cauchy-Schwarz step is a bit wasteful when are far apart, but this does seems to only lead to a minor loss of efficiency in the estimates. We have thus bounded the left-hand side of (22) by

It is now convenient to collapse the double summation to a single summation. We may bound

(since is less than the greater of and ) and observe that each has representations of the form , so we may now bound the left-hand side of (22) by

Note that an element of is either equal to , or lies in the interval for some natural number . In the latter case, we have

In particular, this expression vanishes if . We can thus bound the left-hand side of (22) by

If we introduce the quantity

then we have thus bounded the left-hand side of (22) by

We observe that

when , while in general we have the Buchstab identity

as can be seen by isolating the smallest prime in all the terms in (23) with . (This inequality is very close to being an identity, the only loss coming from the possibility of the prime factor being repeated in a term associated to .) We can iterate this identity to obtain the following conclusion:

Lemma 13 For any , we have

whenever and for some fixed , with the error term being uniform in the choice of .

Proof: Write . We prove the bound by strong induction on . The case follows from (24). Now suppose that and that the claim has already been proven for smaller . Let and . Note that whenever . We thus have from (25) and the induction hypothesis that

applying Mertens’ theorem (or the prime number theorem) we have

and the claim follows from the telescoping identity

Applying this inequality, we have established (22) with

where

We remark that as a first approximation we have

so in the regime , is roughly , which will be negligible for the parameter ranges of of interest. Thus the in this argument is quite close to the from (15) in practice.

Now we turn to (10). Fix . As in the previous section, we can bound the left-hand side of (10) as the sum of the main term

plus an error term

where is the quantity

is the polynomial , and was defined in (19). Using the hypothesis and Cauchy-Schwarz as in the previous section we see that the error term is negligible for the purposes of establishing (10). As for the main term, the same argument used to reduce (9) to (22) shows that (10) reduces to

Here, we can do something a bit crude; with our choice of , the integrand is non-negative, so we can simply discard all but the term and reduce to

(The intuition here is that by refusing to sieve using primes larger than , we have enlarged the sieve , which makes the upper bound (9) more difficult but the lower bound (10) actually becomes easier.) So we can take the same choice (16) of as in the previous section:

Inserting this and (26) into (11) and simplifying, we see that we can obtain once we can verify the inequality

As before, can be taken to be non-integer if desired. Setting to be slightly larger than we obtain Theorem 5.

— 5. Using optimal values of (NEW, June 5, 2013) —

We can do better than given above by using an optimal value of . The following result was obtained recently by Farkas, Pintz, and Revesz, and independently worked out by commenters on this blog:

Theorem 14 (Optimal GPY weight) Let be an integer. Then the ratio

where is a smooth function with that is not identically vanishing, has a minimal value of

where is the first zero of the Bessel function . Furthermore, this minimum is attained if (and only if) is a scalar multiple of the function

Proof: The function , by definition, obeys the Bessel differential equation

and also vanishes to order at the origin. From this and routine computations it is easy to see that is smooth, strictly positive on , and obeys the differential equation

If we write , which is well-defined away from since is non-vanishing on , then obeys the Ricatti-type equation

Now consider the quadratic form

for smooth functions with . A calculation using (29) and integration by parts shows that

and so , giving the first claim; the second claim follows by noting that vanishes if and only if is a scalar multiple of . (Note that the integration by parts is a little subtle, because vanishes to first order at and so blows up to first order; but still vanishes to first order at , allowing one to justify the integration by parts by a standard limiting argument.)

If we now test (14) with a function which is smooth, vanishes to order at , and has a derivative equal to , we see that we can deduce from whenever

Using the known asymptotic

for and large (see e.g. Abramowitz and Stegun), this is asymptotically of the form

or

thus giving a relationship of the form that is superior to the previous relationship .

A similar argument can be given for Theorem 5, using of the form above rather than a monomial (and extended by zero to ). For future optimisation we consider a generalisation of in which the interval is of the form rather than , so that is now rather than . As before, the key point is the estimation of . The arguments leading to (22) go through for any test function , so we have to show

As has derivative equal to , this is

Proof: From (28) we have

From construction we already know that is positive on . The above equation then shows that is negative at , and that cannot have any local minimum in , so is negative throughout. To obtain the final claim we use an argument provided by Gergely Harcos in the comments: from the recursive relations for Bessel functions we can check that is a positive multiple of , and the claim then follows from the interlacing properties of the zeroes of Bessel functions.

Write , so is positive and by Theorem 14 we have

If , then as is negative and increasing we have

for , and thus by change of variable

for , and thus

for all . Similarly

for all . By Cauchy-Schwarz we can thus bound the integral in (30) by

and so (30) reduces to

Repeating the arguments of the previous section, we can reduce this to

and by further continuing the arguments of the previous section we end up being able to take

where

The key inequality (11) now becomes

thus implies whenever (32) is obeyed with the value (31) of .

Ken Wilson

Ken Wilson passed away on June 15 at age 77. He changed how we think about physics.

Renormalization theory, first formulated systematically by Freeman Dyson in 1949, cured the flaws of quantum electrodynamics and turned it into a precise computational tool. But the subject seemed magical and mysterious. Many physicists, Dirac prominently among them, questioned whether renormalization rests on a sound foundation.

Wilson changed that.

The renormalization group concept arose in an extraordinary paper by Gell-Mann and Low in 1954. It was embraced by Soviet physicists like Bogoliubov and Landau, and invoked by Landau to challenge the consistency of quantum electrodynamics. But it was an abstruse and inaccessible topic, as is well illustrated by the baffling discussion at the very end of the two-volume textbook by Bjorken and Drell.

Wilson changed that, too.

Ken Wilson turned renormalization upside down. Dyson and others had worried about the “ultraviolet divergences” occurring in Feynman diagrams. They introduced an artificial cutoff on integrations over the momenta of virtual particles, then tried to show that all the dependence on the cutoff can be eliminated by expressing the results of computations in terms of experimentally accessible quantities. It required great combinatoric agility to show this trick works in electrodynamics. In other theories, notably including general relativity, it doesn’t work.

Wilson adopted an alternative viewpoint. Take the short-distance cutoff seriously, he said, regarding it as part of the physical formulation of the field theory. Now ask what physics looks like at distances much larger than the cutoff. Wilson imagined letting the short-distance cutoff grow, while simultaneously adjusting the theory to preserve its low-energy predictions. This procedure sounds complicated, but Wilson discovered something wonderful — for the purpose of computing low-energy processes the theory becomes remarkably simple, completely characterized by just a few (renormalized) parameters. One recovers Dyson’s results plus much more, while also acquiring a rich and visually arresting physical picture of what is going on.

When I started graduate school in 1975, Wilson, not yet 40, was already a legend. Even Sidney Coleman, for me the paragon of razor sharp intellect, seemed to regard Wilson with awe. (They had been contemporaries at Caltech, both students of Murray Gell-Mann.) It enhanced the legend that Wilson had been notoriously slow to publish. He spent years pondering the foundations of quantum field theory before finally unleashing a torrent of revolutionary papers in the early 70s. Cornell had the wisdom to grant tenure despite Wilson’s unusually low productivity during the 60s.

As a student, I spent countless hours struggling through Wilson’s great papers, some of which were quite difficult. One introduced me to the operator product expansion, which became a workhorse of high-energy scattering theory and the foundation of conformal field theory. Another considered all the possible ways that renormalization group fixed points could control the high-energy behavior of the strong interactions. Conspicuously missing from the discussion was what turned out to be the correct idea — asymptotic freedom. Wilson had not overlooked this possibility; instead he “proved” it to be impossible. The proof contains a subtle error. Wilson analyzed charge renormalization invoking both Lorentz covariance and positivity of the Hilbert space metric, forgetting that gauge theories admit no gauge choice with both properties. Even Ken Wilson made mistakes.

Wilson also formulated the strong-coupling expansion of lattice gauge theory, and soon after pioneered the Euclidean Monte Carlo method for computing the quantitative non-perturbative predictions of quantum chromodynamics, which remains today an extremely active and successful program. But of the papers by Wilson I read while in graduate school, the most exciting by far was this one about the renormalization group. Toward the end of the paper Wilson discussed how to formulate the notion of the “continuum limit” of a field theory with a cutoff. Removing the short-distance cutoff is equivalent to taking the limit in which the correlation length (the inverse of the renormalized mass) is infinitely long compared to the cutoff — the continuum limit is a second-order phase transition. Wilson had finally found the right answer to the decades-old question, “What is quantum field theory?” And after reading his paper, I knew the answer, too! This Wilsonian viewpoint led to further deep insights mentioned in the paper, for example that an interacting self-coupled scalar field theory is unlikely to exist (i.e. have a continuum limit) in four spacetime dimensions.

Wilson’s mastery of quantum field theory led him to another crucial insight in the 1970s which has profoundly influenced physics in the decades since — he denigrated elementary scalar fields as unnatural. I learned about this powerful idea from an inspiring 1979 paper not by Wilson, but by Lenny Susskind. That paper includes a telltale acknowledgment: “I would like to thank K. Wilson for explaining the reasons why scalar fields require unnatural adjustments of bare constants.”

Susskind, channeling Wilson, clearly explains a glaring flaw in the standard model of particle physics — ensuring that the Higgs boson mass is much lighter than the Planck (i.e., cutoff) scale requires an exquisitely careful tuning of the theory’s bare parameters. Susskind proposed to banish the Higgs boson in favor of Technicolor, a new strong interaction responsible for breaking the electroweak gauge symmetry, an idea I found compelling at the time. Technicolor fell into disfavor because it turned out to be hard to build fully realistic models, but Wilson’s complaint about elementary scalars continued to drive the quest for new physics beyond the standard model, and in particular bolstered the hope that low-energy supersymmetry (which eases the fine tuning problem) will be discovered at the Large Hadron Collider. Both dark energy (another fine tuning problem) and the absence so far of new physics beyond the HIggs boson at the LHC are prompting some soul searching about whether naturalness is really a reliable criterion for evaluating success in physical theories. Could Wilson have steered us wrong?

Wilson’s great legacy is that we now regard nearly every quantum field theory as an effective field theory. We don’t demand or expect that the theory will continue working at arbitrarily short distances. At some stage it will break down and be replaced by a more fundamental description. This viewpoint is now so deeply ingrained in how we do physics that today’s students may be surprised to hear it was not always so. More than anyone else, we have Ken Wilson to thank for this indispensable wisdom. Few ideas have changed physics so much.

This post is a continuation of the previous post on sieve theory, which is an ongoing part of the Polymath8 project. As the previous post was getting somewhat full, we are rolling the thread over to the current post.

In this post we will record a new truncation of the elementary Selberg sieve discussed in this previous post (and also analysed in the context of bounded prime gaps by Graham-Goldston-Pintz-Yildirim and Motohashi-Pintz) that was recently worked out by Janos Pintz, who has kindly given permission to share this new idea with the Polymath8 project. This new sieve decouples the parameter that was present in our previous analysis of Zhang’s argument into two parameters, a quantity that used to measure smoothness in the modulus, but now measures a weaker notion of “dense divisibility” which is what is really needed in the Elliott-Halberstam type estimates, and a second quantity which still measures smoothness but is allowed to be substantially larger than . Through this decoupling, it appears that the type losses in the sieve theoretic part of the argument can be almost completely eliminated (they basically decay exponential in and have only mild dependence on , whereas the Elliott-Halberstam analyhsis is sensitive only to , allowing one to set far smaller than previously by keeping large). This should lead to noticeable gains in the quantity in our analysis.

To describe this new truncation we need to review some notation. As in all previous posts (in particular, the first post in this series), we have an asymptotic parameter going off to infinity, and all quantities here are implicitly understood to be allowed to depend on (or to range in a set that depends on ) unless they are explicitly declared to be fixed. We use the usual asymptotic notation relative to this parameter . To be able to ignore local factors (such as the singular series ), we also use the “-trick” (as discussed in the first post in this series): we introduce a parameter that grows very slowly with , and set .

For any fixed natural number , define an admissible -tuple to be a fixed tuple of distinct integers which avoids at least one residue class modulo for each prime . Our objective is to obtain the following conjecture for as small a value of the parameter as possible:

Conjecture 1 () Let be a fixed admissible -tuple. Then there exist infinitely many translates of that contain at least two primes.

The twin prime conjecture asserts that holds for as small as , but currently we are only able to establish this result for (see this comment). However, with the new truncated sieve of Pintz described in this post, we expect to be able to lower this threshold somewhat.

In previous posts, we deduced from a technical variant of the Elliot-Halberstam conjecture for certain choices of parameters , . We will use the following formulation of :

Conjecture 2 () Let be a fixed -tuple (not necessarily admissible) for some fixed , and let be a primitive residue class. Then

for any fixed , where , are the square-free integers whose prime factors lie in , and is the quantity

and is the set of congruence classes

and is the polynomial

The conjecture is currently known to hold whenever (see this comment and this confirmation). Actually, we can prove a stronger result than in this regime in a couple ways. Firstly, the congruence classes can be replaced by a more general systetm of congruence classes obeying a certain controlled multiplicity axiom; see this post. Secondly, and more importantly for this post, the requirement that the modulus lies in can be relaxed; see below.

To connect the two conjectures, the previously best known implication was the folowing (see Theorem 2 from this post):

Theorem 3 Let , and be such that we have the inequality

where is the first positive zero of the Bessel function , and are the quantities

and

Then implies .

Actually there have been some slight improvements to the quantities ; see the comments to this previous post. However, the main error remains roughly of the order , which limits one from taking too small.

To improve beyond this, the first basic observation is that the smoothness condition , which implies that all prime divisors of are less than , can be relaxed in the proof of . Indeed, if one inspects the proof of this proposition (described in these three previous posts), one sees that the key property of needed is not so much the smoothness, but a weaker condition which we will call (for lack of a better term) dense divisibility:

Definition 4 Let . A positive integer is said to be -densely divisible if for every , one can find a factor of in the interval . We let denote the set of positive integers that are -densely divisible.

Certainly every integer which is -smooth (i.e. has all prime factors at most is also -densely divisible, as can be seen from the greedy algorithm; but the property of being -densely divisible is strictly weaker than -smoothness, which is a fact we shall exploit shortly.

We now define to be the same statement as , but with the condition replaced by the weaker condition . The arguments in previous posts then also establish whenever .

The main result of this post is then the following implication, essentially due to Pintz:

Theorem 5 Let , , , and be such that

where

and

and

Then implies .

This theorem has rather messy constants, but we can isolate some special cases which are a bit easier to compute with. Setting , we see that vanishes (and the argument below will show that we only need rather than ), and we obtain the following slight improvement of Theorem 3:

Theorem 6 Let , and be such that we have the inequality

where

Then implies .

This is a little better than Theorem 3, because the error has size about , which compares favorably with the error in Theorem 3 which is about . This should already give a “cheap” improvement to our current threshold , though it will fall short of what one would get if one fully optimised over all parameters in the above theorem.

Returning to the full strength of Theorem 5, let us obtain a crude upper bound for that is a little simpler to understand. Extending the summation to infinity and using the Taylor series for the exponential, we have

We can crudely bound

and then optimise in to obtain

Because of the factor in the integrand for and , we expect the ratio to be of the order of , although one will need some theoretical or numerical estimates on Bessel functions to make this heuristic more precise. Setting to be something like , we get a good bound here as long as , which at current values of is a mild condition.

Pintz’s argument uses the elementary Selberg sieve, discussed in this previous post, but with a more efficient estimation of the quantity , in particular avoiding the truncation to moduli between and which was the main source of inefficiency in that previous post. The basic idea is to “linearise” the effect of the truncation of the sieve, so that this contribution can be dealt with by the union bound (basically, bounding the contribution of each large prime one at a time). This mostly avoids the more complicated combinatorial analysis that arose in the analytic Selberg sieve, as seen in this previous post.

— 1. Review of previous material —

In this section we collect some results from previous posts which we will need.

We first record an asymptotic for multiplicative functions. For any natural number , define a -dimensional multiplicative function to be a multiplicative function which obeys the asymptotic

for all . The following result is Lemma 8 from this previous post:

Lemma 7 Let . Let be a fixed positive integer, and let be a multiplicative function of dimension . Then for any fixed compactly supported, Riemann-integrable function , and any for some fixed , one has

Next, we record a criterion for , which is Lemma 7 from this previous post:

Lemma 8 (Criterion for DHL) Let . Suppose that for each fixed admissible -tuple and each congruence class such that is coprime to for all , one can find a non-negative weight function , fixed quantities , a quantity , and a fixed positive power of such that one has the upper bound

the lower bound

for all , and the key inequality

holds. Then holds. Here is defined to equal when is prime and otherwise.

We can now prove Theorem 5. Fix to obey the hypotheses of this theorem. Let be a congruence class with coprime to for all (this class exists by the admissibility of ). We apply Lemma 8 with

the elementary Selberg sieve defined by

where

are the multiplicative functions

is a fixed smooth function supported on , and is a certain subset of to be chosen shortly. We will assume that non-negative and non-increasing on . In this previous post, we considered this sieve with equal to either all of , or the subset consisting of smooth numbers. For now, we will discuss the estimates as far as we can without having to explicitly specify .

We first consider the asymptotic (5). By arguing exactly as in Section 2 (or Section 3) of this previous post, we can write the left-hand side of (5), up to errors of , as

The summand here is non-negative, so we may crudely replace by all of and apply Lemma 7 to obtain (5) with

Now we turn to the more difficult asymptotic (6). The left-hand side expands as

As observed in Section 2 of this previous post, we have

where

and

Now let be a small fixed constant to be chosen later, and suppose the following claim holds:

Claim 1 (Dense divisibility of moduli) Whenever and are non-zero, then either or else .

Then from the Bombieri-Vinogradov theorem (for the moduli) or the hypothesis (for the larger moduli, noting that ) and standard arguments (cf. Proposition 5 of this post) we have

for any fixed and any multiplicative function of a fixed dimension , where ranges only over those integers of the form with non-zero. From this we easily see (arguing as in Section 2 of this previous post) that the contribution of the error term is , and we are left with establishing the lower bound

up to errors of (henceforth referred to as negligible errors).

As in Section 2 of the previous section, we can write the left-hand side as

where is the -dimensional multiplicative function

So we would like to select small enough that Claim (1) holds, but large enough that we can lower bound (9) by up to negligible errors.

Pintz’s idea is to choose to be the set of all elements of with the property that

Let us first verify Claim 1 with this definition. Suppose that is non-zero, then from (8) and the support of there is a multiple of with (in particular ) and . The latter condition implies that either or that , and . In the latter case we see from (10) (applied to ) that

The latter conclusion implies that is -densely divisible. Indeed, for any we multiply together all the prime divisors of between and one at a time until just before one reaches or exceeds . This must place one at least as large as . Next, one multiplies to this the prime divisors of less than until one reaches or exceeds ; this is possible thanks to (11), and gives a divisor between and as required.

Now we need to obtain a lower bound for (9). If we write

and

(the minus sign being to compensate for the non-positive nature of ) then we have

and thus

Note that this inequality replaces the quadratic expression with a linear expression in the truncation error , which will be more tractable for computing the effect of that error. We may thus lower bound (9) by the difference of

and

In Section 2 of this post it is shown that

which implies that (12) is equal to

up to negligible errors. Similar considerations show that (13) is equal to

up to negligible errors. To upper bound (14), we need to upper bound

For this we need to catalog the ways in which can fail to be in . In order for this to occur, at least one of the following three statements must hold:

• (i) could be divisible by a prime with .
• (ii) could be divisible by a prime with .
• (iii) lies in , but .

We consider the contributions of (i), (ii), (iii) to (14). We begin with the contribution of (i). This is bounded above by

Applying Lemma 7, one can simplify this modulo negligible errors as

which by another application of Lemma 7 is equal to

where we adopt the notation

Applying Mertens’ theorem and summation by parts, this expression is equal up to negligible errors to

where

Now we turn to the contribution of (ii) to (14). This is bounded above by

By Lemma 7 we have

and so we may bound this contribution up to negligible errors by

which by Lemma 7 again is equal (up to negligible errors) to

By definition, . By Mertens’ theorem, we can thus write the above expression up to negligible errors as

Finally, we turn to the contribution of case (iii) to (14). By Proposition 7 we have

so we may bound this contribution up to negligible errors by

where is as in case (iii).

We introduce the quantities

and

so that case (iii) consists of those in such that

From the support of we may also take . This implies that we may factor

for some primes

and some coprime to , with

The contribution of this case may thus be bounded by

Evaluating the inner sum using Lemma 7, we obtain (up to negligible errors)

where is a truncation of :

Again we have . By Mertens’ theorem we may write this (up to negligible errors) as

Putting all this together, we have obtained the lower bound (6) with

where

and

We now place upper bounds on . In this previous post, the bounds

and

for are proven. Thus we have

These are already quite small for , say, which would correspond to .

For we will use the crude estimate

this may surely be improved, but we will not do so here to simplify the exposition. Then we may bound

The point here is that the first term is exponentially decaying in , which can compensate for the second term if which is currently the case in the regime of interest.

One can do a bit better than this. For any parameter , one has

since the left-hand side vanishes for . This gives the bound

If we insert these bounds into (7), send to zero, and optimise in using Theorem 14 from this previous post, we obtain Theorem 5.

Filed under: math.NT, polymath Tagged: Janos Pintz, polymath8, Selberg sieve

I’m trying to finish off a paper that Tobias Fritz and I have been working on, which gives a category-theoretic (and Bayesian!) characterization of relative entropy. It’s a kind of sequel to our paper with Tom Leinster, in which we characterized entropy.

That earlier paper was developed in conversations here on the n-Category Café. It was a lot of fun; I sort of miss that style of working. Also, to get warmed up, I need to think through some things I’ve thought about before. So, I might as well write them down here.

There are many categories related to probability theory, and they’re related in many ways. Last summer—on the 24th of August 2012, according to my notes here—Jamie Vicary, Brendan Fong and I worked through a bunch of these relationships. I need to write them down now, even if they’re not all vitally important to my paper with Tobias. They’re sort of buzzing around my brain like flies.

(Tobias knows this stuff too, and this is how we think about probability theory, but we weren’t planning to stick it in our paper. Maybe we should.)

Let’s restrict attention to probability measures on finite sets, and related structures. We could study these questions more generally, and we should, but not today. What we’ll do is give a unified purely algebraic description of:

• finite sets
• measures on finite sets
• probability measures on finite sets
• functions
• bijections
• measure-preserving functions
• stochastic maps

Finitely generated free $[0,\mathrm{\infty })$-modules

We start with the rig of nonnegative real numbers with their usual addition and multiplication; let’s call this $[0,\mathrm{\infty })$. The idea is that measure theory, and probability theory, are closely related to linear algebra over this rig.

So, we start with the category of finitely generated free $[0,\mathrm{\infty })$-modules, and module homomorphisms. Every such module is isomorphic to $[0,\mathrm{\infty }{)}^S$ for some finite set $S$.

Puzzle. Do we need to say ‘free’ here? Are there finitely generated modules over $[0,\mathrm{\infty })$ that aren’t free?

In other words, every finitely generated free $[0,\mathrm{\infty })$-module is isomorphic to $[0,\mathrm{\infty }{)}^n$ for some $n=0,1,2,\dots$. So, the category of these is equivalent to $\mathrm{Mat}([0,\mathrm{\infty }))$, the category where objects are natural numbers, a morphism from $m$ to $n$ is an $m\times n$ matrix of numbers in $[0,\mathrm{\infty })$, and composition is done by matrix multiplication. So let’s just call this category $\mathrm{Mat}([0,\mathrm{\infty }))$, instead of something complicated like ${\mathrm{FinGenFMod}}_{[0,\mathrm{\infty })}$. I’ll call the morphisms in here maps.

We can take tensor products of finitely generated free modules, and this makes $\mathrm{Mat}([0,\mathrm{\infty }))$ into a symmetric monoidal $†$-category. This means we can draw maps using string diagrams in the usual way. However, I’m feeling lazy so I’ll often write equations when I could be drawing diagrams.

One of the rules of the game is that all these equations will make sense in any symmetric monoidal $†$-category. So we could, if we wanted, generalize ideas from probability theory this way. If you want to do this, you’ll need to know that $[0,\mathrm{\infty })$ is the unit for the tensor product in the category of finitely generated free $[0,\mathrm{\infty })$-algebras. We’ll be seeing this guy a lot. So if you want to generalize, just call it ‘the tensor unit’.

Finite sets

There’s a way to see the category of finite sets lurking in $\mathrm{Mat}([0,\mathrm{\infty }))$, which we can borrow from this paper:

• Bob Coecke, Dusko Pavlovic and Jamie Vicary, A new description of orthogonal bases.

For any finite set $S$, we get a free finitely generated $[0,\mathrm{\infty })$-module, namely $[0,\mathrm{\infty }{)}^S$. This comes with some structure:

• a multiplication $m:[0,\mathrm{\infty }{)}^S\otimes [0,\mathrm{\infty }{)}^S\to [0,\mathrm{\infty }{)}^S$, coming from pointwise multiplication of $[0,\mathrm{\infty })$-valued functions on $S$;
• the unit for this multiplication, an element of $[0,\mathrm{\infty }{)}^S$, which we can write as a morphism $i:[0,\mathrm{\infty })\to [0,\mathrm{\infty }{)}^S$;
• a comultiplication, obtained by taking the diagonal map $\Delta :S\to S\times S$ and promoting it to a linear map $\Delta :[0,\mathrm{\infty }{)}^S\to [0,\mathrm{\infty }{)}^S\otimes [0,\mathrm{\infty }{)}^S$;
• a counit for this comultiplication, obtained by taking the map to the terminal set $!:S\to 1$ and promoting it to a linear map $e:[0,\mathrm{\infty }{)}^S\to [0,\mathrm{\infty })$.

These morphisms $m,i,\Delta ,e$ make

$$x=[0,\mathrm{\infty }{)}^S$$

into a commutative Frobenius algebra in $\mathrm{Mat}([0,\mathrm{\infty }))$. That’s a thing where the unit, counit, multiplication and comultiplication obey these laws:

(I drew these back when I was feeling less lazy.) This Frobenius algebra is also ‘special’, meaning it obeys this:

And it’s also a $†$-Frobenius algebra, meaning that the counit and comultiplication are obtained from the unit and multiplication by ‘flipping’ them using the $†$-category structure. (If we think of a morphism in $\mathrm{Mat}([0,\mathrm{\infty }))$ as a matrix, its dagger is its transpose.)

Conversely, suppose we have any special commutative $†$-Frobenius algebra $x$. Then using the ideas in the paper by Coecke, Pavlovich and Vicary we can recover a basis for $x$, consisting of the vectors $e_i\in x$ with

$$\Delta (e_i)=e_i\otimes e_i$$

This basis forms a set $S$ such that

$$x\cong [0,\mathrm{\infty }{)}^S$$

for some specified isomorphism in $\mathrm{Mat}([0,\mathrm{\infty }))$. Furthermore, this is an isomorphism of special commutative $†$-Frobenius algebras!

In short, a special commutative $†$-Frobenius algebra in $\mathrm{Mat}([0,\mathrm{\infty }))$ is just a fancy way of talking about a finite set.

Functions and bijections

Now suppose we have two special commutative $†$-Frobenius algebra in $\mathrm{Mat}([0,\mathrm{\infty }))$: $x$ and $y$.

Suppose $f:x\to y$ is a Frobenius algebra homomorphism: that is, a map preserving all the structure—the unit, counit, multiplication and comultiplication. Then it comes from an isomorphism of finite sets. This lets us find ${\mathrm{FinSet}}_0$, the groupoid of finite sets and bijections, inside $\mathrm{Mat}([0,\mathrm{\infty }))$.

Alternatively, suppose $f:x\to y$ is just a coalgebra homomorphism: that is a map preserving just the counit and comultiplication. Then it comes from an arbitrary function between finite sets. This lets us find $\mathrm{FinSet}$, the category of finite sets and functions, inside $\mathrm{Mat}([0,\mathrm{\infty }))$.

If $f$ preserves the comultiplication, it automatically preserves the counit. But what if it preserves just the counit? This sounds like a dry, formal question. But it’s not: the answer is something useful, a ‘stochastic map’.

Stochastic maps

A stochastic map from a finite set $S$ to a finite set $T$ is a map sending each point of $S$ to a probability measure on $T$.

We can think of this as a $T\times S$-shaped matrix of numbers in $[0,\mathrm{\infty })$, where a given column gives the probability that a given point in $S$ goes to any point in $T$. The sum of the numbers in each column will be 1. And conversely, any $T\times S$-shaped matrix of numbers in $[0,\mathrm{\infty })$, where each column sums to 1, gives a stochastic map from $S$ to $T$.

But now let’s describe this idea using the category $\mathrm{Mat}([0,\mathrm{\infty }))$. We’ve seen a finite set is the same as a special commutative $†$-Frobenius algebra. So, say we have two of these, $x$ and $y$. Our matrix of numbers in $[0,\mathrm{\infty })$ is just a map

$$f:x\to y$$

So, we just need a way to state the condition that each column in the matrix sums to 1. And this condition simply says that $f$ preserves the counit:

$${ϵ}_y\circ f={ϵ}_x$$

where ${ϵ}_x:x\to [0,\mathrm{\infty })$ is the counit for $x$, and similarly for ${ϵ}_y$.

To understand this, note that if we use the canonical isomorphism

$$x\cong [0,\mathrm{\infty }{)}^S$$

the counit ${ϵ}_x$ can be seen as the map

$$[0,\mathrm{\infty }{)}^S\to [0,\mathrm{\infty })$$

that takes any $S$-tuple of numbers and sums them up. In other words, it’s integration with respect to counting measure. So, the equation

$${ϵ}_y\circ f={ϵ}_x$$

says that if we take any $S$-tuple of numbers, multiply it by the matrix $f$, and then sum up the entries of the resulting $T$-tuple, it’s the same as if we summed up the original $S$-tuple. But this says precisely that each column of the matrix $f$ sums to 1.

Finite measure spaces

Now let’s use our formalism to describe finite measure spaces—by which, beware, I mean a finite sets equipped with measures! To do this, we’ll use a special commutative $†$-Frobenius algebra $x$ in $\mathrm{Mat}([0,\mathrm{\infty }))$ together with any map

$$\mu :[0,\mathrm{\infty })\to x$$

Starting from these, we get a specified isomorphism

$$x\cong [0,\mathrm{\infty }{)}^S$$

and $\mu$ sends the number 1 to a vector in $[0,\mathrm{\infty }{)}^S$: that is, a function on $S$ taking values in $[0,\mathrm{\infty })$. Multiplying this function by counting measure, we get a measure on $S$.

Puzzle. How can we describe this measure without the annoying use of counting measure?

Conversely, any measure on a finite set gives a special commutative $†$-Frobenius algebra $x$ in $\mathrm{Mat}([0,\mathrm{\infty }))$ equipped with a map from $[0,\mathrm{\infty })$.

So, we can say a finite measure space is a special commutative $†$-Frobenius algebra in $\mathrm{Mat}([0,\mathrm{\infty }))$ equipped with a map

$$\mu :[0,\mathrm{\infty })\to x$$

And given two of these,

$$\mu :[0,\mathrm{\infty })\to x,\nu :[0,\mathrm{\infty })\to y$$

and a coalgebra morphism

$$f:x\to y$$

such that the obvious triangle commutes:

$$f\circ \mu =\nu$$

then we get a measure-preserving function between finite measure spaces! Conversely, any measure-preserving function between finite measure spaces gives us such a commutative triangle.

So, we get a way of describing the category $\mathrm{FinMeas}$, with finite measure spaces as objects and measure-preserving maps as objects.

Finite probability measure spaces

I’m mainly interested in probability measures. So suppose $x$ is a special commutative $†$-Frobenius algebra in $\mathrm{Mat}([0,\mathrm{\infty }))$ equipped with a map

$$\mu :[0,\mathrm{\infty })\to x$$

We’ve seen this gives a finite measure space. But this is a probability measure space if and only if

$$e\circ \mu =1$$

where

$$e:x\to [0,\mathrm{\infty })$$

is the counit for $x$. The equation simply says the total integral of our measure $\mu$ is 1.

So, we get a way of describing the category $\mathrm{FinProb}$, with finite probability measure spaces as objects and measure-preserving maps as objects. Given finite probability measure spaces described this way:

$$\mu :[0,\mathrm{\infty })\to x,\nu :[0,\mathrm{\infty })\to y$$

a measure-preserving function is a coalgebra morphism

$$f:x\to y$$

such that the obvious triangle commutes:

$$f\circ \mu =\nu$$

Measure-preserving stochastic maps

Say we have two finite measure spaces. Then we can ask whether a stochastic map from one to the other is measure-preserving. And we can answer this question in the language of $\mathrm{Mat}([0,\mathrm{\infty }))$.

Remember, a finite measure space is a special commutative $†$-Frobenius algebra $x$ in $\mathrm{Mat}([0,\mathrm{\infty }))$ together with a map

$$\mu :[0,\mathrm{\infty })\to x$$

Say we have another one:

$$\nu :[0,\mathrm{\infty })\to y$$

A stochastic map is just a map

$$f:x\to y$$

that preserves the counit:

$${ϵ}_y\circ f={ϵ}_x$$

But it’s a measure-preserving stochastic map if also

$$f\circ \mu =\nu$$

Next…

There’s a lot more to say; I haven’t gotten anywhere near what Tobias and I are doing! But it’s pleasant to have this basic stuff written down.

This is the final continuation of the online reading seminar of Zhang’s paper for the polymath8 project. (There are two other continuations; this previous post, which deals with the combinatorial aspects of the second part of Zhang’s paper, and this previous post, that covers the Type I and Type II sums.) The main purpose of this post is to present (and hopefully, to improve upon) the treatment of the final and most innovative of the key estimates in Zhang’s paper, namely the Type III estimate.

The main estimate was already stated as Theorem 17 in the previous post, but we quickly recall the relevant definitions here. As in other posts, we always take to be a parameter going off to infinity, with the usual asymptotic notation associated to this parameter.

Definition 1 (Coefficient sequences) A coefficient sequence is a finitely supported sequence that obeys the bounds

for all , where is the divisor function.

• (i) If is a coefficient sequence and is a primitive residue class, the (signed) discrepancy of in the sequence is defined to be the quantity

  

• (ii) A coefficient sequence is said to be at scale for some if it is supported on an interval of the form .
• (iii) A coefficient sequence at scale is said to be smooth if it takes the form for some smooth function supported on obeying the derivative bounds

  

  for all fixed (note that the implied constant in the notation may depend on ).

Theorem 2 (Type III estimate) Let be fixed quantities, and let be quantities such that

and

and

for some fixed . Let be coefficient sequences at scale respectively with smooth. Then for any we have

In fact we have the stronger “pointwise” estimate

for all with and all , and some fixed .

Theorem 3 (Type III estimate without ) Let be fixed, and let be quantities such that

and

and

for some fixed . Let be smooth coefficient sequences at scales respectively. Then we have

for all and some fixed .

Let us quickly see how Theorem 3 implies Theorem 2. To show (4), it suffices to establish the bound

for all , where denotes a quantity that is independent of (but can depend on other quantities such as ). The left-hand side can be rewritten as

From Theorem 3 we have

where the quantity does not depend on or . Inserting this asymptotic and using crude bounds on (see Lemma 8 of this previous post) we conclude (4) as required (after modifying slightly).

It remains to establish Theorem 3. This is done by a set of tools similar to that used to control the Type I and Type II sums:

• (i) completion of sums;
• (ii) the Weil conjectures and bounds on Ramanujan sums;
• (iii) factorisation of smooth moduli ;
• (iv) the Cauchy-Schwarz and triangle inequalities (Weyl differencing).

The specifics are slightly different though. For the Type I and Type II sums, it was the classical Weil bound on Kloosterman sums that were the key source of power saving; Ramanujan sums only played a minor role, controlling a secondary error term. For the Type III sums, one needs a significantly deeper consequence of the Weil conjectures, namely the estimate of Bombieri and Birch on a three-dimensional variant of a Kloosterman sum. Furthermore, the Ramanujan sums – which are a rare example of sums that actually exhibit better than square root cancellation, thus going beyond even what the Weil conjectures can offer – make a crucial appearance, when combined with the factorisation of the smooth modulus (this new argument is arguably the most original and interesting contribution of Zhang).

— 1. A three-dimensional exponential sum —

The power savings in Zhang’s Type III argument come from good estimates on the three-dimensional exponential sum

Theorem 4 (Bombieri-Birch bound) Let be square-free. Then for any we have

where is the greatest common divisor of (and we adopt the convention that ). (Here, the denotes a quantity that goes to zero as , rather than as .)

(see Lemma 7 of this previous post). From this and the Chinese remainder theorem we see that factorises as

where . Dilating by , we conclude the multiplicative law

Iterating this law, we see that to prove Theorem 4 it suffices to do so in the case when is prime, or more precisely that

We first consider the case when , so our objective is now to show that

In this case we can write as

where is the Ramanujan sum

Basic Fourier analysis tells us that equals when and when . The expression (6) then follows from direct computation.

Next, suppose that and . Making the change of variables , becomes

Performing the summation, this becomes

For each , the summation is a Kloosterman sum and is thus by the classical Weil bound (Theorem 8 from previous notes). This gives a net estimate of as desired. Similarly if .

The only remaining case is when . Here one cannot proceed purely through Ramanujan and Weil bounds, and we need to invoke the deep result of Bombieri and Birch, proven in Theorem 1 of the the appendix to this paper of Friedlander and Iwaniec. This bound can be proven by applying Deligne’s proof of the Weil conjectures to a certain -function attached to the surface ; an elementary but somewhat lengthy second proof is also given in the above appendix.

To deal with factors such as , the following simple lemma will be useful.

Lemma 5 For any and any we have

in particular

As in the previous theorem, here denotes a quantity that goes to zero as , rather than as .

We now prove Theorem 3. The reader may wish to track the exponents involved in the model regime

where is any fixed power of (e.g. , in which case can be slightly larger than ).

Let be as in Theorem 3, and let be a sufficiently small fixed quantity. It will suffice to show that

where does not depend on . We rewrite the left-hand side as

and then apply completion of sums (Lemma 6 from this previous post) to rewrite this expression as the sum of the main term

plus the error terms

and

where is any fixed quantity and

The first term does not depend on , and the third term is clearly acceptable, so it suffices to show that

Proposition 6 Let be fixed, and let

be such that

and

and

for some fixed , and let be smooth coefficient sequences at scale respectively. Then

for some fixed .

Let us now see why the above proposition implies (8). To prove (8), we may of course assume as the claim is trivial otherwise. We can split

for any function of , so that (8) can be written as

which we expand as

In order to apply Proposition (6) we need to modify the , constraints. By Möbius inversion one has

for any function , and similarly for , so by the triangle inequality we may bound the previous expression by

where

We may discard those values of for which is less than one, as the summation is vacuous in that case. We then apply Proposition (6) with replaced by respectively and set equal to , and replaced by and . One can check that all the hypotheses of Proposition 6 are obeyed, so we may bound (12) by

which by the divisor bound is , which is acceptable (after shrinking slightly).

It remains to prove Proposition 6. Continuing (7), the reader may wish to keep in mind the model case

Note from (9), (10) one has

Expanding out the convolution, our task is to show that

As before, our aim is to obtain a power savings better than over the trivial bound of .

The next step is Weyl differencing. We will need a step size which we will optimise in later. We set

we will make the hypothesis that

and save this condition to be verified later.

By shifting by for and then averaging, we may write the left-hand side of (14) as

By the triangle inequality, it thus suffices to show that

Next, we combine the and summations into a single summation over . We first use a Taylor expansion and (15) to write

for any fixed . If is large enough, then the error term will be acceptable, so it suffices to establish (17) with replaced by for any fixed . We can rewrite

where is such that and

Thus we can estimate the left-hand side of (17) by

Note that implies . But from (10) we have , so in fact we have . Thus

From the divisor bound, we see that for each fixed there are choices for , thus

From this, (18), and Cauchy-Schwarz, we see that to prove (17) it will suffice to show that

We square out (19) as

If we shift by , then relabel by , and use the fact that , we can reduce this to

Next we perform another completion of sums, this time in the variables, to bound

by

for any fixed , where

(the prime is there to distinguish this quantity from in the introduction) and

Making the change of variables and and comparing with(5), we see that

Applying Theorem 4 (and recalling that ) we reduce to showing that

We now choose to be a factor of , thus

for some coprime to . We compute the sum on the left-hand side:

Lemma 7 We have

Proof: We first consider the contribution of the diagonal case . This term may be estimated by

The term gives , while the contribution of the non-zero are acceptable by Lemma 5.

For the non-diagonal case , we see from Lemma 5 that

since , we obtain a bound of from this case as required.

From this lemma, we see that we are done if we can find obeying

as well as the previously recorded condition (16). We can split the condition (21) into three subconditions:

Substituting the definitions (15), (20) of , we can rewrite all of these conditions as lower and upper bounds on . Indeed, (16) follows from (say)

while the other three conditions rearrange to

and

We can combine (23), (24) into a single condition

Also, from (9), (13) we see that this new condition also implies (22). Thus we are done as soon as we find a factor of such that

where

and

From (11) one has

if is sufficiently small. Also, from (11), (9) one also sees that

and . As is -smooth, we can thus find with the desired properties by the greedy algorithm. (In view of Corollary 12 from this previous post, one could also have ensured that has no tiny factors, although this does not seem to be of much actual use in the Type III analysis.)

Today, two articles that I found especially interesting and that I recommend to you:

China’s Tianhe-2 retakes fastest supercomputer crown: A China-based supercomputer has leapfrogged rivals to be named the world’s most powerful system.

This article caught my eye because I think it highlights the degree to which China is rapidly catching up with Europe, the United States and Japan on certain technologies that matter a great deal.  China, unlike the US, which has been generally cutting its scientific spending since around 2000, is putting a tremendous amount of its money into science and engineering, aiming to surpass the world’s current technology leaders. Though they’re still making their way forward, their efforts are starting to pay off.  Since supercomputers are widely used in developing new technology (e.g., simulating novel aircraft), leadership in supercomputers, should they attain it, will have many benefits for the Chinese economy and military.  Lest you think they are merely copying what others have already done, you should make sure to read the last half of the article. Will it take another Sputnik moment to make anti-scientific politicians properly nervous about the cost of falling behind?

The second article of interest was this one (though the headline is a bit overstated…)

Roman Seawater Concrete Holds the Secret to Cutting Carbon Emissions:  Berkeley Lab scientists and their colleagues have discovered the properties that made ancient Roman concrete sustainable and durable

This great story evokes the tragic romance of knowledge lost for centuries — along the lines of the Stradivarius violins that no violin maker today can match. And it weaves several interesting strands.  First is the fact that modern concrete begins to fall apart in seawater in half a century, while the Romans managed to make a concrete that can survive seawater for two millenia.  How did they do it?  

Well, that’s the second interesting part: researchers claim to have figured it out, using one of the most modern of scientific techniques — flashes of ultraviolet or X-ray light, emitted by high-energy electrons traveling at nearly light-speed, in a particle accelerator (the Advanced Light Source). The Advanced Light Source is located at Lawrence Berkeley Laboratory, in the hills above the university we call “Berkeley” (officially the University of California at Berkeley).

The third interesting thing: the researchers learned that the Romans’ concrete, made mainly from lime (from limestone) and volcanic ash (pulverized rock created in abundance during any energetic volcanic eruption), used less lime and was formed at much lower temperatures than modern concrete. If modern concrete were replaced (when appropriate and possible) with a similar material, its production would use much less energy. And since concrete production is a notable contributor to overall energy use, this is not a minor effect.  In short, it’s just possible that this could be one of those rare situations where everyone wins: either the Roman concrete, or, more likely, a modern/ancient hybrid, may turn out to be more durable, more fuel-efficient to produce, and perhaps cheaper than the forms of concrete we use today.  

Thank goodness! The US government is still funding some important research!  Oh.  Right.  I guess it should be mentioned that initial funding for this work came from King Abdullah University of Science and Technology in Saudi Arabia.  Apparently they have a lot of volcanic ash lying about…