5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.