Bertrand's postulate

In number theory, Bertrand's postulate is a theorem stating that for any integer ${\displaystyle n>3}$, there always exists at least one prime number ${\displaystyle p}$ with

${\displaystyle n<p<2n-2.}$

A less restrictive formulation is: for every ${\displaystyle n>1}$ there is always at least one prime ${\displaystyle p}$ such that

${\displaystyle n<p<2n.}$

Another formulation, where ${\displaystyle p_{n}}$ is the ${\displaystyle n}$-th prime, is for ${\displaystyle n\geq 1}$

${\displaystyle p_{n+1}<2p_{n}.}$[1]

This statement was first conjectured in 1845 by Joseph Bertrand[2] (1822–1900). Bertrand himself verified his statement for all numbers in the interval [2, 3 × 10⁶]. His conjecture was completely proved by Chebyshev (1821–1894) in 1852[3] and so the postulate is also called the Bertrand–Chebyshev theorem or Chebyshev's theorem. Chebyshev's theorem can also be stated as a relationship with ${\displaystyle \pi (x)}$, where ${\displaystyle \pi (x)}$ is the prime counting function (number of primes less than or equal to ${\displaystyle x\,}$):

${\displaystyle \pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$, for all ${\displaystyle x\geq 2}$.

Prime number theorem

The prime number theorem (PNT) implies that the number of primes up to x is roughly x/ln(x), so if we replace x with 2x then we see the number of primes up to 2x is asymptotically twice the number of primes up to x (the terms ln(2x) and ln(x) are asymptotically equivalent). Therefore, the number of primes between n and 2n is roughly n/ln(n) when n is large, and so in particular there are many more primes in this 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 > 1, there is a prime p, such that n² < p < (n + 1)². Again we expect that there will be not just one but many primes between n² and (n + 1)², but in this case the PNT doesn't help: the number of primes up to x² is asymptotic to x²/ln(x²) while the number of primes up to (x + 1)² is asymptotic to (x + 1)²/ln((x + 1)²), which is asymptotic to the estimate on primes up to x². So unlike the previous case of x and 2x we don't get a proof of Legendre's conjecture even for all large n. Error estimates on the PNT are not (indeed, cannot be) sufficient to prove the existence of even one prime in this interval.

Generalizations

In 1919, Ramanujan (1887–1920) used properties of the Gamma function to give a simpler proof.[4] The short paper included a generalization of the postulate, from which would later arise the concept of Ramanujan primes. Further generalizations of Ramanujan primes have also happened; for instance, there is a proof that

${\displaystyle 2p_{i-n}>p_{i}{\text{ for }}i>k{\text{ where }}k=\pi (p_{k})=\pi (R_{n})\,,}$

with p_k the kth prime and R_n the nth Ramanujan prime.

Other generalizations of Bertrand's Postulate have been obtained using elementary methods. (In the following, n runs through the set of positive integers.) In 2006, M. El Bachraoui proved that there exists a prime between 2n and 3n. In 1973, Denis Hanson proved that there exists a prime between 3n and 4n.[5] Furthermore, in 2011, Andy Loo proved that as n tends to infinity, the number of primes between 3n and 4n also goes to infinity, thereby generalizing Erdős' and Ramanujan's results (see the section on Erdős' theorems below). The first result is obtained with elementary methods. The second one is based on analytic bounds for the factorial function.

Sylvester's theorem

Bertrand's postulate was proposed for applications to permutation groups. Sylvester (1814–1897) generalized the weaker statement with the statement: the product of k consecutive integers greater than k is divisible by a prime greater than k. Bertrand's (weaker) postulate follows from this by taking k = n, and considering the k numbers n + 1, n + 2, up to and including n + k = 2n, where n > 1. According to Sylvester's generalization, one of these numbers has a prime factor greater than k. Since all these numbers are less than 2(k + 1), the number with a prime factor greater than k has only one prime factor, and thus is a prime. Note that 2n is not prime, and thus indeed we now know there exists a prime p with n < p < 2n.

Erdős's theorems

In 1932, Erdős (1913–1996) also published a simpler proof using binomial coefficients and the Chebyshev function ϑ, defined as:

${\displaystyle \vartheta (x)=\sum _{p=2}^{x}\ln(p)}$

where p ≤ x runs over primes. See proof of Bertrand's postulate for the details.[6]

Erdős proved in 1934 that for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n. An equivalent statement had been proved in 1919 by Ramanujan (see Ramanujan prime).

Better results

It follows from the prime number theorem that for any real ${\displaystyle \varepsilon >0}$ there is a ${\displaystyle n_{0}>0}$ such that for all ${\displaystyle n>n_{0}}$ there is a prime ${\displaystyle p}$ such that ${\displaystyle n<p<(1+\varepsilon )n}$. It can be shown, for instance, that

${\displaystyle \lim _{n\to \infty }{\frac {\pi ((1+\varepsilon )n)-\pi (n)}{n/\log n}}=\varepsilon ,}$

which implies that ${\displaystyle \pi ((1+\varepsilon )n)-\pi (n)}$ goes to infinity (and, in particular, is greater than 1 for sufficiently large ${\displaystyle n}$).[7]

Non-asymptotic bounds have also been proved. In 1952, Jitsuro Nagura proved that for ${\displaystyle n\geq 25}$ there is always a prime between ${\displaystyle n}$ and ${\displaystyle \left(1+{\frac {1}{5}}\right)n}$.[8]

In 1976, Lowell Schoenfeld showed that for ${\displaystyle n\geq 2010760}$, there is always a prime ${\displaystyle p}$ in the open interval ${\displaystyle n<p<\left(1+{\frac {1}{16597}}\right)n}$.[9]

