Finding optimal k0 values: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
No edit summary |
|||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
This is a sub-page for the Polymath8 project "[[bounded gaps between primes]]". | This is a sub-page for the Polymath8 project "[[bounded gaps between primes]]". | ||
* <math>~k_0~</math> (<math>~k_0 \ge 2, k_0 \in \Z~</math>) is a quantity such that every admissible <math>~k_0</math>-tuple has infinitely many translates which each contain at least two primes. | * <math>~k_0~</math> (<math>~k_0 \ge 2, k_0 \in \Z~</math>) is a quantity such that every admissible <math>~k_0</math>-tuple has infinitely many translates which each contain at least two primes. It is then used for [[finding narrow admissible tuples]]. | ||
* <math>\text{MPZ}^{(i)}[\varpi,\delta]</math> holds for some combinations of <math>c_\varpi, c_\delta</math>, and <math>~i~</math> values, where <math>i \ge 1</math> means <math>~i</math>-tuply densely divisible, <math>c_\varpi > 0</math> and <math>~c_\delta > 0~</math> are constants in the constraint on <math>\varpi</math> and <math>~\delta~</math>, such that <math>c_{\varpi}\varpi+c_{\delta}\delta<1</math>. | * <math>\text{MPZ}^{(i)}[\varpi,\delta]</math> holds for some combinations of <math>c_\varpi, c_\delta</math>, and <math>~i~</math> values, where <math>i \ge 1</math> means <math>~i</math>-tuply densely divisible, <math>c_\varpi > 0</math> and <math>~c_\delta > 0~</math> are constants in the constraint on <math>\varpi</math> and <math>~\delta~</math>, such that <math>c_{\varpi}\varpi+c_{\delta}\delta<1</math>. | ||
| Line 46: | Line 46: | ||
== Benchmarks == | == Benchmarks == | ||
The following table provides the results with clean parameter values for the best currently known instances of <math>c_\varpi, c_\delta, i</math> values, respectively without and with using Deligne's theorem. | |||
{| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | {| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | ||
|+ ''' | |+ '''Clean results at <math>k_0 = k_0^{opt}</math> for the best currently known instances of <math>c_\varpi, c_\delta, i</math> values.''' | ||
|- | |- | ||
!colspan="3" | Instance | !colspan="3" | Instance | ||
| Line 86: | Line 88: | ||
| With Deligne's theorem | | With Deligne's theorem | ||
|} | |} | ||
The following table provides the results with minimized parameter values at <math>k_0 = k_0^{opt}</math> for some instances of <math>c_\varpi, c_\delta, i</math> values. | |||
{| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | {| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | ||
| Line 212: | Line 216: | ||
| -5.0940E-06 | | -5.0940E-06 | ||
|} | |} | ||
The following table provides the "unsatisfied" results with minimized parameter values at <math>k_0=(k_0^{opt}-1)</math> for some instances of <math>c_\varpi, c_\delta, i</math> values. Note that the results of these <math>k_0</math> values do not satisfy all constraints, as indicated from the positive objective values. | |||
{| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | {| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | ||
|+ '''" | |+ '''"Unsatisfied" optimal results at <math>k_0=(k_0^{opt}-1)</math> for some instances of <math>c_\varpi, c_\delta, i</math> values.''' | ||
|- | |- | ||
!colspan="3" | Instance | !colspan="3" | Instance | ||
| Line 338: | Line 344: | ||
| 4.0614E-05 | | 4.0614E-05 | ||
|} | |} | ||
The following table provides the results with minimized parameter values at <math>k_0=(k_0^{opt}-1)</math> for some instances of <math>c_\varpi, c_\delta, i</math> values, with an additional condition that <math>\left(1- \frac{j_{k_0-2}^2}{k_0(k_0-1)(1 + 4 \varpi)}\right) \ge 0</math>. Note that these <math>k_0</math> values are more unsatisfied, as indicated from the larger positive objective values that that in the previous table. | |||
{| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | {| class="wikitable" border=1 style="margin: 1em auto 1em auto;" | ||
|+ | |+ '''More conservative "unsatisfied" results at <math>k_0=(k_0^{opt}-1)</math> for some instances of <math>c_\varpi, c_\delta, i</math> values.''' | ||
|- | |- | ||
!colspan="3" | Instance | !colspan="3" | Instance | ||
| Line 497: | Line 506: | ||
| 19 | | 19 | ||
|} | |} | ||
== Code and data == | |||
* [http://www.cs.cmu.edu/~xfxie/software/K0Finder.zip Code for finding optimal <math> k_0</math> values]: Java, bash, and maple are needed. | |||
Latest revision as of 15:14, 20 October 2013
This is a sub-page for the Polymath8 project "bounded gaps between primes".
- [math]\displaystyle{ ~k_0~ }[/math] ([math]\displaystyle{ ~k_0 \ge 2, k_0 \in \Z~ }[/math]) is a quantity such that every admissible [math]\displaystyle{ ~k_0 }[/math]-tuple has infinitely many translates which each contain at least two primes. It is then used for finding narrow admissible tuples.
- [math]\displaystyle{ \text{MPZ}^{(i)}[\varpi,\delta] }[/math] holds for some combinations of [math]\displaystyle{ c_\varpi, c_\delta }[/math], and [math]\displaystyle{ ~i~ }[/math] values, where [math]\displaystyle{ i \ge 1 }[/math] means [math]\displaystyle{ ~i }[/math]-tuply densely divisible, [math]\displaystyle{ c_\varpi \gt 0 }[/math] and [math]\displaystyle{ ~c_\delta \gt 0~ }[/math] are constants in the constraint on [math]\displaystyle{ \varpi }[/math] and [math]\displaystyle{ ~\delta~ }[/math], such that [math]\displaystyle{ c_{\varpi}\varpi+c_{\delta}\delta\lt 1 }[/math].
Optimization Model
For a given set of [math]\displaystyle{ c_\varpi, c_\delta, i }[/math], the basic optimization model is defined as:
[math]\displaystyle{ \text{minimize}~~k_0~ }[/math]
[math]\displaystyle{ \text{subject to:}~ }[/math]
- [math]\displaystyle{ 2(\kappa_1+\kappa_2+\kappa_3) \lt \left(1- \frac{j_{k_0-2}^2}{k_0(k_0-1)(1 + 4 \varpi)}\right) }[/math]
- [math]\displaystyle{ c_\varpi \varpi + c_\delta \delta \lt 1, }[/math]
- [math]\displaystyle{ 0 \lt \varpi \lt 1/4, }[/math]
- [math]\displaystyle{ 0 \lt \delta \leq \delta' \lt \frac{1}{4} + \varpi, }[/math]
- [math]\displaystyle{ A \ge 0, }[/math]
[math]\displaystyle{ \text{where}~ }[/math]
- [math]\displaystyle{ \kappa_1 := \int_{\theta}^1 (1-t)^{(k_0-1)/2} \frac{dt}{t} }[/math]
- [math]\displaystyle{ \kappa_2 := (k_0-1) \int_{\theta}^1 (1-t)^{k_0-1} \frac{dt}{t} }[/math]
- [math]\displaystyle{ \kappa_3 := \tilde \theta \frac{J_{k_0-2}(\sqrt{\tilde \theta} j_{k_0-2})^2 - J_{k_0-3}(\sqrt{\tilde \theta} j_{k_0-2}) J_{k_0-1}(\sqrt{\tilde \theta} j_{k_0-2})}{ J_{k_0-3}(j_{k_0-2})^2 } \exp( A + (k_0-1) \int_{\tilde \delta}^\theta e^{-(A+2\alpha)t} \frac{dt}{t} ) }[/math]
- [math]\displaystyle{ \alpha := \frac{j_{k_0-2}^2}{4(k_0-1)} }[/math]
- [math]\displaystyle{ \theta := \frac{\delta'}{1/4 + \varpi} }[/math]
- [math]\displaystyle{ \tilde \theta := \frac{(i\delta' - \delta)/2 + \varpi}{1/4 + \varpi} }[/math]
- [math]\displaystyle{ \tilde \delta := \frac{\delta}{1/4 + \varpi} }[/math]
and [math]\displaystyle{ \varpi, \delta, \delta', A }[/math] are parameters to be optimized.
More details are described in the page on Dickson-Hardy-Littlewood theorems.
Benchmarks
The following table provides the results with clean parameter values for the best currently known instances of [math]\displaystyle{ c_\varpi, c_\delta, i }[/math] values, respectively without and with using Deligne's theorem.
| Instance | [math]\displaystyle{ k_0^{*} }[/math] | [math]\displaystyle{ ~k_0~ }[/math] | Parameters | Error Terms | Comment | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [math]\displaystyle{ c_{\varpi} }[/math] | [math]\displaystyle{ ~c_{\delta}~ }[/math] | [math]\displaystyle{ ~i~ }[/math] | [math]\displaystyle{ \varpi }[/math] | [math]\displaystyle{ ~\delta~ }[/math] | [math]\displaystyle{ ~\delta'~ }[/math] | [math]\displaystyle{ ~A~ }[/math] | [math]\displaystyle{ ~\kappa_1~ }[/math] | [math]\displaystyle{ ~\kappa_2~ }[/math] | [math]\displaystyle{ ~\kappa_3~ }[/math] | |||
| 168 | 48 | 2 | 1781 | 1783 | 5.950000E-03 | 1E-05 | 1/300 | 800 | 6.662E-07 | 5.209E-09 | 8.340E-47 | Without Deligne's theorem |
| 600/7 | 180/7 | 4 | 630 | 632 | 1.163666E-02 | 1E-04 | 1/105 | 200 | 6.445E-06 | 1.752E-08 | 7.018E-08 | With Deligne's theorem |
The following table provides the results with minimized parameter values at [math]\displaystyle{ k_0 = k_0^{opt} }[/math] for some instances of [math]\displaystyle{ c_\varpi, c_\delta, i }[/math] values.
| Instance | [math]\displaystyle{ k_0^{*} }[/math] | [math]\displaystyle{ ~k_0~ }[/math] | Parameters | Error Terms | Objective | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [math]\displaystyle{ c_{\varpi} }[/math] | [math]\displaystyle{ ~c_{\delta}~ }[/math] | [math]\displaystyle{ ~i~ }[/math] | [math]\displaystyle{ \varpi }[/math] | [math]\displaystyle{ ~\delta~ }[/math] | [math]\displaystyle{ ~\delta'~ }[/math] | [math]\displaystyle{ ~A~ }[/math] | [math]\displaystyle{ ~\kappa_1~ }[/math] | [math]\displaystyle{ ~\kappa_2~ }[/math] | [math]\displaystyle{ ~\kappa_3~ }[/math] | |||
| 348 | 68 | 1 | 5446 | 5447 | 2.8733351E-03 | 1.1672627E-06 | 1.4961657E-03 | 2559.258877 | 5.59E-09 | 1.50E-12 | 6.02E-11 | -1.1882E-06 |
| 168 | 48 | 2 | 1781 | 1783 | 5.9495534E-03 | 9.8965035E-06 | 3.7117059E-03 | 757.8242621 | 1.58E-07 | 3.24E-10 | 3.65E-09 | -5.9684E-06 |
| 148 | 33 | 1 | 1465 | 1466 | 6.7542244E-03 | 1.1357314E-05 | 4.7101572E-03 | 626.6135921 | 8.79E-08 | 8.57E-11 | 3.63E-09 | -2.2867E-06 |
| 140 | 32 | 1 | 1345 | 1346 | 7.1398444E-03 | 1.3180858E-05 | 5.0540952E-03 | 577.7849932 | 1.10E-07 | 1.22E-10 | 4.75E-09 | -6.7812E-06 |
| 116 | 30 | 1 | 1006 | 1007 | 8.6150244E-03 | 2.1905745E-05 | 6.4310210E-03 | 408.9674914 | 2.29E-07 | 3.76E-10 | 1.20E-08 | -6.2561E-06 |
| 108 | 30 | 1 | 901 | 902 | 9.2518776E-03 | 2.6573843E-05 | 7.0318847E-03 | 359.6376563 | 3.08E-07 | 6.00E-10 | 1.76E-08 | -1.0924E-05 |
| 280/3 | 80/3 | 2 | 719 | 720 | 1.0699851E-02 | 5.0521044E-05 | 8.0398983E-03 | 260.2624368 | 1.04E-06 | 4.98E-09 | 4.33E-08 | -5.5687E-06 |
| 600/7 | 180/7 | 4 | 630 | 632 | 1.1639206E-02 | 9.1536798E-05 | 8.3866560E-03 | 194.5246551 | 3.01E-06 | 3.40E-08 | 9.89E-08 | -5.0940E-06 |
The following table provides the "unsatisfied" results with minimized parameter values at [math]\displaystyle{ k_0=(k_0^{opt}-1) }[/math] for some instances of [math]\displaystyle{ c_\varpi, c_\delta, i }[/math] values. Note that the results of these [math]\displaystyle{ k_0 }[/math] values do not satisfy all constraints, as indicated from the positive objective values.
| Instance | [math]\displaystyle{ k_0^{*} }[/math] | [math]\displaystyle{ ~k_0~ }[/math] | Parameters | Error Terms | Objective | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [math]\displaystyle{ c_{\varpi} }[/math] | [math]\displaystyle{ ~c_{\delta}~ }[/math] | [math]\displaystyle{ ~i~ }[/math] | [math]\displaystyle{ \varpi }[/math] | [math]\displaystyle{ ~\delta~ }[/math] | [math]\displaystyle{ ~\delta'~ }[/math] | [math]\displaystyle{ ~A~ }[/math] | [math]\displaystyle{ ~\kappa_1~ }[/math] | [math]\displaystyle{ ~\kappa_2~ }[/math] | [math]\displaystyle{ ~\kappa_3~ }[/math] | |||
| 348 | 68 | 1 | 5446 | 5446 | 2.8733354E-03 | 1.1660200E-06 | 1.4880084E-03 | 2552.313151 | 6.16E-09 | 1.81E-12 | 1.00E-10 | 1.7550E-07 |
| 168 | 48 | 2 | 1781 | 1782 | 5.9495511E-03 | 9.9043741E-06 | 3.7130742E-03 | 757.3673135 | 1.59E-07 | 3.26E-10 | 3.21E-09 | 2.5064E-06 |
| 148 | 33 | 1 | 1465 | 1465 | 6.7542239E-03 | 1.1359571E-05 | 4.7002144E-03 | 625.1479808 | 9.16E-08 | 9.27E-11 | 3.28E-09 | 9.3639E-06 |
| 140 | 32 | 1 | 1345 | 1345 | 7.1398419E-03 | 1.3191801E-05 | 5.0550954E-03 | 567.8210511 | 1.11E-07 | 1.24E-10 | 4.65E-10 | 6.6029E-06 |
| 116 | 30 | 1 | 1006 | 1006 | 8.6150194E-03 | 2.1925014E-05 | 6.4287825E-03 | 408.5511082 | 2.33E-07 | 3.89E-10 | 1.24E-08 | 1.5183E-05 |
| 108 | 30 | 1 | 901 | 901 | 9.2518661E-03 | 2.6615167E-05 | 7.0404135E-03 | 359.5845846 | 3.08E-07 | 5.97E-10 | 1.68E-08 | 1.4703E-05 |
| 280/3 | 80/3 | 2 | 719 | 719 | 1.0699822E-02 | 5.0626919E-05 | 8.0520479E-03 | 259.8370595 | 1.04E-06 | 4.96E-09 | 4.46E-08 | 3.1365E-05 |
| 600/7 | 180/7 | 4 | 630 | 631 | 1.1639134E-02 | 9.1775130E-05 | 8.3989836E-03 | 193.9881059 | 3.02E-06 | 3.40E-08 | 1.00E-07 | 4.0614E-05 |
The following table provides the results with minimized parameter values at [math]\displaystyle{ k_0=(k_0^{opt}-1) }[/math] for some instances of [math]\displaystyle{ c_\varpi, c_\delta, i }[/math] values, with an additional condition that [math]\displaystyle{ \left(1- \frac{j_{k_0-2}^2}{k_0(k_0-1)(1 + 4 \varpi)}\right) \ge 0 }[/math]. Note that these [math]\displaystyle{ k_0 }[/math] values are more unsatisfied, as indicated from the larger positive objective values that that in the previous table.
| Instance | [math]\displaystyle{ k_0^{*} }[/math] | [math]\displaystyle{ ~k_0~ }[/math] | Parameters | Error Terms | Objective | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [math]\displaystyle{ c_{\varpi} }[/math] | [math]\displaystyle{ ~c_{\delta}~ }[/math] | [math]\displaystyle{ ~i~ }[/math] | [math]\displaystyle{ \varpi }[/math] | [math]\displaystyle{ ~\delta~ }[/math] | [math]\displaystyle{ ~\delta'~ }[/math] | [math]\displaystyle{ ~A~ }[/math] | [math]\displaystyle{ ~\kappa_1~ }[/math] | [math]\displaystyle{ ~\kappa_2~ }[/math] | [math]\displaystyle{ ~\kappa_3~ }[/math] | |||
| 168 | 48 | 2 | 1781 | 1782 | 5.9501100E-03 | 7.9483333E-06 | 1.9082658E-03 | 777.7015422 | 1.68E-04 | 2.02E-04 | 9.81E-06 | 7.6073E-04 |
| 600/7 | 180/7 | 4 | 630 | 631 | 1.1648112E-02 | 6.1848056E-05 | 4.2588144E-03 | 222.5549310 | 9.33E-04 | 1.79E-03 | 1.02E-04 | 5.6566E-03 |
Lower Bounds
For each [math]\displaystyle{ ~c_\varpi }[/math], a theoretical lower bound of [math]\displaystyle{ ~k_0 }[/math], called [math]\displaystyle{ k_0^* }[/math], can be obtained by assuming that all error terms [math]\displaystyle{ ~\kappa_1 }[/math], [math]\displaystyle{ ~\kappa_2 }[/math], and [math]\displaystyle{ ~\kappa_3 }[/math] could be completely ignored. This table gives the computational results of [math]\displaystyle{ k_0^* }[/math] for [math]\displaystyle{ c_\varpi \lt 87 }[/math].
| [math]\displaystyle{ ~c_\varpi~ }[/math] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 80 | 566 | 577 | 588 | 599 | 611 | 622 | 633 | - | - | - |
| 70 | 460 | 470 | 481 | 491 | 502 | 512 | 523 | 533 | 544 | 555 |
| 60 | 362 | 372 | 381 | 391 | 400 | 410 | 420 | 430 | 440 | 450 |
| 50 | 273 | 281 | 290 | 299 | 307 | 316 | 325 | 334 | 343 | 353 |
| 40 | 193 | 200 | 208 | 216 | 223 | 231 | 239 | 248 | 256 | 264 |
| 30 | 123 | 129 | 136 | 143 | 149 | 156 | 163 | 171 | 178 | 185 |
| 20 | 65 | 70 | 76 | 81 | 87 | 92 | 98 | 104 | 110 | 117 |
| 10 | 22 | 26 | 30 | 33 | 38 | 42 | 46 | 51 | 55 | 60 |
| 00 | - | - | - | - | 6 | 8 | 10 | 13 | 16 | 19 |
Code and data
- Code for finding optimal [math]\displaystyle{ k_0 }[/math] values: Java, bash, and maple are needed.
