Dirichlet convolution

1 Definition and basic properties

1.1 Arithmetic functions and notation

An arithmetic function is a function \(f:\mathbb{N}\to \mathbb{C}\) (or to another ring or field), where \(\mathbb{N}\) denotes the positive integers. The values of \(f\) are typically studied through their behavior under divisibility, especially because many arithmetic questions naturally decompose along the divisor structure of an integer.

Two standard notational conventions are commonly used. First, \(d\mid n\) indicates that \(d\) divides \(n\). Second, expressions such as \(n/d\) are interpreted only when \(d\mid n\).

1.2 Definition of Dirichlet convolution

Given arithmetic functions \(f\) and \(g\), their Dirichlet convolution \(f*g\) is defined by \[ (f*g)(n)=\sum_{d\mid n} f(d)\, g\!\left(\frac{n}{d}\right), \] for each \(n\in\mathbb{N}\). The sum runs over all positive divisors \(d\) of \(n\). Because both arguments \(d\) and \(n/d\) are divisors of \(n\), the convolution is tightly linked to the multiplicative structure of integers.

1.3 Commutativity and associativity

Dirichlet convolution is commutative: \[ f*g=g*f. \] This follows by substituting \(d\mapsto n/d\) in the divisor sum.

It is also associative: \[ (f*g)*h=f*(g*h). \] Associativity can be seen by expanding both sides into double sums over divisors and then regrouping terms according to common factorization patterns of \(n\).

1.4 Identity element and invertibility

There is a natural identity element \(\varepsilon\) defined by \[ \varepsilon(1)=1,\qquad \varepsilon(n)=0\ \text{for } n>1. \] For any arithmetic function \(f\), \[ (f*\varepsilon)(n)=f(n)= (\varepsilon*f)(n). \] In this convolution algebra, an arithmetic function \(f\) has a convolution inverse \(f^{-1}\) (with respect to \(*\)) if and only if \(f(1)\neq 0\). In that case, \(f^{-1}\) is uniquely determined by recursion on prime powers (or more generally by induction over \(n\)).

1.5 Relation to divisor sums

The convolution definition can be interpreted as a structured divisor-sum transform. The values of \(f\) and \(g\) are sampled on complementary divisors \(d\) and \(n/d\). Many classical arithmetic quantities (such as divisor-counting and divisor-sum functions) arise by choosing particular \(f\) and \(g\), or by convolving simpler functions to encode multiplicative information about divisor sets.

2 Algebraic structure

2.1 Convolution algebra viewpoint

The collection of all arithmetic functions \( \{f:\mathbb{N}\to R\}\), for a commutative ring \(R\), forms a convolution algebra under pointwise addition and Dirichlet convolution. The operation \(*\) is bilinear, associative, and commutative, with identity element \(\varepsilon\).

This viewpoint is useful because it turns certain divisor identities into algebraic equations. Instead of manipulating divisor sums directly, one can often translate statements into equalities of convolutions and use algebraic properties to prove them.

2.2 Units and the role of \( \varepsilon(n) \)

The function \(\varepsilon\) plays the role of the multiplicative unit in the convolution algebra. A function \(f\) is a unit (i.e., invertible) precisely when \(f(1)\neq 0\). Intuitively, the value at \(1\) controls whether the recursion for the inverse begins with a nondegenerate base case.

2.3 Convolution inverses

2.3.1 Möbius inversion as a special case

A central example of inversion is obtained by taking \(f\equiv 1\), the constant function \(1(n)=1\). Its convolution inverse is the Möbius function \(\mu\), meaning \[

1 Definition and basic properties

\] This identity underlies Möbius inversion, which converts relations defined via divisor sums into relations defined via inclusion–exclusion-like cancellation across divisors.

2.4 Bilinearity

Dirichlet convolution is bilinear: \[ ((af+bg)*h)(n)=a(f*h)(n)+b(g*h)(n),\qquad (f*(ah+bk))(n)=a(f*h)(n)+b(f*k)(n). \] This follows immediately from the linearity of each term inside the divisor sum. Bilinearity is essential for transferring linear transformations between arithmetic functions.

3 Interaction with multiplicative functions

3.1 Multiplicativity basics

An arithmetic function \(f\) is multiplicative if \(f(1)=1\) and \[ f(mn)=f(m)f(n)\quad \text{whenever } \gcd(m,n)=1. \] It is completely multiplicative if the same formula holds for all \(m,n\) (without the coprimality condition), which forces \(f(n)\) to factor entirely across prime powers.

3.2 Closure of multiplicative functions under convolution

If \(f\) and \(g\) are multiplicative, then \(f*g\) is also multiplicative. This closure property is one of the reasons Dirichlet convolution is especially effective in number theory: it preserves the structural class of multiplicative functions, allowing one to reason using prime factorization.

3.3 Completely multiplicative vs. multiplicative

