Möbius Inversion on Posets — Zeta & Möbius Transforms

January 2026 · 28 min read

1 — Classical Möbius Inversion

Before generalising, let’s recall the number-theoretic version. The Möbius function μ(n) is defined on positive integers:

μ(1) = 1
μ(n) = (−1)^k if n is a product of k distinct primes
μ(n) = 0 if n has a squared prime factor

The classical Möbius inversion formula states:

Classical Möbius Inversion. If g(n) = Σ_d|n f(d) for all n ≥ 1, then f(n) = Σ_d|n μ(n/d) · g(d).

Quick Example — Euler’s Totient

We know n = Σ_d|n φ(d). Applying inversion: φ(n) = Σ_d|n μ(n/d) · d. For n = 12: divisors are 1, 2, 3, 4, 6, 12.

μ(12) · 1 + μ(6) · 2 + μ(4) · 3 + μ(3) · 4 + μ(2) · 6 + μ(1) · 12
= 0 · 1 + 1 · 2 + 0 · 3 + (−1) · 4 + (−1) · 6 + 1 · 12 = 4 = φ(12) ✓

Why Does It Work?

The proof boils down to the identity Σ_d|n μ(d) = [n = 1]. Substituting the expression for g into the inversion formula and swapping summation order yields exactly this identity. This is the multiplicative viewpoint. The algebraic viewpoint — that μ is the inverse of the constant-1 function under Dirichlet convolution — generalises beautifully to posets.

Direction matters. The formula above sums over divisors of n. There is a dual form: if g(n) = Σ_{n|m, m≤N} f(m), then f(n) = Σ_{n|m, m≤N} μ(m/n) · g(m). Mixing up divisor-sum vs. multiple-sum is a classic CP bug.

2 — Posets & Incidence Algebra

Partially Ordered Sets

A poset (P, ≤) is a set P together with a relation ≤ that is reflexive (x ≤ x), antisymmetric (x ≤ y and y ≤ x ⇒ x = y), and transitive (x ≤ y and y ≤ z ⇒ x ≤ z). Many structures in combinatorics form posets:

Positive integers ordered by divisibility: a ≤ b iff a | b.
Subsets of {1,…,n} ordered by inclusion: S ≤ T iff S ⊆ T.
Partitions of a set ordered by refinement.
Any total order (chain): 1 < 2 < … < n.

The Incidence Algebra

For a locally finite poset P (every interval [x, y] = {z : x ≤ z ≤ y} is finite), the incidence algebra consists of all functions f : {(x, y) : x ≤ y} → ℝ with the convolution product:

(f * g)(x, y) = Σ_{x ≤ z ≤ y} f(x, z) · g(z, y)

The identity element is the Kronecker delta: δ(x, y) = [x = y].

The Zeta Function

The zeta function of the poset is simply: ζ(x, y) = 1 for all x ≤ y, and 0 otherwise. The “zeta transform” of a function f on elements of P is:

g(x) = Σ_{y ≤ x} f(y) = Σ_y ζ(y, x) · f(y)

The Möbius Function

The Möbius function μ of the poset is the inverse of ζ in the incidence algebra. That is, μ * ζ = ζ * μ = δ. It can be computed recursively:

μ(x, x) = 1 μ(x, y) = − Σ_{x ≤ z < y} μ(x, z) // for x < y

General Möbius Inversion. g(x) = Σ_{y ≤ x} f(y) ⇔ f(x) = Σ_{y ≤ x} μ(y, x) · g(y).

This is the master theorem. Every specific inversion formula — number-theoretic, inclusion-exclusion, SOS — is a special case for a particular poset.

3 — Möbius Function on Common Posets

The beauty of the theory is that each poset has its own Möbius function. Here are the ones that appear most often in competitive programming.

(a) Divisor Poset

P = positive integers, a ≤ b iff a | b. The Möbius function of this poset is exactly the number-theoretic μ:

μ(a, b) = μ_NT(b/a)

where μ_NT is zero when b/a has a squared prime factor, and (−1)^k when b/a is a product of k distinct primes.

(b) Boolean Lattice (Subset Poset)

P = all subsets of [n], S ≤ T iff S ⊆ T. The Möbius function is:

μ(S, T) = (−1)^{|T| − |S|}

Möbius inversion on this poset gives the inclusion-exclusion principle. If g(S) = Σ_{T ⊆ S} f(T), then f(S) = Σ_{T ⊆ S} (−1)^|S|−|T| g(T).

