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

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

  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.

  3. Pingback: Dirichlet convolution and the Möbius function | The Math Less Traveled

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

  5. Pingback: More fun with Dirichlet convolution | The Math Less Traveled

  6. Pingback: Dirichlet generating functions | The Math Less Traveled

Comments are closed.