Finite incidence algebras over posets

[sraaphorst]

Summary

Implement the Incidence Algebra for finite partially ordered sets (posets).

https://en.wikipedia.org/wiki/Incidence_algebra

This structure provides a formal way to perform "calculus" on posets, enabling Möbius inversion, inclusion-exclusion, and complex combinatorial enumeration within the Kosmos library.

Conceptual Overview (The "Newbie" Guide)

What is an Incidence Algebra?

If you have a poset $P$, an incidence function is a way of assigning a value (from a ring $R$) to every interval $[x, y]$ where $x \le y$.If $x \not\le y$, the value is implicitly $0$.

The "Algebra" part comes from how we multiply these functions.

Convolution: The "Secret Sauce"

Instead of standard multiplication, we use convolution $(\circ)$. To find the value of $f \circ g$ for an interval $[x, y]$, we look at all elements $z$ that "sit between" $x$ and $y$:

$$(f \circ g)(x, y) = \sum_{x \le z \le y} f(x, z) \cdot g(z, y)$$

in a Hasse diagram with intermediate elements z highlighted.

Key Functions:

Delta ($\delta$): The identity function. $\delta(x, y) = 1$ if $x=y$, and $0$ otherwise.

Zeta ($\zeta$): The "indicator" function. $\zeta(x, y) = 1$ for all $x \le y$.

Möbius ($\mu$): The "inverse" of Zeta. It allows us to undo a summation over a poset (Möbius Inversion).

Mathematical Definitions

For a finite poset $P$ and coefficient ring $R$:

The Interval Set:

$$\mathrm{Int}(P) = \{ (x, y) \in P \times P \mid x \le y \}$$

The Delta Function (Identity):

