Euler phi function: $\sum_{n=1}^{N}\sum_{d\mid n}d\cdot\phi(d)$

I am trying to find the value of $$\sum_{n=1}^{N}\sum_{d|n}d*\phi(d)$$ Is there a method to evaluate this for large N? $\phi(d)$ is the Euler phi function.

Solution 1:

This one can be treated using either the Wiener-Ikehara theorem, which gives the dominant asymptotics, or Mellin-Perron, which predicts additional terms of the expansion. In either case we need the appropriate Dirichlet series.

To find this series recall first that $$\sum_{d|n} \varphi(d) = n$$ which implies that $$\sum_{q\ge 1} \frac{\varphi(q)}{q^s} = \frac{\zeta(s-1)}{\zeta(s)}.$$

Introduce $$a(n) = \sum_{d|n} d \times \varphi(d) = n \sum_{d|n} \varphi(d) \times \left(\frac{d}{n}\right) = n \sum_{d|n} \varphi(d) \times \left(\frac{n}{d}\right)^{-1}.$$ This yields that $$\sum_{q\ge 1} \frac{a(n)/n}{n^s} = \frac{\zeta(s-1)}{\zeta(s)} \zeta(s+1).$$ which finally produces $$\sum_{q\ge 1} \frac{a(n)}{n^s} = \frac{\zeta(s-2)}{\zeta(s-1)} \zeta(s).$$ Call this $L(s).$ The dominant pole of $L(s)$ is at $s=3.$

By the Wiener-Ikehara theorem we thus have $$\sum_{q\le N} a(q) \sim \frac{\zeta(3)}{\zeta(2)} \frac{N^3}{3} = \frac{6}{\pi^2} \zeta(3) \frac{N^3}{3}.$$

Using Mellin-Perron we can predict another term. The Mellin-Perron integral is $$\frac{1}{2\pi i} \int_{7/2-i\infty}^{7/2+i\infty} L(s)\frac{N^s}{s} ds.$$

Shifting this integral to the left we obtain the term for the pole at $s=3$ plus an additional term from the pole at $s=1,$ which is $$\frac{-1/12}{-1/2} \frac{N}{1} = \frac{1}{6} N$$ for our final formula $$\sum_{q=1}^N a(q) \sim \frac{2}{\pi^2} \zeta(3) N^3 + \frac{1}{6} N + \frac{1}{2} \sum_{d|N} d \times \varphi(d).$$

The relative error in percent of this approximation is $0.186\%$ for $N=20$. It is $0.0275\%$ for $N=2000$ and $0.000128\%$ for $N=20000.$

Note. What we have not included here is the contribution from the non-trivial zeros of the Riemann zeta function, which (assuming they are simple) is $$\sum_{\rho} \frac{1}{\zeta'(\rho)} \times \zeta(-1+\rho) \zeta(1+\rho) \frac{N^{1+\rho}}{1+\rho}.$$

Solution 2:

Another, more elementary derivation of the same result is given here: J. Sándor and A. V. Kramer. Über eine Zahlentheoretische Funktion. Mathematica Moravica, 3:53–62, 1999. URL: http://www.moravica.ftn.kg.ac.rs/Vol_3/10-Sandor-Kramer.pdf.

Here is a comment to the previous answer, but I don't have enough "reputation" to write a comment:

The asymptotic "final formula" of Marko Riedel's answer does not include an explicit error term, and I did not follow the derivation, but in any case, the linear term N/6 does not make sense to me. The summand $a(N)$ of the series fluctuates in a quadratic range. For example, when $N$ is a prime, $a(N)=N(N-1)+1$; when $N$ is a power of 2, $a(N)=(2N^2+1)/3$. Thus, when writing an approximation to $\sum_{q=1}^N a(q)$ [or, bringing the last term on the right side to the left as in the "final formula", to $\sum_{q=1}^{N-1} a(q) + 1/2\cdot a(N)$] by a smooth function like $CN^3$ or $C_1N^3+C_2N$, one has to expect a quadratic error term $O(n^2)$, which would swallow any linear or lower-order terms. (Otherwise, by subtracting the approximation for $N-1$ from the approximation for $N$, one could predict $a(N)$ [or $a(N)+a(N-1)$] to better than quadratic order.)