Take the 2-minute tour ×

What is the asymptotically slowest growing function $f(x)$, such that there exists constants $a$ and $b$, such that for all $x>a$, there is always a prime between $x$ and $x+bf(x)$?

$f(x)=x$ works, does $\sqrt{x}$ work, $\log(x)$, or $\log\log(x)$?

share|improve this question
I'm not sure this is known. –  Alex Becker May 8 '12 at 7:22
The Oppermann's conjecture conjectures that there is a prime between $x - \sqrt{x}$, $x$ and $x + \sqrt{x}$. –  user17762 May 8 '12 at 7:29
add comment

1 Answer

up vote 10 down vote accepted

What you are looking at is an upper bound for prime gaps. Bertrands postulate states that there is always a prime between $x$ and $2x$, but this has been improved significantly. The most recent result due to Baker Harman and Pintz states that $$\pi\left(x+x^{0.525}\right) -\pi(x)\gg \frac{x^{0.525}}{\log x}.$$ This means that for sufficiently large $x$, there is always a prime between $x$ and $x+x^{0.525}$. This implies for example that there is always a prime between consecutive cubes, that is there is always a prime in the interval $(x^3,(x+1)^3)$.

As for the expected result, the Wikipedia article covers this as well, see Conjectures about prime gaps. In particular, the Riemann Hypothesis tells us that for any $\epsilon$, we will have a prime in the interval $(x,x+x^{\frac{1}{2}+\epsilon})$ for sufficiently large $x$. Cramer made the much stronger conjecture that there is always be a prime between $x$ and $x+\log^2x$ for sufficiently large $x$.

share|improve this answer
Looking at the conjectures for prime gaps $g_n$, from Riemann $g(p_n)=O(\sqrt{p_n} \log p_n)$, to Cramer $g(p_n)=O((\log p_n)^2),\ $ reminds me a little of the complexity evolution from FastFourierTransform to QuantumFourierTranform... –  draks ... May 8 '12 at 9:17
@draks: I am unfamiliar with this, but curious, would you mind elaborating? –  Eric Naslund May 8 '12 at 10:37
The sequence of $n$ complex numbers $x_0, ..., x_{n−1}$ can be [fast fourier transformed]() into another sequence of $n$ complex numbers in $O_{FFT}(n2^n)$ operations. This is more efficient than just matrix-vector multiplying ${\bf F}\vec x$, with ${\bf F}$ the FourierMatrix. It was found that $\bf F$ can be implemented on quantum computer in only $O_{QFT}(n^2)$ steps, which was used by Peter Shor to show that there exist –  draks ... May 8 '12 at 11:10
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Now replace $n$ by $\log p_n$ and we are back where we started (beside some scalar factors). –  draks ... May 8 '12 at 11:10
To all that are interested in Quantum Information: The Quantum Information and Foundations proposal is currently in commitment phase. –  draks ... May 8 '12 at 17:46
show 1 more comment

Your Answer


