The Beauty of Primes 1: The Product of All Primes

素数之美1：所有素数之积 苏剑林 · 2014-07-30 · Mathematics prime number number theory

In an earlier post on Euler's mathematics, we computed the sum of the reciprocals of all primes and found that this sum diverges, which in turn gives a proof that there are infinitely many primes. In this post, we try computing the product of all primes. Using a simple trick, we obtain an upper bound for the product of primes (later we'll also compute a lower bound), and from this we also get an upper-bound formula for $\pi(n)$. More importantly, this estimate is one of the key ingredients in an elementary proof of Bertrand's postulate (which states that there is always a prime between n and 2n). The content of this post partly draws on Proofs from the Book and An Introduction to Analytic and Probabilistic Number Theory.

The Product of Primes

As I've said before, what's fascinating about number theory is how it keeps surprisingly linking together different areas of mathematics. As readers will soon see, the proof in this post has an important connection with combinatorics (though it's just a simple one). Regarding the product of primes, we have the following result:

The product of all primes not exceeding $n$ is less than $4^{n-1}$.

If we use $p$ to denote a prime, this can be written as $\prod\limits_{p\leq n}p < 4^{n-1}$. In fact, with more sophisticated techniques this estimate can be greatly improved, since the prime number theorem tells us $\pi(n)\sim \frac{n}{\ln n}$, and hence $\prod\limits_{p\leq n}p \sim e^n$, meaning that for any $\varepsilon > 0$, there exists $N(\varepsilon) > 0$ such that for all $n > N(\varepsilon)$, we have $\prod\limits_{p\leq n}p < (e+\varepsilon)^n$. However, the method and estimate used in this post are fairly elementary, so we can only obtain the upper bound $4^n$ — but as readers will soon see, for the purpose of proving Bertrand's postulate, this estimate is good enough.

Let's now prove it. It's easy to check that the result holds for n = 2. And it's obvious that if the estimate holds for odd n, it must also hold for the even number n+1. So we only need to prove it for the case $n=2m+1$. We use mathematical induction: suppose the result holds for all cases $n=1,2,\dots,2m$, and we split $n=2m+1$ into two parts:

$$\prod_{p\leq 2m+1}p=\prod_{p\leq m+1}p\prod_{m+1 < p\leq 2m+1}p < 4^m\prod_{m+1 < p\leq 2m+1}p$$

The last inequality follows from the induction hypothesis. There's still one part left, namely the product of the primes between m+1 and 2m+1. For this we consider the binomial coefficient

$$C_{m+1}^{2m+1}=\binom{2m+1}{m+1}=\frac{(2m+1)!}{(m+1)! m!}$$

By definition, $C_{m+1}^{2m+1}$ is an integer, and it's divisible by every prime greater than m+1 and at most 2m+1, so clearly

$$\prod_{m+1 < p\leq 2m+1}p\leq C_{m+1}^{2m+1}$$

Estimating $C_{m+1}^{2m+1}$, we find that

$$C_{m+1}^{2m+1} \leq 2^{2m}=4^m$$

This is because $C_{m+1}^{2m+1}=C_{m}^{2m+1}$, and

$$C_{m+1}^{2m+1}+C_{m}^{2m+1}\leq \sum_{k=0}^{2m+1}C_{k}^{2m+1}=2^{2m+1}$$

The exponent 4 is optimal — without changing the method of estimation, no better exponent can be extracted from this binomial coefficient. To see this, one only needs to use Stirling's formula to work out the asymptotic approximation of $C_{m+1}^{2m+1}$.

With this estimate for $C_{m+1}^{2m+1}$, we then have

$$\prod_{p\leq 2m+1}p< 4^m\prod_{m+1 < p\leq 2m+1}p\leq 4^{2m}$$

That is, the result holds for $n=2m+1$. By the induction hypothesis, it therefore holds for all positive integers.

The Number of Primes

With this estimate in hand, we can also derive an upper bound for $\pi(n)$, simply by noting that

$$t^{\pi(n)-\pi(t)} < \prod_{p\leq n}p < 4^{n-1}$$

where $t$ is an arbitrary constant. Taking logarithms of both sides gives

$$\pi(n) < \frac{(n-1)\ln 4}{\ln t}+\pi(t)\leq \frac{n\ln 4}{\ln t}+t$$

In number theory, the usual strategy for improving an estimate is to introduce some free parameter — like t above — and then tune that parameter to get the optimal bound. So for the inequality above, let's set $f(t)=\frac{(n-1)\ln 4}{\ln t}+t$ and find its minimum:

$$f'(t)=-\frac{n\ln 4}{(\ln t)^2 t}+1$$

Setting the derivative to zero gives $n\ln 4=(\ln t)^2 t$. This is a transcendental equation with no explicit closed-form solution, but an approximate solution can be obtained by iteration, rewriting it as

$$t_{k+1}=\frac{n\ln 4}{(\ln t_k)^2}$$

Starting from $t_0=n$ and iterating once gives $t_1=\frac{n\ln 4}{(\ln n)^2}$. To avoid ending up with a messy expression, we stop the iteration here, and for simplicity drop the factor $\ln 4$, simply taking $t=n/(\ln n)^2$. Substituting this in and simplifying gives

$$\pi(n) < \left(\ln 4+\frac{8\ln\ln n}{\ln n}\right)\frac{n}{\ln n}$$

This estimate is much weaker than what the prime number theorem gives, but since it's derived from the simplest kind of counting argument, it's satisfying enough.