= Dirichlet convolution
{c}
{title2=$*$}
{wiki}
The <Dirichlet convolution> of <arithmetic functions> $f,g$ is the <arithmetic function>
$$
(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)=\sum_{\substack{a,b>0\\ab=n}}f(a)g(b),\qquad n>0.
$$
In the first sum, $d$ runs over the positive <integer divisors> of $n$; the second uses <ordered pairs> of <positive integers> whose product is $n$. Both sums are finite. Each pair contributes one weight from $f$ and one from $g$, so <Dirichlet convolution> combines information attached to complementary factors. It turns a <divisor sum> into an operation on <arithmetic functions>. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781 lecture notes, Sections 2.3 and 2.4: Dirichlet convolution and examples]{ref}
For $n=12$ the six <ordered pairs> are $(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)$. The <constant-one arithmetic function> gives one per pair, while the <identity arithmetic function> weights the first factor by its size:
$$
\begin{aligned}
\tau&=\mathbf1*\mathbf1,&\tau(12)&=1+1+1+1+1+1=6,\\
\sigma_1&=\operatorname{id}*\mathbf1,&\sigma_1(12)&=1+2+3+4+6+12=28.
\end{aligned}
$$
Here $\tau$ is the <divisor function> and $\sigma_1$ is the <sum-of-divisors function>. By comparison, the <pointwise product of arithmetic functions> gives $(\mathbf1\cdot\mathbf1)(12)=1$ and $(\operatorname{id}\cdot\mathbf1)(12)=12$.
\Image[/dirichlet-convolution-factor-pairs.png]
{title=Six <ordered pairs> of <positive integers> with product 12 contribute to <Dirichlet convolution>: one per pair for the <divisor function>, or the first factor for the <sum-of-divisors function>}
<Commutativity> follows by swapping the two entries of every <ordered pair>. <Associativity> follows by reindexing either grouping over the same ordered <tuples> of three <positive integers>:
$$
((f*g)*h)(n)=\sum_{\substack{a,b,c>0\\abc=n}}f(a)g(b)h(c)=(f*(g*h))(n).
$$
For example, $((\mathbf1*\mathbf1)*\mathbf1)(12)$ counts ordered <tuples> of three <positive integers> with product $12$. Distribute the two occurrences of the <prime factor> $2$ among three entries in $\binom{2+2}{2}=6$ ways, and the one occurrence of the <prime factor> $3$ in $\binom{1+2}{2}=3$ ways. These <binomial coefficients> are the <stars and bars (combinatorics)> counts of exponent choices in the <nonnegative integers>; <prime factorization> therefore gives $6\cdot3=18$ such <tuples>. Directly, the same <Dirichlet convolution> is $\sum_{d\mid12}\tau(d)=1+2+2+3+4+6=18$.
The <Identity for Dirichlet convolution> is $\varepsilon$, and the <Möbius function> reverses a <divisor sum> because $\mu*\mathbf1=\varepsilon$. This makes <Dirichlet convolution> useful both for counting factorizations and for recovering an <arithmetic function> from its <divisor sum>.
Back to article page
