The Mobius Function and Mobius Inversion

In analytic number theory, the Mobius function underlies the Mobius inversion formula relating the prime-counting function and Chebyshev-type sums, and appears in the Mertens function and the Riemann hypothesis's equivalent formulations. In combinatorics, poset Mobius functions compute chromatic polynomials of graphs via the Mobius function of the partition lattice restricted to the lattice of contractions (Whitney's theorem), and drive the enumeration of connected/indecomposable structures from arbitrary ones, directly foreshadowing counting arguments used in Combinatorial Designs where one inverts sums over sub-designs or over the lattice of flats of an associated matroid. In algebraic topology, the Mobius function of the poset of faces of a simplicial complex (the order complex) computes reduced Euler characteristics, linking combinatorics to homology. In theoretical computer science and cryptography, fast Mobius transforms (zeta and Mobius transforms over the Boolean lattice) underlie subset-convolution algorithms used in exact exponential-time algorithms for graph coloring and related NP-hard problems, and Mobius-type inversion appears in algorithms for computing over lattices in cryptographic protocols. In statistics and design of experiments, inclusion-exclusion arguments derived from Boolean-lattice Mobius inversion are used to compute probabilities of unions of events and in the analysis of factorial designs. In group theory, the Mobius function of the subgroup lattice computes the number of generating tuples of a group via the Eulerian function, a tool in probabilistic group theory.

Ask the tutor: Can you show how the Mobius function of the partition lattice is used to derive the chromatic polynomial of a graph?

Think of $\zeta$ as the "summing operator": if $f$ is a function on $P$ and we define $g(x) = \sum_{y \le x} f(y)$, this is exactly the convolution of $f$ against $\zeta$ read appropriately (made precise below). The Mobius function is the operator that undoes this summation — it is the poset-theoretic analogue of a discrete derivative or a difference operator. On the chain $\{0 < 1 < 2 < \dots\}$ (ordinary integers with usual order), $g(x) = \sum_{y\le x} f(y)$ is the running sum, and inversion recovers $f(x) = g(x) - g(x-1)$, the ordinary backward difference. The Mobius function of this poset is $\mu(x,y) = 1$ if $y = x$, $-1$ if $y = x+1$, $0$ otherwise — literally the difference-operator coefficients. On the Boolean lattice $2^{[n]}$, the recursive definition unwinds to $\mu(S,T) = (-1)^{|T\setminus S|}$, and Mobius inversion becomes the inclusion-exclusion principle in its general two-variable form. On the divisor lattice, $\mu(d,n)$ depends only on $n/d$ and reduces to the classical arithmetic function $\mu(n)$ that vanishes on non-squarefree integers and alternates sign according to the number of prime factors of squarefree integers. The unifying picture: whenever you build $g$ from $f$ by summing over "everything at or below," $\mu$ tells you exactly how to peel that sum back apart, with signs and multiplicities dictated purely by the shape of the poset.

Example 1: The number-theoretic Mobius function via the divisor lattice, applied to counting coprime residues. Let $P = (\mathbb{N}_{\ge 1}, \mid)$, the positive integers ordered by divisibility, which is locally finite since for $d\mid n$ the interval $[d,n]$ (divisors of $n$ that are multiples of $d$) is finite. Because $[d,n] \cong [1, n/d]$ as posets (via $z \mapsto z/d$), we have $\mu(d,n) = \mu(1,n/d)$, so it suffices to compute $\mu(n) := \mu(1,n)$. Apply the recursion $\mu(1,1)=1$ and $\sum_{d\mid n}\mu(d, n)=0$ for $n>1$; rewritten using $\mu(d,n)=\mu(n/d)$, this says $\sum_{d \mid n} \mu(n/d) = 0$, i.e. $\sum_{e\mid n}\mu(e) = 0$ for $n > 1$ (relabeling $e = n/d$, which also ranges over all divisors of $n$). Take $n = 30 = 2\cdot 3\cdot 5$. Its divisors are $1,2,3,5,6,10,15,30$. We compute $\mu$ recursively on divisors of $30$ in increasing order:

