Möbius inversion

Theorem 1 (Moebius Inversion).

Let $\mu$ be the Moebius function, and let $f$ and $g$ be two functions on the positive integers. Then the following two conditions are equivalent:

$f(n)$$=$${\displaystyle \sum _{d|n}}g(d)\mathit{\text{ for all }}n\in {\mathbb{N}}^{*}$(1)

$g(n)$$=$${\displaystyle \sum _{d|n}}\mu (d)f\left({\displaystyle \frac{n}{d}}\right)\mathit{\text{ for all }}n\in {\mathbb{N}}^{*}$(2)

Proof: Fix some $n\in {\mathbb{N}}^{*}$. Assuming (1), we have

${\displaystyle \sum _{d|n}}\mu (d)f\left({\displaystyle \frac{n}{d}}\right)$$=$${\displaystyle \sum _{d|n}}\mu (d){\displaystyle \sum _{e|n/d}}g(e)$

$=$${\displaystyle \sum _{k|n}}{\displaystyle \sum _{d|k}}\mu (d)g\left({\displaystyle \frac{n}{k}}\right)$

$=$${\displaystyle \sum _{k|n}}g\left({\displaystyle \frac{n}{k}}\right){\displaystyle \sum _{d|k}}\mu (d)$

$=$$g(n),$

the last step following from the identity given in the Mobius function entry.

Conversely, assuming (2), we get

${\displaystyle \sum _{d|n}}g(d)$$=$${\displaystyle \sum _{d|n}}{\displaystyle \sum _{e|d}}\mu (e)f\left({\displaystyle \frac{d}{e}}\right)$

$=$${\displaystyle \sum _{k|n}}f\left({\displaystyle \frac{n}{k}}\right){\displaystyle \sum _{e|k}}\mu \left({\displaystyle \frac{k}{e}}\right)$

$=$$f(n)\mathit{\hspace{1em}\hspace{1em}}\text{(by the same identity)}$

as claimed.

Definitions: In the notation above, $f$ is called the Möbius transformof $g$, and formula (2) is called the Möbius inversion formula.

Möbius-Rota inversion

G.-C. Rota has described a generalization of the Möbius formalism.In it, the set ${\mathbb{N}}^{*}$, ordered by the relation $x|y$ between elements$x$ and $y$, is replaced by a more general ordered set, and $\mu$is replaced by a function of two variables.

Let $(S,\le )$ be a locally finite ordered set, i.e. an ordered set such that$\{z\in S|x\le z\le y\}$ is a finite set for all $x,y\in S$. Let $A$ be the setof functions $\alpha :S\times S\to \mathbb{Z}$ such that

$\alpha (x,x)$$=$$1\text{ for all }x\in S$(3)

$\alpha (x,y)$$\ne$$0\text{ implies }x\le y$(4)

$A$ becomes a monoid if we define the product of any two of itselements, say $\alpha$ and $\beta$, by

$$(\alpha \beta )(x,y)=\sum _{t\in S}\alpha (x,t)\beta (t,y).$$

The sum makes sense because $\alpha (x,t)\beta (t,y)$ is nonzerofor only finitely many values of $t$.(Clearly this definition is akin to the definition of the productof two square matrices.)

Consider the element $\iota$ of $A$ defined simply by

The function $\iota$, regarded as a matrix over $\mathbb{Z}$, has an inversematrix, say $\nu$. That means

Thus for any $f,g\in A$, the equations

$f$$=$$\iota g$(5)

$g$$=$$\nu f$(6)

are equivalent.

Now let’s sketch out how the traditional Möbius inversion is a specialcase of Rota’s notion. Let $S$ be the set ${\mathbb{N}}^{*}$, ordered by the relation$x|y$ between elements $x$ and $y$. In this case, $\nu$ is essentiallya function of only one variable:

Proposition 3: With the above notation, $\nu (x,y)=\mu (y/x)$for all $x,y\in {\mathbb{N}}^{*}$ such that $x|y$.

The proof is fairly straightforward, by induction on the numberof elements of the interval $\{z\in S|x\le z\le y\}$.

Now let $g$ be a function from ${\mathbb{N}}^{*}$ to some additive group,and write $\overline{g}(x,y)=g(y/x)$ for all pairs $(x,y)$ suchthat $x|y$.

Example: Let $E$ be a set, and let $S$ be the set of allfinite subsets of $E$, ordered by inclusion. The ordered set $S$ isleft-finite, and for any $x,y\in S$ such that $x\subset y$,we have $\nu (x,y)={(-1)}^{|y-x|}$, where $|z|$ denotes the cardinalof the finite set $z$.

A slightly more sophisticated example comes up inconnection with the chromatic polynomial of a graph or matroid.

An Additional Generalization

A final generalization of Moebius inversion occurs when the sum is taken over all integers less than some real value $x$ rather than over the divisors of an integer. Specifically, let $f:ℝ\to ℂ$ and define $F:ℝ\to ℂ$ by $F(x)={\sum }_{n\le x}f(\frac{x}{n})$.

Then

$f(x)={\displaystyle \sum _{n\le x}}\mu (n)F\left({\displaystyle \frac{x}{n}}\right).$

Title	Möbius inversion
Canonical name	MobiusInversion
Date of creation	2013-03-22 11:46:58
Last modified on	2013-03-22 11:46:58
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	25
Author	mathcam (2727)
Entry type	Topic
Classification	msc 11A25
Synonym	Moebius inversion
Related topic	MoebiusFunction
Defines	Mobius inversion formula
Defines	Mobius transform
Defines	Mobius function
Defines	Mobius-Rota inversion