In mathematics, Bertrand's postulate (actually a theorem) states that for each
there is a prime
such that
. It was first proven by Pafnuty Chebyshev, and a short but advanced proof was given by Srinivasa Ramanujan.[1] The gist of the following elementary proof is due to Paul Erdős. The basic idea of the proof is to show that a certain central binomial coefficient needs to have a prime factor within the desired interval in order to be large enough. This is made possible by a careful analysis of the prime factorization of central binomial coefficients.
The main steps of the proof are as follows. First, one shows that every prime power factor
that enters into the prime decomposition of
the central binomial coefficient
is at most
. In particular, every prime larger than
can enter at most once into this decomposition; that is, its exponent
is at most one. The next step is to prove that
has no prime factors at all in the gap interval
. As a consequence of these two bounds, the contribution to the size of
coming from all the prime factors that are at most
grows asymptotically as
for some
. Since the
asymptotic growth of the central binomial coefficient is at least
, one concludes that for
large enough the binomial coefficient must have another prime factor, which can only lie between
and
.
Indeed, making these estimates quantitative, one obtains that this argument is valid for all
. The remaining smaller values of
are easily settled by direct inspection, completing the proof of Bertrand's postulate.
Lemmas and computation
Lemma 1: A lower bound on the central binomial coefficients
Lemma: For any integer
, we have
![{\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba1c21aea68e24e712d0420fc2587717f0b8ae09)
Proof: Applying the binomial theorem,
![{\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/130289f82786900c73c609b2e08b083da8fa333e)
since
is the largest term in the sum in the right-hand side, and the sum has
terms (including the initial
outside the summation).
Lemma 2: An upper bound on prime powers dividing central binomial coefficients
For a fixed prime
, define
to be the largest natural number
such that
divides
.
Lemma: For any prime
,
.
Proof: The exponent of
in
is (see Factorial#Number theory):
![{\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor ,\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/69c0f3fbdebeb8b691a6463592bc7a756dbe845e)
so
![{\displaystyle R(p,n)=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02f9c81e4524c16c8c2f9c39453350597d7b99ec)
But each term of the last summation can either be zero (if
) or 1 (if
) and all terms with
are zero. Therefore
![{\displaystyle R(p,n)\leq \log _{p}(2n),\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/39883489f1529f89cbb37c0b2d6400123fb35b7f)
and
![{\displaystyle p^{R(p,n)}\leq p^{\log _{p}{2n}}=2n.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a48096689ecb4f6e14e03c6c27453f13b966b5d5)
This completes the proof of the lemma.
Lemma 3: The exact power of a large prime in a central binomial coefficient
Lemma: If
is odd and
, then
Proof: There are exactly two factors of
in the numerator of the expression
, coming from the two terms
and
in
, and also two factors of
in the denominator from two copies of the term
in
. These factors all cancel, leaving no factors of
in
. (The bound on
in the preconditions of the lemma ensures that
is too large to be a term of the numerator, and the assumption that
is odd is needed to ensure that
contributes only one factor of
to the numerator.)
Lemma 4: An upper bound on the primorial
We estimate the primorial function,
![{\displaystyle x\#=\prod _{p\leq x}p,\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdc8ebeccb495de75abff31148cc8fd516277dbf)
where the product is taken over all prime numbers
less than or equal to the real number
.
Lemma: For all real numbers
,
.[2]
Proof:
Since
and
, it suffices to prove the result under the assumption that
is an integer,
. Since
is an integer and all the primes
appear in its numerator but not in its denumerator, we have
.
The proof proceeds by mathematical induction.
- If
, then ![{\displaystyle n\#=6<8=2^{2n-3}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9d8c15235eb4373d346ef7563d0dba9cc9006d1)
- If
, then ![{\displaystyle n\#=6<16=2^{2n-3}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d708cb8e3b20175d94f6017889981363832c181c)
- If
is odd and
, then by the above estimate and the induction assumtion for
it's
![{\displaystyle n\#=(2m-1)\#<m\#\cdot 2^{2m-2}<2^{2m-3}2^{2m-2}=2^{4m-5}=2^{2n-3}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39d0ce3a5b87a1bb65cbf840e60510482238fbbf)
- If
is even and
, then by the above estimate and the induction assumtion for
it's
![{\displaystyle n\#=(2m)\#=(2m-1)\#<m\#\cdot 2^{2m-2}<2^{2m-3}2^{2m-2}=2^{4m-5}<2^{4m-3}=2^{2n-3}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93c1ac038c7268aee324427294ae05a94ed83238)
Thus the lemma is proven.
Proof of Bertrand's Postulate
Assume there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n.
If 2 ≤ n < 468, then p can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (each being less than twice its predecessor) such that n < p < 2n. Therefore n ≥ 468.
There are no prime factors p of
such that:
- 2n < p, because every factor must divide (2n)!;
- p = 2n, because 2n is not prime;
- n < p < 2n, because we assumed there is no such prime number;
- 2n / 3 < p ≤ n: by Lemma 3.
Therefore, every prime factor p satisfies p ≤ 2n/3.
When
the number
has at most one factor of p. By Lemma 2, for any prime p we have pR(p,n) ≤ 2n, so the product of the pR(p,n) over the primes less than or equal to
is at most
. Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:
![{\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\right)\left(\prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p^{R(p,n)}\right)<(2n)^{\sqrt {2n}}\prod _{1<p\leq {\frac {2n}{3}}}p=(2n)^{\sqrt {2n}}{\Big (}{\frac {2n}{3}}{\Big )}\#\leq (2n)^{\sqrt {2n}}4^{2n/3}.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/197d27114b3cb1c61944741ba03fee1a5a22d258)
Taking logarithms yields to
![{\displaystyle {\frac {\log 4}{3}}n\leq ({\sqrt {2n}}+1)\log 2n\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6041bebf2182164c630f6f702425a0847c97bc51)
By concavity of the right-hand side as a function of n, the last inequality is necessarily verified on an interval. Since it holds true for n=467 and it does not for n=468, we obtain
![{\displaystyle n<468.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b14e94565939b9ecbe4a9b5e4444990b136160b)
But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.
Proof by Shigenori Tochiori
Using Lemma 4, Tochiori refined Erdos's method and proved if there exists a positive integer
such that there is no prime number
then
. [3]
First, refine lemma 1 to:
Lemma 1': For any integer
, we have
![{\displaystyle {\frac {4^{n}}{n}}<{\binom {2n}{n}}.\ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff80ebd8ca3b5a59a9c71eeeaca612649bac9959)
Proof: By induction:
and assuming the truth of the lemma for
,
![{\displaystyle {\binom {2n}{n}}=2\,{\frac {2n-1}{n}}{\binom {2(n-1)}{n-1}}>2\,{\frac {2n-1}{n}}{\frac {4^{n-1}}{n-1}}>2\cdot 2\,{\frac {4^{n-1}}{n}}={\frac {4^{n}}{n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b56febf0bf272c724de529af7521b90a6474312e)
Then, refine the estimate of the product of all small primes via a better estimate on
(the number of primes at most
):
Lemma 5: For any natural number
, we have
![{\displaystyle \pi (n)\leq {\frac {1}{3}}n+2.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcfe155f1836aa5a542eebf4596dcb9b3c4bc149)
Proof: Except for
, every prime number has
or
. Thus
is upper bounded by the number of natural numbers
with
or
, plus one (since this counts
and misses
). Thus
![{\displaystyle \pi (n)\leq \left\lfloor {\frac {n+5}{6}}\right\rfloor +\left\lfloor {\frac {n+1}{6}}\right\rfloor +1\leq {\frac {n+5}{6}}+{\frac {n+1}{6}}+1={\frac {1}{3}}n+2.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/665ac280d53babfa84a644fafd65ea41cd05d9d3)
Now, calculating the binomial coefficient as in the previous section, we can use the improved bounds to get (for
, which implies
so that
):
![{\displaystyle {\begin{aligned}{\frac {4^{n}}{n}}&\leq {\binom {2n}{n}}\\&=\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\cdot \prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p^{R(p,n)}\\&<(2n)^{\pi ({\sqrt {2n}})}\prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p=(2n)^{{\frac {1}{3}}{\sqrt {2n}}+2}{\frac {(2n/3)\#}{{\sqrt {2n}}\#}}\\&<(2n)^{{\frac {1}{3}}{\sqrt {2n}}+2}{\frac {2^{2\cdot 2n/3-3}}{6}}<(2n)^{{\frac {1}{3}}{\sqrt {2n}}+2}2^{4n/3-5}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a53ee14106d726816fe908b07b64531d6e15fcff)
Taking logarithms to get
![{\displaystyle {\frac {2}{3}}n\log 2<{\frac {1}{3}}{\sqrt {2n}}\log 2n+3\log {\frac {n}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/844b0757de6628f1aa2dfcacc6912bda9206bbf9)
and dividing both sides by
:
![{\displaystyle \log 2<{\sqrt {2}}\cdot {\frac {\log {\sqrt {n}}}{\sqrt {n}}}+{\frac {9}{4}}{\frac {\log {\frac {n}{2}}}{\frac {n}{2}}}+{\frac {\log 2}{\sqrt {2n}}}\equiv f(n)\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b6ebe84ce2e45a83bb2f59250be58637ae2278d)
Now the function
is decreasing for
, so
is decreasing when
. But
![{\displaystyle {\frac {f(2^{6})}{\log 2}}={\sqrt {2}}\cdot {\frac {3}{8}}+{\frac {9}{4}}\cdot {\frac {5}{32}}+{\frac {\sqrt {2}}{16}}=0.97\dots <1<{\frac {f(n)}{\log 2}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9fb53933d9ee3942c2932a80dfa7c1d4ea9cf5e)
so
. The remaining cases are proven by an explicit list of primes, as above.
References
External links