Möbius inversion

A method for inverting sums over partially ordered sets (or posets; cf. also Partially ordered set). The theory of Möbius inversion matured in the classic paper [a4] of G.-C. Rota and is a cornerstone of algebraic combinatorics (cf. also Combinatorics).

Let $P$ be a locally finite partially ordered set, that is, a poset in which every interval $\{ z : x \leq z \leq y \}$ is finite. The Möbius function $\mu$ of $P$ is the function on pairs of elements in $P$ defined by the following conditions: $\mu ( x , y ) = 0$ if $x \nleq y$, $\mu ( x , x ) = 1$ for all $x$, and the recursive relation

$$\begin{equation*} \sum _ { z : x \leq z \leq y } \mu ( x , z ) = 0 \text { if } x < y. \end{equation*}$$

When $P$ is finite, the function value $\mu ( x , y )$ is the $x y$-entry in the inverse of the incidence matrix of the partial order relation on $P$.

Let $f$, $g$ be functions defined from $P$ to a commutative ring $R$ with unity. The Möbius inversion formula states:

$$\begin{equation*} g ( x ) = \sum _ { y : y \leq x } f ( y ) \Leftrightarrow f ( x ) = \sum _ { y : y \leq x } g ( y ) \mu ( y , x ) \end{equation*}$$

or, dually,

$$\begin{equation*} g ( x ) = \sum _ { y : y \geq x } f ( y ) \Leftrightarrow f ( x ) = \sum _ { y : y \geq x } \mu ( x , y ) g ( y ). \end{equation*}$$

For the Boolean algebra $2 ^ { S }$ of all subsets of a set $S$, $\mu ( A , B ) = ( - 1 ) ^ { | B | - | A | }$ when $A \subseteq B$. When $S$ is thought of as a set of "properties" , the Möbius inversion formula yields the principle of inclusion-exclusion (cf. Inclusion-and-exclusion principle).

When $P$ is the distributive lattice of positive integers ordered by divisibility, the Möbius function $\mu ( m , n )$ equals $0$ unless $m$ divides $n$ and $n/m$ is square-free, in which case it equals $( - 1 ) ^ { e }$, where $e$ is the number of primes in the prime factorization of $n/m$. The classical or number-theoretic Möbius inversion formula states:

$$\begin{equation*} g ( n ) = \sum _ { d | n } f ( d ) \Leftrightarrow f ( n ) = \sum _ { d | n } g ( d ) \mu \left( \frac { n } { d } \right). \end{equation*}$$

For example, this yields the following formula for the Euler totient function $\phi ( n )$, the number of positive integers not exceeding $n$ that are relatively prime to $n$ (cf. also Euler function):

$$\begin{equation*} \phi ( n ) = \sum _ { d | n } d \mu \left( \frac { n } { d } \right) . \end{equation*}$$

The Möbius function satisfies many identities. Four often-used identities are:

a) The P. Hall identity:

$$\begin{equation*} \mu ( x , y ) = - C _ { 1 } + C _ { 2 } - C _ { 3 } + \ldots , \end{equation*}$$

where $C_i$ is the number of (strict) chains $x = x _ { 0 } < x _ { 1 } < \ldots < x _ { i - 1 } < x _ { i } = y$ with $i$ links starting at $x$ and ending at $y$ (cf. also Chain).

b) The Weisner theorem: Let $L$ be a finite lattice with minimum $0$. If $x$ and $y$ are elements of $L$ such that $x \geq y > 0$, then

$$\begin{equation*} \mu ( 0 , x ) = - \sum _ { u } \mu ( 0 , u ), \end{equation*}$$

the sum ranging over all elements $u$ such that $u \neq x$ and $u \vee y = x$.

c) The Crapo complementation theorem: An element $y$ is a complement of an element $x$ in a lattice $L$ with minimum $0$ and maximum $1$ if $y \vee x = 1$ and $y \wedge x = 0$. For any element $x$ in a finite lattice $L$,

$$\begin{equation*} \mu ( 0,1 ) = \sum _ { y , z } \mu ( 0 , y ) \mu ( z , 1 ), \end{equation*}$$

the sum ranging over all pairs $y$ and $z$ such that $y \leq z$ and both $y$ and $z$ are complements of $x$.

d) The Boolean expansion lemma: If $A \mapsto \bar{A}$ is a closure operator on a set $S$ (cf. also Closure space), then for a closed set $X$ in the lattice of closed sets,

$$\begin{equation*} \mu ( \overline { \emptyset } , X ) = \sum _ { A : \overline { A } = X } ( - 1 ) ^ { | A | } \end{equation*}$$

The Boolean expansion lemma is a special case of the Galois connection theorem. It is also a special case of the cross-cut theorem. A cross-cut $C$ in a finite lattice $L$ is a set of elements of $L$ satisfying:

1) $C$ does not contain the minimum $0$ or the maximum $1:$

2) no pair of elements of $C$ is comparable;

3) any maximal chain from $0$ to $1$ has non-empty intersection with $C$. A subset $S$ of elements of $L$ is spanning if both the join of all the elements in $S$ is $1$ and the meet of all the elements in $S$ is $0$. If $L$ is a finite lattice with more than two elements and $C$ is a cross-cut in $L$, then

$$\begin{equation*} \mu ( 0,1 ) = q _ { 2 } - q _ { 3 } + q _ { 4 } - \ldots , \end{equation*}$$

where $q_k$ is the number of spanning subsets of $C$ with $k$ elements.