In his 1998 doctoral thesis, Pierre Dusart improved the above result, showing that for ${\displaystyle k\geq 463}$, ${\displaystyle p_{k+1}\leq \left(1+{\frac {1}{2\ln ^{2}{p_{k}}}}\right)p_{k}}$, and in particular for ${\displaystyle x\geq 3275}$, there exists a prime ${\displaystyle p}$ in the interval ${\displaystyle x<p\leq \left(1+{\frac {1}{2\ln ^{2}{x}}}\right)x}$.[10]

In 2010 Pierre Dusart proved that for ${\displaystyle x\geq 396738}$ there is at least one prime ${\displaystyle p}$ in the interval ${\displaystyle x<p\leq \left(1+{\frac {1}{25\ln ^{2}{x}}}\right)x}$.[11]

In 2016, Pierre Dusart improved his result from 2010, showing (Proposition 5.4) that, if ${\displaystyle x\geq 89693}$, there is at least one prime ${\displaystyle p}$ in the interval ${\displaystyle x<p\leq \left(1+{\frac {1}{\ln ^{3}{x}}}\right)x}$.[12] He also shows (Corollary 5.5) that, for ${\displaystyle x\geq 468991632}$, there is at least one prime ${\displaystyle p}$ in the interval ${\displaystyle x<p\leq \left(1+{\frac {1}{5000\ln ^{2}{x}}}\right)x}$.

Baker, Harman and Pintz proved that there is a prime in the interval ${\displaystyle [x-x^{.525},\,x]}$ for all sufficiently large ${\displaystyle x}$.[13]

Consequences

• The sequence of primes, along with 1, is a complete sequence; any positive integer can be written as a sum of primes (and 1) using each at most once.
• The only harmonic number that is an integer is the number 1.[14]

See also

• Oppermann's conjecture

Notes

1. Ribenboim, Paulo (2004). The Little Book of Bigger Primes. New York: Springer-Verlag. p. 181. ISBN 978-0-387-20169-6.
2. Bertrand, Joseph (1845), "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.", Journal de l'École Royale Polytechnique (in French), 18 (Cahier 30): 123–140.
3. Tchebychev, P. (1852), "Mémoire sur les nombres premiers." (PDF), Journal de mathématiques pures et appliquées, Série 1 (in French): 366–390. (Proof of the postulate: 371-382). Also see Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp.15-33, 1854
4. Ramanujan, S. (1919). "A proof of Bertrand's postulate". Journal of the Indian Mathematical Society. 11: 181–182.
5. Hanson, Denis (1973), "On a theorem of Sylvester and Schur", Canadian Mathematical Bulletin, 16 (2): 195–199, doi:10.4153/CMB-1973-035-3.
6. Erdős, P. (1932), "Beweis eines Satzes von Tschebyschef" (PDF), Acta Litt. Sci. (Szeged) (in German), 5 (1930-1932): 194–198
7. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008, p. 494.
8. Nagura, J (1952). "On the interval containing at least one prime number". Proceedings of the Japan Academy, Series A. 28 (4): 177–181. doi:10.3792/pja/1195570997.
9. Lowell Schoenfeld (April 1976). "Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x), II". Mathematics of Computation. 30 (134): 337–360. doi:10.2307/2005976. JSTOR 2005976.
10. Dusart, Pierre (1998), Autour de la fonction qui compte le nombre de nombres premiers (PDF) (PhD thesis) (in French)
11. Dusart, Pierre (2010). "Estimates of Some Functions Over Primes without R.H.". arXiv:1002.0442 [math.NT].
12. Dusart, Pierre (2016). "Explicit estimates of some functions over primes". The Ramanujan Journal. 45: 227–251. doi:10.1007/s11139-016-9839-4. S2CID 125120533.
13. Baker, R. C.; Harman, G.; Pintz, J. (2001). "The difference between consecutive primes, II". Proceedings of the London Mathematical Society. 83 (3): 532–562. CiteSeerX 10.1.1.360.3671. doi:10.1112/plms/83.3.532.
14. Ronald L., Graham; Donald E., Knuth; Oren, Patashnik (1994). Concrete Mathematics. Addison-Wesley.

Bibliography

• P. Erdős (1934). "A Theorem of Sylvester and Schur". Journal of the London Mathematical Society. 9 (4): 282–288. doi:10.1112/jlms/s1-9.4.282.
• Jitsuro Nagura (1952). "On the interval containing at least one prime number". Proc. Japan Acad. 28 (4): 177–181. doi:10.3792/pja/1195570997.
• Chris Caldwell, Bertrand's postulate at Prime Pages glossary.
• H. Ricardo (2005). "Goldbach's Conjecture Implies Bertrand's Postulate". Amer. Math. Monthly. 112: 492.
• Hugh L. Montgomery; Robert C. Vaughan (2007). Multiplicative number theory I. Classical theory. Cambridge tracts in advanced mathematics. 97. Cambridge: Cambridge Univ. Press. p. 49. ISBN 978-0-521-84903-6.
• J. Sondow (2009). "Ramanujan primes and Bertrand's postulate". Amer. Math. Monthly. 116 (7): 630–635. arXiv:0907.5232. doi:10.4169/193009709x458609.

External links

• Sondow, Jonathan & Weisstein, Eric W. "Bertrand's Postulate". MathWorld.
• A proof of the weak version in the Mizar system: http://mizar.org/version/current/html/nat_4.html#T56
• Bertrand's postulate − A proof of the weak version at www.dimostriamogoldbach.it/en/