moebius-inversion

Möbius Inversion Skill

"The Möbius function inverts summation over divisors - the fundamental tool connecting local constraints to global structure."

Overview

Möbius inversion provides:

1. Alternating sums - Invert cumulative sums to get point values
2. Chromatic polynomials - Count colorings via bond lattice
3. Incidence algebras - Algebraic structure on posets
4. Centrality predicates - Validate node importance via inversion

Classical Möbius Function

Definition

For positive integers:

μ(n) = { 1      if n = 1
       { (-1)^k if n = p₁p₂...pₖ (k distinct primes)
       { 0      if n has squared prime factor

Key Values

Implementation

function moebius(n)
    if n == 1
        return 1
    end
    
    # Factor n
    factors = factor(n)
    
    # Check for squared factors
    for (p, e) in factors
        if e > 1
            return 0
        end
    end
    
    # (-1)^(number of prime factors)
    return (-1)^length(factors)
end

Möbius Inversion Formula

For Divisors

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

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

Example: Euler's Totient

# φ(n) counts integers 1 ≤ k ≤ n with gcd(k,n) = 1
# We have: n = Σ_{d|n} φ(d)
# By Möbius inversion: φ(n) = Σ_{d|n} μ(n/d) × d

function euler_totient(n)
    result = 0
    for d in divisors(n)
        result += moebius(n ÷ d) * d
    end
    return result
end

Möbius on Posets

General Definition

For a locally finite poset (P, ≤), the Möbius function μ: P × P → ℤ is:

μ(x, x) = 1
μ(x, y) = -Σ_{x ≤ z < y} μ(x, z)  if x < y
μ(x, y) = 0                        if x ≰ y

Inversion on Posets

If f(x) = Σ_{y ≤ x} g(y) then: