Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Define $M_n$ to be the $n$th maximal gap between primes. That is, $M_1=1$ thanks to $3-2=1$; $M_2=2$ thanks to $5-3=2$; $M_3=4$ thanks to $11-7=4$; and in general, $M_n = p_{i+1}-p_i$, where $p_i$ is the smallest prime such that $p_{i+1} - p_i > p_{j+1} - p_j$ for all $j < i$.

Is there a conjecture or proof with maximal prime gaps, $M_n$, which says that the gap will not more than double between one maximal to the next, $$\frac{M_{n+1}}{M_n} \le 2$$ for $n>1$, or $$\frac{M_{n+1}}{M_n} < 2$$ for $n>3$?

If yes, who wrote it?

Edit: Currently, there are three answers, of which only one appears to try to answer the posed question "who wrote it?" or if the conjecture exist. Greg Martin answered with "I haven't seen a conjecture of this type." which seems to point towards this conjecture being an original conjecture. But, there is no one else which agreed with him or changed the statement.

While the extra information of all of the answers is nice, it appears that proving this conjecture would lead to disprove something with the "heuristic analysis using Cramér's model" and how its is used. But I digress, this would be another question.

I have also not seen a conjecture like this, so I hoped someone else may have and can state a reference that I can source.

Edit 2: Now four nice answers, but none which answer the question.

share|improve this question
    
Is $M_n = P_n-P_{n-1}$? –  teddybear May 13 at 19:29
    
@tedybear $M_n = p_{i+1} - p_i$ where $p_i$ is the smallest prime such that $p_{i+1} - p_i > p_{j+1} - p_j$ for all $j < i$. –  user160140 May 13 at 19:29
    
$M_n$ = A005250(n) where A005250 is a sequence in the OEIS. –  user160140 May 13 at 19:36
    
Is this right $M_n = \max\{p_{i+1}-p_i: \ 1\leq i\leq n\}$ ? –  Integral May 13 at 19:53
    
@Integral The index of $M_n$ is for A005250. –  user160140 May 13 at 20:08

4 Answers 4

