§27.5 Inversion Formulas

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

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(\NVar{n}\right)$: Möbius function, $\left\lfloor\NVar{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).$

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),$
 27.5.5 $\mathop{\ln\/}\nolimits n=\sum_{d\divides n}\mathop{\Lambda\/}\nolimits\!\left% (d\right)\Longleftrightarrow\mathop{\Lambda\/}\nolimits\!\left(n\right)=\sum_{% d\divides n}(\mathop{\ln\/}\nolimits d)\mathop{\mu\/}\nolimits\!\left(\frac{n}% {d}\right).$ Symbols: $\mathop{\Lambda\/}\nolimits\!\left(\NVar{n}\right)$: Mangoldt’s function, $\mathop{\mu\/}\nolimits\!\left(\NVar{n}\right)$: Möbius function, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $d$: positive integer and $n$: positive integer Permalink: http://dlmf.nist.gov/27.5.E5 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08

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),$
 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}},$
 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)}.$

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