Besides order-theoretic, homological and counting proofs of these results, there are also proofs using the Möbius algebra, a generalization of the Burnside algebra of a group.

Much work has been done on calculating Möbius functions of specific partially ordered sets. For example, if $U$ and $V$ are subspaces in the lattice of subspaces of a finite-dimensional vector space over a finite field of order $q$ and $U \subseteq V$, then

$$\begin{equation*} \mu ( U , V ) = ( - 1 ) ^ { d } q ^ { d ( d - 1 ) / 2 }, \end{equation*}$$

where $d$ is the difference $\operatorname { dim }V - \operatorname { dim } U$.

There are many results relating structural properties and properties of the Möbius function. Two examples follow. For an element $x$ in a lattice, $\mu ( 0 , x ) \neq 0$ only if the element $x$ is a join of atoms. (Atoms are elements covering the minimum $0$; cf. also Atom.) If $L$ is a finite lattice in which $\mu ( x , 1 )$ is non-zero for all elements $x$, then there exists a bijection $\gamma$ from $L$ to itself such that for every $x$, $\gamma ( x ) \vee x$ is the maximum $1$.

Möbius functions occur in many proofs. For example, they are heavily used in the original proof of Dilworth's theorem that in a finite modular lattice, the number of elements covering $k$ or fewer elements equals the number of elements covered by $k$ or fewer elements, and its extension, that the incidence matrix or combinatorial Radon transform between these two sets of elements is invertible.

The Möbius function has a homological interpretation. The value $\mu ( 0,1 ) + 1$ for a partially ordered set $P$ with minimum $0$ and maximum $1$ is the Euler characteristic of the order complex of $P$, the simplicial complex whose simplices are the chains of $P \backslash \{ 0,1 \}$, the partially ordered set $P$ with $0$ and $1$ deleted. Because polytopes are topologically spheres, this yields the following theorem. If $E$ and $F$ are faces in the face lattice of a polytope and $E \subseteq F$, then $\mu ( E , F ) = ( - 1 ) ^ { d }$, where $d$ is the difference $\operatorname { dim } F - \operatorname { dim } E$. Taking the nerve of a covering of the order complex (cf. also Nerve of a family of sets), one obtains a homology based on a cross-cut and the cross-cut theorem.

The homological interpretation is especially interesting for a geometric lattice $L$. In this case, the only non-trivial homology groups (cf. Homology group) are $H _ { 0 }$ and $H _ { n - 2 }$, where $n$ is the rank of $L$, and $| \mu ( 0,1 ) |$ is the rank or dimension of the top homology group $H _ { n - 2 }$. Rota has proved the following sign theorem: If $X$ is a rank-$k$ flat in a geometric lattice, then $( - 1 ) ^ { k } \mu ( 0 , X )$ is positive. Indeed, $( - 1 ) ^ { k } \mu ( 0 , X )$ counts certain subsets in the broken-circuit complex defined by H. Whitney.

The characteristic polynomial $\chi ( L ; \lambda )$ of a ranked partially ordered set $L$ is the polynomial

$$\begin{equation*} \sum _ { X : X \in L } \mu ( 0 , X ) \lambda ^ { \operatorname { rank } ( L ) - \operatorname { rank } ( X ) } \end{equation*}$$

in the variable $\lambda$. With simple modifications, one can obtain from the characteristic polynomial of a geometric lattice the Poincaré polynomial of an arrangement of hyperplanes and the chromatic polynomial of a graph (cf. also Graph colouring). The characteristic polynomial is an essential tool in the critical problem for matroids (cf. also Matroid). Related to the characteristic polynomial is the Eulerian function $\phi ( G ; s )$ of a finite group $G$, defined to be the Dirichlet polynomial

$$\begin{equation*} \sum _ { H : H \leq G } \mu ( H , G ) | H | ^ { S }, \end{equation*}$$

where the sum ranges over all subgroups in the subgroup lattice of $G$. When $s$ is a positive integer, $\phi ( G ; s )$ is the number of $s$-tuples of group elements whose underlying set generate $G$.

The Möbius invariant $\mu ( M )$ of a matroid $M$ is the integer $| \mu ( 0,1 ) |$ with $\mu$ calculated in its lattice of flats if $M$ has no loops, and $0$ otherwise. Except when the element $a$ is an isthmus, $\mu ( M )$ satisfies the relation

$$\begin{equation*} \mu ( M ) = \mu ( M \backslash a ) - \mu ( M / a ), \end{equation*}$$

where $M \backslash a$ is $M$ with $a$ deleted and $M / a$ is $M$ contracted at $a$. The triple $( M \backslash a , M , M / a )$ is an analogue of a short exact sequence (cf. also Exact sequence). Many other invariants (including the characteristic polynomial) satisfy contraction-and-deletion relations. In addition, inductive arguments involving contractions and deletions are often used in proofs.

References

[a1]	M. Barnabei, A. Brini, G.-C. Rota, "Theory of Möbius functions" Russian Math. Surveys , 3 (1986) pp. 135–188
[a2]	A. Björner, "Homology and shellability of matroids and geometric lattices" N.L. White (ed.) , Matroid Applications , Cambridge Univ. Press (1992) pp. 226–283
[a3]	J.P.S. Kung, "Radon transforms in combinatorics and lattice theory" I. Rival (ed.) , Combinatorics and Ordered Sets , Amer. Math. Soc. (1986) pp. 33–74
[a4]	G.-C. Rota, "On the foundations of combinatorial theory I: Theory of Möbius functions" Z. Wahrsch. Verw. Gebiete , 2 (1964) pp. 340–368