20
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ How did you prove the original claim, with $2^{n-1}$? $\endgroup$ Jun 29, 2014 at 15:26
  • 2
    $\begingroup$ Sidenote: for any $b<e$, lcm(1, 2, ..., n) > b^n for large enough n. $\endgroup$
    – Charles
    Jun 29, 2014 at 15:45
  • $\begingroup$ Huh... is it true that, as $n\to\infty$, we have $e^{-n}\mathrm{lcm}(1,\ldots,n)\to 1$? $\endgroup$ Jun 29, 2014 at 15:49
  • 2
    $\begingroup$ @GTonyJacobs Yes, it is equivalent to the Prime Number Theorem. $\endgroup$ Jun 30, 2014 at 19:16
  • 3
    $\begingroup$ $\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 :-) $\endgroup$
    – r9m
    Jul 3, 2014 at 9:15

2 Answers 2

14
+50
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.