Dirichlet convolution and the Möbius function

Recall from last time that the Dirichlet convolution of two functions f and g is written f \ast g and defined by:

\displaystyle (f \ast g)(n) = \sum_{ab = n} f(a) g(b)

where the sum is taken over all possible factorizations of n into a product ab of positive integers. Last time we saw that \ast is commutative and associative, and has \varepsilon(n) as an identity, where \varepsilon is the function which produces 1 for an input of 1 and 0 for all other inputs.

So what does the Möbius function have to do with this? Let’s start by considering a different function:

\displaystyle \mathbf{1}(n) = 1

is the function which ignores its input and always returns 1. Of course this is not the same thing as \varepsilon, and despite its name \mathbf{1} is indeed not an identity for Dirichlet convolution. That is, if we take some function f and find its Dirichlet convolution with \mathbf{1}, we don’t get f again—but we do get something interesting:

\displaystyle (\mathbf{1} \ast f)(n) = \sum_{ab=n} \mathbf{1}(a) f(b) = \sum_{ab=n} f(b) = \sum_{d \mid n} f(d)

The first step is the definition of \ast; the second step is the definition of \mathbf{1}; and the last step just notes that the sum of all f(b) where ab = n is the same as taking the sum of f(d) for all divisors of n.

That is, \mathbf{1} \ast f is the function which for a given n outputs not just f(n) but the sum of f over all divisors of n.

We’re now ready to see how \mu enters the picture!

Claim: \mathbf{1} \ast \mu = \varepsilon.

That is, \mu is the inverse of \mathbf{1} 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?

\displaystyle (\mathbf{1} \ast \mu)(n) = \sum_{d \mid n} \mu(d) = \varepsilon(n).

Actually, there was hardly anything left to prove! The first equality is because of what we just showed about taking the Dirichlet convolution of \mathbf{1} with something else. And the second equality is a property of \mu we just finished proving in some previous posts.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in combinatorics, proof and tagged , , , . Bookmark the permalink.

One Response to Dirichlet convolution and the Möbius function

  1. Pingback: Möbius inversion | The Math Less Traveled

Comments are closed.