I'm trying to estimate asymptotically the following sums: $$ S_1(m, n) = \sum_{1\leq i \leq n, (m,i)=1}{\frac{1}{i}} $$

$$ S_2(n) = \sum_{i=1}^n{i\phi(i)}, $$

where $(m,i) = GCD(m,i)$, and $\phi(i)$ is the Euler totient function of $i$.

I would be grateful for any hints.

  • $\begingroup$ Use Möbius inversion/inclusion-exclusion on $$\sum_{1 \leqslant i \leqslant n} \frac{1}{i} = \sum_{d \mid m} \sum_{\substack{1 \leqslant i \leqslant n \\ (m,i) = d}} \frac{1}{i}.$$ $\endgroup$ – Daniel Fischer Jul 27 '17 at 13:15
  • $\begingroup$ @DanielFisher, I am confused how Möbius inversion could be used here. The left part of your equation depends on $n$ and the first sum of the right part is among $d|m$ (not $d|n$). In addition the sum $$\sum_{1 \leq i \leq n \\ (m,i)=d}{\frac{1}{i}}$$ is a function depending on 3 variables: $m, n, d$. $\endgroup$ – foveo Jul 27 '17 at 15:56
  • $\begingroup$ View it as an inclusion-exclusion problem. Consider $n$ fixed. Partition the set $A = \{1, 2, \dotsc, n\}$ into the sets $A_d = \{ i \in A : (m,i) = d\}$. $\endgroup$ – Daniel Fischer Jul 27 '17 at 16:02
  • $\begingroup$ @DanielFischer I have posted this argument below. $\endgroup$ – Marko Riedel Jul 27 '17 at 22:08

For the first sum, use inclusion-exclusion and consider the Hasse diagram of the divisor poset of $m$, with the weights of the nodes $d|m$ being $\mu(d).$ A node $d$ here represents the set of values $q\le n$ that are multiples of $d.$ A value $q$ appears in all nodes $d|m$ where $d|q$ and hence the total weight of a value $q$ is

$$\sum_{d|(q,m)} \mu(d).$$

This is one when $(q,m)=1$ and zero when $(q,m)\gt 1$ which means that these weights are an exact representation of the problem. Observe that the contribution from node $d$ is

$$\frac{1}{d} H_{\lfloor n/d\rfloor}$$

and hence

$$S_1(m, n) = \sum_{d|m} \mu(d) \frac{1}{d} H_{\lfloor n/d\rfloor}.$$

Using the dominant two terms $H_n \sim \log n + \gamma$ this becomes

$$(\log n + \gamma) \sum_{d|m} \mu(d) \frac{1}{d} - \sum_{d|m} \mu(d) \frac{1}{d} \log d.$$

Now for the asymptotics with respect to $n$ the first is

$$(\log n + \gamma) \prod_{p|m} \left(1-\frac{1}{p}\right)$$

and we find for the leading two terms (logarithm followed by next term, a constant)

$$\bbox[5px,border:2px solid #00A000]{ \frac{\varphi(m)}{m} \log n + \frac{\varphi(m)}{m} \gamma - \sum_{d|m} \mu(d) \frac{1}{d} \log d.}$$

which is precisely as it ought to be (initial term may be conjectured by inspection). Note that additional terms from the expansion of $H_n$ like $H_n \sim \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2}$ only contribute lower order terms, i.e. terms in inverse powers of $n$ times constants dependent on $m,$ e.g. the next term happens to be zero:

$$\sum_{d|m} \mu(d) \frac{1}{d} \frac{1}{2n/d} = \frac{1}{2n} \sum_{d|m} \mu(d) = 0$$

and the one after that is

$$\sum_{d|m} \mu(d) \frac{1}{d} \frac{1}{12n^2/d^2} = \frac{1}{12n^2} \sum_{d|m} \mu(d) d.$$

Fixing $m$ yields a bona fide asymptotic expansion in $n$.

  • 1
    $\begingroup$ Very well explained. A minuscule nitpick, though: the next term is zero only if $m > 1$, which isn't explicitly demanded in the question. But for $m = 1$ we just have $S_1(1,n) = H_n$ anyway, so then it's trivial. $\endgroup$ – Daniel Fischer Jul 27 '17 at 22:42
  • $\begingroup$ Thank you for the kind remark. Good point about $m=1.$ $\endgroup$ – Marko Riedel Jul 27 '17 at 22:45
  • $\begingroup$ We also use that $\chi(n) = 1_{gcd(n,m)=1}$ is a $m$-periodic Dirichlet character with $L(s,\chi) = \sum_{n=1}^\infty \chi(n) n^{-s} = \zeta(s)\prod_{p| m} (1-p^{-s})$ thus $\sum_{n \le x} \frac{\chi(n)}{n} \sim Res(L(s,\chi),1) \sum_{n \le x} \frac{1}{n} \sim \log x \ \ \frac{\phi(m)}{m}$. $\endgroup$ – reuns Jul 30 '17 at 0:46

You can use that $\frac{\phi(n)}{n} = \sum_{d | n} \frac{\mu(d)}{d}$ to obtain $$\sum_{n \le x} \frac{\phi(n)}{n} = \sum_{d \le x} \frac{\mu(d)}{d} \lfloor x/d \rfloor= x \sum_{d \le x} \frac{\mu(d)}{d^2} + \mathcal{O}(\sum_{d \le x} |\mu(d)/d|)= \frac{x}{\zeta(2)}+ \mathcal{O}(\log x)$$ which implies by summation by parts $$\sum_{n \le x} n \phi(n) = x^2\sum_{n \le x} \frac{\phi(n)}{n}+\sum_{n \le x-1} (\sum_{m \le n} \frac{\phi(m)}{m})(n^2-(n+1)^2) = \frac{x^3}{3 \zeta(2)} + \mathcal{O}(x^2 \log x)$$

  • $\begingroup$ Thanks for your answer, it is very helpful for me. I wish I could mark two comments as answers. $\endgroup$ – foveo Aug 1 '17 at 21:08
  • $\begingroup$ @foveo what is it useful for ? $\endgroup$ – reuns Aug 2 '17 at 12:26
  • $\begingroup$ I am trying to estimate asymptotically the number of different \{0, 1\}-valued functions over integer grid which can be defined by a system of two linear inequalities. Eventually I came up with several sums involving $\phi(n)$. $\endgroup$ – foveo Aug 14 '17 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.