In number theory, Bertrand's postulate is the theorem that for any integer n > 3 {\displaystyle n>3} , there exists at least one prime number p {\displaystyle p} with
n < p < 2 n − 2. {\displaystyle n<p<2n-2.}
A less restrictive formulation is: for every n > 1 {\displaystyle n>1} , there is always at least one prime p {\displaystyle p} such that
n < p < 2 n . {\displaystyle n<p<2n.}
Another formulation, where p n {\displaystyle p_{n}} is the n {\displaystyle n} -th prime, is: for n ≥ 1 {\displaystyle n\geq 1}
p n + 1 < 2 p n . {\displaystyle p_{n+1}<2p_{n}.}
This hypothesis was first conjectured in 1845 by Joseph Bertrand, who verified it for all integers up to 3,000,000. Chebyshev proved it in 1852 and so it is also called the Bertrand–Chebyshev theorem or Chebyshev's theorem. Chebyshev's theorem can also be stated as a relationship with π ( x ) {\displaystyle \pi (x)} , the prime-counting function (number of primes less than or equal to x {\displaystyle x} ):
π ( x ) − π ( x 2 ) ≥ 1 , for all x ≥ 2. {\displaystyle \pi (x)-\pi {\bigl (}{\tfrac {x}{2}}{\bigr )}\geq 1,{\text{ for all }}x\geq 2.}
Prime number theorem The prime number theorem (PNT) implies that the number of primes up to x {\displaystyle x} , denoted π ( x ) {\displaystyle \pi (x)} , is roughly x / log ( x ) {\displaystyle x/{\text{log}}(x)} , so if we replace x {\displaystyle x} with 2 x {\displaystyle 2x} then we see the number of primes up to 2 x {\displaystyle 2x} is asymptotically twice the number of primes up to x {\displaystyle x} (the terms log ( 2 x ) {\displaystyle {\text{log}}(2x)} and log ( x ) {\displaystyle {\text{log}}(x)} are asymptotically equivalent). Therefore, the number of primes between n {\displaystyle n} and 2 n {\displaystyle 2n} is roughly n / log ( n ) {\displaystyle n/{\text{log}}(n)} when n {\displaystyle 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 weaker than the PNT; but it makes precise claims about what happens for small values of n {\displaystyle n} . The similar and still unsolved Legendre's conjecture asks whether for every n ≥ 1 {\displaystyle n\geq 1} , there is a prime p {\displaystyle p} such that n 2 < p < ( n + 1 ) 2 {\displaystyle n^{2}<p<(n+1)^{2}} . Again we expect that there will be not just one but many primes between n 2 {\displaystyle n^{2}} and ( n + 1 ) 2 {\displaystyle (n+1)^{2}} , but in this case the PNT does not help: the number of primes up to x 2 {\displaystyle x^{2}} is asymptotic to x 2 / log ( x 2 ) {\displaystyle x^{2}/{\text{log}}(x^{2})} while the number of primes up to ( x + 1 ) 2 {\displaystyle (x+1)^{2}} is asymptotic to ( x + 1 ) 2 / log ( ( x + 1 ) 2 ) {\displaystyle (x+1)^{2}/{\text{log}}((x+1)^{2})} , which is asymptotic to the estimate on primes up to x 2 {\displaystyle x^{2}} . So, unlike the previous case of x {\displaystyle x} and 2 x {\displaystyle 2x} , we do not get a proof of Legendre's conjecture for large n {\displaystyle 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 {\displaystyle \varepsilon >0} , there exists an S {\displaystyle S} such that for x > S {\displaystyle x>S} :
( 1 − ε ) x 2 2 log x < π ( x 2 ) < ( 1 + ε ) x 2 2 log x , {\displaystyle (1-\varepsilon ){\frac {x^{2}}{2\log x}}\;<\;\pi (x^{2})\;<\;(1+\varepsilon ){\frac {x^{2}}{2\log x}}\;,}
( 1 − ε ) ( x + 1 ) 2 2 log ( x + 1 ) < π ( ( x + 1 ) 2 ) < ( 1 + ε ) ( x + 1 ) 2 2 log ( x + 1 ) . {\displaystyle (1-\varepsilon ){\frac {(x+1)^{2}}{2\log(x+1)}}\;<\;\pi ((x+1)^{2})\;<\;(1+\varepsilon ){\frac {(x+1)^{2}}{2\log(x+1)}}\;.}
The ratio between the lower bound π ( ( x + 1 ) 2 ) {\textstyle \pi ((x+1)^{2})} and the upper bound of π ( x 2 ) {\textstyle \pi (x^{2})} is
( x + 1 ) 2 x 2 ⋅ log x log ( x + 1 ) ⋅ 1 − ε 1 + ε . {\displaystyle {\frac {(x+1)^{2}}{x^{2}}}\cdot {\frac {\log x}{\log(x+1)}}\cdot {\frac {1-\varepsilon }{1+\varepsilon }}\;.}
Note that since ( x + 1 ) 2 x 2 → 1 {\displaystyle {\frac {(x+1)^{2}}{x^{2}}}\rightarrow 1} when x → ∞ {\displaystyle x\rightarrow \infty } , log x log ( x + 1 ) < 1 {\displaystyle {\frac {\log x}{\log(x+1)}}<1} for all x > 0, and 1 − ε 1 + ε < 1 {\displaystyle {\frac {1-\varepsilon }{1+\varepsilon }}<1} for a fixed ε {\displaystyle \varepsilon } , there exists an R {\displaystyle R} such that the ratio above is less than 1 for all x > R {\displaystyle x>R} . Thus, it does not ensure that there exists a prime between π ( x 2 ) {\textstyle \pi (x^{2})} and π ( ( x + 1 ) 2 ) {\textstyle \pi ((x+1)^{2})} . More generally, these simple bounds are not enough to prove that there exists a prime between π ( x n ) {\textstyle \pi (x^{n})} and π ( ( x + 1 ) n ) {\textstyle \pi ((x+1)^{n})} for any positive integer n > 1 {\displaystyle n>1} .
Generalizations In 1919, Ramanujan (1887–1920) used properties of the Gamma function to give a simpler proof than Chebyshev. His 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 been discovered; for instance, there is a proof that
2 p i − n > p i for i > k where k = π ( p k ) = π ( R n ) , {\displaystyle 2p_{i-n}>p_{i}{\text{ for }}i>k{\text{ where }}k=\pi (p_{k})=\pi (R_{n})\,,}
with p k {\displaystyle p_{k}} the k {\displaystyle k} -th prime and R n {\displaystyle R_{n}} the n {\displaystyle n} -th Ramanujan prime. Other generalizations of Bertrand's postulate have been obtained using elementary methods. (In the following, n {\displaystyle n} runs through the set of positive integers.) In 1973, Denis Hanson proved that there exists a prime between 3 n {\displaystyle 3n} and 4 n {\displaystyle 4n} . In 2006, apparently unaware of Hanson's result, M. El Bachraoui proposed a proof that there exists a prime between 2 n {\displaystyle 2n} and 3 n {\displaystyle 3n} . El Bachraoui's proof is an extension of Erdős's arguments for the primes between n {\displaystyle n} and 2 n {\displaystyle 2n} . Shevelev, Greathouse, and Moses (2013) discuss related results for similar intervals. Bertrand's postulate over the Gaussian integers is an extension of the idea of the distribution of primes, but in this case on the complex plane. Thus, as Gaussian primes extend over the plane and not only along a line, and doubling a complex number is not simply multiplying by 2 but doubling its norm (multiplying by 1 + i {\displaystyle 1+i} ), different definitions lead to different results, some are still conjectures, some proven.
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 {\displaystyle k} consecutive integers greater than k {\displaystyle k} is divisible by a prime greater than k {\displaystyle k} . The result was discovered independently in 1929 by Issai Schur, and is now often known as the Sylvester–Schur theorem. Bertrand's postulate follows from this result, by taking k = n {\displaystyle k=n} , and considering the k {\displaystyle k} numbers n + 1 , n + 2 , … , n + k = 2 n {\displaystyle n+1,n+2,\dots ,n+k=2n} , where n > 1 {\displaystyle n>1} . According to Sylvester's generalization, one of these numbers has a prime factor greater than k {\displaystyle k} . Since all these numbers are less than 2 ( k + 1 ) {\displaystyle 2(k+1)} , the number with a prime factor greater than k {\displaystyle k} has only one prime factor, and thus is a prime. Since 2 n {\displaystyle 2n} is not prime, we know there exists a prime p {\displaystyle p} with n < p < 2 n {\displaystyle n<p<2n} .
Erdős's theorems In 1932, Erdős (1913–1996) published a simpler proof using binomial coefficients and the Chebyshev function ϑ {\displaystyle \vartheta } , defined as:
ϑ ( x ) = ∑ p = 2 x log ( p ) , {\displaystyle \vartheta (x)=\sum _{p=2}^{x}\log(p),}
where p ≤ x runs over primes. See proof of Bertrand's postulate for the details. Erdős proved in 1934 that for any positive integer k {\displaystyle k} , there is a natural number N {\displaystyle N} such that for all n > N {\displaystyle n>N} , there are at least k {\displaystyle k} primes between n {\displaystyle n} and 2 n {\displaystyle 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 ε > 0 {\displaystyle \varepsilon >0} there is a n 0 > 0 {\displaystyle n_{0}>0} such that for all n > n 0 {\displaystyle n>n_{0}} there is a prime p {\displaystyle p} such that n < p < ( 1 + ε ) n {\displaystyle n<p<(1+\varepsilon )n} . It can be shown, for instance, that
lim n → ∞ π ( ( 1 + ε ) n ) − π ( n ) n / log n = ε , {\displaystyle \lim _{n\to \infty }{\frac {\pi ((1+\varepsilon )n)-\pi (n)}{n/\log n}}=\varepsilon ,}
which implies that π ( ( 1 + ε ) n ) − π ( n ) {\displaystyle \pi ((1+\varepsilon )n)-\pi (n)} goes to infinity (and, in particular, is greater than 1 for sufficiently large n {\displaystyle n} ). Non-asymptotic bounds have also been proved. In 1952, Jitsuro Nagura proved that for n ≥ 25 {\displaystyle n\geq 25} there is always a prime between n {\displaystyle n} and ( 1 + 1 5 ) n {\displaystyle {\bigl (}1+{\tfrac {1}{5}}{\bigr )}n} . In 1976, Lowell Schoenfeld showed that for n ≥ 2 010 760 {\displaystyle n\geq 2\,010\,760} , there is always a prime p {\displaystyle p} in the open interval n < p < ( 1 + 1 16 597 ) n {\displaystyle n<p<{\bigl (}1+{\tfrac {1}{16\,597}}{\bigr )}n} . In his 1998 doctoral thesis, Pierre Dusart improved the above result, showing that for k ≥ 463 {\displaystyle k\geq 463} ,
p k + 1 ≤ ( 1 + 1 2 log 2 p k ) p k {\displaystyle p_{k+1}\leq \left(1+{\frac {1}{2\log ^{2}{p_{k}}}}\right)p_{k}} , and in particular for x ≥ 3 275 {\displaystyle x\geq 3\,275} , there exists a prime p {\displaystyle p} in the interval x < p ≤ ( 1 + 1 2 log 2 x ) x {\displaystyle x<p\leq \left(1+{\frac {1}{2\log ^{2}{x}}}\right)x} . In 2010 Pierre Dusart proved that for x ≥ 396 738 {\displaystyle x\geq 396\,738} there is at least one prime p {\displaystyle p} in the interval x < p ≤ ( 1 + 1 25 log 2 x ) x {\displaystyle x<p\leq \left(1+{\frac {1}{25\log ^{2}{x}}}\right)x} . In 2016, Pierre Dusart improved his result from 2010, showing (Proposition 5.4) that if x ≥ 89 693 {\displaystyle x\geq 89\,693} , there is at least one prime p {\displaystyle p} in the interval x < p ≤ ( 1 + 1 log 3 x ) x {\displaystyle x<p\leq \left(1+{\frac {1}{\log ^{3}{x}}}\right)x} . He also shows (Corollary 5.5) that for x ≥ 468 991 632 {\displaystyle x\geq 468\,991\,632} , there is at least one prime p {\displaystyle p} in the interval x < p ≤ ( 1 + 1 5 000 log 2 x ) x {\displaystyle x<p\leq \left(1+{\frac {1}{5\,000\log ^{2}{x}}}\right)x} . Baker, Harman and Pintz proved that there is a prime in the interval [ x − x 0.525 , x ] {\displaystyle [x-x^{0.525},\,x]} for all sufficiently large x {\displaystyle x} . Dudek proved that for all n ≥ e e 33.3 {\displaystyle n\geq e^{e^{33.3}}} , there is at least one prime between n 3 {\displaystyle n^{3}} and ( n + 1 ) 3 {\displaystyle (n+1)^{3}} . Dudek also proved that the Riemann hypothesis implies that for all x ≥ 2 {\displaystyle x\geq 2} there is a prime p {\displaystyle p} satisfying
x − 4 π x log x < p ≤ x . {\displaystyle x-{\frac {4}{\pi }}{\sqrt {x}}\log x<p\leq x.}
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.
See also Oppermann's conjecture Prime gap Proof of Bertrand's postulate Ramanujan prime
Notes
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. Vol. 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/