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 up¹, 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.² Next time we will see what this has to do with the Möbius function $\mu$ .

Haha.↩
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

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

View all posts by Brent →

8 Responses to Dirichlet convolution

tomas says:

December 6, 2016 at 5:43 pm

Your blog is best! Thank you very much for your beatiful posts. I am realy enjoing it.
- Brent says:
  
  December 6, 2016 at 8:49 pm
  
  Thanks, I’m really glad you’re enjoying it!
Andrey Mokhov says:

December 7, 2016 at 11:45 am

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:
  
  December 7, 2016 at 10:34 pm
  
  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.
Pingback: Dirichlet convolution and the Möbius function | The Math Less Traveled
Pingback: Möbius inversion | The Math Less Traveled
Pingback: More fun with Dirichlet convolution | The Math Less Traveled
Pingback: Dirichlet generating functions | The Math Less Traveled