Question regarding $C(n)$ and $B(n)$ in Hanson’s proof that $\prod\limits_{p^a \le n} p < 3^n$

least-common-multiplemultinomial-coefficientsprime numbersproof-explanation

In Denis Hanson's proof, he defines two terms:

(1) $B(n)$: which is the Least Common Multiple of $\{1,2,\dots,n\}$

$$B(n) = \prod\limits_{p^a \le n}p$$

(2) $C(n)$: an integer

$$C(n) = \dfrac{n!}{\lfloor n/a_1 \rfloor\lfloor n/a_2 \rfloor\lfloor n/a_3 \rfloor\dots}$$

where $a_1 = 2$ and $a_{n+1} = a_1 a_2 \dots a_n + 1$

The proof ends with the following conclusion:

$$C(n) < 3^n$$

I am completely lost where $C(n)$ was shown to be equal or greater to $B(n)$.

Am I misunderstanding?

If someone could explain how $C(n) \ge \text{LCM}(1,2,\dots,n)$, I would greatly appreciate it.

Best Answer

Since $\alpha_p$ is such that $p^{\alpha_p}$ is the highest power of $p$ not exceeding $n$, we can write $$\alpha_p=[\log_pn]$$ So, $B(n)$ is written as $$B(n)=\prod_{p\le n}p^{[\log_pn]}$$

From LEMMA 2., we get $$[\log_pn]\le \beta_p(n)$$ from which $$B(n)=\prod_{p\le n}p^{[\log_pn]}\le \prod_{p\le n}p^{\beta_p(n)}=C(n)$$ follows.

Related Solutions

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

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

Not clear in one step in the inequality for the proof LCM$(1,2,\dots,n) < 3^n$

First of all, from your previous question, I think (2.6) should be $$C(n) < \dfrac{(en)^{k-1+1/(a_{k+1}\color{red}{-}1)}w^n}{a_1^{(a_1-1)/a_1}a_2^{(a_2-1)/a_2}\dots a_k^{(a_k-1)/a_k}}\lt e^{k - 3/2}n^{k - 3/2}w^n$$ (see the minus sign in red in the numerator)

To prove $$\dfrac{(en)^{k-1+1/(a_{k+1}-1)}w^n}{a_1^{(a_1-1)/a_1}a_2^{(a_2-1)/a_2}\dots a_k^{(a_k-1)/a_k}}\lt e^{k - 3/2}n^{k - 3/2}w^n\tag1$$ it is sufficient to prove $$(en)^{k-1+1/(a_{k+1}-1)-(k-3/2)}\lt a_1^{(a_1-1)/a_1}a_2^{(a_2-1)/a_2}\dots a_k^{(a_k-1)/a_k},$$ i.e. $$(en)^{1/2+1/(a_{k+1}-1)}\lt a_1^{(a_1-1)/a_1}a_2^{(a_2-1)/a_2}\dots a_k^{(a_k-1)/a_k}$$ Since $n\le a_1a_2\cdots a_k$, it is sufficient to prove $$(ea_1a_2\cdots a_k)^{1/2+1/(a_{k+1}-1)}\lt a_1^{(a_1-1)/a_1}a_2^{(a_2-1)/a_2}\dots a_k^{(a_k-1)/a_k},$$ i.e. $$e^{1/2+1/(a_{k+1}-1)}\lt a_1^{1/2-1/a_1-1/(a_{k+1}-1)}a_2^{1/2-1/a_2-1/(a_{k+1}-1)}\cdots a_k^{1/2-1/a_k-1/(a_{k+1}-1)},$$ i.e. $$e^{1/2+1/(a_{k+1}-1)}2^{1/(a_{k+1}-1)}\lt a_2^{1/2-1/a_2-1/(a_{k+1}-1)}\cdots a_k^{1/2-1/a_k-1/(a_{k+1}-1)}$$ Since $a_i^{1/2-1/a_i-1/(a_{k+1}-1)}\gt 1$ for $2\le i\le k-1$, It is sufficient to prove $$e^{1/2+1/(a_{k+1}-1)}2^{1/(a_{k+1}-1)}\lt a_k^{1/2-1/a_k-1/(a_{k+1}-1)}\tag2$$ for $k\ge 3$.

Note here that seeing $(2)$ as an inequality on $k$, we see that the LHS of $(2)$ is decreasing and that the RHS of $(2)$ is increasing, so it is sufficient to prove $(2)$ for $k=3$, which is equivalent to $$2e^{22}\lt 7^{14}$$ which is indeed true.

Therefore, $(1)$ is true.

Best Answer

Related Solutions

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

Not clear in one step in the inequality for the proof LCM$(1,2,\dots,n) < 3^n$

Related Question