I pulled one of the tables of prime gaps off wikipedia and put a final column, $g/\log^2p,$ just as in the section in Guy's book. For $11 \leq p < 4 \cdot 10^{18},$ we have $g < \log^2p.$ Completely unprovable for larger $p.$ After line 3 (prime is 7) the closest we get to $1$ is line 64, $ \; g = 1132,$ $ \; p \approx 1.69 \cdot 10^{15},$ $ \; g/\log^2p \approx 0.920639.$ I believe Cramer-Granville is the conjecture that $ \; \limsup g/\log^2 p$ is nonzero but finite, and the disagreement is over whether it is more likely to be $1$ or something else.

       Stolen from 
       http://users.cybercity.dk/~dsl522332/math/primegaps/maximal.htm

       the size of the gap is g

       next are the number of decimal digits in p

       for 4 * 10^18 > p >= 11, g < log^2 p = (log p)^2.

       Oh, logarithms base e == 2.718281828459


   ==================================
            g   digits of p           p    log p   g/log p  g/log^2 p
     1      1   1                      2 0.693147   1.4427    2.08137
     2      2   1                      3  1.09861  1.82048    1.65707
     3      4   1                      7  1.94591  2.05559    1.05637
     4      6   2                     23  3.13549  1.91357   0.610294
     5      8   2                     89  4.48864  1.78228   0.397065
     6     14   3                    113  4.72739  2.96147   0.626449
     7     18   3                    523  6.25958  2.87559    0.45939
     8     20   3                    887  6.78784  2.94644   0.434076
     9     22   4                   1129  7.02909  3.12985   0.445271
    10     34   4                   1327  7.19068  4.72835   0.657566
    11     36   4                   9551   9.1644  3.92824   0.428642
    12     44   5                  15683  9.66033  4.55471   0.471486
    13     52   5                  19609  9.88374  5.26116   0.532305
    14     72   5                  31397  10.3545  6.95352   0.671548
    15     86   6                 155921  11.9571  7.19238   0.601515
    16     96   6                 360653  12.7957  7.50254   0.586334
    17    112   6                 370261   12.822  8.73501   0.681254
    18    114   6                 492113  13.1065    8.698   0.663642
    19    118   7                1349533  14.1153  8.35974   0.592248
    20    132   7                1357201  14.1209  9.34782   0.661983
    21    148   7                2010733   14.514   10.197   0.702566
    22    154   7                4652353  15.3529  10.0307   0.653342
    23    180   8               17051707  16.6518  10.8097   0.649161
    24    210   8               20831323   16.852  12.4615   0.739466
    25    220   8               47326693  17.6726  12.4487   0.704405
    26    222   9              122164747  18.6209  11.9221   0.640254
    27    234   9              189695659  19.0609  12.2764   0.644062
    28    248   9              191912783  19.0726   13.003   0.681764
    29    250   9              387096133  19.7742  12.6427   0.639356
    30    282   9              436273009  19.8938  14.1753   0.712549
    31    288  10             1294268491  20.9812  13.7266   0.654231
    32    292  10             1453168141   21.097  13.8408   0.656056
    33    320  10             2300942549  21.5566  14.8447   0.688637
    34    336  10             3842610773  22.0694  15.2247   0.689855
    35    354  10             4302407359  22.1824  15.9586   0.719423
    36    382  11            10726904659   23.096  16.5396   0.716125
    37    384  11            20678048297  23.7523  16.1668   0.680642
    38    394  11            22367084959  23.8309  16.5332   0.693772
    39    456  11            25056082087  23.9444  19.0441   0.795349
    40    464  11            42652618343  24.4764  18.9571   0.774506
    41    468  12           127976334671  25.5751   18.299   0.715502
    42    474  12           182226896239  25.9285   18.281   0.705055
    43    486  12           241160624143  26.2087  18.5434   0.707529
    44    490  12           297501075799  26.4187  18.5475   0.702059
    45    500  12           303371455241  26.4382   18.912   0.715328
    46    514  12           304599508537  26.4423  19.4386   0.735133
    47    516  12           416608695821  26.7554  19.2858   0.720819
    48    532  12           461690510011  26.8582  19.8078   0.737495
    49    534  12           614487453523  27.1441  19.6728   0.724756
    50    540  12           738832927927  27.3283  19.7597   0.723048
    51    582  13          1346294310749  27.9284   20.839   0.746159
    52    588  13          1408695493609  27.9737  21.0198   0.751412
    53    602  13          1968188556461  28.3081   21.266   0.751232
    54    652  13          2614941710599  28.5923  22.8034   0.797536
    55    674  13          7177162611713  29.6019  22.7688   0.769166
    56    716  14         13829048559701  30.2578  23.6633   0.782057
    57    766  14         19581334192423  30.6056  25.0281   0.817762
    58    778  14         42842283925351  31.3885  24.7861   0.789655
    59    804  14         90874329411493  32.1405  25.0152   0.778307
    60    806  15        171231342420521   32.774  24.5926   0.750369
    61    906  15        218209405436543  33.0165  27.4408   0.831126
    62    916  16       1189459969825483  34.7123  26.3884   0.760203
    63    924  16       1686994940955803  35.0617  26.3535   0.751632
    64   1132  16       1693182318746371  35.0654  32.2825   0.920639
    65   1184  17      43841547845541059  38.3194  30.8982   0.806335
    66   1198  17      55350776431903243  38.5525  31.0745   0.806032
    67   1220  17      80873624627234849  38.9317   31.337   0.804922
    68   1224  18     203986478517455989  39.8568  30.7099   0.770506
    69   1248  18     218034721194214273  39.9234  31.2598   0.782995
    70   1272  18     305405826521087869  40.2604  31.5943   0.784749
    71   1328  18     352521223451364323  40.4039  32.8681   0.813489
    72   1356  18     401429925999153707  40.5338  33.4536   0.825325
    73   1370  18     418032645936712127  40.5743  33.7652   0.832181
    74   1442  18     804212830686677669  41.2286  34.9757   0.848335
    75   1476  19    1425172824437699411  41.8008  35.3103   0.844728
          g   digits of p             p    log p   g/log p  g/log^2 p
   ==================================