$$\delta(x, y) = \left\{ \begin{array}{ll} 1 & x = y \\\ 0 & \mbox{otherwise} \end{array} \right.$$

The Zeta Function:

$$\zeta(x, y) = \left\{ \begin{array}{ll} 1 & x \le y \\\ 0 & \mbox{otherwise} \end{array} \right.$$

The Möbius Function (Recursive Definition):

$$\mu(x, y) = \left\{ \begin{array}{ll} 1 & x = y \\\ -\sum_{x \le z < y} \mu(x, z) & x < y \end{array} \right.$$

Given a finite poset P and a coefficient ring R, the incidence algebra consists of functions

$$f : \left\{ (x, y) \in P \times P | x \le y \right\} \rightarrow R$$

with pointwise addition and convolution multiplication as defined below

$$(f \circ g)(x, y) = \sum_{x \le z \le y} f(x, z) * g(z, y)$$

This gives a natural algebraic structure over finite posets and supports zeta functions, delta functions, Möbius functions, and Möbius inversion.

Motivation

They provide a concrete bridge between:

• finite posets;
• convolution algebras;
• Möbius inversion;
• inclusion-exclusion;
• combinatorial enumeration;
• DAG/path-like decomposition ideas;
• future Hopf/combinatorial algebra work.

This is high-value infrastructure for combinatorics.

Mathematical definition

For a finite poset $P$, define the interval set:

$$\mathop{Int}(P) = \left\{ (x, y) | x \le y \right\}$$

An incidence function over a coefficient ring $R$ is a function:

$$\mathop{Int}(P) \rightarrow R$$

Addition is pointwise:

$$(f + g)(x, y) = f(x, y) + g(x, y)$$

Multiplication is convolution:

$$(f \circ g)(x, y) = \sum_{x \le z \le y} f(x, z) * g(z, y)$$

The multiplicative identity is the delta function:

$$\delta(x, y) = \left\{ \begin{array}{ll} 1 & \mbox{if } x = y \\\ 0 & \mbox{otherwise} \end{array} \right.$$

The zeta function is:

$$\zeta(x, y) = \left\{ \begin{array}{ll} 1 & x \le y \\\ 0 & \mbox{otherwise} \end{array} \right.$$

The Möbius function is the convolution inverse of zeta:

$$\mu = \zeta^{-1}$$

when the coefficient structure supports the needed negation/inversion behavior.

Packages to consider:

org.vorpal.kosmos.combinatorics.posets.incidence
org.vorpal.kosmos.algebra.incidence

Core Data Structures

We need a way to represent the intervals and the mapping of those intervals to ring elements.

/** 
 * Represents a closed interval [lower, upper] in a poset.
 */
data class Interval<P : Any>(val lower: P, val upper: P)

/**
 * An incidence function maps comparable pairs (intervals) to values in Ring R.
 */
data class IncidenceFunction<P : Any, R : Any>(
    val poset: Poset<P>,
    val values: Map<Interval<P>, R>
)

Proposed algebra constructor

We start with the ring structure, and think about the modules / algebra later.

The IncidenceRing should handle the logic for addition and convolution.

object IncidenceAlgebras {
    fun <P : Any, R : Any> incidenceRing(
        poset: Poset<P>,
        ring: Ring<R>
    ): Ring<IncidenceFunction<P, R>> = object : Ring<IncidenceFunction<P, R>> {
        
        override val zero = IncidenceFunction(poset, emptyMap())

        override fun add(a: IncidenceFunction<P, R>, b: IncidenceFunction<P, R>): IncidenceFunction<P, R> {
            val allKeys = a.values.keys + b.values.keys
            val newValues = allKeys.associateWith { interval ->
                ring.add(a.getVal(interval), b.getVal(interval))
            }
            return IncidenceFunction(poset, newValues)
        }

        override fun multiply(f: IncidenceFunction<P, R>, g: IncidenceFunction<P, R>): IncidenceFunction<P, R> {
            // Implementation of (f * g)(x, y) = sum_{x <= z <= y} f(x, z) * g(z, y)
            val newValues = mutableMapOf<Interval<P>, R>()
            
            for (interval in poset.allIntervals()) {
                val (x, y) = interval
                val sum = poset.elementsBetween(x, y).fold(ring.zero) { acc, z ->
                    val term = ring.multiply(f.getVal(x, z), g.getVal(z, y))
                    ring.add(acc, term)
                }
                if (sum != ring.zero) newValues[interval] = sum
            }
            return IncidenceFunction(poset, newValues)
        }
    }

    fun <P : Any, R : Any> incidenceAlgebra(
        poset: Poset<P>,
        coefficientRing: CommutativeRing<R>
    ): Algebra<R, IncidenceFunction<P, R>> // optional, later
}

Constructors and helpers

fun <P : Any, R : Any> IncidenceFunction<P, R>.getVal(x: P, y: P): R = 
    values[Interval(x, y)] ?: ring.zero

fun <P : Any, R : Any> zero(...)
fun <P : Any, R : Any> delta(...)
fun <P : Any, R : Any> zeta(...)
fun <P : Any, R : Any> singleton(interval, value)
fun <P : Any, R : Any> fromFunction(...)

Suggested member helpers:

operator fun get(lower: P, upper: P): R
fun support(): FiniteSet<Interval<P>>d
fun intervals(): FiniteSet<Interval<P>>

Accessing a non-comparable pair should return zero, but validate internal maps to only store comparable intervals.

Multiplication implementation

For each comparable interval $(x, y)$:

$$(f \circ g)(x, y) = \sum_{z ∈ P, x ≤ z ≤ y} f(x, z) * g(z, y)$$

Implementation sketch:

val value = poset.elements
    .filter { z -> poset.leq(x, z) && poset.leq(z, y) }
    .fold(ring.zero) { acc, z ->
        ring.add(
            acc,
            ring.mul(f[x, z], g[z, y])
        )
    }

Initial Tasks

1. nterval Validation: Ensure IncidenceFunction only stores pairs where poset.leq(x, y).
2. Topological Sort: Implement a helper to calculate $\mu$ by iterating through intervals in a rank-compatible order.
3. Standard Instances: Provide zeta(poset, ring), delta(poset, ring), and mobius(poset, ring).

Once scoped operators exist:

with(ring) {
    intervalElements.fold(zero) { acc, z ->
        acc + f[x, z] * g[z, y]
    }
}

Möbius function

For finite posets, compute $\mu$ recursively:

$$\mu(x, y) = \left\{ \begin{array}{ll} 1 & x = y \\\ -\sum_{x \le z < y} \mu(x, z) & x < y \end{array} \right.$$

This requires a topological ordering / rank-compatible traversal over intervals.

Initial implementation may restrict to finite posets where elements can be topologically sorted.

Tests

Basic interval behavior

• intervals are exactly comparable pairs;
• non-comparable pairs are not stored;
• get(x, y) works for comparable pairs;
• optional: get(x, y) returns zero for non-comparable pairs.

Known Identities for Testing

• Chain Poset: $\mu(x, y)$ should be $1$ if $x=y$, $-1$ if $y$ covers $x$, and $0$ otherwise.
• Boolean Lattice: $\mu(A, B) = (-1)^{|B \setminus A|}$.
• Divisibility Poset: Should match the classical number-theoretic Möbius function.

Ring laws

Use existing law framework:

• additive abelian group;
• multiplicative monoid;
• distributivity;
• identity;
• associativity of convolution.

Test on small finite posets to keep arithmetic simple.

Delta identity

For arbitrary incidence functions $f$:

$$\delta \circ f = f f \circ \delta = f$$

Zeta and Möbius

For known posets:

Chain $0 &lt; 1 &lt; 2 &lt; ... &lt; n$

Expected:

$$\mu(x, y) = \left\{ \begin{array}{ll} 1 & x = y \\\ -1 & y \gtrdot x \\\ 0 & \text{otherwise} \end{array} \right.$$

where $\gtrdot$ means "covers," $y$ covers $x$ if $y \gt x$ and $\not\exists z , x \le z \le y$.

Intuition

• The Hasse Diagram: In a Hasse diagram, $y$ covers $x$ if there is a direct edge drawn upward from $x$ to $y$. If you have to pass through another node to get from $x$ up to $y$, it is not a covering relation.

• Discrete Steps: You can think of a cover as the smallest possible "jump" you can make upward in the poset.

Examples

• Integers: $(\mathbb{Z}, \le)$: $5$ covers $4$, and $n+1$ covers $n$. There are no integers between $n$ and $n+1$.
• Power Set: $(\mathcal{P}(S), \subseteq)$: A set $B$ covers a set $A$ if $B$ contains exactly one more element than $A$ (i.e., $B = A \cup {e}$ for some $e \notin A$).
• Divisibility: $(\mathbb{N}, \mid)$: $12$ covers $6$ and $4$, but $12$ does not cover $3$ (because $3 &lt; 6 &lt; 12$). In this poset, $y$ covers $x$ if $y/x$ is a prime number.
• Real Numbers: $(\mathbb{R}, \le)$: No element covers another. Between any two distinct real numbers $x &lt; y$, there is always another number $z$ (like their average). This is called a dense order.

In the context of Incidence Algebras, the "length" of the intervals in terms of covering steps determines the values of functions like $\mu(x, y)$. For example, in many "nice" posets (like Eulerian posets), $\mu(x, y) = (-1)^n$ where $n$ is the number of covering steps between $x$ and $y$.

Boolean lattice

For subsets $A \subseteq B$:

$$\mu(A, B) = (-1)^{\left|B \setminus A\right|}$$

Möbius inversion

If:

$$g(x) = \sum_{y ≤ x} f(y)$$

then:

$$f(x) = \sum_{y ≤ x} \mu(y, x) g(y)$$

Initial scope

Start with finite posets only.

Do not support infinite locally finite posets yet. The locally finite definition is mathematically relevant, but Kosmos can begin with finite posets, where all intervals are automatically finite.

Non-goals for first pass

• Infinite posets.
• Topological / analytic completions.
• General category incidence algebras.
• Coalgebra / Hopf-algebra packaging.
• Optimized sparse matrix representation.

Future extensions

• Incidence coalgebras.
• Möbius inversion utilities.
• Category incidence algebras.
• Matrix representation of incidence algebras under linear extensions.
• Boolean lattice helpers.
• Divisibility posets and number-theoretic Möbius function.

Consider a strictly upper triangular matrix representation if we have a linear extension (topological sort) of the poset. For a poset of size $n$, the incidence algebra is isomorphic to a subalgebra of $M_n(R)$.