(c) Partition Lattice

P = set partitions of [n], ordered by refinement (π ≤ σ iff every block of π is contained in a block of σ).

For an interval [π, σ] where σ has blocks of sizes b₁, …, b_k that merge t₁, …, t_k blocks of π: μ(π, σ) = Π_i (−1)^t_i−1 (t_i−1)!

(d) Chain (Total Order)

P = {1, 2, …, n} with the usual ≤. Since every element y with x ≤ y ≤ x+1 is either x or x+1, the Möbius function is:

μ(x, x) = 1
μ(x, x+1) = −1
μ(x, y) = 0 for y > x+1

Inversion here gives the telescoping/difference formula: if g(n) = Σ_k=1ⁿ f(k), then f(n) = g(n) − g(n−1).

Unifying perspective. Inclusion-exclusion is μ on the Boolean lattice. Number-theoretic Möbius inversion is μ on the divisor lattice. Prefix-sum differencing is μ on a chain. They are all the same theorem.

4 — Subset Sum / Zeta Transform

The Sum-over-Subsets (SOS) Transform

Given a function f defined on all 2ⁿ subsets, the subset zeta transform (or SOS DP) computes:

f̂(S) = Σ_{T ⊆ S} f(T)

A naive approach iterates over all subsets of each S, giving O(3ⁿ) total work (each element is either in T, in S\T, or not in S). The SOS DP reduces this to O(n · 2ⁿ) by processing one dimension at a time:

// SOS DP — subset zeta transform
// After this, f[S] = sum of original f[T] for all T ⊆ S
for (int i = 0; i < n; i++)
    for (int S = 0; S < (1 << n); S++)
        if (S >> i & 1)
            f[S] += f[S ^ (1 << i)];

The idea: in dimension i, every mask S with bit i set absorbs the value from the mask S with bit i cleared. After processing all n dimensions, f[S] has accumulated contributions from every subset.

Möbius Inversion (Inclusion-Exclusion)

To recover the original f from f̂, we apply the Möbius transform of the Boolean lattice — which is inclusion-exclusion. The fast version:

// Subset Möbius transform (inverse of SOS)
// Recovers original f from its subset-sum transform
for (int i = 0; i < n; i++)
    for (int S = 0; S < (1 << n); S++)
        if (S >> i & 1)
            f[S] -= f[S ^ (1 << i)];

The structure is identical to the zeta transform, but with subtraction instead of addition. This reflects μ(S, T) = (−1)^|T|−|S| on the Boolean lattice.

Superset-Sum Variant

Sometimes we need the superset sum: f̂(S) = Σ_{S ⊆ T} f(T). The DP flips the condition:

// Superset zeta transform
for (int i = 0; i < n; i++)
    for (int S = (1 << n) - 1; S >= 0; S--)
        if (!((S >> i) & 1))
            f[S] += f[S | (1 << i)];

// Superset Möbius transform (inverse)
for (int i = 0; i < n; i++)
    for (int S = (1 << n) - 1; S >= 0; S--)
        if (!((S >> i) & 1))
            f[S] -= f[S | (1 << i)];

Common bug: wrong loop direction. For the subset zeta transform, iterate S in any order (the DP is independent per dimension). But be careful with the superset variant: the condition checks bit i is not set, and we add from the mask with bit i set. Swapping subset/superset conditions silently produces wrong results.

5 — Divisor Sum Transform

The Transform

Given an array f[1..N], the divisor zeta transform computes:

g(n) = Σ_{d | n} f(d)

This can be done in O(N log N) using a sieve-style iteration: for each d, add f[d] to g[d], g[2d], g[3d], …. The total work is N/1 + N/2 + … + N/N = O(N ln N).

// Divisor zeta transform: g[n] = sum of f[d] for all d | n
vector<long long> g(N + 1, 0);
for (int d = 1; d <= N; d++)
    for (int multiple = d; multiple <= N; multiple += d)
        g[multiple] += f[d];

Möbius Inversion

To recover f from g, apply the number-theoretic Möbius function:

// Divisor Möbius transform: recover f from g
// First, compute mu[] via linear sieve
vector<int> mu(N + 1, 0);
vector<int> primes;
vector<bool> is_composite(N + 1, false);
mu[1] = 1;
for (int i = 2; i <= N; i++) {
    if (!is_composite[i]) {
        primes.push_back(i);
        mu[i] = -1;
    }
    for (int p : primes) {
        if ((long long)i * p > N) break;
        is_composite[i * p] = true;
        if (i % p == 0) {
            mu[i * p] = 0;
            break;
        }
        mu[i * p] = -mu[i];
    }
}

