Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
5  
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
2  
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
1  
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
show 4 more comments

1 Answer

up vote 8 down vote accepted

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

share|improve this answer
    
@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
add comment

Your Answer

 
discard

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.