Short intervals containing primes ================================= .. if-builder:: html .. toctree:: :maxdepth: 2 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 :math:`(n,2n-3]` contains a prime as soon as :math:`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 :math:`x`. By now, analytical means combined with sieve methods (see :cite:`Baker-Harman-Pintz01` ) ensures us that each of the intervals :math:`[x,x+x^{0.525}]` for :math:`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 :math:`[x-K\sqrt{x}\log x,x]` contains a prime, where :math:`K` is an effective large constant and :math:`x` is sufficiently large (cf :cite:`Wolke83` for an account on this subject). A theorem of Schoenfeld :cite:`Schoenfeld76` also tells us that the interval :math:`\displaystyle [x-\sqrt{x}\log^2x/(4\pi),x]` contains a prime for :math:`x\geq 599` under the Riemann Hypothesis. These results are still far from the conjecture in :cite:`Cramer36` on probabilistic grounds: the interval :math:`[x-K\log^2x,x]` contains a prime for any :math:`K > 1` and :math:`x\geq x_0(K)`. Note that this statement has been proved for almost all intervals in a quadratic average sense in :cite:`Selberg43` assuming the Riemann Hypothesis and replacing :math:`K` by a function :math:`K(x)` tending arbitrarily slowly to infinity. :cite:`Schoenfeld76` proved the following. .. admonition:: Theorem (1976) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`2\,010\,760`. Then the interval :math:`\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). :cite:`Wedeniwski02` and the Zeta grid project verified this hypothesis till height :math:`T_0=2.41\cdot 10^{11}` and :cite:`Gourdon-Demichel04` till height :math:`T_0=2.44 \cdot 10^{12}` thus extending the work :cite:`Lune-Riele-Winter86` who had conducted such a verification in 1986 till height :math:`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 :cite:`Saouter-Demichel10` 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 :cite:`Wedeniwski02` can be replicated in a very rigorous setting, but that it may be difficult to do so with the results of :cite:`Gourdon-Demichel04` with the hardware at our disposal. In :cite:`Ramare-Saouter02`, we used the value :math:`T_0=3.3 \cdot 10^{9}` and obtained the following. .. admonition:: Theorem (2002) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`10\,726\,905\,041`. Then the interval :math:`\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 :cite:`Ramare-Saouter02` also contains the following. .. admonition:: Theorem (2002) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`\exp(53)`. Then the interval :math:`\displaystyle \Bigl( x \Bigl(1-\frac1{204\,879\,661}\Bigr),x \Bigr]` contains at least one prime. Increasing the lower bound in :math:`x` only improves the constant by less than 5 percent. If we rely on :cite:`Gourdon-Demichel04`, we can prove that .. admonition:: Theorem (2004, conditional) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`\exp(60)`. Then the interval :math:`\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 :math:`10^{15}` in :cite:`Nicely99`, extending a result of :cite:`Young-Potler89`. The above theorem is improved in ` `_. We find in particular the next result. .. admonition:: Theorem (2014) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`\exp(60)`. Then the interval :math:`\displaystyle \Bigl( x \Bigl(1-\frac1{1\,966\,196\,911}\Bigr),x \Bigr]` contains at least one prime. This is further improved in ` `_. We find in particular the next result. .. admonition:: Theorem (2024) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`\exp(60)`. Then the interval :math:`\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 :cite:`Trudgian16`, we find .. admonition:: Theorem (2016) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`2\,898\,242`. The interval :math:`\displaystyle \Bigl[ x, x \Bigl(1+\frac1{111(\log x)^2}\Bigr) \Bigr]` contains at least one prime. In :cite:`Dusart16`, we find .. admonition:: Theorem (2016) :class: thm-tme-emt Let :math:`x` be a real number larger than :math:`468\,991\,632`. The interval :math:`\displaystyle \Bigl[ x, x \Bigl(1+\frac1{5000(\log x)^2}\Bigr) \Bigr]` contains at least one prime. Let :math:`x` be a real number larger than :math:`89\,693`. The interval :math:`\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 :math:`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 :math:`10^{10} \le x \le 10^{20}` and uses prime generation techniques :cite:`Maurer95`: 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 :cite:`Deshouillers-teRiele-Saouter98`. The generation technique we use relies on a theorem proven in :cite:`Brillhart-Lehmer-Selfridge75` 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 :cite:`Jaeschke93` 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 Ceby\v sev is still under examination though it does not give results as good as analytical means (see :cite:`CostaPereira89` for the latest result). For very large numbers :cite:`Dudek16b` proved the following. .. admonition:: Theorem (2014) :class: thm-tme-emt The interval :math:`(x,x+3 x^{2/3}]` contains a prime for :math:`x\ge \exp(\exp(34.32))`. This is improved in :cite:`Cully21` as follows. .. admonition:: Theorem (2021) :class: thm-tme-emt The interval :math:`(x,x+3 x^{2/3}]` contains a prime for :math:`x\ge \exp(\exp(33.99))`. 3. Interval with primes under RH, without any congruence condition ------------------------------------------------------------------ .. admonition:: Theorem (2002) :class: thm-tme-emt Under the Riemann Hypothesis, the interval :math:`\bigl]x-\tfrac85\sqrt{x}\log x,x\bigr]` contains a prime for :math:`x\ge2`. This is improved upon in :cite:`Dudek15` into: .. admonition:: Theorem (2015) :class: thm-tme-emt Under the Riemann Hypothesis, the interval :math:`\bigl]x-\tfrac4{\pi}\sqrt{x}\log x,x\bigr]` contains a prime for :math:`x\ge2`. In :cite:`Carneiro-Milinovich-Soundararajan19`, the authors go one step further and prove the next result. .. admonition:: Theorem (2019) :class: thm-tme-emt Under the Riemann Hypothesis, the interval :math:`\bigl]x-\tfrac{22}{25}\sqrt{x}\log x,x\bigr]` contains a prime for :math:`x\ge4`. 4. Interval with primes, with congruence condition -------------------------------------------------- Collecting references: :cite:`McCurley84-2`, :cite:`McCurley84-3`, :cite:`Kadiri05-2`.