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.)

  • 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$ Aug 15, 2015 at 20:12
  • $\begingroup$ Thus it looks probable on the first glance that estimate of the remainder depends on RH. $\endgroup$ Aug 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$ Aug 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$ Aug 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$ Aug 15, 2015 at 23:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.