If $m \ge 2n$, does $\binom{m}{n}$ always have prime factor greater than $n$?

103 Views Asked by At

Backgrounds

Paul Erdos proved Bertrand's Postulate by showing that $\binom{2n}{n}$ always have prime factor greater than $n$.

What I tried

Counterexamples require $n$ consecutive numbers which only has prime factors equal to or less than $n$, which becomes very rare after $1$ to $n$.

I tried following the argument from Wikipedia link.

Lemma 1. By Stirling's approximation, $\binom{m}{n} \approx \sqrt{\frac{1}{2\pi }}\frac{m^{m-0.5}}{n^{n-0.5}(m-n)^{(m-n-0.5)}}$.

Lemma 2. Define $R(p, m, n)$ to be the greatest natural number $r$ such that $p^r$ divides $\binom{m}{n}$. Then by same argument with Wikipedia article, $p^{R(p, m, n)}\le m$.

(I had to omit Lemma 3 of the original article because it exploited the property of $2$ itself)

Lemma 3. Asymptotics of Chebyshev function gives that $x\#\approx e^x$.

Lemma 4. By PNT, $\pi(x)\approx\frac{x}{\log x}$.

Now, assume that $\binom{m}{n}$ has no prime factors larger than $n$. This means$\binom{m}{n}=\prod_{p\le n}p^{R(p,m,n)}$. By lemma 2 and 3,$$\binom{m}{n}\le\prod_{p\le n}p^{R(p,m,n)}\le\prod_{p\le \sqrt{n}}p^{R(p,m,n)}\prod_{\sqrt{n}<p\le n}p\le m^{\pi(\sqrt{n})}n\#\approx e^nm^{\pi(\sqrt{n})}$$. By Lemma 4, $e^nm^{\pi(\sqrt{n})}\approx e^nm^{\frac{2\sqrt{n}}{\log n}}$. Now what is left is to show that $e^nm^{\frac{2\sqrt{n}}{\log n}}<\sqrt{\frac{1}{2\pi }}\frac{m^{m-0.5}}{n^{n-0.5}(m-n)^{(m-n-0.5)}}$ for sufficiently large $m, n$.

Use approximation $\sqrt{\frac{1}{2\pi }} \approx -0.919$ and taking logs on each side gives$$n+\frac{2\sqrt{n}}{\log n}\log m<-0.919+(m-0.5)\log m-(n-0.5)\log n-(m-n-0.5)\log (m-n)$$ Because $\log (m-n)<\log m$,$$(n-0.5)\log n+n+0.919<\left(n-\frac{2\sqrt{n}}{\log n}\right)\log m$$ Above inequality holds for arbitrarily large $n$ if $m=2n$, so this argument doesn't reduce the infinite search space.

Question

Can you prove that $\binom{m}{n}$ always contain prime factor larger than $n$ or provide a counterexample?