Short intervals containing primes

1. Interval with primes, without any congruence condition
The story seems to start in 1845 when Bertrand conjectured after numerical trials that the interval ]n,2n3] contains a prime as soon as n4. This was proved by \v Ceby\v sev in 1852 in a famous work where he got the first good quantitative estimates for the number of primes less than a given bound, say x. By now, analytical means combined with sieve methods (see [Baker et al., 2001 †Baker, R., Harman, G., & Pintz, J. 2001
The difference between consecutive primes, III
Proc. London Math. Soc., 83(3), 532--562.
] ) ensures us that each of the intervals [x,x+x0.525] for xx0 contains at least one prime. This statement concerns only for the (very) large integers. It falls very close to what we can get under the assumption of the Riemann Hypothesis: the interval [xKxlogx,x] contains a prime, where K is an effective large constant and x is sufficiently large (cf [Wolke, 1983 †Wolke, D. 1983
On the explicit formula of Riemann-von Mangoldt, II
J. London Math. Soc., 2(28).
] for an account on this subject). A theorem of Schoenfeld [Schoenfeld, 1976 †Schoenfeld, L. 1976
Sharper bounds for the Chebyshev Functions ϑ(X) and ψ(X) II
Math. Comp., 30(134), 337--360.
] also tells us that the interval
[xxlog2x/(4π),x]
contains a prime for x599 under the Riemann Hypothesis. These results are still far from the conjecture in [Cramer, 1936 †Cramer, H. 1936
On the order of magnitude of the difference between consecutive prime numbers
Acta Arith., 2, 23--46.
] on probabilistic grounds: the interval [xKlog2x,x] contains a prime for any K>1 and xx0(K). Note that this statement has been proved for almost all intervals in a quadratic average sense in [Selberg, 1943 †Selberg, A. 1943
On the normal density of primes in small intervals, and the difference between consecutive primes
Archiv Math. Naturv., B.47(6), 82--105.
] assuming the Riemann Hypothesis and replacing K by a function K(x) tending arbitrarily slowly to infinity. [Schoenfeld, 1976 †Schoenfeld, L. 1976
Sharper bounds for the Chebyshev Functions ϑ(X) and ψ(X) II
Math. Comp., 30(134), 337--360.
] proved the following.
Theorem (1976)
Let x be a real number larger than 2010760. Then the interval
]x(1116597),x]
contains at least one prime.
The main ingredient is the explicit formula and a numerical verification of the Riemann hypothesis. From a numerical point of view, the Riemann Hypothesis is known to hold up to a very large height (and larger than in 1976). [Wedeniwski, 2002 †Wedeniwski, S. 2002
On the Riemann hypothesis
http://www.zetagrid.net/zeta/announcements.html
] and the Zeta grid project verified this hypothesis till height T0=2.411011 and [Gourdon & Demichel, 2004 †Gourdon, X., & Demichel, P. 2004
The 1013 first zeros of the Riemann Zeta Function and zeros computations at very large height
http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeros1e13-1e24.pdf
] till height T0=2.441012 thus extending the work [Van de Lune et al., 1986 †Van de Lune, J., te Riele, H.J.J., & D.T.Winter. 1986
On the zeros of the Riemann zeta-function in the critical strip. IV
Math. Comp., 46(174), 667--681.
] who had conducted such a verification in 1986 till height 5.45×108. This latter computations has appeared in a refereed journal, but this is not the case so far concerning the other computations; section 4 of the paper [Saouter & Demichel, 2010 †Saouter, Y., & Demichel, P. 2010
A sharp region where {π(x)li(x)} is positive
Math. Comp., 79(272), 2395--2405.
] casts some doubts on whether all the zeros where checked. Discussions in 2012 with Dave Platt from the university of Bristol led me to believe that the results of [Wedeniwski, 2002 †Wedeniwski, S. 2002
On the Riemann hypothesis
http://www.zetagrid.net/zeta/announcements.html
] can be replicated in a very rigorous setting, but that it may be difficult to do so with the results of [Gourdon & Demichel, 2004 †Gourdon, X., & Demichel, P. 2004
The 1013 first zeros of the Riemann Zeta Function and zeros computations at very large height
http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeros1e13-1e24.pdf
] with the hardware at our disposal. In [Ramaré & Saouter, 2003 †Ramaré, O., & Saouter, Y. 2003
Short effective intervals containing primes
J. Number Theory, 98, 10--33.
], we used the value T0=3.3109 and obtained the following.
Theorem (2002)
Let x be a real number larger than 10726905041. Then the interval
]x(1128314000),x]
contains at least one prime.
If one is interested in somewhat larger value, the paper [Ramaré & Saouter, 2003 †Ramaré, O., & Saouter, Y. 2003
Short effective intervals containing primes
J. Number Theory, 98, 10--33.
] also contains the following.
Theorem (2002)
Let x be a real number larger than exp(53). Then the interval
]x(11204879661),x]
contains at least one prime.
Increasing the lower bound in x only improves the constant by less than 5 percent. If we rely on [Gourdon & Demichel, 2004 †Gourdon, X., & Demichel, P. 2004
The 1013 first zeros of the Riemann Zeta Function and zeros computations at very large height
http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeros1e13-1e24.pdf
], we can prove that
Theorem (2004, conditional)
Let x be a real number larger than exp(60). Then the interval
]x(1114500755538),x]
contains at least one prime.
Note that all prime gaps have been computed up to 1015 in [Nicely, 1999 †Nicely, T.R. 1999
New maximal primes gaps and first occurences
Math. Comp., 68(227), 1311--1315.
], extending a result of [Young & Potler, 1989 †Young, A., & Potler, J. 1989
First occurence prime gaps
Math. Comp., 52(185), 221--224.
]. The proof of these latter results has an asymptotical part, for x1020 where we used the numerical verification of the Riemann hypothesis together with two other arguments: a (very strong) smoothing argument and a use of the Brun-Titchmarsh inequality. The second part is of algorithmic nature and covers the range 1010x1020 and uses prime generation techniques [Maurer, 1995 †Maurer, U. 1995
Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters
Journal of Cryptology, 8(3), 123--156.
]: we only look at families of numbers whose primality can be established with one or two Fermat-like or Pocklington's congruences. This kind of technique has been already used in a quite similar problem in [Deshouillers et al., 1998 †Deshouillers, J.-M., te Riele, H.J.J., & Saouter, Y. 1998
New experimental results concerning the Goldbach conjecture
In: Buhler, J.P. (ed), Algorithmic number theory. Lect. Notes Comput. Sci., no. 1423.
]. The generation technique we use relies on a theorem proven in [Brillhart et al., 1975 †Brillhart, J., Lehmer, D.H., & Selfridge, J.L. 1975
New primality crietria and factorizations for 2m±1
Math. Comp., 29(130), 620--647.
] and enables us to generate dense enough families for the upper part of the range to be investigated. For the remaining (smaller) range, we use theorems of [Jaeschke, 1993 †Jaeschke, G. 1993
On strong pseudoprimes to several bases
Math. Comp., 61(204), 915--926.
] that yield a fast primality test (for this limited range).
Theorem (2002)
Under the Riemann Hypothesis, the interval ]x85xlogx,x] contains a prime for x2.


Let us recall here that a second line of approach following the original work of \v Ceby\v sev is still under examination though it does not give results as good as analytical means (see [Costa Pereira, 1989 †Costa Pereira, N. 1989
Elementary estimates for the Chebyshev function ψ(X) and for the Möbius function M(X)
Acta Arith., 52, 307--337.
] for the latest result).
2. Interval with primes, with congruence condition
Collecting references: [McCurley, 1984a †McCurley, K.S. 1984a
Explicit estimates for the error term in the prime number theorem for arithmetic progressions
Math. Comp., 42, 265--285.
], [McCurley, 1984b †McCurley, K.S. 1984b
Explicit estimates for θ(x;3,) and ψ(x;3,)
Math. Comp., 42, 287--296.
], [Kadiri, 2008 †Kadiri, H. 2008
Short effective intervals containing primes in arithmetic progressions and the seven cube problem
Math. Comp., 77(263), 1733--1748.
].

Last updated on December 27th, 2012, by Olivier Ramaré