Dirichlet convolution

From AoPSWiki

For two functions $f, g : \mathbb{N} \rightarrow \mathbb{C}$ , the Dirichlet convolution (or simply convolution, when the context is clear) $\displaystyle f * g$ of $\displaystyle f$ and $\displaystyle g$ is defined as

$\sum_{d\mid n} f(d)g\left( \frac{n}{d} \right)$ .

We usually only consider positive divisors of $\displaystyle n$ . We are often interested in convolutions of weak multiplicative functions; the set of weak multiplicative functions is closed under convolution. In general, convolution is commutative and associative; it also has an identity, the function $\displaystyle f(n)$ defined to be 1 if $\displaystyle n=1$ , and 0 otherwise. Not all functions have inverses (e.g., the function $\displaystyle f(n) : n \mapsto 0$ has no inverse, as $\displaystyle f*g = f$ , for all functions $g: \mathbb{N} \rightarrow \mathbb{C}$ ), although all functions $\displaystyle f$ such that $\displaystyle f(1) \neq 0$ have inverses.

Closure of Weak Multiplicative Functions Under Convolution

Theorem. If $f,g : \mathbb{N} \rightarrow \mathbb{C}$ are weak multiplicative functions, then so is $\displaystyle f*g$ .

Proof. Let $\displaystyle m,n$ be relatively prime. We wish to prove that $\displaystyle (f*g)(mn) = (f*g)(m)\cdot (f*g)(n)$ .

For $a \in \mathbb{N}$ , let $\displaystyle {\rm D}_a$ be the set of divisors of $\displaystyle a$ . For relatively prime $\displaystyle m,n$ , we claim that the function $p : (d_m,d_n) \mapsto d_md_n$ is a bijection from ${\rm D}_m \times {\rm D}_n$ to $\displaystyle {\rm D}_{mn}$ . Indeed, for any $\displaystyle d_m \mid m$ and $\displaystyle d_n \mid n$ , so $p({\rm D}_m \times {\rm D}_n) \subseteq {\rm D}_{mn}$ . Furthermore, for each $d \mid mn$ , there exist unique $\displaystyle d_m, d_n$ such that $d_m \mid m$ , $d_n \mid n$ , $\displaystyle d_md_n = d$ . Thus $\displaystyle p$ is bijective. As a result of our claim, we have the identity

$\sum_{d_m \mid m, d_n \mid n}a(d_m)b(d_n) = \sum_{d_m \mid m} a(d_m) \cdot \sum_{d_n \mid n}b(d_n)$ ,

for any functions $\displaystyle a,b$ mapping subsets of $\mathbb{N}$ into $\mathbb{C}$ . In particular, we may let the domains of $\displaystyle a$ and $\displaystyle b$ be $\displaystyle {\rm D}_m, {\rm D}_n$ , and define $\displaystyle a(d_m) = f(d_m)g(m/d_m)$ and $\displaystyle b(d_n) = f(d_n)g(n/d_n)$ . We then have

$\sum_{d_m \mid m}f(d_m)g(m/d_m) \cdot \sum_{d_n \mid n}f(d_n)g(n/d_n) = \sum_{d_m \mid m, d_n \mid n}f(d_m)g(m/d_m)f(d_n)g(n/d_n)$ .

But since each divisor of $\displaystyle m$ is relatively prime to every divisor of $\displaystyle n$ , we have

$\sum_{d_m \mid m, d_n \mid n}f(d_m)g(m/d_m)f(d_n)g(n/d_n) = \sum_{d_m \mid m, d_n \mid n}f(d_md_n)g\left(\frac{mn}{d_md_n}\right) = \sum_{d \mid mn}f(d)g(mn/d)$ ,

as desired.

Resources

This article is a stub. Help us out by expanding it.

Personal tools

Navigation

Search

Toolbox

Dirichlet convolution

From AoPSWiki

Closure of Weak Multiplicative Functions Under Convolution

Resources