share|improve this answer
    
The first column is $n$. The column with g is the same as $M_n$. Column with p is $p_i$. –  user160140 May 13 at 21:00
1  
Granville won't even conjecture that it's finite, just that it's at least $2/e^\gamma\approx1.1229.$ –  Charles May 13 at 21:01
1  
@Charles, there's no accounting for taste. –  Will Jagy May 13 at 21:16

I haven't seen a conjecture of this type. It is conjectured that among all primes up to $x$, the largest gap has size like $(\ln x)^2$ or a constant multiple thereof. The next time that gap occurs, each number following the gap will have a roughly $1/\ln x$ probability of being prime (by the prime number theorem). So we expect the next gap to be about $Y\ln x$ larger than the previous one, where $Y$ is a continuous random variable with a Poisson distribution with parameter $\lambda=1$. This implies that the order of magnitude of $M_{N+1}-M_n$ typically has size $\sqrt M_n$ (times a fluctuating constant); in particular, for any $\varepsilon>0$, we should have $M_{n+1}/M_n < 1+\varepsilon$ for sufficiently large $n$.

share|improve this answer
    
If I am reading this answer correctly: $M_{n+1} < M_n + c \sqrt M_n$ for n > some value? –  user160140 May 13 at 20:21
    
Does this fluctuating constant $c$ have bounds? –  user160140 May 13 at 21:04
    
Should that read $1 \ge \varepsilon > 0$ for what I am observing? –  user160140 May 13 at 21:22
    
My guess is that the factor $c$ will have a distribution function, so will be "bounded most of the time" but not literally bounded. I suspect something of the shape $M_{n+1} < M_n + 1000 \sqrt M_n \ln M_n$ will probably be true (but not provable, at least by me!). –  Greg Martin May 13 at 23:09
2  
The latter statement is almost certainly true. –  Greg Martin May 14 at 15:26

This is all some rather shaky heuristics, but here is what I think:

A random integer n is prime with probability $1 - \frac{1}{\ln{n}}$ and composite with probability $1 - \frac{1}{\ln{n}}$.

A random integer n is followed by at least $M$ composite numbers with probability $(1 - \frac{1}{\ln{n}})^M$ which is about $\exp (-\frac{M}{\ln{n}})$. That's true for every integer $n$, including integers $n$ which are primes.

If the record gap so far is $M$, then a prime $p$ is followed by a record gap with probability $\exp (-\frac{M}{\ln{p}})$. It is followed by a gap of length $2M$ or more with probability $\exp (-\frac{2M}{\ln{p}})$. If that prime $p$ is indeed followed by a record gap, then the probability that it is followed by a gap doubling the record is $\exp (-\frac{M}{\ln{p}})$.

So the chance that a prime $p$ is followed by a record gap is the same as the chance that the record gap is twice the previous record gap. The table above shows 75 record gap up to $1.4 * 10^{18}$. The distance between two record gaps is about $8 * 10^{17}$. $\ln p$ is about 40, so the chance for a prime being followed by a record gap is about $\frac{1}{2 * 10^{16}}$. The chance that a record gap is twice the previous gap is also $\frac{1}{2 * 10^{16}}$. So this is very unlikely to happen.

Anyone who knows how to make $\frac{1}{\ln{p}}$ look nicer? See comment below.

share|improve this answer
    
Nice again, but does not answer the question. To answer the "how to make 1 / ln p look nicer?" meta.math.stackexchange.com/questions/5020/… –  user160140 May 19 at 23:50

Here's a heuristic analysis using Cramér's model. TL;DR: the conjecture is likely false.

The expected maximal gap in this model is $\log^2n$, so suppose we're looking just after finding just such a gap. The probability that a number is prime is $x=1/\log n$ and so the probability that a given prime will have a gap of length $k+1$ is $x(1-x)^k$. The probability that a given prime will not be followed by a record gap is thus $$ 1-(1-x)^{\log^2n}=1-\left((1-1/\log n)^{\log n}\right)^{\log n}\approx1-e^{-\log n}=1-1/n. $$ and the probability that a given prime will be followed by a record of at least $k$ times the old one is $$ (1-x)^{k\log^2n}\approx e^{-k\log n}=n^{-k}. $$

