4
$\begingroup$

I would be curious to have a reference for the following proof of Euclid's Theorem on the infinitude of primes:

Using Legendre's formula (also called de Polignac's formula) for $p$-adic valuations of factorials it is not difficult to prove that $$p^{v_p{n\choose a}}\leq n$$ (with $v_p{n\choose a}$ denoting the multiplicity of the prime $p$ in the prime-factorization of the binomial coefficient ${n\choose a}$) for every prime number $p$ and integers $0\leq a\leq n$.

Since ${2n\choose n}$ involves only primes up to $2n$, we get therefore $${2n\choose n}\leq (2n)^{\pi(2n)}$$ with $\pi(2n)$ denoting the number of primes $\leq 2n$.

Using Stirling's approximation ${2n\choose n}\sim\frac{2^{2n}}{\sqrt{\pi n}}$ and taking the logarithm we get now $$2n\log 2\leq \frac{\log \pi+\log n}{2}+\pi(2n)\log(2n)\ .$$

This implies asymptotically $$\liminf \frac{\log(2n)}{2n}\pi(2n)\geq \log 2$$ which is just short by a factor $\log 2$ of the prime-number Theorem and implies that there are infinitely many primes.

Remark: Assuming $\lim\frac{\pi(\lambda x)}{\pi(x)}=\lambda$ for all $\lambda>0$, these arguments can be refined to a proof of the prime-number Theorem.

$\endgroup$
2
  • 1
    $\begingroup$ Not the exact same proof but there's a very similar idea in Hardy and Wright. They are interested in that part in proving Chebyshev's theorem so they need to do slightly more work. But the same basic point of how you use the binomial coefficients is there. $\endgroup$
    – JoshuaZ
    Commented Dec 28, 2022 at 16:09
  • 4
    $\begingroup$ The binomial idea is implicit in Chebyshev's estimates (and Ramanujan's proof of these estimates). It appears explicitly in Erdős' proof of these estimates (1931), so I would consider the proof in the post to be a streamlined version of his argument. See here: cut-the-knot.org/arithmetic/algebra/BertrandPostulate.shtml $\endgroup$ Commented Dec 28, 2022 at 16:12

1 Answer 1

10
$\begingroup$

As Ofir says in the comments, this is very similar to but somewhat simpler than Erdős' proof of Bertrand's postulate. As in that argument, the appeal to Stirling's approximation can be replaced by the simpler estimate ${2n \choose n} \ge \frac{4^n}{2n+1}$ which just comes from observing that ${2n \choose n} \ge {2n \choose k}, 0 \le k \le 2n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .