Bertrand's postulate is a theorem stating that for any integer, there always exists at least one prime number with A less restrictive formulation is: for every there is always at least one prime such that Another formulation, where is the -th prime, is for This statement was first conjectured in 1845 by Joseph Bertrand. Bertrand himself verified his statement for all numbers in the interval His conjecture was completely proved by Chebyshev in 1852 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, where is the prime counting function :
The prime number theorem implies that the number of primes up to x is roughly x/ln, 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 and ln. Therefore the number of primes between n and 2n is roughly n/ln 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. The similar and still unsolvedLegendre's conjecture asks whether for every n > 1, there is a prime p, such that n2 < p < 2. Again we expect that there will be not just one but many primes between n2 and 2, but in this case the PNT doesn't help: the number of primes up to x2 is asymptotic to x2/ln while the number of primes up to 2 is asymptotic to 2/ln, which is asymptotic to the estimate on primes up to x2. 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 sufficient to prove the existence of even one prime in this interval.
Generalizations
In 1919, Ramanujan used properties of the Gamma function to give a simpler proof. 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 with pk the kth prime and Rn the nth Ramanujan prime. Other generalizations of Bertrand's Postulate have been obtained using elementary methods. 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. 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. 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 generalized the weaker statement with the statement: the product of k consecutive integers greater thank is divisible by a prime greater than k. Bertrand's postulate follows from this by takingk = 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, 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.
It follows from the prime number theorem that for any real there is a such that for all there is a prime such. It can be shown, for instance, that which implies that goes to infinity. Non-asymptotic bounds have also been proved. In 1952, Jitsuro Nagura proved that for there is always a prime between and. In 1976, Lowell Schoenfeld showed that for, there is always a prime in the open interval. In his 1998 doctoral thesis, Pierre Dusart improved the above result, showing that for, and in particular for, there exists a prime in the interval. In 2010 Pierre Dusart proved that for there is at least one prime in the interval. In 2016, Pierre Dusart improved his result from 2010, showing that, if, there is at least one prime in the interval. He also shows that, for, there is at least one prime in the interval. Baker, Harman and Pintz proved that there is a prime in the interval for all sufficiently large.
Consequences
The sequence of primes, along with 1, is a complete sequence; any positive integer can be written as a sum of primes using each at most once.
The only harmonic number that is an integer is the number 1.
