Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Proof of Bertrand's postulate

In mathematics, Bertrand's postulate states that for each n ≥ 2 there is a prime p such that n < p < 2n. It was first proven by Pafnuty Chebyshev; the gist of the following elementary but involved proof by contradiction is due to Paul Erdős.

We denote the set of prime numbers with $\Bbb{P}$ and define:

$\theta(x) = \sum_{p\in\Bbb{P};\, p\leq x} \ln (p)$

Lemma

$\theta(n) < n \cdot \ln(4)$ for all integers $n\ge 1$

Proof

n = 1:

$\theta(1)= 0 < 1 \cdot \ln(4)$

n = 2:

$\theta(2)=\ln(2) < 2 \cdot \ln(4)$

n > 2 and n is even:

$\theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4)$ (by induction)

(because every even no. is not prime, so the sum is aligned with the previous prime)

$n > 2$ and n is odd. Let n = 2m+1 with m > 0:

$4^m = \frac {(1+1)^{2m+1}}{2} = \frac {\sum_{k=0}^{2m+1}{2m+1 \choose k}} {2} = \frac {x+{2m+1 \choose m}+{2m+1 \choose m+1}}{2} \ge {2m+1 \choose m}$

Each prime p with $m+1 < p \le 2m+1$ divides ${2m+1 \choose m}$ giving us:

$\theta(2m+1) - \theta(m+1) \le \ln(4^m) = m \cdot \ln(4)$

By induction $\theta(m+1) < (m+1) \cdot \ln 4$ , so:

$\theta(n) = \theta(2m+1) < (2m+1) \cdot \ln(4) = n \cdot \ln(4)$

Q.E.D.

Now for the 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 < 2048, then one of the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503 (each being less than twice its predecessor), call it p, will satisfy n < p < 2n. Therefore n ≥ 2048.

$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k}$

Since ${2n \choose n}$ is the largest term in the sum we have:

$\frac {4^n} {2n+1} \le {2n \choose n}$

Define $R (p, n)$ to be highest number x, such that $p x$ divides ${2n \choose n}$ . Since n! has $\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor$ factors of p we get:

$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 \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$

But each term $\left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor$ can either be 0 $(\frac {n} {p^j} \mod 1 < 1/2)$ or 1 $(\frac {n} {p^j} \mod 1 \ge 1/2)$ and all terms with $j> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$ are 0. Therefore $R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor$ , and we get:

$p^{R(p,n)} = \exp \left ( R(p,n) \ln p \right ) \le \exp \left ( \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor \ln p \right ) \le 2n$

For $p > \sqrt{2n}$ we have $\left \lfloor \frac {\ln (2n)} {\ln(p)} \right \rfloor \le 1$ or $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor$ .

${2n \choose n}$ has no prime factors p such that:

2n < p, because 2n is the largest factor.
$n<p \le 2n$ , because we assumed there is no such prime number.
$\frac {2n} {3} <p \le n$ , because $p > \sqrt{2n}$ (since $n \ge 5$ ) which gives us $R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0$ .

Each prime factor of ${2n \choose n}$ is therefore not larger than $\frac {2n} {3}$ .

${2n \choose n}$ has at most one factor of every prime $p > \sqrt{2n}$ . As $p^{R(p,n)} \le 2n$ , the product of $p R (p, n)$ over all other primes is at most $(2n)^\sqrt{2n}$ . Since ${2n \choose n}$ is the product of $p R (p, n)$ over all primes p, we get:

$\frac {4^n}{2n+1} \le {2n \choose n} \le (2n)^\sqrt{2n} \prod_{p \in \mathbb{P} }^{\frac {2n} {3}} p = (2n)^\sqrt{2n} e^{\theta(\frac {2n} {3})}$

Using our lemma $\theta(n) < n \cdot \ln(4)$ :

$\frac {4^n} {2n+1} \le (2n)^\sqrt{2n} 4^{\frac {2n} {3}}$

Since we have $(2 n + 1) < (2 n) 2$ :

$4^{\frac {n}{3}} \le (2n)^{2+\sqrt{2n}}$

Also $2 \le \frac {\sqrt{2n}}{3}$ (since $n \ge 18$ ):

$4^{\frac {n}{3}} \le (2n)^{\frac {4} {3}\sqrt{2n}}$

Taking logarithms:

$\sqrt{2n} \ln(2) \le 4 \cdot \ln(2n)$

Substituting 2^2t for 2n:

$\frac {2^t} {t} \le 8$

This gives us t < 6 and the contradiction:

$n=\frac {2^{2t}} {2}<\frac {2^{2 \cdot 6}} {2}=2048$

Thus no counterexample to the postulate is possible.

Q.E.D.

Science Fair Project Encyclopedia Contents Page

03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

Science Fair Project Encyclopedia

Proof of Bertrand's postulate