Suppose is a function defined for positive integers . Then we can define an infinite series as follows:
(This might look a bit strange, but bear with me!) For example, suppose for all . Then
(Note that in this case, with , the infinite sum converges; but often we just use as a formal placeholder and don’t particularly care about convergence. That is, is perfectly well defined as an infinite series without worrying about the value of .)
In fact is called the Dirichlet generating function for . Of course, this name should remind you of Dirichlet convolution—and it’s no coincidence; Dirichlet convolution and Dirichlet generating functions are closely related. Let’s see how.
Suppose we have two functions and , and consider multiplying their Dirichlet generating functions (with plain old, regular multiplication):
We have a big (well, infinite) sum of things multiplied by another big sum. By distributivity, we’re going to get a big sum as a result, where each term of the resulting sum is the product of one thing chosen from the left-hand sum and one thing chosen from the right-hand sum. (This is just like FOIL, only way cooler and more infinite-r.) That is, the resulting sum is going to look something like this:
with one term for every possible choice of and . The in the denominator is of course equal to , and we can collect up all the fractions with the same denominator: for each , we will get a denominator of in each case where we pick some and whose product is . So we can reorganize the terms in the above sum, grouping together all the terms where the product of and is the same, and rewrite it like this (is this starting to look familiar…?):
Now we can factor out the (since it doesn’t depend on or ), like so:
But the inner sum is now just the definition of the Dirichlet convolution of and ! So the whole thing becomes
And finally, we note that the thing on the right is itself the Dirichlet generating function for . So in summary, we have shown that
Neato! So in some sense, Dirichlet generating functions “turn Dirichlet convolution into regular multiplication”.