Möbius inversion formula

The classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. It was later generalized to other "Möbius inversion formulas"; see incidence algebra. The classic version states that if g(n) and f(n) are arithmetic functions satisfying

$g(n)=\sum _{d\,\mid \,n}f(d)\quad {\mbox{for every integer }}n\geq 1$

then

$f(n)=\sum _{d\,\mid \,n}g(d)\mu (n/d)\quad {\mbox{for every integer }}n\geq 1$

where μ is the Möbius function and the sums extend over all positive divisors d of n. In effect, the original f(n) can be determined given g(n) by using the inversion formula. The two sequences are said to be Möbius transforms of each other.

The formula is also correct if f and g are functions from the positive integers into some abelian group.

In the language of convolutions (see multiplicative function and Dirichlet convolution), the inversion formula can also be expressed as

μ * 1 = ε.

An equivalent formulation of the inversion formula more useful in combinatorics is as follows: suppose F(x) and G(x) are complex-valued functions defined on the interval [1,∞) such that

$G(x)=\sum _{1\leq n\leq x}F(x/n)\quad {\mbox{ for all }}x\geq 1$

then

$F(x)=\sum _{1\leq n\leq x}\mu (n)G(x/n)\quad {\mbox{ for all }}x\geq 1.$

Here the sums extend over all positive integers n which are less than or equal to x.

The Möbius inversion treated above is the original Möbius inversion. When the partially ordered set of natural numbers ordered by divisibility one is replaced by other locally finite partially ordered sets, one has other Möbius inversion formulas; for an account of those, see incidence algebra.

Common functions

A series of functions on the positive integers can be defined by the transform in the first equation above. If one starts with Euler's totient function and repeatedly apply the transformation process, the following functions are the result:

(1) $\phi (n)$ Totient function

(2) $f(n)=n$ identity function

(3) $\sigma (n)$ Divisor function

If the starting function is the Möbius function itself, the list of functions is:

(1) $\mu (n)$ Möbius function

(2)$\epsilon (n)={\begin{cases}1,&{\mbox{if }}n{\mbox{=1}}\\0,&{\mbox{if }}n{>1}\end{cases}}$ the unit function, also written as u(n)

(3) $f(n)=1$ constant function 1

(4) $\tau (n)$ (number of divisors of n, see Divisor function)

Both of these lists of functions extend infinitely in both directions. The Möbius Inversion formula enables these lists to be traversed backwards.

Generalisations

There is also a multiplicative version of the Möbius inversion formula, which can be proved by an exactly similar proof, and which holds in abelian groups:

${\mbox{If }}F(n)=\prod _{d|n}f(d),{\mbox{ then }}f(n)=\prod _{d|n}F(n/d)^{\mu (n/d)}.$

Physics

Physicists have shown that the Möbius inversion formula can, in the context of a theory with a logarithmic spectrum, be obtained by means of supersymmetry and a Witten index calculation.

See also

• Lambert series.