Finding narrow admissible tuples

From Polymath1Wiki

(Difference between revisions)
Jump to: navigation, search
(Benchmarks)
(Benchmarks)
Line 258: Line 258:
|  
|  
|
|
-
|  
+
| 226,104
| 200,852
| 200,852
| 197,874
| 197,874

Revision as of 08:24, 5 September 2013

For any natural number k0, an admissible k0-tuple is a finite set {\mathcal H} of integers of cardinality k0 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 k0, so this is a finitely checkable condition.) Let H(k0) denote the minimal diameter \max {\mathcal H} - \min {\mathcal H} of an admissible k0-tuple. As part of the Polymath8 project, we would like to find as good an upper bound on H(k0) as possible for given values of k0. 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 k0logk0 + k0 for k0 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

{\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}

where m is minimized subject to staying admissible. Any m with pm + 1 > k0 yields an admissible tuple; in particular, one can just take {\mathcal H} to be the first k0 primes past k0, but this is not optimal. Applying the prime number theorem then gives the upper bound H \leq (1+o(1)) k_0\log k_0.

Hensley-Richards sieve

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

{\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}\}

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

Asymmetric Hensley-Richards sieve

The asymmetric Hensley-Richard sieve uses the tuple

{\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}\}

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

Schinzel sieve

Given 0 < y < z < x, the Schinzel sieve (discussed in [S1961], [HR1973], [GR1998], [CJ2001]) sieves the interval [1,x] by 1mod p for primes p \le y and by 0mod p for primes y < p \le z. Provided that z is large enough (z = k0 clearly suffices), the first k0 survivors form an admissible k0-tuple (but not necessarily the narrowest one in the interval). The case y = 1 corresponds to a sieve of Eratosthenes; if one minimizes z and takes the first k0 survivors greater than 1, this yields the same admissible k0 tuple as Zhang, with the minimal possible value of m.

Shifted Schinzel sieve

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

Greedy sieve

Within a given interval, one sieves a single residue class amod p for increasing primes p=2,3,5,\ldots, with a chosen to maximize the number of survivors. Ties can be broken in a number of ways: minimize a\in[0,p-1], maximize a\in [0,p-1], minimize |a-\lfloor p/2\rfloor|, 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 k0-tuple {\mathcal H} among the survivors (if there are fewer than k0 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 [s,\ s+x] using y = 2 and z = \sqrt{x} and then continuing in a greedy fashion, as proposed by Sutherland. One first optimizes the shift value s over some larger interval (e.g. [-k_0\log\ k_0,\ k_0\log\ k_0]) and then continues the sieving over primes p > z 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 [0,\ p-1]).

Seeded greedy sieve

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

Iterated merging

Given an admissible k0-tuple \mathcal{H}_1, 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 k0-tuple \mathcal{H}_2 in roughly the same interval as \mathcal{H}_1, then performs a randomized greedy sieve using the seed set \mathcal{S} = \mathcal{H}_1 \cup \mathcal{H}_2 to obtain an admissible k0-tuple \mathcal{H}_3. If \mathcal{H}_3 is narrower than \mathcal{H}_2, replace \mathcal{H}_2 with \mathcal{H}_3, otherwise try again with a new \mathcal{H}_3. Eventually the diameter of \mathcal{H}_2 will become less than or equal to that of \mathcal{H}_1. As long as \mathcal{H}_1\ne \mathcal{H}_2, one can continue to attempt to improve \mathcal{H}_2, but in practice one stops after some number of retries.

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

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

Local optimizations

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

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


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

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 \mathcal U be the intersection of \mathcal H with [a;p] \cup [b;q], and let \mathcal V be a subset of the integers that lie in the intersection of the interval I containing H and the set [a';p] \cup [b';q] such that the set \mathcal H' formed by removing the elements of \mathcal U from \mathcal H and adding the elements of \mathcal V is admissible. A necessary (and often sufficient) condition for and integer v to lie in \mathcal V 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 \mathcal H' lies in the interval \mathcal I containing \mathcal H, so its diameter is no greater than that of \mathcal H, however its cardinality may differ. If it happens that \mathcal H' contains more elements than \mathcal H , then by eliminating points at either end of \mathcal H' we obtain an admissible k0-tuple that is narrower than \mathcal H and may ``adjust" \mathcal H by replacing it with \mathcal H' . The process of adjustment can often be applied repeatedly, yielding a sequence of successively narrower admissible k0-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

 \pi(x+y) - \pi(x) \leq F(y) (*)

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

 k_0 \leq F( H(k_0)+1 ). (**)

Indeed, if one assumes the prime tuples conjecture, any admissible k0-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

 \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}

which then gives the lower bound

 H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0.

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

 k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.

First Montgomery-Vaughan large sieve inequality

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

 k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2

for any Q > 1, which is a parameter that one can optimise over (the optimal value is comparable to H(k0)1 / 2).

