How can we find an asymptotic formula for $$\sum_{\substack{1\leq k\leq n \\ (n,k)=1}}f(k)?$$ Here $f$ is some function and $(n,k)$ is the gcd of $k$ and $n$. I am particularily interested in the case $$\sum_{\substack{1\leq k\leq n \\ (n,k)=1}}\frac{1}{k}.$$ I know about the result $$\sum_{\substack{1\le k\le n\\(n,k)=1}}k=\frac{n\varphi(n)}{2}$$ which was discussed here, but I don't know if I can use it in the case of $f(k)=1/k$.
Asymptotics for sums of the form $\sum \limits_{\substack{1\leq k\leq n \\ (n,k)=1}}f(k)$
-
0I can do something in elementary number theory: let $g(k)=\sum_{0
, we have $\sum_{d\mid n}g(n/d)/d=H_n$, where $H_n=\sum_{k=1}^n1/k$. We can apply Mobius inversion, but it seems no benefit. – 2012-06-29 -
0You can try Dirichlet generating function: let $\tilde G(z)=\sum_{n>0}n^{-z}$, we have $\zeta(z+1)\tilde G(z)=\sum_{n>0}n^{-z}H_n$. It might be useful in analytic number theory. – 2012-06-29
1 Answers
Hint: Try using the fact that $\sum_{d|n} \mu(d)$ is an indicator function for when $n=1$. This allows us to do the following for any function $f$:
$$\sum_{n\leq x}\sum_{k\leq n,\ \gcd (k,n)=1} f(k,n)=\sum_{n\leq x}\sum_{k\leq n} f(k,n) \sum_{d|k, \ d|n} \mu (d) =\sum_{d\leq x} \mu(d) \sum_{n\leq \frac{x}{d}}\sum_{k\leq n} f(dk,nk).$$
This method is very general, and works in a surprisingly large number of situations. I encourage you to try it.
Remark: Using this approach I get $$\sum_{n\leq x}\sum_{k\leq n,\ \gcd(k,n)=1} \frac{1}{k}=\frac{6x}{\pi^{2}}\log x+\left(-\frac{\zeta^{'}(2)}{\zeta(2)^2}+\frac{6\left(\gamma-1\right)}{\pi^{2}}\right)x+O\left(\log^{2}x\right).$$
Edit: I made a slight miscalculation in my remark, missing the factor of $\zeta(2)^2$ in the $\zeta^{'}(2)$ term, and have updated the asymptotic.
-
0Thanks! Just a quick question, what do you mean by $f(k,n)$ and $f(dk,nk)$? – 2012-06-29
-
0@Carolus: $f$ is any two variable function, $f:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{R}$. (Note that 1 variable functions, such as $f(n,k)=\frac{1}{k}$ count as a subset. – 2012-06-29
-
1I think you misunderstood the OP's idea. He want to find the asymptotics for $\sum_{0
. The summation is over $k$, not both $k$ and $n$. – 2012-06-29 -
0@Eric: I ran into some problems with a similar case. $\sum_{2\leq k\leq n,\ (k,n)=1}\frac{n}{k}$. Any thoughts? – 2012-07-02
-
0@Carolus: Frank Science makes a good point, perhaps I have misread your question. Is the summation over both variables, or just over 1 variable? – 2012-07-02
-
0@Eric: When I asked my question I was looking for a technique for _one_ variable, but in the end I needed to sum over both $k$ and $n$, so your method was fine. But now however, I have a hard time modifying it to fit the case I just mentioned, $2\leq k\leq n$. If there is a one-variable method I suppose I'm interested in that as well :) – 2012-07-03
-
0I think it should be $f(dk,dn)$ instead of $f(dk,nk)$ in the end? – 2012-10-30