How to prove this inequality: $\sum_{i=1}^{n}\sum_{j=1}^{n}\text{lcm}(i,j)\ge\frac{7}{8}n^3$?

Question

Let $n$ be postive integers. Show that $$\sum_{i=1}^{n}\sum_{j=1}^{n}[i,j]\ge\dfrac{7}{8}n^3\,,$$ where $[a,b]$ denote the least common multiple of $a$ and $b$.

For $n=1,2,3 $, it is clear. How to prove this inequality? Thanks!

Answer 1

Let $S_n:=\sum\limits_{i=1}^n\,\sum\limits_{j=1}^n\,\text{lcm}(i,j)$. We have $S_1=1\geq \dfrac{7}{8}\cdot 1^3$ and $S_2=7\geq \dfrac{7}{8}\cdot 2^3$. Assume that $n>2$ is an integer such that $$S_{n-1}\geq \dfrac{7}{8}\,(n-1)^3\,.$$ Then, $$S_{n}-S_{n-1}=n+2\,\sum_{k=1}^{n-1}\,\text{lcm}(k,n)\,.$$ Since $n>3$, $$S_n-S_{n-1}\geq n+2\,\big(\text{lcm}(n-1,n)+\text{lcm}(n-2,n)\big)\,.$$ We see that $\text{lcm}(n-1,n)=(n-1)n$ and $\text{lcm}(n-2,n)\geq \dfrac{(n-2)n}{2}$. Ergo, $$S_n-S_{n-1}\geq n+2\,\left((n-1)n+\frac{(n-2)n}{2}\right)=3n^2-3n\,.$$ For $n>2$, we have $$3n^2-3n\geq 3\cdot 3^2-3\cdot 3=18>7;$$ therefore, $$3n^2-3n> \frac{7}{8}\,(3n^2-3n+1)=\frac{7}{8}\,\big(n^3-(n-1)^3\big)\,.$$ Consequently, $$S_n>\frac{7}{8}\,\big(n^3-(n-1)^3\big)+S_{n-1}\geq \frac{7}{8}\,\big(n^3-(n-1)^3\big)+\frac{7}{8}\,(n-1)^3=\frac{7}{8}\,n^3\,.$$ By induction, $$\sum_{i=1}^n\,\sum_{j=1}^n\,\text{lcm}(i,j)=S_n\geq \frac{7}{8}\,n^3$$ for every positive integer $n$. The equality holds if and only if $n=2$.

Let $H_n:=\sum\limits_{k=1}^n\,\dfrac1k$ for each positive integer $n$. Apparently, we also have $$S_n\geq 2\,\sum_{k=1}^n\,k^2\,H_k-\frac{n(n+1)(4n-1)}{6}\,.$$
The inequality above becomes an equality if and only if $n=1$ and $n=2$.

If $\gamma$ is the Euler–Mascheroni constant, then using $H_n>\ln(n)+\gamma$ for every positive integer $n$ yields $$\begin{align}S_n&\geq 2\,\int_0^n\,x^2\,\big(\ln(x)+\gamma)\,\text{d}x-\frac{n(n+1)(4n-1)}{6} \\&=\dfrac{2n^3}{9}\,\big(3\ln(n)-1\big)+\frac{2\gamma n^3}{3}-\frac{n(n+1)(4n-1)}{6}\,.\end{align}$$ I am going to predict again as I have done in many threads that $$S_n=\alpha n^3\ln(n)+\beta n^3+o(n^3)\,,$$ where $\alpha$ and $\beta$ are constants. (Clearly, $\alpha\geq \frac{2}{3}$.) However, I can be wrong about this. I have not tried to find an upper bound of $S_n$ that is of the form $\mathcal{O}\big(n^3\,\ln(n)\big)$. (The OP posted another question regarding an upper bound.)