Dirichlet convolution

Revision as of 20:40, 21 June 2009 by 5849206328x (talk | contribs) (Categorized)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

We usually only consider positive divisors of $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 $f(n)$ defined to be 1 if $n=1$, and 0 otherwise. Not all functions have inverses (e.g., the function $f(n) : n \mapsto 0$ has no inverse, as $f*g = f$, for all functions $g: \mathbb{N} \rightarrow \mathbb{C}$), although all functions $f$ such that $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 $f*g$.

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

For $a \in \mathbb{N}$, let ${\rm D}_a$ be the set of divisors of $a$. For relatively prime $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 ${\rm D}_{mn}$. Indeed, for any $d_m \mid m$ and $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 $d_m, d_n$ such that $d_m \mid m$, $d_n \mid n$, $d_md_n = d$. Thus $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 $a,b$ mapping subsets of $\mathbb{N}$ into $\mathbb{C}$. In particular, we may let the domains of $a$ and $b$ be ${\rm D}_m, {\rm D}_n$, and define $a(d_m) = f(d_m)g(m/d_m)$ and $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 $m$ is relatively prime to every divisor of $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.