 Dirichlet convolution

The Dirichlet convolution of arithmetic functions $f,g$ is the arithmetic functionIn 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. ^[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:Here $\tau$ is the divisor function and ${\sigma }_1$ is the sum-of-divisors function. By comparison, the pointwise product of arithmetic functions gives $(1\cdot 1)(12)=1$ and $(\mathrm{id}\cdot 1)(12)=12$.

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:For example, $((1\ast 1)\ast 1)(12)$ counts ordered tuples of three positive integers with product $12$. Distribute the two occurrences of the prime factor $2$ among three entries in $\left(\genfrac{}{}{0ex}{}{2+2}{2}\right)=6$ ways, and the one occurrence of the prime factor $3$ in $\left(\genfrac{}{}{0ex}{}{1+2}{2}\right)=3$ ways. These binomial coefficients are the stars and bars counts of exponent choices in the nonnegative integers; prime factorization therefore gives $6\cdot 3=18$ such tuples. Directly, the same Dirichlet convolution is ${\sum }_{d\mid 12}\tau (d)=1+2+2+3+4+6=18$.

The Identity for Dirichlet convolution is $\epsilon$, and the Möbius function reverses a divisor sum because $\mu \ast 1=\epsilon$. This makes Dirichlet convolution useful both for counting factorizations and for recovering an arithmetic function from its divisor sum.