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

Is there a result in the spirit of Bertrand-Chebyshev which talks about the existence of prime powers between n and 2n (or 3n or something like that) for n large?

share|improve this question
add comment

3 Answers 3

up vote 7 down vote accepted

It follows from the prime number theorem that for fixed $k$, provided $n$ is sufficiently large, there is a prime $p$ such that $p^k$ is between $n$ and $2n$. Does this answer your question?

share|improve this answer
    
Thank you very much for your quick answer. Yes, it answers the question, and it goes to show the power of the PNT. –  Chebolu Apr 27 '11 at 16:01
1  
I wonder if there is an elementary proof of this without using PNT, like Erdős' proof of Bertrand's Postulate? –  Tony Huynh Apr 27 '11 at 17:24
add comment

Actually there is a power of 2. It goes to show the power of binary arithmetic ... : write 2n in binary and write zeroes after the initial one.

share|improve this answer
2  
In other words, if $2^{k - 1}$ is the largest power of 2 less than n, then $n \leq 2^k < 2n$? –  Ryan Reich Apr 27 '11 at 18:14
    
Yes, you said it. –  Charles Matthews Apr 27 '11 at 18:43
add comment

For fixed $k$, the existence of a prime power $p^k$ between $n$ and $2n$ is (asymptotically) equivalent to the existence of a prime $p$ between $m$ and $\sqrt[k]{2} m$ where $m = \sqrt[k]{n}$. Bachraoui gives an elementary proof here that there exists a prime between $m$ and $\frac{3}{2} m$ for sufficiently large $m$.

I remember reading on MO that it is known that similar elementary proofs exist for showing the existence of primes between $m$ and $(1 + \epsilon) m$ for any $\epsilon > 0$ and, furthermore, that the existence of these proofs itself depends on the PNT. However, I can't track down where I read this.

share|improve this answer
3  
Possibly it is this question you have in mind: mathoverflow.net/questions/53498/nontrivial-circular-arguments –  quid Apr 27 '11 at 19:00
    
Yes, that's the one. –  Qiaochu Yuan Apr 27 '11 at 20:11
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.