4
$\begingroup$

Let $\operatorname{LCM}[n]:=\operatorname{lcm}\{1,\ldots,n\}$. It is easy to verify $\operatorname{LCM}[n]\geq 2^{\pi(n)}$, where $\pi(n)$ counts the number of distinct primes up to $n$.

But how can I prove the bound $\operatorname{LCM}[n]\geq (\sqrt{n})^{\pi(n)}$?

For the bound $2^{\pi(n)}$, I used the identity:

$\operatorname{LCM}[n]=\!\!\!\prod_{p\in\mathbb{P},p\leq n} p ^{\lfloor \log_p(n) \rfloor}$

But this doesn't work with the lower bound of $\operatorname{LCM}[n]\geq (\sqrt{n})^{\pi(n)}$. Can someone give me a hint?

4 Answers 4

5

The exact same identity works. You can do much better than $p^{\lfloor \log_p(n) \rfloor} \ge 2$, and show that $p^{\lfloor \log_p(n) \rfloor} > \sqrt{n}$. Here's the idea: $p^{\lfloor \log_p(n) \rfloor}$ is just the largest power of $p$ that fits into $[1,n]$.

If $p$ is in the range $(n^{1/2},n]$ there is nothing to prove. But if $p$ is in $(n^{1/3},n^{1/2}]$ then $p^2 \le n$ and $p^2 > \sqrt{n}$. If you think about it, no matter what prime you start with, there is some power of $p$ that is larger than $\sqrt{n}$.

  • 0
    I didn't see $\lfloor \log_p(n)\ge \log_p(n)/2$. Now, it is clear. Thank you.2012-06-18
3

Not sure why I can't comment here, but anyway... Here's a suggestion:

From your bound, you get $LCM[n]\ge\prod_{p\in\mathbb P, p\le n}p$.

It would therefore suffice to show that the geometric mean of $\{p\in\mathbb P,p\le n\}$ is greater than $\sqrt n$. Pairing the primes, the smallest with the biggest etc, the product of each pair is greater than $n$ (by Bertrand's postulate) so you're done?

  • 0
    The Bertrand's postulate says that the product of 2 and the largest prime less than $n$ exceeds $n$. I guess I didn't think about 3 or the subsequent primes. In practice, this should get easier and the products should get bigger, but maybe I do need a little more firepower than Bertrand's postulate..2012-06-18
3

All that is needed for the proof is the elementary inequality $\lfloor x\rfloor \geq \dfrac{x}{2} \text{ for $x \geq 1$}$

Note that the $\text{lcm}(\{1,2,\ldots,n\}) = \exp(\psi(n))$, where $\psi(n)$ is the second Chebyshev function. Hence, we want to prove that $\exp(\psi(n)) \geq \exp \left( \log(\sqrt{n}) \pi(n)\right) = \exp \left( \dfrac{\pi(n) \log(n)}2 \right)$ So, we need to prove that $\psi(n) \geq \dfrac{\pi(n) \log(n)}2$.

Note that $\psi(n) = \sum_{p\text{ is prime}} \sum_{\overset{k \in \mathbb{Z}^+}{p^k \leq n}} \log_e(p) = \sum_{p\text{ is prime}} \log_e(p) \lfloor \log_p(n)\rfloor$ Now for $x\geq 1$, we have $\lfloor x\rfloor \geq \dfrac{x}{2}$. Since $p \leq n$, we have $\lfloor \log_p(n)\rfloor \geq \dfrac{\log_p(n)}{2}$.

Hence, we get that $\psi(n) = \sum_{p\text{ is prime}} \log_e(p) \lfloor \log_p(n)\rfloor \geq \sum_{p\text{ is prime}} \dfrac{\log_e(p) \log_p(n)}{2} = \sum_{p\text{ is prime}} \dfrac{\log_e(n)}{2} = \dfrac{\pi(n)\log_2(n)}2$

  • 0
    (+1) I hope you don't mind, but I just came across this question and I had a similar idea. I use $\lfloor x\rfloor\gt\frac x2$, but not $\psi$. I think my approach might be a bit simpler. However, if you feel it is too similar, I will remove it.2013-07-04
1

This is a slightly different, and hopefully simpler, take on this answer.

We have that for $x\ge1$, $\lfloor x\rfloor\gt\frac x2$. Thus, for $n\gt1$, $n$ has at least one prime factor, so

$ \begin{align} \mathrm{lcm}(1,2,3,\dots,n) &=\prod_{\substack{p\le n\\p\text{ prime}}}p^{\left\lfloor\log(n)/\log(p)\right\rfloor}\\ &\gt\prod_{\substack{p\le n\\p\text{ prime}}}p^{\frac12\log(n)/\log(p)}\\ &=\prod_{\substack{p\le n\\p\text{ prime}}}n^{1/2}\\ &=\left(n^{1/2}\right)^{\pi(n)} \end{align} $