Dirichlet Convolution

Dirichlet convolution is the algebraic backbone connecting elementary and analytic number theory. It is the mechanism behind Mobius Inversion: because $\mathbf 1 * \mu = \varepsilon$ (a fact you can verify is equivalent to $\sum_{d\mid n}\mu(d)=[n=1]$), any relation $f = g*\mathbf 1$ can be inverted to $g = f*\mu$, giving formulas for $\varphi$, $\mu$, and related sums that appear throughout combinatorics and cryptography (e.g., counting primitive roots or reduced residues). In analytic number theory, convolution is the coefficient-level shadow of multiplying Dirichlet Series and Euler Products: if $F(s)=\sum f(n)n^{-s}$ and $G(s)=\sum g(n)n^{-s}$ converge absolutely, then $F(s)G(s) = \sum_n (f*g)(n) n^{-s}$, which is exactly why the Euler product for the Riemann zeta function $\zeta(s)=\sum n^{-s}$ factors over primes — the convolution identity $\mathbf{1} = \mathbf{1} * \varepsilon$ and multiplicativity of $\tau, \sigma$ translate directly into product formulas. In algorithmic number theory and competitive programming, "sum over divisors" (SOS) convolution techniques for computing $f*g$ for all $n\le N$ in $O(N\log N)$ time (a sieve-like divisor convolution) are used in Project Euler–style computations and in fast Möbius-transform algorithms for subset convolution in combinatorics. In cryptography, Euler's totient — itself built via $\varphi = \mu * N$ — underlies RSA key generation, and multiplicativity of $\varphi$ (a direct corollary of the theorem here) is what makes totient computation from a prime factorization tractable. The ring-theoretic viewpoint, made precise in The Ring of Arithmetic Functions, also underlies formal Dirichlet-series manipulations in random matrix theory and analytic approaches to the distribution of primes.

Ask the tutor: How does the multiplicativity of $f*g$ let us derive a closed formula for $\varphi(n)$ or $\sigma(n)$ directly from the prime factorization of $n$?

Picture the divisors of $n$ arranged on a number line from $1$ up to $n$, paired off as $(d, n/d)$ so that each pair multiplies back to $n$. The convolution $(f*g)(n)$ is a weighted sum over all such pairings, with $f$ evaluated at one member of the pair and $g$ at the complementary member. It is the arithmetic analogue of convolving two sequences in signal processing, except that "shifting" is replaced by "dividing," and the ambient group $(\mathbb{Z},+)$ is replaced by the divisibility poset of $\mathbb{Z}^+$ under multiplication. The reason multiplicativity survives this operation is a lattice fact: if $\gcd(m,n)=1$, every divisor of $mn$ factors uniquely as a divisor of $m$ times a divisor of $n$. So the divisor lattice of $mn$ is literally the product of the divisor lattices of $m$ and of $n$ — a grid, not a tangled mess. Summing $f(d_1d_2)g(mn/(d_1d_2))$ over this grid separates into independent sums over the two factors, exactly mirroring how $f$ and $g$ themselves separate over coprime arguments.

Each cell in that grid is a divisor $d=d_1d_2$ of $12$, uniquely built from a divisor $d_1\in\{1,2,4\}$ of $4$ and $d_2\in\{1,3\}$ of $3$. The convolution sum over all $6$ divisors of $12$ is exactly the double sum over this $3\times 2$ grid, which is the algebraic heart of the theorem below.

Proof technique. This is a direct combinatorial/algebraic proof by reindexing a divisor sum via a bijection induced by coprimality, followed by factoring a double sum into a product of single sums — the standard technique for all multiplicativity-preservation arguments in elementary number theory (it recurs verbatim when proving $\sigma$, $\tau$, $\varphi$, $\mu$ multiplicative, and when proving Dirichlet series multiply as Euler products).

Example 1: Convolving $\mu$ (Möbius function) with $N$ (identity power function), asymmetric and nontrivial. Let $\mu$ be the Möbius function, $\mu(1)=1$, $\mu(n)=(-1)^k$ if $n$ is a product of $k$ distinct primes, and $\mu(n)=0$ if $n$ has a squared prime factor. Let $N(n)=n$ (the identity function on $\mathbb{Z}^+$, viewed as an arithmetic function). Both are multiplicative: $N$ trivially since $N(mn)=mn=N(m)N(n)$ always; $\mu$ is a standard fact we take as known (it will itself be proved multiplicative by an argument identical in spirit to the one above, applied to the specific definition of $\mu$). We compute $(\mu * N)(n)$ for the concrete, asymmetric value $n = 20 = 2^2\cdot 5$. The divisors of $20$ are $1,2,4,5,10,20$. By definition,

Tabulate:

Sum: $20-10+0-4+2+0 = 8$. Now check this against the general identity $\mu * N = \varphi$ (Euler's totient), a classical fact (indeed $\varphi(n)=\sum_{d\mid n}\mu(d)(n/d)$ is one standard formula for $\varphi$). We should get $\varphi(20)$. Since $20=4\cdot 5$ with $\gcd(4,5)=1$ and $\varphi$ multiplicative, $\varphi(20)=\varphi(4)\varphi(5) = 2\cdot 4 = 8$. This matches our direct computation of $8$ exactly, confirming both the arithmetic and the identity $\mu*N=\varphi$ on this nontrivial, non-symmetric case (note $20$ is not a prime power and not squarefree, a genuinely mixed test case). We can also verify multiplicativity of $\mu*N$ itself directly at $n=20=4\cdot5$ using our theorem, since it guarantees $(\mu*N)(20) = (\mu*N)(4)\cdot(\mu*N)(5)$ without recomputing the 6-term sum. Compute the two smaller convolutions:

Then the theorem predicts $(\mu*N)(20)=2\cdot 4=8$, matching the value $8$ computed directly from all six divisors of $20$. This is precisely the content of the Main Theorem verified on real numbers: the six-term sum over $20$'s divisor lattice collapses to the product of a two-term sum (over $4$'s divisors) and a two-term sum (over $5$'s divisors), exactly as the divisor-splitting lemma predicts.

Example 2: A convolution not of two "named" functions — building $\sigma$ from $N$ and the constant function $\mathbf{1}$, tested at $n=45$. Let $\mathbf{1}(n)=1$ for all $n$ (constant function, multiplicative since $1\cdot1=1$ for all coprime pairs), and let $N(n)=n$ as before. Consider $(\mathbf{1}*N)(n) = \sum_{d\mid n} N(d) = \sum_{d\mid n} d = \sigma(n)$, the sum-of-divisors function. This is by definition the classical identity $\sigma = \mathbf{1}*N$. Take the asymmetric test case $n=45 = 9\cdot 5 = 3^2\cdot 5$. Divisors of $45$: $1,3,5,9,15,45$. Direct sum:

Now use the Main Theorem: since $\mathbf{1}$ and $N$ are both multiplicative, $\sigma=\mathbf{1}*N$ is multiplicative, so for the coprime factorization $45 = 9\cdot 5$,

Compute each factor from its own (smaller) divisor sum: divisors of $9$ are $1,3,9$, giving $\sigma(9)=1+3+9=13$; divisors of $5$ are $1,5$, giving $\sigma(5)=1+5=6$. Then

which matches the direct 6-term computation exactly. Notice the saving in labor: instead of summing over all $6$ divisors of $45$, multiplicativity (guaranteed by the theorem, since it applies to any pair of multiplicative functions, not just famous ones) lets us work with the $3$ divisors of $9$ and $2$ divisors of $5$ separately — a $6$-term sum reduced to a $3$-term and a $2$-term sum, a pattern that becomes dramatic for highly composite $n$.