Dirichlet Convolution

$(f\ast g)(n)={\sum }_{d\mid n}f(d)g\left(\frac{n}{d}\right).$

This operation turns the set of arithmetic functions into a commutative ring, and most classical number-theoretic identities are one-line statements in it.

The algebra

• Identity: $ϵ(n)=[n=1]$, so $f\ast ϵ=f$.
• Commutative and associative.
• The convolution of two multiplicative functions is multiplicative.
• Every $f$ with $f(1)\ne 0$ has an inverse under $\ast$.

The standard functions

Symbol	Definition
$ϵ(n)$	$[n=1]$ — the identity
$1(n)$	$1$ for all $n$
$\mathrm{Id}(n)$	$n$
${\mathrm{Id}}_k(n)$	$n^k$
$\mu$	Möbius
$\phi$	Euler totient
$d={\sigma }_0$	number of divisors
$\sigma ={\sigma }_1$	sum of divisors

The identities — all one line each

$$\begin{array}{rlrl}\mu \ast 1& =ϵ& & \text{(the defining property of }\mu )\\ \phi \ast 1& =\mathrm{Id}& & ({\sum }_{d\mid n}\phi (d)=n)\\ 1\ast 1& =d& & \\ \mathrm{Id}\ast 1& =\sigma & & \\ \phi & =\mu \ast \mathrm{Id}& & (\phi (n)={\sum }_{d\mid n}\mu (d)\frac{n}{d})\\ {\mathrm{Id}}_k\ast 1& ={\sigma }_k& & \end{array}$$

Möbius inversion is just: $g=f\ast 1⟺f=g\ast \mu$, which follows immediately from $\mu \ast 1=ϵ$ and associativity.

Seeing these as ring identities makes them memorable — you derive them instead of memorising them.

Computing a convolution

All values up to $N$ — $O(N\log N)$:

vector<long long> conv(N + 1, 0);
for (int i = 1; i <= N; i++)
    for (int j = i; j <= N; j += i)
        conv[j] += f[i] * g[j / i];

The harmonic-series sieve again.

Du’s sieve — prefix sums for huge $N$

To compute $S_f(N)={\sum }_{n\le N}f(n)$ for $N$ up to $10^{11}$, find a $g$ such that $f\ast g$ and $g$ both have easy prefix sums. Then

${\sum }_{n\le N}(f\ast g)(n)={\sum }_{d\le N}g(d)S_f\left(\lfloor \frac{N}{d}\rfloor \right),$

so isolating the $d=1$ term gives the recursion

$g(1)S_f(N)={\sum }_{n\le N}(f\ast g)(n)-{\sum }_{d=2}^{N}g(d)S_f\left(\lfloor \frac{N}{d}\rfloor \right).$

Evaluate with divisor blocks ($O(\sqrt{N})$ distinct values of $\lfloor N/d\rfloor$), memoise the results, and precompute $S_f$ for $n\le N^{2/3}$ with a linear sieve.

Complexity: $O(N^{2/3})$ with the sieve cutoff at $N^{2/3}$.

Target	Choose $g$	Because
$\sum \mu (n)$ (Mertens)	$g=1$	$\mu \ast 1=ϵ$, whose prefix sum is 1
$\sum \phi (n)$	$g=1$	$\phi \ast 1=\mathrm{Id}$, prefix sum $\frac{N(N+1)}{2}$
$\sum \mu (n)n$	$g=\mathrm{Id}$
$\sum \phi (n)n$	$g=\mathrm{Id}$

map<long long,long long> memo;
long long S(long long n) {                        // sum of phi(1..n)
    if (n <= CUT) return pre[n];
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;
    long long res = n % 2 ? (n+1)/2 % MOD * (n % MOD) : n/2 % MOD * ((n+1) % MOD);
    for (long long l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res -= (r - l + 1) * S(n / l);
    }
    return memo[n] = res;
}

The related methods

• Min_25 sieve and Powerful Number sieve — compute $\sum f(n)$ for multiplicative $f$ that is a polynomial on primes, in $O(N^{3/4}/\log N)$ or better. More general than Du’s sieve, considerably more intricate.
• Dirichlet hyperbola method — ${\sum }_{n\le N}(f\ast g)(n)$ in $O(\sqrt{N})$ when both prefix sums are known:
  ${\sum }_{n\le N}(f\ast g)(n)={\sum }_{i\le \sqrt{N}}f(i)S_g(N/i)+{\sum }_{j\le \sqrt{N}}g(j)S_f(N/j)-S_f(\sqrt{N})S_g(\sqrt{N}).$

Why bother

Problems asking for ${\sum }_{n\le 10^{10}}\phi (n)$ or the number of coprime pairs below $10^{11}$ are unreachable by sieving. Du’s sieve makes them routine, and the whole framework rests on recognising the right Dirichlet identity.

See also: Möbius Function · Euler Totient · Divisor Functions