Polymath Wiki - User contributions [en]

Polymath8 grant acknowledgments

2013-09-23T06:27:44Z

Savitt: /* Other acknowledgments */

Participants should be arranged in alphabetical order of surname.

== Participants and contact information ==

(Caution: this list may be incomplete. Participants who have made significant contributions to the project (on par with a co-author on a traditional mathematical research paper should add themselves to this list, or email tao@math.ucla.edu if they are unable to do so directly. Participants who have made auxiliary contributions to the project (on par with those mentioned in an Acknowledgments section in a traditional paper) should add themselves instead to the list at the bottom of the page.)

* Wouter Castryck, KU Leuven, [https://perswww.kuleuven.be/~u0040935/]
* Etienne Fouvry, Université Paris-Sud, [Etienne.Fouvry@math.u-psud.fr]
* Gergely Harcos, Rényi Institute, [http://www.renyi.hu/~gharcos/]
* Emmanuel Kowalski, ETHZ, [http://www.math.ethz.ch/~kowalski/]
* Philippe Michel, EPFL, [http://tan.epfl.ch/philippe.michel]
* Paul Nelson, EPFL, [http://people.epfl.ch/paul.nelson]
* Eytan Paldi, Technion Institute
* Janos Pintz, Rényi Institute, [http://www.renyi.hu/~pintz/]
* Andrew V. Sutherland, MIT, [http://math.mit.edu/~drew]
* Terence Tao, UCLA, [http://www.math.ucla.edu/~tao]
* Xiao-Feng Xie, Carnegie Mellon University, [http://www.cs.cmu.edu/~xfxie]

== Grant information ==

* Wouter Castryck was supported by FWO-Vlaanderen.
* Etienne Fouvry was partially supported by the Institut Universitaire de France.
* Gergely Harcos was supported by OTKA grants K 101855 and K 104183, and by ERC Advanced Grant 228005.
* Phillipe Michel was partially supported by the grant SNF-137488 and the grant ERC-EQUIARITH AdG- 228304.
* Paul Nelson is supported by NSF grant OISE-1064866 and partially supported by grant SNF-137488.
* Janos Pintz was supported by OTKA grants No. K100291, NK104183 and ERC-AdG. 228005.
* Andrew V. Sutherland was supported by NSF grant DMS-1115455.
* Terence Tao was supported by a Simons Investigator grant, and by NSF grant DMS-1266164.

== Other acknowledgments ==

Other contributors to the project include [http://maths.anu.edu.au/people/vigleik-angeltveit Vigleik Angelveit], [https://www.dpmms.cam.ac.uk/~bjg23/ Ben Green], Hannes, [http://tqft.net/ Scott Morrison], [http://math.byu.edu/home/user/50 Pace Nielsen], [http://math.arizona.edu/~savitt/papers David Savitt] and v08ltu.

We also thank John Friedlander for help with the references, and Thomas Engelsma for supplying us with his data on admissible prime tuples.

Thanks to Michael Nielsen for hosting the polymath wiki for this project.

Finding narrow admissible tuples

2013-06-12T01:00:16Z

Savitt: /* Benchmarks */ typos

For any natural number <math>k_0</math>, an ''admissible <math>k_0</math>-tuple'' is a finite set <math>{\mathcal H}</math> of integers of cardinality <math>k_0</math> which avoids at least one residue class modulo <math>p</math> for each prime <math>p</math>. (Note that one only needs to check those primes <math>p</math> of size at most <math>k_0</math>, so this is a finitely checkable condition.) Let <math>H(k_0)</math> denote the minimal diameter <math>\max {\mathcal H} - \min {\mathcal H}</math> of an admissible <math>k_0</math>-tuple. As part of the [[Bounded gaps between primes|Polymath8]] project, we would like to find as good an upper bound on <math>H(k_0)</math> as possible for given values of <math>k_0</math>. To a lesser extent, we would also be interested in lower bounds on this quantity. There is some scattered numerical evidence that the optimal value of H is roughly of size <math>k_0 \log k_0 + k_0</math> for <math>k_0</math> in the range of interest.

== Upper bounds ==

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo <math>p</math> from an interval for a lot of primes <math>p</math>. Examples of sieves, in roughly increasing order of efficiency, are listed below.

=== Zhang sieve ===

The Zhang sieve uses the tuple

:<math>{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}</math>

where <math>m</math> is taken to optimize the diameter <math>p_{m+k_0}-p_{m+1}</math> while staying admissible (in practice, this basically means making <math>m</math> as small as possible). Certainly any <math>m</math> with <math>p_{m+1} > k_0</math> works (in particular, one can just take <math>{\mathcal H}</math> to be the first <math>k_0</math> primes past <math>k_0</math>, but this is not optimal. Applying the prime number theorem then gives the upper bound <math>H \leq (1+o(1)) k_0\log k_0</math>.

=== Hensley-Richards sieve ===

The Hensley-Richards sieve [HR1973], [HR1973b], [R1974] uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1}\}</math>

where m is again optimised to minimize the diameter while staying admissible.

=== Asymmetric Hensley-Richards sieve ===

The asymmetric Hensley-Richard sieve uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1+i}\}</math>

where <math>i</math> is an integer and <math>i,m</math> are optimised to minimize the diameter while staying admissible.

=== Schinzel sieve ===
Given <math>0<y<z</math>, the Schinzel sieve (discussed in [HR1973], [CJ2001] first sieves by <math>1\bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y . For a given choice of <math>y</math>, the parameter <math>z</math> is minimized subject to ensuring that the first <math>k_0</math> survivors (after the first) form an admissible sequence <math>\mathcal{H}</math>, so the only free parameter is <math>y</math>, which is chosen to minimize the diameter of <math>\mathcal{H}</math>. The case <math>y=1</math> corresponds to a sieve of Eratosthenes, which will typically yield the same sequence as Zhang with the minimal (but not necessarily optimal) value of <math>m</math> that yields an admissible <math>k_0</math>-tuple. As originally proposed, the Schinzel sieve works over the positive integers, but one can instead sieve intervals centered about the origin, or asymmetric intervals, as with the Hensley-Richards sieve.

=== Greedy sieve ===
For a given interval (e.g., <math>[1,x]</math>, <math>[-x,x]</math>, or asymmetric <math>[x_0,x_1]</math>) one sieves a single residue class <math>a \bmod p</math> for increasing primes <math>p=2,3,5,\ldots</math>, with <math>a</math> chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize <math>a\in[0,p-1]</math>, maximize <math>a\in [0,p-1]</math>, minimize <math>|a-\lfloor p/2\rfloor|</math>, or randomly. If not all residue classes modulo <math>p</math> are occupied by survivors, then <math>a</math> will be chosen so that no survivors are sieved.
This necessarily occurs once <math>p</math> exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest <math>k_0</math>-tuple <math>{\mathcal H}</math> among the survivors (if there are fewer than <math>k_0</math> survivors, retry with a wider interval).

=== Greedy-Schinzel sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a Schinzel sieve with <math>y=2</math> and <math>z=\sqrt{x_1-x_0}</math> and then continuing in a greedy fashion
This method was proposed by Sutherland and originally referred to as a [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 "greedy-greedy"] approach. This nomenclature arose from the fact that one optimization that can be applied to the standard Schinzel sieve on a given interval is to "greedily" avoid sieving modulo primes where the set of survivors is already admissible (this may occur for primes less than the minimal value of <math>z</math> that yields <math>k_0</math>-survivors), while a second optimization is to use a value of <math>z</math> that is intentionally smaller than necessary and switch to greedy sieving for primes greater than <math>z</math>. With the choice <math>z=\sqrt{x_1-x_0}</math>, unless the initial interval is much larger than necessary, all primes up to <math>z</math> will require a residue class to be sieved and the first "greedy" seldom applies.

=== Seeded greedy sieve ===
Given an initial sequence <math>{\mathcal S}</math> that is known to contain an admissible <math>k_0</math>-tuple, one can apply greedy sieving to the minimal interval containing <math>{\mathcal S}</math> until an admissible sequence of survivors remains, and then choose the narrowest <math>k_0</math>=tuple it contains. The sieving methods above can be viewed as the special case where <math>{\mathcal S}</math> is the set of integers in some interval. The main difference is that the choice of <math>{\mathcal S}</math> affects when ties occur and how they are broken with greedy sieving.
One approach is to take <math>{\mathcal S}</math> to be the union of two <math>k_0</math>-tuples that lie in roughly the same interval (see Iterated merging) below.

=== Iterated merging ===
Given an admissible <math>k_0</math>-tuple <math>\mathcal{H}_1</math>, one can attempt to improve it using an iterated merging approach [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 suggested by Castryck]. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible <math>k_0</math>-tuple <math>\mathcal{H}_2</math> in roughly the same interval as <math>\mathcal{H}_1</math>, then performs a randomized greedy sieve using the seed set <math>\mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2</math> to obtain an admissible <math>k_0</math>-tuple <math>\mathcal{H}_3</math>. If <math>\mathcal{H}_3</math> is narrower than <math>\mathcal{H}_2</math>, replace <math>\mathcal{H}_2</math> with <math>\mathcal{H}_3</math>, otherwise try again with a new <math>\mathcal{H}_3</math>.
Eventually the diameter of <math>\mathcal{H}_2</math> will become less than or equal to that of <math>\mathcal{H}_1</math>.
As long as <math>\mathcal{H}_1\ne \mathcal{H}_2</math>, one can continue to attempt to improve <math>\mathcal{H}_2</math>, but in practice one stops after some number of retries.

As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23733 described by Sutherland], one can then replace <math>\mathcal{H}_1</math> with <math>\mathcal{H}_2</math> and begin the process anew, yielding a randomized algorithm that can be run indefinitely. Key parameters to this algorithm are the choice of the interval used when constructing <math>\mathcal{H}_2</math>, which is typically made wider than the minimal interval containing <math>\mathcal{H}_1</math> by a small factor <math>\delta</math> on each side (Sutherland suggests <math>\delta = 0.0025</math>), and the number of failed attempts allowed while attempting to impove <math>\mathcal{H}_2</math>.

Eventually this process will tend to converge to particular <math>\mathcal{H}_1</math> that it cannot improve (or more generally, a set of similar <math>\mathcal{H}_1</math>'s with the same diameter). Interleaving iterated merging with the local optimizations described below often allows the algorithm to make further progress.

----

Iterated merging can be viewed as a form of simulated annealing. The set <math>\mathcal{S}</math> initially contains at least two admissible <math>k_0</math>-tuples (typically many more), and as the algorithm proceeds the set <math>\mathcal{S}</math> converges toward <math>\mathcal{H}_1</math> and the number of admissible <math>k_0</math>-tuples it contains declines. One can regard the cardinality of the difference between <math>\mathcal{S}</math> and <math>\mathcal{H}_1</math> as a measure of the "temperature" of a gradually cooling system, since the number of choices available to the algorithm declines as this cardinality is reduced (more precisely, one may consider the entropy of the possible sequence of tie-breaking choices available for a given <math>\mathcal{S}</math>).

=== Local optimizations ===

Let <math>\mathcal H = \{h_1,\ldots, h_{k_0}\}</math> be an admissible <math>k_0</math>-tuple with endpoints <math>h_1</math> and <math>h_{k_0}</math>, and let <math>\mathcal I</math> be the interval <math>[h_1,h_{k_0}]</math>. If there exists an integer <math>h\in\mathcal I</math> such that removing one of <math>\mathcal H</math>'s endpoints and inserting <math>h</math> yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, then call <math>\mathcal H</math> ''contractible'', and if not, say that <math>\mathcal H</math> non-contractible. Note that <math>\mathcal H'</math> necessarily has smaller diameter than <math>\mathcal H</math>. Any of the sieving methods described above may produce admissible <math>k_0</math>-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing <math>\mathcal H</math> by <math>\mathcal H'</math> if this test succeeds.

We can also ''shift'' <math>\mathcal H </math> to the left by removing its right end point <math>h_{k_0}</math> and replacing it with the greatest integer <math>h_0 < h_1</math> that yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, and we can similarly shift <math>\mathcal H</math> to the right. The diameter of <math>\mathcal H'</math> need not be less than <math>\mathcal H</math>, but if it is, it provides a useful replacement. More generally, by shifting <math>\mathcal H</math> repeatedly we can produce a sequence of admissible <math>k_0</math>-tuples that lie successively further to the left or right. In general the diameter of these tuples may grow as we do so, but it will also occasionally decline, and we may be able to find a shifted <math>\mathcal H'</math> with smaller diameter than <math>\mathcal H</math>.

----

A more sophisticated local optimization involves a process of ``adjustment" [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23766 proposed by Savitt].
Let <math>\mathcal H </math> be an admissible <math>k_0</math>-tuple.
For a prime <math>p</math> and an integer <math>a</math>, let <math>[a;p]</math> denote the residue class <math>a\bmod p</math>, i.e. the set of integers <math>\{ x : x = a \bmod p\}</math>.
Call <math>[a;p]</math> occupied if it contains an element of <math>\mathcal H </math>.

Suppose that <math>[a;p]</math> and <math>[b;q]</math> are occupied residue classes, for some distinct primes <math>p</math> and <math>q</math>, and that <math>[a';p]</math> and <math>[b';q]</math> are unoccupied.
Let <math>\mathcal U</math> be the intersection of <math>\mathcal H</math> with <math>[a;p] \cup [b;q]</math>, and let <math>\mathcal V</math> be a subset of the integers that lie in the intersection of the interval <math>I</math> containing <math>H</math> and the set <math>[a';p] \cup [b';q]</math> such that
the set <math>\mathcal H' </math> formed by removing the elements of <math>\mathcal U</math> from <math>\mathcal H </math> and adding the elements of <math>\mathcal V </math> is admissible.
A necessary (and often sufficient) condition for and integer <math>v</math> to lie in <math>\mathcal V</math> is that <math>v</math> must not lie in a residue class <math>[c;r]</math> that is the unique unoccupied residue class modulo <math>r</math> for any prime <math>r</math> other than <math>p</math> or <math>q</math>.

The admissible set <math>\mathcal H' </math> lies in the interval <math>\mathcal I</math> containing <math>\mathcal H</math>, so its diameter is no greater than that of <math>\mathcal H</math>, however its cardinality may differ. If it happens that <math>\mathcal H' </math> contains more elements than <math>\mathcal H </math>, then by eliminating points at either end of <math>\mathcal H' </math> we obtain an admissible <math>k_0</math>-tuple that is narrower than <math>\mathcal H</math> and may ``adjust" <math>\mathcal H </math> by replacing it with <math>\mathcal H' </math>.
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible <math>k_0</math>-tuples.

=== Further refinements ===

== Lower bounds ==

There is a substantial amount of literature on bounding the quantity <math>\pi(x+y)-\pi(x)</math>, the number of primes in a shifted interval <math>[x+1,x+y]</math>, where <math>x,y</math> are natural numbers. As a general rule, whenever a bound of the form

: <math> \pi(x+y) - \pi(x) \leq F(y) </math> (*)

is established for some function <math>F(y)</math> of <math>y</math>, the method of proof also gives a bound of the form

: <math> k_0 \leq F( H(k_0)+1 ).</math> (**)

Indeed, if one assumes the prime tuples conjecture, any admissible <math>k_0</math>-tuple of diameter <math>H</math> can be translated into an interval of the form <math>[x+1,x+H+1]</math> for some <math>x</math>. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for <math>x>y</math>, the set of primes between <math>x+1</math> and <math>x+y</math> is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

=== Brun-Titchmarsh inequality ===

The Brun-Titchmarsh theorem gives

: <math> \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}</math>

which then gives the lower bound

: <math> H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0</math>.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem [MV1973, Corollary 2], giving the more precise inequality

: <math> k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.</math>

=== First Montgomery-Vaughan large sieve inequality ===

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

: <math> k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2</math>

for any <math>Q > 1</math>, which is a parameter that one can optimise over (the optimal value is comparable to <math>H(k_0)^{1/2}</math>).

=== Second Montgomery-Vaughan large sieve inequality ===

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

: <math> k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}</math>

for any <math>z > 1</math>, which is a parameter similar to <math>Q</math> in the previous inequality, and <math>c</math> is an absolute constant. In the original paper of Montgomery and Vaughan, <math>c</math> was taken to be <math>3/2</math>; this was then reduced to <math>\sqrt{22}/\pi</math> [B1995, p.162] and then to <math>3.2/\pi</math> [M1978]. It is conjectured that <math>c</math> can be taken to in fact be <math>1</math>.

== Benchmarks ==

Efforts to fill in the blank fields in this table are very welcome.

{| border=1
|-
!<math>k_0</math>!!3,500,000!! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 10,719 !! 5,000 !! 4,000 !! 3,000 !! 2,000 !! 1,000 !! 672
|-
! Upper bounds
|-
| First <math>k_0</math> primes past <math>k_0</math>
| [http://arxiv.org/abs/1305.6369 59,874,594]
| 2,530,338
| 420,878
| 310,134
| 275,082
| 117,714
| 50,840
| 39,660
| 28,972
| 18,386
| 8,424
| 5,406
|-
|Zhang sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 59,093,364]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411932.txt 411,932]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23282_268536.txt 268,536]
| [http://math.mit.edu/~drew/admissible_10719.txt 114,806]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
| [http://math.mit.edu/~drew/admissible_4000_38596.txt 38,596]
| [http://math.mit.edu/~drew/admissible_3000_28008.txt 28,008]
| [http://math.mit.edu/~drew/admissible_2000_17766.txt 17,766]
| [http://math.mit.edu/~drew/admissible_1000_8212.txt 8,212]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
|-
|Hensley-Richards sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2422558.txt 2,422,558]
| [http://math.mit.edu/~drew/admissible_34429_402790.txt 402,790]
| [http://math.mit.edu/~drew/admissible_26024_297454.txt 297,454]
| [http://math.mit.edu/~drew/admissible_23283_262794.txt 262,794]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
| [http://math.mit.edu/~drew/admissible_4000_38498.txt 38,498]
| [http://math.mit.edu/~drew/admissible_3000_27806.txt 27,806]
| [http://math.mit.edu/~drew/admissible_2000_17726.txt 17,726]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
|-
|Asymmetric Hensley-Richards
|
|
| [http://math.mit.edu/~drew/admissible_34429_401700.txt 401,700]
| [http://math.mit.edu/~drew/admissible_26024_296154.txt 296,154]
| [http://math.mit.edu/~drew/admissible_23283_262286.txt 262,286]
| [http://math.mit.edu/~drew/admissible_10719_112562.txt 112,562]
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
| [http://math.mit.edu/~drew/admissible_4000_37932.txt 37,932]
| [http://math.mit.edu/~drew/admissible_3000_27638.txt 27,638]
| [http://math.mit.edu/~drew/admissible_2000_17676.txt 17,676]
| [http://math.mit.edu/~drew/admissible_1000_8168.txt 8,168]
| [http://math.mit.edu/~drew/admissible_672_5220.txt 5,220]
|-
|Schinzel sieve
|
|
|
|
|
|
|
|
|
|
|
|
|-
|greedy-Schinzel sieve
|
|
|
| [http://math.mit.edu/~drew/admissible_26024_286308.txt 286,308]
| [http://math.mit.edu/~drew/admissible_23283_253968.txt 253,968]
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
| [http://math.mit.edu/~drew/admissible_4000_36756.txt 36,756]
| [http://math.mit.edu/~drew/admissible_3000_26754.txt 26,754]
| [http://math.mit.edu/~drew/admissible_2000_17054.txt 17,054]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5.030]
|-
|Best known tuple
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2345896.txt 2,345,896]
| [http://math.mit.edu/~drew/admissible_34429_386532.txt 386,532]
| [http://math.mit.edu/~drew/admissible_26024_285210.txt 285,210]
| [http://math.mit.edu/~drew/admissible_23283_252804.txt 252,804]
| [http://math.mit.edu/~drew/admissible_10719_108462.txt 108,462]
| [http://math.mit.edu/~drew/admissible_5000_46824.txt 46,824]
| [http://math.mit.edu/~drew/admissible_4000_36636.txt 36,636*]
| [http://math.mit.edu/~drew/admissible_3000_26622.txt 26,622]
| [http://math.mit.edu/~drew/admissible_2000_16984.txt 16,984*]
| [http://math.mit.edu/~drew/admissible_1000_7808.txt 7,808*]
| [http://math.mit.edu/~drew/admissible_672_5010.txt 5,010*]
|-
| Engelsma data
| N/A
| N/A
| N/A
| N/A
| N/A
| N/A
| N/A
| 36,622
| 26,622
| 16,978
| 7,802
| 4,998
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 2,372,232
| 394,096
| 290,604
| 257,405
| 110,119
| 47,586
| 37,176
| 27,019
| 17,202
| 7,907
| 5,046
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,642]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,924]
|
|
|
|
|
|
|
|
|-
|MV with <math>c=3.2/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,322]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,719]
|
|
|
|
|
|
|
|
|-
|MV with <math>c=\sqrt{22}/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 227,078]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,860]
|
|
|
|
|
|
|
|
|-
|Second Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 226,987]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,793]
|
|
|
|
|
|
|
|
|-
|Brun-Titchmarsh
| 30,137,225
| 1,272,083
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 211,046]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555]
| 137,756
| 58,863
| 25,351
| 19,785
| 14,358
| 9,118
| 4,167
| 2,648
|-
|First Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711]
|
|
|
|
|
|
|
|
|}

<nowiki>*</nowiki> indicates that the widths listed are the best known tuples that have been found by the methods that gave the entries for larger values of <math>k_0</math>, but are not as narrow as the literally best known tuples (due to Engelsma).

The greedy-Schinzel tuples were generated by breaking ties downward in every case, as in Sutherland's original greedy-greedy algorithm (and the optimal interval was selected on this basis).
As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23588 noted by Castryck], breaking ties upward may produce better results in some cases.
The chosen intervals are not guaranteed to be optimal (especially for the larger valued of <math>k_0</math>), but are believed to be so.

Finding narrow admissible tuples

2013-06-11T20:18:51Z

Savitt: /* Benchmarks */

For any natural number <math>k_0</math>, an ''admissible <math>k_0</math>-tuple'' is a finite set <math>{\mathcal H}</math> of integers of cardinality <math>k_0</math> which avoids at least one residue class modulo <math>p</math> for each prime <math>p</math>. (Note that one only needs to check those primes <math>p</math> of size at most <math>k_0</math>, so this is a finitely checkable condition.) Let <math>H(k_0)</math> denote the minimal diameter <math>\max {\mathcal H} - \min {\mathcal H}</math> of an admissible <math>k_0</math>-tuple. As part of the [[Bounded gaps between primes|Polymath8]] project, we would like to find as good an upper bound on <math>H(k_0)</math> as possible for given values of <math>k_0</math>. To a lesser extent, we would also be interested in lower bounds on this quantity. There is some scattered numerical evidence that the optimal value of H is roughly of size <math>k_0 \log k_0 + k_0</math> for <math>k_0</math> in the range of interest.

== Upper bounds ==

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo <math>p</math> from an interval for a lot of primes <math>p</math>. Examples of sieves, in roughly increasing order of efficiency, are listed below.

=== Zhang sieve ===

The Zhang sieve uses the tuple

:<math>{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}</math>

where <math>m</math> is taken to optimize the diameter <math>p_{m+k_0}-p_{m+1}</math> while staying admissible (in practice, this basically means making <math>m</math> as small as possible). Certainly any <math>m</math> with <math>p_{m+1} > k_0</math> works, but this is not optimal. Applying the prime number theorem then gives the upper bound <math>H \leq (1+o(1)) k_0\log k_0</math>.

=== Hensley-Richards sieve ===

The Hensley-Richards sieve [HR1973], [HR1973b], [R1974] uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1}\}</math>

where m is again optimised to minimize the diameter while staying admissible.

=== Asymmetric Hensley-Richards sieve ===

The asymmetric Hensley-Richard sieve uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1+i}\}</math>

where <math>i</math> is an integer and <math>i,m</math> are optimised to minimize the diameter while staying admissible.

=== Schinzel sieve ===
Given <math>0<y<z</math>, the Schinzel sieve (discussed in [HR1973], [CJ2001] first sieves by <math>1\bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y . For a given choice of <math>y</math>, the parameter <math>z</math> is minimized subject to ensuring that the first <math>k_0</math> survivors (after the first) form an admissible sequence <math>\mathcal{H}</math>, so the only free parameter is <math>y</math>, which is chosen to minimize the diameter of <math>\mathcal{H}</math>. The case <math>y=1</math> corresponds to a sieve of Eratosthenes, which will typically yield the same sequence as Zhang with the minimal (but not necessarily optimal) value of <math>m</math> that yields an admissible <math>k_0</math>-tuple. As originally proposed, the Schinzel sieve works over the positive integers, but one can instead sieve intervals centered about the origin, or asymmetric intervals, as with the Hensley-Richards sieve.

=== Greedy sieve ===
For a given interval (e.g., <math>[1,x]</math>, <math>[-x,x]</math>, or asymmetric <math>[x_0,x_1]</math>) one sieves a single residue class <math>a \bmod p</math> for increasing primes <math>p=2,3,5,\ldots</math>, with <math>a</math> chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize <math>a\in[0,p-1]</math>, maximize <math>a\in [0,p-1]</math>, minimize <math>|a-\lfloor p/2\rfloor|</math>, or randomly. If not all residue classes modulo <math>p</math> are occupied by survivors, then <math>a</math> will be chosen so that no survivors are sieved.
This necessarily occurs once <math>p</math> exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest <math>k_0</math>-tuple <math>{\mathcal H}</math> among the survivors (if there are fewer than <math>k_0</math> survivors, retry with a wider interval).

=== Greedy-Schinzel sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a Schinzel sieve with <math>y=2</math> and <math>z=\sqrt{x_1-x_0}</math> and then continuing in a greedy fashion
This method was proposed by Sutherland and originally referred to as a [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 "greedy-greedy"] approach. This nomenclature arose from the fact that one optimization that can be applied to the standard Schinzel sieve on a given interval is to "greedily" avoid sieving modulo primes where the set of survivors is already admissible (this may occur for primes less than the minimal value of <math>z</math> that yields <math>k_0</math>-survivors), while a second optimization is to use a value of <math>z</math> that is intentionally smaller than necessary and switch to greedy sieving for primes greater than <math>z</math>. With the choice <math>z=\sqrt{x_1-x_0}</math>, unless the initial interval is much larger than necessary, all primes up to <math>z</math> will require a residue class to be sieved and the first "greedy" seldom applies.

=== Seeded greedy sieve ===
Given an initial sequence <math>{\mathcal S}</math> that is known to contain an admissible <math>k_0</math>-tuple, one can apply greedy sieving to the minimal interval containing <math>{\mathcal S}</math> until an admissible sequence of survivors remains, and then choose the narrowest <math>k_0</math>=tuple it contains. The sieving methods above can be viewed as the special case where <math>{\mathcal S}</math> is the set of integers in some interval. The main difference is that the choice of <math>{\mathcal S}</math> affects when ties occur and how they are broken with greedy sieving.
One approach is to take <math>{\mathcal S}</math> to be the union of two <math>k_0</math>-tuples that lie in roughly the same interval (see Iterated merging) below.

=== Iterated merging ===
Given an admissible <math>k_0</math>-tuple <math>\mathcal{H}_1</math>, one can attempt to improve it using an iterated merging approach [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 suggested by Castryck]. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible <math>k_0</math>-tuple <math>\mathcal{H}_2</math> in roughly the same interval as <math>\mathcal{H}_1</math>, then performs a randomized greedy sieve using the seed set <math>\mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2</math> to obtain an admissible <math>k_0</math>-tuple <math>\mathcal{H}_3</math>. If <math>\mathcal{H}_3</math> is narrower than <math>\mathcal{H}_2</math>, replace <math>\mathcal{H}_2</math> with <math>\mathcal{H}_3</math>, otherwise try again with a new <math>\mathcal{H}_3</math>.
Eventually the diameter of <math>\mathcal{H}_2</math> will become less than or equal to that of <math>\mathcal{H}_1</math>.
As long as <math>\mathcal{H}_1\ne \mathcal{H}_2</math>, one can continue to attempt to improve <math>\mathcal{H}_2</math>, but in practice one stops after some number of retries.

As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23733 described by Sutherland], one can then replace <math>\mathcal{H}_1</math> with <math>\mathcal{H}_2</math> and begin the process anew, yielding a randomized algorithm that can be run indefinitely. Key parameters to this algorithm are the choice of the interval used when constructing <math>\mathcal{H}_2</math>, which is typically made wider than the minimal interval containing <math>\mathcal{H}_1</math> by a small factor <math>\delta</math> on each side (Sutherland suggests <math>\delta = 0.0025</math>), and the number of failed attempts allowed while attempting to impove <math>\mathcal{H}_2</math>.

Eventually this process will tend to converge to particular <math>\mathcal{H}_1</math> that it cannot improve (or more generally, a set of similar <math>\mathcal{H}_1</math>'s with the same diameter). Interleaving iterated merging with the local optimizations described below often allows the algorithm to make further progress.

----

Iterated merging can be viewed as a form of simulated annealing. The set <math>\mathcal{S}</math> initially contains at least two admissible <math>k_0</math>-tuples (typically many more), and as the algorithm proceeds the set <math>\mathcal{S}</math> converges toward <math>\mathcal{H}_1</math> and the number of admissible <math>k_0</math>-tuples it contains declines. One can regard the cardinality of the difference between <math>\mathcal{S}</math> and <math>\mathcal{H}_1</math> as a measure of the "temperature" of a gradually cooling system, since the number of choices available to the algorithm declines as this cardinality is reduced (more precisely, one may consider the entropy of the possible sequence of tie-breaking choices available for a given <math>\mathcal{S}</math>).

=== Local optimizations ===

Let <math>\mathcal H = \{h_1,\ldots, h_{k_0}\}</math> be an admissible <math>k_0</math>-tuple with endpoints <math>h_1</math> and <math>h_{k_0}</math>, and let <math>\mathcal I</math> be the interval <math>[h_1,h_{k_0}]</math>. If there exists an integer <math>h\in\mathcal I</math> such that removing one of <math>\mathcal H</math>'s endpoints and inserting <math>h</math> yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, then call <math>\mathcal H</math> ''contractible'', and if not, say that <math>\mathcal H</math> non-contractible. Note that <math>\mathcal H'</math> necessarily has smaller diameter than <math>\mathcal H</math>. Any of the sieving methods described above may produce admissible <math>k_0</math>-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing <math>\mathcal H</math> by <math>\mathcal H'</math> if this test succeeds.

We can also ''shift'' <math>\mathcal H </math> to the left by removing its right end point <math>h_{k_0}</math> and replacing it with the greatest integer <math>h_0 < h_1</math> that yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, and we can similarly shift <math>\mathcal H</math> to the right. The diameter of <math>\mathcal H'</math> need not be less than <math>\mathcal H</math>, but if it is, it provides a useful replacement. More generally, by shifting <math>\mathcal H</math> repeatedly we can produce a sequence of admissible <math>k_0</math>-tuples that lie successively further to the left or right. In general the diameter of these tuples may grow as we do so, but it will also occasionally decline, and we may be able to find a shifted <math>\mathcal H'</math> with smaller diameter than <math>\mathcal H</math>.

----

A more sophisticated local optimization involves a process of ``adjustment" [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23766 proposed by Savitt].
Let <math>\mathcal H </math> be an admissible <math>k_0</math>-tuple.
For a prime <math>p</math> and an integer <math>a</math>, let <math>[a;p]</math> denote the residue class <math>a\bmod p</math>, i.e. the set of integers <math>\{ x : x = a \bmod p\}</math>.
Call <math>[a;p]</math> occupied if it contains an element of <math>\mathcal H </math>.

Suppose that <math>[a;p]</math> and <math>[b;q]</math> are occupied residue classes, for some distinct primes <math>p</math> and <math>q</math>, and that <math>[a';p]</math> and <math>[b';q]</math> are unoccupied.
Let <math>\mathcal U</math> be the intersection of <math>\mathcal H</math> with <math>[a;p] \cup [b;q]</math>, and let <math>\mathcal V</math> be a subset of the integers that lie in the intersection of the interval <math>I</math> containing <math>H</math> and the set <math>[a';p] \cup [b';q]</math> such that
the set <math>\mathcal H' </math> formed by removing the elements of <math>\mathcal U</math> from <math>\mathcal H </math> and adding the elements of <math>\mathcal V </math> is admissible.
A necessary (and often sufficient) condition for and integer <math>v</math> to lie in <math>\mathcal V</math> is that <math>v</math> must not lie in a residue class <math>[c;r]</math> that is the unique unoccupied residue class modulo <math>r</math> for any prime <math>r</math> other than <math>p</math> or <math>q</math>.

The admissible set <math>\mathcal H' </math> lies in the interval <math>\mathcal I</math> containing <math>\mathcal H</math>, so its diameter is no greater than that of <math>\mathcal H</math>, however its cardinality may differ. If it happens that <math>\mathcal H' </math> contains more elements than <math>\mathcal H </math>, then by eliminating points at either end of <math>\mathcal H' </math> we obtain an admissible <math>k_0</math>-tuple that is narrower than <math>\mathcal H</math> and may ``adjust" <math>\mathcal H </math> by replacing it with <math>\mathcal H' </math>.
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible <math>k_0</math>-tuples.

=== Further refinements ===

== Lower bounds ==

There is a substantial amount of literature on bounding the quantity <math>\pi(x+y)-\pi(x)</math>, the number of primes in a shifted interval <math>[x+1,x+y]</math>, where <math>x,y</math> are natural numbers. As a general rule, whenever a bound of the form

: <math> \pi(x+y) - \pi(x) \leq F(y) </math> (*)

is established for some function <math>F(y)</math> of <math>y</math>, the method of proof also gives a bound of the form

: <math> k_0 \leq F( H(k_0)+1 ).</math> (**)

Indeed, if one assumes the prime tuples conjecture, any admissible <math>k_0</math>-tuple of diameter <math>H</math> can be translated into an interval of the form <math>[x+1,x+H+1]</math> for some <math>x</math>. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for <math>x>y</math>, the set of primes between <math>x+1</math> and <math>x+y</math> is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

=== Brun-Titchmarsh inequality ===

The Brun-Titchmarsh theorem gives

: <math> \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}</math>

which then gives the lower bound

: <math> H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0</math>.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem [MV1973, Corollary 2], giving the more precise inequality

: <math> k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.</math>

=== First Montgomery-Vaughan large sieve inequality ===

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

: <math> k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2</math>

for any <math>Q > 1</math>, which is a parameter that one can optimise over (the optimal value is comparable to <math>H(k_0)^{1/2}</math>).

=== Second Montgomery-Vaughan large sieve inequality ===

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

: <math> k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}</math>

for any <math>z > 1</math>, which is a parameter similar to <math>Q</math> in the previous inequality, and <math>c</math> is an absolute constant. In the original paper of Montgomery and Vaughan, <math>c</math> was taken to be <math>3/2</math>; this was then reduced to <math>\sqrt{22}/\pi</math> [B1995, p.162] and then to <math>3.2/\pi</math> [M1978]. It is conjectured that <math>c</math> can be taken to in fact be <math>1</math>.

== Benchmarks ==

Efforts to fill in the blank fields in this table are very welcome.

{| border=1
|-
!<math>k_0</math>!!3,500,000!! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 10,719 !! 5,000 !! 2,000 !! 1,000 !! 672
|-
! Upper bounds
|-
|Zhang sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 59,093,364]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411932.txt 411,932]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23282_268536.txt 268,536]
| [http://math.mit.edu/~drew/admissible_10719.txt 114,806]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
| [http://math.mit.edu/~drew/admissible_2000_17766.txt 17,766]
| [http://math.mit.edu/~drew/admissible_1000_8212.txt 8,212]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
|-
|Hensley-Richards sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2422558.txt 2,422,558]
| [http://math.mit.edu/~drew/admissible_34429_402790.txt 402,790]
| [http://math.mit.edu/~drew/admissible_26024_297454.txt 297,454]
| [http://math.mit.edu/~drew/admissible_23283_262794.txt 262,794]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
| [http://math.mit.edu/~drew/admissible_2000_17726.txt 17,726]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
|-
|Asymmetric Hensley-Richards
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23636 401,700]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23748 297,076]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23826 262,566]
| [http://math.mit.edu/~drew/admissible_10719_112646.txt 112,646]
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
|
|
|
|-
|Schinzel sieve
|
|
|
|
|
|
|
|
|
|
|-
|greedy-Schinzel sieve
|
|
|
|
|
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
| [http://math.mit.edu/~drew/admissible_2000_17054.txt 17,054]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5.030]
|-
|Best known tuple
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2345896.txt 2,345,896]
| [http://math.mit.edu/~drew/admissible_34429_386532.txt 386,532]
| [http://math.mit.edu/~drew/admissible_26024_285210.txt 285,210]
| [http://math.mit.edu/~drew/admissible_23283_252804.txt 252,804]
| [http://math.mit.edu/~drew/admissible_10719_108462.txt 108,462]
| [http://math.mit.edu/~drew/admissible_5000_46824.txt 46,824]
| [http://math.mit.edu/~drew/admissible_2000_16984.txt 16,984*], 16978
| [http://math.mit.edu/~drew/admissible_1000_7808.txt 7,808*], 7802
| [http://math.mit.edu/~drew/admissible_672_5010.txt 5,010*], 4998
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 2,372,232
| 394,096
| 290,604
| 257,405
| 110,119
| 47,586
| 17,202
| 7,907
| 5,046
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,642]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,924]
|
|
|
|
|
|
|-
|MV with <math>c=3.2/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,322]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,719]
|
|
|
|
|
|
|-
|MV with <math>c=\sqrt{22}/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 227,078]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,860]
|
|
|
|
|
|
|-
|Second Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 226,987]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,793]
|
|
|
|
|
|
|-
|Brun-Titchmarsh
| 30,137,225
| 127,083
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 211,046]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555]
| 137,756
| 58,863
| 25,351
| 9,118
| 4,167
| 2,648
|-
|First Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711]
|
|
|
|
|
|
|}

<nowiki>*</nowiki> For the best known tuples with <math>k_0 = 2000,1000,672</math> we have listed two values: the larger value is the the width of the best known tuples that have been found by the methods that gave the entries for larger values of <math>k_0</math>; the smaller value is the width of literally the best known tuples (due to Engelsma). For 3000- and 4000-tuples, Engelsma has found widths of 26622 and 36622 respectively.

Finding narrow admissible tuples

2013-06-11T18:11:31Z

Savitt: /* Benchmarks */

For any natural number <math>k_0</math>, an ''admissible <math>k_0</math>-tuple'' is a finite set <math>{\mathcal H}</math> of integers of cardinality <math>k_0</math> which avoids at least one residue class modulo <math>p</math> for each prime <math>p</math>. (Note that one only needs to check those primes <math>p</math> of size at most <math>k_0</math>, so this is a finitely checkable condition.) Let <math>H(k_0)</math> denote the minimal diameter <math>\max {\mathcal H} - \min {\mathcal H}</math> of an admissible <math>k_0</math>-tuple. As part of the [[Bounded gaps between primes|Polymath8]] project, we would like to find as good an upper bound on <math>H(k_0)</math> as possible for given values of <math>k_0</math>. To a lesser extent, we would also be interested in lower bounds on this quantity. There is some scattered numerical evidence that the optimal value of H is roughly of size <math>k_0 \log k_0 + k_0</math> for <math>k_0</math> in the range of interest.

== Upper bounds ==

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo <math>p</math> from an interval for a lot of primes <math>p</math>. Examples of sieves, in roughly increasing order of efficiency, are listed below.

=== Zhang sieve ===

The Zhang sieve uses the tuple

:<math>{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}</math>

where <math>m</math> is taken to optimize the diameter <math>p_{m+k_0}-p_{m+1}</math> while staying admissible (in practice, this basically means making <math>m</math> as small as possible). Certainly any <math>m</math> with <math>p_{m+1} > k_0</math> works, but this is not optimal. Applying the prime number theorem then gives the upper bound <math>H \leq (1+o(1)) k_0\log k_0</math>.

=== Hensley-Richards sieve ===

The Hensley-Richards sieve [HR1973], [HR1973b], [R1974] uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1}\}</math>

where m is again optimised to minimize the diameter while staying admissible.

=== Asymmetric Hensley-Richards sieve ===

The asymmetric Hensley-Richard sieve uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1+i}\}</math>

where <math>i</math> is an integer and <math>i,m</math> are optimised to minimize the diameter while staying admissible.

=== Schinzel sieve ===
Given <math>0<y<z</math>, the Schinzel sieve (discussed in [HR1973], [CJ2001] first sieves by <math>1\bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y . For a given choice of <math>y</math>, the parameter <math>z</math> is minimized subject to ensuring that the first <math>k_0</math> survivors (after the first) form an admissible sequence <math>\mathcal{H}</math>, so the only free parameter is <math>y</math>, which is chosen to minimize the diameter of <math>\mathcal{H}</math>. The case <math>y=1</math> corresponds to a sieve of Eratosthenes, which will typically yield the same sequence as Zhang with the minimal (but not necessarily optimal) value of <math>m</math> that yields an admissible <math>k_0</math>-tuple. As originally proposed, the Schinzel sieve works over the positive integers, but one can instead sieve intervals centered about the origin, or asymmetric intervals, as with the Hensley-Richards sieve.

=== Greedy sieve ===
For a given interval (e.g., <math>[1,x]</math>, <math>[-x,x]</math>, or asymmetric <math>[x_0,x_1]</math>) one sieves a single residue class <math>a \bmod p</math> for increasing primes <math>p=2,3,5,\ldots</math>, with <math>a</math> chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize <math>a\in[0,p-1]</math>, maximize <math>a\in [0,p-1]</math>, minimize <math>|a-\lfloor p/2\rfloor|</math>, or randomly. If not all residue classes modulo <math>p</math> are occupied by survivors, then <math>a</math> will be chosen so that no survivors are sieved.
This necessarily occurs once <math>p</math> exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest <math>k_0</math>-tuple <math>{\mathcal H}</math> among the survivors (if there are fewer than <math>k_0</math> survivors, retry with a wider interval).

=== Greedy-Schinzel sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a Schinzel sieve with <math>y=2</math> and <math>z=\sqrt{x_1-x_0}</math> and then continuing in a greedy fashion
This method was proposed by Sutherland and originally referred to as a [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 "greedy-greedy"] approach. This nomenclature arose from the fact that one optimization that can be applied to the standard Schinzel sieve on a given interval is to "greedily" avoid sieving modulo primes where the set of survivors is already admissible (this may occur for primes less than the minimal value of <math>z</math> that yields <math>k_0</math>-survivors), while a second optimization is to use a value of <math>z</math> that is intentionally smaller than necessary and switch to greedy sieving for primes greater than <math>z</math>. With the choice <math>z=\sqrt{x_1-x_0}</math>, unless the initial interval is much larger than necessary, all primes up to <math>z</math> will require a residue class to be sieved and the first "greedy" seldom applies.

=== Seeded greedy sieve ===
Given an initial sequence <math>{\mathcal S}</math> that is known to contain an admissible <math>k_0</math>-tuple, one can apply greedy sieving to the minimal interval containing <math>{\mathcal S}</math> until an admissible sequence of survivors remains, and then choose the narrowest <math>k_0</math>=tuple it contains. The sieving methods above can be viewed as the special case where <math>{\mathcal S}</math> is the set of integers in some interval. The main difference is that the choice of <math>{\mathcal S}</math> affects when ties occur and how they are broken with greedy sieving.
One approach is to take <math>{\mathcal S}</math> to be the union of two <math>k_0</math>-tuples that lie in roughly the same interval (see Iterated merging) below.

=== Iterated merging ===
Given an admissible <math>k_0</math>-tuple <math>\mathcal{H}_1</math>, one can attempt to improve it using an iterated merging approach [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 suggested by Castryck]. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible <math>k_0</math>-tuple <math>\mathcal{H}_2</math> in roughly the same interval as <math>\mathcal{H}_1</math>, then performs a randomized greedy sieve using the seed set <math>\mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2</math> to obtain an admissible <math>k_0</math>-tuple <math>\mathcal{H}_3</math>. If <math>\mathcal{H}_3</math> is narrower than <math>\mathcal{H}_2</math>, replace <math>\mathcal{H}_2</math> with <math>\mathcal{H}_3</math>, otherwise try again with a new <math>\mathcal{H}_3</math>.
Eventually the diameter of <math>\mathcal{H}_2</math> will become less than or equal to that of <math>\mathcal{H}_1</math>.
As long as <math>\mathcal{H}_1\ne \mathcal{H}_2</math>, one can continue to attempt to improve <math>\mathcal{H}_2</math>, but in practice one stops after some number of retries.

As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23733 described by Sutherland], one can then replace <math>\mathcal{H}_1</math> with <math>\mathcal{H}_2</math> and begin the process anew, yielding a randomized algorithm that can be run indefinitely. Key parameters to this algorithm are the choice of the interval used when constructing <math>\mathcal{H}_2</math>, which is typically made wider than the minimal interval containing <math>\mathcal{H}_1</math> by a small factor <math>\delta</math> on each side (Sutherland suggests <math>\delta = 0.0025</math>), and the number of failed attempts allowed while attempting to impove <math>\mathcal{H}_2</math>.

Eventually this process will tend to converge to particular <math>\mathcal{H}_1</math> that it cannot improve (or more generally, a set of similar <math>\mathcal{H}_1</math>'s with the same diameter). Interleaving iterated merging with the local optimizations described below often allows the algorithm to make further progress.

----

Iterated merging can be viewed as a form of simulated annealing. The set <math>\mathcal{S}</math> initially contains at least two admissible <math>k_0</math>-tuples (typically many more), and as the algorithm proceeds the set <math>\mathcal{S}</math> converges toward <math>\mathcal{H}_1</math> and the number of admissible <math>k_0</math>-tuples it contains declines. One can regard the cardinality of the difference between <math>\mathcal{S}</math> and <math>\mathcal{H}_1</math> as a measure of the "temperature" of a gradually cooling system, since the number of choices available to the algorithm declines as this cardinality is reduced (more precisely, one may consider the entropy of the possible sequence of tie-breaking choices available for a given <math>\mathcal{S}</math>).

=== Local optimizations ===

Let <math>\mathcal H = \{h_1,\ldots, h_{k_0}\}</math> be an admissible <math>k_0</math>-tuple with endpoints <math>h_1</math> and <math>h_{k_0}</math>, and let <math>\mathcal I</math> be the interval <math>[h_1,h_{k_0}]</math>. If there exists an integer <math>h\in\mathcal I</math> such that removing one of <math>\mathcal H</math>'s endpoints and inserting <math>h</math> yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, then call <math>\mathcal H</math> ''contractible'', and if not, say that <math>\mathcal H</math> non-contractible. Note that <math>\mathcal H'</math> necessarily has smaller diameter than <math>\mathcal H</math>. Any of the sieving methods described above may produce admissible <math>k_0</math>-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing <math>\mathcal H</math> by <math>\mathcal H'</math> if this test succeeds.

We can also ''shift'' <math>\mathcal H </math> to the left by removing its right end point <math>h_{k_0}</math> and replacing it with the greatest integer <math>h_0 < h_1</math> that yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, and we can similarly shift <math>\mathcal H</math> to the right. The diameter of <math>\mathcal H'</math> need not be less than <math>\mathcal H</math>, but if it is, it provides a useful replacement. More generally, by shifting <math>\mathcal H</math> repeatedly we can produce a sequence of admissible <math>k_0</math>-tuples that lie successively further to the left or right. In general the diameter of these tuples may grow as we do so, but it will also occasionally decline, and we may be able to find a shifted <math>\mathcal H'</math> with smaller diameter than <math>\mathcal H</math>.

----

A more sophisticated local optimization involves a process of ``adjustment" [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23766 proposed by Savitt].
Let <math>\mathcal H </math> be an admissible <math>k_0</math>-tuple.
For a prime <math>p</math> and an integer <math>a</math>, let <math>[a;p]</math> denote the residue class <math>a\bmod p</math>, i.e. the set of integers <math>\{ x : x = a \bmod p\}</math>.
Call <math>[a;p]</math> occupied if it contains an element of <math>\mathcal H </math>.

Suppose that <math>[a;p]</math> and <math>[b;q]</math> are occupied residue classes, for some distinct primes <math>p</math> and <math>q</math>, and that <math>[a';p]</math> and <math>[b';q]</math> are unoccupied.
Let <math>\mathcal U</math> be the intersection of <math>\mathcal H</math> with <math>[a;p] \cup [b;q]</math>, and let <math>\mathcal V</math> be a subset of the integers that lie in the intersection of the interval <math>I</math> containing <math>H</math> and the set <math>[a';p] \cup [b';q]</math> such that
the set <math>\mathcal H' </math> formed by removing the elements of <math>\mathcal U</math> from <math>\mathcal H </math> and adding the elements of <math>\mathcal V </math> is admissible.
A necessary (and often sufficient) condition for and integer <math>v</math> to lie in <math>\mathcal V</math> is that <math>v</math> must not lie in a residue class <math>[c;r]</math> that is the unique unoccupied residue class modulo <math>r</math> for any prime <math>r</math> other than <math>p</math> or <math>q</math>.

The admissible set <math>\mathcal H' </math> lies in the interval <math>\mathcal I</math> containing <math>\mathcal H</math>, so its diameter is no greater than that of <math>\mathcal H</math>, however its cardinality may differ. If it happens that <math>\mathcal H' </math> contains more elements than <math>\mathcal H </math>, then by eliminating points at either end of <math>\mathcal H' </math> we obtain an admissible <math>k_0</math>-tuple that is narrower than <math>\mathcal H</math> and may ``adjust" <math>\mathcal H </math> by replacing it with <math>\mathcal H' </math>.
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible <math>k_0</math>-tuples.

=== Further refinements ===

== Lower bounds ==

There is a substantial amount of literature on bounding the quantity <math>\pi(x+y)-\pi(x)</math>, the number of primes in a shifted interval <math>[x+1,x+y]</math>, where <math>x,y</math> are natural numbers. As a general rule, whenever a bound of the form

: <math> \pi(x+y) - \pi(x) \leq F(y) </math> (*)

is established for some function <math>F(y)</math> of <math>y</math>, the method of proof also gives a bound of the form

: <math> k_0 \leq F( H(k_0)+1 ).</math> (**)

Indeed, if one assumes the prime tuples conjecture, any admissible <math>k_0</math>-tuple of diameter <math>H</math> can be translated into an interval of the form <math>[x+1,x+H+1]</math> for some <math>x</math>. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for <math>x>y</math>, the set of primes between <math>x+1</math> and <math>x+y</math> is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

=== Brun-Titchmarsh inequality ===

The Brun-Titchmarsh theorem gives

: <math> \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}</math>

which then gives the lower bound

: <math> H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0</math>.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem [MV1973, Corollary 2], giving the more precise inequality

: <math> k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.</math>

=== First Montgomery-Vaughan large sieve inequality ===

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

: <math> k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2</math>

for any <math>Q > 1</math>, which is a parameter that one can optimise over (the optimal value is comparable to <math>H(k_0)^{1/2}</math>).

=== Second Montgomery-Vaughan large sieve inequality ===

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

: <math> k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}</math>

for any <math>z > 1</math>, which is a parameter similar to <math>Q</math> in the previous inequality, and <math>c</math> is an absolute constant. In the original paper of Montgomery and Vaughan, <math>c</math> was taken to be <math>3/2</math>; this was then reduced to <math>\sqrt{22}/\pi</math> [B1995, p.162] and then to <math>3.2/\pi</math> [M1978]. It is conjectured that <math>c</math> can be taken to in fact be <math>1</math>.

== Benchmarks ==

Efforts to fill in the blank fields in this table are very welcome.

{| border=1
|-
!<math>k_0</math>!!3,500,000!! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 10,719 !! 5,000 !! 2,000 !! 1,000 !! 672
|-
! Upper bounds
|-
|Zhang sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 59,093,364]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411932.txt 411,932]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23282_268536.txt 268,536]
| [http://math.mit.edu/~drew/admissible_10719.txt 114,806]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
| [http://math.mit.edu/~drew/admissible_2000_17766.txt 17,766]
| [http://math.mit.edu/~drew/admissible_1000_8212.txt 8,212]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
|-
|Hensley-Richards sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2422558.txt 2,422,558]
| [http://math.mit.edu/~drew/admissible_34429_402790.txt 402,790]
| [http://math.mit.edu/~drew/admissible_26024_297454.txt 297,454]
| [http://math.mit.edu/~drew/admissible_23283_262794.txt 262,794]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
| [http://math.mit.edu/~drew/admissible_2000_17726.txt 17,726]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
|-
|Asymmetric Hensley-Richards
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23636 401,700]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23748 297,076]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23826 262,566]
| [http://math.mit.edu/~drew/admissible_10719_112646.txt 112,646]
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
|
|
|
|-
|Schinzel sieve
|
|
|
|
|
|
|
|
|
|
|-
|greedy-Schinzel sieve
|
|
|
|
|
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
| [http://math.mit.edu/~drew/admissible_2000_17054.txt 17,054]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5.030]
|-
|Best known tuple
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2345896.txt 2,345,896]
| [http://math.mit.edu/~drew/admissible_34429_386532.txt 386,532]
| [http://math.mit.edu/~drew/admissible_26024_285210.txt 285,210]
| [http://math.mit.edu/~drew/admissible_23283_252804.txt 252,804]
| [http://math.mit.edu/~drew/admissible_10719_108462.txt 108,462]
| [http://math.mit.edu/~drew/admissible_5000_46824.txt 46,824]
| [http://math.mit.edu/~drew/admissible_2000_16984.txt 16,984]
| [http://math.mit.edu/~drew/admissible_1000_7808.txt 7,808]
| [http://math.mit.edu/~drew/admissible_672_5010.txt 5,010*], 4998
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 2,372,232
| 394,096
| 290,604
| 257,405
| 110,119
| 47,586
| 17,202
| 7,907
| 5,046
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,642]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,924]
|
|
|
|
|
|
|-
|MV with <math>c=3.2/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,322]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,719]
|
|
|
|
|
|
|-
|MV with <math>c=\sqrt{22}/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 227,078]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,860]
|
|
|
|
|
|
|-
|Second Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 226,987]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,793]
|
|
|
|
|
|
|-
|Brun-Titchmarsh
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 211,046]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555]
|
|
|
|
|
|
|-
|First Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711]
|
|
|
|
|
|
|}

<nowiki>*</nowiki> The best known tuple for <math>k_0 = 672</math> has width 4998, due to Engelsma; 5010 is the width of the best known tuple that was found by the methods that yielded the entries to the left of 5010 in the "best known tuple" row.

Finding narrow admissible tuples

2013-06-11T17:27:42Z

Savitt: /* Benchmarks */

For any natural number <math>k_0</math>, an ''admissible <math>k_0</math>-tuple'' is a finite set <math>{\mathcal H}</math> of integers of cardinality <math>k_0</math> which avoids at least one residue class modulo <math>p</math> for each prime <math>p</math>. (Note that one only needs to check those primes <math>p</math> of size at most <math>k_0</math>, so this is a finitely checkable condition.) Let <math>H(k_0)</math> denote the minimal diameter <math>\max {\mathcal H} - \min {\mathcal H}</math> of an admissible <math>k_0</math>-tuple. As part of the [[Bounded gaps between primes|Polymath8]] project, we would like to find as good an upper bound on <math>H(k_0)</math> as possible for given values of <math>k_0</math>. To a lesser extent, we would also be interested in lower bounds on this quantity. There is some scattered numerical evidence that the optimal value of H is roughly of size <math>k_0 \log k_0 + k_0</math> for <math>k_0</math> in the range of interest.

== Upper bounds ==

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo <math>p</math> from an interval for a lot of primes <math>p</math>. Examples of sieves, in roughly increasing order of efficiency, are listed below.

=== Zhang sieve ===

The Zhang sieve uses the tuple

:<math>{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}</math>

where <math>m</math> is taken to optimize the diameter <math>p_{m+k_0}-p_{m+1}</math> while staying admissible (in practice, this basically means making <math>m</math> as small as possible). Certainly any <math>m</math> with <math>p_{m+1} > k_0</math> works, but this is not optimal. Applying the prime number theorem then gives the upper bound <math>H \leq (1+o(1)) k_0\log k_0</math>.

=== Hensley-Richards sieve ===

The Hensley-Richards sieve [HR1973], [HR1973b], [R1974] uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1}\}</math>

where m is again optimised to minimize the diameter while staying admissible.

=== Asymmetric Hensley-Richards sieve ===

The asymmetric Hensley-Richard sieve uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1+i}\}</math>

where <math>i</math> is an integer and <math>i,m</math> are optimised to minimize the diameter while staying admissible.

=== Schinzel sieve ===
Given <math>0<y<z</math>, the Schinzel sieve (discussed in [HR1973], [CJ2001] first sieves by <math>1\bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y . For a given choice of <math>y</math>, the parameter <math>z</math> is minimized subject to ensuring that the first <math>k_0</math> survivors (after the first) form an admissible sequence <math>\mathcal{H}</math>, so the only free parameter is <math>y</math>, which is chosen to minimize the diameter of <math>\mathcal{H}</math>. The case <math>y=1</math> corresponds to a sieve of Eratosthenes, which will typically yield the same sequence as Zhang with the minimal (but not necessarily optimal) value of <math>m</math> that yields an admissible <math>k_0</math>-tuple. As originally proposed, the Schinzel sieve works over the positive integers, but one can instead sieve intervals centered about the origin, or asymmetric intervals, as with the Hensley-Richards sieve.

=== Greedy sieve ===
For a given interval (e.g., <math>[1,x]</math>, <math>[-x,x]</math>, or asymmetric <math>[x_0,x_1]</math>) one sieves a single residue class <math>a \bmod p</math> for increasing primes <math>p=2,3,5,\ldots</math>, with <math>a</math> chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize <math>a\in[0,p-1]</math>, maximize <math>a\in [0,p-1]</math>, minimize <math>|a-\lfloor p/2\rfloor|</math>, or randomly. If not all residue classes modulo <math>p</math> are occupied by survivors, then <math>a</math> will be chosen so that no survivors are sieved.
This necessarily occurs once <math>p</math> exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest <math>k_0</math>-tuple <math>{\mathcal H}</math> among the survivors (if there are fewer than <math>k_0</math> survivors, retry with a wider interval).

=== Greedy-Schinzel sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a Schinzel sieve with <math>y=2</math> and <math>z=\sqrt{x_1-x_0}</math> and then continuing in a greedy fashion
This method was proposed by Sutherland and originally referred to as a [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 "greedy-greedy"] approach. This nomenclature arose from the fact that one optimization that can be applied to the standard Schinzel sieve on a given interval is to "greedily" avoid sieving modulo primes where the set of survivors is already admissible (this may occur for primes less than the minimal value of <math>z</math> that yields <math>k_0</math>-survivors), while a second optimization is to use a value of <math>z</math> that is intentionally smaller than necessary and switch to greedy sieving for primes greater than <math>z</math>. With the choice <math>z=\sqrt{x_1-x_0}</math>, unless the initial interval is much larger than necessary, all primes up to <math>z</math> will require a residue class to be sieved and the first "greedy" seldom applies.

=== Seeded greedy sieve ===
Given an initial sequence <math>{\mathcal S}</math> that is known to contain an admissible <math>k_0</math>-tuple, one can apply greedy sieving to the minimal interval containing <math>{\mathcal S}</math> until an admissible sequence of survivors remains, and then choose the narrowest <math>k_0</math>=tuple it contains. The sieving methods above can be viewed as the special case where <math>{\mathcal S}</math> is the set of integers in some interval. The main difference is that the choice of <math>{\mathcal S}</math> affects when ties occur and how they are broken with greedy sieving.
One approach is to take <math>{\mathcal S}</math> to be the union of two <math>k_0</math>-tuples that lie in roughly the same interval (see Iterated merging) below.

=== Iterated merging ===
Given an admissible <math>k_0</math>-tuple <math>\mathcal{H}_1</math>, one can attempt to improve it using an iterated merging approach [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 suggested by Castryck]. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible <math>k_0</math>-tuple <math>\mathcal{H}_2</math> in roughly the same interval as <math>\mathcal{H}_1</math>, then performs a randomized greedy sieve using the seed set <math>\mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2</math> to obtain an admissible <math>k_0</math>-tuple <math>\mathcal{H}_3</math>. If <math>\mathcal{H}_3</math> is narrower than <math>\mathcal{H}_2</math>, replace <math>\mathcal{H}_2</math> with <math>\mathcal{H}_3</math>, otherwise try again with a new <math>\mathcal{H}_3</math>.
Eventually the diameter of <math>\mathcal{H}_2</math> will become less than or equal to that of <math>\mathcal{H}_1</math>.
As long as <math>\mathcal{H}_1\ne \mathcal{H}_2</math>, one can continue to attempt to improve <math>\mathcal{H}_2</math>, but in practice one stops after some number of retries.

As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23733 described by Sutherland], one can then replace <math>\mathcal{H}_1</math> with <math>\mathcal{H}_2</math> and begin the process anew, yielding a randomized algorithm that can be run indefinitely. Key parameters to this algorithm are the choice of the interval used when constructing <math>\mathcal{H}_2</math>, which is typically made wider than the minimal interval containing <math>\mathcal{H}_1</math> by a small factor <math>\delta</math> on each side (Sutherland suggests <math>\delta = 0.0025</math>), and the number of failed attempts allowed while attempting to impove <math>\mathcal{H}_2</math>.

Eventually this process will tend to converge to particular <math>\mathcal{H}_1</math> that it cannot improve (or more generally, a set of similar <math>\mathcal{H}_1</math>'s with the same diameter). Interleaving iterated merging with the local optimizations described below often allows the algorithm to make further progress.

----

Iterated merging can be viewed as a form of simulated annealing. The set <math>\mathcal{S}</math> initially contains at least two admissible <math>k_0</math>-tuples (typically many more), and as the algorithm proceeds the set <math>\mathcal{S}</math> converges toward <math>\mathcal{H}_1</math> and the number of admissible <math>k_0</math>-tuples it contains declines. One can regard the cardinality of the difference between <math>\mathcal{S}</math> and <math>\mathcal{H}_1</math> as a measure of the "temperature" of a gradually cooling system, since the number of choices available to the algorithm declines as this cardinality is reduced (more precisely, one may consider the entropy of the possible sequence of tie-breaking choices available for a given <math>\mathcal{S}</math>).

=== Local optimizations ===

Let <math>\mathcal H = \{h_1,\ldots, h_{k_0}\}</math> be an admissible <math>k_0</math>-tuple with endpoints <math>h_1</math> and <math>h_{k_0}</math>, and let <math>\mathcal I</math> be the interval <math>[h_1,h_{k_0}]</math>. If there exists an integer <math>h\in\mathcal I</math> such that removing one of <math>\mathcal H</math>'s endpoints and inserting <math>h</math> yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, then call <math>\mathcal H</math> ''contractible'', and if not, say that <math>\mathcal H</math> non-contractible. Note that <math>\mathcal H'</math> necessarily has smaller diameter than <math>\mathcal H</math>. Any of the sieving methods described above may produce admissible <math>k_0</math>-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing <math>\mathcal H</math> by <math>\mathcal H'</math> if this test succeeds.

We can also ''shift'' <math>\mathcal H </math> to the left by removing its right end point <math>h_{k_0}</math> and replacing it with the greatest integer <math>h_0 < h_1</math> that yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, and we can similarly shift <math>\mathcal H</math> to the right. The diameter of <math>\mathcal H'</math> need not be less than <math>\mathcal H</math>, but if it is, it provides a useful replacement. More generally, by shifting <math>\mathcal H</math> repeatedly we can produce a sequence of admissible <math>k_0</math>-tuples that lie successively further to the left or right. In general the diameter of these tuples may grow as we do so, but it will also occasionally decline, and we may be able to find a shifted <math>\mathcal H'</math> with smaller diameter than <math>\mathcal H</math>.

----

A more sophisticated local optimization involves a process of ``adjustment" [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23766 proposed by Savitt].
Let <math>\mathcal H </math> be an admissible <math>k_0</math>-tuple.
For a prime <math>p</math> and an integer <math>a</math>, let <math>[a;p]</math> denote the residue class <math>a\bmod p</math>, i.e. the set of integers <math>\{ x : x = a \bmod p\}</math>.
Call <math>[a;p]</math> occupied if it contains an element of <math>\mathcal H </math>.

Suppose that <math>[a;p]</math> and <math>[b;q]</math> are occupied residue classes, for some distinct primes <math>p</math> and <math>q</math>, and that <math>[a';p]</math> and <math>[b';q]</math> are unoccupied.
Let <math>\mathcal U</math> be the intersection of <math>\mathcal H</math> with <math>[a;p] \cup [b;q]</math>, and let <math>\mathcal V</math> be a subset of the integers that lie in the intersection of the interval <math>I</math> containing <math>H</math> and the set <math>[a';p] \cup [b';q]</math> such that
the set <math>\mathcal H' </math> formed by removing the elements of <math>\mathcal U</math> from <math>\mathcal H </math> and adding the elements of <math>\mathcal V </math> is admissible.
A necessary (and often sufficient) condition for and integer <math>v</math> to lie in <math>\mathcal V</math> is that <math>v</math> must not lie in a residue class <math>[c;r]</math> that is the unique unoccupied residue class modulo <math>r</math> for any prime <math>r</math> other than <math>p</math> or <math>q</math>.

The admissible set <math>\mathcal H' </math> lies in the interval <math>\mathcal I</math> containing <math>\mathcal H</math>, so its diameter is no greater than that of <math>\mathcal H</math>, however its cardinality may differ. If it happens that <math>\mathcal H' </math> contains more elements than <math>\mathcal H </math>, then by eliminating points at either end of <math>\mathcal H' </math> we obtain an admissible <math>k_0</math>-tuple that is narrower than <math>\mathcal H</math> and may ``adjust" <math>\mathcal H </math> by replacing it with <math>\mathcal H' </math>.
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible <math>k_0</math>-tuples.

=== Further refinements ===

== Lower bounds ==

There is a substantial amount of literature on bounding the quantity <math>\pi(x+y)-\pi(x)</math>, the number of primes in a shifted interval <math>[x+1,x+y]</math>, where <math>x,y</math> are natural numbers. As a general rule, whenever a bound of the form

: <math> \pi(x+y) - \pi(x) \leq F(y) </math> (*)

is established for some function <math>F(y)</math> of <math>y</math>, the method of proof also gives a bound of the form

: <math> k_0 \leq F( H(k_0)+1 ).</math> (**)

Indeed, if one assumes the prime tuples conjecture, any admissible <math>k_0</math>-tuple of diameter <math>H</math> can be translated into an interval of the form <math>[x+1,x+H+1]</math> for some <math>x</math>. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for <math>x>y</math>, the set of primes between <math>x+1</math> and <math>x+y</math> is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

=== Brun-Titchmarsh inequality ===

The Brun-Titchmarsh theorem gives

: <math> \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}</math>

which then gives the lower bound

: <math> H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0</math>.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem [MV1973, Corollary 2], giving the more precise inequality

: <math> k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.</math>

=== First Montgomery-Vaughan large sieve inequality ===

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

: <math> k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2</math>

for any <math>Q > 1</math>, which is a parameter that one can optimise over (the optimal value is comparable to <math>H(k_0)^{1/2}</math>).

=== Second Montgomery-Vaughan large sieve inequality ===

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

: <math> k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}</math>

for any <math>z > 1</math>, which is a parameter similar to <math>Q</math> in the previous inequality, and <math>c</math> is an absolute constant. In the original paper of Montgomery and Vaughan, <math>c</math> was taken to be <math>3/2</math>; this was then reduced to <math>\sqrt{22}/\pi</math> [B1995, p.162] and then to <math>3.2/\pi</math> [M1978]. It is conjectured that <math>c</math> can be taken to in fact be <math>1</math>.

== Benchmarks ==

Efforts to fill in the blank fields in this table are very welcome.

{| border=1
|-
!<math>k_0</math>!!3,500,000!! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 10,719 !! 5,000 !! 2,000 !! 1,000 !! 672
|-
! Upper bounds
|-
|Zhang sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 59,093,364]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411932.txt 411,932]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23282_268536.txt 268,536]
| [http://math.mit.edu/~drew/admissible_10719.txt 114,806]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
| [http://math.mit.edu/~drew/admissible_2000_17766.txt 17,766]
| [http://math.mit.edu/~drew/admissible_1000_8212.txt 8,212]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
|-
|Hensley-Richards sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2422558.txt 2,422,558]
| [http://math.mit.edu/~drew/admissible_34429_402790.txt 402,790]
| [http://math.mit.edu/~drew/admissible_26024_297454.txt 297,454]
| [http://math.mit.edu/~drew/admissible_23283_262794.txt 262,794]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
| [http://math.mit.edu/~drew/admissible_2000_17726.txt 17,726]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
|-
|Asymmetric Hensley-Richards
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23636 401,700]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23748 297,076]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23826 262,566]
| [http://math.mit.edu/~drew/admissible_10719_112646.txt 112,646]
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
|
|
|
|-
|Schinzel sieve
|
|
|
|
|
|
|
|
|
|
|-
|greedy-Schinzel sieve
|
|
|
|
|
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
| [http://math.mit.edu/~drew/admissible_2000_17054.txt 17,054]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5.030]
|-
|Best known tuple
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2345896.txt 2,345,896]
| [http://math.mit.edu/~drew/admissible_34429_386532.txt 386,532]
| [http://math.mit.edu/~drew/admissible_26024_285210.txt 285,210]
| [http://math.mit.edu/~drew/admissible_23283_252804.txt 252,804]
| [http://math.mit.edu/~drew/admissible_10719_108462.txt 108,462]
| [http://math.mit.edu/~drew/admissible_5000_46824.txt 46,824]
| [http://math.mit.edu/~drew/admissible_2000_16984.txt 16,984]
| [http://math.mit.edu/~drew/admissible_1000_7808.txt 7,808]
| [http://math.mit.edu/~drew/admissible_672_5026.txt 5,026*], 4998
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 2,372,232
| 394,096
| 290,604
| 257,405
| 110,119
| 47,586
| 17,202
| 7,907
| 5,046
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,642]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,924]
|
|
|
|
|
|
|-
|MV with <math>c=3.2/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,322]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,719]
|
|
|
|
|
|
|-
|MV with <math>c=\sqrt{22}/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 227,078]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,860]
|
|
|
|
|
|
|-
|Second Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 226,987]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,793]
|
|
|
|
|
|
|-
|Brun-Titchmarsh
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 211,046]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555]
|
|
|
|
|
|
|-
|First Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711]
|
|
|
|
|
|
|}

* The best known tuple for <math>k_0 = 672</math> has width 4998, due to Engelsma; 5026 is the width of the best known tuple that was found by the methods that yielded the entries to the left of 5026 in the "best known tuple" row.

Finding narrow admissible tuples

2013-06-11T17:25:42Z

Savitt: /* Benchmarks */

For any natural number <math>k_0</math>, an ''admissible <math>k_0</math>-tuple'' is a finite set <math>{\mathcal H}</math> of integers of cardinality <math>k_0</math> which avoids at least one residue class modulo <math>p</math> for each prime <math>p</math>. (Note that one only needs to check those primes <math>p</math> of size at most <math>k_0</math>, so this is a finitely checkable condition.) Let <math>H(k_0)</math> denote the minimal diameter <math>\max {\mathcal H} - \min {\mathcal H}</math> of an admissible <math>k_0</math>-tuple. As part of the [[Bounded gaps between primes|Polymath8]] project, we would like to find as good an upper bound on <math>H(k_0)</math> as possible for given values of <math>k_0</math>. To a lesser extent, we would also be interested in lower bounds on this quantity. There is some scattered numerical evidence that the optimal value of H is roughly of size <math>k_0 \log k_0 + k_0</math> for <math>k_0</math> in the range of interest.

== Upper bounds ==

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo <math>p</math> from an interval for a lot of primes <math>p</math>. Examples of sieves, in roughly increasing order of efficiency, are listed below.

=== Zhang sieve ===

The Zhang sieve uses the tuple

:<math>{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}</math>

where <math>m</math> is taken to optimize the diameter <math>p_{m+k_0}-p_{m+1}</math> while staying admissible (in practice, this basically means making <math>m</math> as small as possible). Certainly any <math>m</math> with <math>p_{m+1} > k_0</math> works, but this is not optimal. Applying the prime number theorem then gives the upper bound <math>H \leq (1+o(1)) k_0\log k_0</math>.

=== Hensley-Richards sieve ===

The Hensley-Richards sieve [HR1973], [HR1973b], [R1974] uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1}\}</math>

where m is again optimised to minimize the diameter while staying admissible.

=== Asymmetric Hensley-Richards sieve ===

The asymmetric Hensley-Richard sieve uses the tuple

:<math>{\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0/2+1/2\rfloor-1+i}\}</math>

where <math>i</math> is an integer and <math>i,m</math> are optimised to minimize the diameter while staying admissible.

=== Schinzel sieve ===
Given <math>0<y<z</math>, the Schinzel sieve (discussed in [HR1973], [CJ2001] first sieves by <math>1\bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y . For a given choice of <math>y</math>, the parameter <math>z</math> is minimized subject to ensuring that the first <math>k_0</math> survivors (after the first) form an admissible sequence <math>\mathcal{H}</math>, so the only free parameter is <math>y</math>, which is chosen to minimize the diameter of <math>\mathcal{H}</math>. The case <math>y=1</math> corresponds to a sieve of Eratosthenes, which will typically yield the same sequence as Zhang with the minimal (but not necessarily optimal) value of <math>m</math> that yields an admissible <math>k_0</math>-tuple. As originally proposed, the Schinzel sieve works over the positive integers, but one can instead sieve intervals centered about the origin, or asymmetric intervals, as with the Hensley-Richards sieve.

=== Greedy sieve ===
For a given interval (e.g., <math>[1,x]</math>, <math>[-x,x]</math>, or asymmetric <math>[x_0,x_1]</math>) one sieves a single residue class <math>a \bmod p</math> for increasing primes <math>p=2,3,5,\ldots</math>, with <math>a</math> chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize <math>a\in[0,p-1]</math>, maximize <math>a\in [0,p-1]</math>, minimize <math>|a-\lfloor p/2\rfloor|</math>, or randomly. If not all residue classes modulo <math>p</math> are occupied by survivors, then <math>a</math> will be chosen so that no survivors are sieved.
This necessarily occurs once <math>p</math> exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest <math>k_0</math>-tuple <math>{\mathcal H}</math> among the survivors (if there are fewer than <math>k_0</math> survivors, retry with a wider interval).

=== Greedy-Schinzel sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a Schinzel sieve with <math>y=2</math> and <math>z=\sqrt{x_1-x_0}</math> and then continuing in a greedy fashion
This method was proposed by Sutherland and originally referred to as a [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 "greedy-greedy"] approach. This nomenclature arose from the fact that one optimization that can be applied to the standard Schinzel sieve on a given interval is to "greedily" avoid sieving modulo primes where the set of survivors is already admissible (this may occur for primes less than the minimal value of <math>z</math> that yields <math>k_0</math>-survivors), while a second optimization is to use a value of <math>z</math> that is intentionally smaller than necessary and switch to greedy sieving for primes greater than <math>z</math>. With the choice <math>z=\sqrt{x_1-x_0}</math>, unless the initial interval is much larger than necessary, all primes up to <math>z</math> will require a residue class to be sieved and the first "greedy" seldom applies.

=== Seeded greedy sieve ===
Given an initial sequence <math>{\mathcal S}</math> that is known to contain an admissible <math>k_0</math>-tuple, one can apply greedy sieving to the minimal interval containing <math>{\mathcal S}</math> until an admissible sequence of survivors remains, and then choose the narrowest <math>k_0</math>=tuple it contains. The sieving methods above can be viewed as the special case where <math>{\mathcal S}</math> is the set of integers in some interval. The main difference is that the choice of <math>{\mathcal S}</math> affects when ties occur and how they are broken with greedy sieving.
One approach is to take <math>{\mathcal S}</math> to be the union of two <math>k_0</math>-tuples that lie in roughly the same interval (see Iterated merging) below.

=== Iterated merging ===
Given an admissible <math>k_0</math>-tuple <math>\mathcal{H}_1</math>, one can attempt to improve it using an iterated merging approach [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 suggested by Castryck]. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible <math>k_0</math>-tuple <math>\mathcal{H}_2</math> in roughly the same interval as <math>\mathcal{H}_1</math>, then performs a randomized greedy sieve using the seed set <math>\mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2</math> to obtain an admissible <math>k_0</math>-tuple <math>\mathcal{H}_3</math>. If <math>\mathcal{H}_3</math> is narrower than <math>\mathcal{H}_2</math>, replace <math>\mathcal{H}_2</math> with <math>\mathcal{H}_3</math>, otherwise try again with a new <math>\mathcal{H}_3</math>.
Eventually the diameter of <math>\mathcal{H}_2</math> will become less than or equal to that of <math>\mathcal{H}_1</math>.
As long as <math>\mathcal{H}_1\ne \mathcal{H}_2</math>, one can continue to attempt to improve <math>\mathcal{H}_2</math>, but in practice one stops after some number of retries.

As [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23733 described by Sutherland], one can then replace <math>\mathcal{H}_1</math> with <math>\mathcal{H}_2</math> and begin the process anew, yielding a randomized algorithm that can be run indefinitely. Key parameters to this algorithm are the choice of the interval used when constructing <math>\mathcal{H}_2</math>, which is typically made wider than the minimal interval containing <math>\mathcal{H}_1</math> by a small factor <math>\delta</math> on each side (Sutherland suggests <math>\delta = 0.0025</math>), and the number of failed attempts allowed while attempting to impove <math>\mathcal{H}_2</math>.

Eventually this process will tend to converge to particular <math>\mathcal{H}_1</math> that it cannot improve (or more generally, a set of similar <math>\mathcal{H}_1</math>'s with the same diameter). Interleaving iterated merging with the local optimizations described below often allows the algorithm to make further progress.

----

Iterated merging can be viewed as a form of simulated annealing. The set <math>\mathcal{S}</math> initially contains at least two admissible <math>k_0</math>-tuples (typically many more), and as the algorithm proceeds the set <math>\mathcal{S}</math> converges toward <math>\mathcal{H}_1</math> and the number of admissible <math>k_0</math>-tuples it contains declines. One can regard the cardinality of the difference between <math>\mathcal{S}</math> and <math>\mathcal{H}_1</math> as a measure of the "temperature" of a gradually cooling system, since the number of choices available to the algorithm declines as this cardinality is reduced (more precisely, one may consider the entropy of the possible sequence of tie-breaking choices available for a given <math>\mathcal{S}</math>).

=== Local optimizations ===

Let <math>\mathcal H = \{h_1,\ldots, h_{k_0}\}</math> be an admissible <math>k_0</math>-tuple with endpoints <math>h_1</math> and <math>h_{k_0}</math>, and let <math>\mathcal I</math> be the interval <math>[h_1,h_{k_0}]</math>. If there exists an integer <math>h\in\mathcal I</math> such that removing one of <math>\mathcal H</math>'s endpoints and inserting <math>h</math> yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, then call <math>\mathcal H</math> ''contractible'', and if not, say that <math>\mathcal H</math> non-contractible. Note that <math>\mathcal H'</math> necessarily has smaller diameter than <math>\mathcal H</math>. Any of the sieving methods described above may produce admissible <math>k_0</math>-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing <math>\mathcal H</math> by <math>\mathcal H'</math> if this test succeeds.

We can also ''shift'' <math>\mathcal H </math> to the left by removing its right end point <math>h_{k_0}</math> and replacing it with the greatest integer <math>h_0 < h_1</math> that yields an admissible <math>k_0</math>-tuple <math>\mathcal H'</math>, and we can similarly shift <math>\mathcal H</math> to the right. The diameter of <math>\mathcal H'</math> need not be less than <math>\mathcal H</math>, but if it is, it provides a useful replacement. More generally, by shifting <math>\mathcal H</math> repeatedly we can produce a sequence of admissible <math>k_0</math>-tuples that lie successively further to the left or right. In general the diameter of these tuples may grow as we do so, but it will also occasionally decline, and we may be able to find a shifted <math>\mathcal H'</math> with smaller diameter than <math>\mathcal H</math>.

----

A more sophisticated local optimization involves a process of ``adjustment" [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23766 proposed by Savitt].
Let <math>\mathcal H </math> be an admissible <math>k_0</math>-tuple.
For a prime <math>p</math> and an integer <math>a</math>, let <math>[a;p]</math> denote the residue class <math>a\bmod p</math>, i.e. the set of integers <math>\{ x : x = a \bmod p\}</math>.
Call <math>[a;p]</math> occupied if it contains an element of <math>\mathcal H </math>.

Suppose that <math>[a;p]</math> and <math>[b;q]</math> are occupied residue classes, for some distinct primes <math>p</math> and <math>q</math>, and that <math>[a';p]</math> and <math>[b';q]</math> are unoccupied.
Let <math>\mathcal U</math> be the intersection of <math>\mathcal H</math> with <math>[a;p] \cup [b;q]</math>, and let <math>\mathcal V</math> be a subset of the integers that lie in the intersection of the interval <math>I</math> containing <math>H</math> and the set <math>[a';p] \cup [b';q]</math> such that
the set <math>\mathcal H' </math> formed by removing the elements of <math>\mathcal U</math> from <math>\mathcal H </math> and adding the elements of <math>\mathcal V </math> is admissible.
A necessary (and often sufficient) condition for and integer <math>v</math> to lie in <math>\mathcal V</math> is that <math>v</math> must not lie in a residue class <math>[c;r]</math> that is the unique unoccupied residue class modulo <math>r</math> for any prime <math>r</math> other than <math>p</math> or <math>q</math>.

The admissible set <math>\mathcal H' </math> lies in the interval <math>\mathcal I</math> containing <math>\mathcal H</math>, so its diameter is no greater than that of <math>\mathcal H</math>, however its cardinality may differ. If it happens that <math>\mathcal H' </math> contains more elements than <math>\mathcal H </math>, then by eliminating points at either end of <math>\mathcal H' </math> we obtain an admissible <math>k_0</math>-tuple that is narrower than <math>\mathcal H</math> and may ``adjust" <math>\mathcal H </math> by replacing it with <math>\mathcal H' </math>.
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible <math>k_0</math>-tuples.

=== Further refinements ===

== Lower bounds ==

There is a substantial amount of literature on bounding the quantity <math>\pi(x+y)-\pi(x)</math>, the number of primes in a shifted interval <math>[x+1,x+y]</math>, where <math>x,y</math> are natural numbers. As a general rule, whenever a bound of the form

: <math> \pi(x+y) - \pi(x) \leq F(y) </math> (*)

is established for some function <math>F(y)</math> of <math>y</math>, the method of proof also gives a bound of the form

: <math> k_0 \leq F( H(k_0)+1 ).</math> (**)

Indeed, if one assumes the prime tuples conjecture, any admissible <math>k_0</math>-tuple of diameter <math>H</math> can be translated into an interval of the form <math>[x+1,x+H+1]</math> for some <math>x</math>. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for <math>x>y</math>, the set of primes between <math>x+1</math> and <math>x+y</math> is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

=== Brun-Titchmarsh inequality ===

The Brun-Titchmarsh theorem gives

: <math> \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}</math>

which then gives the lower bound

: <math> H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0</math>.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem [MV1973, Corollary 2], giving the more precise inequality

: <math> k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.</math>

=== First Montgomery-Vaughan large sieve inequality ===

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

: <math> k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2</math>

for any <math>Q > 1</math>, which is a parameter that one can optimise over (the optimal value is comparable to <math>H(k_0)^{1/2}</math>).

=== Second Montgomery-Vaughan large sieve inequality ===

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

: <math> k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}</math>

for any <math>z > 1</math>, which is a parameter similar to <math>Q</math> in the previous inequality, and <math>c</math> is an absolute constant. In the original paper of Montgomery and Vaughan, <math>c</math> was taken to be <math>3/2</math>; this was then reduced to <math>\sqrt{22}/\pi</math> [B1995, p.162] and then to <math>3.2/\pi</math> [M1978]. It is conjectured that <math>c</math> can be taken to in fact be <math>1</math>.

== Benchmarks ==

Efforts to fill in the blank fields in this table are very welcome.

{| border=1
|-
!<math>k_0</math>!!3,500,000!! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 10,719 !! 5,000 !! 2,000 !! 1,000 !! 672
|-
! Upper bounds
|-
|Zhang sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 59,093,364]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411932.txt 411,932]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23282_268536.txt 268,536]
| [http://math.mit.edu/~drew/admissible_10719.txt 114,806]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
| [http://math.mit.edu/~drew/admissible_2000_17766.txt 17,766]
| [http://math.mit.edu/~drew/admissible_1000_8212.txt 8,212]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
|-
|Hensley-Richards sieve
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2422558.txt 2,422,558]
| [http://math.mit.edu/~drew/admissible_34429_402790.txt 402,790]
| [http://math.mit.edu/~drew/admissible_26024_297454.txt 297,454]
| [http://math.mit.edu/~drew/admissible_23283_262794.txt 262,794]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
| [http://math.mit.edu/~drew/admissible_2000_17726.txt 17,726]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
|-
|Asymmetric Hensley-Richards
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23636 401,700]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23748 297,076]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23826 262,566]
| [http://math.mit.edu/~drew/admissible_10719_112646.txt 112,646]
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
|
|
|
|-
|Schinzel sieve
|
|
|
|
|
|
|
|
|
|
|-
|greedy-Schinzel sieve
|
|
|
|
|
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
| [http://math.mit.edu/~drew/admissible_2000_17054.txt 17,054]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5.030]
|-
|Best known tuple
| [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 57,554,086]
| [http://math.mit.edu/~drew/admissible_181000_2345896.txt 2,345,896]
| [http://math.mit.edu/~drew/admissible_34429_386532.txt 386,532]
| [http://math.mit.edu/~drew/admissible_26024_285210.txt 285,210]
| [http://math.mit.edu/~drew/admissible_23283_252804.txt 252,804]
| [http://math.mit.edu/~drew/admissible_10719_108462.txt 108,462]
| [http://math.mit.edu/~drew/admissible_5000_46824.txt 46,824]
| [http://math.mit.edu/~drew/admissible_2000_16984.txt 16,984]
| [http://math.mit.edu/~drew/admissible_1000_7808.txt 7,808]
| [http://math.mit.edu/~drew/admissible_672_5026.txt 5,026*]
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 2,372,232
| 394,096
| 290,604
| 257,405
| 110,119
| 47,586
| 17,202
| 7,907
| 5,046
|-
! Lower bounds
|-
|MV with <math>c=1</math> (conjectural)
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,642]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,924]
|
|
|
|
|
|
|-
|MV with <math>c=3.2/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 234,322]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 172,719]
|
|
|
|
|
|
|-
|MV with <math>c=\sqrt{22}/\pi</math>
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 227,078]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,860]
|
|
|
|
|
|
|-
|Second Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 226,987]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 167,793]
|
|
|
|
|
|
|-
|Brun-Titchmarsh
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 211,046]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555]
|
|
|
|
|
|
|-
|First Montgomery-Vaughan
|
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711]
|
|
|
|
|
|
|}

* In fact the best known tuple for <math>k_0 = 672</math> has width 4998, due to Engelsma; 5026 is the width of the best known tuple that was found by the methods that yielded the entries to the left of 5026 in the "best known tuple" row.

Bounded gaps between primes

2013-06-08T14:58:36Z

Savitt: /* World records */

== World records ==

* <math>H</math> is a quantity such that there are infinitely many pairs of consecutive primes of distance at most <math>H</math> apart. Would like to be as small as possible (this is a primary goal of the Polymath8 project).
* <math>k_0</math> is a quantity such that every admissible <math>k_0</math>-tuple has infinitely many translates which each contain at least two primes. Would like to be as small as possible. Improvements in <math>k_0</math> lead to improvements in <math>H</math>. (The relationship is roughly of the form <math>H \sim k_0 \log k_0</math>; there is an active discussion on optimising this relationship [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/ here].)
* <math>\varpi</math> is a technical parameter related to a specialized form of the [https://en.wikipedia.org/wiki/Elliott%E2%80%93Halberstam_conjecture Elliott-Halberstam conjecture]. Would like to be as large as possible. Improvements in <math>\varpi</math> lead to improvements in <math>k_0</math>. (The relationship is roughly of the form <math>k_0 \sim \varpi^{-3/2}</math>; there is an active discussion on optimising these improvements [http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/ here].) In more recent work, the single parameter <math>\varpi</math> is replaced by a pair <math>(\varpi,\delta)</math> (in previous work we had <math>\delta=\varpi</math>). Discussion on improving the values of <math>(\varpi,\delta)</math> is currently being held [http://terrytao.wordpress.com/2013/06/04/online-reading-seminar-for-zhangs-bounded-gaps-between-primes/ here].

{| border=1
|-
!Date!!<math>\varpi</math> or (<math>\varpi,\delta)</math>)!! <math>k_0</math> !! <math>H</math> !! Comments
|-
| 14 May
| 1/1,168 ([http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf Zhang])
| 3,500,000 ([http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf Zhang])
| 70,000,000 ([http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf Zhang])
| All subsequent work is based on Zhang's breakthrough paper.
|-
| 21 May
|
|
| 63,374,611 ([http://mathoverflow.net/questions/131185/philosophy-behind-yitang-zhangs-work-on-the-twin-primes-conjecture/131354#131354 Lewko])
| Optimises Zhang's condition <math>\pi(H)-\pi(k_0) > k_0</math>; [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23439 can be reduced by 1] by parity considerations
|-
| 28 May
|
|
| 59,874,594 ([http://arxiv.org/abs/1305.6369 Trudgian])
| Uses <math>(p_{m+1},\ldots,p_{m+k_0})</math> with <math>p_{m+1} > k_0</math>
|-
| 30 May
|
|
| 59,470,640 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/ Morrison])
58,885,998? ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23441 Tao])

59,093,364 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23444 Morrison])

57,554,086 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23448 Morrison])
| Uses <math>(p_{m+1},\ldots,p_{m+k_0})</math> and then <math>(\pm 1, \pm p_{m+1}, \ldots, \pm p_{m+k_0/2-1})</math> following [HR1973], [HR1973b], [R1974] and optimises in m
|-
| 31 May
|
| 2,947,442 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23460 Morrison])
2,618,607 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23467 Morrison])
| 48,112,378 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23460 Morrison])
42,543,038 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23467 Morrison])

