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{align*} (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{align*}\] $\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{align*} 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{align*}\]

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{align*} 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{align*}\]

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{align} \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{align}\] 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{align} \mathbf{1}*(\mathbf{1}*\varphi) &= \mathbf{1}*I \\ (\mathbf{1}*\mathbf{1})*\varphi &= \sigma \\ d*\varphi &= \sigma.\ _\square \end{align}\]

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 $

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.

Contents