View source for Finding narrow admissible tuples

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 minimized subject to staying admissible.  Any <math>m</math> with <math>p_{m+1} > k_0</math> yields an admissible tuple; 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 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<x</math>, the Schinzel sieve (discussed in [S1961], [HR1973], [GR1998], [CJ2001]) sieves the interval <math>[1,x]</math> by <math>1 \bmod p</math> for primes <math>p \le y</math> and by <math>0\bmod p</math> for primes <math>y < p \le z</math>.  Provided that <math>z</math> is large enough (<math>z=k_0</math> clearly suffices), the first <math>k_0</math> survivors form an admissible <math>k_0</math>-tuple (but not necessarily the narrowest one in the interval).
The case <math>y=1</math> corresponds to a sieve of Eratosthenes; if one minimizes <math>z</math> and takes the first <math>k_0</math> survivors greater than 1, this yields the same admissible <math>k_0</math> tuple as Zhang, with the minimal possible value of <math>m</math>.

=== Shifted Schinzel sieve ===
As a generalization of the Schinzel sieve, one may instead sieve shifted intervals <math>[s,s+x]</math>.  This is effectively equivalent to sieving the interval <math>[0,x]</math> of the residue classes <math>-s\ \bmod\ p</math> for primes <math>p\le y</math> and <math> 1-s\ \bmod\ p</math> for primes <math>y<p\le z</math>.

