45

Prime gaps studies seems to be one of the most fertile topics in analytic number theory, for long and in lots of directions :

  • lower bounds (recent works by Maynard, Tao et al. [1])
  • upper bounds (recent works by Zhang and the whole Polymath 8 project [2])
  • statistics on most frequent gaps ("jumping champions" [3])
  • mean gaps (prime number theorem)
  • median gaps (Erdös-Kac and related conjectures)

I keep wondering about why so many efforts ? indeed it can be for pure knowledge of prime number distributions and properties for themselves, and that would already be a sufficient motivation, but is there any hope for further applications and consequences ?

What I am thinking about is the following. Since Weil's works on explicit formulae, prime distribution knowledge is useful to deduce properties on operator's spectrum or zeroes of L-functions. For instance, all the works since Montgomery around pair correlation of zeroes and $n$-densities estimates, and their relations with primes properties (underlined by Montgomery and Goldston [4]).

So my question is, mainly related to the jumping champions problem [3] : could we, by the mean of explicit formulae or whatever else, deduce from prime gaps properties some properties out of this apparently very specific field (zeroes of zeta functions, spectral informations, families statistics, etc?) ?

Hoping the question will not be an affront to those for who the answers will be obvious and trivial, I keep impatiently waiting for possible motivations and external relations for this prime gap world ;)

Best regards

== References ==

[1] James Maynard, Small gaps between primes, Ann. of Math. (2) 181 (2015), no. 1, 383--413.

[2] Yitang Zhang, Bounded gaps between primes, Ann. of Math. (2) 179 (2014), no. 3, 1121--1174.

[3] Andrew Odlyzko, Michael Rubinstein, and Marek Wolf, Jumping champions, Experiment. Math. 8 (1999), no. 2, 107--118.

[4] D. A. Goldston, S. M. Gonek, A. E. Özlük, and C. Snyder, On the pair correlation of zeros of the Riemann zeta-function, Proc. London Math. Soc. (3) 80 (2000), no. 1, 31--49.

Desiderius Severus
  • 5,324
  • 4
    I think a big reason for the interest in gaps is that there are many interesting questions on the local distribution of prime numbers to which gaps are the first step. Most notably there's the Hardy-Littlewood tuples conjecture, but there are probably tuples versions of the other problems. And these tuples statements are the most closely connected to other fields like zeroes of L-functions. But we have to handle prime gaps first... – Will Sawin Mar 20 '16 at 19:13
  • 1
    Anyone who does not believe in the sacred meaning of reducing 70 million to 246 is a heretic and should be [censored]. Such is my belief. – Nikita Sidorov Mar 20 '16 at 19:59
  • 3
    @NikitaSidorov I could believe in its deep interest, surely not in its sacred meaning ! There is no place for authority argument or universally admitted research program as justification; but if it's the truth you will probably be able to convince me quite easily ;) – Desiderius Severus Mar 20 '16 at 21:59
  • 9
    I think there may be a selection bias in effect here, in that results whose statement is appealing and elementary are more likely to be publicised outside of the specialist field the statement arises from, whereas highly active, but more technical, work may not reach the awareness of the lay person or even the general mathematician. For instance, I would venture that there is significantly more work on the gaps between zeroes of zeta than gaps between primes, but these don't tend to get nearly as much exposure in the popular science press. – Terry Tao Mar 21 '16 at 15:42
  • It is tempting to respond to the title question with motivations and applications using coprime gaps, of which large prime gaps are just one area of application. However, this question seems to focus on wanting applications specific to the realm of analytic number theory. Is that still the main intent, or are broader responses also welcome? Gerhard "Getting Into Practice For Writing" Paseman, 2016.03.22. – Gerhard Paseman Mar 22 '16 at 23:08
  • @GerhardPaseman I was thinking about explicit formulaes only because it appeared to me as a potential wide realm of applications, and probably for lack of culture too. Of course, every broader answer will be welcome : what I want is to grasp and discuss as far as possible (even philosophically) prime gaps motivations and neighborhood. – Desiderius Severus Mar 23 '16 at 06:58
  • @NikitaSidorov my belief is the opposite, though who cares either way. –  May 20 '19 at 09:11

3 Answers3

31

Since you ask about zeta zeros, Riemann hypothesis implies the gap is $O(\sqrt{p_n} \log p_n)$.

Larger gap will give you nontrivial zero off the critical line, disproving RH.

On the other hand, bounding the gap by $O(polylog(p_n))$ will solve the open problem for deterministically finding primes in polynomial time.

For practical purposes, some cryptographic algorithms need to find prime efficiently. Large gaps may break some implementations.

joro
  • 24,174
  • Thanks for the answer, it helps understanding some consequences. But what about results that are mainly statistical in essence, as the one I quoted of Odlyzko and Rubinstein ? Would this kind of result be of any use, put aside giving new conjectures or behavior confirmations ? (without any despise, it would already justify its interest by far) – Desiderius Severus Mar 20 '16 at 15:55
  • 3
    Is the claim "Large gaps may break some implementations." a hypothetical in the sense "One could imagine somebody wrote some code that relies on an unproved bound for the size of primes." or do you know of an actual example of an implementation (in relevant use) that would break? If so, in which way would it break? –  Mar 20 '16 at 17:37
  • 2
    "Larger gap will give you nontrivial zero off the critical line, disproving RH." While true that gap is so huge relative to what is expected that I'd be quite surprised such large gaps were to be found even if RH were wrong. –  Mar 20 '16 at 17:40
  • 2
    @quid I meant the implementation may malfunction, in the sense that it will fail to find prime due to hypothetically large gap (very unlikely to me), no need to write any code. As for RH, it is not strong enough for Legendre conjecture. I believe Cramer's conjecture (or maybe something slightly weaker, but still polylog), so the answer is purely hypothetical as the question is. Since current implementations work on large scale, large gaps don't seem to exist for current key size ;) – joro Mar 20 '16 at 18:44
  • @joro Even if larger gaps would disprove RH, it would be the case only for asymptotically larger gaps. Hence how can we motivate non-asymptotical, but only numerical, statistics ? (even if it seems nice results, beautiful methods, and a natural way of exploring and researching) Unlike numerical research of zeroes of zeta or Odlyzko's work on pair-correlations, aiming at reinforcing conjectures and advancing in already known directions towards unproven results, what can we hope from such a kind of statistics ? (maybe lower bounds for the implicit constant in the RH bound ?) – Desiderius Severus Mar 20 '16 at 22:05
  • 2
    @DesideriusSeverus "Even if larger gaps would disprove RH, it would be the case only for asymptotically larger gaps." That's false. There are completely explicit bounds on prime gaps under RH, and so one example could disprove it. (It's unrealistic as I commented, but it is possible.) Generally, you seem to severely underestimate the relevance of numerical statistics for the development of the theory. The very Prime Number Theorem was conjecture based on numerical statistics. –  Mar 20 '16 at 22:30
  • @quid That makes it clear at least, you gave in your post an asymptotic bound without saying there was an explicit constant, hence I could not imagine there was ;) And I tried to make clear I am not underestimating any relevance, just seeking some clear motivations. And here is one, indeed. Thank you quid. – Desiderius Severus Mar 20 '16 at 22:55
  • @DesideriusSeverus glad you find the information you got useful; I wrote no post though (only some comments). –  Mar 20 '16 at 22:57
  • @quid I am ready to bet some actual implementation will fail to find prime in case unrealistically large gaps exist and "random numbers" are against them. Don't have time at the moment to examine code, but I vaguely remember some generate primes by starting from random $n$ and then increment it. – joro Mar 21 '16 at 07:53
  • 1
    I guess it is plausible somebody increments for one random n, but I am not quite sure if this were good practice. In such a scenario I would further agree that a very large gap would result it in the algo not terminatining; of course you cannot test everything over a sqaurerootish gap for 2000 bit prime generation. Although I would not describe this as "break." And I'd assume a decent implementation to have some fallback if it takes too long. (Also AFAIK in practice often not actual prime test are used and the thing is "probabilistic" in other ways.) –  Mar 21 '16 at 11:01
  • 1
    A cryptographical application that generated random primes in this way would have a far bigger problem, namely that the resulting distribution would be heavily nonuniform (skewed towards primes that follow larger gaps). – Emil Jeřábek Mar 21 '16 at 14:54
  • @EmilJeřábek Any reference for your claim? Any reference to source code that generates primes in other way? – joro Mar 21 '16 at 15:07
  • I have yet to see any references for your claim. – Emil Jeřábek Mar 21 '16 at 15:14
  • 1
    What type of reference do you need for the distribution to be skewed? The probability for getting one specific prime $p_{n}$ in your setup is the probability of choosing as starting value something greater than $p_{n-1}$ and not greater than $p_n$. If the starting values are uniformly distributed this is proportional to $p_n - p_{n-1}$, which is not at all the same for all $p_n$. It may be debatable how much of a problem this is a in a given context, but certainly it will be skewed. –  Mar 21 '16 at 15:29
  • 1
    In fact, there are standards for such things: see http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf . Various algorithms for generation of primes are described in appendices B.3 and C. I can’t see any of them to use your strategy; they mostly apply rejection sampling. – Emil Jeřábek Mar 21 '16 at 15:31
  • @EmilJeřábek Does the secrecy of the gap matter? By Cramer's conjecture you can bruteforce it efficiently. In some algorithms like DH/DSA the primes are public. – joro Mar 21 '16 at 15:38
  • @quid Independently of justifications coming from finding large gaps, my question remain about the interest in finding "jumping champions" : could we find any application of finding which are the most frequent gaps appearing in prime distribution ? (in the work of Odlyzko and al., they are of course smaller than the known bounds) – Desiderius Severus Mar 22 '16 at 13:01
  • @DesideriusSeverus the point of the investigations is to understand (the distribution of) the prime numbers better, which not quite so coincidentally is a main reason for caring about zeta-functions, explicit formula, etc in the first place. –  Mar 22 '16 at 13:32
  • It’s not that the secrecy of the gap would matter per se, but that the distribution is non-uniform. This is relevant in cases where the primes are used as essential parts of private data (e.g., RSA keys), as it directly reduces their entropy, making them easier to brute-force. – Emil Jeřábek Mar 23 '16 at 15:54
  • I understand from the comments above that the implied constant in the $O(\sqrt(p_n)\log(p_n))$ is actually explicitly known. Would someone be so kind to modify the post and add in the constant? I am quite curious to learn how large exactly is 'very large' in this context! – Vincent Feb 01 '18 at 12:41
9

There is also a recent paper "Unexpected biases in the distribution of consecutive primes" by Robert J. Lemke Oliver and Kannan Soundararajan, which resulted in some sensational headlines. The relation to prime gaps is currently under discussion on math.SE.

Reikku Kulon
  • 231
  • 1
  • 1
2

A new (strong) result may affect proving Legendre's conjecture

The first thing you can read there is "prime gaps".

Konstantinos Gaitanas
  • 3,826
  • 12
    This conjecture, which I consider as historical artifact and not of much relevance today, basically is just a conjecture on prime gaps; to give this as motivation is almost circular. –  Mar 20 '16 at 19:19