Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 5 down vote accepted

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

share|improve this answer
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$. –  tomasz Jun 18 '12 at 18:15
    
@tomasz Thanks, that's a nice way to formalize the intuition. –  Erick Wong Jun 18 '12 at 18:23
    
I didn't see $\lfloor \log_p(n)\ge \log_p(n)/2$. Now, it is clear. Thank you. –  wieschoo Jun 18 '12 at 18:27
add comment

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?

share|improve this answer
    
Because you do not have 50 reputation points yet, you can only comment on your own questions and answers; the "add comment" button will only appear for you once you gain 50 points (here is an explanation of reputation points). If you'd like, I can convert this post to a comment for you. –  Zev Chonoles Jun 18 '12 at 17:58
    
Fortunately, you should be there, shortly. ^_^ –  Cameron Buie Jun 18 '12 at 18:15
    
I don't see the Bertrand's postulate argument you are sketching, although I certainly agree with the conclusion. More details? –  David Speyer Jun 18 '12 at 18: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. –  Erick Wong Jun 18 '12 at 18:20
    
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.. –  anthonyquas Jun 18 '12 at 18:23
add comment

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

share|improve this answer
    
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. –  wieschoo Jun 18 '12 at 18:25
    
(+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. –  robjohn Jul 4 '13 at 10:51
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.