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

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!

-
How do I comment on here? Must the primes be distinct? –  Dan Donnelly Dec 30 '10 at 9:54
The primes are less than any given $n \in \mathbb{N}, n > 1$ thats not good :-). Because for n=2 its not possible. And if they are all less for any $n$ it means that you can freely choose $n$.. you probably want $n$ fixed –  Listing Dec 30 '10 at 10:04
So, primorials, huh? –  Ｊ. Ｍ. Dec 30 '10 at 10:06
@InterestedQuest : It not necessary that $x_{1}, x_{2}, x_{3}, \cdots x_{y}$ is be the collection of all the primes less than n, the inequality would still hold for any other subset of primes less than n, the LHS is at it's maximum when all the primes less than n are considered. –  Arjang Dec 31 '10 at 1:06

## 3 Answers

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$.

-
That's a nice argument! Going by your last inequality, when you say $[n]$ you mean the floor $\lfloor n \rfloor$, yes? You can type that as \lfoor n \rfloor. Also, Erdős has a slightly different accent in his name. –  Rahul Dec 30 '10 at 12:49
@Rahul. Thanks for sugestions I've updated the post with them. –  Esteban Crespi Dec 30 '10 at 13:06
This argument was certainly popularized by Erdos because he used it in his proof of Bertrand's postulate, but I am not 100% convinced it is due to him. –  Qiaochu Yuan Dec 30 '10 at 13:14
@Esteban. But if $n$ is odd, say $n=5$, then $${n \choose \lfloor n/2\rfloor}$$ is not one of the summands in the binomial expansion of $(1+1)^n$. Does this affect your proof? –  TCL Dec 30 '10 at 18:58
@Esteban: Your formula for the binomial coefficient $\binom{n}{\lfloor n/2\rfloor}$ is not quite right when $n$ is odd; for example, if $n=7$, then you have $\binom{7}{3} = \frac{7!}{3!4!}$, but your formula has $\frac{7}{3!3!}$. The correct formula would be $\frac{n!}{\lfloor n/2\rfloor!\lceil n/2\rceil!}$. Also, the assertion about primes is not quite right for the same reason; e.g., for $n=9$, you claim that $5$ appears in the numertor but not the denominator of $\binom{9}{4}$, but this is incorrect. You need the ceiling function for that assertion, or just $n/2$ itself. –  Arturo Magidin Dec 30 '10 at 19:14

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

-

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.

-
In Esteban's answer the question was raised as to the origin of this proof. Does anyone know or is it lost in the mists of time? –  Derek Jennings Dec 31 '10 at 13:20
For searching purposes: $\theta(x)$ is the Chebyshev function, the logarithm of the primorial. –  Ｊ. Ｍ. Dec 31 '10 at 13:34