§27.5 Inversion Formulas

Notes:: See Apostol (1976, Chapter 2 and p. 228). For (27.5.7) use (27.5.2) and formal substitution.
Keywords:: Dirichlet product (or convolution), Möbius inversion formulas, number-theoretic functions, number theory
Permalink:: http://dlmf.nist.gov/27.5

If a Dirichlet series $F(s)$ generates $f(n)$ , and $G(s)$ generates $g(n)$ , then the product $F(s)G(s)$ generates

27.5.1 $h(n)=\sum _{{d\divides n}}f(d)g\left(\frac{n}{d}\right),$

Symbols:: $d$ : positive integer, $n$ : positive integer, $f$ : function, $g$ : function and $h$ : function
Permalink:: http://dlmf.nist.gov/27.5.E1
Encodings:: TeX, pMML, png

called the Dirichlet product (or convolution) of $f$ and $g$ . The set of all number-theoretic functions $f$ with $f(1)\neq 0$ forms an abelian group under Dirichlet multiplication, with the function $\left\lfloor 1/n\right\rfloor$ in (27.2.5) as identity element; see Apostol (1976, p. 129). The multiplicative functions are a subgroup of this group. Generating functions yield many relations connecting number-theoretic functions. For example, the equation $\mathop{\zeta\/}\nolimits\!\left(s\right)\cdot(\ifrac{1}{\mathop{\zeta\/}\nolimits\!\left(s\right)})=1$ is equivalent to the identity

27.5.2 $\sum _{{d\divides n}}\mathop{\mu\/}\nolimits\!\left(d\right)=\left\lfloor\frac{1}{n}\right\rfloor,$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $\left\lfloor x\right\rfloor$ : floor of $x$ , $d$ : positive integer and $n$ : positive integer
A&S Ref:: 24.3.1 II.B (in slightly different form)
Referenced by:: §27.5
Permalink:: http://dlmf.nist.gov/27.5.E2
Encodings:: TeX, pMML, png

which, in turn, is the basis for the Möbius inversion formula relating sums over divisors:

27.5.3 $g(n)=\sum _{{d\divides n}}f(d)\Longleftrightarrow f(n)=\sum _{{d\divides n}}g(d)\mathop{\mu\/}\nolimits\!\left(\frac{n}{d}\right).$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer, $n$ : positive integer, $f$ : function and $g$ : function
A&S Ref:: 24.3.1 II.C
Permalink:: http://dlmf.nist.gov/27.5.E3
Encodings:: TeX, pMML, png

Special cases of Möbius inversion pairs are:

27.5.4 $n=\sum _{{d\divides n}}\mathop{\phi\/}\nolimits\!\left(d\right)\Longleftrightarrow\mathop{\phi\/}\nolimits\!\left(n\right)=\sum _{{d\divides n}}d\mathop{\mu\/}\nolimits\!\left(\frac{n}{d}\right),$

Symbols:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$ , $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer
A&S Ref:: 24.3.2 II.B
Permalink:: http://dlmf.nist.gov/27.5.E4
Encodings:: TeX, pMML, png

27.5.5 $\mathop{\mathrm{log}\,\/}\nolimits n=\sum _{{d\divides n}}\mathop{\Lambda\/}\nolimits\!\left(d\right)\Longleftrightarrow\mathop{\Lambda\/}\nolimits\!\left(n\right)=\sum _{{d\divides n}}(\mathop{\mathrm{log}\,\/}\nolimits d)\mathop{\mu\/}\nolimits\!\left(\frac{n}{d}\right).$

Symbols:: $\mathop{\Lambda\/}\nolimits\!\left(n\right)$ : Mangoldt’s function, $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.5.E5
Encodings:: TeX, pMML, png

Other types of Möbius inversion formulas include:

27.5.6 $G(x)=\sum _{{n\leq x}}F\left(\frac{x}{n}\right)\Longleftrightarrow F(x)=\sum _{{n\leq x}}\mathop{\mu\/}\nolimits\!\left(n\right)G\left(\frac{x}{n}\right),$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $n$ : positive integer, $x$ : real number, $F(s)$ : Dirichlet series and $G(s)$ : Dirichlet series
A&S Ref:: 24.3.1 II.C
Permalink:: http://dlmf.nist.gov/27.5.E6
Encodings:: TeX, pMML, png

27.5.7 $G(x)=\sum _{{m=1}}^{\infty}\frac{F(mx)}{m^{s}}\Longleftrightarrow F(x)=\sum _{{m=1}}^{\infty}\mathop{\mu\/}\nolimits\!\left(m\right)\frac{G(mx)}{m^{s}},$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $m$ : positive integer, $x$ : real number, $F(s)$ : Dirichlet series and $G(s)$ : Dirichlet series
Referenced by:: §27.17, §27.5
Permalink:: http://dlmf.nist.gov/27.5.E7
Encodings:: TeX, pMML, png

27.5.8 $g(n)=\prod _{{d\divides n}}f(d)\Longleftrightarrow f(n)=\prod _{{d\divides n}}\left(g\left(\frac{n}{d}\right)\right)^{{\mathop{\mu\/}\nolimits\!\left(d\right)}}.$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer, $n$ : positive integer, $f$ : function and $g$ : function
A&S Ref:: 24.3.1 II.C
Permalink:: http://dlmf.nist.gov/27.5.E8
Encodings:: TeX, pMML, png

For a general theory of Möbius inversion with applications to combinatorial theory see Rota (1964).