Let $$ G_n=\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j). $$ What is the asymptotics of $G_n$? (As much of it as it's known to date, preferably.)
$\begingroup$
$\endgroup$
6
-
5$\begingroup$ It is equivalent to $n^2\log n/\zeta(2)$. Proof: fix value $d$ of gcd, then number of pairs with $gcd(i,j)=d$ equals number of coprime pairs in $[1,n/d]^2$, which is equivalent to $(n/d)^2/\zeta(2)$. $\endgroup$– Fedor PetrovAug 15, 2015 at 20:12
-
$\begingroup$ Thus it looks probable on the first glance that estimate of the remainder depends on RH. $\endgroup$– Fedor PetrovAug 15, 2015 at 20:14
-
$\begingroup$ There is a classic estimate $\sum_{i=1}^k \varphi(i)/i = k/\zeta(2) + O(\log k)$. $\endgroup$– Max AlekseyevAug 15, 2015 at 22:39
-
1$\begingroup$ Using $\gcd(i,j) = \sum_{d \mid (i,j)} \phi(d)$, the sum simplifies to $\sum_{d \le n} \phi(d) \lfloor \frac{n}{d} \rfloor ^2 = n^2 \sum_{d \le n} \frac{\phi(d)}{d^2} + O(n^2)$. The sum $\sum_{d \le n} \frac{\phi(d)}{d^2}$ can be evaluated using Tauberian theorems and the identity $\sum_{d \le n} \frac{\phi(d)}{d^s} = \frac{\zeta(s-1)}{\zeta(s)}$, and one gets the main term described by Fedor Petrov. $\endgroup$– Ofir GorodetskyAug 15, 2015 at 23:37
-
1$\begingroup$ Another approach, which is less trivial but more accurate, is rewriting $\sum_{d \le n} \phi(d) \lfloor \frac{n}{d} \rfloor ^2$ as $\sum_{d \le n} (\phi*h)(d)$ where $h(n):=2n-1$. So it follows that your sum is $\sum_{i \le n} a_i$ where $\sum \frac{a_i}{i^s} = \frac{\zeta(s-1)}{\zeta(s)} (2\zeta(s-1) - \zeta(s))$, and again Tauberian theorems regarding Dirichlet series will come in handy, at least for the main term. As Fedor noted, getting the correct error term will require information on zeroes of $\zeta(s)$. $\endgroup$– Ofir GorodetskyAug 15, 2015 at 23:38
|
Show 1 more comment