Completely multiplicative functions are a stricter subclass. When \(f\) and \(g\) are completely multiplicative, the convolution generally becomes more structured but not necessarily completely multiplicative. The distinction matters when computing values, since completely multiplicative behavior is determined directly by primes, while multiplicativity only applies across coprime parts.

3.4 Convolution and prime power evaluation

3.4.1 Computing \( (f*g)(p^k) \)

For multiplicative functions \(f\) and \(g\), convolution can be reduced to prime powers. Let \(n=p^k\). The divisors of \(p^k\) are \(p^j\) for \(0\le j\le k\), so \[ (f*g)(p^k)=\sum_{j=0}^k f(p^j)\, g(p^{k-j}). \] This is effectively a one-dimensional discrete convolution of the sequences \(f(p^j)\) and \(g(p^j)\). Once prime power values are known, multiplicativity determines values on all integers.

4 Examples and standard identities

4.1 Convolution involving constant functions

The constant function \(1(n)=1\) yields \[ (1*g)(n)=\sum_{d\mid n} g\!\left(\frac{n}{d}\right)=\sum_{d\mid n} g(d), \] since substituting \(d\leftrightarrow n/d\) leaves the divisor set unchanged. Thus convolving with \(1\) produces the classical divisor sum transform.

Similarly, \[ (f*1)(n)=\sum_{d\mid n} f(d). \] These identities connect Dirichlet convolution directly to divisor-counting and divisor-sum functions.

4.2 Convolution with the identity function \( \mathrm{id}(n) \)

The identity function \(\mathrm{id}(n)=n\) is completely multiplicative and satisfies \(\mathrm{id}(p^k)=p^k\). Convolution with \(\mathrm{id}\) often encodes “weighted by divisors” sums. For example, \[ (\mathrm{id}*1)(n)=\sum_{d\mid n} d=\sigma(n), \] where \(\sigma(n)\) denotes the sum of divisors of \(n\). More generally, \((f*\mathrm{id})(n)\) combines \(f(d)\) with a factor depending on the complementary divisor \(n/d\).

4.3 Convolution with the divisor-counting function \( \tau(n) \)

The divisor-counting function \(\tau(n)\) is defined by \(\tau(n)=\sum_{d\mid n}1=\bigl(1* \varepsilon\bigr)(n)\) in convolution terms (and simply \(\tau(n)= (1*1_{\{? \}})\) is better expressed via divisor sums). A concrete identity uses the fact that \[ (\,1*1\,)(n)=\sum_{d\mid n}1\cdot 1 = \tau(n). \] Thus \(\tau\) can be seen as the self-convolution of the constant arithmetic function \(1\).

4.4 Convolution with the sum-of-divisors function \( \sigma(n) \)

The sum-of-divisors function \(\sigma(n)=\sum_{d\mid n} d\) can be expressed as \[ \sigma = \mathrm{id}*1, \] since \[ (\mathrm{id}*1)(n)=\sum_{d\mid n} \mathrm{id}(d)\cdot 1\!\left(\frac{n}{d}\right)=\sum_{d\mid n} d. \] Convolutions involving \(\sigma\) frequently appear in formulas for divisor sums weighted by multiplicative factors.

4.5 The Möbius function and classical inversion

The Möbius function \(\mu\) satisfies the defining inversion identity \[ \sum_{d\mid n}\mu(d)= \begin{cases} 1,& n=1,\\ 0,& n>1. \end{cases} \] In convolution language, this is exactly \(1*\mu=\varepsilon\). As a result, \(\mu\) acts as the “cancelling kernel” that reverses divisor-sum transforms.

5 Möbius inversion theorem

5.1 Statement of Möbius inversion

A common form of Möbius inversion states: if arithmetic functions \(F\) and \(f\) satisfy \[ F(n)=\sum_{d\mid n} f(d), \] then \[ f(n)=\sum_{d\mid n} \mu(d)\, F\!\left(\frac{n}{d}\right). \] The theorem holds because \(\mu\) is the convolution inverse of the constant function \(1\).

5.2 Dirichlet convolution form of inversion

In convolution notation, the same relationship can be written succinctly. The condition \(F=1*f\) means \[ F(n)=(1*f)(n)=\sum_{d\mid n} f(d). \] Since \(\mu\) is the inverse of \(1\), one gets \[ f=\mu*F, \] i.e. \[ f(n)=(\mu*F)(n)=\sum_{d\mid n}\mu(d)\,F\!\left(\frac{n}{d}\right). \]

5.3 Applications to divisor-sum transforms

Möbius inversion is repeatedly used to convert identities that involve divisor summations into equivalent statements where the original function is recovered. Typical applications include:

reversing relations between counting functions and multiplicative parameters,
extracting coefficients from arithmetic Dirichlet series relations,
proving or simplifying formulas for sums over divisors by introducing \(\mu\) to separate contributions from different factorization patterns.

5.4 Examples of inversion computations

For instance, consider a function \(F\) known to be the divisor sum of \(f\): \(F(n)=\sum_{d\mid n} f(d)\). Then the inversion formula provides an explicit computation of \(f(n)\) by summing \(\mu(d)\,F(n/d)\) over all divisors. Because \(\mu(d)\) is supported on squarefree integers and takes only values in \(\{-1,0,1\}\), many terms vanish, making the inversion practical for concrete values and for symbolic manipulations in identities.

6 Dirichlet generating series

6.1 Dirichlet series of arithmetic functions

For an arithmetic function \(f\), its Dirichlet generating series is often written as \[ \sum_{n=1}^\infty \frac{f(n)}{n^s}, \] where \(s\) is a complex variable. When the series converges (for instance, for sufficiently large \(\Re(s)\)), it packages arithmetic information into an analytic function.

6.2 Product rule under Dirichlet convolution

Dirichlet convolution corresponds to multiplication of Dirichlet generating series. Specifically, if the relevant series converge absolutely in some region, then \[ \sum_{n=1}^\infty \frac{(f*g)(n)}{n^s} = \left(\sum_{n=1}^\infty \frac{f(n)}{n^s}\right) \left(\sum_{n=1}^\infty \frac{g(n)}{n^s}\right). \] This is the analytic manifestation of the algebraic rule \(*\) in the convolution algebra.

6.3 Conditions for convergence and formal identities

The product rule requires justification: interchanging sums or rearranging terms must be valid. In many contexts, one assumes absolute convergence for \(\Re(s)\) large enough. In more algebraic treatments, one can regard Dirichlet generating series as formal objects where the convolution–multiplication correspondence is used without analytic convergence concerns, as long as manipulations are controlled.

6.4 Using generating series to derive convolution identities

Once convolution identities are established in the arithmetic setting, they can be transferred to the level of generating functions. Conversely, if one knows factorization properties of Dirichlet series (such as Euler products for multiplicative functions), one can infer corresponding convolution structures. This two-way translation is a key method in analytic number theory: it turns questions about sums over divisors into questions about products of series.

7 Common special functions and their convolutions

7.1 The zeta function as a series transform

The Riemann zeta function can be written as a Dirichlet series \[ \zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s}, \] which is the Dirichlet generating series of the constant function \(1(n)\equiv 1\). In this sense, convolution identities involving \(1\) correspond to multiplication by \(\zeta(s)\) in generating-series form.

7.2 Euler product perspective

For multiplicative functions \(f\), Dirichlet series often factor as an Euler product \[ \sum_{n=1}^\infty \frac{f(n)}{n^s} = \prod_{p}\left(\sum_{k=0}^\infty \frac{f(p^k)}{p^{ks}}\right), \] under suitable convergence conditions. Since convolution corresponds to multiplication of series, convolution translates into product operations at the level of Euler factors, making prime-power computations central.

7.3 Convolution behavior of classical arithmetic functions

Classical arithmetic functions frequently admit clean convolution relations:

\(1\) generates divisor-sum transforms.
\(\mu\) inverts those transforms.
\(\mathrm{id}\) and \(1\) combine to produce \(\sigma\).
\(\tau\) appears from \(1*1\).

These patterns illustrate that many “named” functions arise naturally as convolutions of simpler kernels.

7.4 Prime-factorization-driven convolution rules

For multiplicative functions, convolution can be computed systematically from prime powers:

1 Definition and basic properties

2 Algebraic structure

3 Interaction with multiplicative functions

This rule reduces many convolution questions to manageable calculations on each prime independently.

8 Computational and methodological aspects

8.1 Efficient evaluation using divisor lists

To compute \((f*g)(n)\) directly from the definition, one can list all divisors \(d\) of \(n\) and sum \(f(d)g(n/d)\). For practical computation, it is common to pair divisors \(d\) with \(n/d\) to avoid redundant evaluations and to exploit symmetry when \(f\) and \(g\) share properties.

8.2 Prime-power recursion techniques

When \(f\) and \(g\) are multiplicative, a more scalable method uses prime-power recursion. One computes convolution on each \(p^k\) using the one-dimensional sum \[ (f*g)(p^k)=\sum_{j=0}^k f(p^j)g(p^{k-j}), \] and then reconstructs values on \(n\) by multiplicativity. This approach often outperforms divisor enumeration for large integers with known prime factorizations.

8.3 Convolution-based proof strategies

Proofs involving convolution often follow a standard strategy:

translate the desired identity into a convolution equation,
use algebraic properties (commutativity, associativity, bilinearity),
apply inverses when needed (for instance, using that \(\mu\) inverts divisor sums),
reduce to prime powers for multiplicative functions.

This method tends to streamline divisor-sum arguments by leveraging the convolution algebra framework.

8.4 Checking identities via prime powers

To verify an identity \(H(n)=(f*g)(n)\) for multiplicative \(f,g\), it typically suffices to check it on prime powers. Because multiplicative functions are determined by their prime-power values, confirming \[ H(p^k)=(f*g)(p^k)\quad \text{for all primes }p\text{ and }k\ge 0 \] implies the identity for all \(n\). This reduces potentially complicated global sums to localized checks on each prime.