• $\mu(1) = 1$.
• $\mu(2)$: from $\mu(1)+\mu(2)=0 \Rightarrow \mu(2)=-1$.
• $\mu(3) = -1$, $\mu(5) = -1$ similarly (each prime $p$: $\mu(1)+\mu(p)=0$).
• $\mu(6)$: divisors of $6$ are $1,2,3,6$; $\mu(1)+\mu(2)+\mu(3)+\mu(6)=0 \Rightarrow 1-1-1+\mu(6)=0 \Rightarrow \mu(6)=1$.
• $\mu(10) = 1$, $\mu(15)=1$ by the identical computation.
• $\mu(30)$: divisors $1,2,3,5,6,10,15,30$; sum of $\mu$ over the first seven is $1-1-1-1+1+1+1 = 0$, so $\mu(30) = 0 - 0 = 0$... let's be careful and just require the total sum over all divisors of $30$ to vanish: $1 + (-1) + (-1) + (-1) + 1 + 1 + 1 + \mu(30) = 0$, i.e. $1 + \mu(30) = 0$, so $\mu(30) = -1$.

This matches the closed form: for squarefree $n$ with $k$ distinct prime factors, $\mu(n) = (-1)^k$; here $30$ has $k=3$ prime factors, so $\mu(30) = (-1)^3 = -1$, confirming the recursive computation. Now use Mobius inversion to count integers in $\{1,\dots, 100\}$ coprime to $30$ (i.e. not divisible by $2$, $3$, or $5$) — the classic inclusion-exclusion computation, re-derived via the divisor lattice. Let $A(n)$, for $n \mid 30$, denote the number of integers in $[1,100]$ divisible by $n$: $A(n) = \lfloor 100/n \rfloor$. Let $F(1)$ be the count of integers coprime to $30$. In general, for $d\mid 30$, let $F(d)$ be the number of integers in $[1,100]$ whose gcd with $30$ is exactly $d$; then

