## Dirichlet convolution

Let $f$ and $g$ be two functions defined on the positive integers. Then the Dirichlet convolution of $f$ and $g$, written $f \ast g$, is another function on the positive integers, defined as follows:

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

The sum is taken over all possible factorizations of $n$ into a product $ab$ of positive integers. For example, suppose $f(n) = n$ and $g(n) = n^2$. Then

$\displaystyle \begin{array}{rcl}(f \ast g)(6) &=& \displaystyle \sum_{ab = 6} f(a) g(b) \\[1.5em] &=& f(1)g(6) + f(2)g(3) + f(3)g(2) + f(6)g(1) \\[1em] &=& 1 \cdot 6^2 + 2 \cdot 3^2 + 3 \cdot 2^2 + 6 \cdot 1^2 \\[1em] &=& 36 + 18 + 12 + 6 = 72.\end{array}$

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 $\mu$ and hence with primes and factorization.

So what properties does $\ast$ have?

• It’s commutative, that is, $f \ast g = g \ast f$. This follows directly from the commutativity of multiplication:

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

• It’s also associative, that is, $f \ast (g \ast h) = (f \ast g) \ast h$. This also follows from the associativity of multiplication, and distributivity of multiplication over addition. The proof is kind of fiddly but not really difficult:

$\displaystyle \begin{array}{rcl} (f \ast (g \ast h))(n) &=& \displaystyle \sum_{ab = n} f(a) (g \ast h)(b) \\[1.5em] &=& \displaystyle \sum_{ab = n} f(a) \left( \sum_{cd = b} g(c) h(d) \right) \\[1.5em] &=& \displaystyle \sum_{ab = n} \sum_{cd = b} f(a) \left( g(c) h(d) \right) \\[1.5em] &=& \displaystyle \sum_{a(cd) = n} f(a) (g(c) h(d)) \\[1.5em] &=& \displaystyle \sum_{(ac)d = n} (f(a) g(c)) h(d) \\[1.5em] &=& \displaystyle \sum_{ed = n} \sum_{ac=e} (f(a) g(c)) h(d) \\[1.5em] &=& \displaystyle \sum_{ed = n} \left(\sum_{ac=e} f(a)g(c)\right) h(d) \\[1.5em] &=& \displaystyle \sum_{ed = n} (f \ast g)(e) h(d) \\[1.5em] &=& ((f \ast g) \ast h)(n) \end{array}$

• Define the function $\varepsilon$ as follows:

$\displaystyle \varepsilon(n) = \begin{cases} 1 & \text{if } n=1 \\ 0 & \text{otherwise.} \end{cases}$

Then I claim that $\varepsilon$ is an identity element for $\ast$, that is, for any function $f$ we have $f \ast \varepsilon = \varepsilon \ast f = f$. By definition,

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

But $\varepsilon(b) = 0$ for every $b$ other than $1$, which cancels out most of the terms of the sum. The only term that does not become zero is $f(n) \varepsilon(1) = f(n)$. So the right-hand sum reduces to just $f(n)$, that is, $f \ast \varepsilon = f$. Since we already know $\ast$ is commutative this proves that $\varepsilon \ast f = f$ too.

So, to sum up1, we have defined the Dirichlet convolution $\ast$, and shown that it is associative, commutative, and has $\varepsilon$ as an identity element. That is, to use some fancy math words, we have shown that $(\ast, \varepsilon)$ 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 $\mu$.

1. Haha.

2. Technically we should also specify the codomain of the functions, but it doesn’t matter much: typically it is taken to be the complex numbers, but really anything with a commutative, associative multiplication that distributes over addition will do.

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.

### 8 Responses to Dirichlet convolution

1. tomas says:

Your blog is best! Thank you very much for your beatiful posts. I am realy enjoing it.

• Brent says:

Thanks, I’m really glad you’re enjoying it!

2. Whoa, what an unexpected monoid!

Curiously, Dirichlet convolution seems to distribute over usual $+$: $f * (g + h) = f * g + f * h$. So, we have a semiring $(*, \epsilon, +, 0)$.

• Brent says:

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.