# Bounds on a sum of gcd's

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.

-

Wow, very nice! I feel somewhat silly for not noticing breaking it up into a sum of $1 \le j \le i \le n$, but this is very elegant and answers my question perfectly. – dinoboy Mar 10 '13 at 8:58
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.