Let and be two functions defined on the positive integers. Then the Dirichlet convolution of and , written , is another function on the positive integers, defined as follows:
The sum is taken over all possible factorizations of into a product of positive integers. For example, suppose and . Then
At this point this may seem somewhat arbitrary, but over the next few posts we’ll see that it’s not arbitrary at all—this operation is deeply connected with the Möbius function and hence with primes and factorization.
So what properties does have?
It’s commutative, that is, . This follows directly from the commutativity of multiplication:
It’s also associative, that is, . This also follows from the associativity of multiplication, and distributivity of multiplication over addition. The proof is kind of fiddly but not really difficult:
Define the function as follows:
Then I claim that is an identity element for , that is, for any function we have . By definition,
But for every other than , which cancels out most of the terms of the sum. The only term that does not become zero is . So the right-hand sum reduces to just , that is, . Since we already know is commutative this proves that too.
So, to sum up1, we have defined the Dirichlet convolution , and shown that it is associative, commutative, and has as an identity element. That is, to use some fancy math words, we have shown that is a commutative monoid over the set of functions defined on the positive integers.2 Next time we will see what this has to do with the Möbius function .