42,342,946 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23468 Morrison])
| Optimizes Zhang's condition <math>\omega>0</math>, and then uses an [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23465 improved bound] on <math>\delta_2</math>
|-
| 1 Jun
|
|
| 42,342,924 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23473 Tao])
| Tiny improvement using the parity of <math>k_0</math>
|-
| 2 Jun
|
| 866,605 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23479 Morrison])
| 13,008,612 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23479 Morrison])
| Uses a [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23473 further improvement] on the quantity <math>\Sigma_2</math> in Zhang's analysis (replacing the previous bounds on <math>\delta_2</math>)
|-
| 3 Jun
| 1/1,040? ([http://mathoverflow.net/questions/132632/tightening-zhangs-bound-closed v08ltu])
| 341,640 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23512 Morrison])
| 4,982,086 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23512 Morrison])
4,802,222 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23516 Morrison])
| Uses a [http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/ different method] to establish <math>DHL[k_0,2]</math> that removes most of the inefficiency from Zhang's method.
|-
| 4 Jun
| 1/224?? ([http://polymathprojects.org/2013/06/04/polymath-proposal-bounded-gaps-between-primes/#comment-19961 v08ltu])
1/240?? ([http://terrytao.wordpress.com/2013/06/04/online-reading-seminar-for-zhangs-bounded-gaps-between-primes/#comment-232661 v08ltu])
|
| 4,801,744 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23534 Sutherland])
4,788,240 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23543 Sutherland])
| Uses asymmetric version of the Hensley-Richards tuples
|-
| 5 Jun
|
| 34,429? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-232721 Paldi]/[http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-232732 v08ltu])
34,429 ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-232840 Tao]/[http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-232843 v08ltu]/[http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-232877 Harcos])
| 4,725,021 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23555 Elsholtz])
4,717,560 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23562 Sutherland])

