# $\text{lcm}(1,2,3,\ldots,n)\geq 2^n$ for $n\geq 7$

I can prove that $\text{lcm}(1,2,3,\ldots,n)\geq 2^{n-1}$.

Newly, i read in a paper that for $n\geq 7$ we have:

$$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$$

Can you prove it?

(This inequality is an interesting inequality. For example with this inequality can find a lower bound for the number of primes less than $n$.)

• How did you prove the original claim, with $2^{n-1}$? Jun 29, 2014 at 15:26
• Sidenote: for any $b<e$, lcm(1, 2, ..., n) > b^n for large enough n. Jun 29, 2014 at 15:45
• Huh... is it true that, as $n\to\infty$, we have $e^{-n}\mathrm{lcm}(1,\ldots,n)\to 1$? Jun 29, 2014 at 15:49
• @GTonyJacobs Yes, it is equivalent to the Prime Number Theorem. Jun 30, 2014 at 19:16
• $\text{lcm}(1,2,3,\ldots,n) = n\text{lcm}\left(\binom{n-1}{1},\cdots,\binom{n-1}{n-1}\right) \ge [n/2]\binom{n}{[n/2]} \geq 2^n$ for $n \ge 7$ .. W|A :-)
– r9m
Jul 3, 2014 at 9:15

The proof for this, is almost the same for proving the bound of $2^{n-1}$. Consider for $1\le m\le n$ $$I_{m,n}=\int_{0}^{1}x^{m-1}(1-x)^{n-m}=\sum_{r=0}^{n-m}\frac{a_r}{m+r}\quad \text{ for some }a_i\in \mathbb{Z}$$ Let $\displaystyle\ell_n=\text{lcm}(1,2,\dots,n)$. See $\ell_nI_{m,n}\in \mathbb{Z}$ for $1\le m\le n$. Now it can be easily seen that $\displaystyle I_{m,n}=\frac{1}{m\dbinom{n}{m}}$. Which will follow from integration by parts or reduction formulae. Then we have: $$m\dbinom{n}{m}\mid \ell_n\quad \forall \;\;1\le m\le n$$ In general $$n\dbinom{2n}{n}\mid \ell_{2n}\quad \text{ and }\quad (2n+1)\dbinom{2n}{n}=(n+1)\dbinom{2n+1}{n+1}\mid \ell_{2n+1}$$ Now since $\ell_{2n}\mid \ell_{2n+1}$ we have \begin{align*} & n(2n+1)\dbinom{2n}{n}\mid \ell_{2n+1}\\ \implies & \ell_{2n+1}\ge n(2n+1)\dbinom{2n}{n}\ge n\cdot 4^n\ge 2^{2n+2}\quad \text{ for } \quad n\ge 4\end{align*} The second last inequality holds since $\dbinom{2n}{n}$ is the largest co-efficient in the expansion of $(1+x)^{2n}$. Hence $(1+1)^{2n}\le \dbinom{2n}{n}(2n+1)$. Also $$\ell_{2n+2}\ge \ell_{2n+1}\ge 2^{2n+2}\quad \text{ for }\quad n\ge 4$$ Hence we have proved $$\ell_n\ge 2^{n}\quad \text{ for }\quad n\ge 9$$ Smaller cases are checked by hand. Thus we are done.

Also about the fact that $\log \ell_n\approx n$. This is a sketch.

Take some prime $p$ dividing $\ell_n$. Now $\nu_p$ be the highest exponent of $p$ in $\ell_n$. Then $p^{\nu_p}\mid k$ for some $1\le k\le n$, then $p^{\nu_p}\le n\implies \nu_p\le \frac{\log n}{\log p}$ Now \begin{align*} &\ell_n=\prod_{p\le n}p^{\nu_p}\le \prod_{p\le n}p^{\frac{\log n}{\log p}}\\ \implies & \log \ell_n\le \sum_{p\le n}\left(\frac{\log n}{\log p}\cdot \log p\right)=\pi(n)\log n\approx n\quad \text{for large }n\end{align*} where the last statement holds due to the prime number theorem.

For real $$x$$ let $$L(x) = \operatorname{lcm}(1,2,3,\dots,\lfloor x \rfloor)$$, we have: $$L(n) = \prod_{p^k\le n } p \qquad\qquad(1)$$ where the product extends to all prime powers in the range $$1, n$$.

in his proof of Bertrand's postulate, Tchebyshev proved that $$n! = \prod_{k=1}^\infty L\left(\frac{n}{k}\right) \qquad\qquad(2)$$

this can be proved easily by induction, it is trivial for $$n=1$$ then going from $$n-1$$ involves a factor of $$n$$ in the left hand side while in the right hand side, we get a product of terms: $$\frac{L(n/k)}{L((n-1)/k)} = \begin{cases} p \quad & \text{if } n/k=p^t\\ 1 &\text{otherwise} \end{cases}$$ so we have a factor $$p$$ for every $$p^t\vert n$$ and so a total factor of $$n$$ also in the right.

