6
$\begingroup$

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

  • 0
    I 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
  • 0
    You 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 1

3

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.

  • 0
    Thanks! 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
  • 1
    I 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
  • 0
    I think it should be $f(dk,dn)$ instead of $f(dk,nk)$ in the end?2012-10-30