(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Möbius inversion

(Topic)

Theorem 1 (Moebius Inversion) Let $\mu$ be the Moebius function, and let and be two functions on the positive integers. Then the following two conditions are equivalent:

$\displaystyle f(n)$	$\displaystyle =$	$\displaystyle \sum_{d\vert n}g(d)\textrm{ for all }n\in\mathbb{N}^{*}$	(1)
$\displaystyle g(n)$	$\displaystyle =$	$\displaystyle \sum_{d\vert n}\mu(d)f\left(\frac{n}{d}\right)\textrm{ for all }n\in\mathbb{N}^{*}$	(2)

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

$\displaystyle \sum_{d\vert n}\mu(d)f\left(\frac{n}{d}\right)$	$\displaystyle =$	$\displaystyle \sum_{d\vert n}\mu(d)\sum_{e\vert n/d}g(e)$
	$\displaystyle =$	$\displaystyle \sum_{k\vert n}\sum_{d\vert k}\mu(d)g\left(\frac{n}{k}\right)$
	$\displaystyle =$	$\displaystyle \sum_{k\vert n}g\left(\frac{n}{k}\right)\sum_{d\vert k}\mu(d)$
	$\displaystyle =$	$\displaystyle g(n),$

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

Conversely, assuming (2), we get

$\displaystyle \sum_{d\vert n}g(d)$	$\displaystyle =$	$\displaystyle \sum_{d\vert n}\sum_{e\vert d}\mu(e)f\left(\frac{d}{e}\right)$
	$\displaystyle =$	$\displaystyle \sum_{k\vert n}f\left(\frac{n}{k}\right)\sum_{e\vert k}\mu\left(\frac{k}{e}\right)$
	$\displaystyle =$	$\displaystyle f(n)$ (by the same identity)

as claimed.

Definitions: In the notation above, is called the Möbius transform of , 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\vert y$ between elements

and

, 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\vert x\le z\le y\}$ is a finite set for all $x,y\in S$ . Let be the set of functions $\alpha:S\times S\to\mathbb{Z}$ such that

$\displaystyle \alpha(x,x)$	$\displaystyle =$	$\displaystyle 1\textrm{ for all }x\in S$	(3)
$\displaystyle \alpha(x,y)$	$\displaystyle \neq$	$\displaystyle 0\textrm{ implies }x\leq y$	(4)

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

$\displaystyle (\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 nonzero for only finitely many values of

. (Clearly this definition is akin to the definition of the product of two square matrices.)

Consider the element $\iota$ of defined simply by

$\begin{displaymath}\iota(x,y)= \begin{cases} 1 & \textrm{ if $x\le y$} \\ 0 & \text{otherwise.} \end{cases}\end{displaymath}$

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

$\begin{displaymath} \sum_{t\in S}\iota(x,t)\nu(t,y)= \begin{cases} 1 & \text{if $x=y$,} \\ 0 & \text{otherwise.} \end{cases}\end{displaymath}$

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

$\displaystyle f$	$\displaystyle =$	$\displaystyle \iota g$	(5)
$\displaystyle g$	$\displaystyle =$	$\displaystyle \nu f$	(6)

are equivalent.

Now let's sketch out how the traditional Möbius inversion is a special case of Rota's notion. Let be the set $\mathbb{N}^{*}$ , ordered by the relation $x\vert y$ between elements and . In this case, $\nu$ is essentially a 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\vert y$ .

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

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

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

A slightly more sophisticated example comes up in connection 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 rather than over the divisors of an integer. Specifically, let $f:\mathbb{R}\rightarrow\mathbb{C}$ and define $F:\mathbb{R}\rightarrow \mathbb{C}$ by $F(x)=\sum_{n\leq x} f(\frac{x}{n})$ .

Then

$\displaystyle f(x)=\sum_{n\leq x} \mu(n) F\left(\frac{x}{n}\right).$

"Möbius inversion" is owned by mathcam. [ full author list (3) | owner history (2) ]

(view preamble)