# Always a prime between $x$ and $x+cf(x)$

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)$?

-
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

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$.
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
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