6 Möbius Inversion and Lattices

Motivation
Problem 1: We are interested in counting the number of surjections from [n] to [k]. Al-
though this is difficult to count directly, it is rather easy to count the number of (arbitrary)
functions from [n] to a given subset H of [k], as this is given by |H|n . The solution to this
problem is a standard representative of an inclusion-exclusion argument.

Euler’s φ: For n ∈ N \ {0} we define

φ(n) = {1 ≤ k ≤ n : GCD(k, n) = 1}

Note that φ(n) is the order of the multiplicative group Z∗n .

P
Proposition 6.1 d|n φ(d) = n

Proof: The number of integers m ∈ [n] with (m, n) = d (i.e. m = m0 d and n = n0 d with
(m0 , n0 ) = 1 and m0 ≤ n0 ) is precisely φ(n0 ) = φ(n/d). Thus
X X
n= φ(n/d) = φ(d) 
d|n d|n

Problem 2: Use the above proposition to find φ(n).

Problem 3: We are interested in counting the number of linear functions from Fnq onto Fkq .
Although this is difficult to do directly, it is easy to count the number of (arbitrary) linear
functions from Fnq to Fkq as we may freely assign the image of a basis, and this forces the
remaining elements, this is given by (q k )n = q nk .

General Problem: Consider a poset (P, ≤) and a function f : P → C and let g : P → C

P
be given by g(x) = y≤x f (x). We would like to use g to find f .
 2
Möbius Inversion
Incidence Algebra: If (P, ≤) is a poset, the associated incidence algebra is

A(P ) = {α ∈ CP ×P : α(x, y) = 0 unless x ≤ y}

Note that if α, β ∈ A(P ) then by matrix multiplication we have

X
(αβ)(x, y) = α(x, z)β(z, y).
z∈P

It is immediate that A(P ) is closed under scalar multiplication, addition, and multiplication.
We let I ∈ A(P ) denote the function with I(x, y) = 0 if x 6= y and I(x, y) = 1 if x = y and
note that I is a multiplicative identity.

Zeta Function: The zeta function is given by

