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:

g(x) = Σ_{y ≤ x} μ(y, x) × f(y)

Implementation

struct Poset
    elements::Vector
    leq::Function  # (x, y) -> Bool
end

function moebius_poset(P::Poset, x, y)
    if x == y
        return 1
    end
    if !P.leq(x, y)
        return 0
    end
    
    # Sum over interval [x, y)
    result = 0
    for z in P.elements
        if P.leq(x, z) && P.leq(z, y) && z != y
            result -= moebius_poset(P, x, z)
        end
    end
    return result
end

Chromatic Polynomial

Bond Lattice

For a graph G, the bond lattice L(G) consists of partitions of V(G) induced by edge subsets.

Whitney's Formula

The chromatic polynomial P(G, k) counts proper k-colorings:

P(G, k) = Σ_{π ∈ L(G)} μ(0̂, π) × k^{|π|}

where |π| is the number of parts in partition π.

Implementation

function chromatic_polynomial(G, k)
    """
    Compute P(G, k) via Möbius inversion on bond lattice.
    """
    partitions = bond_lattice(G)
    
    result = 0
    for π in partitions
        μ_val = moebius_bond_lattice(G, partition_0, π)
        result += μ_val * k^(num_parts(π))
    end
    
    return result
end

Deletion-Contraction

Alternative recursive formula:

function chromatic_deletion_contraction(G, k)
    if ne(G) == 0
        return k^nv(G)
    end
    
    e = first(edges(G))
    G_delete = delete_edge(G, e)
    G_contract = contract_edge(G, e)
    
    return chromatic_deletion_contraction(G_delete, k) - 
           chromatic_deletion_contraction(G_contract, k)
end

Alternating Möbius for GF(3)

Sign Inversion Symmetry

For GF(3) = {-1, 0, +1}:

Action:     {-, 0, +}
Perception: {+, 0, -}  (Möbius-inverted)

μ × μ = identity (applying twice returns original)

Perception-Action Duality

function moebius_duality(state::GF3)
    """
    Möbius inversion creates observer/observed duality.
    Action and perception are inverted images.
    """
    # μ(3) = -1 for our tritwise system
    μ_3 = -1
    
    return state * μ_3
end

# Verify involution: μ ∘ μ = id
@assert moebius_duality(moebius_duality(1)) == 1
@assert moebius_duality(moebius_duality(-1)) == -1
@assert moebius_duality(moebius_duality(0)) == 0

Centrality Validity via Inversion

Local-Global Inversion

function centrality_moebius_valid(G, centrality::Vector)
    """
    Validate centrality using Möbius inversion.
    
    Local constraint: c(v) = Σ_{u ∈ N(v)} contribution(u)
    Global invariant: Σ_v c(v) = 1
    
    Möbius inversion recovers individual contributions from sums.
    """
    n = nv(G)
    
    # Build divisibility-like structure on graph
    # Each node "divides" its neighbors
    contributions = zeros(n)
    
    for v in 1:n
        local_sum = 0.0
        for u in neighbors(G, v)
            # Möbius contribution from u
            dist = shortest_path_length(G, 1, u)  # Use node 1 as reference
            μ_val = moebius(dist + 1)  # +1 to avoid μ(0)
            local_sum += μ_val * centrality[u]
        end
        contributions[v] = local_sum
    end
    
    # Validity: contributions should be consistent
    return all(abs.(contributions .- mean(contributions)) .< 0.1)
end

Alternating Harmonic Centrality

function alternating_harmonic_centrality(G)
    """
    Centrality via alternating sums (Möbius-weighted paths).
    
    c(v) = Σ_{k≥1} μ(k) × (paths of length k from v) / k
    """
    n = nv(G)
    centrality = zeros(n)
    
    A = adjacency_matrix(G)
    max_k = diameter(G)
    
    for v in 1:n
        for k in 1:max_k
            μ_k = moebius(k)
            if μ_k != 0
                # Count paths of length k from v
                paths_k = A^k[v, :]
                centrality[v] += μ_k * sum(paths_k) / k
            end
        end
    end
    
    # Normalize
    return centrality ./ sum(abs.(centrality))
end

Incidence Algebra

Definition

The incidence algebra I(P) of a poset P consists of functions f: P × P → ℂ where f(x, y) = 0 if x ≰ y.

Convolution Product

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

Key Elements

Implementation

struct IncidenceAlgebra
    poset::Poset
end

function convolve(I::IncidenceAlgebra, f, g)
    P = I.poset
    result = Dict{Tuple, Number}()
    
    for x in P.elements, y in P.elements
        if !P.leq(x, y)
            result[(x, y)] = 0
            continue
        end
        
        sum = 0
        for z in P.elements
            if P.leq(x, z) && P.leq(z, y)
                sum += f(x, z) * g(z, y)
            end
        end
        result[(x, y)] = sum
    end
    
    return (x, y) -> result[(x, y)]
end

# Verify: ζ * μ = δ
function verify_inversion(I::IncidenceAlgebra)
    ζ = (x, y) -> I.poset.leq(x, y) ? 1 : 0
    μ = (x, y) -> moebius_poset(I.poset, x, y)
    δ = (x, y) -> x == y ? 1 : 0
    
    ζμ = convolve(I, ζ, μ)
    
    for x in I.poset.elements, y in I.poset.elements
        @assert ζμ(x, y) == δ(x, y)
    end
    return true
end

GF(3) Triad Integration

Trit Assignment

Conservation: (-1) + (0) + (+1) = 0 ✓

μ(3) = -1 is Central

For GF(3), the key Möbius value is:

μ(3) = -1  (3 is prime)

This means:
- Tritwise inversion flips sign
- Three iterations: μ³ = -μ (mod 3 behavior)
- Connects to spectral gap via λ₂ ≥ 2√2

DuckDB Schema

CREATE TABLE moebius_values (
    n INT PRIMARY KEY,
    mu INT,  -- -1, 0, or 1
    is_squarefree BOOLEAN,
    prime_factors INT[],
    computed_at TIMESTAMP
);

CREATE TABLE poset_moebius (
    poset_id VARCHAR,
    x VARCHAR,
    y VARCHAR,
    mu_xy INT,
    PRIMARY KEY (poset_id, x, y)
);

CREATE TABLE chromatic_coefficients (
    graph_id VARCHAR,
    k INT,
    p_g_k BIGINT,  -- P(G, k)
    bond_lattice_size INT,
    computed_at TIMESTAMP,
    PRIMARY KEY (graph_id, k)
);

CREATE TABLE centrality_alternating (
    graph_id VARCHAR,
    vertex_id INT,
    harmonic_centrality FLOAT,
    moebius_valid BOOLEAN,
    PRIMARY KEY (graph_id, vertex_id)
);

Commands

just moebius-table 100           # Print μ(n) for n ≤ 100
just moebius-invert data.json    # Apply inversion to sums
just moebius-chromatic graph.json 5  # P(G, 5)
just moebius-centrality graph.json   # Alternating harmonic centrality
just moebius-verify graph.json       # Validate centrality predicates

Literature

1. Möbius (1831) - Original number-theoretic definition
2. Rota (1964) - "On the Foundations of Combinatorial Theory I: Theory of Möbius Functions"
3. Stanley (1986) - "Enumerative Combinatorics" (comprehensive treatment)
4. Cioabă & Murty - Chromatic polynomial via Möbius
5. Music Topos (2024) - GF(3) integration and alternating centrality

Related Skills

• ramanujan-expander - Spectral validation
• ihara-zeta - Prime cycle extraction
• three-match - 3-coloring constraints
• acsets - Bond lattice as C-set
• influence-propagation - Centrality validation