3
$\begingroup$

I believe there was an old conjecture that there's always a prime number between N and 2N.

What's the history and how is this proven is the easiest/elementary/deepest ways?

Improve this question
$\endgroup$
6
  • 6
    $\begingroup$ Is this a joke? This is an old theorem. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 26, 2009 at 23:17
  • 2
    $\begingroup$ No, not a joke, I'm pretty bad in standard number theory facts and I confused it with a bunch of other primes-related hard statements. I am very red-faced now though :) $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 26, 2009 at 23:20
  • $\begingroup$ Well, this was of course quite a stupid question of me because most part of analytic number theory would make no sense if such a bad approximation to pi(x) was not known... $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 26, 2009 at 23:22
  • 1
    $\begingroup$ Bertrand's Postulate is not a consequence of the Prime Number Theorem, so it doesn't follow that if BP was unproven then even a bad approximation of pi(x) would be beyond reach. What I'm trying to say is, the theorem and the proof are well-known but it's not quite such a stupid question :-) $\endgroup$
    – Alon Amit
    Commented Oct 27, 2009 at 4:45
  • 1
    $\begingroup$ @Alon, well, it is an asymptotic consequence. $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 27, 2009 at 7:50

7 Answers 7

Reset to default
13
$\begingroup$

Proven. This is called Bertrand's postulate. Here is Erdos' elementary proof; the original proof is due to Chebyshev.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There's also a brief but informative Wikipedia entry: en.wikipedia.org/wiki/Bertrand%27s_postulate $\endgroup$
    – Manny Reyes
    Commented Oct 26, 2009 at 23:19
  • 2
    $\begingroup$ Nathan Fine summarized Erdos' accomplishment thus: Chebyshev said, And I say it again, There's always a prime Between $n$ and $2n$. $\endgroup$
    – Gerry Myerson
    Commented Mar 16, 2010 at 21:46
7
$\begingroup$

For large enough x, x+x^.525 contains a prime see:

R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532–562.

For more on related results on prime gaps see the follwoing

http://en.wikipedia.org/wiki/Prime_gap

Improve this answer
$\endgroup$
4
$\begingroup$

There are various proofs of Bertrand's postulate. There is quite an easy one available if one treats it together with the proof of the usual (double) Chebyshev bound as a unit. One optimizes the proof of the Chebyshev bound for subsequently proving Bertrand's Postulate by the method of Ramanujan (getting rid of the appeal to Stirling's formula at the same time).

The history of Bertrand's Postulate is set forth in The Development of Prime Number Theory by Wladyslaw Narkiewicz.

A comment to the comment by Michael Lugo. The Prime Number Theorem is considerably harder to prove than Bertrand's Postulate, and getting the PNT in the form of good explicit inequalities is hard work on top of that (such inequalities exist, and are useful for some purposes).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am sorry that this failed to come out nicely. I ought to clean it up, but unfortunately I don't know how to about it. engelbrekt $\endgroup$
    – engelbrekt
    Commented Oct 27, 2009 at 18:15
  • $\begingroup$ Math Overflow currently has no LaTeX support, it could be best to make a reference to an outside site an post a pdf file there. $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 27, 2009 at 18:43
  • $\begingroup$ I cut the unreadable LaTeX. It would be easy for me to make a pdf file, but I have no webpage... $\endgroup$
    – engelbrekt
    Commented Oct 27, 2009 at 19:10
  • $\begingroup$ I think there are some wikis with LaTex support... $\endgroup$
    – Ilya Nikokoshev
    Commented Oct 27, 2009 at 19:25
4
$\begingroup$

See Chandrasekharan, Analyic Number Theory, for the proof by S. S. Pillai. It is quite easy.

Improve this answer
$\endgroup$
3
$\begingroup$

Erdös's proof is also contained in Chapter 2 of Proofs from THE BOOK, by Aigner & Ziegler.

Improve this answer
$\endgroup$
2
$\begingroup$

It has to be noted that we can also give a (conditional) proof of Bertrand's Postulate assuming the veracity of Goldbach's Conjecture. This was the subject matter of a filler piece that appeared on page 492 of the sixth issue (vol. 112) of the Monthly.

Also, it has to be noted that the reference given by Michael Lugo doesn't contain the original proof of Erdős. The original one is to be found here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the pointer to the original proof. The reference I gave is where I first saw the proof. (And the original proof was published in German; my German is not so good.) $\endgroup$
    – Michael Lugo
    Commented Nov 8, 2009 at 18:29
1
$\begingroup$

One remark to relate Bertrand's postulate to the prime number theorem: Chebyshev's work was related to bounding ratios of factorials--in particular $\frac{2n!}{n!n!}.$

His later proof that $C\frac{x}{\log x} < \pi(x) < D\frac{x}{\log x}$ made use of other ratios (in this case $\frac{30n!n!}{15n!5n!3n!}$). In theory one could try and improve the numbers used in the ratio to asymptotically prove the prime number theorem. Jonathan Bober (among others) have worked on this. He has catalogued many different combinations of ratios of factorials (this also ends up tying into G and E functions....but I'm already out of my depth of what I'm capable of explaining).

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .