Namespaces
Variants
Actions

Difference between revisions of "Möbius inversion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(gt to >)
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
<!--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]]).
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301801.png" /> be a locally finite partially ordered set, that is, a poset in which every interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301802.png" /> is finite. The Möbius function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301803.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301804.png" /> is the function on pairs of elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301805.png" /> defined by the following conditions: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301806.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301807.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301808.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m1301809.png" />, and the recursive relation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018010.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { z : x \leq z \leq y } \mu ( x , z ) = 0 \text { if } x < y. \end{equation*}
  
When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018011.png" /> is finite, the function value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018012.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018013.png" />-entry in the inverse of the incidence matrix of the partial order relation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018014.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018016.png" /> be functions defined from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018017.png" /> to a [[Commutative ring|commutative ring]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018018.png" /> with unity. The Möbius inversion formula states:
+
Let $f$, $g$ be functions defined from $P$ to a [[Commutative ring|commutative ring]] $R$ with unity. The Möbius inversion formula states:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018019.png" /></td> </tr></table>
+
\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,
 
or, dually,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018020.png" /></td> </tr></table>
+
\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]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018021.png" /> of all subsets of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018023.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018024.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018025.png" /> 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]]).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018026.png" /> is the [[Distributive lattice|distributive lattice]] of positive integers ordered by divisibility, the Möbius function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018027.png" /> equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018028.png" /> unless <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018029.png" /> divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018031.png" /> is square-free, in which case it equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018033.png" /> is the number of primes in the prime factorization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018034.png" />. The classical or number-theoretic Möbius inversion formula states:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018035.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018036.png" />, the number of positive integers not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018037.png" /> that are relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018038.png" /> (cf. also [[Euler function|Euler function]]):
+
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]]):
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018039.png" /></td> </tr></table>
+
\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:
 
The Möbius function satisfies many identities. Four often-used identities are:
Line 29: Line 37:
 
a) The P. Hall identity:
 
a) The P. Hall identity:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018040.png" /></td> </tr></table>
+
\begin{equation*} \mu ( x , y ) = - C _ { 1 } + C _ { 2 } - C _ { 3 } + \ldots , \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018041.png" /> is the number of (strict) chains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018042.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018043.png" /> links starting at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018044.png" /> and ending at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018045.png" /> (cf. also [[Chain|Chain]]).
+
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|Chain]]).
  
b) The Weisner theorem: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018046.png" /> be a finite [[Lattice|lattice]] with minimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018047.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018048.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018049.png" /> are elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018050.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018051.png" />, then
+
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 > 0$, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018052.png" /></td> </tr></table>
+
\begin{equation*} \mu ( 0 , x ) = - \sum _ { u } \mu ( 0 , u ), \end{equation*}
  
the sum ranging over all elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018053.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018054.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018055.png" />.
+
the sum ranging over all elements $u$ such that $u \neq x$ and $u \vee y = x$.
  
c) The Crapo complementation theorem: An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018056.png" /> is a complement of an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018057.png" /> in a lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018058.png" /> with minimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018059.png" /> and maximum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018060.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018061.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018062.png" />. For any element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018063.png" /> in a finite lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018064.png" />,
+
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$,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018065.png" /></td> </tr></table>
+
\begin{equation*} \mu ( 0,1 ) = \sum _ { y , z } \mu ( 0 , y ) \mu ( z , 1 ), \end{equation*}
  
the sum ranging over all pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018067.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018068.png" /> and both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018070.png" /> are complements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018071.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018072.png" /> is a closure operator on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018073.png" /> (cf. also [[Closure space|Closure space]]), then for a closed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018074.png" /> in the lattice of closed sets,
+
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,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018075.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018076.png" /> in a finite lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018077.png" /> is a set of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018078.png" /> satisfying:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018079.png" /> does not contain the minimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018080.png" /> or the maximum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018081.png" />
+
1) $C$ does not contain the minimum $0$ or the maximum $1:$
  
2) no pair of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018082.png" /> is comparable;
+
2) no pair of elements of $C$ is comparable;
  
