In number theory, Bertrand's postulate is the theorem that for any integer , there 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 [2] (1822–1900). Bertrand himself verified his statement for all integers .
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 , the prime-counting function (number of primes less than or equal to ):
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 n2 < p < (n + 1)2. Again we expect that there will be not just one but many primes between n2 and (n + 1)2, but in this case the PNT doesn't help: the number of primes up to x2 is asymptotic to x2/ln(x2) while the number of primes up to (x + 1)2 is asymptotic to (x + 1)2/ln((x + 1)2), 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 (indeed, cannot be) sufficient to prove the existence of even one prime in this interval.
In 1919, Ramanujan (1887–1920) used properties of the Gamma function to give a simpler proof than Chebyshev's. [4] 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
with pk the kth prime and Rn 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 1973, Denis Hanson proved that there exists a prime between 3n and 4n. [5] In 2006, apparently unaware of Hanson's result, M. El Bachraoui proposed a proof that there exists a prime between 2n and 3n. [6]
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), different definitions lead to different results, some are still conjectures, some proven. [7]
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.
In 1932, Erdős (1913–1996) also published a simpler proof using binomial coefficients and the Chebyshev function , defined as:
where p ≤ x runs over primes. See proof of Bertrand's postulate for the details. [8]
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).
It follows from the prime number theorem that for any real there is a such that for all there is a prime such that . It can be shown, for instance, that
which implies that goes to infinity (and, in particular, is greater than 1 for sufficiently large ). [9]
Non-asymptotic bounds have also been proved. In 1952, Jitsuro Nagura proved that for there is always a prime between and . [10]
In 1976, Lowell Schoenfeld showed that for , there is always a prime in the open interval . [11]
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 . [12]
In 2010 Pierre Dusart proved that for there is at least one prime in the interval . [13]
In 2016, Pierre Dusart improved his result from 2010, showing (Proposition 5.4) that if , there is at least one prime in the interval . [14] He also shows (Corollary 5.5) 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 . [15]
Dudek proved that for all , there is at least one prime between and . [16]
Dudek also proved that the Riemann hypothesis implies that for all there is a prime satisfying
In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann.
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter ζ (zeta), is a mathematical function of a complex variable defined as
In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are π and e.
Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.
In mathematics, Stirling's approximation is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of . It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre.
The sum of the reciprocals of all prime numbers diverges; that is:
Chebyshev's theorem is any of several theorems proven by Russian mathematician Pafnuty Chebyshev.
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic progressions. It is well known for its results on prime numbers and additive number theory.
In mathematics, Bertrand's postulate states that for each there is a prime such that . First conjectured in 1845 by Joseph Bertrand, it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.
In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by π(x) (unrelated to the number π).
In mathematics, the inverse trigonometric functions are the inverse functions of the trigonometric functions. Specifically, they are the inverses of the sine, cosine, tangent, cotangent, secant, and cosecant functions, and are used to obtain an angle from any of the angle's trigonometric ratios. Inverse trigonometric functions are widely used in engineering, navigation, physics, and geometry.
In mathematics, the polygamma function of order m is a meromorphic function on the complex numbers defined as the (m + 1)th derivative of the logarithm of the gamma function:
In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function only multiplies prime numbers.
In analytic number theory, Mertens' theorems are three 1874 results related to the density of prime numbers proved by Franz Mertens.
Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proven by Euclid in his work Elements. There are several proofs of the theorem.
In mathematics, the Chebyshev function is either a scalarising function (Tchebycheff function) or one of two related functions. The first Chebyshev functionϑ (x) or θ (x) is given by
In mathematics, a Ramanujan prime is a prime number that satisfies a result proven by Srinivasa Ramanujan relating to the prime-counting function.
In the 1760s, Johann Heinrich Lambert was the first to prove that the number π is irrational, meaning it cannot be expressed as a fraction , where and are both integers. In the 19th century, Charles Hermite found a proof that requires no prerequisite knowledge beyond basic calculus. Three simplifications of Hermite's proof are due to Mary Cartwright, Ivan Niven, and Nicolas Bourbaki. Another proof, which is a simplification of Lambert's proof, is due to Miklós Laczkovich. Many of these are proofs by contradiction.
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 1/2. Many consider it to be the most important unsolved problem in pure mathematics. It is of great interest in number theory because it implies results about the distribution of prime numbers. It was proposed by Bernhard Riemann (1859), after whom it is named.
Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.