Jul 042012
 

In 1949, Leo Moser gave a proof of  Bertrand’s postulate in the paper “A theorem of the distribution of primes”(American Mathematical Monthly,624-624,1949,vol56). Maybe this proof  is the simplest one among all proofs of  Bertrand’s postulate.

  1. If \(n<p\leqslant 2n\), then \(p\) occurs exactly once in \({2n\choose n}\);
  2. If \(n\geqslant 3, \frac{2n}3<p<n\), then \(p\) doesn’t occurs in \({2n\choose n}\);
  3. If \(p^2>2n\), then \(p\) occurs at most once in \({2n\choose n}\);
  4. If \(2^\alpha\leqslant 2n<2^{\alpha+1}\), then \(p\) occurs at most \(\alpha\) times in \({2n\choose n}\).

If  \(2^\alpha<2n\leqslant  2^{\alpha+1}\), suppose there is no prime \(p\) with

\begin{equation}n<p<2n,\end{equation}

then

\begin{equation}{2n\choose n}\leqslant{2a_1\choose a_1}{2a_2\choose a_2}\dotsm{2\choose 1}\bigg({2a_k\choose a_k}{2a_{k+1}\choose a_{k+1}}\dotsm{2\choose 1}\bigg)^\alpha,\end{equation}

where \(a_1=\big[\frac{n+1}3\big], k=\big[\frac{\alpha+1}2\big]\), and \(a_i=\big[\frac{a_{i-1}+1}3\big]\), for \(i=2,\,3,\,\dotsc\,.\)

By \(1,\,2,\,3\) and \((1)\), every prime which appears on the left-hand side of \((2)\) appears also on the right; and those primes which appear with multiplicity greater than \(1\) on the left appear on the right with multiplicity at least \(2\alpha+1\), which by \(4\) is at least equal to the multiplicity with which they appear on the left.

On the other hand, It is obvious that

\begin{equation}2n>2a_1+2a_2+\dotsb+ 2+\alpha(2a_k+2a_{k+1}+\dotsb+2)\end{equation}

for \(n>2^{11}.\) Hence the inequality in \((2)\) should be reversed. So for \(n>2^{11}\), we have a contradiction which proves Bertrand’s postulate for these values of \(n\).

Jun 262012
 

Sylvester’s theorem  the binomial coefficient

\begin{equation}{n\choose k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}\end{equation}

has a prime divisor \(p\) greater than \(k\). In other words, if \(n\geq 2k\), then the product of  \(k\) consecutive integers greater than \(k\) is divisible by a prime greater than \(k\). Note that for \(n=2k\) we obtain precisely Bertrand’s postulate.

Theorem 

  1. if \(n>6\) is an integer, then there always exists at least two prime numbers \(p\), one  is the form \(4k+1\) and the other \(4k+3\), such that \(n<p<2n\).
  2. if \(k\) is a positive  integer, then there always exists a positive  integer \(N\) such that  for every  integer \(n>N\),  there exist at least \(k\) prime numbers \(p\) such that \(n<p<2n\).
  • 对任意正整数 \(n>6\) ,  至少存在一个 \(4k+1\) 型和一个 \(4k+3\)  型素数 \(p\)  使得  \(n<p<2n\).
  • 对任意正整数 \(k\),  存在正整数 \(N\),  使得只要正整数 \(n>N\),  就存在 \(k\) 个素数 \(p\) 使得 \(n<p<2n\).

注意, 定理 \(2\) 已经隐含在 Ramanujan 给出的 Bertrand’s postulate 的证明中 Ramanujan’s proof of Bertrand’s postulate.

Jun 092012
 

Bertrand’s postulate states that if \(x\geq4\), then there always exists at least one prime \(p\) with\(x<p<2x-2\). A weaker but more elegant formulation is: for every \(x>1\) there is always at least one prime p such that \(x<p<2x\).

In 1919, Ramanujan used properties of  the  Gamma function to give a simple  proof  that  appeared as  a  paper “A proof of Bertrand’s postulate” in the  Journal of the Indian Mathematical Society \( 11: 181–182\).

Let’s begin with the  Chebyshev function :

The  first  Chebyshev  function \(\vartheta(x)\)  is defined with

\begin{equation}\vartheta(x)=\sum_{p\leqslant x}\log p,\end{equation}

The second Chebyshev function \(\psi(x)\) is given by

\begin{equation}\psi(x)=\sum_{i\geqslant 1}\vartheta(x^{\frac1i}),\end{equation}

so

\begin{equation}\log \left[x\right]!=\sum_{i\geqslant 1}\psi(\frac1ix) ,\end{equation}

where \(\left[x\right]\)denotes as usual the greatest integer \(\leqslant x\).

From \((2)\) we have

\begin{equation}\psi(x)-2\psi(\sqrt{x})=\vartheta(x)-\vartheta(x^\frac12)+\vartheta(x^\frac13)-\dotsb,\end{equation}

and from \((3)\)

\begin{equation}\log\left[x\right]!-2\log\left[\frac12x\right]!=\psi(x)-\psi(\frac12x)+\psi(\frac13x)-\dotsb .\end{equation}

Remembering  that \(\vartheta(x)\) and \(\psi(x)\) are steadily increasing functions, from \((4)\) and \((5)\) we get that

\begin{equation}\psi(x)-2\psi(\sqrt{x})\leqslant\vartheta(x)\leqslant\psi(x);\end{equation}

and

\begin{equation}\psi(x)-\psi(\frac12x)\leqslant \log \left[x\right]!-2\log \left[\frac12x\right]!\leqslant\psi(x)-\psi(\frac12x)+\psi(\frac13x). \end{equation}

But it is easy to see that

\begin{equation}\begin{split}\log \Gamma(x)-2\log \Gamma(\frac12x+\frac12)&\leqslant \log \left[x\right]!-2\log \left[\frac12x\right]!\\&\leqslant\log \Gamma(x+1)-2\log \Gamma(\frac12x+\frac12).\end{split}\end{equation}

Now using Stirling’s approximation we deduce from \((8)\) that

\begin{equation}\log \left[x\right]!-2\log \left[\frac12x\right]!<\frac34x, \text{if}  x>0;\end{equation}

and

\begin{equation}\log \left[x\right]!-2\log \left[\frac12x\right]!>\frac23x, \text{if}  x>300.\end{equation}

It follows from \((7)\), \((9)\) and  \((10)\) that

\begin{equation}\psi(x)-\psi(\frac12x)<\frac34x, \text{if}  x>0;\end{equation}

and

\begin{equation}\psi(x)-\psi(\frac12x)+\psi(\frac13x)>\frac23x, \text{if } x>300. \end{equation}

Now changing \(x\) to \(\frac12x\), \(\frac14x\), \(\frac18x\), \(\dotsc\) in \((11)\) and adding up all the results, we obtain

\begin{equation}\psi(x)<\frac32x,\text{if}  x>0.\end{equation}

Again we have

\begin{equation}\begin{split}\psi(x)-\psi(\frac12x)+\psi(\frac13x)&\leqslant\vartheta(x)+2\psi(\sqrt{x})-\vartheta(\frac12x)+\psi(\frac13x)\\&<\vartheta(x)-\vartheta(\frac12x)+\frac12x+3\sqrt{x},\end {split}\end{equation}

in virtue of  \((6)\) and \((13)\).

It  follow from \((12)\) and \((14)\) that

\begin{equation}\vartheta(x)-\vartheta(\frac{1}{2}x)>\frac{1}{6}x-3\sqrt{x}\text{, if }x>300.\end{equation}

But it is obvious that

\begin{equation}\frac16x-3\sqrt{x}\geqslant 0\text{, if } x\geqslant 324,\end{equation}

Hence

\begin{equation}\vartheta(2x)-\vartheta(x)>0, \text{if } x\geqslant162.\end{equation}

In other words there is at least one prime between \(x\) and \(2x\) if  \(x\geq162\). Thus Bertrand’s postulate is proved for all values of  \(x\) not less than \(162\); and, by actual verification, we find that it is true for smaller values.

 

It is obvious that

\begin{equation}\vartheta(x)-\vartheta(\frac12x)\leqslant(\pi(x)-\pi(\frac12x))\log x,\end{equation}

for all values of  \(x\). It follows from \((15)\) and \((18)\) that

\begin{equation}\pi(x)-\pi(\frac12x)>\frac1{\log x}(\frac16x-3\sqrt{x})\text{, if}  x>300.\end{equation}

From this we easily deduce that

\begin{equation}\pi(x)-\pi(\frac12x)\geqslant1,2,3,4,5,\dotsc\text{, if } x\geqslant2,11,17,29,41,\dotsc\end{equation}

respectively.