Short intervals containing primes¶
1. Interval with primes, without congruence condition, saving a constant¶
The story seems to start in 1845 when Bertrand conjectured after numerical trials that the interval \((n,2n-3]\) contains a prime as soon as \(n\ge4\). This was proved by Pafnouti Tchebychev 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] ) ensures us that each of the intervals \([x,x+x^{0.525}]\) for \(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 \([x-K\sqrt{x}\log x,x]\) contains a prime, where \(K\) is an effective large constant and \(x\) is sufficiently large (cf [Wolke, 1983] for an account on this subject). A theorem of Schoenfeld [Schoenfeld, 1976] also tells us that the interval
\(\displaystyle [x-\sqrt{x}\log^2x/(4\pi),x]\) contains a prime for \(x\geq 599\) under the Riemann Hypothesis. These results are still far from the conjecture in [Cramer, 1936] on probabilistic grounds: the interval \([x-K\log^2x,x]\) contains a prime for any \(K > 1\) and \(x\geq x_0(K)\). Note that this statement has been proved for almost all intervals in a quadratic average sense in [Selberg, 1943] assuming the Riemann Hypothesis and replacing \(K\) by a function \(K(x)\) tending arbitrarily slowly to infinity.
[Schoenfeld, 1976] proved the following.
Theorem (1976)
Let \(x\) be a real number larger than \(2\,010\,760\). Then the interval \(\displaystyle \Bigl( x , x\Bigl(1+\frac1{16\,597}\Bigr))\) 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] and the Zeta grid project verified this hypothesis till height \(T_0=2.41\cdot 10^{11}\) and [Gourdon and Demichel, 2004] till height \(T_0=2.44 \cdot 10^{12}\) thus extending the work [Van de Lune et al., 1986] who had conducted such a verification in 1986 till height \(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 and Demichel, 2010] 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] can be replicated in a very rigorous setting, but that it may be difficult to do so with the results of [Gourdon and Demichel, 2004] with the hardware at our disposal.
In [Ramaré and Saouter, 2003], we used the value \(T_0=3.3 \cdot 10^{9}\) and obtained the following.
Theorem (2002)
Let \(x\) be a real number larger than \(10\,726\,905\,041\). Then the interval \(\displaystyle \Bigl( x \Bigl(1-\frac1{28\,314\,000}\Bigr),x \Bigr]\) contains at least one prime.
If one is interested in somewhat larger value, the paper [Ramaré and Saouter, 2003] also contains the following.
Theorem (2002)
Let \(x\) be a real number larger than \(\exp(53)\). Then the interval \(\displaystyle \Bigl( x \Bigl(1-\frac1{204\,879\,661}\Bigr),x \Bigr]\) 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 and Demichel, 2004], we can prove that
Theorem (2004, conditional)
Let \(x\) be a real number larger than \(\exp(60)\). Then the interval \(\displaystyle \Bigl( x \Bigl(1-\frac1{14\,500\,755\,538}\Bigr),x \Bigr]\) contains at least one prime.
Note that all prime gaps have been computed up to \(10^{15}\) in [Nicely, 1999], extending a result of [Young and Potler, 1989].
The above theorem is improved in ` <Biblio.html#>`_. We find in particular the next result.
Theorem (2014)
Let \(x\) be a real number larger than \(\exp(60)\). Then the interval \(\displaystyle \Bigl( x \Bigl(1-\frac1{1\,966\,196\,911}\Bigr),x \Bigr]\) contains at least one prime.
This is further improved in ` <Biblio.html#>`_. We find in particular the next result.
Theorem (2024)
Let \(x\) be a real number larger than \(\exp(60)\). Then the interval \(\displaystyle \Bigl( x \Bigl(1-\frac1{76\,900\,000\,000}\Bigr),x \Bigr]\) contains at least one prime.
2. Interval with primes, no congruence condition, saving more than a constant¶
In [Trudgian, 2016], we find
Theorem (2016)
Let \(x\) be a real number larger than \(2\,898\,242\). The interval \(\displaystyle \Bigl[ x, x \Bigl(1+\frac1{111(\log x)^2}\Bigr) \Bigr]\) contains at least one prime.
In [Dusart, 2018], we find
Theorem (2016)
Let \(x\) be a real number larger than \(468\,991\,632\). The interval \(\displaystyle \Bigl[ x, x \Bigl(1+\frac1{5000(\log x)^2}\Bigr) \Bigr]\) contains at least one prime.
Let \(x\) be a real number larger than \(89\,693\). The interval \(\displaystyle \Bigl[ x, x \Bigl(1+\frac1{\log^3 x}\Bigr) \Bigr]\) contains at least one prime.
The proof of these latter results has an asymptotical part, for \(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 \(10^{10} \le x \le 10^{20}\) and uses prime generation techniques [Maurer, 1995]: 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]. The generation technique we use relies on a theorem proven in [Brillhart et al., 1975] 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] that yield a fast primality test (for this limited range).
Let us recall here that a second line of approach following the original work of v Cebyv sev is still under examination though it does not give results as good as analytical means (see [Costa Pereira, 1989] for the latest result).
For very large numbers [Dudek, 2016] proved the following.
Theorem (2014)
The interval \((x,x+3 x^{2/3}]\) contains a prime for \(x\ge \exp(\exp(34.32))\).
This is improved in [Cully-Hugill, 2021] as follows.
Theorem (2021)
The interval \((x,x+3 x^{2/3}]\) contains a prime for \(x\ge \exp(\exp(33.99))\).
3. Interval with primes under RH, without any congruence condition¶
Theorem (2002)
Under the Riemann Hypothesis, the interval \(\bigl]x-\tfrac85\sqrt{x}\log x,x\bigr]\) contains a prime for \(x\ge2\).
This is improved upon in [Dudek, 2015] into:
Theorem (2015)
Under the Riemann Hypothesis, the interval \(\bigl]x-\tfrac4{\pi}\sqrt{x}\log x,x\bigr]\) contains a prime for \(x\ge2\).
In [Carneiro et al., 2019], the authors go one step further and prove the next result.
Theorem (2019)
Under the Riemann Hypothesis, the interval \(\bigl]x-\tfrac{22}{25}\sqrt{x}\log x,x\bigr]\) contains a prime for \(x\ge4\).
4. Interval with primes, with congruence condition¶
Collecting references: [McCurley, 1984], [McCurley, 1984], [Kadiri, 2008].