(
1 if x ≤ y
ζ(x, y) =
0 otherwise

Note that ζ ∈ A(P ).

Möbius Function: We define a function µ ∈ A(P ) by the rule that µ(x, y) = 0 whenever
x 6≤ y and µ(x, x) = 1 and then define the other values inductively by the rule:
X
µ(x, y) = − µ(x, z)
x≤z<y

It is immediate from this definition that

(
X 1 if x = y
µ(x, z) = (1)
x≤z≤y 0 otherwise

This last equation is equivalent to the µζ = I. So, in fact, µ is the inverse of ζ. Note
further that by this construction, µ is always integer valued. The equation ζµ = I yields the
following similar identity for the Möbius function.
(
X 1 if x = y
µ(z, y) = (2)
x≤z≤y 0 otherwise
 3
Theorem 6.2 (Möbius Inversion) Let (P, ≤) be a poset, let µ be its Möbius function, let
P
f : P → C and let g : P → C be given by g(x) = y≤x f (y). Then
X
f (x) = µ(y, x)g(y)
y≤x

Proof:
!
X X X
µ(y, x)g(y) = µ(y, x) f (z)
y≤x y≤x z≤y
X
= µ(y, x)f (z)
z≤y≤x
!
X X
= f (z) µ(y, x)
z≤x z≤y≤x

= f (x) 

Note: The above formula is precisely what we need to solve our general problem, so long
as we can find the Möbius function.

Proposition 6.3 The Möbius function for the poset of subsets of [n] is given by:
(
(−1)|B|−|A| if A ⊆ B
µ(A, B) =
0 otherwise

Proof: It suffices to show that µ(∅, B) = (−1)|B| as the other cases are similar. This case
we prove by induction on |B|. As a base, note that it holds trivially when |B| = 0. For the
inductive step, let |B| = b and assume that the result holds for all sets with size less than
|B|. Then using 0 = (1 − 1)|B| = C⊆B (−1)|C| and the formula for the Möbius function we
P

have
X
µ(∅, B) = − µ(∅, C)
C⊂B
X
=− (−1)|C|
C⊂B

= (−1)|B| 

Answer to Problem 1: For every H ⊆ [k] let f (H) denote the number of surjections from
P
[n] to H. Then define for every H ⊆ [k] the function g(H) = J⊆H f (J). Now, g(H) is
 4
precisely the total number of functions from [n] to H so g(H) = |H|n . By Möbius inversion
we get
k  
X
k−|H| n
X k
f ([k]) = (−1) |H| = (−1)k−i in
i=0
i
H⊆[k]

More generally, using the Möbius function on the poset of subsets of [n] is the general
technique of inclusion-exclusion.

Lattice: A lattice is a poset (L, ≤) with the following additional properties:

(i) for every x, y ∈ L there is a unique element, denoted x ∨ y, with the property that
z ≥ x and z ≥ y implies z ≥ x ∨ y.

(ii) for every x, y ∈ L there is a unique element, denoted x ∧ y, with the property that
z ≤ x and z ≤ y implies z ≤ x ∧ y.

It follows immediately from (i) and (ii) that for any subset X ⊆ L there is a unique element
which is minimal (maximal) subject to being greater than (less than) or equal to all elements
in X. It follows from this that every finite lattice has a unique minimal element which we
denote by 0L and a unique maximal element which we denote by 1L .

Theorem 6.4 (Weisner) Let µ be the Möbius function of a finite lattice (L, ≤) and let
a ∈ L with a > 0L . Then
X
µ(0L , x) = 0
x:x∨a=1L

Proof: Now, using the Möbius formula (2) in the first equality, and the Möbius formula (1)
together with the observation that y 6= 0L in the third we have:
X X X
µ(0L , x) = µ(0L , x) µ(y, 1L )
x:x∨a=1L x y≥x∨a
X X
= µ(y, 1L ) µ(0L , x)
y≥a x≤y

=0 
 5
Divisibility Poset
Proposition 6.5 In the divisibility poset on the positive integers we have
(
(−1)k if ab = p1 p2 . . . pk where p1 , . . . , pk are distinct primes
µ(a, b) =
0 otherwise
(note that µ(a, a) = 1 since 1 is a product of zero distinct primes).

Proof: To compute µ(a, b) it suffices to consider the case when a = 1 (the 0 of the lattice).
For this we proceed by induction on b. The base case, when b = 1 holds trivially. For the
inductive step, choose a prime p which divides b. Now, by Weisner’s Theorem we have
X X
µ(0, b) = − µ(0, d) = − µ(0, d)
d6=b:d∨p=b d6=b:LCM (d,p)=b

Now, if p2 |b the sum on the right is empty and we have µ(0, b) = 0 as desired. Otherwise,
there is only one possible choice for d, namely d = b/p and for this choice we have: µ(0, b) =
−µ(0, b/p) and now the result follows by induction. 

Number Theoretic Möbius: Noting that the above function depends only on b/a, we
now define a one parameter Möbius function on the positive integers as follows:
(
(−1)k if n = p1 p2 . . . pk where p1 , . . . , pk are distinct primes
µ(n) =
0 otherwise

Proposition 6.6 (Solution to Problem 2) For every positive integer n we have

φ(n) X µ(d)
=
n d
d|n
P
Proof: We have shown d|n φ(d) = n so by Möbius inversion (applied with f = φ and g the
identity) we get
φ(n) 1X X d X µ(d)
= µ(d, n)d = µ(n/d) =
n n n d
d|n d|n d|n

Theorem 6.7 For a prime power q, the number of monic irreducible polynomials of degree
n over Fq which we denote by Nn is given by
1X
Nn = µ(n/d)q d
n
d|n
 6
Proof: We previously proved that q n =
P
d|n dNd . Applying Möbius inversion (for the
functions f (n) = nNn and g(n) = q n ) gives us
X
nNn = µ(n/d)q d
d|n

from which the result follows. 

Note: There is a connection between the Möbius & zeta functions for a poset and the number
theoretic Möbius and Riemann zeta function. This is given by the following theorem (the
Riemann ζ function is given by ζ(s) = ∞ 1
P
n=1 ns and defined on all s ∈ C with Re(s) > 1).

Theorem 6.8 ∞
1 X µ(n)
=
ζ(s) n=1 ns

Proof: Letting pi denote the ith prime, the Euler product expression for ζ is
∞
X 1
ζ(s) =
n=1
ns
1 1
= 1 + s + s ...
 2 3  
1 1 1 1
= 1 + s + 2s + . . . 1 + s + 2s + . . . . . .
p1 p1 p2 p2
∞
Y 1
=
i=1
1 − p1s
i

Using this we find

∞  
1 Y 1
= 1− s
ζ(s) i=1 pi
∞
X µ(n)
= 
n=1
ns
 7
Subspace Poset
Gaussian Numbers: If n, k are positive integers and q is a power of a prime, we define

(q n − 1)(q n−1 − 1) . . . (q n−k+1 − 1)

 
n
=
k q (q k − 1)(q k−1 − 1) . . . (q − 1)
n
Proposition 6.9 The number of k-dimensional subspaces of Fnq is k q
. More generally, the
number of k-dimensional subspaces of Fnq containing a given `-dimensional subspace is given
by n−`
 
k−` q
.

Proof: Fix subspaces U ⊆ V ⊆ Fnq and suppose that dim(U ) = a and dim(V ) = b. The
number of maximal chains in the subspace poset with smallest element U and largest element
V depends only on a, b. To construct such a chain, we may choose the next term above U
by taking the space spanned by U and any of the q b − q a vectors in V \ U . However, every
such subspace will be formed by q a+1 − q a different vectors, so the total number of ways to
q b−a −1
choose this next term is q−1
. Continuing in this manner we find that the total number of
chains between U and V is
(q b−a − 1)(q b−a−1 − 1) . . . (q − 1)
(q − 1)b−a
(q c −1)(q c−1 −1)...(q−1)
This depends only on the difference of a and b so defining M (c) = (q−1)c
we
have that M (c) is the number of maximal chains between any pair of subspaces U ⊆ V with
d im(V ) − d im(U ) = c. Now, the total number of maximal chains is M (n) and the number
containing any fixed k-dimensional subspace is M (k)M (n − k) which gives us

M (n)
#{V ≤ Fnq : dim(V ) = k} =
M (k)M (n − k)
(q n − 1)(q n−1 − 1) . . . (q − 1)
=
(q k − 1)(q k−1 − 1) . . . (q − 1)(q n−k − 1)(q n−k−2 − 1) . . . (q − 1)
(q n − 1)(q n−1 − 1) . . . (q n−k+1 − 1)
=
(q k − 1)(q k−1 − 1) . . . (q − 1)
 
n
=
k q

A similar computation yields the more general result that the number of k-dimensional
subspaces containing a fixed `-dimensional subspace is n−`
 
k−` q
. 
 8
Proposition 6.10 The Möbius function for the subspace poset of Fnq is
k
(−1)k q (2) if U ⊆ V and d im(V ) − d im(U ) = k
(
µ(U, V ) =
0 otherwise

Proof: Again we may assume without loss that U = {0} and that V = Fnq . Now, we proceed
by induction on n. As a base, note the result is trivial if n = 1. For the inductive step,
choose a 1-dimensional subspace P ⊆ V and apply Weisner’s theorem to get
X
µ(0, V ) = − µ(0, W )
W <V :W ∨P =V
n−1
(−1)n−1 q ( )
X
=− 2

W <V :P 6≤W,dim(W )=n−1

   !
n n−1 n−1
=− − (−1)n−1 q ( 2 )
n−1 q n−2 q
   !
n n−1 n−1
=− − (−1)n−1 q ( 2 )
1 q 1 q
 n
q − 1 q n−1 − 1

n−1
=− − (−1)n−1 q ( 2 )
q−1 q−1
n−1 (n−1
n−1
(−1) q 2 )


=− q
n
= (−1)n q ( 2 )

Answer to Problem 3: Let V = Fkq . For every subspace U ⊆ V let f (U ) denote the
number of surjective linear mappings from Fnq to U and let g(U ) denote the number of
arbitrary linear mappings from Fnq to U . Then g(U ) = q n dim(U ) so by Möbius inversion we
have
X
f (V ) = µ(U, V )g(U )
U ⊆V
k  
k k−i
(−1)k−i q ( )+ni
X
= 2

i=0
i q