# An upper bound to sum of ratios of gcd's and products

It seems like the sum $S(n)$ should be possible to upperbound by an expression of the form ${\mathcal O}(n^a\cdot \log^b(n))$ as $n \rightarrow \infty$: $$S(n)\stackrel{\triangle}{=}\sum_{1\leq x \neq y\leq n} \frac{gcd(x,y)^2}{x y}.$$ Any pointers, ideas, appreciated. Since $gcd(x,y) \leq \min(x,y)$ an upper bound is given by $$S(n) \leq \sum_{1\leq x \neq y\leq n} \frac{\min(x,y)^2}{x y} = 2 \sum_{1\leq x < y\leq n} \frac{x}{y}$$ which can be rewritten as $$S(n) \leq 2 \sum_{1\leq x \leq n-1} x \sum_{x+1 \leq y \leq n} \frac{1}{y} = 2 \sum_{1\leq x \leq n-1} x (H(n)-H(x)),$$ where $H(n)$ denotes the harmonic sum. This then gives $$S(n) \leq 2 H(n) \left[\sum_{1\leq x \leq n-1} x\right] -2 \left[\sum_{1\leq x \leq n-1} x H(x)\right]$$ or $$S(n) \leq n(n-1) H(n) - 2 (1\times H(1)+2 \times H(2)+\cdots+(n-1) \times H(n-1))$$ or to a first order approximation $$S(n) \leq n(n-1) H(n) - 2 \sum_{1\leq x \leq n-1} x \log x \approx n^2 \log n - 2 (1+\sum_{2\leq x \leq n-1} x \log x) .$$ An application of the arithmetic geometric mean inequality an Stirling seems to give an estimate of $(n-1)^2$ for the subtracted sum while an integral approximation says that the subtracted sum is ${\cal O}(n^2 \log n)$ which would cancel the first term! Using the estimate $\log n + \gamma$ for the Harmonic sum then leaves us with $S(n) \leq \gamma n(n-1).$

Is there a more accurate estimate?

• More easily, fixing y and summing 2x/y for x from 1 to y-1 gives y-1, leading to n choose 2 as an upper bound on S(n). Lucia's approach of summing on lines (at,bt) does lead to a better estimate, both on upper and lower bounds. Feb 15 '14 at 18:42

Suppose that $x <y$. Write $x=ga$ and $y=gb$ where $g$ is the gcd of $x$ and $y$; thus $a$ and $b$ are coprime with $a<b$, and $g\le n/b$. So $$S(n) = 2 \sum_{\substack{{a<b \le n} \\ {(a,b)=1}}} \frac{1}{ab} \sum_{g\le n/b} 1 \le 2\sum_{\substack{{a<b\le n} \\ {(a,b)=1}}} \frac{1}{ab} \frac{n}{b}.$$ Now ignore the condition that $(a,b)=1$, getting (using $\sum_{b>a} 1/b^2 \le 1/a$) $$S(n) \le 2n \sum_{a\le n} \frac{1}{a} \sum_{a<b\le n} \frac{1}{b^2} \le 2n\sum_{a\le n} \frac{1}{a^2} \le \frac{\pi^2}{3} n.$$ With more effort you can prove that $S(n) \sim Cn$ for some constant $C$.
Edit: The OP Kodlu noted that numerically the constant $C$ seemed to be $2$, which was surprising to me. So here's a sketch as to why the constant comes out to be $2$. The argument above is pretty accurate, and is essentially an asymptotic. Thus from above one finds that $$C = 2\sum_{\substack{{1\le a<b } \\ {(a,b)=1} }} \frac{1}{ab^2}.$$ Now use Mobius inversion $\sum_{d|(a,b)} \mu(d) =1$ if $(a,b)=1$ and zero otherwise. Thus, with $a=dr$ and $b=ds$,
$$C= 2\sum_{1\le a<b} \frac{1}{ab^2} \sum_{d|(a,b)} \mu(d) =2 \sum_{d=1}^{\infty} \frac{\mu(d)}{d^3} \sum_{1\le r<s} \frac{1}{rs^2}.$$ The sum over $d$ is $1/\zeta(3)$, and the sum over $r$ and $s$ is the multizeta value $\zeta(2,1)$ which Euler showed equals $\zeta(3)$. Thus $C=2$ and $S(n) \sim 2n$ (and in fact the argument above gives this as an upper bound always, as seen in the numerics).
• @kodlu: That's very interesting and surprising to me. But I see now that the constant is indeed $2$ by Euler's formula that the multizeta value $\zeta(2,1)$ equals $\zeta(3)$. I'll edit my answer to include this. Feb 17 '14 at 1:04