Combining the two, the probability that the gap will be exceeded by a factor of $k$ or more is $$ \sum_{i=0}^\infty(1-1/n)^in^{-k}=\frac{n}{n^k}=\frac{1}{n^{k-1}} $$ and hence $k=2$ is right on the boundary: we expect records to double the previous record infinitely often (since $\int1/n$ diverges), but records should be 2.001 times the previous record finitely often.

Now this is really taking the heuristic too far. Cramér's model is not state of the art, and has been shown to make incorrect predictions on the fine behavior of the primes ([1], [2]). But the basic idea is that there is a phase transition, probably around 2, from ratios that appear infinitely often to finitely often (or never!).

Improvement

A better version would allow the starting gap to be other than $\log^2n$. This crude version is conservative, since a distribution of values would make it easier to get large factors between the two.

In fact, if you redo the calculation supposing that the old record is only $s\log^2 n$ then you expect that gaps of size $1+1/s$ should occur infinitely often. So if you think that a positive proportion of the time the largest prime gap below $n$ is $0.99\log^2n$ then you should get records topping the previous one by a factor of 2+1/99 infinitely often.

Technical Notes

A further improvement would be to take small factors into account (a relative of the so-called W-trick). It's hard to predict the net effect but if anything it would also make larger factors happen more often.

A minor issue is that my analysis uses $1/\log n$ as though it is constant. But the interesting range is the next $n$ primes after $n$, so it suffices to look up to about $n+n\log n$ which has logarithm about $\log n+\log\log n$ which is less than $(1+\varepsilon)\log n$ for any $\varepsilon>0$ and large enough $n$.

Conclusion

The conjecture is on shaky ground. There's good reason to think big ratios of maximal gaps happen infinitely often. On the other hand, looking at the heuristics we're talking about amazingly big numbers before these sorts of events happen. Each event we're looking at is a new maximal prime gap, and a 'success' at any given maximal prime gap has asymptotic probability 0 of happening, getting positive probability only when we integrate over a large number of new maximal prime gaps. But we know only a handful of these, so it's entirely possible that we'll never see only of these megajumps.

Bibliography

[1] János Pintz, Cramér vs. Cramér. On Cramér's probabilistic model for primes, Funct. Approx. Comment. Math. 37 (2007), part 2, pp. 361–376.

[2] H. Maier, Primes in short intervals, Michigan Math. J. 32 (1985), pp. 221–225.

share|improve this answer
    
So, are you suggesting that gaps are as big as $2n+2$ at $n$? The reason I ask is "So if you think that a positive proportion of the time the largest prime gap below n is $0.99\log^2n$ then you should get records topping the previous one by a factor of 2+1/99 infinitely often." For some reason, this does not hold for "infinitely often". –  user160140 May 14 at 4:31
    
@user160140: No, that's not what I'm suggesting at all. I'm saying that under this heuristic, infinitely often the next largest gap after G is 2G or greater. An example would be a gap of 4000 following a gap of 2000, which might happen around, say, $10^{26}.$ –  Charles May 14 at 4:38
    
OK, so you are saying that lots of record gaps $2^iG$ breaking former records of $2^{i-1}G$ where $i \to \infty$ will happen near each other to the point that at $10^{big number}$ there is a gap of you guessed it $2*10^{big number}$. Or, there has to be a constant less than $\infty$ such that there will not be an issue? I am guessing 1 by the comments by Greg Martin, but I would not be surprised if it turns out to be $2/e^\gamma\approx1.1229$ for reason you state. –  user160140 May 14 at 5:37
    
@user160140: I'm not saying any of those things. I don't expect a gap G to be broken by a gap of $2^iG$ for arbitrarily large $i$ (in fact I doubt even $i=4$ would ever happen), I'm not expecting gaps to be precise multiples of the previous gap, I don't expect gaps to happen near powers of 10, and certainly gaps near $n$ are not of size $2n$ (should be more like $k\log^2n$). –  Charles May 14 at 5:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.