And he used (2) to prove something implying: $$\frac{n! \lfloor n/30\rfloor!}{\lfloor n/2\rfloor!\lfloor n/3\rfloor!\lfloor n/5\rfloor!} \text{ is an integer and divides } L(n)$$

Using the same method we are going to show something weaker: $$R(n)=\frac{n! \lfloor n/12\rfloor!}{\lfloor n/2\rfloor!\lfloor n/3\rfloor!\lfloor n/4\rfloor!} \text{ is an integer and divides } L(n) \qquad\qquad(3)$$

To prove (3) we substitute (2) in $$R(n)$$ and we get $$R(n) = \frac{L(n)L(n/2)L(n/3)\dots \times L(n/12)L(n/2 4)\dots }{ L(n/2)L(n/4)L(n/8) \dots \times L(n/3)L(n/6)L(n/9) \dots \times L(n/4)L(n/8)L(n/12) \dots}$$
it is easy to check that this simplifies to $$R(n) = \frac{L(n)}{L(n/4)}\times \frac{L(n/5)}{L(n/6)} \times \frac{L(n/7)}{L(n/8)} \times \frac{L(n/11)}{L(n/12)} \times \dots$$ where the sequence repeats modulo 12 this ie the next term would be $$L(n/(12+1))/L(n/(12+4))$$, the next $$L(n/(12+5))/L(n/(12+4))$$ and so on. As every factor $$L(n)/L(n/4), \dots$$ is an integer this shows that $$R(n)$$ is an integer. On the other hand the same product shows that $$R(n) = \prod_{n/4< p^k \le n} p \times \prod_{n/6< p^k \le n/5} p \times \prod_{n/7< p^k \le n/8} \times \dots$$ and as the ranges in the products do not overlap we have: $$R(n) \text{ divides }\prod_{ p^k \le n} p = L(n)$$ And this ends the proof of (3).

So it is enough to show that $$R(n) \ge 2^n$$ for $$n\ge 7$$. $$R(n)$$ es easy to compute knowing $$R(n-1)$$ just checking which new factors appear in the numerator and denominator of $$R(n)$$ when going from $$n-1$$ to $$n$$: $$\frac{R(n)}{R(n-1)} = \begin{cases} n \quad & \text{ si } \operatorname{gcd}(n,12)=1\\ 2 \quad & \text{ si } \gcd(n,12)=2\\ 3 \quad & \text{ si } \gcd(n,12)=3\\ 8/n \quad & \text{ si } \gcd(n,12)=4\\ 6/n \quad & \text{ si } \gcd(n,12)=6\\ 2/n \quad & \text{ si } \gcd(n,12)=12 \end{cases}$$ Now we can proceed by induction, suppose that we know that $$R(12k) \ge 2^{12k}$$, for some $$k\ge 1$$ then the following table shows that $$R(12k+t) \ge 2^{12k+t}$$

$$t$$ $$\gcd(12,t)$$ $$\frac{R(12k+t)}{R(12k+t-1)}$$ $$R(12k+t)/R(12k)$$
1 1 $$12k+1$$ $$12k+1 \ge 2$$
2 2 $$2$$ $$2(12k+1)\ge 2^2$$
3 3 $$3$$ $$6(12k+1)\ge 2^3$$
4 4 $$\frac{4}{12k+4}$$ $$6\frac{12k+1}{3k+1}\ge 2^4$$
5 1 $$12k+5$$ $$\ge 24(12k+1)\ge 2^5$$
6 6 $$\frac{6}{12k+6}$$ $$\ge 144 \frac{12k+5}{12k+6}\ge 2^6$$
7 1 $$12k+7$$ $$\ge 144 (12k+5) \ge 2^7$$
8 4 $$\frac{4}{12k+8}$$ $$\ge 576 \frac{12k+5}{12k+8} \ge 2^8$$
9 3 $$3$$ $$\ge 1728 \frac{12k+5}{12k+8} \ge 2^9$$
10 2 $$2$$ $$\ge 3456 \frac{12k+5}{12k+8} \ge 2^{10}$$
11 1 $$12k+11$$ $$\ge 3456 \frac{12k+5} \ge 2^{11}$$
12 12 $$\frac{2}{12k+12}$$ $$\ge 6912 \frac{12k+5}{12k+12} \ge 2^{12}$$

We also have that $$R(7)=R(8)=420$$, $$R(9)=1260$$, $$R(10)=2520$$, $$R(11)=27720$$ and $$R(12)=4620$$, all of them verify $$R(n)\ge 2^n$$ so we finally have $$L(n) \ge R(n)\ge 2^n.$$