Bertrand's postulate

From Wikipedia, the free encyclopedia

Bertrand's postulate (actually a theorem) states that for any integer n > 3, there always exists at least one prime number p with n < p < 2n − 2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2n.

This statement was first conjectured in 1845 by Joseph Bertrand (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 1850 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 $\scriptstyle \pi (x)\,$ , where $\scriptstyle \pi (x)\,$ is the prime counting function (number of primes less than or equal to $\scriptstyle x\,$ ):

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

In 1919, Ramanujan (1887–1920) used properties of the Gamma function to give a simpler proof,^[1] from which the concept of Ramanujan primes would later arise, and Erdős (1913–1996) in 1932 published a simpler proof using the Chebyshev function ϑ, defined as:

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

where p ≤ x runs over primes, and the binomial coefficients. See proof of Bertrand's postulate for the details.

Sylvester's theorem

Bertrand's postulate was proposed for applications to permutation groups. Sylvester (1814–1897) generalized it with the statement: the product of k consecutive integers greater than k is divisible by a prime greater than k.

Erdős's theorems

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).

The prime number theorem (PNT) implies that the number of primes up to x is roughly x/log(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 log(2x) and log(x) are asymptotically equivalent). Therefore the number of primes between n and 2n is roughly n/log(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²/log(x²) while the number of primes up to (x + 1)² is asymptotic to (x + 1)²/log((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.

Better results

It follows from the prime number theorem that for any real ε > 0, there exists an n₀ such that there is always a prime between n and (1 + ε)n for all n > n₀: it can be shown, for instance, that

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

which implies that π((1 + ε)n) − π(n) goes to infinity (and in particular is greater than 1 for sufficiently large n).^[2]

Non-asymptotic bounds have also been proved. In 1952, Jitsuro Nagura proved that for n ≥ 25, there is always a prime between n and (1 + 1/5)n.^[3]

In 1976, Lowell Schoenfeld showed that for n ≥ 2010760, there is always a prime between n and (1 + 1/16597)n.^[4] In 1998, Pierre Dusart improved the result in his doctoral thesis, showing that for k ≥ 463, p_k+1 ≤ (1 + 1/(ln²p_k))p_k, and in particular for x ≥ 3275, there exists a prime number between x and (1 + 1/(2ln²x))x.^[5] In 2010 he proved, that for x ≥ 396738 there is at least one prime between x and (1 + 1/(25ln²x))x.^[6]

Generalizations of Bertrand's Postulate have also been obtained by 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.^[7] In 2011, Andy Loo proved that there exists a prime between 3n and 4n. Furthermore, he 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 above).^[8] None of these proofs require the use of deep analytic results.

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 number 1 is the only integer which is a harmonic number.

Notes

↑ Ramanujan, S. (1919). "A proof of Bertrand's postulate". Journal of the Indian Mathematical Society 11: 181–182
↑ G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008, p. 494.
↑ Nagura, J. "On the interval containing at least one prime number." Proceedings of the Japan Academy, Series A 28 (1952), pp. 177–181.
↑ 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.
↑ Dusart, Pierre (1998), Autour de la fonction qui compte le nombre de nombres premiers (PDF) (in french)
↑ Dusart, Pierre (2010). "Estimates of Some Functions Over Primes without R.H.". arXiv:1002.0442.
↑ M. El Bachraoui, Primes in the Interval (2n, 3n)
↑ Loo, Andy (2011), "On the Primes in the Interval (3n, 4n)" (PDF), International Journal of Contemporary Mathematical Sciences 6 (38): 1871–1882

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.
Jonathan Sondow and Eric W. Weisstein, "Bertrand's Postulate", MathWorld.
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 0-521-84903-9. Cite uses deprecated parameters (help)

v t e Prime number classes

By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))

By integer sequence	Fibonacci Lucas Motzkin Bell Partitions Pell Perrin Newman–Shanks–Williams

By property	Lucky Wall–Sun–Sun Wilson Wieferich Wieferich pair Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Wolstenholme Good Super Higgs Highly cototient Illegal

Base-dependent	Happy Dihedral Palindromic Emirp Repunit (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Full reptend Unique Primeval Self Smarandache–Wellin

Patterns	Twin (p, p + 2) Bi-twin chain (p − 1, p + 1, 2p − 1, 2p + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)

By size	Titanic (1,000+ digits) Gigantic (10,000+) Mega (1,000,000+) Largest known

Complex numbers	Eisenstein prime Gaussian prime

Composite numbers	Pseudoprime Almost prime Semiprime Interprime

Related topics	Probable prime Industrial-grade prime Formula for primes Prime gap

List of prime numbers

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.