The quest for narrow admissible tuples July 2, 2013Posted by Scott Morrison in polymath.
Tags: admissible tuples, polymath8, zhang
(A guest post by Andrew Sutherland.)
With more than 400 comments tacked on to the previous blog post, it’s past time to rollover to a new one. As just punishment for having contributed more than my fair share of those comments, Scott has asked me to write a guest post summarizing the current state of affairs. This task is made easier by Tao’s recent progress report on the polymath project to sharpen Zhang’s result on bounded gaps between primes. If you haven’t already read the progress report I encourage you to do so, but for the benefit of newcomers who would like to understand how our quest for narrow admissible tuples fits in the bounded prime gaps polymath project, here goes.
The Hardy-Littlewood prime tuples conjecture states that every admissible tuple has infinitely many translates that consist entirely of primes. Here a tuple is simply a set of integers, which we view as an increasing sequence ; we refer to a tuple of size as a -tuple. A tuple is admissible if it does not contain a complete set of residues modulo any prime . For example, 0,2,4 is not an admissible 3-tuple, but both 0,2,6 and 0,4,6 are. A translate of a tuple is obtained by adding a fixed integer to each element; the sequences 5,7,11 and 11,13,17 are the first two translates of 0,2,6 that consist entirely of primes, and we expect that there are infinitely more. Admissibility is clearly a necessary condition for a tuple to have infinitely many translates made up of primes; the conjecture is that it is also sufficient.
Zhang proved a weakened form the prime tuples conjecture, namely, that for all sufficiently large , every admissible -tuple has infinitely many translates that contain at least 2 primes (as opposed to ). He made this result explicit by showing that one may take , and then noted the existence of an admissible -tuple with diameter (difference of largest and smallest elements) less than 70,000,000. Zhang’s -tuple consists of the first primes greater than , which is clearly admissible. As observed by Trudgian, the diameter of this -tuple is actually less than 60,000,000 (it is precisely 59,874,954).
Further improvements to Zhang’s bound came rapidly, first by finding narrower admissible -tuples, then by optimizing and the critical parameter on which it depends (this means making larger; is proportional to ). Since it began on June 4, the polymath8 project has been working along three main lines of attack: (1) improving bounds on and a related parameter , (2) deriving smaller values of from a given pair , and (3) the search for narrow admissible -tuples.You can see the steady progress that has been made on these three interlocking fronts by viewing the list of world records.
A brief perusal of this list makes it clear that, other than some quick initial advances made by tightening obvious slack in Zhang’s bounds, most of the big gains have come from improving the bounds on (edit: as pointed out by v08ltu below, reducing the dependence of on from to was also a major advance); see Tao’s progress report and related blog posts for a summary of this work. Once new values of and have been established, it is now relatively straight-forward to derive an optimal (at least within 1 or 2; the introduction of Pintz’s method has streamlined this process). There then remains the task of finding admissible -tuples that are as narrow as possible; it is this last step that is the subject of this blog post and the two that preceded it. Our goal is to compute , the smallest possible diameter of an admissible -tuple, or at least to obtain bounds (particularly upper bounds) that are as tight as we can make them.
A general way to construct a narrow admissible -tuple is to suppose that we first sieve the integers of one residue class modulo each prime and then choose a set of survivors, preferably ones that are as close together as possible. In fact, it is usually not necessary to sieve a residue class for every prime in order to obtain an admissible -tuple, asymptotically an bound should suffice. The exact number of residue classes that require sieving depends not only on , but also on the interval in which one looks for survivors (it could also depend on the order in which one sieves residue classes, but we will ignore this issue).
All of the initial methods we considered involved sieving residue classes 0 mod , and varied only in where to look for the survivors. Zhang takes the first survivors greater than 1 (after sieving modulo primes up to ), and Morrison’s early optimizations effectively did the same, but with a lower sieving bound. The Hensley-Richards approach instead selects survivors from an interval centered at the origin, and the asymmetric Hensley-Richards optimization shifts this interval slightly (see our wiki page for precise descriptions of each of these approaches, along with benchmark results for particular values of interest).
But there are sound practical reasons for not always sieving 0 mod . Assuming we believe the prime tuples conjecture (which we do!), we can certainly find an optimally narrow admissible -tuple somewhere among the primes greater than , all of which survive sieving 0 modulo primes . However, the quantitative form of the prime tuples conjecture tells us roughly how far we might need to search in order to find one. The answer is depressingly large: the expected number of translates of any particular admissible -tuple to be found among the primes is thus we may need to search through the primes in an interval of size exponential in in order to have a good chance of finding even one translate of the -tuple we seek.
Schinzel suggested that it would be better to sieve 1 mod 2 rather than 0 mod 2, and more generally to sieve 1 mod for all primes up to some intermediate bound and then switch to sieving 0 mod for the remaining primes. We find that simply following Schinzel’s initial suggestion, works best, and one can see the improvement this yields on the benchmarks page (unlike Schinzel, we don’t restrict ourselves to picking the first survivors to the right of the origin, we may shift the interval to obtain a better bound).
But sieving a fixed set of residue classes is still too restrictive. In order to find narrower admissible tuples we must relax this constraint and instead consider a greedy approach, where we start by picking an interval in which we hope to find survivors (we know that the size of this interval should be just slightly larger than ), and then run through the primes in order, sieving whichever residue class is least occupied by survivors (we can break ties in any way we like, including at random). Unfortunately a purely greedy approach does not work very well. What works much better is to start with a Schinzel sieve, sieving 1 mod 2 and 0 mod primes up to a bound slightly smaller than , and then start making greedy choices. Initially the greedy choice will tend to be the residue class 0 mod , but it will deviate as the primes get larger. For best results the choice of interval is based on the success of the greedy sieving.
This is known as the “greedy-greedy” algorithm, and while it may not have a particularly well chosen name (this is the downside of doing math in a blog comment thread, you tend to throw out the first thing that comes to mind and then get stuck with it), it performs remarkably well. For the values of listed in the benchmarks table, the output of the greedy-greedy algorithm is within 1 percent of the best results known, even for , where the optimal value is known.
But what about that last 1 percent? Here we switch to local optimizations, taking a good admissible tuple (e.g. one output by the greedy-greedy algorithm) and trying to make it better. There are several methods for doing this, some involve swapping a small set of sieved residue classes for a different set, others shift the tuple by adding elements at one end and deleting them from the other. Another approach is to randomly perturb the tuple by adding additional elements that make it inadmissible and then re-sieving to obtain a new admissible tuple. This can be done in a structured way by using a randomized version of the greedy-greedy algorithm to obtain a similar but slightly different admissible tuple in approximately the same interval, merging it with the reference tuple, and then re-sieving to obtain a new admissible tuple. These operations can all be iterated and interleaved, ideally producing a narrower admissible tuple. But even when this does not happen one often obtains a different admissible tuple with the same diameter, providing another reference tuple against which further local optimizations may be applied.
Recently, improvements in the bounds on brought below 4507, and we entered a regime where good bounds on are already known, thanks to prior work by Engelsma. His work was motivated by the second Hardy-Littlewood conjecture, which claims that for all , a claim that Hensley and Richards showed is asymptotically incompatible with the prime tuples conjecture (and now generally believed to be false). Engelsma was able to find an admissible 447-tuple with diameter 3158, implying that if the prime tuples conjecture holds then there exists an (infinitely many in fact) for which , which is greater than . In the process of obtaining this result, Engelsma spent several years doing extensive computations, and obtained provably optimal bounds on for all , as well as upper bounds on for . The quality of these upper bounds is better in some regions than in others (Engelsma naturally focused on the areas that were most directly related to his research), but they are generally quite good, and for up to about 700 believed to be the best possible.
We have now merged our results with those of Engelsma and placed them in an online database of narrow admissible -tuples that currently holds records for all up to 5000. The database is also accepts submissions of better admissible tuples, and we invite anyone and everyone to try and improve it. Since it went online a week ago it has processed over 1000 submissions, and currently holds tuples that improve Engelsma’s bounds at 1927 values of , the smallest of which is 785. As I write this stands at (subject to confirmation), which happens to be one of the places where we have made an improvement, yielding a current prime gap bound of 6,712 (but I expect this may drop again soon).
In addition to supporting the polymath prime gaps project, we expect this database will have other applications, including further investigations of the second Hardy-Littlewood conjecture. As can be seen in this chart, not only have we found many examples of admissible -tuples whose diameter satisfies , one can view the growth rate of the implied lower bounds on in this chart.