Suppose that $f: \mathbb{N} \to \mathbb{C}$ is a multiplicative function; i.e., $f(mn) = f(m)f(n)$ if $m, n$ are coprime. I'm interested in efficiently calculating sums of the form $\sum_{k=1}^N f(k)$, where by efficiently I mean in $\tilde{o}(N)$ operations. (Tildes above $O$ and $o$ indicate that we are ignoring logarithmic factors.)
This does not seem to be possible for all multiplicative functions. For example, if we let $f(2^k) = 0$ and $f(p^k) = (-1)^{(p-1)/2}$ for $p>2$, then it seems that computing $\sum_{k=1}^N f(k)$ is at least as hard as determining how the primes in $[N/2, N]$ are distributed among the residue classes $\{1, 3\}$ modulo $4$, and I have no reason to think that this is doable in substantially fewer than $\tilde{O}(N)$ operations. (I'm not sure if this precise example works, but I think that something along these lines should be as hard as exactly counting primes of some form in $[N/2,N]$, and I think that exactly counting such primes is hard to do efficiently.)
However, efficiently computing these sorts of sums is certainly possible for some multiplicative functions. For example, it's well-known that if $f(n) = d(n) = \sum_{d \mid n} 1$, so that $f(p^k) = k + 1$, we have $$\sum_{k=1}^N d(k) = 2\sum_{j=1}^{\lfloor\sqrt{N}\rfloor} \left\lfloor\frac{N}{j}\right\rfloor - \left\lfloor\sqrt{N}\right\rfloor^2.$$ This computation can clearly be performed in $\tilde{O}(\sqrt{N})$ operations.
Similarly, if $f(n) = \sigma_1(n) = \sum_{d \mid n} d$, so that $f(p^k) = \frac{p^{k+1}-1}{p-1}$, we have $$\sum_{k=1}^N \sigma_1(k) = \sum_{j_1 = 1}^{\lfloor\sqrt{N}\rfloor} j_1\left\lfloor\frac{N}{j_1}\right\rfloor + \sum_{j_2 = 1}^{\lfloor\sqrt{N}\rfloor} \frac{1}{2}\left\lfloor\frac{N}{j_2}\right\rfloor\left(\left\lfloor\frac{N}{j_2}\right\rfloor+1\right) - \frac{\lfloor\sqrt{N}\rfloor^2\left(\lfloor\sqrt{N}\rfloor+1\right)}{2},$$ and more complicated expressions exist for all $\sigma_e(n)$ (at least for non-negative integers $e$). So again we have an algorithm that takes $\tilde{O}(\sqrt{N})$ operations.
(In general I see no reason to expect "generic" algorithms faster than $\tilde{O}(\sqrt{N})$, simply because computing $f(m)$ for certain $m \approx N$ should involve knowing the primes up to at least $\sqrt{N}$.)
I have several related questions:
What other common multiplicative functions admit efficient algorithms for interval sums? For example, can we efficiently compute $\sum_{k \le N} \mu(k)$ or $\sum_{k \le N} \phi(k)$? We have the easy re-write $$\sum_{k \le N} \phi(k) = \frac{1}{2} \sum_{g \le N} \mu(g) \left\lfloor\frac{n}{g}\right\rfloor \left(\left\lfloor\frac{n}{g}\right\rfloor + 1\right),$$ but it's not clear to me how to speed this up substantially. (If I haven't screwed up the details, this formula seems to indicate that any efficient algorithm for interval sums of $\mu(n)$ would give an efficient algorithm for interval sums of $\phi(n)$, with the reverse implication also holding provided we continue to ignore log factors.)
Suppose I specify an arbitrary multiplicative function $f(n)$ at every prime power $p^k$ by some "formula" $v(p,k)$. Suppose furthermore that it is easy (i.e., takes $\tilde{O}(1)$ operations) to compute the "naive sum" $$V(N,k) = \sum_{1 \le n \le N} v(n,k), $$ where we don't take into account the factorization properties of $n$ in computing the naive sum. Is it "automatic" that an efficient algorithm for interval sums of $f(n)$ exists? What if we restrict $v(p,k)$ to be a polynomial in $k$, $p$, and $p^k$ (or, more boldly, a polynomial in $k, p, p^2, \cdots, p^k$)?
I have no reason to suspect this is the case, but it seems like there might be some complicated inclusion-exclusion involving $V(n,k)$ terms that I haven't yet figured out which would give an efficient algorithm. Note that if $v(p,k) = k + 1$ or $v(p,k) = 1 + p^e + \cdots + p^{ke}$ we recover the cases discussed above.
If I have an efficient algorithm for interval sums of $f$ and $g$, can I find an efficient algorithm for interval sums of the Dirichlet convolution $f * g$?
Can we make rigorous the idea that there is a natural $\tilde{O}(\sqrt{N})$ lower bound for algorithms for interval sums of multiplicative functions?