## 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. ## 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.

### 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. Andrey Mokhov says:

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.

Comments are closed.