Is this inequality true? : $$\displaystyle \prod_{i\le \left\lfloor{\frac{n-1}{2}}\right\rfloor}\left\lfloor{\frac{\left\lfloor{\frac{n-1}{2}}\right\rfloor}{i}}\right\rfloor\le \operatorname{lcm}(1,2,\cdots,n)$$ Induction doesn't seem to work here. This is a repost of this problem. I am reposting since nobody wanted to do it at Math SE. The problem comes from my teacher, part of an exam that ended long ago. But he hadn't proved it, and neither has anyone else. I have checked for a few $n$ and it seemed to be true. But since no proof hasn't surfaced yet, I ask the experts. Thanks for any and all help.
$\begingroup$
$\endgroup$
7
-
3$\begingroup$ Up to constant factors / lower-order terms, by Stirling's formula, the left-hand side grows like $e^{n/2}$ and by the Prime Number Theorem the right-hand side grows like $e^n$. Hence for "large" $n$ your inequality holds. To complete the proof, you'd need to work out the gory details about "small" $n$. $\endgroup$– Stefan Kohl ♦Commented Jun 28, 2014 at 17:31
-
5$\begingroup$ Here's a proof with no calculations: First show that $\binom{n}{k}$ divides lcm of $1$, $\ldots$, $n$. Then show that $\binom{n}{\lfloor n/2\rfloor}$ exceeds the LHS. You should get a stronger inequality this way with $\lfloor n/2\rfloor$ instead of $\lfloor (n-1)/2\rfloor$. $\endgroup$– LuciaCommented Jun 28, 2014 at 17:48
-
$\begingroup$ @Lucia: Nice! I made it more complicated, but that's life. $\endgroup$– GH from MOCommented Jun 28, 2014 at 17:53
-
$\begingroup$ @Stefan, without floors I can believe your growth estimates. However, it still seems high. Can you give a good exponential lower bound for the LHS as well? $\endgroup$– The Masked AvengerCommented Jun 28, 2014 at 18:17
-
2$\begingroup$ @GHfromMO: I don't think that's true. It does grow exponentially of course, but like $\exp(Cn/2)$ where $C=\sum_{k=1}^{\infty} (\log k)/(k(k+1))=0.78...$. (Divide the product over $i$ into the ranges $n/(2(k+1)) \le i \le n/(2k)$, and then what I say follows.) $\endgroup$– LuciaCommented Jun 28, 2014 at 18:48
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
Let me outline the proof, it resonates with Stefan Kohl's comment.
It suffices to prove the inequality for $n=2k+1$ odd, since replacing $n$ by $n+1$ for $n$ odd only increases the right hand side. Now a stronger inequality is, for $n=2k+1$, $$ \prod_{i\leq k}\frac{k}{i} \leq \operatorname{lcm}(1,2,\dots,2k+1). $$ Taking natural logarithm of both sides, this becomes $$ \sum_{i\leq k}\log(k/i) \leq \sum_{m\leq 2k+1}\Lambda(m). $$ The left hand side can be estimated from above as $$ \sum_{i\leq k}\log(k/i) < \int_0^k \log(k/x)\,dx= k, $$ so it suffices to prove that $$ k \leq \sum_{m\leq 2k+1}\Lambda(m). $$ The right hand side is the Chebyshev function at $2k+1$, hence it is asymptotically $2k$ by the Prime Number Theorem. The above bound we need is much weaker, and it should follow from the elementary lower bounds (by Chebyshev, Erdős, etc.) that are usually proved in a first course of (analytic) number theory.
Added. As Lucia pointed out, there is a much shorter approach, namely: $$ \prod_{i\leq k}\frac{k}{i} \leq \binom{2k+1}{k}\leq\prod_{p\leq 2k+1}p\leq\operatorname{lcm}(1,2,\dots,2k+1). $$ The middle inequality requires some thought, and I leave it to the reader. Compare with Erdős's proof of Bertrand's postulate.
answered Jun 28, 2014 at 17:52