nLab
Möbius inversion

Contents

Idea

The classical Möbius inversion formula is a principle originating in number theory, which says that if ff and gg are two (say, complex-valued) functions on the positive natural numbers, then

f(n)= dng(d)f(n) = \sum_{d\mid n} g(d)

if and only if

g(n)= dnf(d)μ(n/d)g(n) = \sum_{d\mid n} f(d)\mu(n/d)

where the sums run over the divisors of nn, and where μ\mu is the Möbius function:

μ(n)={(1) r nis the product ofrdistinct primes 0 otherwise \mu(n) = \begin{cases}(-1)^r & n\,\text{is the product of}\,r\,\text{distinct primes}\\0 & \text{otherwise}\end{cases}

Gian-Carlo Rota(1964) described a vast generalization of the Möbius inversion formula, which was at the same time a generalization of the classical inclusion-exclusion principle in combinatorics. Rota’s formulation of Möbius inversion applies to functions defined over partially ordered sets, while further category-theoretic generalizations have also been proposed.

Möbius inversion for posets

Incidence algebras and the zeta function

The incidence algebra of a poset PP (relative to a commutative ring RR) is an associative unital algebra defined as follows. Its elements are functions f:P×PRf : P \times P\to R such that xyx \nleq y implies f(x,y)=0f(x,y) = 0. Pointwise addition f+gf+g and scalar multiplication rfr\cdot f are defined straightforwardly ((f+g)(x,y)=f(x,y)+g(x,y)(f+g)(x,y) = f(x,y) + g(x,y), (rf)(x,y)=rf(x,y)(r\cdot f)(x,y) = r\cdot f(x,y)), while the convolution product f*gf*g is defined as follows:

(f*g)(x,y)= xzyf(x,z)g(z,y)(f*g)(x,y) = \sum_{x \le z \le y} f(x,z) \cdot g(z,y)

Note that the unit of the convolution product is the Kronecker delta:

δ(x,y)={1 x=y 0 otherwise\delta(x,y) = \begin{cases}1 & x = y \\ 0 & \text{otherwise}\end{cases}

We write I(P)I(P) for the incidence algebra of PP. A special and important element of I(P)I(P) is given by

ζ(x,y)={1 xy 0 otherwise\zeta(x,y) = \begin{cases}1 & x \le y \\ 0 & \text{otherwise}\end{cases}

referred to as the zeta function of PP.

The Möbius function and the Möbius inversion formula

A Möbius function of PP is defined as an inverse to the zeta function with respect to the convolution product. Such an inverse always exists if the poset is locally finite, that is, if every interval [x,y]={zxzy}[x,y] = \{z \mid x \le z\le y\} is finite.

Proposition

(Rota 1964): If PP is a locally finite poset, then there exists a function μ\mu such that ζ*μ=μ*ζ=δ\zeta * \mu = \mu * \zeta = \delta.

Proof

μ(x,y)\mu(x,y) can be computed by induction on the number of elements in the interval [x,y][x,y]. In the base case we set μ(x,x)=1\mu(x,x) = 1. Otherwise in the case that xyx \ne y, we assume by induction that μ(x,z)\mu(x,z) has already been defined for all zz in the half-open interval [x,y)[x,y), and set

μ(x,y)= xz<yμ(x,z). \mu(x,y) = -\sum_{x \le z \lt y} \mu(x,z).

From this definition, it is immediate that if

x 0<x 1<<x nx_0 \lt x_1 \lt \cdots \lt x_n

is a chain of length nn in PP, where each x i+1x_{i+1} covers x ix_i, then for all iji \leq j,

μ(x i,x j)={1 i=j 1 ji=1 0 ji2 \mu(x_i,x_j) = \begin{cases}1 & i = j \\ -1 & j - i = 1\\ 0 & j - i \ge 2\end{cases}

It follows that both of the sums xzyμ(x,z)\sum_{x \le z \le y} \mu(x,z) and xzyμ(z,y)\sum_{x \le z \le y} \mu(z,y) add to zero unless x=yx = y, hence that ζ*μ=μ*ζ=δ\zeta*\mu = \mu*\zeta = \delta.

We are now ready to state the Möbius inversion formula(s) for posets.

Proposition

(Rota 1964): Let ff and gg be functions defined over a locally finite poset PP. Then

f(y)= xyg(x)if and only ifg(y)= xyf(x)μ(x,y).f(y) = \sum_{x \le y} g(x) \qquad\text{if and only if}\qquad g(y) = \sum_{x \le y} f(x)\mu(x,y).

Dually, we also have that

f(x)= yxg(y)if and only ifg(x)= yxμ(x,y)f(y).f(x) = \sum_{y \ge x} g(y) \qquad\text{if and only if}\qquad g(x) = \sum_{y \ge x} \mu(x,y)f(y).
Proof

An easy way of proving the Möbius inversion formulas (Kung et al.) is to view ζ\zeta and μ\mu as matrices acting on the column vectors ff and gg by multiplication. Then the first proposition simply says that f=g*ζf = g * \zeta iff f*μ=gf * \mu = g, while the dual formulation says that f=ζ*gf = \zeta * g iff μ*f=g\mu * f = g.

Properties of the Möbius function

Duality

The opposite poset P opP^{op} has the same Möbius function as PP except with the arguments exchanged:

μ P op(x,y)=μ P(y,x)\mu_{P^{op}}(x,y) = \mu_P(y,x)

The product formula

The Möbius function of the cartesian product P×QP \times Q of two posets PP and QQ is the product of their Möbius functions:

μ P×Q((x,y),(x,y))=μ P(x,x)μ Q(y,y)\mu_{P\times Q}((x,y), (x',y')) = \mu_P(x,x') \cdot \mu_Q(y,y')

for all x,xPx,x' \in P and y,yQy,y' \in Q.

The Galois coconnection theorem

Suppose PP and QQ are related by an adjunction (i.e., covariant Galois connection) fg:QPf \dashv g : Q \to P. Then for all xPx \in P, yQy \in Q, the following equation holds:

uP f(u)=yμ P(x,u)= vQ g(v)=xμ Q(v,y) \sum_{\substack{u \in P\\ f(u) = y}} \mu_P(x,u) = \sum_{\substack{v \in Q \\ g(v) = x}} \mu_Q(v,y)

(This result essentially goes back to Rota (1964) but in a slightly different formulation; for the above formulation, see Greene (1981), Aguiar and Ferrer Santos (2000), Kung et al. (2009).)

Examples of Möbius inversion

Inclusion-exclusion

Let 𝒫X\mathcal{P}X be the lattice of subsets of a finite set XX. 𝒫X\mathcal{P}X is isomorphic to the cartesian product of |X||X| many copies of 2={0<1}\mathbf{2} = \{ 0 \lt 1 \}, and so by the product rule for the Möbius function, we have

μ(I,J)=(1) |J||I|\mu(I,J) = (-1)^{|J|-|I|}

for any pair of subsets I,JXI,J \subseteq X such that IJI \subseteq J. The Möbius inversion formula then says that for any functions ff and gg defined on 𝒫X\mathcal{P}X, we have

f(J)= IJg(I)if and only ifg(J)= IJ(1) |J||I|f(I)f(J) = \sum_{I \subseteq J} g(I) \qquad\text{if and only if}\qquad g(J) = \sum_{I \subseteq J} (-1)^{|J|-|I|} f(I)

or dually that

f(I)= JIg(J)if and only ifg(I)= JI(1) |J||I|f(J)f(I) = \sum_{J \supseteq I} g(J) \qquad\text{if and only if}\qquad g(I) = \sum_{J \supseteq I} (-1)^{|J|-|I|} f(J)

This is called the inclusion-exclusion principle.

As a textbook example of the inclusion-exclusion principle in action, suppose we want to compute g(I)g(I) = the number of permutations of XX fixing exactly the elements in II. Well, it is easy to compute the number of permutations of XX fixing at least the elements in II,

f(I)= JIg(J)=(|X||I|)!f(I) = \sum_{J \supseteq I} g(J) = (|X|-|I|)!

but then we can compute gg in terms of ff via Möbius inversion. As a special case, when |X|=n|X| = n and I=I = \emptyset, we recover the classical formula for the number of derangements of nn elements:

!n= k=0 n(1) k(nk)(nk)!= k=0 n(1) kn!k! !n = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)! = \sum_{k=0}^n (-1)^k \frac{n!}{k!}

where a derangement is defined as a permutation fixing no elements.

Exercise: Prove that n!= k=0 n(1) k(nk)(nk) nn! = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^n.

Number-theoretic Möbius inversion

The classical Möbius inversion formula is recovered by considering the set of positive natural numbers ordered by divisibility.

Möbius inversion for categories

References

The classical reference on Möbius inversion for posets is:

  • Gian-Carlo Rota, On the foundations of combinatorial theory I: theory of Möbius functions , Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368.

and a more modern reference is:

  • Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan. Combinatorics: The Rota Way. Cambridge, 2009.

Möbius inversion for categories is discussed in:

Other references include:

  • Curtis Greene, The Möbius Function of a Partially Ordered Set, NATO Advanced Study Institute, Series C (1981), 555-581.
  • Joachim Kock, Incidence Hopf algebras, pdf

  • Imma Gálvez-Carrillo, Joachim Kock, Andrew Tonks, Decomposition spaces, incidence algebras and Möbius inversion, arxiv/1404.3202

  • Metropolis, N.; Rota, Gian-Carlo, Witt vectors and the algebra of necklaces, Advances in Mathematics 50 (2): 95–125 (1983) doi

  • Marcelo Aguiar and Walter Ferrer Santos, Galois connections for incidence Hopf algebras of partially ordered sets, Adv. Math. 151 (2000), 71-100.

  • wikipedia Möbius function, necklace polynomial

category: combinatorics

Last revised on August 30, 2018 at 10:32:52. See the history of this page for a list of all contributions to it.