3) any maximal chain from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018083.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018084.png" /> has non-empty intersection with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018085.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018086.png" /> of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018087.png" /> is spanning if both the join of all the elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018088.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018089.png" /> and the meet of all the elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018090.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018091.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018092.png" /> is a finite lattice with more than two elements and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018093.png" /> is a cross-cut in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018094.png" />, then
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018095.png" /></td> </tr></table>
+
\begin{equation*} \mu ( 0,1 ) = q _ { 2 } - q _ { 3 } + q _ { 4 } - \ldots , \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018096.png" /> is the number of spanning subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018097.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018098.png" /> elements.
+
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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m13018099.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180100.png" /> are subspaces in the lattice of subspaces of a finite-dimensional vector space over a finite field of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180101.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180102.png" />, then
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180103.png" /></td> </tr></table>
+
\begin{equation*} \mu ( U , V ) = ( - 1 ) ^ { d } q ^ { d ( d - 1 ) / 2 }, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180104.png" /> is the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180105.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180106.png" /> in a lattice, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180107.png" /> only if the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180108.png" /> is a join of atoms. (Atoms are elements covering the minimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180109.png" />; cf. also [[Atom|Atom]].) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180110.png" /> is a finite lattice in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180111.png" /> is non-zero for all elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180112.png" />, then there exists a bijection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180113.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180114.png" /> to itself such that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180115.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180116.png" /> is the maximum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180117.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180118.png" /> or fewer elements equals the number of elements covered by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180119.png" /> or fewer elements, and its extension, that the incidence matrix or combinatorial Radon transform between these two sets of elements is invertible.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180120.png" /> for a partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180121.png" /> with minimum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180122.png" /> and maximum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180123.png" /> is the [[Euler characteristic|Euler characteristic]] of the order complex of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180124.png" />, the [[Simplicial complex|simplicial complex]] whose simplices are the chains of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180125.png" />, the partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180126.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180127.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180128.png" /> deleted. Because polytopes are topologically spheres, this yields the following theorem. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180129.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180130.png" /> are faces in the face lattice of a polytope and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180131.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180132.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180133.png" /> is the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180134.png" />. 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 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180135.png" />. In this case, the only non-trivial homology groups (cf. [[Homology group|Homology group]]) are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180136.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180137.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180138.png" /> is the rank of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180139.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180140.png" /> is the rank or dimension of the top homology group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180141.png" />. Rota has proved the following sign theorem: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180142.png" /> is a rank-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180143.png" /> flat in a geometric lattice, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180144.png" /> is positive. Indeed, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180145.png" /> counts certain subsets in the broken-circuit complex defined by H. Whitney.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180146.png" /> of a ranked partially ordered set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180147.png" /> is the polynomial
+
The characteristic polynomial $\chi ( L ; \lambda )$ of a [[ranked poset|ranked partially ordered set]] $L$ is the polynomial
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180148.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { X : X \in L } \mu ( 0 , X ) \lambda ^ { \operatorname { rank } ( L ) - \operatorname { rank } ( X ) } \end{equation*}
  
in the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180149.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180150.png" /> of a finite group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180151.png" />, defined to be the Dirichlet polynomial
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180152.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180153.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180154.png" /> is a positive integer, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180155.png" /> is the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180156.png" />-tuples of group elements whose underlying set generate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180157.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180158.png" /> of a matroid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180159.png" /> is the integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180160.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180161.png" /> calculated in its lattice of flats if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180162.png" /> has no loops, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180163.png" /> otherwise. Except when the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180164.png" /> is an isthmus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180165.png" /> satisfies the relation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180166.png" /></td> </tr></table>
+
\begin{equation*} \mu ( M ) = \mu ( M \backslash a ) - \mu ( M / a ), \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180167.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180168.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180169.png" /> deleted and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180170.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180171.png" /> contracted at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180172.png" />. The triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130180/m130180173.png" /> 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.
+
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====
 
====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>
+
<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>

Latest revision as of 09:24, 10 November 2023

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
How to Cite This Entry:
Möbius inversion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=M%C3%B6bius_inversion&oldid=16520
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