Maximal gaps between prime k-tuples

© 2011-2013 by Alexei Kourbatov, JavaScripter.net/math.
Journal of Integer Sequences: Maximal gaps between prime k-tuples: a statistical approach, Article 13.5.2, MR3065331, arXiv:1301.2242.

Gaps between consecutive primes have been extensively studied [1–8, 20–23]. The prime number theorem  suggests that “typical” prime gaps near p have the size about log p. On the other hand, Cramér  conjectured that maximal gaps between primes near p are at most about as large as log2p when p → ∞. Moreover, Shanks  stated that the maximal gaps are asymptotically equal to log2p. All maximal gaps between primes are now known, up to low 19-digit primes [1–5, 23]. This data apparently supports the Cramér and Shanks conjectures: thus far, if we divide by log2p the prime gap ending at p, the resulting ratio is always less than one – but tends to grow closer to one, albeit very slowly and irregularly.

Less is known about maximal gaps between prime constellations, or prime k-tuples [9–14, 19, 24]. We can conjecture that average gaps between prime k-tuples near p are O(logkp) as p → ∞, in agreement with the Hardy-Littlewood k-tuple conjecture [9,14]. Computations show that maximal gaps between k-tuples are at most about log p times the average gap, which implies that maximal gaps are O(logk+1p) as p → ∞. Probability-based heuristics described below suggests a general formula predicting the size of maximal gaps between k-tuples: maximal gaps are approximately max(a, a(log(p/a) − b)), where a = Cklogkp is the estimated average gap near p, and Ck and b are positive parameters depending on the type of k-tuple. This formula approximates maximal gaps better and in a wider range than a linear function of logk+1p (cf. Rodriguez and Rivera  for the special case k = 2; note the issues caused by a linear approximation). In what follows, we will focus on three specific types of prime k-tuples:

• twin primes (k = 2),
• prime quadruplets (k = 4), and
• prime sextuplets (k = 6).

The observations can be generalized to other k-tuples; however, the numeric constants will change depending on the specific type of k-tuple. See Appendixes for data on maximal gaps between prime triplets (k = 3), quintuplets (k = 5), septuplets (k = 7), and decuplets (k = 10).

Definitions and notation

Twin primes are pairs of consecutive primes that have the form {p, p+2}. This is the densest repeatable pattern of two primes.

Prime quadruplets are clusters of four consecutive primes of the form {p, p+2, p+6, p+8}. This is the densest repeatable pattern of four primes.

Prime sextuplets are clusters of six consecutive primes of the form {p, p+4, p+6, p+10, p+12, p+16}. This is the densest repeatable pattern of six primes.

Prime k-tuples are clusters of k consecutive primes that have a repeatable pattern. Thus, twin primes are a specific type of prime k-tuples, with k = 2; prime quadruplets are another specific type of prime k-tuples, with k = 4; and prime sextuplets are yet another type of prime k-tuples, with k = 6. (The densest k-tuples possible for a given k may also be called prime constellations or prime k-tuplets.)

Gaps between prime k-tuples are center-to-center distances between consecutive k-tuples. If the prime at the “far” end of the gap is p, we denote the gap gk(p). For example, the gap between the quadruplets {11,13,17,19} and {101,103,107,109} is g4(101) = 90. The gap between the twin primes {17,19} and {29,31} is g2(29) = 12.

A maximal gap is a gap that is strictly greater than all preceding gaps. In other words, a maximal gap is the first occurrence of a gap at least this size. As an example, consider gaps between prime quadruplets (4-tuples): the gap of 90 preceding the quadruplet {101,103,107,109} is a maximal gap (i.e. the first occurrence of a gap of at least 90), while the gap of 90 preceding {191,193,197,199} is not a maximal gap (not the first occurrence of a gap at least this size). A synonym for maximal gap is record gap; see e.g. OEIS Sequences A113274, A113404, A200503 (record gaps between twins, quadruplets, and sextuplets, respectively).

Hereafter p denotes a prime, log x denotes the natural logarithm of x, and logkx = (log x)k is log x raised to the k-th power.

Simple conjectures for the gap size

