The tightest prime zipper - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:55:25Z http://mathoverflow.net/feeds/question/111954 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111954/the-tightest-prime-zipper The tightest prime zipper Joseph O'Rourke 2012-11-10T01:02:30Z 2012-11-10T12:36:11Z <p>Define a <em>prime zipper</em> as an increasing function $f(n)$ mapping $\mathbb{N}$ into $\mathbb{N}$ with the property that, for every $n \ge 1$, there is at least one prime within the inclusive interval $[ f(n), f(n+1) ]$. For example, let $f(n)=2^n$. <br /> &nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/PrimeZipper.jpg" alt="PrimeZipper" /> <br /> This is a prime zipper, because <a href="http://en.wikipedia.org/wiki/Bertrand%27s_postulate" rel="nofollow">Bertrand's Postulate</a> says that, for every $n$, there is a prime $p$ such that $n &lt; p &lt; 2n$.</p> <p>What is the slowest-growing known or conjectured prime zipper? Is there a polynomial prime zipper?</p> http://mathoverflow.net/questions/111954/the-tightest-prime-zipper/111956#111956 Answer by Eric Naslund for The tightest prime zipper Eric Naslund 2012-11-10T01:14:03Z 2012-11-10T02:21:17Z <p>The slowest growing zipper will depend on the size of $p_{n+1}-p_n$ where $p_n$ is the $n^{th}$ prime number. There are many results regarding the size of the largest prime gap. </p> <p><strong>Unconditional:</strong> The work of Baker, Harman and Pintz shows that $$p_{n+1}-p_n \ll p_n^{0.525}$$ for some computable constant. This means that your zipper function may be taken to be $f(n)=Cn^{40/19}$ for some constant $C$. The $\frac{40}{19}$ appears in the exponent because $\frac{40}{19}=\frac{1}{1-0.525}$. </p> <p><strong>Conditional:</strong> If we assume the <a href="http://en.wikipedia.org/wiki/Riemann_hypothesis" rel="nofollow">Riemann Hypothesis</a>, then we have $$p_{n+1}-p_n \ll \sqrt {p_n}\log p_n,$$ and we may take $f(n)=n^2 \log n$. Assuming <a href="http://en.wikipedia.org/wiki/Cram%25C3%25A9r%2527s_conjecture" rel="nofollow">Cramer's conjecture</a>, which says that $$p_{n+1}-p_n =O\left((\log p_n)^2\right),$$ would allows us to take $f(n)=Cn(\log n)^2$ for some constant $C$.</p> <p>Also see this <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">Wikipedia article on prime gaps.</a></p> <p><strong>Remark:</strong> Note that finding a prime zipper which grows slower than $f(n)=Cn^{40/19}$ would imply better bounds on the largest prime gap, so your question is equivalent to asking what is the largest prime gap.</p> <p>** Avoid pointless functions such as $f(n)=p_n+1$.</p>