Namespaces
Variants
Actions

Möbius inversion

From Encyclopedia of Mathematics
Jump to: navigation, search

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 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
How to Cite This Entry:
Möbius inversion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=M%C3%B6bius_inversion&oldid=54307
This article was adapted from an original article by Joseph P.S. Kung (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article