=== Greedy sieve ===
Within a given interval, 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-greedy sieve ===
Heuristically, the performance of the greedy sieve is significantly improved by starting with a shifted Schinzel sieve on <math>[s,\ s+x]</math> using <math>y = 2</math> and <math>z = \sqrt{x}</math> and then continuing in a greedy fashion, as [http://sbseminar.wordpress.com/2013/05/30/i-just-cant-resist-there-are-infinitely-many-pairs-of-primes-at-most-59470640-apart#comment-23566 proposed by Sutherland].  One first optimizes the shift value <math>s</math> over some larger interval (e.g. <math>[-k_0\log\ k_0,\ k_0\log\ k_0]</math>) and then continues the sieving over primes <math>p > z</math> greedily choosing the best residue class for each prime according to a chosen tie-breaking rule (in Sutherland's original implementation, ties are broken downward in <math>[0,\ p-1]</math>).

=== 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 !! 341,640 !! 181,000 !! 34,429 !! 26,024 !! 23,283 !! 22,949 !! 10,719 !! 7,140 !! 6,329 !! 5,453 !! 5,000 
|-
! Upper bounds
|-
| First <math>k_0</math> primes past <math>k_0</math> 
| [http://arxiv.org/abs/1305.6369 59,874,594]
| 5,005,362
| 2,530,338
| 420,878
| 310,134
| 275,082
| 270,698
| 117,714
| 75,222
| 65,924
| 55,892
| 50,840
|-
|Zhang sieve
| [http://math.mit.edu/~drew/admissible_3500000_59093364.txt 59,093,364]
| [http://math.mit.edu/~drew/admissible_341640_4923060.txt 4,923,060]
| [http://math.mit.edu/~drew/admissible_181000_2486370.txt 2,486,370]
| [http://math.mit.edu/~drew/admissible_34429_411946.txt 411,946]
| [http://math.mit.edu/~drew/admissible_26024_303558.txt 303,558]
| [http://math.mit.edu/~drew/admissible_23283_268544.txt 268,544]
| [http://math.mit.edu/~drew/admissible_22949_264460.txt 264,460]
| [http://math.mit.edu/~drew/admissible_10719_114814.txt 114,814]
| [http://math.mit.edu/~drew/admissible_7140_73448.txt 73,448]
| [http://math.mit.edu/~drew/admissible_6329_64182.txt 64,182]
| [http://math.mit.edu/~drew/admissible_5453_54488.txt 54,488]
| [http://math.mit.edu/~drew/admissible_5000_49578.txt 49,578]
|-
|Hensley-Richards sieve
| [http://math.mit.edu/~drew/admissible_3500000_57554086.txt 57,554,086]
| [http://math.mit.edu/~drew/admissible_341640_4802222.txt 4,802,222]
| [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_22949_258780.txt 258,780]
| [http://math.mit.edu/~drew/admissible_10719_112868.txt 112,868]
| [http://math.mit.edu/~drew/admissible_7140_72538.txt 72,538]
| [http://math.mit.edu/~drew/admissible_6329_63708.txt 63,708]
| [http://math.mit.edu/~drew/admissible_5453_53654.txt 53,654] 
| [http://math.mit.edu/~drew/admissible_5000_48634.txt 48,634]
|-
|Asymmetric Hensley-Richards
| [http://math.mit.edu/~drew/admissible_3500000_57480832.txt 57,480,832]
| [http://math.mit.edu/~drew/admissible_341640_4788240.txt 4,788,240]
| [http://math.mit.edu/~drew/admissible_181000_2418054.txt 2,418,054]
| [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_22949_258302.txt 258,302]
| [http://math.mit.edu/~drew/admissible_10719_112562.txt 112,562]
| [http://math.mit.edu/~drew/admissible_7140_72062.txt 72,062]
| [http://math.mit.edu/~drew/admissible_6329_62900.txt 62,900]
| [http://math.mit.edu/~drew/admissible_5453_53278.txt 53,278]
| [http://math.mit.edu/~drew/admissible_5000_48484.txt 48,484]
|-
|Shifted Schinzel sieve
| [http://math.mit.edu/~drew/admissible_3500000_56789070.txt 56,789,070]
| [http://math.mit.edu/~drew/admissible_341640_4740846.txt 4,740,846]
| [http://math.mit.edu/~drew/admissible_181000_2396594.txt 2,396,594]
| [http://math.mit.edu/~drew/admissible_34429_399248.txt 399,248]
| [http://math.mit.edu/~drew/admissible_26024_294810.txt 294,810]
| [http://math.mit.edu/~drew/admissible_23283_260714.txt 260,714]
| [http://math.mit.edu/~drew/admissible_22949_256702.txt 256,702]
| [http://math.mit.edu/~drew/admissible_10719_112200.txt 112,200]
| [http://math.mit.edu/~drew/admissible_7140_71930.txt 71,930]
| [http://math.mit.edu/~drew/admissible_6329_62892.txt 62,892]
| [http://math.mit.edu/~drew/admissible_5453_53236.txt 53,236]
| [http://math.mit.edu/~drew/admissible_5000_48472.txt 48,472]
|-
| Greedy-greedy sieve
| [http://math.mit.edu/~drew/admissible_3500000_55233744.txt 55,233,744]
| [http://math.mit.edu/~drew/admissible_341640_4603276.txt 4,603,276]
| [http://math.mit.edu/~drew/admissible_181000_2326458.txt 2,326,458]
| [http://math.mit.edu/~drew/admissible_34429_388076.txt 388,076]
| [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_22949_249992.txt 249,992]
| [http://math.mit.edu/~drew/admissible_10719_108694.txt 108,694]
| [http://math.mit.edu/~drew/admissible_7140_69564.txt 69,564]
| [http://math.mit.edu/~drew/admissible_6329_60942.txt 60,942]
| [http://math.mit.edu/~drew/admissible_5453_51688.txt 51,688]
| [http://math.mit.edu/~drew/admissible_5000_46968.txt 46,968]
|-
|Best known tuple
| [http://math.mit.edu/~drew/admissible_3500000_55233504.txt 55,233,504]
| [http://math.mit.edu/~drew/admissible_341640_4601036.txt 4,601,036]
| [http://math.mit.edu/~drew/admissible_181000_2323344.txt 2,323,344]
| [http://math.mit.edu/~drew/admissible_34429_386344.txt 386,344]
| [http://math.mit.edu/~drew/admissible_26024_285102.txt 285,102]
| [http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_23283_252722_-135118.txt 252,722]
| [http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_22949_248816_262.txt 248,816]
| [http://math.mit.edu/~drew/admissible_10719_108440.txt 108,440]
| [http://math.mit.edu/~drew/admissible_7140_69280.txt 69,280]
| [http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_6329_60726_14.txt 60,726]
| [http://math.mit.edu/~drew/admissible_5453_51526.txt 51,526]
| [http://math.mit.edu/~drew/admissible_5000_46806.txt 46,806]
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 56,238,957
| 4,694,650
| 2,372,232
| 394,096
| 290,604
| 257,405
| 253,381
| 110,119
| 70,496
| 61,727
| 52,371
| 47,586
|-
! Lower bounds
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 19)
| 
|
| 
|
| 
| 
| 
| 
|
| 
| 
| 
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 17)
| 
|
| 
|
| 
| 
| 
| 
|
| 
| 
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23925 38,048]
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 13)
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23930 29,508,018]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23930 1,513,556]
|
| 
| 
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23953 193,420]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23925 85,878]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-24008 49,464]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-24037 41,860]
| 37,920
|-
|Partitioning
| 24,208,216
| 2,362,920
| 1,251,784
| 238,040
| 179,932
| 160,940
| 158,656
| 74,128
| 49,306
| 43,678
| 37,630
| 34,578
|-
|MV with <math>c=1</math> (conjectural)
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 32,503,908]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 1,395,694]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 234,872]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 173,420]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 153,691]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 151,298]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 66,314]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 37,274]
| 31,644
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 28,781]
|-
|MV with <math>c=3.2/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 32,469,985]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23913 1,393,869]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 234,529]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 173,140]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 153,447]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 151,056]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 66,211]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 37,207]
| 31,584
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 28,737]
|-
|MV with <math>c=\sqrt{22}/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 31,765,216]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 1,357,096]
| [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]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 148,719]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 146,393]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 63,917]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 35,903]
| 30,478
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 27,708]
|-
|Second Montgomery-Vaughan
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 31,756,667]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 1,356,644]
| [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]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 148,656]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 146,338]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23896 63,886]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 35,887]
| 30,463
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 27,696]
|-
|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
| 135,599
| 58,863
|
| 32,916
| 27,910
| 25,351
|-
|First Montgomery-Vaughan
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 28,080,007]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23926 1,184,954]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23621 196,729] 
196,719

[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 197,096]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 145,711] 
145,461
| 128,971
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 126,931]
| 55,149
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 55,178]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23950 30,982]
| 26,388
| 24,012
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 24,037]
|}



{| border=1
|-
!<math>k_0</math> !! 4,000 !! 3,405 !! 3,000 !! 2,000 !! 1,783 !! 1,000 !! 672 !! 632 !! 342
|-
! Upper bounds
|-
| First <math>k_0</math> primes past <math>k_0</math> 
| 39,660
| 33,222
| 28,972
| 18,386
| 16,174
| 8,424
| 5,406
| 5,028
| 2,472
|-
|Zhang sieve
| [http://math.mit.edu/~drew/admissible_4000_38596.txt 38,596]
| [http://math.mit.edu/~drew/admissible_3405_32296.txt 32,296]
| [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_1783_15620.txt 15,620]
| [http://math.mit.edu/~drew/admissible_1000_8218.txt 8,218]
| [http://math.mit.edu/~drew/admissible_672_5216.txt 5,216]
| [http://math.mit.edu/~drew/admissible_632_4860.txt 4,860]
| [http://math.mit.edu/~drew/admissible_342_2416.txt 2,416]
|-
|Hensley-Richards sieve
| [http://math.mit.edu/~drew/admissible_4000_38498.txt 38,498]
| [http://math.mit.edu/~drew/admissible_3405_31820.txt 31,820]
| [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_1783_15756.txt 15,756]
| [http://math.mit.edu/~drew/admissible_1000_8258.txt 8,258]
| [http://math.mit.edu/~drew/admissible_672_5314.txt 5,314]
| [http://math.mit.edu/~drew/admissible_632_4918.txt 4,918]
| [http://math.mit.edu/~drew/admissible_342_2446.txt 2,446]
|-
|Asymmetric Hensley-Richards
| [http://math.mit.edu/~drew/admissible_4000_37932.txt 37,932]
| [http://math.mit.edu/~drew/admissible_3405_31762.txt 31,762]
| [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_1783_15470.txt 15,470]
| [http://math.mit.edu/~drew/admissible_1000_8168.txt 8,168]
| [http://math.mit.edu/~drew/admissible_672_5220.txt 5,220]
| [http://math.mit.edu/~drew/admissible_632_4876.txt 4,876]
| [http://math.mit.edu/~drew/admissible_342_2424.txt 2,424]
|-
|Shifted Schinzel sieve
| [http://math.mit.edu/~drew/admissible_4000_38006.txt 38,006]
| [http://math.mit.edu/~drew/admissible_3405_31910.txt 31,910]
| [http://math.mit.edu/~drew/admissible_3000_27600.txt 27,600]
| [http://math.mit.edu/~drew/admissible_2000_17554.txt 17,554]
| [http://math.mit.edu/~drew/admissible_1783_15484.txt 15,484]
| [http://math.mit.edu/~drew/admissible_1000_8072.txt 8,072]
| [http://math.mit.edu/~drew/admissible_672_5196.txt 5,196]
| [http://math.mit.edu/~drew/admissible_632_4868.txt 4,868]
| [http://math.mit.edu/~drew/admissible_342_2416.txt 2,416]
|-
| Greedy-greedy sieve
| [http://math.mit.edu/~drew/admissible_4000_36756.txt 36,756]
| [http://math.mit.edu/~drew/admissible_3405_30750.txt 30,750]
| [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_1783_15036.txt 15,036]
| [http://math.mit.edu/~drew/admissible_1000_7854.txt 7,854]
| [http://math.mit.edu/~drew/admissible_672_5030.txt 5,030]
| [http://math.mit.edu/~drew/admissible_632_4710.txt 4,710]
| [http://math.mit.edu/~drew/admissible_342_2350.txt 2,350]
|-
| Engelsma data
| [http://www.opertech.com/primes/webdata/k4000-4507/k4000-4099/k4000_36622.txt 36,622]
| [http://www.opertech.com/primes/webdata/k3000-3999/k3400-3499/k3405_30606.txt 30,606]
| [http://www.opertech.com/primes/webdata/k3000-3999/k3000-3099/k3000_26622.txt 26,622]
| [http://www.opertech.com/primes/webdata/k2000-2999/k2000-2099/k2000_16978.txt 16,978]
| [http://www.opertech.com/primes/webdata/k1000-1999/k1000-1099/k1783_14958.txt 14,958]
| [http://www.opertech.com/primes/webdata/k1000-1999/k1000-1099/k1000_7802.txt 7,802]
| [http://www.opertech.com/primes/webdata/k2-999/k600-699/k672_4998.txt 4,998]
| [http://www.opertech.com/primes/webdata/k2-999/k600-699/k672_4680.txt 4,680]
| [http://www.opertech.com/primes/webdata/k2-999/k300-399/k342_2328.txt 2,328]
|-
|Best known tuple
| [http://math.mit.edu/~drew/admissible_4000_36610.txt 36,610]
| [http://math.mit.edu/~drew/admissible_3405_30600.txt 30,600]
| [http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_3000_26606_-29486.txt 26,606]
| [http://www.cs.cmu.edu/~xfxie/project/admissible/admissible_2000_16978_1108.txt 16,978]
| [http://math.mit.edu/~drew/admissible_1783_14950.txt 14,950]
| [http://math.mit.edu/~drew/admissible_1000_7802.txt 7,802]
| [http://math.mit.edu/~drew/admissible_672_4998.txt 4,998]
| [http://math.mit.edu/~drew/admissible_632_4680.txt '''4,680''']
| [http://math.mit.edu/~drew/admissible_342_2328.txt 2,328]
|-
! Predictions
|-
| <math>k_0 \log k_0 + k_0</math>
| 37,176
| 31,098
| 27,019
| 17,202
| 15,131
| 7,907
| 5,046
| 4,708
| 2,338
|-
! Lower bounds
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 23)
| 
| 
| 
| 
|
|
|
|
| 2,110
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 19)
| 
| 
| 
| 
|
|
|
| 4,080
| 2,096
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 17)
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23925 29,746]
| 25,328
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23925 21,884]
| 14,176
| 12,520
| 6,660
| 4,310
| 4,020
| 2,072
|-
|Inclusion-exclusion (<math>p_\text{exh}</math>= 13)
| 29,824
| 25,058
| 21,838
| 14,046
| 12,408
| 6,594
| 4,278
| 3,976
| 2,046
|-
|Partitioning
| 27,552
| 23,518
| 20,704
| 13,720
| 12,240
| 6,808
| [https://sites.google.com/site/avishaytal/files/Primes.pdf 4,574]
| 4,276
| [http://www.opertech.com/primes/k-tuples.html 2,328]
|-
|MV with <math>c=1</math> (conjectural)
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 22,564]
| 18,898
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 16,456]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,500]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,858]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 3,124]
|
| 1,454
|-
|MV with <math>c=3.2/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 22,523]
| 18,866
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 16,428]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,480]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,847]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 3,118]
|
| 1,450
|-
|MV with <math>c=\sqrt{22}/\pi</math>
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 21,701]
| 18,153
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 15,758]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,061]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,648]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 2,979]
|
| 1,361
|-
|Second Montgomery-Vaughan
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 21,690]
| 18,143
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 15,751]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 10,056]
|
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 4,645]
| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 2,977]
|
| 1,360
|-
|Brun-Titchmarsh
| 19,785
| 16,536
| 14,358
| 9,118
|
| 4,167
| 2,648
|
| 1,214
|-
|First Montgomery-Vaughan
| 18,768
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 18,859]
| 15,783
| 13,696
| 8,448
[http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23906 8,615]
|
| 3,959
| 2,558
|
| 1,191
|}


The '''bold number''' indicates the best currently known result for a twin-prime-like theorem.

For the Zhang tuples the minimal <math>m</math> that produced an admissible <math>k_0</math>-tuple was used.  In some cases one can achieve a smaller diameter using an <math>m</math> that is slightly larger than the minimal admissible value, as noted [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23917 here].

The shifted Schinzel tuples were generated with <math>y=2</math> using an optimally chosen interval contained in <math>[-k_0\log k_0, 2k_0\log k_0]</math> (the interval is not in every case guaranteed to be optimal, particularly for larger values of <math>k_0</math>, but it is believed to be so).

The greedy-greedy tuples were generated using Sutherland's original algorithm, breaking ties downward in every case (and the optimal interval in <math>[-k_0\log k_0, 2k_0\log k_0]</math> 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 lower bounds listed in the partitioning and inclusion-exclusion rows were computed as described by Avishay in Sections 1 resp.&nbsp;2 of this [https://sites.google.com/site/avishaytal/files/Primes.pdf document] (the case <math>k_0</math>=342 corresponds to the trivial partition). The partitioning method was strengthened by using [http://sbseminar.wordpress.com/2013/07/02/the-quest-for-narrow-admissible-tuples/#comment-24517 <math>H(343) \geq 2334</math>], [http://sbseminar.wordpress.com/2013/07/02/the-quest-for-narrow-admissible-tuples/#comment-24327 <math>H(370) \geq 2530</math>] and [http://sbseminar.wordpress.com/2013/07/02/the-quest-for-narrow-admissible-tuples/#comment-24327 <math>H(385) \geq 2656</math>] (a complete list of bounds for <math>k_0</math> up to 4,000,000 can be found [http://math.mit.edu/~drew/partition_bounds_342_plus_4000000.txt here]), and (for <math>k_0 \leq 10719</math>) certain [http://sbseminar.wordpress.com/2013/07/02/the-quest-for-narrow-admissible-tuples/#comment-24496 mod 6 considerations]. The inclusion-exclusion involved an exhaustive search (along http://sbseminar.wordpress.com/2013/07/02/the-quest-for-narrow-admissible-tuples/#comment-24513 these lines]) up to <math>p_\text{exh}</math>.