# 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{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 alos 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 \)

**Cite as:**Dirichlet Convolution.

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