Introduction to Möbius Functions

Bruce E. Sagan

Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu

1. Motivation and Introduction

2. Möbius functions of posets

3. The Möbius Inversion Theorem

4. The incidence algebra

5. The Möbius algebra

6. The order complex Motivation and Introduction

I. Number Theory. The number-theoretic Möbius function is μ : ℤ_{>0} → ℤ defined as

μ(n) = \{ \begin{matrix}0 & if n is not square free, \\ (−1)^{k} & if n = product of k distinct primes, \end{matrix}

The importance of μ lies in the number-theoretic Möbius Inversion Theorem.

Theorem 1 Let f, g : ℤ_{>0} → ℤ satisfy

f(n) = _{d|n}^{∑} g(d)

for all n ∈ ℤ_{>0}. Then

g(n) = _{d|n}^{∑} μ(n/d)f(d).

II. Combinatorics. A very useful tool is the Principle of Inclusion-Exclusion or PIE.

Theorem 2 Let S be a finite set and S_{1}, …, S_{n} ⊆ S.

|S − n ; ⋃ ; i=1 S_{i}| = |S| − _{1≤i≤n}^{∑} |S_{i}| + _{1≤i<j≤n}^{∑} |S_{i} ∩ S_{j}|

− ⋯ + (−1)^{n}| n ; ⋂ ; i=1 S_{i}|.

III. Theory of Finite Differences. If one takes a function f : ℤ_{≥0} → ℂ then there is an analog of the derivative, namely the difference operator

Δf(n) = f(n) − f(n − 1)

(where f(−1) = 0 by definition), and an analog of the integral, namely the summation operator

Sf(n) = n ; ∑ ; i=0 f(n).

The Fundamental Theorem of the Difference Calculus then states

Theorem 3 (FTDC) If f : ℤ_{≥0} → ℂ then

ΔSf(n) = f(n).

One of the advantages of the combinatorial Möbius function is that its inversion theorem unifies and generalizes the previous three results. In addition, it makes the number-theoretic definition transparant, encodes topological information about poets, and has even been used to bound the running time of certain algorithms.

Möbius functions of posets

Let P be a finite poset (partially ordered set ) which is a set P with an order relation ≤ satisfying the three axioms for all x, y, z ∈ P:

1. (reflexsive) x ≤ x,

2. (antisymmetry) x ≤ y and y ≤ x implies x = y,

3. (transitivity) x ≤ y and y ≤ z implies x ≤ z,

A poset is represented by its Hasse diagram which is a graph whose vertices are the elements of P and with an edge from x up to y if x is covered by y (i.e., x < y and there is no z with x < z < y).

Examples:

1. The chain, C_{n}, consists of the integers {0, 1, …, n} ordered in the usual manner.

2. The Boolean algebra, B_{n}, has as elements all subsets of [n] := {1, 2, …, n} and ⊆ as order relation.

3. The divisor poset, D_{n}, consists of all d|n ordered by c ≤ d if c|d.

[figure: 0; 1; 2; 3; C_{3}; ∅; B_{3}; {1}; {2}; {3}; {1, 2}; {1, 3}; {2, 3}; {1, 2, 3}; 1; 2; 3; 6; 9; 18; D_{18}]

If P has a unique minimal element then it will be denoted ˆ0 = ˆ0_{P} , and if it has a unique maximal element then we will use the notation ˆ1 = ˆ1_{P} .

If P has a ˆ0 then its Möbius function, μ : P → Z, is defined recursively by

μ(x) = \{ \begin{matrix}1 & if x = ˆ0, \\ − ∑_{y<x} μ(y) & if x > ˆ0. \end{matrix}

Equivalently

_{y≤x}^{∑} μ(y) = δ_{x,ˆ0}

where δ_{x,ˆ0} is the Kronecker delta.

Computations: It is immediate directly from the definition of μ that in C_{n} we have

μ(x) = \{ \begin{matrix}1 & if x = 0 \\ −1 & if x = 1 \\ 0 & if x ≥ 2 \end{matrix}

1. If x ∈ B_{n} then μ(x) = (−1)^{|x|}.

2. If x ∈ D_{n} then μ(x) is the number theory function.

If P, Q are posets then order P × Q componentwise.

Proposition 4 If P × Q has Möbius function μ then

μ(x, y) = μ_{P} (x)μ_{Q}(y)

Proof It suffices to show that μ′(x, y) := μ_{P} (x)μ_{Q}(y) satisfies the defining equation for μ.

_{(a,b)≤(x,y)}^{∑} μ′(a, b) = _{(a,b)≤(x,y)}^{∑} μ_{P} (a)μ_{Q}(b)
= _{a≤x}^{∑} μ_{P} (a) _{b≤y}^{∑} μ_{Q}(b)
= δ_{x,ˆ0_{P}} δ_{y,ˆ0_{Q}} = δ_{(x,y),(ˆ0_{P} ,ˆ0_{Q})} .

P and Q are isomorphic, P ≅ Q, if there is a bijection f : P → Q with both f and f^{−1} order-preserving.

Proposition 5 If f : P → Q is an isomorphism then μ_{P} (x) = μ_{Q}(f(x)).

1. B_{n} is isomorphic as a poset to the n-fold product (C_{1})^{n} where a set corresponds to its bit-string. Now for each bit μ(0) = 1, μ(1) = −1, so μ(x) = (−1)^{|x|}.

2. If n has prime factorization n = ∏_{i} p_{i}^{n_{i}} then we have an isomorphism D_{n} ≅ ×_{i}C_{n_{i}}. So p_{i}^{n_{i}} contributes -1 or 0 to the product for μ depending on whether n_{i} = 1 or n_{i} ≥ 2.

The Möbius Inversion Theorem (MIT)

It is convenient to extend the definition of μ. If x ≤ y in P then we have the interval

[x, y] = {z ∈ P : x ≤ z ≤ y}.

Let Int P denote the set of intervals of P.

If P is any finite poset, then its Möbius function, μ : Int P → Z, is defined recursively by

μ(x, y) = \{ \begin{matrix}1 & if x = y, \\ − ∑_{x≤z<y} μ(x, z) & if x < y. \end{matrix}

Equivalently

_{x≤z≤y}^{∑} μ(x, z) = δ_{x,y}.

So if P has a ˆ0 then μ(x) = μ(ˆ0, x). Furthermore, we can consider [x, y] as a poset in it’s own right with x = ˆ0_{[x,y]} and in this poset the new definition reduces to the old one.

Note that our previous computations also give the two-variable version of μ since in all cases an interval [x, y] in P_{n} (P = C, B, or D) satisfies

[x, y] ≅ P_{k}

for some k ≤ n.

Theorem 6 Let P be a poset and f, g : P → ℂ. MIT1 If for all x ∈ P we have f(x) = ∑_{y≤x} g(y) then

g(x) = _{y≤x}^{∑} μ(y, x)f(y).

MIT2 If for all x ∈ P we have f(x) = ∑_{y≥x} g(y) then g(x) = _{y≥x}^{∑} μ(x, y)f(y).

Proof We prove MIT2 as MIT1 is similar.

_{y≥x}^{∑} μ(x, y)f(y) = _{y≥x}^{∑} μ(x, y) _{z≥y}^{∑} g(z)
= _{z≥x}^{∑} g(z) _{x≤y≤z}^{∑} μ(x, y)
= _{z∈P}^{∑} g(z)δ_{x,z}
= g(x).

Note (a) ℂ above can be replaced by any vector space.

(b) The converses of MIT1 & 2 are also true.

It is now easy to obtain the three theorems from the introduction as corollaries by using Möbius inversion over D_{n}, B_{n}, and C_{n}, respectively.

I. If f(m) = ∑_{d|m} g(d) for all m then in D_{n} we have f(m) = ∑_{d≤m} g(d). So by MIT and [d, m] ≅ D_{m/d}

g(m) = _{d≤m}^{∑} μ(d, m)f(d) = _{d|m}^{∑} μ(m/d)f(d).

II. For the PIE, given S_{1}, …, S_{n} ⊆ S and x ∈ B_{n} let S_{x} = ∩_{i∈x}S_{i}. Define f, g : B_{n} → ℤ_{≥0} by

f(x) = |S_{x}|,
g(x) = |S_{x} − _{i∉x}^{⋃} S_{i}|.

For example in B_{2}

\begin{matrix}f(∅) = |S| & g(∅) = |S − (S_{1} ∪ S_{2})| \\ f(1) = |S_{1}| & g(1) = |S_{1} − S_{2}| \\ f(2) = |S_{2}| & g(2) = |S_{2} − S_{2}| \\ f(12) = |S_{1} ∩ S_{2}| & g(12) = |S_{1} ∩ S_{2}|. \end{matrix}

By definition f(x) = ∑_{y≥x} g(y), so by MIT2

|S − n ; ⋃ ; i=1 S_{i}| = g(∅) = _{y≥∅}^{∑} μ(y)f(y) = _{y∈B_{n}}^{∑}(−1)^{|y|} |_{i∈y}^{⋂} S_{i}| .

III. For the FTDC, use g(m) := Sf(m) = ∑_{i≤m} f(i) in C_{n}. So by MIT1 and [i, j] ≅ C_{j−i}

f(m) = _{i≤m}^{∑} μ(i, m)g(i) = g(m) − g(m − 1)

= Δg(m) = ΔSf(m).

The incidence algebra

Consider the incidence algebra of P, I(P), which consists of all functions f : Int(P) → ℂ. The multiplication in this algebra is convolution defined by

f ∗ g(x, y) = _{x≤z≤y}^{∑} f(x, z)g(z, y).

It will be convenient to extend a f ∈ I(P) to any pair (x, y) ∈ P × P by letting f(x, y) = 0 if x ≰ y. So

f ∗ g(x, y) = _{z∈P}^{∑} f(x, z)g(z, y).

Let x_{1}, x_{2}, …, x_{n} be a fixed linear extension of P (so P = {x_{1}, …, x_{n}} and x_{i} < x_{j} in P implies i < j). Define a set of complex matrices Mat (P) with rows and columns indexed by x_{1}, …, x_{n}:

M ∈ Mat (P) ⟺ m_{x,y} = 0 if x ≰ y.

Proposition 7 I(P) ≅ M(P) as algebras via the isomporphism

f ∈ I(P) ↔ M_{f} = (f(x, y)).

For example, B_{2} has linear extension ∅, 1, 2, 12 and

M_{μ} = ( \begin{matrix}1 & −1 & −1 & 1 \\ 0 & 1 & 0 & −1 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 \end{matrix} )

Corollary 8 1. I(P) has an identity element denoted 1 : Int(P) → ℂ given by 1(x, y) = δ_{x,y}.

2. f ∈ I(P) is invertible iff f(x, x) ≠ 0 for all x ∈ P. Proof 1. M_{1} is the identity matrix.

2. M_{f} is invertible iff det M_{f} ≠ 0. Since M_{f} is upper triangular, det M_{f} = ∏_{x∈P} f(x, x). Define ζ ∈ I(P) by

ζ(x, y) = 1 ∀[x, y] ∈ Int P.

Corollary 9 We have ζ^{−1} = μ. Proof It suffices to show μ ∗ ζ = 1 but

(μ ∗ ζ)(x, y) = _{x≤z≤y}^{∑} μ(x, z)ζ(z, y)

= _{x≤z≤y}^{∑} μ(x, z) = 1(x, y).

The Möbius algebra

A lattice is a poset L where every x, y ∈ L have a greatest lower bound or meet, x ∧ y, and a least upper bound or joint, x ∨ y. For example,

Poset  x ∧ y  x ∨ y
C_{n} min {x, y} max {x, y}
B_{n} x ∩ y x ∪ y
D_{n} gcd (x, y) lcm (x, y)

Consider the complex vector space of formal sums

M(L) = {_{x∈L}^{∑} c_{x}x : c_{x} ∈ ℂ}.

So the elements of L are a basis for M(L). For x ∈ L, define

ϵ_{x} := _{z≤x}^{∑} μ(z, x)x

in M(L). For example in A(B_{2}) where we have μ(z, x) = (−1)^{|x−z|}

ϵ_{∅} = μ(∅, ∅)∅ = ∅,
ϵ_{1} = μ(1, 1)1 − μ(∅, 1)∅ = 1 − ∅,
ϵ_{2} = μ(2, 2)2 − μ(∅, 2)∅ = 2 − ∅,
ϵ_{12} = _{x∈B_{2}}^{∑} μ(x, 12)x = 12 − 1 − 2 + ∅.

Lemma 10 a. If x ∈ L then x = _{z≤x}^{∑} ϵ_{z}. b. The set B = {ϵ_{x} : x ∈ L} is a basis for M(L). Proof 1. This follows immediately by applying the converse of MIT1 to the definition of the ϵ_{x}.

2. Since |B| = |L| we need only prove that the ϵ_{x} span, which follows from part 1. The Möbius algebra is M(L) with multiplication

ϵ_{x} · ϵ_{y} = δ_{x,y}ϵ_{x}.

Proposition 11 If x, y ∈ L then x · y = x ∧ y. Proof Using Lemma ?? .a

x · y = (_{z≤x}^{∑} ϵ_{z}) · (_{w≤y}^{∑} ϵ_{w})
= ∑_{{z≤x \atop w≤y}} ϵ_{z} · ϵ_{w}

= _{z≤x,y}^{∑} ϵ_{z}
= _{z≤x∧y}^{∑} ϵ_{z}
= x ∧ y.

Theorem 12 (Wiesner’s Theorem) Suppose L is a finite lattice and c ∈ L \ ˆ1. Then

_{x∧c=ˆ0}^{∑} μ(x, ˆ1) = 0.

Proof Expand c · ϵˆ1 in two ways

c · ϵˆ1 = _{d≤c}^{∑} ϵ_{d} · ϵˆ1 = 0

since d ≤ c < ˆ1 so d ≠ ˆ1 and ϵ_{d} · ϵˆ1 = 0. Now by the Proposition

0 = c · ϵˆ1 = c · _{x≤ˆ1}^{∑} μ(x, ˆ1)x = _{x∈L}^{∑} μ(x, ˆ1)x ∧ c.

Taking the coefficient of ˆ0 on both sides finishes the proof.

Theorem 13 (Dual Weisner) Suppose L is a finite lattice and d ∈ L \ ˆ0. Then

_{x∨c=ˆ1}^{∑} μ(ˆ0, x) = 0.

The atoms of poset P are

A = A(P) = {a ∈ P : a covers ˆ0 }.

The coatoms of poset P are

A^{∗} = A^{∗}(P) = {b ∈ P : ˆ1 covers b }.

For example

P  A(P)  A^{∗}(P)
C_{n}  {1}  {n − 1}
B_{n} {x : |x| = 1} {x : |x| = n − 1}
D_{n} {p prime : p|n } {n/p : p prime }

Theorem 14 (P. Hall) Let L be a finite lattice.

a. If ⋁ A(L) ≠ ˆ1 then μ(ˆ0, ˆ1) = 0.

b. If ⋀ A^{∗}(L) ≠ ˆ0 then μ(ˆ0, ˆ1) = 0.

Proof a. Let c = ⋁ A(L) in Weisner which is OK since c ≠ ˆ1.

∴ _{x∧c=ˆ0}^{∑} μ(x, ˆ1) = 0.

But x ∧ c = ˆ0 implies x = ˆ0. (If x ≠ ˆ0 then x ≥ a for some a ∈ A(L) so x ∧ c ≥ a.) But then the sum above has only one term corresponding to x = ˆ0 and so reduces to μ(ˆ0, ˆ1) = 0.

The order complex

A chain C of length l in P is C : x_{0} < x_{1} < … < x_{l}. Equivalently C ≅ C_{l}. Let P have a ˆ0 and a ˆ1 ≠ ˆ0. The order complex is

ΔP = {C : x_{0} > ˆ0, x_{l} < ˆ1}

Then ΔP is a simplicial complex since any subset of a chain is a chain. (We do not include ˆ0 or ˆ1 in our chains since if we did ΔP would be contractible.) For example

[figure: 23; 2; 3; 12; 13; 1; 2 < 23; 3 < 23; 2 < 12; 3 < 13; 1 < 12; 1 < 13]

The simplices of ΔP of dimension l are

Δ^{l}P = {C ∈ ΔP : C has length l }.

Also Δ^{−1}P = {∅} and Δ^{l}P = ∅ for l ≤ −2.

Lemma 15 For l ≥ 0 : (ζ − 1)^{l}(ˆ0, ˆ1) = |Δ^{l−2}P |. Proof From the definitions

(ζ − 1)(x, y) = \{ \begin{matrix}1 & if x < y \\ 0 & if x = y \end{matrix}

∴ (ζ − 1)^{l}(ˆ0, ˆ1)

= _{ˆ0≤x_{0}≤...≤x_{l−2}≤ˆ1}^{∑}(ζ − 1)(ˆ0, x_{0}) ⋯ (ζ − 1)(x_{l−2}, ˆ1)
= _{ˆ0<x_{0}<...<x_{l−2}<ˆ1}^{∑} 1
= |Δ^{l−2}P |.

Proposition 16 (Reduced Euler Characteristic) μ(ˆ0, ˆ1) = _{l≥−1}^{∑}(−1)^{l}|Δ^{l}P |.

Proof By the lemma & (ζ − 1)^{l}(ˆ0, ˆ1) = 0 for large l:

μ(ˆ0, ˆ1) = ζ^{−1}(ˆ0, ˆ1)
= [1 + (ζ − 1)]^{−1}(ˆ0, ˆ1)

= _{l≥0}^{∑}(−1)^{l}(ζ − 1)^{l}(ˆ0, ˆ1)
= _{l≥0}^{∑}(−1)^{l}|Δ^{l−2}P |
= _{l≥−1}^{∑}(−1)^{l}|Δ^{l}P |.