Ihara Zeta Function Skill

Ihara Zeta Function Skill

"The Ihara zeta function encodes all non-backtracking closed walks - the 'prime cycles' of a graph."

Overview

The Ihara zeta function generalizes the Riemann zeta function to graphs:

1. Prime cycles - Non-backtracking closed walks (graph analog of primes)
2. Determinant formula - ζ_G(u)^{-1} = det(I - uB) relation
3. Ramanujan connection - Riemann Hypothesis analog for graphs
4. Non-backtracking matrix - Central object for spectral clustering

Definition

Ihara Zeta Function

For a graph G, the Ihara zeta function is:

ζ_G(u) = ∏_{[C]} (1 - u^{|C|})^{-1}

where:

• Product is over equivalence classes [C] of primitive closed non-backtracking walks
• |C| is the length of the cycle
• Primitive = not a power of a shorter cycle

Non-Backtracking Walk

A walk v₀ → v₁ → v₂ → ... → vₖ is non-backtracking if:

vᵢ₊₁ ≠ vᵢ₋₁  for all i

(Never immediately return to the previous vertex)

The Determinant Formula

Bass-Hashimoto Formula

ζ_G(u)^{-1} = (1 - u²)^{|E| - |V|} · det(I - uB)

where B is the non-backtracking matrix.

Non-Backtracking Matrix

Indexed by directed edges (e, f) where head(e) = tail(f) and e ≠ f⁻¹:

function non_backtracking_matrix(G)
    # Directed edges: 2|E| entries
    directed_edges = [(u,v) for (u,v) in edges(G) 
                      for dir in [(u,v), (v,u)]]
    
    m = length(directed_edges)
    B = zeros(m, m)
    
    for (i, e) in enumerate(directed_edges)
        for (j, f) in enumerate(directed_edges)
            # e = (a→b), f = (c→d)
            # Connect if b = c AND a ≠ d (non-backtracking)
            if e[2] == f[1] && e[1] != f[2]
                B[i, j] = 1
            end
        end
    end
    
    return B
end

Prime Cycles and Möbius

Connection to Number Theory

Möbius Function on Paths

A path of length n is prime (non-backtracking) iff μ(n) ≠ 0:

function is_prime_path(path)
    """
    Check if path is non-backtracking (prime).
    Equivalent to μ(length) ≠ 0 in our encoding.
    """
    for i in 2:length(path)-1
        if path[i-1] == path[i+1]
            return false  # Backtracking detected
        end
    end
    return true
end

function moebius_filter(paths)
    """
    Filter to prime (non-backtracking) paths using Möbius.
    μ(n) ≠ 0 ⟺ n is squarefree ⟺ no repeated factors ⟺ no backtracking.
    """
    return filter(is_prime_path, paths)
end

Ramanujan and Riemann Hypothesis

Graph Riemann Hypothesis

A d-regular graph G satisfies the Graph Riemann Hypothesis if all poles of ζ_G(u) in |u| < 1/√(d-1) lie on the circle |u| = 1/√(d-1).

Theorem: G is Ramanujan ⟺ G satisfies the Graph Riemann Hypothesis.

Verification

function check_graph_riemann_hypothesis(G)
    d = degree(G)
    B = non_backtracking_matrix(G)
    
    # Eigenvalues of B
    eigenvalues = eigvals(B)
    
    # Poles of zeta at 1/λ for each eigenvalue λ
    poles = 1 ./ eigenvalues
    
    # Check: all poles with |u| < 1/√(d-1) lie on |u| = 1/√(d-1)
    critical_radius = 1 / √(d - 1)
    
    for pole in poles
        r = abs(pole)
        if r < critical_radius && abs(r - critical_radius) > 0.001
            return false  # Pole inside critical circle but not on it
        end
    end
    
    return true
end

Spectral Clustering via Non-Backtracking

The Spectral Redemption Theorem

Bordenave-Lelarge-Massoulié (2015):

Non-backtracking spectral clustering succeeds down to the information-theoretic threshold, where adjacency-based methods fail.

