Dirichlet Convolution

Dirichlet convolution is a binary operation on arithmetic functions. It is commutative, associative, and distributive over addition and has other important number-theoretical properties. It is also intimately related to Dirichlet series. It is a useful tool to construct and prove identities relating sums of arithmetic functions.

Definition

An arithmetic function is a function whose domain is the natural numbers (positive integers) and whose codomain is the complex numbers.

Suppose $f, g$ are arithmetic functions. Then the Dirichlet convolution of $f$ and $g$ , denoted by $f * g$ , is the following arithmetic function:

$\displaystyle (f * g)(n) = \sum_{d | n} f(d) g \left( \frac{n}{d} \right),$

where the sum is taken over all positive divisors $d$ of $n$ .

Consider the identity function $I(n) = n$ for all natural numbers $n$ , and the constant function $\mathbf{1}(n) = 1$ for all natural numbers $n$ . Their convolution is

$\displaystyle\begin{aligned} (I * \mathbf{1})(n) &= \sum_{d | n} I(d) \mathbf{1} \left( \frac{n}{d} \right) \\ &= \sum_{d | n} d \cdot 1 \\ &= \sum_{d | n} d = \sigma(n) \end{aligned}$ $\big($ for a definition of $\sigma(n)$ , see below $\big).$ We write this as $I*\mathbf{1} = \sigma$ .

Properties

Let $f,g,h$ be arithmetic functions. Then we have the following:

Convolution is commutative: $f * g = g * f$ .
It is associative: $(f * g) * h = f * (g * h)$ .
It is distributive over addition: $f * (g + h) = (f * g) + (f * h)$ .
It has an identity: define $e(n) = \big\lfloor \frac1{n} \big\rfloor = \begin{cases} 1&\text{if } n=1 \\ 0&\text{otherwise.} \end{cases}$ Then $e*f = f*e = f$ for any $f$ .
The (Dirichlet) convolution of two multiplicative functions is again multiplicative.

So the set of arithmetic functions forms a ring under the operations addition and convolution, and the subset of multiplicative functions is a subring.

Important Functions for Dirichlet Convolution

Some arithmetic functions are important in Dirichlet convolutions since taking the convolution of two of them generally gives another of these special functions.

Definition	Explanation
$\mathbf{1}(n) = 1$	Constant function that returns 1 no matter its argument. This function is completely multiplicative.
$I(n) = n$	Identity function that returns its argument. This function is completely multiplicative.
$I_k(n) = n^k$	Function that returns its argument raised to the $k^\text{th}$ power; $I_1= I$ and $I_0=\mathbf{1}.$
$e(n) = \begin{cases} 1 &\text{if } n=1 \\ 0 &\text{if } n > 1 \end{cases}$	Multiplicative identity function (not to be confused with $I$ ) that returns 1 if its argument is 1, and otherwise returns 0. This function is completely multiplicative.
$d(n) = \sum_{d\|n} 1$	Divisor function that returns the number of positive divisors of $n$ . This function is multiplicative.
$\sigma(n) = \sum_{d\|n} d$	Divisor sum function that returns the sum of the positive divisors of $n$ . This function is multiplicative.
$\sigma_k(n) = \sum_{d\|n} d^k$	Function that returns the sum of each of the positive divisors of $n$ raised to the $k^\text{th}$ power; $\sigma_1$ is $\sigma$ and $\sigma_0$ is $d$ . This function is multiplicative.
$\varphi$	Euler's totient function that returns the number of positive integers $d \le n$ such that $d,n$ are relatively prime. This function is multiplicative.
$\lambda(n) = (-1)^{\Omega(n)}$	Liouville function; the exponent $\Omega(n)$ is the number of prime divisors of $n$ , counting multiplicity. This function is multiplicative.
$\mu(n) = \begin{cases} (-1)^{\Omega(n)} &\text{if \$n\$ is square-free} \\ 0 &\text{otherwise} \end{cases}$	Möbius function that is similar to the Liouville function except that it returns 0 if the argument is not squarefree (divisible by a perfect square other than 1). This function is multiplicative.

Here are some results about the convolution of these functions:

$\mathbf{1} * \mathbf{1} = d$ . This is immediate from the definition.
$I * \mathbf{1} = \sigma$ . Proved above; more generally, $I_k * \mathbf{1} = \sigma_k$ .
$\varphi * \mathbf{1} = I$ . For a proof, see the Bijective Proofs wiki.
$\mu * \mathbf{1} = e$ . For a proof, see Möbius Function.

Dirichlet Inverse

The Dirichlet inverse of an arithmetic function $f$ is another arithmetic function $g$ satisfying $f * g = e$ . As it turns out, every arithmetic function $f$ that satisfies $f(1) \neq 0$ has a Dirichlet inverse.

The Dirichlet inverse $g$ of $f$ is given by the following: $g(1) = \frac{1}{f(1)}$ , and for all positive integers $n > 1$ ,

$\displaystyle g(n) = \frac{-1}{f(1)} \sum_{d|n, d<n} f\left( \frac{n}{d} \right) g(d) ,$

where the sum runs over all proper positive divisors $d$ of $n$ .

First, consider when $n = 1$ . Write

$\displaystyle\begin{aligned} e(1) &= (f * g)(1) \\ 1 &= \sum_{d|1} f\left( \frac{1}{d} \right) g(d) \\ &= f(1) g(1) \\ g(1) &= \frac{1}{f(1)}. \end{aligned}$

The first equality comes from the definition of $g$ being the Dirichlet inverse of $f$ ; the third equality comes because there is only a single positive divisor of 1.

Now we consider $n > 1$ . Write

$\displaystyle\begin{aligned} e(n) &= (f * g)(n) \\ 0 &= \sum_{d|n} f \left( \frac{n}{d} \right) g(d) \\ &= f(1) g(n) + \sum_{d|n, d<n} f \left( \frac{n}{d} \right) g(d) \\ -f(1) g(n) &= \sum_{d|n, d<n} f \left( \frac{n}{d} \right) g(d) \\ g(n) &= \frac{-1}{f(1)} \sum_{d|n, d<n} f \left( \frac{n}{d} \right) g(d). \end{aligned}$

The second equality is because convolution is commutative. The fourth equality separates the case $d = n$ from the remaining cases in the summation. The last equality is valid because $f(1) \neq 0$ . $_\square$

As noted above, $\mu * \mathbf{1} = e$ , so the Dirichlet inverse of $\mathbf{1}$ is $\mu$ . This fact is called Möbius inversion; see Möbius Function for much more about its applications.

Examples

Show that the Dirichlet inverse of $\lambda$ is $|\mu|$ .

Both $\lambda$ and $|\mu|$ are multiplicative, so their Dirichlet convolution $\lambda*|\mu|$ is multiplicative. Therefore, $e$ is also multiplicative, so it suffices to show that the two functions agree on prime powers. (This important fact is explained in the wiki on multiplicative functions.)
Now, $\begin{aligned} \big(\lambda*|\mu|\big)\big(p^k\big) &= \sum_{d|p^k}\lambda\left(\frac{p^k}{d}\right)\big|\mu(d)\big| \\ &= \lambda\big(p^k\big)+\lambda\big(p^{k-1}\big) \\&= (-1)^k+(-1)^{k-1}\\&=0. \end{aligned}$ Since $e\big(p^k\big) = 0$ , the functions agree on prime powers and hence are the same. $_\square$

Show that $d*\varphi = \sigma$ .

Start with $\mathbf{1}*\varphi = I$ and convolve both sides with $\mathbf{1}$ : $\begin{aligned} \mathbf{1}*(\mathbf{1}*\varphi) &= \mathbf{1}*I \\ (\mathbf{1}*\mathbf{1})*\varphi &= \sigma \\ d*\varphi &= \sigma.\ _\square \end{aligned}$

Show that $\sum_{a|n} \sigma\left(\frac na\right) \varphi(a) = nd(n).$

The left side is $\sigma*\varphi = (\mathbf{1}*I)*(\mu*I),$ where $\varphi = \mu*I$ comes from Möbius inversion of $\varphi*\mathbf{1} = I.$ Rearranging and moving parentheses around gives $\sigma*\varphi = (I*I)*(\mu*\mathbf{1}) = (I*I)*e = I*I,$ and $(I*I)(n) = \sum_{a|n} a \frac{n}{a} = \sum_{a|n} n = nd(n).$ $_\square$

Contents