A short proof of Chebyshev’s inequality

A proof from my book. This theorem was needed to estimate (from below) the growth function of Okninski’s semigroup. For every natural number n let \pi(n)  denote the number of primes \le n. Say, \pi(1)=0, \pi(2)=1, \pi(10)=4, etc. The next theorem was proved by Chebyshev in 1850. We present a proof based on some ideas of Erdos (he used these ideas to prove another Chebyshev theorem that for every natural n there is a prime between n and 2n).

THEOREM  There exists a constant c>0 such that for every natural number n we have \frac{cn}{\ln n}\le \pi(n)\le n-1.

PROOF. The inequality \pi(n)\le n-1 is obvious, so we should only prove the inequality \frac{cn}{\ln n}\le \pi(n). For every natural number m consider the middle binomial coefficient \binom{2m}{m} in the Newton expansion of (1+1)^{2m}=4^m.

EXERCISE 1.  Prove that \binom{2m}{m}\ge \frac{4^m}{2m+1}. HINT: Use the Pascal triangle formula to prove that the middle binomial coefficient is the biggest one. Then use the fact that the sum of the binomial coefficients is 4^m, and the number of them is 2m+1.

For a prime p and a number m we define o_p(m) as the largest exponent of p that divides m. Note that o_p(m_1m_2)=o_p(m_1)+o_p(m_2) and if m_2 divides                m_1, then o_p(\frac{m_1}{m_2})=o_p(m_1)-o_p(m_2).

EXERCISE 2. For every natural number m and prime p we have o_p(m!)=\sum_{i=1}^{r} \left\lfloor \frac{m}{p^i}\right\rfloor where r is such that p^r\le m\le p^{r+1}. HINT: There are \left\lfloor \frac mp\right\rfloor numbers \le m that are divisible by p, \left\lfloor \frac{m}{p^2}\right\rfloor numbers \le m that are divisible by p^2, etc.

LEMMA. If k=o_p(\binom{2m}{m})>0, i.e., p divides \binom{2m}{m}, then p^k\le 2m.

PROOF. Let r be the natural number such that p^r\le 2m <p^{r+1}. Then by Exercise 2.

k=o_p\left(\binom{2m}{m}\right)=o_p((2m)!)-2o_p(m!)=\sum_{i=1}^r \left\lfloor \frac{2m}{p^i}\right\rfloor -2\sum_{i=1}^r \left\lfloor \frac m{p^i}\right\rfloor = \sum_{i=1}^r (\left\lfloor \frac{2m}{p^i}\right\rfloor -2\left\lfloor \frac m{p^I}\right\rfloor) \le r

because for every positive real number x we have \left\lfloor 2x\right\rfloor - 2\left\lfloor x\right\rfloor \le 1. Therefore p^k\le p^r\le 2m. Now let us deduce the theorem from this lemma. Since \pi(n+1)\le \pi(n)+1 for every n, we can assume that n=2m is even. Let k=\pi(2m). Every prime that divides \binom{2m}{m} does not exceed 2m. Therefore \binom{2m}{m}=\prod_{i=1}^\ell p_i^{a_i}, where all primes p_i are different and p_i\le 2m, so \ell \le k. Hence \ln \binom{2m}{m}=\sum a_i\ln p_i. By Lemma, each a_i\ln p_i does not exceed \ln 2m. Hence by Exercise 1


\ell\ge \frac{\ln \binom{2m}{m}}{\ln(2m)}\ge \frac{\ln \frac{4^m}{2m+1}}{\ln(2m)} \ge c\frac{2m}{\ln(2m)}


for some c>0. Thus \pi(2m)\ge c\frac{2m}{\ln(2m)}.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: