Dirichlet convolution
The Dirichlet convolution, also known as divisor convolution, is a fundamental binary operation in number theory defined on the set of arithmetic functions, which are functions from the positive integers to the complex numbers.[1] For two arithmetic functions f and g, their Dirichlet convolution (f \ast g) is defined by (f \ast g)(n) = \sum_{d \mid n} f(d) \, g\left(\frac{n}{d}\right) for each positive integer n, where the sum runs over all positive divisors d of n.[1] This operation was developed in the early 19th century by Peter Gustav Lejeune Dirichlet as part of his foundational work in analytic number theory.[2] The Dirichlet convolution is both commutative, satisfying f \ast g = g \ast f, and associative, allowing (f \ast g) \ast h = f \ast (g \ast h) for any arithmetic functions f, g, h.[1] Together with pointwise addition, it endows the set of arithmetic functions with a commutative ring structure, where the constant function \delta(n) = 1 if n=1 and $0 otherwise serves as the multiplicative identity, since f \ast \delta = f for any f.[1] If f and g are multiplicative functions—meaning f(mn) = f(m)f(n) and similarly for g whenever \gcd(m,n)=1—then f \ast g is also multiplicative.[1] One of the most notable applications of Dirichlet convolution is in the theory of Dirichlet series, where the product of two such series corresponds exactly to the convolution of their coefficient functions, facilitating the analysis of sums over divisors.[3] It also underpins Möbius inversion, a cornerstone of inversion formulas in number theory: if g(n) = \sum_{d \mid n} f(d), then f(n) = \sum_{d \mid n} \mu(d) \, g(n/d), where \mu is the Möbius function, the Dirichlet inverse of the constant function $1(n)=1.[1] These properties have made Dirichlet convolution indispensable for studying prime distributions, zeta functions, and other arithmetic phenomena.[2]Fundamentals
Definition
Arithmetic functions are functions f: \mathbb{N} \to \mathbb{C} defined on the positive integers \mathbb{N} with values in the complex numbers \mathbb{C}.[3][1] The Dirichlet convolution is a binary operation on pairs of such arithmetic functions f and g, denoted (f * g)(n) and defined for each positive integer n by (f * g)(n) = \sum_{d \mid n} f(d) \, g\left(\frac{n}{d}\right), where the sum runs over all positive divisors d of n.[3][1] This operation is defined over the domain of positive integers and produces another arithmetic function with range in \mathbb{C}.[3][1] It serves as an analog to ordinary convolution but adapted to the multiplicative structure of the positive integers, facilitating the study of arithmetic functions under divisor summation.[1]Basic Properties
The Dirichlet convolution operation exhibits several fundamental algebraic properties that render it a powerful tool in the study of arithmetic functions. These properties include commutativity, associativity, and the existence of an identity element, which collectively establish a rich structural framework.[4] The operation is commutative, meaning that for any arithmetic functions f and g, (f * g)(n) = (g * f)(n) for all positive integers n. This follows directly from the symmetry in the convolution sum, where the terms f(d)g(n/d) and g(d)f(n/d) pair identically over the divisors d of n.[4] Similarly, Dirichlet convolution is associative: (f * (g * h))(n) = ((f * g) * h)(n) for all arithmetic functions f, g, h and all n. Associativity arises from the ability to regroup the triple sum over divisors in the nested convolutions, ensuring the order of summation does not affect the result.[4] An identity element exists under this operation, given by the unit function \delta, defined as \delta(n) = 1 if n = 1 and \delta(n) = 0 otherwise. For any arithmetic function f, the convolution satisfies (\delta * f)(n) = f(n) = (f * \delta)(n) for all n, as the sum reduces to the single term where d=1 and n/d = n.[4] These properties—commutativity, associativity, and the identity—imply that the set of all arithmetic functions, equipped with Dirichlet convolution, forms a commutative monoid.[4] Furthermore, Dirichlet convolution preserves multiplicativity: if both f and g are multiplicative functions (i.e., f(mn) = f(m)f(n) and g(mn) = g(m)g(n) whenever \gcd(m,n)=1), then their convolution f * g is also multiplicative. This preservation stems from the fact that, for coprime m and n, the divisors of mn factor uniquely into divisors of m and n, allowing the convolution sum to separate multiplicatively.[4]Dirichlet Inverse
Construction
The Dirichlet inverse of an arithmetic function f with f(1) \neq 0 is defined as the arithmetic function f^{-1} satisfying f * f^{-1} = \varepsilon = f^{-1} * f, where * denotes the Dirichlet convolution and \varepsilon is the multiplicative identity function given by \varepsilon(1) = 1 and \varepsilon(n) = 0 for all integers n > 1.[5] This inverse exists and is unique within the set of arithmetic functions under Dirichlet convolution, forming an abelian group structure for all such invertible elements.[6] The condition f(1) \neq 0 ensures invertibility, as the value at 1 determines the group's unit compatibility.[5] To compute f^{-1}, a recursive formula is used, leveraging the definition at the identity. Specifically, f^{-1}(1) = 1 / f(1). For n > 1, f^{-1}(n) = -\frac{1}{f(1)} \sum_{\substack{d \mid n \\ d < n}} f(d) \, f^{-1}\left( \frac{n}{d} \right). This recursion proceeds by induction on n, computing values in order of increasing magnitude since the sum involves previously determined terms for proper divisors.[5] An equivalent form interchanges the arguments in the summand due to the commutativity of Dirichlet convolution.[6] For multiplicative functions, the construction preserves multiplicativity. If f is multiplicative and f(1) \neq 0, then f^{-1} is also multiplicative, as the convolution of multiplicative functions yields another multiplicative function, and the identity \varepsilon is multiplicative.[6] This follows directly from the recursive formula, since values at prime powers determine the function completely, and the recursion respects the multiplicative structure. As a direct consequence of the inverse's existence, the general Möbius inversion principle holds: if g(n) = \sum_{d \mid n} f(d) h(n/d) for arithmetic functions f and h with f(1) \neq 0, then h(n) = \sum_{d \mid n} f^{-1}(d) g(n/d).[5] This generalizes the classical Möbius inversion by replacing the constant function 1 (whose inverse is the Möbius function \mu) with arbitrary invertible f.[7]Examples
A prominent example of Dirichlet convolution involves the constant arithmetic function \zeta(n) = 1 for all positive integers n, often referred to as the zeta function in the context of arithmetic functions. The convolution \zeta * \zeta yields the divisor function \sigma_0(n), which counts the number of positive divisors of n. For instance, \sigma_0(1) = 1, \sigma_0(2) = 2, \sigma_0(4) = 3, and \sigma_0(6) = 4.[8] The Dirichlet inverse of the constant function \zeta is the Möbius function \mu, defined as \mu(1) = 1, \mu(p) = -1 for any prime p, \mu(p^k) = 0 for prime powers with k \geq 2, and \mu(n) = 0 if n has a squared prime factor (i.e., n is not square-free); otherwise, \mu(n) = (-1)^r where r is the number of distinct prime factors of n.[8][9] This inverse property is verified by the convolution \mu * \zeta = \varepsilon, where \varepsilon is the unit function with \varepsilon(1) = 1 and \varepsilon(n) = 0 for n > 1. The following table computes (\mu * \zeta)(n) for small values of n:| n | Divisors d of n | Terms \sum_{d \mid n} \mu(d) \zeta(n/d) | (\mu * \zeta)(n) |
|---|---|---|---|
| 1 | 1 | \mu(1) \zeta(1) = 1 \cdot 1 = 1 | 1 |
| 2 | 1, 2 | \mu(1) \zeta(2) + \mu(2) \zeta(1) = 1 \cdot 1 + (-1) \cdot 1 = 0 | 0 |
| 3 | 1, 3 | \mu(1) \zeta(3) + \mu(3) \zeta(1) = 1 \cdot 1 + (-1) \cdot 1 = 0 | 0 |
| 4 | 1, 2, 4 | \mu(1) \zeta(4) + \mu(2) \zeta(2) + \mu(4) \zeta(1) = 1 \cdot 1 + (-1) \cdot 1 + 0 \cdot 1 = 0 | 0 |
| 6 | 1, 2, 3, 6 | \mu(1) \zeta(6) + \mu(2) \zeta(3) + \mu(3) \zeta(2) + \mu(6) \zeta(1) = 1 \cdot 1 + (-1) \cdot 1 + (-1) \cdot 1 + 1 \cdot 1 = 0 | 0 |