Recall from last time that the Dirichlet convolution of two functions and is written and defined by:
where the sum is taken over all possible factorizations of into a product of positive integers. Last time we saw that is commutative and associative, and has as an identity, where is the function which produces for an input of and for all other inputs.
So what does the Möbius function have to do with this? Let’s start by considering a different function:
is the function which ignores its input and always returns . Of course this is not the same thing as , and despite its name is indeed not an identity for Dirichlet convolution. That is, if we take some function and find its Dirichlet convolution with , we don’t get again—but we do get something interesting:
The first step is the definition of ; the second step is the definition of ; and the last step just notes that the sum of all where is the same as taking the sum of for all divisors of .
That is, is the function which for a given outputs not just but the sum of over all divisors of .
We’re now ready to see how enters the picture!
That is, is the inverse of with respect to Dirichlet convolution. In my next post we’ll see some cool implications of this; for now, let’s just prove it.
Proof. Here’s the proof. Ready?
Actually, there was hardly anything left to prove! The first equality is because of what we just showed about taking the Dirichlet convolution of with something else. And the second equality is a property of we just finished proving in some previous posts.
Pingback: Möbius inversion | The Math Less Traveled