The tightest prime zipper

2012-11-10T01:02:30Z

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?

Answer by Eric Naslund for The tightest prime zipper

2012-11-10T01:14:03Z

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

The tightest prime zipper - MathOverflow

The tightest prime zipper

Answer by Eric Naslund for The tightest prime zipper