Límites de una suma de gcd's

Question

¿Existe un número real positivo $C$ y un número entero positivo $M$ tal que para todo $n > M$ que tenemos: $$\sum_{i=1}^n\sum_{j=1}^n\gcd (i, j)\ge Cn^2 \log n$$

Esto apareció originalmente como un problema de la Olimpiada en el caso de $4n^2$ en el lado derecho. Este caso es mucho más sencillo; basta con dejar que $i$ sólo se extienden sobre valores primos y se obtiene rápidamente una $\omega \left ( n^2 \log \log \frac{n}{\log n} \right )$ atado si no la he cagado. La motivación para el límite anterior se deriva del hecho de que $$\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}$$ Así que tenemos: $$\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$$

Sin embargo, este razonamiento es bastante poco riguroso. ¿Alguien tiene alguna idea de cómo demostrar rigurosamente este límite? Por supuesto, demostrar que la suma de hecho se "acerca" a $\frac{6}{\pi^2} n^2 \log n$ como $n \to \infty$ sería aún mejor.

Answer 1

Lema: Tenemos que $$\sum_{d\leq x}\frac{\phi(d)}{d^{2}}=\frac{6}{\pi^{2}}\log x+O(1).$$ Esto se deduce del hecho de que $\sum_{n\leq x}\phi(n)=\frac{3}{\pi^2}x^2 +O(x\log x)$ junto con la suma parcial.

Utilizando la identidad de convolución $\left(1*\phi\right)(n)=n$ vemos que $$\sum_{i,j\leq x}\gcd\left(i,j\right)=\sum_{i,j\leq x}\sum_{d|i,j}\phi(d),$$ y cambiando el orden de la suma se obtiene $$\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)$$ Ampliación $\left[\frac{x}{d}\right]=\frac{x}{d}-\left\{ \frac{x}{d}\right\},$ llegamos a la asíntota deseada $$\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).$$

Utilizando la identidad explícita de la ecuación $(1)$ con mucho trabajo podemos derivar el segundo término en la expansión asintótica.

Answer 2

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