# Question about Paul Erdös' proof on the Sylvester-Schur Theorem

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

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

• Thank you very much! I've been struggling with this one for the last two days. This really helps! – Larry Freeman Sep 17 '18 at 6:29
• @Larry Freeman: You are welcome! – mathlove Sep 17 '18 at 6:30