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

  • 2
    You can just logarithm both sides of the inequality, yielding $\lfloor log_p(n)\rfloor\geq log_p(n)/2$ which is of course true for $n\geq p$.2012-06-18
  • 0
    @tomasz Thanks, that's a nice way to formalize the intuition.2012-06-18
  • 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
    Because you do not have 50 reputation points yet, [you can only comment on your own questions and answers](http://meta.stackexchange.com/questions/19756/how-do-comments-work/19757#19757); the "add comment" button will only appear for you once you gain 50 points (here is an [explanation of reputation points](http://meta.stackexchange.com/questions/7237/how-does-reputation-work/7238#7238)). If you'd like, I can convert this post to a comment for you.2012-06-18
  • 0
    Fortunately, you should be there, shortly. ^_^2012-06-18
  • 0
    I don't see the Bertrand's postulate argument you are sketching, although I certainly agree with the conclusion. More details?2012-06-18
  • 1
    I'm not sure this proof strategy works, though maybe it's fixable. Bertrand's postulate is consistent with the list of odd primes looking something like: [all odd numbers up to $m$], [all numbers of the form $(2^k)m + 1$]. When we pair up these primes for a certain $n$, the pairs near the middle will both be in the small section, but $n$ itself will be huge.2012-06-18
  • 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
    Thank you. I haven't much experience with the $\psi$-function. So I can follow $\psi(n) = \sum_{p\text{ is prime}} \sum_{\overset{k \in \mathbb{Z}^+}{p^k \leq n}} \log_e(p)$. Maybe it is the right time for my to read sth about that. Thank you anyway.2012-06-18
  • 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} $$