Bounds on a sum of gcd's

Question

Does there exist a positive real number $C$ and a positive integer $M$ such that for all $n > M$ we have: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j)\ge Cn^2 \log n$$

This originally appeared as an Olympiad problem in the case of $4n^2$ on the RHS. This case was much simpler; simply let $i$ only range on primes values and one quickly derives a $\omega \left ( n^2 \log \log \frac{n}{\log n} \right )$ bound if I didn't mess up. The motivation for above bound is derived from the fact that $$\sum_{j=1}^n \gcd(i,j) \approx \frac{n}{i} \sum_{d|i} \varphi(i/d) \cdot d \approx n \cdot \tau(i) \cdot \frac{6}{\pi^2}$$ So we have: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j) \approx \frac{6n^2}{\pi^2} \sum_{i=1}^n \frac{1}{i} \approx \frac{6}{\pi^2} n^2 \log n$$

However, this is pretty unrigorous reasoning. Does anybody have any ideas as to how to rigorously prove this bound? Of course, showing that the sum in fact gets "close" to $\frac{6}{\pi^2} n^2 \log n$ as $n \to \infty$ would be even better.

Answer 1

\begin{align} \sum_{i=1}^{n}{\sum_{j=1}^{n}{\gcd (i, j)}}& =2\sum_{1 \leq j \leq i \leq n}{\gcd (i, j)}-\sum_{i=1}^{n}{\gcd(i, i)} \\ & =2\sum_{i=1}^{n}{\sum_{d \mid i}{\varphi{\left(\frac{i}{d}\right)}d}}-\frac{n(n+1)}{2} \\ & =2\sum_{d=1}^{n}{d\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}{\varphi{(k)}}}-\frac{n(n+1)}{2} \\ & =2\sum_{d=1}^{n}{d(\frac{3}{\pi^2}\left\lfloor \frac{n}{d}\right\rfloor^2+O(\left\lfloor \frac{n}{d}\right\rfloor \log(\left\lfloor \frac{n}{d}\right\rfloor)))}+O(n^2) \\ & =2\sum_{d=1}^{n}{d((\frac{3}{\pi^2}(\frac{n}{d})^2+O(\frac{n}{d}))+O(\frac{n}{d} \log (\frac{n}{d})))}+O(n^2) \\ & =\frac{6n^2}{\pi^2}\sum_{d=1}^{n}{\frac{1}{d}}+O(n^2)+O(n^2\log(n)-n\sum_{d=1}^{n}{\log(d)})+O(n^2) \\ & =\frac{6n^2}{\pi^2}(\log n+O(1))+O(n^2)+O(n^2\log(n)-n(n \log n-n+O(1))) \\ & =\frac{6}{\pi^2}n^2\log n+O(n^2) \end{align}

Answer 2

Lemma: We have that $$\sum_{d\leq x}\frac{\phi(d)}{d^{2}}=\frac{6}{\pi^{2}}\log x+O(1).$$ This follows from the fact that $\sum_{n\leq x}\phi(n)=\frac{3}{\pi^2}x^2 +O(x\log x)$ along with partial summation.

Using the convolution identity $\left(1*\phi\right)(n)=n$, we see that $$\sum_{i,j\leq x}\gcd\left(i,j\right)=\sum_{i,j\leq x}\sum_{d|i,j}\phi(d),$$ and switching the order of summation yields $$\sum_{d\leq x}\phi(d)\sum_{i,j\leq\frac{x}{d}}1=\sum_{d\leq x}\phi(d)\left[\frac{x}{d}\right]^{2}.\ \ \ \ \ \ \ \ \ \ \ \ (1)$$ Expanding out $\left[\frac{x}{d}\right]=\frac{x}{d}-\left\{ \frac{x}{d}\right\},$ we arrive at the desired asymptotic $$\sum_{i,j\leq x}\gcd\left(i,j\right)=x^{2}\sum_{d\leq x}\frac{\phi(d)}{d^{2}}+O(x^2)=\frac{6}{\pi^{2}}x^2\log x+O(x^2).$$

Using the explicit identity in equation $(1)$, with a lot of work we can derive the second term in the asymptotic expansion.