§ 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),$

Defines:: $f$ : function, $g$ : function and $h$ : function
Symbols:: $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.5.E1
Encodings:: TeX, pMathML, 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 $\zeta\!\left(s\right)\cdot(\ifrac{1}{\zeta\!\left(s\right)})=1$ is equivalent to the identity

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

Symbols:: $\mu\!\left(n\right)$ : Möbius function, $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, pMathML, 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)\mu\!\left(\frac{n}{d}\right).$

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

Special cases of Möbius inversion pairs are:

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

Symbols:: $\phi\!\left(n\right)$ : Euler's totient function, $\mu\!\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, pMathML, png

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

Symbols:: $\Lambda\!\left(n\right)$ : Mangoldt's function, $\mu\!\left(n\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.5.E5
Encodings:: TeX, pMathML, 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}}\mu\!\left(n\right)G\left(\frac{x}{n}\right),$

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

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

Defines:: $F(s)$ : Dirichlet series and $G(s)$ : Dirichlet series
Symbols:: $\mu\!\left(n\right)$ : Möbius function, $m$ : positive integer and $x$ : real number
Referenced by:: §27.17, §27.5
Permalink:: http://dlmf.nist.gov/27.5.E7
Encodings:: TeX, pMathML, 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)^{{\mu\!\left(d\right)}}.$

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

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