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

#### Contents

## 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 convolutionof $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$

**Cite as:**Dirichlet Convolution.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/dirichlet-convolution/