Difference between revisions of "Dirichlet convolution"

Latest revision as of 21:40, 21 June 2009

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.

@@ Line 1: / Line 1: @@
-For two functions <math> f, g : \mathbb{N} \rightarrow \mathbb{C} </math>, the '''Dirichlet convolution''' (or simply '''convolution''', when the context is clear) <math> \displaystyle f * g </math> of <math> \displaystyle f </math> and <math> \displaystyle g </math> is defined as
+For two functions <math> f, g : \mathbb{N} \rightarrow \mathbb{C} </math>, the '''Dirichlet convolution''' (or simply '''convolution''', when the context is clear) <math>f * g </math> of <math>f </math> and <math>g </math> is defined as
 <center>
 <math> \sum_{d\mid n} f(d)g\left( \frac{n}{d} \right) </math>.
 </center>
-We usually only consider positive divisors of <math> \displaystyle n </math>.  We are often interested in convolutions of weak [[multiplicative function]]s; the set of weak multiplicative functions is closed under convolution.  In general, convolution is commutative and associative; it also has an identity, the function <math> \displaystyle f(n) </math> defined to be 1 if <math> \displaystyle n=1 </math>, and 0 otherwise.  Not all functions have inverses (e.g., the function <math> \displaystyle f(n) : n \mapsto 0 </math> has no inverse, as <math> \displaystyle f*g = f </math>, for all functions <math> g: \mathbb{N} \rightarrow \mathbb{C} </math>), although all functions <math> \displaystyle f </math> such that <math> \displaystyle f(1) \neq 0 </math> have inverses.
+We usually only consider positive divisors of <math>n </math>.  We are often interested in convolutions of weak [[multiplicative function]]s; the set of weak multiplicative functions is closed under convolution.  In general, convolution is commutative and associative; it also has an identity, the function <math>f(n) </math> defined to be 1 if <math>n=1 </math>, and 0 otherwise.  Not all functions have inverses (e.g., the function <math>f(n) : n \mapsto 0 </math> has no inverse, as <math>f*g = f </math>, for all functions <math> g: \mathbb{N} \rightarrow \mathbb{C} </math>), although all functions <math>f </math> such that <math>f(1) \neq 0 </math> have inverses.
 == Closure of Weak Multiplicative Functions Under Convolution ==
-'''Theorem.'''  If <math> f,g : \mathbb{N} \rightarrow \mathbb{C} </math> are weak multiplicative functions, then so is <math> \displaystyle f*g </math>.
+'''Theorem.'''  If <math> f,g : \mathbb{N} \rightarrow \mathbb{C} </math> are weak multiplicative functions, then so is <math>f*g </math>.
-''Proof.''  Let <math> \displaystyle m,n </math> be relatively prime.  We wish to prove that <math> \displaystyle (f*g)(mn) = (f*g)(m)\cdot (f*g)(n) </math>.
+''Proof.''  Let <math>m,n </math> be relatively prime.  We wish to prove that <math>(f*g)(mn) = (f*g)(m)\cdot (f*g)(n) </math>.
-For <math> a \in \mathbb{N} </math>, let <math> \displaystyle {\rm D}_a </math> be the set of divisors of <math> \displaystyle a </math>.  For relatively prime <math> \displaystyle m,n </math>, we claim that the function <math> p : (d_m,d_n) \mapsto d_md_n </math> is a [[bijection]] from <math> {\rm D}_m \times {\rm D}_n </math> to <math> \displaystyle {\rm D}_{mn} </math>.  Indeed, for any <math> \displaystyle d_m \mid m </math> and <math> \displaystyle d_n \mid n </math>, so <math> p({\rm D}_m \times {\rm D}_n) \subseteq {\rm D}_{mn} </math>.  Furthermore, for each <math> d \mid mn </math>, there exist unique <math> \displaystyle d_m, d_n </math> such that <math> d_m \mid m </math>, <math> d_n \mid n </math>, <math> \displaystyle d_md_n = d </math>.  Thus <math> \displaystyle p </math> is bijective.  As a result of our claim, we have the identity
+For <math> a \in \mathbb{N} </math>, let <math>{\rm D}_a </math> be the set of divisors of <math>a </math>.  For relatively prime <math>m,n </math>, we claim that the function <math> p : (d_m,d_n) \mapsto d_md_n </math> is a [[bijection]] from <math> {\rm D}_m \times {\rm D}_n </math> to <math>{\rm D}_{mn} </math>.  Indeed, for any <math>d_m \mid m </math> and <math>d_n \mid n </math>, so <math> p({\rm D}_m \times {\rm D}_n) \subseteq {\rm D}_{mn} </math>.  Furthermore, for each <math> d \mid mn </math>, there exist unique <math>d_m, d_n </math> such that <math> d_m \mid m </math>, <math> d_n \mid n </math>, <math>d_md_n = d </math>.  Thus <math>p </math> is bijective.  As a result of our claim, we have the identity
 <center>
 <math> \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) </math>,
 </center>
-for any functions <math> \displaystyle a,b </math> mapping subsets of <math> \mathbb{N} </math> into <math> \mathbb{C} </math>.  In particular, we may let the domains of <math> \displaystyle a </math> and <math> \displaystyle b </math> be <math> \displaystyle {\rm D}_m, {\rm D}_n </math>, and define <math> \displaystyle a(d_m) = f(d_m)g(m/d_m) </math> and <math> \displaystyle b(d_n) = f(d_n)g(n/d_n) </math>.  We then have
+for any functions <math>a,b </math> mapping subsets of <math> \mathbb{N} </math> into <math> \mathbb{C} </math>.  In particular, we may let the domains of <math>a </math> and <math>b </math> be <math>{\rm D}_m, {\rm D}_n </math>, and define <math>a(d_m) = f(d_m)g(m/d_m) </math> and <math>b(d_n) = f(d_n)g(n/d_n) </math>.  We then have
 <center>
 <math> \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) </math>.
 </center>
-But since each divisor of <math> \displaystyle m </math> is relatively prime to every divisor of <math> \displaystyle n </math>, we have
+But since each divisor of <math>m </math> is relatively prime to every divisor of <math>n </math>, we have
 <center>
 <math> \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) </math>,
@@ Line 31: / Line 31: @@
 {{stub}}
+[[Category:Definition]]

Page

Toolbox

Search

Difference between revisions of "Dirichlet convolution"

Latest revision as of 21:40, 21 June 2009

Closure of Weak Multiplicative Functions Under Convolution

Resources