# The tightest prime zipper

Define a prime zipper 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$.

This is a prime zipper, because Bertrand's Postulate says that, for every $n$, there is a prime $p$ such that $n < p < 2n$.

What is the slowest-growing known or conjectured prime zipper? Is there a polynomial prime zipper?

-
You can use results from analytic number theory to craft many such zippers. Using f(x)= ceil(x+x^{0.525}), and letting g(n) be the nth iterate of x_0 will be one of the slowest growing provable zippers. Alternately use f(x)=ceil(x + x/a), where a is something like 160000, and be sure to start large enough. I personally think ceil(x + log(x)^2) should work with x_0 = 8. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.11.09 –  Gerhard Paseman Nov 10 '12 at 1:12
The link doesn't work for me probably because the percent-encoding for "apostrophe" is wrong. You meant to link to this Wikipedia article, I guess? en.wikipedia.org/wiki/Bertrand%27s_postulate –  Yuichiro Fujiwara Nov 10 '12 at 1:14
I don't understand why Bertrand's postulate doesn't immediately imply that 2^n is a prime zipper. Am I misreading something? –  Qiaochu Yuan Nov 10 '12 at 5:55
It is conjectured, widely believed, but not proved, that there's always a prime between consecutive squares. –  Gerry Myerson Nov 10 '12 at 6:41
You might be interested in what Scott Aaronson has to say in section 3.3 of his article, " Why Philosophers Should Care About Computational Complexity", available on the arXiv: arxiv.org/abs/1108.1791. In footnote 17, he points out that "the first prime larger than 2k − 1" will count as a "known prime" if the gap between n-digit primes never exceeds n^2. –  Sam Hopkins Nov 11 '12 at 0:16

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.

Unconditional: 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}$.

Conditional: If we assume the Riemann Hypothesis, 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 Cramer's conjecture, 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$.

Also see this Wikipedia article on prime gaps.

Remark: 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.

** Avoid pointless functions such as $f(n)=p_n+1$.

-
@Eric: Thank you for this informed and precise answer! Your comments make clear that my question bumps into the as-yet not-totally resolved determination of largest prime gaps. –  Joseph O'Rourke Nov 11 '12 at 0:31
You can decrease the constant to $1/(8\pi)$ in your first conditional proof, a result of Schoenfeld. –  Charles Nov 16 '12 at 15:19