5
$\begingroup$

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

  • 2
    I'm not sure this is known.2012-05-08
  • 2
    The Oppermann's conjecture conjectures that there is a prime between $x - \sqrt{x}$, $x$ and $x + \sqrt{x}$.2012-05-08

1 Answers 1

10

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

  • 0
    Looking at the conjectures for prime gaps $g_n$, from [Riemann](http://en.wikipedia.org/wiki/Riemann_hypothesis#Large_prime_gap_conjecture) $g(p_n)=O(\sqrt{p_n} \log p_n)$, to [Cramer](http://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture) $g(p_n)=O((\log p_n)^2),\ $ reminds me a little of the complexity evolution from FastFourierTransform to QuantumFourierTranform...2012-05-08
  • 0
    @draks: I am unfamiliar with this, but curious, would you mind elaborating?2012-05-08
  • 1
    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](http://mathworld.wolfram.com/FourierMatrix.html). 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 exist2012-05-08
  • 1
    [Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer](http://xxx.lanl.gov/abs/quant-ph/9508027). Now replace $n$ by $\log p_n$ and we are back where we started (beside some scalar factors).2012-05-08
  • 0
    To all that are interested in Quantum Information: The [Quantum Information and Foundations](http://area51.stackexchange.com/proposals/36039/quantum-information-and-foundations?referrer=G-oXDJgd8JaWXYyF_kRbzQ2) proposal is currently in commitment phase.2012-05-08
  • 0
    @draks: Thanks for the comment!2012-05-08