Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.