Editing Bertrand's postulate (section)

== Prime number theorem ==

The [[prime number theorem]] (PNT) implies that the number of primes up to ''x'', ''π(x)'', is roughly ''x''/log(''x''), so if we replace ''x'' with 2''x'' then we see the number of primes up to 2''x'' is asymptotically twice the number of primes up to ''x'' (the terms log(2''x'') and log(''x'') are asymptotically equivalent).  Therefore, the number of primes between ''n'' and 2''n'' is roughly ''n''/log(''n'') when ''n'' is large, and so in particular there are many more primes in this [[interval (mathematics)|interval]] than are guaranteed by Bertrand's postulate.  So Bertrand's postulate is comparatively weaker than the PNT. But PNT is a deep theorem, while Bertrand's Postulate can be stated more memorably and proved more easily, and also makes precise claims about what happens for small values of ''n''. (In addition, Chebyshev's theorem was proved before the PNT and so has historical interest.)

The similar and still unsolved [[Legendre's conjecture]] asks whether for every ''n''&nbsp;≥&thinsp;1, there is a prime ''p'' such that ''n''<sup>2</sup> < ''p'' < (''n''&nbsp;+&thinsp;1)<sup>2</sup>. Again we expect that there will be not just one but many primes between ''n''<sup>2</sup>  and (''n''&nbsp;+&thinsp;1)<sup>2</sup>, but in this case the PNT does not help: the number of primes up to ''x''<sup>2</sup> is asymptotic to ''x''<sup>2</sup>/log(''x''<sup>2</sup>) while the number of primes up to (''x''&nbsp;+&thinsp;1)<sup>2</sup> is asymptotic to (''x''&nbsp;+&nbsp;1)<sup>2</sup>/log((''x''&nbsp;+&nbsp;1)<sup>2</sup>), which is asymptotic to the estimate on primes up to ''x''<sup>2</sup>.  So, unlike the previous case of ''x'' and 2''x'', we do not get a proof of Legendre's conjecture for large ''n''. Error estimates on the PNT are not (indeed, cannot be) sufficient to prove the existence of even one prime in this interval. In greater detail, the PNT allows to estimate the boundaries for all ''ε > 0'', there exists an ''S'' such that for ''x > S'':
: <math> (1-\varepsilon)\frac {x^2}{2\log x} \; < \; \pi(x^2) \; < \; (1+\varepsilon)\frac {x^2}{2\log x} \; ,</math>
: <math> (1-\varepsilon)\frac {(x+1)^2}{2\log (x+1)} \; < \; \pi((x+1)^2) \; < \; (1+\varepsilon)\frac {(x+1)^2}{2\log (x+1)} \; .</math>

The ratio between the lower bound ''π((x+1)<sup>2</sup>)'' and the upper bound of ''π(x<sup>2</sup>)'' is
: <math> \frac {(x+1)^2}{x^2}\cdot \frac {\log x}{\log (x+1)} \cdot \frac {1-\varepsilon}{1+\varepsilon} \; .</math>

Note that since <math> \frac {(x+1)^2}{x^2} \rightarrow 1</math> when <math> x \rightarrow \infty</math>, <math> \frac {\log x}{\log (x+1)} < 1</math> for all ''x > 0'', and <math> \frac {1-\varepsilon}{1+\varepsilon} < 1 </math> for a fixed ''ε'', there exists an ''R'' such that the ratio above is less than 1 for all ''x > R''. Thus, it does not ensure that there exists a prime between ''π(x<sup>2</sup>)'' and ''π((x+1)<sup>2</sup>)''. More generally, these simple bounds are not enough to prove that there exists a prime between ''π(x<sup>n</sup>)'' and ''π((x+1)<sup>n</sup>)'' for any positive integer ''n > 1''.