View source for Möbius inversion

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 173 formulas, 173 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
A method for inverting sums over partially ordered sets (or posets; cf. also [[Partially ordered set|Partially ordered set]]). The theory of Möbius inversion matured in the classic paper [[#References|[a4]]] of G.-C. Rota and is a cornerstone of algebraic combinatorics (cf. also [[Combinatorics|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 &lt; 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|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|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|Inclusion-and-exclusion principle]]).

When $P$ is the [[Distributive lattice|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|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 } &lt; x _ { 1 } &lt; \ldots &lt; x _ { i - 1 } &lt; x _ { i } = y$ with $i$ links starting at $x$ and ending at $y$ (cf. also [[Chain|Chain]]).

b) The Weisner theorem: Let $L$ be a finite [[Lattice|lattice]] with minimum $0$. If $x$ and $y$ are elements of $L$ such that $x \geq y &gt; 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|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|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|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|Euler characteristic]] of the order complex of $P$, the [[Simplicial complex|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|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|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 poset|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|arrangement of hyperplanes]] and the chromatic polynomial of a graph (cf. also [[Graph colouring|Graph colouring]]). The characteristic polynomial is an essential tool in the critical problem for matroids (cf. also [[Matroid|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|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====
<table><tr><td valign="top">[a1]</td> <td valign="top">  M. Barnabei,   A. Brini,   G.-C. Rota,   "Theory of Möbius functions"  ''Russian Math. Surveys'' , '''3'''  (1986)  pp. 135–188</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  A. Björner,   "Homology and shellability of matroids and geometric lattices"  N.L. White (ed.) , ''Matroid Applications'' , Cambridge Univ. Press  (1992)  pp. 226–283</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  G.-C. Rota,   "On the foundations of combinatorial theory I: Theory of Möbius functions"  ''Z. Wahrsch. Verw. Gebiete'' , '''2'''  (1964)  pp. 340–368</td></tr></table>