// Now invert: f[n] = sum_{d|n} mu(n/d) * g[d]
vector<long long> f(N + 1, 0);
for (int d = 1; d <= N; d++)
    for (int multiple = d; multiple <= N; multiple += d)
        f[multiple] += mu[multiple / d] * g[d];

Alternatively, we can perform the inversion in-place via a multiplicative sieve (one prime at a time), analogous to the SOS DP for subsets:

// In-place divisor Möbius transform (prime-by-prime)
// Transforms g[] in-place to recover f[]
for (int p : primes) {
    for (int j = N / p; j >= 1; j--)
        g[j * p] -= g[j];
}

This processes one prime at a time in decreasing order of multiples, perfectly mirroring the SOS DP over bits. It runs in O(N log log N) — the same as the Sieve of Eratosthenes.

Dirichlet Convolution

The divisor sum transform is convolution with the constant-1 function (also called ζ in analytic number theory): g = f * ζ. The inversion is g * μ = f. More generally, the Dirichlet convolution of f and h is:

(f * h)(n) = Σ_{d | n} f(d) · h(n/d)

Useful identities: φ = μ * id (Euler’s totient), σ_k = id_k * ζ, and μ * ζ = ε (the identity for convolution: ε(n) = [n=1]).

Off-by-one with 0-indexing. When implementing divisor transforms, indices start at 1. If your array is 0-indexed, f[0] is meaningless and must be skipped. Starting the outer loop at d = 0 causes division by zero or infinite loops.

6 — C++ Implementations

SOS DP (Subset Zeta / Möbius)

#include <bits/stdc++.h>
using namespace std;

// Subset zeta transform: f[S] becomes sum over all T ⊆ S of original f[T]
void subset_zeta(vector<long long>& f, int n) {
    for (int i = 0; i < n; i++)
        for (int S = 0; S < (1 << n); S++)
            if (S >> i & 1)
                f[S] += f[S ^ (1 << i)];
}

// Subset Möbius transform: inverse of subset_zeta
void subset_mobius(vector<long long>& f, int n) {
    for (int i = 0; i < n; i++)
        for (int S = 0; S < (1 << n); S++)
            if (S >> i & 1)
                f[S] -= f[S ^ (1 << i)];
}

// Superset zeta transform: f[S] becomes sum over all T ⊇ S of original f[T]
void superset_zeta(vector<long long>& f, int n) {
    for (int i = 0; i < n; i++)
        for (int S = 0; S < (1 << n); S++)
            if (!((S >> i) & 1))
                f[S] += f[S | (1 << i)];
}

// Superset Möbius transform: inverse of superset_zeta
void superset_mobius(vector<long long>& f, int n) {
    for (int i = 0; i < n; i++)
        for (int S = 0; S < (1 << n); S++)
            if (!((S >> i) & 1))
                f[S] -= f[S | (1 << i)];
}

int main() {
    int n; cin >> n;
    vector<long long> f(1 << n);
    for (auto& x : f) cin >> x;

    // Compute subset sums
    vector<long long> g = f;
    subset_zeta(g, n);

    // Recover original via Möbius inversion
    subset_mobius(g, n);
    // g now equals original f

    for (int S = 0; S < (1 << n); S++)
        cout << g[S] << " \n"[S == (1 << n) - 1];
}

Divisor Sum / Möbius Transform

#include <bits/stdc++.h>
using namespace std;

struct DivisorTransform {
    int N;
    vector<int> mu, primes;

    DivisorTransform(int N) : N(N), mu(N + 1, 0) {
        vector<bool> comp(N + 1, false);
        mu[1] = 1;
        for (int i = 2; i <= N; i++) {
            if (!comp[i]) { primes.push_back(i); mu[i] = -1; }
            for (int p : primes) {
                if ((long long)i * p > N) break;
                comp[i * p] = true;
                if (i % p == 0) { mu[i * p] = 0; break; }
                mu[i * p] = -mu[i];
            }
        }
    }

    // g[n] = sum_{d|n} f[d]
    void zeta(vector<long long>& f) {
        for (int p : primes)
            for (int j = 1; j * p <= N; j++)
                f[j * p] += f[j];
    }

    // Inverse: recover f from its divisor-sum transform
    void mobius(vector<long long>& f) {
        for (int p : primes)
            for (int j = N / p; j >= 1; j--)
                f[j * p] -= f[j];
    }
};

int main() {
    int N; cin >> N;
    vector<long long> f(N + 1);
    for (int i = 1; i <= N; i++) cin >> f[i];

    DivisorTransform dt(N);
    dt.zeta(f);
    // f[n] now holds sum_{d|n} original_f[d]

    dt.mobius(f);
    // f is restored to original values

    for (int i = 1; i <= N; i++)
        cout << f[i] << " \n"[i == N];
}

General Möbius Inversion on a Small Poset

For an arbitrary poset of size n given by its adjacency (Hasse diagram), we can compute the Möbius function μ(x, y) for all pairs in O(n³) using the recursive definition and memoisation, or by inverting the zeta matrix.

#include <bits/stdc++.h>
using namespace std;

// Given: le[x][y] = true iff x <= y in the poset
// Returns: mu[x][y] for all x <= y (0 otherwise)
vector<vector<int>> compute_mobius(const vector<vector<bool>>& le, int n) {
    vector<vector<int>> mu(n, vector<int>(n, 0));
    // Process in topological order: for each x, compute mu(x, y) for y >= x
    for (int x = 0; x < n; x++) {
        mu[x][x] = 1;
        for (int y = x + 1; y < n; y++) {
            if (!le[x][y]) continue;
            int s = 0;
            for (int z = x; z < y; z++)
                if (le[x][z] && le[z][y])
                    s += mu[x][z];
            mu[x][y] = -s;
        }
    }
    return mu;
}

// General inversion: given g[x] = sum_{y <= x} f[y], recover f
vector<long long> invert(const vector<long long>& g,
                          const vector<vector<int>>& mu,
                          const vector<vector<bool>>& le, int n) {
    vector<long long> f(n, 0);
    for (int x = 0; x < n; x++)
        for (int y = 0; y <= x; y++)
            if (le[y][x])
                f[x] += (long long)mu[y][x] * g[y];
    return f;
}

int main() {
    int n; cin >> n;
    vector<vector<bool>> le(n, vector<bool>(n, false));
    // Read Hasse diagram edges and compute transitive closure
    int m; cin >> m;
    for (int i = 0; i < n; i++) le[i][i] = true;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; // u <= v (covers)
        le[u][v] = true;
    }
    // Transitive closure (Floyd-Warshall style)
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (le[i][k] && le[k][j])
                    le[i][j] = true;

    auto mu = compute_mobius(le, n);

    // Example: read g[], invert to get f[]
    vector<long long> g(n);
    for (auto& x : g) cin >> x;
    auto f = invert(g, mu, le, n);
    for (int i = 0; i < n; i++)
        cout << f[i] << " \n"[i == n - 1];
}

7 — CP Applications

Inclusion-Exclusion as Boolean Möbius Inversion

The classic inclusion-exclusion formula is exactly Möbius inversion on the Boolean lattice 2^[n]. For instance, to count integers in [1, N] not divisible by any prime in {p₁, …, p_k}:

For each subset S ⊆ {p₁, …, p_k}, let g(S) = ⌊N / Π_{p ∈ S} p⌋ (numbers divisible by all primes in S).
The answer is Σ_S (−1)^|S| g(S), which is the Möbius transform of g evaluated at ∅.

When k ≤ 20, SOS DP computes all Möbius values in O(k · 2^k).

Bitmask Problems with SOS DP

Problem pattern: Given arrays a[0..2ⁿ−1], compute for each mask S the sum/max/count over all submasks T ⊆ S (or supermasks T ⊇ S). This arises in:

Counting pairs (i, j) with a[i] AND a[j] = 0
Maximum XOR subset queries
Convolution of set functions (OR convolution, AND convolution)

OR convolution: To compute h[S] = Σ_{T₁ | T₂ = S} f[T₁] · g[T₂], apply subset zeta to both f and g, multiply pointwise, then apply subset Möbius:

// OR convolution via SOS
void or_convolve(vector<long long>& f, vector<long long>& g,
                 vector<long long>& h, int n) {
    subset_zeta(f, n);
    subset_zeta(g, n);
    h.resize(1 << n);
    for (int S = 0; S < (1 << n); S++)
        h[S] = f[S] * g[S];
    subset_mobius(h, n);
}

GCD / LCM Sums via Divisor Möbius

A very common CP pattern: compute Σ_i<j f(gcd(a_i, a_j)). The standard approach:

