Möbius inversion on posets and lattices: alternating sums, chromatic polynomials, incidence algebras, and centrality predicates.
/plugin marketplace add plurigrid/asi/plugin install plurigrid-asi-skills@plurigrid/asiThis skill inherits all available tools. When active, it can use any tool Claude has access to.
"The Möbius function inverts summation over divisors - the fundamental tool connecting local constraints to global structure."
Möbius inversion provides:
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
| n | μ(n) | Meaning |
|---|---|---|
| 1 | 1 | Identity |
| 2 | -1 | Prime |
| 3 | -1 | Prime - key for GF(3) |
| 4 | 0 | Squared (2²) |
| 5 | -1 | Prime |
| 6 | 1 | Two primes (2·3) |
| 12 | 0 | Has 2² |
| 30 | -1 | Three primes (2·3·5) |
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
If f(n) = Σ_{d|n} g(d) then:
g(n) = Σ_{d|n} μ(n/d) × f(d)
= Σ_{d|n} μ(d) × f(n/d)
# φ(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
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
If f(x) = Σ_{y ≤ x} g(y) then:
g(x) = Σ_{y ≤ x} μ(y, x) × f(y)
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
For a graph G, the bond lattice L(G) consists of partitions of V(G) induced by edge subsets.
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 π.
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
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
For GF(3) = {-1, 0, +1}:
Action: {-, 0, +}
Perception: {+, 0, -} (Möbius-inverted)
μ × μ = identity (applying twice returns original)
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
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
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
The incidence algebra I(P) of a poset P consists of functions f: P × P → ℂ where f(x, y) = 0 if x ≰ y.
(f * g)(x, y) = Σ_{x ≤ z ≤ y} f(x, z) × g(z, y)
| Element | Definition | Role |
|---|---|---|
| δ (delta) | δ(x,y) = [x = y] | Identity |
| ζ (zeta) | ζ(x,y) = [x ≤ y] | Summation |
| μ (Möbius) | ζ * μ = μ * ζ = δ | Inversion |
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
| Component | Trit | Role |
|---|---|---|
| ramanujan-expander | -1 | Validator - spectral bounds |
| ihara-zeta | 0 | Coordinator - non-backtracking |
| moebius-inversion | +1 | Generator - produces alternating sums |
Conservation: (-1) + (0) + (+1) = 0 ✓
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
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)
);
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
ramanujan-expander - Spectral validationihara-zeta - Prime cycle extractionthree-match - 3-coloring constraintsacsets - Bond lattice as C-setinfluence-propagation - Centrality validation