|
|
|
Viewing Version
4
of
'Bertrand's conjecture, proof of'
|
[ view 'Bertrand's conjecture, proof of'
|
back to history
]
| Title of object: |
Bertrand's conjecture, proof of |
| Canonical Name: |
ProofOfBertrandsConjecture |
| Type: |
Proof |
| Created on: |
2002-12-24 08:44:13 |
| Modified on: |
2005-07-11 22:54:12 |
| Classification: |
msc:11N05 |
Revision comment (for changes between this and next version):
Changes for correction #8767 ('Notation for floor').
Also fixed Erd\H{o}s's name. |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
This is a version of Erd\"{o}s's proof as it appears in Hardy and Wright.
We start by deriving an upper bound on $\Theta$.
Definition.
$$ \Theta(n)=\sum_{\substack{p\leq n\\p{\:\mathrm{prime}}}} \log p $$
Theorem. $\Theta(n)\leq n\log 4$
Proof. By induction.
The cases for $n=1$ and $n=2$ follow by inspection.
For even $n>2$, the case follows immediately from the case for $n-1$ since $n$ isn't prime.
So let $n=2m+1$ with $m>0$ and consider $(1+1)^{2m+1}$ and its binomial expansion. Since ${{2m+1}\choose m}={{2m+1}\choose{m+1}}$ and both terms occur exactly once, we find ${{2m+1}\choose m}\leq 4^m$. Each prime $p$ with $m+1<p\leq 2m+1$ divides ${2m+1}\choose m$ and so $\Theta(2m+1)-\Theta(m+1)\leq\log{{2m+1}\choose m}\leq m\log4$. By induction $\Theta(m+1)\leq(m+1)\log4$ and so $\Theta(2m+1)\leq(2m+1)\log4$.
Now we can deal with the main theorem. Suppose $n>2$ and there is no prime $p$ with $n<p<2n$.
Consider $(1+1)^{2n}$. Since ${2n}\choose n$ is the largest term in the binomial expansion that has $2n+1$ terms, ${{2n}\choose n}\geq\frac{4^n}{2n+1}$.
For a prime $p$ define $r(p,n)$ to be the highest power of $p$ dividing ${2n}\choose n$. We first look at the highest power of $p$ dividing $n!$. Every $p$-th term contributes a factor, so we have already $[\frac{n}{p}]$ factors, where $[x]$ is the integer part of $x$. However, every $p^2$-th term contributes an extra factor above that, and every $p^3$-th term one more and so on. So the highest power of $p$ dividing $n!$ is $\sum_j[\frac{n}{p^j}]$. Now for $r(p,n)$ we need to take the factors contributed by $(2n)!$ and subtract twice the factors taken away by $n!$. This leads us to $r(p,n)=\sum_j([\frac{2n}{p^j}]-2[\frac{n}{p^j}])$. Now each of these terms is either $0$ or $1$ (as is every value of $[2x]-2[x]$), and the terms vanish for $j>[\frac{\log(2n)}{\log p}]$, so $r(p,n)\leq[\frac{\log(2n)}{\log p}]$ or $p^{r(p,n)}\leq 2n$.
Now ${{2n}\choose n}=\prod_p p^{r(p,n)}$. By the previous inequality, primes larger than $2n$ do not contribute to this product and by assumption there are no primes between $n$ and $2n$. So $${{2n}\choose n}=\prod_{\substack{1\leq p \leq n\\ p{\:\mathrm{prime}}}}p^{r(p,n)}.$$
If $p>\sqrt{2n}$, all the terms for higher powers of $p$ vanish and $r(p,n)=[\frac{2n}{p}]-2[{{n}\over{p}}]$.
For $n>p>\frac{2n}{3}$, $\frac{3}{2}>\frac{n}{p}>1$ and so for $p>\frac{2n}{3}>\sqrt{2n}$ we can apply the previous formula for $r(p,n)$ and find that it's zero. So for all $n>4$, the contribution of the primes larger than $\frac{2n}{3}$ is zero.
Now for $p>\sqrt{2n}$, $r(p,n)$ is at most $1$, so an upper bound for the contribution for the primes between $\sqrt{2n}$ and $\frac{2n}{3}$ is the product of all primes smaller than $\frac{2n}{3}$ which equals $e^{\Theta(\frac{2n}{3})}$. There are at most $\sqrt{2n}$ primes smaller than $\sqrt{2n}$ and by the inequality $p^{r(p,n)}\leq 2n$ their product is less than
$(2n)^{\sqrt{2n}}$.
Combining these we get $$\frac{4^n}{2n+1}\leq{{2n}\choose{n}}\leq (2n)^{\sqrt{2n}}e^{\Theta(\frac{2n}{3})}.$$
Using $2n+1<(2n)^2$ and taking logarithms, we find $n\frac{\log4}{3}\leq (\sqrt{2n}+2)\log(2n)$ which is clearly false for large enough $n$, say $n=2^{11}$, leading to a contradiction. For smaller $n$, we prove the theorem by exhibiting a sequence of primes in which each is smaller than the double of its predecessor, e.g., $3, 5, 7, 13,
23, 43, 83, 163, 317, 631, 1259, 2503$. |
|
|
|
|
|
