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]$]n,2n-3]$ contains a prime as soon as n4$n\ge4$. 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$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]$[x,x+x^{0.525}]$ for xx0$x \geq x_0$ 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]$[x-K\sqrt{x}\log x,x]$ contains a prime, where K$K$ is an effective large constant and x$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)$\vartheta(X)$ and ψ(X)$\psi(X)$ II
Math. Comp., 30(134), 337--360.
] also tells us that the interval
[xxlog2x/(4π),x]
contains a prime for x599$x\geq 599$ 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]$[x-K\log^2x,x]$ contains a prime for any K>1$K>1$ and xx0(K)$x\geq x_0(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$K$ by a function K(x)$K(x)$ tending arbitrarily slowly to infinity. [Schoenfeld, 1976 †Schoenfeld, L. 1976
Sharper bounds for the Chebyshev Functions ϑ(X)$\vartheta(X)$ and ψ(X)$\psi(X)$ II
Math. Comp., 30(134), 337--360.
] proved the following.
Theorem (1976)
Let x$x$ be a real number larger than 2010760$2\,010\,760$. 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$T_0=2.41\cdot 10^{11}$ and [Gourdon & Demichel, 2004 †Gourdon, X., & Demichel, P. 2004
The 1013$10^{13}$ 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$T_0=2.44 \cdot 10^{12}$ 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$5.45\times10^8$. 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)$\pi(x)-{\rm 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$10^{13}$ 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$T_0=3.3 \cdot 10^{9}$ and obtained the following.
Theorem (2002)
Let x$x$ be a real number larger than 10726905041$10\,726\,905\,041$. 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$x$ be a real number larger than exp(53)$\exp(53)$. Then the interval
]x(11204879661),x]
contains at least one prime.
Increasing the lower bound in x$x$ only improves the constant by less than 5 percent. If we rely on [Gourdon & Demichel, 2004 †Gourdon, X., & Demichel, P. 2004
The 1013$10^{13}$ 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$x$ be a real number larger than exp(60)$\exp(60)$. Then the interval
]x(1114500755538),x]
contains at least one prime.
Note that all prime gaps have been computed up to 1015$10^{15}$ 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$x\ge 10^{20}$ 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$10^{10} \le x \le 10^{20}$ 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$2^m \pm 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]$\bigl]x-\tfrac85\sqrt{x}\log x,x\bigr]$ contains a prime for x2$x\ge2$.

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)$\psi(X)$ and for the Möbius function M(X)$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,)$\theta(x;3,\ell)$ and ψ(x;3,)$\psi(x;3,\ell)$
Math. Comp., 42, 287--296.