Editing Proof of Bertrand's postulate

{{short description|Solved prime-number problem}}
In [[mathematics]], [[Bertrand's postulate]] (now a [[theorem]]) states that, for each <math>n \ge 2</math>, there is a [[prime number|prime]] <math>p</math> such that <math>n<p<2n</math>. First [[conjecture]]d in 1845 by [[Joseph Louis François Bertrand|Joseph Bertrand]],<ref>{{Citation|first=Joseph |last=Bertrand |author-link=Joseph Bertrand |title=Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme. |journal=Journal de l'École Royale Polytechnique |issue=Cahier 30 |volume=18 |year=1845 |pages=123–140 |language=fr |url={{Google Books|WTa-qRIWckoC|page=123|plainurl=yes}}}}.</ref> it was first [[mathematical proof|proven]] by [[Chebyshev]], and a shorter but also advanced proof was given by [[Ramanujan]].<ref>{{Citation |first=S. |last=Ramanujan |title=A proof of Bertrand's postulate |journal=Journal of the Indian Mathematical Society |volume=11 |year=1919 |pages=181–182 |url=http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper24/page1.htm }}</ref>

The following [[elementary proof]] was published by [[Paul Erdős]] in 1932, as one of his earliest mathematical publications.<ref>{{Citation |first=Pál |last=Erdős |title=Beweis eines Satzes von Tschebyschef |journal=Acta Scientarium Mathematicarum (Szeged) |volume=5 | issue=3–4 |year=1932 |pages=194–198 | trans-title=Proof of a theorem of Chebyshev |url=https://users.renyi.hu/~p_erdos/1932-01.pdf | zbl=004.10103 }}</ref> The basic idea is to show that the [[central binomial coefficient]]s must have a [[prime factor]] within the [[interval (mathematics)|interval]] <math>(n, 2n)</math> in order to be large enough. This is achieved through analysis of their factorizations.

The main steps of the proof are as follows. First, one shows that the contribution of every [[prime power]] factor <math>p^r</math> in the prime decomposition of the central binomial coefficient <math>\textstyle\binom{2n}{n}=(2n)!/(n!)^2</math> is at most <math>2n</math>; then, one shows that every prime larger than <math>\sqrt{2n}</math> appears at most once.

The next step is to prove that <math>\tbinom{2n}{n}</math> has no prime factors in the interval <math>(\tfrac{2n}{3}, n)</math>. As a consequence of these bounds, the contribution to the size of <math>\tbinom{2n}{n}</math> coming from the prime factors that are at most <math>n</math> grows [[asymptotic analysis|asymptotically]] as <math>\theta^{\!\;n}</math> for some <math>\theta<4</math>. Since the asymptotic growth of the central binomial coefficient is at least <math>4^n\!/2n</math>, the conclusion is that, [[proof by contradiction|by contradiction]] and for large enough <math>n</math>, the binomial coefficient must have another prime factor, which can only lie between <math>n</math> and <math>2n</math>.

The argument given is valid for all <math>n\ge427</math>. The remaining values of&nbsp;<math>n</math> are verified by direct inspection, which completes the proof.

==Lemmas in the proof==

The proof uses the following four [[lemma (mathematics)|lemmas]] to establish facts about the primes present in the central binomial coefficients.

===Lemma 1===
For any [[integer]] <math>n>0</math>, we have
:<math>\frac{4^n}{2n} \le \binom{2n}{n}.</math>

'''Proof:''' Applying the [[binomial theorem]],
:<math>4^n = (1 + 1)^{2n} = \sum_{k = 0}^{2n} \binom{2n}{k}=2+\sum_{k = 1}^{2n-1} \binom{2n}{k} \le 2n\binom{2n}{n},</math>
since <math>\tbinom{2n}{n}</math> is the largest term in the sum in the right-hand side, and the sum has <math>2n</math> terms (including the initial <math>2</math> outside the summation).

===Lemma 2===
For a fixed prime <math>p</math>, define <math>R = R(n,p)</math> to be the [[p-adic order|''p''-adic order]] of <math>\tbinom{2n}{n}</math>, that is, the largest [[natural number]] <math>r</math> such that <math>p^r</math> divides <math>\tbinom{2n}{n}</math>.

For any prime <math>p</math>, <math>p^{R }\le 2n</math>.

'''Proof:''' The exponent of <math>p</math> in <math>n!</math> is given by [[Legendre's formula]]
:<math>\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor\!,</math>
so
:<math>R=\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)</math>
But each term of the last summation must be either zero (if <math>n/p^j \bmod 1<1/2</math>) or one (if <math>n/p^j\bmod 1\ge1/2</math>), and all terms with <math>j>\log_p(2n)</math> are zero. Therefore,
:<math>R \le \log_p(2n),</math>
and
:<math>p^R \le p^{\log_p(2n)} = 2n.</math>

===Lemma 3=== 
If <math>p</math> is an [[parity (mathematics)|odd]] prime and <math>\frac{2n}{3} < p \leq n</math>, then <math>R(n,p) = 0.</math>

'''Proof:''' There are exactly two factors of <math>p</math> in the numerator of the expression <math>\tbinom{2n}{n}=(2n)!/(n!)^2</math>, coming from the two terms <math>p</math> and <math>2p</math> in <math>(2n)!</math>, and also two factors of <math>p</math> in the denominator from one copy of the term <math>p</math> in each of the two factors of <math>n!</math>. These factors all cancel, leaving no factors of <math>p</math> in <math>\tbinom{2n}{n}</math>. (The bound on <math>p</math> in the preconditions of the lemma ensures that <math>3p</math> is too large to be a term of the numerator, and the assumption that <math>p</math> is odd is needed to ensure that <math>2p</math> contributes only one factor of <math>p</math> to the numerator.)

===Lemma 4===
An upper bound is supplied for the [[primorial]] function,
:<math>n\#=\prod_{p\,\le\,n}p,</math>
where the product is taken over all ''prime'' numbers <math>p</math> less than or equal to <math>n</math>.

For all <math>n\ge1</math>, <math>n\#<4^n</math>.

'''Proof:''' We use [[Mathematical induction#Complete (strong) induction|complete induction]].

For <math>n=1,2</math> we have <math>1\#=1<4</math> and <math>2\#=2<4^2=16</math>.

Let us assume that the inequality holds for all <math>1\le n\le2k-1</math>. Since <math>n=2k>2</math> is composite, we have
:<math>(2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}.</math>

Now let us assume that the inequality holds for all <math>1\le n\le2k</math>. Since <math>\binom{2k+1}{k}=\frac{(2k+1)!}{k!(k+1)!}</math> is an integer and all the primes <math>k+2\le p\le2k+1</math> appear only in the numerator, we have
:<math>\frac{(2k+1)\#}{(k+1)\#}\le\binom{2k+1}{k}=\frac12\!\left[\binom{2k+1}{k}+\binom{2k+1}{k+1}\right]<\frac12(1+1)^{2k+1}=4^k .</math>
Therefore,
:<math>(2k+1)\#=(k+1)\#\cdot\frac{(2k+1)\#}{(k+1)\#}\le4^{k+1}\binom{2k+1}{k}<4^{k+1}\cdot4^k=4^{2k+1}.</math>

==Proof of Bertrand's Postulate==
Assume that there is a [[counterexample]]: an integer ''n''&nbsp;≥&nbsp;2 such that there is no prime ''p'' with ''n''&nbsp;<&nbsp;''p''&nbsp;<&nbsp;2''n''.

If 2 ≤ ''n'' &lt; 630, then ''p'' can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (each being the largest prime less than twice its predecessor) such that ''n''&nbsp;<&nbsp;''p''&nbsp;<&nbsp;2''n''. Therefore, ''n''&nbsp;≥&nbsp;630.

There are no prime factors ''p'' of <math>\textstyle\binom{2n}{n}</math> such that:
* 2''n'' < ''p'', because every factor must divide (2''n'')!;
* ''p'' = 2''n'', because 2''n'' is not prime;
* ''n'' < ''p'' < 2''n'', because we assumed there is no such prime number;
* 2''n''/3 < ''p'' ≤ ''n'': by [[#Lemma 3|Lemma 3]].
Therefore, every prime factor ''p'' satisfies ''p'' ≤ 2''n''/3.

When <math>p > \sqrt{2n},</math> the number <math>\textstyle {2n \choose n} </math> has at most one factor of ''p''. By [[#Lemma 2|Lemma 2]], for any prime ''p'' we have ''p''<sup>''R''(''p'',''n'')</sup> ≤ 2''n'', and <math>\pi(x)\le x-1</math> since 1 is neither prime nor composite. Then, starting with [[#Lemma 1|Lemma 1]] and decomposing the {{nowrap|right-hand}} side into its prime factorization, and finally using [[#Lemma 4|Lemma 4]], these bounds give:
:<math>\frac{4^n}{2n}\le\binom{2n}{n}=\left(\,\prod_{p\,\le\,\sqrt{2n}}p^{R(p,n)}\right)\!\!\left(\prod_{\sqrt{2n}\,<\,p\,\le\,2n/3}\!\!\!\!\!\!\!p^{R(p,n)}\right)<\left(\,\prod_{p\,\le\,\sqrt{2n}}\!\!2n\right)\!\!\left(\prod_{p\,\le\,2n/3}\!\!p\right)\le(2n)^{\sqrt{2n}-1}4^{2n/3}.</math>
Therefore
:<math>4^{n/3}<(2n)^\sqrt{2n}</math>, which simplifies to <math>2^\sqrt{2n}<(2n)^3.</math>
Taking the base-2 [[logarithm]] of both sides yields
:<math>\sqrt{2n}<3\log_2(2n).</math>
By [[concave function|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 <math>n=426</math> and it does not for <math>n=427</math>, we obtain
:<math>n<427.</math>
But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.

===Addendum to proof===
It is possible to reduce the bound to <math>n=50</math>.

For <math>n\ge17,</math> we get <math>\pi(n)<\frac{n}{2}-1</math>, so we can say that the product <math>p^R</math> is at most <math>(2n)^{0.5\sqrt{2n}-1}</math>, which gives

:<math>\begin{align}&\frac{4^n}{2n}\le\binom{2n}{n}\le(2n)^{0.5\sqrt{2n}-1}4^{2n/3}\\&4^{\sqrt{2n}}\le(2n)^3\\&2\sqrt{2n}\le3\log_2(2n)\end{align}</math>

which is true for <math>n=49</math> and false for <math>n=50</math>.

==References==
{{Reflist}}

==External links==
* Chebyshev's Theorem and Bertrand's Postulate (Leo Goldmakher): https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf
* Proof of Bertrand's Postulate (UW Math Circle): https://sites.math.washington.edu/~mathcircle/circle/2013-14/advanced/mc-13a-w10.pdf
* Proof in the [[Mizar system]]: http://mizar.org/version/current/html/nat_4.html#T56
* {{Mathworld|urlname=BertrandsPostulate|title=Bertrand's Postulate}}

{{DEFAULTSORT:Bertrands postulate, proof of}}
[[Category:Prime numbers]]
[[Category:Factorial and binomial topics]]
[[Category:Article proofs]]
[[Category:Theorems about prime numbers]]