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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →