# Finding narrow admissible tuples

### From Polymath1Wiki

(→Benchmarks) |
(→Benchmarks) |
||

Line 281: | Line 281: | ||

| [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 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-23896 66,314] | ||

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 28,781] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 22,564] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [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 | + | | [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 | + | | [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 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 3,124] |

|- | |- | ||

|MV with <math>c=3.2/\pi</math> | |MV with <math>c=3.2/\pi</math> | ||

Line 296: | Line 296: | ||

| [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 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-23896 66,211] | ||

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 28,737] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 22,523] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [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 | + | | [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 | + | | [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 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 3,118] |

|- | |- | ||

|MV with <math>c=\sqrt{22}/\pi</math> | |MV with <math>c=\sqrt{22}/\pi</math> | ||

Line 311: | Line 311: | ||

| [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 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-23896 63,917] | ||

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 27,708] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 21,701] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [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 | + | | [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 | + | | [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 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 2,979] |

|- | |- | ||

|Second Montgomery-Vaughan | |Second Montgomery-Vaughan | ||

Line 326: | Line 326: | ||

| [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 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-23896 63,886] | ||

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 27,696] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 21,690] |

- | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 | + | | [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 | + | | [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 | + | | [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 | + | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23905 2,977] |

|- | |- | ||

|Brun-Titchmarsh | |Brun-Titchmarsh | ||

Line 339: | Line 339: | ||

| [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555] | | [http://sbseminar.wordpress.com/2013/06/05/more-narrow-admissible-sets/#comment-23777 155,555] | ||

| 137,756 | | 137,756 | ||

- | | | + | | 135,599 |

| 58,863 | | 58,863 | ||

| 25,351 | | 25,351 |

## Revision as of 01:21, 14 June 2013

For any natural number *k*_{0}, an *admissible k_{0}-tuple* is a finite set of integers of cardinality

*k*

_{0}which avoids at least one residue class modulo

*p*for each prime

*p*. (Note that one only needs to check those primes

*p*of size at most

*k*

_{0}, so this is a finitely checkable condition.) Let

*H*(

*k*

_{0}) denote the minimal diameter of an admissible

*k*

_{0}-tuple. As part of the Polymath8 project, we would like to find as good an upper bound on

*H*(

*k*

_{0}) as possible for given values of

*k*

_{0}. 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

*k*

_{0}log

*k*

_{0}+

*k*

_{0}for

*k*

_{0}in the range of interest.

## Contents |

## Upper bounds

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

### Zhang sieve

The Zhang sieve uses the tuple

where *m* is taken to optimize the diameter while staying admissible (in practice, this basically means making *m* as small as possible). Certainly any *m* with *p*_{m + 1} > *k*_{0} works (in particular, one can just take to be the first *k*_{0} primes past *k*_{0}, but this is not optimal. Applying the prime number theorem then gives the upper bound .

### Hensley-Richards sieve

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

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

### Asymmetric Hensley-Richards sieve

The asymmetric Hensley-Richard sieve uses the tuple

where *i* is an integer and *i*,*m* are optimised to minimize the diameter while staying admissible.

### Schinzel sieve

Given 0 < *y* < *z*, the Schinzel sieve (discussed in [HR1973], [CJ2001] first sieves by 1mod *p* for primes and by 0mod *p* for primes . For a given choice of *y*, the parameter *z* is minimized subject to ensuring that the first *k*_{0} survivors (after the first) form an admissible sequence , so the only free parameter is *y*, which is chosen to minimize the diameter of . The case *y* = 1 corresponds to a sieve of Eratosthenes, which will typically yield the same sequence as Zhang with the minimal (but not necessarily optimal) value of *m* that yields an admissible *k*_{0}-tuple. As originally proposed, the Schinzel sieve works over the positive integers, but one can apply the sieve to any given interval, and as with the Hensley-Richards sieve, it is generally better to use an asymmetric interval (which need not contain the origin).

### Greedy sieve

Within a given interval, one sieves a single residue class *a*mod *p* for increasing primes , with *a* chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize , maximize , minimize , or randomly. If not all residue classes modulo *p* are occupied by survivors, then *a* will be chosen so that no survivors are sieved.
This necessarily occurs once *p* exceeds the number of survivors but typically happens much sooner. One then chooses the narrowest *k*_{0}-tuple among the survivors (if there are fewer than *k*_{0} 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 *y* = 2 and and then continuing in a greedy fashion
This method was proposed by Sutherland and originally referred to as a "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 *z* that yields *k*_{0}-survivors), while a second optimization is to use a value of *z* that is intentionally smaller than necessary and switch to greedy sieving for primes greater than *z*. With the choice , unless the initial interval is much larger than necessary, all primes up to *z* will require a residue class to be sieved and the first "greedy" seldom applies.

### Seeded greedy sieve

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

### Iterated merging

Given an admissible *k*_{0}-tuple , one can attempt to improve it using an iterated merging approach suggested by Castryck. One first uses a greedy (or greedy-Schinzel) sieve to construct an admissible *k*_{0}-tuple in roughly the same interval as , then performs a randomized greedy sieve using the seed set to obtain an admissible *k*_{0}-tuple . If is narrower than , replace with , otherwise try again with a new .
Eventually the diameter of will become less than or equal to that of .
As long as , one can continue to attempt to improve , but in practice one stops after some number of retries.

As described by Sutherland, one can then replace with 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 , which is typically made wider than the minimal interval containing by a small factor δ on each side (Sutherland suggests δ = 0.0025), and the number of failed attempts allowed while attempting to impove .

Eventually this process will tend to converge to particular that it cannot improve (or more generally, a set of similar '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 initially contains at least two admissible *k*_{0}-tuples (typically many more), and as the algorithm proceeds the set converges toward and the number of admissible *k*_{0}-tuples it contains declines. One can regard the cardinality of the difference between and 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 ).

### Local optimizations

Let be an admissible *k*_{0}-tuple with endpoints *h*_{1} and , and let be the interval . If there exists an integer such that removing one of 's endpoints and inserting *h* yields an admissible *k*_{0}-tuple , then call *contractible*, and if not, say that non-contractible. Note that necessarily has smaller diameter than . Any of the sieving methods described above may produce admissible *k*_{0}-tuples that are contractible, so it is worth testing for contractibility as a post-processing step after sieving and replacing by if this test succeeds.

We can also *shift* to the left by removing its right end point and replacing it with the greatest integer *h*_{0} < *h*_{1} that yields an admissible *k*_{0}-tuple , and we can similarly shift to the right. The diameter of need not be less than , but if it is, it provides a useful replacement. More generally, by shifting repeatedly we can produce a sequence of admissible *k*_{0}-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 with smaller diameter than .

A more sophisticated local optimization involves a process of ``adjustment" proposed by Savitt.
Let be an admissible *k*_{0}-tuple.
For a prime *p* and an integer *a*, let [*a*;*p*] denote the residue class *a*mod *p*, i.e. the set of integers {*x*:*x* = *a*mod *p*}.
Call [*a*;*p*] occupied if it contains an element of .

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

The admissible set lies in the interval containing , so its diameter is no greater than that of , however its cardinality may differ. If it happens that contains more elements than , then by eliminating points at either end of we obtain an admissible *k*_{0}-tuple that is narrower than and may ``adjust" by replacing it with .
The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible *k*_{0}-tuples.

### Further refinements

## Lower bounds

There is a substantial amount of literature on bounding the quantity π(*x* + *y*) − π(*x*), the number of primes in a shifted interval [*x* + 1,*x* + *y*], where *x*,*y* are natural numbers. As a general rule, whenever a bound of the form

- (*)

is established for some function *F*(*y*) of *y*, the method of proof also gives a bound of the form

- (**)

Indeed, if one assumes the prime tuples conjecture, any admissible *k*_{0}-tuple of diameter *H* can be translated into an interval of the form [*x* + 1,*x* + *H* + 1] for some *x*. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for *x* > *y*, the set of primes between *x* + 1 and *x* + *y* 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

which then gives the lower bound

- .

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

### First Montgomery-Vaughan large sieve inequality

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

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

### Second Montgomery-Vaughan large sieve inequality

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

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

## Benchmarks

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

k_{0} | 3,500,000 | 181,000 | 34,429 | 26,024 | 23,283 | 22,949 | 10,719 | 5,000 | 4,000 | 3,000 | 2,000 | 1,000 | 672 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Upper bounds | |||||||||||||

First k_{0} primes past k_{0}
| 59,874,594 | 2,530,338 | 420,878 | 310,134 | 275,082 | 270,698 | 117,714 | 50,840 | 39,660 | 28,972 | 18,386 | 8,424 | 5,406 |

Zhang sieve | 59,093,364 | 2,486,370 | 411,932 | 303,558 | 268,536 | 264,414 | 114,806 | 49,578 | 38,596 | 28,008 | 17,766 | 8,212 | 5,216 |

Hensley-Richards sieve | 57,554,086 | 2,422,558 | 402,790 | 297,454 | 262,794 | 258,780 | 112,868 | 48,634 | 38,498 | 27,806 | 17,726 | 8,258 | 5,314 |

Asymmetric Hensley-Richards | 2,418,054 | 401,700 | 296,154 | 262,286 | 258,302 | 112,562 | 48,484 | 37,932 | 27,638 | 17,676 | 8,168 | 5,220 | |

Schinzel sieve | 2,413,228 | 400,512 | 295,162 | 262,206 | 258,000 | 112,440 | 48,726 | 38,168 | 27,632 | 17,616 | 8,160 | 5,196 | |

greedy-Schinzel sieve | 2,326,476 | 388,076 | 286,308 | 253,968 | 249,992 | 108,694 | 46,968 | 36,756 | 26,754 | 17,054 | 7,854 | 5,030 | |

Best known tuple | 57,554,086 | 2,326,476 | 386,532 | 285,210 | 252,804 | 248,910 | 108,462 | 46,824 | 36,636* | 26,622 | 16,984* | 7,808* | 5,010* |

Engelsma data | - | - | - | - | - | - | - | - | 36,622 | 26,622 | 16,978 | 7,802 | 4,998 |

Predictions | |||||||||||||

k_{0}logk_{0} + k_{0}
| 56,238,957 | 2,372,232 | 394,096 | 290,604 | 257,405 | 253,381 | 110,119 | 47,586 | 37,176 | 27,019 | 17,202 | 7,907 | 5,046 |

Lower bounds | |||||||||||||

MV with c = 1 (conjectural)
| 234,872 | 173,420 | 153,691 | 151,298 | 66,314 | 28,781 | 22,564 | 16,456 | 10,500 | 4,858 | 3,124 | ||

MV with c = 3.2 / π
| 234,529 | 173,140 | 153,447 | 151,056 | 66,211 | 28,737 | 22,523 | 16,428 | 10,480 | 4,847 | 3,118 | ||

MV with | 227,078 | 167,860 | 148,719 | 146,393 | 63,917 | 27,708 | 21,701 | 15,758 | 10,061 | 4,648 | 2,979 | ||

Second Montgomery-Vaughan | 226,987 | 167,793 | 148,656 | 146,338 | 63,886 | 27,696 | 21,690 | 15,751 | 10,056 | 4,645 | 2,977 | ||

Brun-Titchmarsh | 30,137,225 | 1,272,083 | 211,046 | 155,555 | 137,756 | 135,599 | 58,863 | 25,351 | 19,785 | 14,358 | 9,118 | 4,167 | 2,648 |

First Montgomery-Vaughan | 196,729
196,719 | 145,711
145,461 | 128,971 | 55,149 | 24,012 | 18,768 | 13,696 | 8,448 | 3,959 | 2,558 |

* 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 *k*_{0}, but are not as narrow as the literally best known tuples (due to Engelsma).

The Schinzel tuples were generated with *y* = 2 using an optimally chosen interval (the interval is not in every case guaranteed to be optimal, particularly for larger values of *k*_{0}, but it is believed to be so).

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 noted by Castryck, breaking ties upward may produce better results in some cases. As with the Schinzel tuples, the chosen intervals are not guaranteed to be optimal but are believed to be so.