There are simple formulas for gaps between k-tuples of a specific type. These formulas give rough estimates of the gap gk(p) that ends at a prime p:
(A) Average gaps between prime k-tuples are gk(p)Ck logkpa(p), where Ck are constants.
(B) Maximal gaps between prime k-tuples are O(logk+1p):   gk(p) < Mk logk+1p, where MkCk.
(C) Maximal gaps between prime k-tuples are asymptotically equal to Cklogk+1p as p → ∞.

Statement (A) follows from the Hardy-Littlewood k-tuple conjecture [9,14] that predicts the total counts of prime k-tuples (and thereby average frequencies of k-tuples); the constants Ck are reciprocals of the Hardy-Littlewood constants. For example,
C2 ≈ 0.75739... (for twin primes)
C3 ≈ 0.34986... (for prime triplets)
C4 ≈ 0.240895... (for prime quadruplets)
C6 ≈ 0.057808... (for prime sextuplets).

Statements (B) and (C) are also conjectural – they are suggested by heuristics and supported by large sets of known maximal gaps such as listed below for k = 2, 4, 6. (For more data, see Appendixes as well as the following OEIS sequences: maximal gaps between triplets A201596, A201598, quintuplets A201062, A201073, septuplets A201051, A201251, and decuplets A202281 and A202361. Data in these sequences thus far seem to support our general conjectures – or at least do not contradict them. However, one would need to analyze huge amounts of additional data, especially for k-tuples with larger k, to boost the confidence level. Of course, no amount of data can replace a formal proof – which we do not have at this time, much like we still lack a formal proof of similar conjectures for primes [7,8].)

The constants Mk (k ≥ 2) in (B) are less than 1; moreover, computations suggest that MkCk. In particular, for k = 2, 4, 6 statement (B) becomes:
Maximal gaps between 2-tuples (twin prime pairs) are O(log3p): g2(p) < 0.76 log3p.
Maximal gaps between 4-tuples (prime quadruplets) are O(log5p): g4(p) < 0.241 log5p.
Maximal gaps between 6-tuples (prime sextuplets) are O(log7p): g6(p) < 0.058 log7p.

Statement (C) is stronger than (B) and analogous to the Shanks conjecture for primes . Together, statements (A), (B), (C) tell us that:

Maximal gaps between prime k-tuples are at most about log p times the average gap.

Can we predict the maximal gaps even better? Probability-based heuristics can help!

Prime k-tuples are rare and seemingly random. Life offers many examples of unusually large intervals between rare random events: the longest runs of two-dice rolls without getting a twelve, maximal intervals between cars crossing a bridge at night, maximal intervals between clicks of a Geiger counter measuring very low radioactivity, etc. Schilling gives many more statistical examples of this kind in his paper The longest run of heads  and states “the log n law” for the length or duration of the longest runs. Reasoning as in , one can statistically estimate the expected maximal intervals between rare random events by expressing the maximal intervals in terms of the average intervals:
E(max interval)  =  a log(T/a) + O(a),     with standard deviation of about a,
where a is the average interval between the rare events, and T is the total observation time or length (1 << a << T).

For lack of a better model, we will simulate the distribution of prime k-tuples by a timeline of rare random events. (A quick nod to purists: Yes, we have to remember that consecutive prime k-tuples are not independent events; thus they are beyond the proven range of applicability of most statistical models. The same is true for consecutive primes. But we are not proving a theorem here – just stating conjectures.) By analogy with the above statistical formula, for maximal gaps gk(p) we define a heuristic maximal gap estimator E(max gk(p)) – a function of p, with two more positive arguments, a and b:

