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 are arithmetic functions. Then the Dirichlet convolution of and , denoted by , is the following arithmetic function:
where the sum is taken over all positive divisors of .
Consider the identity function for all natural numbers , and the constant function for all natural numbers . Their convolution is
for a definition of , see below We write this as .
Let be arithmetic functions. Then we have the following:
- Convolution is commutative: .
- It is associative: .
- It is distributive over addition: .
- It has an identity: define Then for any .
- 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.
|Constant function that returns 1 no matter its argument. This function is completely multiplicative.|
|Identity function that returns its argument. This function is completely multiplicative.|
|Function that returns its argument raised to the power; and|
|Multiplicative identity function (not to be confused with ) that returns 1 if its argument is 1, and otherwise returns 0. This function is completely multiplicative.|
|Divisor function that returns the number of positive divisors of . This function is multiplicative.|
|Divisor sum function that returns the sum of the positive divisors of . This function is multiplicative.|
|Function that returns the sum of each of the positive divisors of raised to the power; is and is . This function is multiplicative.|
|Euler's totient function that returns the number of positive integers such that are relatively prime. This function is multiplicative.|
|Liouville function; the exponent is the number of prime divisors of , counting multiplicity. This function is multiplicative.|
|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:
The Dirichlet inverse of an arithmetic function is another arithmetic function satisfying . As it turns out, every arithmetic function that satisfies has a Dirichlet inverse.
The Dirichlet inverse of is given by the following: , and for all positive integers ,
where the sum runs over all proper positive divisors of .
First, consider when . Write
The first equality comes from the definition of being the Dirichlet inverse of ; the third equality comes because there is only a single positive divisor of 1.
Now we consider . Write
The second equality is because convolution is commutative. The fourth equality separates the case from the remaining cases in the summation. The last equality is valid because .
As noted above, , so the Dirichlet inverse of is . This fact is called Möbius inversion; see Möbius Function for much more about its applications.
Show that the Dirichlet inverse of is .
Both and are multiplicative, so their Dirichlet convolution is multiplicative. Therefore, 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, Since , the functions agree on prime powers and hence are the same.
Show that .
Start with and convolve both sides with :
The left side is where comes from Möbius inversion of Rearranging and moving parentheses around gives and