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
.
Your blog is best! Thank you very much for your beatiful posts. I am realy enjoing it.
Thanks, I’m really glad you’re enjoying it!
Whoa, what an unexpected monoid!
Curiously, Dirichlet convolution seems to distribute over usual
:
. So, we have a semiring
.
Good point, I hadn’t thought of that. It makes sense though, this corresponds to the semiring of Dirichlet generating functions. I’ll have to write about the connection to generating functions in a future post.
Pingback: Dirichlet convolution and the Möbius function | The Math Less Traveled
Pingback: Möbius inversion | The Math Less Traveled
Pingback: More fun with Dirichlet convolution | The Math Less Traveled
Pingback: Dirichlet generating functions | The Math Less Traveled