function non_backtracking_clustering(G, k)
    """
    Cluster graph into k communities using non-backtracking eigenvectors.
    
    Succeeds where spectral clustering on adjacency matrix fails
    (the 'spectral redemption' phenomenon).
    """
    B = non_backtracking_matrix(G)
    
    # Get top k+1 eigenvectors (skip trivial)
    λ, V = eigen(B)
    idx = sortperm(abs.(λ), rev=true)
    
    # Project directed edge eigenvectors to vertices
    vertex_embeddings = project_to_vertices(G, V[:, idx[2:k+1]])
    
    # Cluster in embedding space
    return kmeans(vertex_embeddings, k)
end

Zeta Function Computation

Direct Computation

function ihara_zeta_coefficient(G, n)
    """
    Coefficient of u^n in log ζ_G(u).
    
    = (1/​n) × (number of primitive closed non-backtracking walks of length n)
    """
    B = non_backtracking_matrix(G)
    
    # tr(B^n) counts all closed non-backtracking walks of length n
    # Möbius inversion extracts primitive ones
    total = tr(B^n)
    
    # Subtract non-primitive (powers of shorter cycles)
    primitive_count = 0
    for d in divisors(n)
        if d < n
            primitive_count += moebius(n ÷ d) * ihara_zeta_coefficient(G, d) * d
        end
    end
    
    return (total - primitive_count) / n
end

Via Determinant

function ihara_zeta_inverse(G, u)
    """
    Compute ζ_G(u)^{-1} using Bass-Hashimoto formula.
    """
    B = non_backtracking_matrix(G)
    n_vertices = nv(G)
    n_edges = ne(G)
    
    # ζ_G(u)^{-1} = (1 - u²)^{|E| - |V|} × det(I - uB)
    return (1 - u^2)^(n_edges - n_vertices) * det(I - u * B)
end

GF(3) Triad Integration

Trit Assignment

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

The Tritwise Triangle

         Ihara Zeta (Graphs)
              /\
             /  \
            /    \
           /      \
    Möbius -------- Chromatic
  (Number Theory)  (Combinatorics)

All three connect via:

• Ihara ↔ Möbius: Prime cycles counted by Möbius inversion
• Möbius ↔ Chromatic: P(G,k) via Möbius on bond lattice
• Chromatic ↔ Ihara: Both encode graph structure

DuckDB Schema

CREATE TABLE prime_cycles (
    cycle_id VARCHAR PRIMARY KEY,
    graph_id VARCHAR,
    vertices VARCHAR[],
    length INT,
    is_primitive BOOLEAN,
    equivalence_class INT,
    seed BIGINT
);

CREATE TABLE zeta_coefficients (
    graph_id VARCHAR,
    n INT,
    coefficient FLOAT,
    primitive_count INT,
    computed_at TIMESTAMP,
    PRIMARY KEY (graph_id, n)
);

CREATE TABLE non_backtracking_spectrum (
    graph_id VARCHAR PRIMARY KEY,
    eigenvalues FLOAT[],
    spectral_radius FLOAT,
    satisfies_grh BOOLEAN,  -- Graph Riemann Hypothesis
    is_ramanujan BOOLEAN
);

Commands

just ihara-zeta graph.json           # Compute zeta function
just ihara-primes graph.json 10      # List prime cycles up to length 10
just ihara-grh graph.json            # Check Graph Riemann Hypothesis
just ihara-cluster graph.json 3      # Non-backtracking clustering
just ihara-spectrum graph.json       # Eigenvalues of B matrix

Literature

1. Ihara (1966) - Original definition for p-adic groups
2. Bass (1992) - Determinant formula (Bass-Hashimoto)
3. Hashimoto (1989) - Non-backtracking matrix connection
4. Stark-Terras (1996) - Survey of graph zeta functions
5. Bordenave et al. (2015) - Spectral redemption via non-backtracking

Related Skills

• ramanujan-expander - Spectral gap and Alon-Boppana
• moebius-inversion - Alternating sums, prime extraction
• three-match - Graph coloring (chromatic polynomial)
• acsets - Graph representation