(every multiple of $d$ that divides into $30$'s divisor structure is counted once, grouped by its exact gcd with $30$). This is exactly a down-set sum in the divisor-lattice-restricted-to-$[d,30]$, and Mobius inversion (with the poset $[d,30]$, isomorphic to divisors of $30/d$) gives

Setting $d=1$:

Plugging in $A(1)=100, A(2)=50, A(3)=33, A(5)=20, A(6)=16, A(10)=10, A(15)=6, A(30)=3$ and the $\mu$-values found above:

So exactly $26$ integers from $1$ to $100$ are coprime to $30$ — this is inclusion-exclusion, executed automatically by the divisor-lattice Mobius function.

Example 2: Mobius function of the partition lattice, applied to counting connected graphs from all graphs. Let $\Pi_n$ be the lattice of set partitions of $\{1,\dots,n\}$, ordered by refinement ($\sigma \le \tau$ if every block of $\sigma$ is contained in a block of $\tau$; so $\hat 0$ is the all-singletons partition and $\hat 1$ is the one-block partition). This poset is finite, hence trivially locally finite. A classical computation (not reproved in full generality here, but illustrated concretely) gives, for the interval $[\hat 0, \hat 1]$ of the full lattice $\Pi_n$:

We verify this directly for $n=4$ by the defining recursion, rather than quoting the general formula blindly. The interval $[\hat 0,\hat 1]$ in $\Pi_4$ consists of all set partitions of $\{1,2,3,4\}$, grouped by the number of blocks $k$: there are $S(4,k)$ (Stirling numbers of the second kind) partitions into $k$ blocks: $S(4,1)=1$, $S(4,2)=7$, $S(4,3)=6$, $S(4,4)=1$ (total $15$ partitions, correct since $B_4=15$, the $4$th Bell number). A key structural fact used to compute $\mu(\hat 0, \sigma)$: for any partition $\sigma$ with blocks of sizes $b_1,\dots,b_k$, the interval $[\hat 0,\sigma]$ in $\Pi_n$ is isomorphic to the product $\Pi_{b_1}\times \cdots \times \Pi_{b_k}$ of smaller partition lattices, and $\mu$ is multiplicative over products of posets: $\mu_{(P\times Q)}((x,y),(x',y')) = \mu_P(x,x')\mu_Q(y,y')$. Hence

Apply this to every partition of $\{1,2,3,4\}$ and sum using $\sum_{\sigma \le \hat 1}\mu(\hat 0,\sigma) = 0$ solved for the top term, i.e. directly compute $\mu(\hat 0,\hat 1)$ from the recursion $\mu(\hat 0,\hat 1) = -\sum_{\sigma < \hat 1}\mu(\hat 0,\sigma)$:

• $k=1$ block (only $\hat 0$ itself is excluded from this count — wait, $k=1$ here is $\hat 1$ itself, excluded from the sum): skip.
• $k=4$: the single partition $\hat 0 = \{1\}\{2\}\{3\}\{4\}$, block sizes all $1$: $\mu(\hat0,\hat0)=1$. Contributes $1$.
• $k=3$: $6$ partitions of type $\{2,1,1\}$ (one pair, two singletons), each with $\mu = (-1)^{2-1}(2-1)! \cdot (-1)^0 0! \cdot(-1)^0 0! = (-1)(1)(1)(1) = -1$. Contributes $6 \times (-1) = -6$.
• $k=2$: two block-type shapes: $\{3,1\}$ (a triple and a singleton) and $\{2,2\}$ (two pairs). Number of $\{3,1\}$-partitions: $\binom{4}{3}=4$; each has $\mu = (-1)^{3-1}(3-1)!\cdot(-1)^0 0! = (1)(2)(1) = 2$. Contributes $4\times 2 = 8$. Number of $\{2,2\}$-partitions: $\binom{4}{2}/2 = 3$; each has $\mu = [(-1)^{1}(1)!]^2 = (-1)^2 = 1$. Contributes $3\times 1 = 3$. Total for $k=2$: $8+3=11$.

Check block-count totals: $1$ ($k=4$) $+ 6$ ($k=3$) $+ 4+3=7$ ($k=2$) $= 14$, plus $\hat 1$ itself $=15=B_4$. Correct. Sum of $\mu(\hat 0,\sigma)$ over all $\sigma < \hat 1$: $1 + (-6) + 11 = 6$. So

confirming the formula for $n=4$.

Application. Let $c_n$ = number of connected labeled graphs on $n$ vertices, and $g_n = 2^{\binom n 2}$ = number of all labeled graphs on $n$ vertices. Every graph decomposes uniquely into connected components, giving a partition of the vertex set; grouping by the induced partition $\sigma$, the number of graphs whose components are exactly the blocks of $\sigma$ is $\prod_{\text{blocks }B} c_{|B|}$, and summing over all $\sigma \ge$ a fixed finer structure recovers $g_n$ as a sum over $\Pi_n$. Concretely, for $n=4$:

with $c_1 = 1$. This exhibits $g_n$ as built from $c_n$ by summation over $\Pi_n$; Mobius inversion on $\Pi_n$ (exactly the mechanism above) is the standard route to solving for $c_n$ in terms of $g_1,\dots,g_n$, foreshadowing how partition-lattice Mobius functions recur when counting labeled structures built from smaller connected or indecomposable blocks — the same combinatorial engine that powers block-design counting arguments in Combinatorial Designs.

:::warning[The classic error: assuming $\mu$ depends only on $|[x,y]|$] A very common mistake is to guess that $\mu(x,y)$ is some universal function of the interval's size alone (as it happens to be on the divisor lattice for principal ideals, and on chains). This is false in general: $\mu(x,y)$ depends on the full internal structure — the number and arrangement of elements strictly between $x$ and $y$ — not merely on $|[x,y]|$. Two intervals with the same cardinality can have different $\mu$-values; for instance in the partition lattice $\Pi_4$, the interval $[\hat0,\sigma]$ for $\sigma$ of type $\{2,1,1\}$ has $\mu=-1$ while for $\sigma$ of type $\{2,2\}$ has $\mu=1$, yet both intervals have the same number of elements (both isomorphic to a $2$-element chain times a point, but with different multiplicities of the isomorphism factors — one must actually track the isomorphism type of $[x,y]$ as a poset, not just its size). Always recompute $\mu$ from the recursion or from a verified structural (product/interval) formula — never from cardinality alone.