Second Montgomery-Vaughan large sieve inequality

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

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

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 \sqrt{22}/\pi [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.

k0 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 k0 primes past k0 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 59,093,364 4,923,060 2,486,370 411,946 303,558 268,544 264,460 114,814 73,448 64,182 54,488 49,578
Hensley-Richards sieve 57,554,086 4,802,222 2,422,558 402,790 297,454 262,794 258,780 112,868 72,538 63,708 53,654 48,634
Asymmetric Hensley-Richards 57,480,832 4,788,240 2,418,054 401,700 296,154 262,286 258,302 112,562 72,062 62,900 53,278 48,484
Shifted Schinzel sieve 56,789,070 4,740,846 2,396,594 399,248 294,810 260,714 256,702 112,200 71,930 62,892 53,236 48,472
Greedy-greedy sieve 55,233,744 4,603,276 2,326,458 388,076 286,308 253,968 249,992 108,694 69,564 60,942 51,688 46,968
Best known tuple 55,233,504 4,597,926 2,323,344 386,344 285,102 252,720 248,816 108,440 69,280 60,726 51,526 46,806
Predictions
k0logk0 + k0 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 (pexh= 19) 226,104 200,852 197,874 87,690 56,726 49,794 42,494 38,710
Inclusion-exclusion (pexh= 17) 301,864 224,100 198,998 195,962 86,940 56,238 49,356 42,114 38,342
Inclusion-exclusion (pexh= 13) 29,508,018 3,298,126 1,703,774 297,726 221,266 196,562 193,578 85,954 55,614 48,858 41,648 37,920
Partitioning (pexh= 7) 2,365,090 1,252,938 238,264 180,094 161,092 158,802 74,160 49,320 43,688 37,630 34,590
Partitioning (pexh= 5) 2,364,700 1,252,726 238,222 180,064 161,062 158,776 74,150 49,312 43,684 37,630 34,590
MV with c = 1 (conjectural) 32,503,908 2,751,677 1,395,694 234,872 173,420 153,691 151,298 66,314 42,551 37,274 31,644 28,781
MV with c = 3.2 / π 32,469,985 2,748,330 1,393,869 234,529 173,140 153,447 151,056 66,211 42,471 37,207 31,584 28,737
MV with c=\sqrt{22}/\pi 31,765,216 2,677,851 1,357,096 227,078 167,860 148,719 146,393 63,917 40,946 35,903 30,478 27,708
Second Montgomery-Vaughan 31,756,667 2,676,967 1,356,644 226,987 167,793 148,656 146,338 63,886 40,929 35,887 30,463 27,696
Brun-Titchmarsh 30,137,225 2,517,690 1,272,083 211,046 155,555 137,756 135,599 58,863 37,610 32,916 27,910 25,351
First Montgomery-Vaughan 28,080,007 2,342,969 1,184,954 197,096 145,711 128,971 126,931 55,178 35,235 30,982 26,388 24,037


k0 4,000 3,405 3,000 2,000 1,783 1,000 672 632 342
Upper bounds
First k0 primes past k0 39,660 33,222 28,972 18,386 16,174 8,424 5,406 5,028 2,472
Zhang sieve 38,596 32,296 28,008 17,766 15,620 8,218 5,216 4,860 2,416
Hensley-Richards sieve 38,498 31,820 27,806 17,726 15,756 8,258 5,314 4,918 2,446
Asymmetric Hensley-Richards 37,932 31,762 27,638 17,676 15,470 8,168 5,220 4,876 2,424
Shifted Schinzel sieve 38,006 31,910 27,600 17,554 15,484 8,072 5,196 4,868 2,416
Greedy-greedy sieve 36,756 30,750 26,754 17,054 15,036 7,854 5,030 4,710 2,350
Engelsma data 36,622 30,606 26,622 16,978 14,958 7,802 4,998 4,680 2,328
Best known tuple 36,610 30,600 26,606 16,978 14,950 7,802 4,998 4,680 2,328
Predictions
k0logk0 + k0 37,176 31,098 27,019 17,202 15,131 7,907 5,046 4,708 2,338
Lower bounds
Inclusion-exclusion (pexh= 23) 30,560 25,734 22,432 14,410 12,678 6,696 4,374 4,104 2,110
Inclusion-exclusion (pexh= 19) 30,366 25,566 22,284 14,332 12,614 6,672 4,344 4,080 2,096
Inclusion-exclusion (pexh= 17) 30,132 25,328 22,086 14,176 12,522 6,660 4,310 4,020 2,072
Inclusion-exclusion (pexh= 13) 29,824 25,058 21,838 14,046 12,408 6,594 4,278 3,976 2,046
Partitioning (pexh= 7) 27,556 23,524 20,704 13,724 12,244 6,810 4,574 4,276 2,328
Partitioning (pexh= 5) 27,556 23,524 20,704 13,722 12,244 6,808 4,574 4,276 2,328
MV with c = 1 (conjectural) 22,564 18,898 16,456 10,500 9,253 4,858 3,124 2,919 1,454
MV with c = 3.2 / π 22,523 18,866 16,428 10,480 9,236 4,847 3,118 2,913 1,450
MV with c=\sqrt{22}/\pi 21,701 18,153 15,758 10,061 8,850 4,648 2,979 2,778 1,361
Second Montgomery-Vaughan 21,690 18,143 15,751 10,056 8,845 4,645 2,977 2,776 1,360
Brun-Titchmarsh 19,785 16,536 14,358 9,118 8,013 4,167 2,648 2,468 1,214
First Montgomery-Vaughan 18,859 15,783 13,696 8,615 7,547 3,959 2,558 2,392 1,191


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

For the Zhang tuples the minimal m that produced an admissible k0-tuple was used. In some cases one can achieve a smaller diameter using an m that is slightly larger than the minimal admissible value, as noted here.

The shifted Schinzel tuples were generated with y = 2 using an optimally chosen interval contained in [ − k0logk0,2k0logk0] (the interval is not in every case guaranteed to be optimal, particularly for larger values of k0, 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 [ − k0logk0,2k0logk0] was selected on this basis). As 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. 2 of this document (the case k0=342 corresponds to the trivial partition). The partitioning method was strengthened by using H(343) \geq 2334, H(370) \geq 2530 and H(385) \geq 2656 (a complete list of bounds for k0 up to 4,000,000 can be found here), and (for k_0 \leq 341640) by combining the partition method with sieving for primes up to pexh, as described here. The inclusion-exclusion involved an exhaustive search (along these lines) up to pexh, using the inclusion-exclusion set of primes greater than pexh and less than the first prime where the depth-2 inclusion-exclusion bound is no longer positive.

Personal tools