Difference between revisions of "Dirichlet convolution"
5849206328x (talk | contribs) m (Categorized) |
|||
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> | + | 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> | <center> | ||
<math> \sum_{d\mid n} f(d)g\left( \frac{n}{d} \right) </math>. | <math> \sum_{d\mid n} f(d)g\left( \frac{n}{d} \right) </math>. | ||
</center> | </center> | ||
− | We usually only consider positive divisors of <math> | + | 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 == | == 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> | + | '''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> | + | ''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> | + | 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> | <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>, | <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> | </center> | ||
− | for any functions <math> | + | 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> | <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>. | <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> | </center> | ||
− | But since each divisor of <math> | + | But since each divisor of <math>m </math> is relatively prime to every divisor of <math>n </math>, we have |
<center> | <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>, | <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}} | {{stub}} | ||
+ | [[Category:Definition]] |
Latest revision as of 20:40, 21 June 2009
For two functions , the Dirichlet convolution (or simply convolution, when the context is clear) of and is defined as
.
We usually only consider positive divisors of . 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 defined to be 1 if , and 0 otherwise. Not all functions have inverses (e.g., the function has no inverse, as , for all functions ), although all functions such that have inverses.
Closure of Weak Multiplicative Functions Under Convolution
Theorem. If are weak multiplicative functions, then so is .
Proof. Let be relatively prime. We wish to prove that .
For , let be the set of divisors of . For relatively prime , we claim that the function is a bijection from to . Indeed, for any and , so . Furthermore, for each , there exist unique such that , , . Thus is bijective. As a result of our claim, we have the identity
,
for any functions mapping subsets of into . In particular, we may let the domains of and be , and define and . We then have
.
But since each divisor of is relatively prime to every divisor of , we have
,
as desired.
Resources
This article is a stub. Help us out by expanding it.