Show that product of primes, $\prod_{k=1}^{\pi(n)} p_k < 4^n$

Question

This an interesting problem my friend has been working on for a while now (I just saw it an hour ago, but could not come up with anything substantial besides some PMI attempts).

Here's the full problem:

Let $x_{1}, x_{2}, x_{3}, \cdots x_{y}$ be all the primes that are less than a given $n>1,n \in \mathbb{N}$.

Prove that $$x_{1}x_{2}x_{3}\cdots x_{y} < 4^n$$

Any ideas very much appreciated!

Answer 1

I think the following argument is from Erdős: The binomial coefficient $$ {n \choose {\lfloor n/2 \rfloor}} = \frac{n!}{{\lfloor n/2 \rfloor}!{\lceil n/2 \rceil}!}$$ is an integer. Any prime in the range ${\lceil n/2 \rceil}+1 \le p \le n$ will appear in the numerator but not in the denominator, as a consequence $n \choose {\lfloor n/2 \rfloor}$ is divisible by the product of all the primes in the range ${\lceil n/2 \rceil}+1 \le p \le n$. On the other hand if $n$ is even then it will be the central term in the binomial expansion of $(1+1)^n$ so $$ {n \choose {\lfloor n/2 \rfloor}} \le 2^n $$ and if $n$ is odd then $n \choose \lfloor n/2 \rfloor$ and $n \choose \lceil n/2 \rceil$ will be the two central terms of the binomial expansion of $(1+1)^n$, as they are equal we have $$ {n \choose {\lfloor n/2 \rfloor}} \le 2^{n-1} $$ we apply this recursively to $n$, $\lceil n/2 \rceil, \lceil n/4 \rceil, \dots$, but $$ { \lceil n/2 \rceil \choose \lfloor \lceil n/2 \rceil/2 \rfloor } = { \lceil n/2 \rceil \choose \lfloor n/4 \rfloor } \le 2^{\lfloor n/2 \rfloor } $$ using either of the two preceding inequalities depending on the parity of $\lceil n/2 \rceil$, by the same argument we get $${ \lceil n/4 \rceil \choose \lfloor \lceil n/4 \rceil/2 \rfloor } ={ \lceil n/4 \rceil \choose \lfloor n/8 \rfloor } \le 2^{\lfloor n/4 \rfloor }$$ and so on, so $$ \begin{align}{n \choose {\lfloor n/2 \rfloor}}{{\lceil n/2 \rceil} \choose {\lfloor n/4 \rfloor}}{{\lceil n/4 \rceil} \choose {\lfloor n/8 \rfloor}}\cdots &\le 2^n\cdot 2^{{\lfloor n/2 \rfloor}} \cdot 2^{{\lfloor n/4 \rfloor}} \cdots \\\\ &\le 2^{n + {\lfloor n/2 \rfloor} + {\lfloor n/4 \rfloor} + \cdots } \\\\ &\le 2^{n(1 + 1/2 + 1/4 + \cdots) } = 2^{2n} = 4^n\end{align}$$ but the left hand side is divisible by all the primes up to $n$. So the product of any subset of these primes will also be bounded by $4^n$.

Answer 2

I just like to point out that this argument is in Hardy and Wright, An Introduction to the Theory of Numbers, with the slight differences that they avoid the use of the floor and ceiling functions, and finish off (quite nicely, in my opinion) with induction.

I'll type it here, to save you looking it up.

Theorem: $\theta(n) < 2n \log 2$ for all $ n \ge 1,$ where $$\theta(x) = \log \prod_{p \le x} p.$$

Let $M = { 2m+1 \choose m},$ an integer, which occurs twice in the expansion of $(1+1)^{2m+1}$ and so $2M < 2^{2m+1}.$ Thus $M< 2^{2m}.$

If $m+1 < p \le 2m+1,$ $p$ divides $M$ since it divides the numerator, but not the denominator, of $ { 2m+1 \choose m } = \frac{(2m+1)(2m)\ldots(m+2)}{m!}.$

Hence

$$\left( \prod_{m+1 < p \le 2m+1} p \right) | M $$

and

$$ \theta(2m+1) - \theta(m+1) = \sum_{m+1 < p \le 2m+1} \log p \le \log M < 2m \log 2.$$

The theorem is clear for $n=1$ and $n=2,$ so suppose that it is true for all $n \le N-1.$ If $N$ is even, we have

$$ \theta(N)= \theta(N-1) < 2(N-1) \log 2 < 2N \log 2.$$

If $N$ is odd, $N=2m+1 $ say, we have

$$\begin{align} \theta(N)=\theta(2m+1) &=\theta(2m+1)-\theta(m+1)+\theta(m+1) \\ &< 2m \log 2 +2(m+1) \log 2 \\ &=2(2m+1) \log 2 = 2N \log 2, \end{align}$$

since $m+1 < N.$ Hence the theorem is true for $n=N$ and the result follows by induction.

EDIT: It turns out that this proof was discovered by Erdős and another mathematician, Kalmar, independently and almost simultaneously, in 1939. See Reflections, Ramanujan and I, by Paul Erdős.

Answer 3

Note my comment above, also when you look a bit at the net you directly find proofs for this theorem. The easiest ones probably use induction, it is basically like this proof:

http://mathrefresher.blogspot.com/2009/11/primorial.html