Namespaces
Variants
Actions

Difference between revisions of "Dirichlet convolution"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
The Dirichlet convolution of two arithmetical functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301501.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301502.png" /> is defined as
+
The Dirichlet convolution of two [[arithmetic function]]s $f(n)$ and $g(n)$ is defined as
 +
$$
 +
(f*g)(n) = \sum_{d|n} f(d) g(n/d) \ ,
 +
$$
 +
where the sum is over the positive divisors $d$ of $n$. General background material on the Dirichlet convolution can be found in, e.g., [[#References|[a1]]], [[#References|[a6]]], [[#References|[a8]]].
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301503.png" /></td> </tr></table>
+
Sums of the form $\sum_{d|n} f(d) g(n/d)$ played an important role from the very beginning of the theory of arithmetical functions. Many results from early times involved these sums. For example, in 1857 J. Liouville published a long list of arithmetical identities of this type (see [[#References|[a5]]]). It is fruitful to treat the sums $\sum_{d|n} f(d) g(n/d)$ as giving a binary operation on the set of arithmetical functions (cf. also [[Binary relation]]). This aspect was introduced by E.T. Bell [[#References|[a2]]] and M. Cipolla [[#References|[a3]]] in 1915.
  
where the sum is over the positive divisors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301504.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301505.png" /> (cf. also [[Arithmetic function|Arithmetic function]]). General background material on the Dirichlet convolution can be found in, e.g., [[#References|[a1]]], [[#References|[a6]]], [[#References|[a8]]].
+
The set of arithmetical functions forms a [[commutative ring]] with unity under the usual addition and the Dirichlet convolution. An arithmetical function $f$ possesses a Dirichlet inverse if and only if $f(1) /neq 0$. For example, the Dirichlet inverse of the constant function 1 is the [[Möbius function]] $\mu$. The [[Möbius inversion]] formula states that
 +
$$
 +
f(n) = \sum_{d|n} g(d) \Leftrightarrow g(n) = \sum_{d|n} \mu(d) f(n/d) \ .
 +
$$
  
Sums of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301506.png" /> played an important role from the very beginning of the theory of arithmetical functions. Many results from early times involved these sums. For example, in 1857 J. Liouville published a long list of arithmetical identities of this type (see [[#References|[a5]]]). It is fruitful to treat the sums <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301507.png" /> as giving a binary operation on the set of arithmetical functions (cf. also [[Binary relation|Binary relation]]). This aspect was introduced by E.T. Bell [[#References|[a2]]] and M. Cipolla [[#References|[a3]]] in 1915.
+
The relation of the Dirichlet convolution with [[Dirichlet series]] is also important.
 
 
The set of arithmetical functions forms a [[Commutative ring|commutative ring]] with unity under the usual addition and the Dirichlet convolution. An arithmetical function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301508.png" /> possesses a Dirichlet inverse if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d1301509.png" />. For example, the Dirichlet inverse of the constant function 1 is the [[Möbius function|Möbius function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015010.png" />. The Möbius inversion formula states that
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015011.png" /></td> </tr></table>
 
 
 
The relation of the Dirichlet convolution with [[Dirichlet series|Dirichlet series]] is also important.
 
  
 
There are many analogues and generalizations of the Dirichlet convolution; for example, E. Cohen [[#References|[a4]]] defined the unitary convolution as
 
There are many analogues and generalizations of the Dirichlet convolution; for example, E. Cohen [[#References|[a4]]] defined the unitary convolution as
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015012.png" /></td> </tr></table>
+
(f \times g)(n) = \sum_{d \Vert n} f(d) g(n/d) \ ,
 
+
$$
where the sum is over the positive divisors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015013.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015014.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015015.png" />, see also [[#References|[a10]]]. W. Narkiewicz [[#References|[a7]]] developed a more general convolution:
+
where the sum is over the [[unitary divisor]]s of $n$: the positive divisors $d$ of $n$ such that $\mathrm{hcf}(d,n/d) = 1$, see also [[#References|[a10]]]. W. Narkiewicz [[#References|[a7]]] developed a more general convolution:
 
+
$$
 +
(f *_A g)(n) = \sum_{d \in A(n)} f(d) g(n/d) \ ,
 +
$$
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015016.png" /></td> </tr></table>
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015016.png" /></td> </tr></table>
  
where, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015018.png" /> is a subset of the set of the positive divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130150/d13015019.png" />. See [[#References|[a9]]] for a survey of various binary operations on the set of arithmetical functions.
+
where, for each $n$, $A(n)$ is a subset of the set of the positive divisors of $n$. See [[#References|[a9]]] for a survey of various binary operations on the set of arithmetical functions.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T.M. Apostol,  "Introduction to analytic number theory" , Springer  (1976)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.T. Bell,  "An arithmetical theory of certain numerical functions"  ''Univ. Wash. Publ. Math. Phys. Sci.'' , '''I''' :  1  (1915)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Cipolla,  "Sui principi del calculo arithmetico integrale"  ''Atti Accad. Gioenia Cantonia'' , '''5''' :  8  (1915)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E. Cohen,  "Arithmetical functions associated with the unitary divisors of an integer"  ''Math. Z.'' , '''74'''  (1960)  pp. 66–80</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  L.E. Dickson,  "History of the theory of numbers" , '''I''' , Chelsea, reprint  (1952)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P.J. McCarthy,  "Introduction to arithmetical functions" , Springer  (1986)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  W. Narkiewicz,  "On a class of arithmetical convolutions"  ''Colloq. Math.'' , '''10'''  (1963)  pp. 81–94</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  R. Sivaramakrishnan,  "Classical theory of arithmetic functions" , ''Monographs and Textbooks in Pure and Applied Math.'' , '''126''' , M. Dekker  (1989)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  M.V. Subbarao,  "On some arithmetic convolutions" , ''The Theory of Arithmetic Functions'' , ''Lecture Notes in Mathematics'' , '''251''' , Springer  (1972)  pp. 247–271</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  R. Vaidyanathaswamy,  "The theory of multiplicative arithmetic functions"  ''Trans. Amer. Math. Soc.'' , '''33'''  (1931)  pp. 579–662</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  T.M. Apostol,  "Introduction to analytic number theory" , Springer  (1976)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  E.T. Bell,  "An arithmetical theory of certain numerical functions"  ''Univ. Wash. Publ. Math. Phys. Sci.'' , '''I''' :  1  (1915)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Cipolla,  "Sui principi del calculo arithmetico integrale"  ''Atti Accad. Gioenia Cantonia'' , '''5''' :  8  (1915)</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  E. Cohen,  "Arithmetical functions associated with the unitary divisors of an integer"  ''Math. Z.'' , '''74'''  (1960)  pp. 66–80</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  L.E. Dickson,  "History of the theory of numbers" , '''I''' , Chelsea, reprint  (1952)</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  P.J. McCarthy,  "Introduction to arithmetical functions" , Springer  (1986)</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  W. Narkiewicz,  "On a class of arithmetical convolutions"  ''Colloq. Math.'' , '''10'''  (1963)  pp. 81–94</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top">  R. Sivaramakrishnan,  "Classical theory of arithmetic functions" , ''Monographs and Textbooks in Pure and Applied Math.'' , '''126''' , M. Dekker  (1989)</TD></TR>
 +
<TR><TD valign="top">[a9]</TD> <TD valign="top">  M.V. Subbarao,  "On some arithmetic convolutions" , ''The Theory of Arithmetic Functions'' , ''Lecture Notes in Mathematics'' , '''251''' , Springer  (1972)  pp. 247–271</TD></TR>
 +
<TR><TD valign="top">[a10]</TD> <TD valign="top">  R. Vaidyanathaswamy,  "The theory of multiplicative arithmetic functions"  ''Trans. Amer. Math. Soc.'' , '''33'''  (1931)  pp. 579–662</TD></TR>
 +
</table>

Revision as of 22:26, 11 December 2014

The Dirichlet convolution of two arithmetic functions $f(n)$ and $g(n)$ is defined as $$ (f*g)(n) = \sum_{d|n} f(d) g(n/d) \ , $$ where the sum is over the positive divisors $d$ of $n$. General background material on the Dirichlet convolution can be found in, e.g., [a1], [a6], [a8].

Sums of the form $\sum_{d|n} f(d) g(n/d)$ played an important role from the very beginning of the theory of arithmetical functions. Many results from early times involved these sums. For example, in 1857 J. Liouville published a long list of arithmetical identities of this type (see [a5]). It is fruitful to treat the sums $\sum_{d|n} f(d) g(n/d)$ as giving a binary operation on the set of arithmetical functions (cf. also Binary relation). This aspect was introduced by E.T. Bell [a2] and M. Cipolla [a3] in 1915.

The set of arithmetical functions forms a commutative ring with unity under the usual addition and the Dirichlet convolution. An arithmetical function $f$ possesses a Dirichlet inverse if and only if $f(1) /neq 0$. For example, the Dirichlet inverse of the constant function 1 is the Möbius function $\mu$. The Möbius inversion formula states that $$ f(n) = \sum_{d|n} g(d) \Leftrightarrow g(n) = \sum_{d|n} \mu(d) f(n/d) \ . $$

The relation of the Dirichlet convolution with Dirichlet series is also important.

There are many analogues and generalizations of the Dirichlet convolution; for example, E. Cohen [a4] defined the unitary convolution as $$ (f \times g)(n) = \sum_{d \Vert n} f(d) g(n/d) \ , $$ where the sum is over the unitary divisors of $n$: the positive divisors $d$ of $n$ such that $\mathrm{hcf}(d,n/d) = 1$, see also [a10]. W. Narkiewicz [a7] developed a more general convolution: $$ (f *_A g)(n) = \sum_{d \in A(n)} f(d) g(n/d) \ , $$

where, for each $n$, $A(n)$ is a subset of the set of the positive divisors of $n$. See [a9] for a survey of various binary operations on the set of arithmetical functions.

References

[a1] T.M. Apostol, "Introduction to analytic number theory" , Springer (1976)
[a2] E.T. Bell, "An arithmetical theory of certain numerical functions" Univ. Wash. Publ. Math. Phys. Sci. , I : 1 (1915)
[a3] M. Cipolla, "Sui principi del calculo arithmetico integrale" Atti Accad. Gioenia Cantonia , 5 : 8 (1915)
[a4] E. Cohen, "Arithmetical functions associated with the unitary divisors of an integer" Math. Z. , 74 (1960) pp. 66–80
[a5] L.E. Dickson, "History of the theory of numbers" , I , Chelsea, reprint (1952)
[a6] P.J. McCarthy, "Introduction to arithmetical functions" , Springer (1986)
[a7] W. Narkiewicz, "On a class of arithmetical convolutions" Colloq. Math. , 10 (1963) pp. 81–94
[a8] R. Sivaramakrishnan, "Classical theory of arithmetic functions" , Monographs and Textbooks in Pure and Applied Math. , 126 , M. Dekker (1989)
[a9] M.V. Subbarao, "On some arithmetic convolutions" , The Theory of Arithmetic Functions , Lecture Notes in Mathematics , 251 , Springer (1972) pp. 247–271
[a10] R. Vaidyanathaswamy, "The theory of multiplicative arithmetic functions" Trans. Amer. Math. Soc. , 33 (1931) pp. 579–662
How to Cite This Entry:
Dirichlet convolution. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dirichlet_convolution&oldid=35562
This article was adapted from an original article by Pentti Haukkanen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article