397,110? ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23563 Sutherland])

4,656,298 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 Sutherland])

389,922 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23566 Sutherland])

388,310 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23571 Sutherland])

388,284 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23570 Castryck])

388,248 ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23573 Sutherland])

[http://math.mit.edu/~drew/admissable.txt 388,188] ([http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23576 Sutherland])

387,982 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23588 Castryck])

387,974 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23591 Castryck])

| k_0 bound uses the optimal Bessel function cutoff. Originally only provisional due to neglect of the kappa error, but then it was confirmed that the kappa error was within the allowed tolerance.
H bound obtained by a hybrid Schinzel/greedy (or "greedy-greedy") sieve

|-
| 6 Jun
| (1/488,3/9272)? ([http://arxiv.org/abs/1306.1497 Pintz])
1/552? ([http://arxiv.org/abs/1306.1497 Pintz], [http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233149 Tao])
| 60,000*? ([http://arxiv.org/abs/1306.1497 Pintz])

52,295*? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233150 Peake])

11,123? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233151 Tao])
| 387,960 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23598 Angelveit])
[http://math.mit.edu/~drew/admissable_34429_387910.txt 387,910] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23599 Sutherland])

387,904 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23602 Angeltveit])

[http://math.mit.edu/~drew/admissable_34429_387814.txt 387,814] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23605 Sutherland])

[http://math.mit.edu/~drew/admissable_34429_387766.txt 387,766] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23608 Sutherland])

[http://math.mit.edu/~drew/admissable_34429_387754.txt 387,754] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23613 Sutherland])

[http://math.mit.edu/~drew/admissable_34429_387620.txt 387,620] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23652 Sutherland])

768,534*? ([http://arxiv.org/abs/1306.1497 Pintz])

| Improved H-bounds based on experimentation with different residue classes and different intervals, and randomized tie-breaking in the greedy sieve.
|-
| 7 Jun
| (1/538, 1/660)? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233178 v08ltu])
(1/538, 31/20444)? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233182 v08ltu])

(1/942, 19/27004)? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233321 v08ltu])