Let cnt[d] = number of elements divisible by d.
Let pairs[d] = C(cnt[d], 2) = number of pairs where d | gcd.
Let exact[d] = number of pairs where gcd = d exactly.
By Möbius inversion: exact[d] = Σ_{d | m} μ(m/d) · pairs[m].
Answer = Σ_d f(d) · exact[d].

Steps 1–2 run in O(N log N), step 4 is a divisor Möbius transform in O(N log log N). Total: O(N log N).

Contest shortcut. Many GCD-sum problems reduce to: (1) build a frequency/count array, (2) apply divisor zeta, (3) do pointwise computation, (4) apply divisor Möbius. Once you recognise the pattern, implementation takes < 5 minutes.

Walkthrough: Coprime Pairs Count

Problem. Given n integers a₁, …, a_n (≤ 10⁶), count pairs (i, j) with gcd(a_i, a_j) = 1.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    const int MAXV = 1000001;
    vector<long long> cnt(MAXV, 0);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        cnt[x]++;
    }

    // Divisor zeta: cnt[d] = number of a_i divisible by d
    vector<long long> div_cnt(MAXV, 0);
    for (int d = 1; d < MAXV; d++)
        for (int m = d; m < MAXV; m += d)
            div_cnt[d] += cnt[m];

    // pairs[d] = C(div_cnt[d], 2) = pairs where d | gcd
    vector<long long> pairs(MAXV, 0);
    for (int d = 1; d < MAXV; d++)
        pairs[d] = div_cnt[d] * (div_cnt[d] - 1) / 2;

    // Möbius inversion: exact[d] = pairs where gcd = d exactly
    // Compute mu via sieve
    vector<int> mu(MAXV, 0);
    mu[1] = 1;
    vector<int> primes;
    vector<bool> comp(MAXV, false);
    for (int i = 2; i < MAXV; i++) {
        if (!comp[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if ((long long)i * p >= MAXV) break;
            comp[i * p] = true;
            if (i % p == 0) { mu[i * p] = 0; break; }
            mu[i * p] = -mu[i];
        }
    }

    // Answer = sum_{d=1}^{MAXV} mu[d] * pairs[d]
    // (because exact[1] = sum_{d} mu[d] * pairs[d])
    long long ans = 0;
    for (int d = 1; d < MAXV; d++)
        ans += mu[d] * pairs[d];

    cout << ans << "\n";
}

Walkthrough: Subset OR Convolution

Problem. Given two arrays f and g of size 2ⁿ, compute h[S] = Σ_{A | B = S} f[A] · g[B] for all S.

This is directly solved by the OR convolution shown above: apply SOS zeta to f and g, multiply pointwise, then SOS Möbius. Total time: O(n · 2ⁿ).

AND vs OR convolution. For AND convolution (h[S] = Σ_{A & B = S} f[A] · g[B]), use the superset zeta/Möbius transforms instead of subset. Using subset transforms for AND convolution is a common mistake that produces completely wrong answers.

8 — Summary

Key Ideas

Möbius inversion generalises from integers to any locally finite poset.
The Möbius function μ is the inverse of the zeta function in the incidence algebra.
Classical number-theoretic μ, inclusion-exclusion, and prefix-sum differencing are all special cases.

CP Toolkit

SOS DP — O(n · 2ⁿ) zeta/Möbius on Boolean lattice.
Divisor sieve — O(N log N) or O(N log log N) zeta/Möbius on divisor lattice.
OR/AND convolution — pointwise multiply in transformed domain.
GCD sums — count by divisor, then Möbius invert.

Poset	μ(x, y)	Transform Complexity	CP Name
Chain (1 < 2 < …)	−1 if cover, else 0	O(n)	Prefix sums / differences
Boolean lattice 2^[n]	(−1)^\|T\|−\|S\|	O(n · 2ⁿ)	SOS DP / inclusion-exclusion
Divisor lattice	μ_NT(b/a)	O(N log log N)	Divisor sieve / Möbius sieve
Partition lattice	Π (−1)^t_i−1(t_i−1)!	problem-specific	(rare in CP)

Master recipe for CP. (1) Identify the underlying poset. (2) Write the “easy direction” as a zeta transform. (3) Do pointwise work in the transformed domain. (4) Apply the Möbius transform to invert. This pattern covers inclusion-exclusion, GCD sums, bitmask convolutions, and more.

In the next post, we’ll explore combinatorial species theory — a categorical framework that gives a principled way to build generating functions for labelled and unlabelled combinatorial structures.