E(max gk(p))  =  max(aa log(p/a) − ba),   with  a = Ck logkp.
Here, the role of the total observation time T is played by p (we are looking for maximal gaps that occur from 0 up to p). The role of average intervals a is played by the size of average gaps between k-tuples near p, i.e. we set a = Ck logkp, as predicted by the Hardy-Littlewood k-tuple conjecture – see (A) above. The constants Ck are reciprocal to the Hardy-Littlewood constants, which are known to a high precision [9,11]. For instance, in case of twin primes (k = 2) we have a value reciprocal to the twin prime constant 2Π2: C2 = (2Π2)−1 = (1.3203236...)−1 = 0.75739... Unlike simpler statistical problems with constant a, in our case the average gap a itself grows with p. (Using the Geiger counter analogy, this means that during a very long observation time T the radioactivity level not only is low, but gradually gets even lower, so the average intervals between clicks grow longer and longer.) The additional parameter b helps us compensate for this growth and achieve a better fit with known data on k-tuples. The choice b ≈ 2/k works well in most cases; the choice b ≈ 3 works even better for k = 1 (i.e. for maximal gaps between primes).

Is the prediction accurate?

Below are graphs and numerical data for k = 2, 4, 6. The diamond-shaped data points on the graphs are the actual maximal gaps between k-tuples obtained from a lengthy computation. We easily see that all maximal gaps gk(p) are smaller than the empirical upper bound Cklogk+1p (top red line). The estimator (blue curve) E(max gk) = a(log(p/a) − b) approximates the actual maximal gaps quite closely (usually predicting the maximal gap sizes with accuracy ±2a or better). At first, the estimator curve seems to go way below the respective upper bound (red line). However, substituting a = Ck logkp we can rewrite the estimator as

E(max gk) = a log(p/a) − ab = a log pa(log a + b) = Cklogk+1po(logk+1p),
which shows that E(max gk) < Cklogk+1p, but at the same time E(max gk) is asymptotically equal to the upper bound Cklogk+1p as p → ∞. This means that eventually the red line and blue curve will become “almost parallel” as p → ∞. That is to say, if the slope of the red line were even a little less than Ck – while the blue curve were to remain as it is – then the red line would intersect the blue curve at some (very distant) point.

Notes. Of course, it is not guaranteed that the formula a(log(p/a) − b) is valid for very big p. Importantly, for any p, the estimator does not predict the existence of a maximal gap gk(p) anywhere near p – it only gives us a good guess for the size of gk(p) if there is a maximal gap near p. As far as rigorous proofs are concerned, we don't even know whether there are infinitely many k-tuples of a given type − for example, whether there are infinitely many twin primes for k = 2. (The famous twin prime conjecture as well as the more general k-tuple conjecture thus far remain unproven. Thanks to the theorems of Zhang  and Maynard , we now know that at least some types of prime k-tuples do occur infinitely often.) Maximal gaps between twin primes up to 1.2 × 1015

```  1st twin pair:   2nd twin pair:     Gap g2(p):
3                5              2
5               11              6
17               29             12
41               59             18
71              101             30
311              347             36
347              419             72
659              809            150
2381             2549            168
5879             6089            210
13397            13679            282
18539            18911            372
24419            24917            498
62297            62927            630
187907           188831            924
687521           688451            930
688451           689459           1008
850349           851801           1452
2868959          2870471           1512
4869911          4871441           1530
9923987          9925709           1722
14656517         14658419           1902
17382479         17384669           2190
30752231         30754487           2256
32822369         32825201           2832
96894041         96896909           2868
136283429        136286441           3012
234966929        234970031           3102
248641037        248644217           3180
255949949        255953429           3480
390817727        390821531           3804
698542487        698547257           4770
2466641069       2466646361           5292
4289385521       4289391551           6030
19181736269      19181742551           6282
24215097497      24215103971           6474
24857578817      24857585369           6552
40253418059      40253424707           6648
42441715487      42441722537           7050
43725662621      43725670601           7980
65095731749      65095739789           8040
134037421667     134037430661           8994
198311685749     198311695061           9312
223093059731     223093069049           9318
353503437239     353503447439          10200
484797803249     484797813587          10338
638432376191     638432386859          10668
784468515221     784468525931          10710
794623899269     794623910657          11388
1246446371789    1246446383771          11982
1344856591289    1344856603427          12138
1496875686461    1496875698749          12288
2156652267611    2156652280241          12630
2435613754109    2435613767159          13050
4491437003327    4491437017589          14262
13104143169251   13104143183687          14436
14437327538267   14437327553219          14952
18306891187511   18306891202907          15396
18853633225211   18853633240931          15720
23275487664899   23275487681261          16362
23634280586867   23634280603289          16422
38533601831027   38533601847617          16590
43697538391391   43697538408287          16896
56484333976919   56484333994001          17082
74668675816277   74668675834661          18384
116741875898981  116741875918727          19746
136391104728629  136391104748621          19992
221346439666109  221346439686641          20532
353971046703347  353971046725277          21930
450811253543219  450811253565767          22548
742914612256169  742914612279527          23358
1121784847637957 1121784847661339          23382
1149418981410179 1149418981435409          25230
```