<math>207 \varpi + 43\delta < \frac{1}{4}</math> ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233321 v08ltu]/[http://terrytao.wordpress.com/2013/06/04/online-reading-seminar-for-zhangs-bounded-gaps-between-primes/#comment-233400 Green])]
| 11,018? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233167 Tao])
10,721? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233178 v08ltu])

10,719? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233182 v08ltu])

25,111? ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233321 v08ltu])

26,024 ([http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/#comment-233364 vo8ltu])
| [http://maths-people.anu.edu.au/~angeltveit/admissible_11123_113520.txt 113,520]? ([http://maths-people.anu.edu.au/~angeltveit/admissible_11123_113520.txt Angeltveit])
[http://maths-people.anu.edu.au/~angeltveit/admissible_10721_109314.txt 109,314]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23663 Angeltveit/Sutherland])

[http://math.mit.edu/~drew/admissable_60000_707328.txt 707,328*] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23666 Sutherland])

[http://math.mit.edu/~drew/admissable_10721_108990.txt 108,990]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23666 Sutherland])

[http://math.mit.edu/~drew/admissable_11123_113462.txt 113,462*]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23667 Sutherland])

[http://math.mit.edu/~drew/admissable_11018_112302.txt 112,302*]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23667 Sutherland])

[http://math.mit.edu/~drew/admissable_11018_112272.txt 112,272*]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23669 Sutherland])

116,386*? ([http://polymathprojects.org/2013/06/04/polymath-proposal-bounded-gaps-between-primes/#comment-20116 Sun])

[http://math.mit.edu/~drew/admissable_10719_108978.txt 108,978]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23675 Sutherland])

[http://math.mit.edu/~drew/admissable_10719_108634.txt 108,634]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23677 Sutherland])

[https://perswww.kuleuven.be/~u0040935/108632.txt 108,632]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23680 Castryck])

[http://math.mit.edu/~drew/admissable_10719_108600.txt 108,600]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23682 Sutherland])

[https://perswww.kuleuven.be/~u0040935/108570.txt 108,570]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23683 Castryck])

[http://math.mit.edu/~drew/admissable_10719_108556.txt 108,556]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23684 Sutherland])

[http://www.cs.cmu.edu/~xfxie/project/admissible/admissable_10719_108550.txt 108,550]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23688 xfxie])

[http://math.mit.edu/~drew/admissable_25111_275424.txt 275,424]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23694 Sutherland])

[http://math.mit.edu/~drew/admissable_10719_108540.txt 108,540]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23695 Sutherland])

[http://math.mit.edu/~drew/admissable_25111_275418.txt 275,418]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23697 Sutherland])

[http://math.mit.edu/~drew/admissable_25111_275404.txt 275,404]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23699 Sutherland])

[https://perswww.kuleuven.be/~u0040935/25111_275292.txt 275,292]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23701 Castryck-Sutherland])

275,262? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23703 Castryck]-[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23702 pedant]-Sutherland)

[http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_25111_275388.txt 275,388?*] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23704 xfxie]-Sutherland)

[https://perswww.kuleuven.be/~u0040935/25111_275126.txt 275,126]? ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23706 Castryck]-pedant-Sutherland)

274,970? ([https://www.dropbox.com/sh/jjxi0jmcskx1xcz/iBBVwZTj-x Castryck-pedant-Sutherland])

[http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_25111_275208.txt 275,208]?* ([http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_25111_275208.txt xfxie])

387,534 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23716 pedant-Sutherland])
| Note: Many of the results are provisional due to a number of issues found in the most recent preprint of Pintz.
|-
| June 8
|
|
| 286,224 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23720 Sutherland])
[http://math.mit.edu/~drew/admissable_26024_285810.txt 285,810] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23722 Sutherland])

[http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_26024_286216.txt 286,216] ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23723 xfxie-Sutherland])

285,752 ([http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23725 pedant-Sutherland])
| values of <math>\varpi,\delta,k_0</math> now confirmed; most tuples available [https://www.dropbox.com/sh/jjxi0jmcskx1xcz/iBBVwZTj-x on dropbox]
|}

? - unconfirmed or conditional

?? - theoretical limit of an analysis, rather than a claimed record

* - is majorized by an earlier but independent result

== Benchmarks ==

Let H be the minimal diameter of an admissible tuple of cardinality <math>k_0 = 34,429</math>. For benchmark upper bounds:

* The Zhang sieve (as optimized by Trudgian and later Morrison) [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23613 gives] <math>H \leq 411,932</math>.
* The Hensley-Richards sieve [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23633 gives] <math>H \leq 402,790</math> after optimization.
* The shifted Hensley-Richards sieve [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23636 gives] <math>H \leq 401,700</math> after optimization.

For benchmark lower bounds:

* The easier version of the Montgomery-Vaughan large sieve inequality <math>k_0 \sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H+1+Q^2</math> [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 gives] <math>H \geq 196,729</math>.
* The Montgomery-Vaughan Brun-Titchmarsh bound <math>k_0 \leq \frac{2(H+1)}{\log(H+1)}</math> [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23611 gives] <math>H \geq 211,046</math>.
* The Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23634 gives] <math>H \geq 226,987</math> after optimization.
* Using a refinement of this inequality [B1995, p.162] [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23641 improves this] to <math>H \geq 227,078</math>.
* A further (unpublished) refinement [http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.bams/1183540922 due to Selberg] [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23648 increases this to] <math>H \geq 234,322</math>, and conjecturally to <math>H \geq 234,642</math>.

== Polymath threads ==

* [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart I just can’t resist: there are infinitely many pairs of primes at most 59470640 apart], Scott Morrison, 30 May 2013 Inactive
* [http://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/ The prime tuples conjecture, sieve theory, and the work of Goldston-Pintz-Yildirim, Motohashi-Pintz, and Zhang], Terence Tao, 3 June 2013. Active
* [http://polymathprojects.org/2013/06/04/polymath-proposal-bounded-gaps-between-primes/ Polymath proposal: bounded gaps between primes], Terence Tao, 4 June 2013. Active
* [http://terrytao.wordpress.com/2013/06/04/online-reading-seminar-for-zhangs-bounded-gaps-between-primes/ Online reading seminar for Zhang’s “bounded gaps between primes], Terence Tao, 4 June 2013. Active
* [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/ More narrow admissible sets], Scott Morrison, 5 June 2013. Active

== Code and data ==

* [https://github.com/semorrison/polymath8 Hensely-Richards sequences], Scott Morrison
** [http://tqft.net/misc/finding%20k_0.nb A mathematica notebook for finding k_0], Scott Morrison
** [https://github.com/avi-levy/dhl python implementation], Avi Levy
* [http://www.opertech.com/primes/k-tuples.html k-tuple pattern data], Thomas J Engelsma
** [https://perswww.kuleuven.be/~u0040935/k0graph.png A graph of this data]
* [https://github.com/vit-tucek/admissible_sets Sifted sequences], Vit Tucek
* [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart/#comment-23555 Other sifted sequences], Christian Elsholtz
* [http://www.ams.org/journals/mcom/2001-70-236/S0025-5718-01-01348-5/S0025-5718-01-01348-5.pdf Size of largest admissible tuples in intervals of length up to 1050], Clark and Jarvis
* [http://math.mit.edu/~drew/admissable_v0.1.tar C implementation of the "greedy-greedy" algorithm], Andrew Sutherland
* [https://www.dropbox.com/sh/jjxi0jmcskx1xcz/iBBVwZTj-x Dropbox for sequences], pedant

== Other relevant blog posts ==

* [http://terrytao.wordpress.com/2008/11/19/marker-lecture-iii-small-gaps-between-primes/ Marker lecture III: “Small gaps between primes”], Terence Tao, 19 Nov 2008.
* [http://blogs.ethz.ch/kowalski/2009/01/22/the-goldston-pintz-yildirim-result-and-how-far-do-we-have-to-walk-to-twin-primes/ The Goldston-Pintz-Yildirim result, and how far do we have to walk to twin primes ?], Emmanuel Kowalski, 22 Jan 2009.
* [http://www.math.columbia.edu/~woit/wordpress/?p=5865 Number Theory News], Peter Woit, 12 May 2013.
* [http://golem.ph.utexas.edu/category/2013/05/bounded_gaps_between_primes.html Bounded Gaps Between Primes], Emily Riehl, 14 May 2013.
* [http://blogs.ethz.ch/kowalski/2013/05/21/bounded-gaps-between-primes/ Bounded gaps between primes!], Emmanuel Kowalski, 21 May 2013.
* [http://blogs.ethz.ch/kowalski/2013/06/04/bounded-gaps-between-primes-some-grittier-details/ Bounded gaps between primes: some grittier details], Emmanuel Kowalski, 4 June 2013.
** [http://www.math.ethz.ch/~kowalski/zhang-notes.pdf The slides from the talk mentioned in that post]
* [http://aperiodical.com/2013/06/bound-on-prime-gaps-bound-decreasing-by-leaps-and-bounds/ Bound on prime gaps bound decreasing by leaps and bounds], Christian Perfect, 8 June 2013.

== MathOverflow ==

* [http://mathoverflow.net/questions/131185/philosophy-behind-yitang-zhangs-work-on-the-twin-primes-conjecture Philosophy behind Yitang Zhang’s work on the Twin Primes Conjecture], 20 May 2013.
* [http://mathoverflow.net/questions/131825/a-technical-question-related-to-zhangs-result-of-bounded-prime-gaps A technical question related to Zhang’s result of bounded prime gaps], 25 May 2013.
* [http://mathoverflow.net/questions/132452/how-does-yitang-zhang-use-cauchys-inequality-and-theorem-2-to-obtain-the-error How does Yitang Zhang use Cauchy’s inequality and Theorem 2 to obtain the error term coming from the <math>S_2</math> sum], 31 May 2013.
* [http://mathoverflow.net/questions/132632/tightening-zhangs-bound-closed Tightening Zhang’s bound], 3 June 2013.
** [http://meta.mathoverflow.net/discussion/1605/tightening-zhangs-bound/ Metathread for this post]
* [http://mathoverflow.net/questions/132731/does-zhangs-theorem-generalize-to-3-or-more-primes-in-an-interval-of-fixed-len Does Zhang’s theorem generalize to 3 or more primes in an interval of fixed length?], 3 June 2013.

== Wikipedia ==

* [http://en.wikipedia.org/wiki/Bessel_function Bessel function]
* [http://en.wikipedia.org/wiki/Bombieri-Vinogradov_theorem Bombieri-Vinogradov theorem]
* [http://en.wikipedia.org/wiki/Brun%E2%80%93Titchmarsh_theorem Brun-Titchmarsh theorem]
* [http://en.wikipedia.org/wiki/Prime_gap Prime gap]
* [http://en.wikipedia.org/wiki/Second_Hardy%E2%80%93Littlewood_conjecture Second Hardy-Littlewood conjecture]
* [http://en.wikipedia.org/wiki/Twin_prime_conjecture Twin prime conjecture]

== Recent papers and notes ==

* [http://arxiv.org/abs/1304.3199 On the exponent of distribution of the ternary divisor function], Étienne Fouvry, Emmanuel Kowalski, Philippe Michel, 11 Apr 2013.
* [http://www.renyi.hu/~revesz/ThreeCorr0grey.pdf On the optimal weight function in the Goldston-Pintz-Yildirim method for finding small gaps between consecutive primes], Bálint Farkas, János Pintz and Szilárd Gy. Révész, To appear in: Paul Turán Memorial Volume: Number Theory, Analysis and Combinatorics, de Gruyter, Berlin, 2013. 23 pages.
* [http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf Bounded gaps between primes], Yitang Zhang, to appear, Annals of Mathematics. Released 21 May, 2013.
* [http://arxiv.org/abs/1305.6289 Polignac Numbers, Conjectures of Erdös on Gaps between Primes, Arithmetic Progressions in Primes, and the Bounded Gap Conjecture], Janos Pintz, 27 May 2013.
* [http://arxiv.org/abs/1305.6369 A poor man's improvement on Zhang's result: there are infinitely many prime gaps less than 60 million], T. S. Trudgian, 28 May 2013.
* [http://www.math.ethz.ch/~kowalski/friedlander-iwaniec-sum.pdf The Friedlander-Iwaniec sum], É. Fouvry, E. Kowalski, Ph. Michel., May 2013.
* [http://terrytao.files.wordpress.com/2013/06/bounds.pdf Notes on Zhang's prime gaps paper], Terence Tao, 1 June 2013.
* [http://arxiv.org/abs/1306.0511 Bounded prime gaps in short intervals], Johan Andersson, 3 June 2013.
* [http://arxiv.org/abs/1306.0948 Bounded length intervals containing two primes and an almost-prime II], James Maynard, 5 June 2013.
* [http://arxiv.org/abs/1306.1497 A note on bounded gaps between primes], Janos Pintz, 6 June 2013.

== Media ==

* [http://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-come-in-pairs-1.12989 First proof that infinitely many prime numbers come in pairs], Maggie McKee, Nature, 14 May 2013.
* [http://www.newscientist.com/article/dn23535-proof-that-an-infinite-number-of-primes-are-paired.html Proof that an infinite number of primes are paired], Lisa Grossman, New Scientist, 14 May 2013.
* [https://www.simonsfoundation.org/features/science-news/unheralded-mathematician-bridges-the-prime-gap/ Unheralded Mathematician Bridges the Prime Gap], Erica Klarreich, Simons science news, 20 May 2013.
** The article also appeared on Wired as "[http://www.wired.com/wiredscience/2013/05/twin-primes/ Unknown Mathematician Proves Elusive Property of Prime Numbers]".
* [http://www.slate.com/articles/health_and_science/do_the_math/2013/05/yitang_zhang_twin_primes_conjecture_a_huge_discovery_about_prime_numbers.html The Beauty of Bounded Gaps], Jordan Ellenberg, Slate, 22 May 2013.
* [http://www.newscientist.com/article/dn23644 Game of proofs boosts prime pair result by millions], Jacob Aron, New Scientist, 4 June 2013.

== Bibliography ==

Additional links for some of these references (e.g. to arXiv versions) would be greatly appreciated.

* [BFI1986] Bombieri, E.; Friedlander, J. B.; Iwaniec, H. Primes in arithmetic progressions to large moduli. Acta Math. 156 (1986), no. 3-4, 203–251. [http://www.ams.org/mathscinet-getitem?mr=834613 MathSciNet] [http://link.springer.com/article/10.1007%2FBF02399204 Article]
* [BFI1987] Bombieri, E.; Friedlander, J. B.; Iwaniec, H. Primes in arithmetic progressions to large moduli. II. Math. Ann. 277 (1987), no. 3, 361–393. [http://www.ams.org/mathscinet-getitem?mr=891581 MathSciNet] [https://eudml.org/doc/164255 Article]
* [BFI1989] Bombieri, E.; Friedlander, J. B.; Iwaniec, H. Primes in arithmetic progressions to large moduli. III. J. Amer. Math. Soc. 2 (1989), no. 2, 215–224. [http://www.ams.org/mathscinet-getitem?mr=976723 MathSciNet] [http://www.ams.org/journals/jams/1989-02-02/S0894-0347-1989-0976723-6/ Article]
* [B1995] Jörg Brüdern, Einführung in die analytische Zahlentheorie, Springer Verlag 1995
* [CJ2001] Clark, David A.; Jarvis, Norman C.; Dense admissible sequences. Math. Comp. 70 (2001), no. 236, 1713–1718 [http://www.ams.org/mathscinet-getitem?mr=1836929 MathSciNet] [http://www.ams.org/journals/mcom/2001-70-236/S0025-5718-01-01348-5/home.html Article]
* [FI1981] Fouvry, E.; Iwaniec, H. On a theorem of Bombieri-Vinogradov type., Mathematika 27 (1980), no. 2, 135–152 (1981). [http://www.ams.org/mathscinet-getitem?mr=610700 MathSciNet] [http://www.math.ethz.ch/~kowalski/fouvry-iwaniec-on-a-theorem.pdf Article]
* [FI1983] Fouvry, E.; Iwaniec, H. Primes in arithmetic progressions. Acta Arith. 42 (1983), no. 2, 197–218. [http://www.ams.org/mathscinet-getitem?mr=719249 MathSciNet] [http://matwbn.icm.edu.pl/ksiazki/aa/aa42/aa4226.pdf Article]
* [FI1985] Friedlander, John B.; Iwaniec, Henryk, Incomplete Kloosterman sums and a divisor problem. With an appendix by Bryan J. Birch and Enrico Bombieri. Ann. of Math. (2) 121 (1985), no. 2, 319–350. [http://www.ams.org/mathscinet-getitem?mr=786351 MathSciNet] [http://www.jstor.org/stable/1971175 JSTOR]
* [GPY2009] Goldston, Daniel A.; Pintz, János; Yıldırım, Cem Y. Primes in tuples. I. Ann. of Math. (2) 170 (2009), no. 2, 819–862. [http://arxiv.org/abs/math/0508185 arXiv] [http://www.ams.org/mathscinet-getitem?mr=2552109 MathSciNet]
* [GR1998] Gordon, Daniel M.; Rodemich, Gene Dense admissible sets. Algorithmic number theory (Portland, OR, 1998), 216–225, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998. [http://www.ams.org/mathscinet-getitem?mr=1726073 MathSciNet] [http://www.ccrwest.org/gordon/ants.pdf Article]
* [HR1973] Hensley, Douglas; Richards, Ian, On the incompatibility of two conjectures concerning primes. Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972), pp. 123–127. Amer. Math. Soc., Providence, R.I., 1973. [http://www.ams.org/mathscinet-getitem?mr=340194 MathSciNet] [http://www.ams.org/journals/bull/1974-80-03/S0002-9904-1974-13434-8/S0002-9904-1974-13434-8.pdf Article]
* [HR1973b] Hensley, Douglas; Richards, Ian, Primes in intervals. Acta Arith. 25 (1973/74), 375–391. [http://www.ams.org/mathscinet-getitem?mr=396440 MathSciNet] [https://eudml.org/doc/205282 Article]
* [MP2008] Motohashi, Yoichi; Pintz, János A smoothed GPY sieve. Bull. Lond. Math. Soc. 40 (2008), no. 2, 298–310. [http://arxiv.org/abs/math/0602599 arXiv] [http://www.ams.org/mathscinet-getitem?mr=2414788 MathSciNet] [http://blms.oxfordjournals.org/content/40/2/298 Article]
* [MV1973] Montgomery, H. L.; Vaughan, R. C. The large sieve. Mathematika 20 (1973), 119–134. [http://www.ams.org/mathscinet-getitem?mr=374060 MathSciNet] [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=6718308 Article]
* [R1974] Richards, Ian On the incompatibility of two conjectures concerning primes; a discussion of the use of computers in attacking a theoretical problem. Bull. Amer. Math. Soc. 80 (1974), 419–438. [http://www.ams.org/mathscinet-getitem?mr=337832 MathSciNet] [http://www.ams.org/journals/bull/1974-80-03/S0002-9904-1974-13434-8/home.html Article]
* [S1961] Schinzel, A. Remarks on the paper "Sur certaines hypothèses concernant les nombres premiers". Acta Arith. 7 1961/1962 1–8. [http://www.ams.org/mathscinet-getitem?mr=130203 MathSciNet] [http://matwbn.icm.edu.pl/ksiazki/aa/aa7/aa711.pdf Article]
* [S2007] K. Soundararajan, Small gaps between prime numbers: the work of Goldston-Pintz-Yıldırım. Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 1, 1–18. [http://www.ams.org/mathscinet-getitem?mr=2265008 MathSciNet] [http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/ Article] [http://arxiv.org/abs/math/0605696 arXiv]