I'm going through the proof and I am not clear the sufficiency of Erdös's argument at one step.
Here's the set up to the argument:
(1) Let $\{x\}$ be the least integer greater or equal to $x$.
(2) Let $a_i$ be shorthand for $\left\{\dfrac{n}{2^i}\right\}$ so that $a_1 =\left\{\dfrac{n}{2}\right\}, a_2 =\left\{\dfrac{n}{2^2}\right\}, a_k =\left\{\dfrac{n}{2^k}\right\}$ and $a_1 \ge a_2 \ge a_3 \ge \dots a_k$
(3) $a_k \le 2a_{k+1}$ since $a_k < \dfrac{n}{2^k}+1 = \dfrac{2n}{2^{k+1}}+1 \le 2a_{k+1} + 1$
(4) If $m$ is the first exponent for which $\dfrac{n}{2^m} \le 1$, then $a_m = 1$
Now, here's the conclusion that Erdös makes:
$\prod\limits_{p_i \le n}p_i\prod\limits_{p_k \le \sqrt{n}}p_k\prod\limits_{p_l \le \sqrt[3]{n}}p_l \dots \le {2a_1 \choose a_1}{2a_2 \choose a_2}\dots{2a_m\choose a_m}$
The argument for this is based on the following observations (which all seem reasonable to me — I am just not clear how they add up to the conclusion above)
- $1 < y \le n$ is completely covered by the intervals:
$$a_m < y\le 2a_m, a_{m-1} < y \le 2a_{m-1}, \dots, a_1 < y \le 2a_1$$
- The interval $1 < y \le \left\lfloor\sqrt[k]{n}\right\rfloor$ is completely covered by the intervals:
$$\left\lfloor\sqrt[k]{a_m}\right\rfloor < y\le \left\lfloor\sqrt[k]{(2a_m)}\right\rfloor, \left\lfloor\sqrt[k]{a_{m-1}}\right\rfloor < y\le \left\lfloor\sqrt[k]{(2a_{m-1})}\right\rfloor, \dots,$$
I am not clear how this shows for the inequality above: "the right side being a multiple of the left."
Best Answer
From the observations, we can say that
$$\prod\limits_{p_i \le \sqrt[k]n}p_i\le \left(\prod_{\left\lfloor\sqrt[k]{a_1}\right\rfloor < p_i\le \left\lfloor\sqrt[k]{2a_1}\right\rfloor}p_i\right)\left(\prod_{\left\lfloor\sqrt[k]{a_2}\right\rfloor < p_i\le \left\lfloor\sqrt[k]{2a_2}\right\rfloor}p_i\right)\cdots \left(\prod_{\left\lfloor\sqrt[k]{a_1}\right\rfloor < p_i\le \left\lfloor\sqrt[k]{2a_m}\right\rfloor}p_i\right)$$ and that the right side is a multiple of the left.
So, $$\begin{align}&\prod\limits_{p_i \le n}p_i\prod\limits_{p_k \le \sqrt{n}}p_k\prod\limits_{p_l \le \sqrt[3]{n}}p_l \dots \\\\&\le \left(\prod_{\left\lfloor a_1\right\rfloor < p_i\le \left\lfloor 2a_1\right\rfloor}p_i\right)\left(\prod_{\left\lfloor a_2\right\rfloor < p_i\le \left\lfloor 2a_2\right\rfloor}p_i\right)\cdots \left(\prod_{\left\lfloor a_1\right\rfloor < p_i\le \left\lfloor 2a_m\right\rfloor}p_i\right) \\\\&\qquad\times \left(\prod_{\left\lfloor\sqrt{a_1}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_1}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor\sqrt{a_2}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_2}\right\rfloor}p_k\right)\cdots \left(\prod_{\left\lfloor\sqrt{a_1}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_m}\right\rfloor}p_k\right) \\\\&\qquad\times \left(\prod_{\left\lfloor\sqrt[3]{a_1}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_1}\right\rfloor}p_l\right)\left(\prod_{\left\lfloor\sqrt[3]{a_2}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_2}\right\rfloor}p_l\right)\cdots \left(\prod_{\left\lfloor\sqrt[3]{a_1}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_m}\right\rfloor}p_l\right) \\\\&\qquad\times\cdots \\\\&=\left(\prod_{\left\lfloor a_1\right\rfloor < p_i\le \left\lfloor 2a_1\right\rfloor}p_i\right)\left(\prod_{\left\lfloor\sqrt{a_1}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_1}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor\sqrt[3]{a_1}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_1}\right\rfloor}p_l\right)\cdots \\\\&\qquad\times\left(\prod_{\left\lfloor a_2\right\rfloor < p_i\le \left\lfloor 2a_2\right\rfloor}p_i\right)\left(\prod_{\left\lfloor \sqrt{a_2}\right\rfloor < p_k\le \left\lfloor \sqrt{2a_2}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor \sqrt[3]{a_2}\right\rfloor < p_l\le \left\lfloor \sqrt[3]{2a_2}\right\rfloor}p_l\right)\cdots \\\\&\qquad\times\cdots \\\\&\qquad\times \left(\prod_{\left\lfloor{a_m}\right\rfloor < p_i\le \left\lfloor{2a_m}\right\rfloor}p_i\right)\left(\prod_{\left\lfloor\sqrt{a_m}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_m}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor\sqrt[3]{a_m}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_m}\right\rfloor}p_l\right)\cdots \end{align}$$
Since $\binom{2a_k}{a_k}$ is divisible by any prime $p$ such that $$\sqrt[s]{a_k}\lt p\le \sqrt[s]{2a_k}$$ for any positive integer $s$, we see that $$\left(\prod_{\left\lfloor a_k\right\rfloor < p_i\le \left\lfloor 2a_k\right\rfloor}p_i\right)\left(\prod_{\left\lfloor\sqrt{a_k}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_k}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor\sqrt[3]{a_k}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_k}\right\rfloor}p_l\right)\cdots$$ divides $$\binom{2a_k}{a_k}$$
Therefore, we can say that $$\begin{align}&\left(\prod_{\left\lfloor a_1\right\rfloor < p_i\le \left\lfloor 2a_1\right\rfloor}p_i\right)\left(\prod_{\left\lfloor\sqrt{a_1}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_1}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor\sqrt[3]{a_1}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_1}\right\rfloor}p_l\right)\cdots \\\\&\qquad\times\left(\prod_{\left\lfloor a_2\right\rfloor < p_i\le \left\lfloor 2a_2\right\rfloor}p_i\right)\left(\prod_{\left\lfloor \sqrt{a_2}\right\rfloor < p_k\le \left\lfloor \sqrt{2a_2}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor \sqrt[3]{a_2}\right\rfloor < p_l\le \left\lfloor \sqrt[3]{2a_2}\right\rfloor}p_l\right)\cdots \\\\&\qquad\times\cdots \\\\&\qquad\times \left(\prod_{\left\lfloor{a_m}\right\rfloor < p_i\le \left\lfloor{2a_m}\right\rfloor}p_i\right)\left(\prod_{\left\lfloor\sqrt{a_m}\right\rfloor < p_k\le \left\lfloor\sqrt{2a_m}\right\rfloor}p_k\right)\left(\prod_{\left\lfloor\sqrt[3]{a_m}\right\rfloor < p_l\le \left\lfloor\sqrt[3]{2a_m}\right\rfloor}p_l\right)\cdots\end{align}$$ divides $${2a_1 \choose a_1}{2a_2 \choose a_2}\dots{2a_m\choose a_m}$$
It follows from these that $${2a_1 \choose a_1}{2a_2 \choose a_2}\dots{2a_m\choose a_m}$$ is a multiple of $$\prod\limits_{p_i \le n}p_i\prod\limits_{p_k \le \sqrt{n}}p_k\prod\limits_{p_l \le \sqrt[3]{n}}p_l \dots $$