The ratio g2(p)/log3p is never greater than 0.76. (The maximal values of g2(p) for p up to 1.2 × 1015 were first computed in 2008 by Richard Fischer  and later extended by Tomás Oliveira e Silva .) Maximal gaps between prime quadruplets up to 1015:

```    1st 4-tuple:    2nd 4-tuple:      Gap g4(p):
5              11               6
11             101              90
191             821             630
821            1481             660
2081            3251            1170
3461            5651            2190
5651            9431            3780
25301           31721            6420
34841           43781            8940
88811           97841            9030
122201          135461           13260
171161          187631           16470
301991          326141           24150
739391          768191           28800
1410971         1440581           29610
1468631         1508621           39990
2990831         3047411           56580
3741161         3798071           56910
5074871         5146481           71610
5527001         5610461           83460
8926451         9020981           94530
17186591        17301041          114450
21872441        22030271          157830
47615831        47774891          159060
66714671        66885851          171180
76384661        76562021          177360
87607361        87797861          190500
122033201       122231111          197910
132574061       132842111          268050
204335771       204651611          315840
628246181       628641701          395520
1749443741      1749878981          435240
2115383651      2115824561          440910
2128346411      2128859981          513570
2625166541      2625702551          536010
2932936421      2933475731          539310
3043111031      3043668371          557340
3593321651      3593956781          635130
5675642501      5676488561          846060
25346635661     25347516191          880530
27329170151     27330084401          914250
35643379901     35644302761          922860
56390149631     56391153821         1004190
60368686121     60369756611         1070490
71335575131     71336662541         1087410
76427973101     76429066451         1093350
87995596391     87996794651         1198260
96616771961     96618108401         1336440
151023350501    151024686971         1336470
164550390671    164551739111         1348440
171577885181    171579255431         1370250
210999769991    211001269931         1499940
260522319641    260523870281         1550640
342611795411    342614346161         2550750
1970587668521   1970590230311         2561790
4231588103921   4231591019861         2915940
5314235268731   5314238192771         2924040
7002440794001   7002443749661         2955660
8547351574961   8547354997451         3422490
15114108020021  15114111476741         3456720
16837633318811  16837637203481         3884670
30709975578251  30709979806601         4228350
43785651890171  43785656428091         4537920
47998980412211  47998985015621         4603410
55341128536691  55341133421591         4884900
92944027480721  92944033332041         5851320
412724560672211 412724567171921         6499710
473020890377921 473020896922661         6544740
885441677887301 885441684455891         6568590
947465687782631 947465694532961         6750330
979876637827721 979876644811451         6983730
```
The ratio g4(p)/log5p is never greater than 0.241. Maximal gaps between prime 6-tuples up to 1015:

```    1st 6-tuple:    2nd 6-tuple:      Gap g6(p):
7              97              90
97           16057           15960
19417           43777           24360
43777         1091257         1047480
3400207         6005887         2605680
11664547        14520547         2856000
37055647        40660717         3605070
82984537        87423097         4438560
89483827        94752727         5268900
94752727       112710877        17958150
381674467       403629757        21955290
1569747997      1593658597        23910600
2019957337      2057241997        37284660
5892947647      5933145847        40198200
6797589427      6860027887        62438460
14048370097     14112464617        64094520
23438578897     23504713147        66134250
24649559647     24720149677        70590030
29637700987     29715350377        77649390
29869155847     29952516817        83360970
45555183127     45645253597        90070470
52993564567     53086708387        93143820
58430706067     58528934197        98228130
93378527647     93495691687       117164040
97236244657     97367556817       131312160
240065351077    240216429907       151078830
413974098817    414129003637       154904820
419322931117    419481585697       158654580
422088931207    422248594837       159663630
427190088877    427372467157       182378280
610418426197    610613084437       194658240
659829553837    660044815597       215261760
660863670277    661094353807       230683530
853633486957    853878823867       245336910
1089611097007   1089869218717       258121710
1247852774797   1248116512537       263737740
1475007144967   1475318162947       311017980
1914335271127   1914657823357       322552230
1953892356667   1954234803877       342447210
3428196061177   3428617938787       421877610
9367921374937   9368397372277       475997340
10254799647007  10255307592697       507945690
13786576306957  13787085608827       509301870
21016714812547  21017344353277       629540730
33157788914347  33158448531067       659616720
41348577354307  41349374379487       797025180
72702520226377  72703333384387       813158010
89165783669857  89166606828697       823158840
122421000846367 122421855415957       854569590
139864197232927 139865086163977       888931050
147693859139077 147694869231727      1010092650
186009633998047 186010652137897      1018139850
202607131405027 202608270995227      1139590200
332396845335547 332397997564807      1152229260
424681656944257 424682861904937      1204960680
437804272277497 437805730243237      1457965740
```
The ratio g6(p)/log7p is never greater than 0.058; in fact, for all of the above gaps g6(p), the ratio is far less.

On maximal gaps between primes

For comparison, here is the same model applied to maximal gaps between primes (A005250):

Maximal gaps are about a(log(p/a) − b), with a = log p and b ≈ 3.
This leads to the well-known Cramér and Shanks conjectures for prime gaps g(p):
lim sup(g(p)/log2p) = 1   as p → ∞     (Cramér ),
while maximal gaps between consecutive primes are asymptotically equal to log2p (Shanks ).

Indeed, for a = log p and any fixed b ≥ 0, we have log2p > a(log(p/a) − b) `~` log2p as p → ∞. An adjustment to the Cramér-Shanks conjecture? Maier's theorem  states that there are (relatively short) intervals where typical gaps between primes are greater than the average (log p). Based in part on this theorem, Granville  adjusted the Cramér-Shanks conjecture and proposed that, as p → ∞, lim sup(g(p)/log2p) ≥ 2e−γ = 1.1229... This would mean that an infinite subsequence of maximal gaps must lie above the Cramér-Shanks upper limit log2p, i.e. above the red line on this graph – and this hypothetical subsequence (or an infinite subset thereof) must approach a line whose slope is about 1.1229 times steeper! However, for now, there is not a single data point for maximal prime gaps above log2p, where p denotes the end-of-gap prime. Apparently Helmut Maier himself did not feel that the Cramér-Shanks conjecture was necessarily in danger because of his theorem; thus, Maier and Pomerance  simply remarked in 1990 (five years after the publication of Maier's theorem):

Cramér conjectured that lim sup G(x) / log2x = 1, while Shanks made the stronger conjecture that G(x) `~` log2x, but we are still a long way from proving these statements.
[Here G(x) denotes the largest prime gap below x.]
So do we possibly need a constant before log2x in the asymptotic equivalence G(x) `~` log2x? Or maybe the asymptotic equivalence is not valid at all? Maybe the best way we can hope to describe the maximal prime gaps is in weaker terms of an upper limit, lim sup (G(x)/log2x)? We'll live and see! (Let us hope to live long enough...)

Appendixes

The above heuristic argument appears to be applicable to prime k-tuples for all natural k, as long as the Hardy-Littlewood k-tuple conjecture [9,14] remains valid. However, we have purposely chosen only the cases k = 2, 4, 6 for the main presentation above. Data and specific conjectures for other values of k can be found in these appendixes:
• Maximal gaps between prime triplets (k = 3)
• Maximal gaps between prime quintuplets (k = 5)
• Maximal gaps between prime septuplets (k = 7)
• Maximal gaps between prime decuplets (k = 10)
• Hardy-Littlewood constants and reciprocals

References

1. Young, J. and Potler, A. First Occurrence Prime Gaps. Math. Comp. 52, 221-224, 1989.

2. Nicely, Thomas R. List of prime gaps. http://www.trnicely.net/gaps/gaplist.html (2011)

