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.

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$.

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.

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

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.

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.

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$