3. Oliveira e Silva, Tomás. Gaps between consecutive primes. http://www.ieeta.pt/~tos/gaps.html (2001-2013)

4. Ribenboim, Paulo. The little book of big primes, New York, Springer-Verlag, 1991.
(Second edition: The little book of bigger primes, New York, Springer-Verlag, 2004)

5. Weisstein, Eric W. Prime Gaps. From MathWorld – A Wolfram Web Resource.
http://mathworld.wolfram.com/PrimeGaps.html (2011)

6. Hardy, Godfrey H. and Wright, Edward M. An Introduction to the Theory of Numbers, 6th ed. Oxford, Oxford University Press, 2008, p.10.

7. Cramér, Harald. On the Order of Magnitude of the Difference between Consecutive Prime Numbers. Acta Arith. 2, 23-46, 1936.

8. Shanks, Daniel. On Maximal Gaps Between Successive Primes. Math. Comp. 18, 646-651, 1964.

9. Hardy, Godfrey H. and Littlewood, John E. Some Problems of 'Partitio Numerorum.' III. On the Expression of a Number as a Sum of Primes. Acta Math. 44, 1-70, 1923.

10. Smith, Herschel F. On a generalization of the prime pair problem, Mathematical Tables and Other Aids to Computation, v. 11, 1957, p. 274.
http://www.ams.org/journals/mcom/1957-11-060/S0025-5718-1957-0094314-8/home.html

11. Forbes, Anthony D. Prime k-tuplets. http://anthony.d.forbes.googlepages.com/ktuplets.htm (2011)

12. Rivera, Carlos and Rodriguez, Luis. Gaps between consecutive twin prime pairs
http://www.primepuzzles.net/conjectures/conj_066.htm

13. Fischer, Richard. Maximale Lücken (Intervallen) von Primzahlenzwillingen.
http://www.fermatquotient.com/PrimLuecken/ZwillingsRekordLuecken (2008)

14. Weisstein, Eric W. k-Tuple Conjecture. From MathWorld – A Wolfram Web Resource.
http://mathworld.wolfram.com/k-TupleConjecture.html (2011)

15. Schilling, Mark F. The longest run of heads. The College Mathematics Journal, v.21, No.3, 196-207, 1990.

16. Maier, Helmut. Primes in short intervals, Michigan Math. J., v.32, 221-225, 1985.

17. Granville, Andrew. Harald Cramér and the distribution of prime numbers. Scand. Act. J. 1, 12-28, 1995.
http://www.dms.umontreal.ca/~andrew/PDF/cramer.pdf

18. Maier, Helmut and Pomerance, Carl. Unusually large gaps between consecutive primes. Transactions of the AMS, v.322, No. 1, 201-237, 1990.

19. Wolf, Marek. Some remarks on the distribution of twin primes, http://arxiv.org/abs/math/0105211 (2001)

20. Wolf, Marek. Some heuristics on the gaps between consecutive primes, http://arxiv.org/abs/1102.0481 (2011)

2013 — New Proofs

21. Zhang, Yitang. Bounded gaps between primes, Annals of Math. 179, No.3, 1121-1174, 2014.

22. Maynard, James. Small gaps between primes, http://arxiv.org/abs/1311.4600 (2013)

Recent Computations and Heuristics

23. Oliveira e Silva, Tomás, Herzog, Siegfried, and Pardi, Silvio. Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4·1018, Math. Comp. 83, 2033-2060, 2014.

24. Oliveira e Silva, Tomás, Gaps between twin primes. http://sweet.ua.pt/tos/twin_gaps.html (2013)

25. Kourbatov, Alexei, Maximal gaps between prime k-tuples: a statistical approach. Journal of Integer Sequences, 16, Article 13.5.2, 2013. arXiv:1301.2242

26. Kourbatov, Alexei, Tables of record gaps between prime constellations, arXiv:1309.4053 (2013)

27. Kourbatov, Alexei, The distribution of maximal prime gaps in Cramer's probabilistic model of primes, Int. Journal of Statistics and Probability, 3, No.2, 18-29, 2014. arXiv:1401.6959