Incidence Algebras

The incidence algebra of a finite poset $P$ has a basis indexed by its intervals — the pairs $x ≤ y$ — and a product that is composition:

$$e_{[x,y]} \cdot e_{[u,z]} = \begin{cases} e_{[x,z]} & y = u \\ 0 & \text{otherwise}\end{cases}$$

Composable intervals compose; non-composable ones annihilate. That makes this the first family here whose product is usually zero — an honest annihilation, not a refusal to answer.

The point is the Möbius function

The zeta function $ζ(x,y) = 1$ on every interval is an element of this algebra, and because a poset can be listed in a linear extension, $ζ$ is upper-triangular with ones on the diagonal — so it is invertible over the integers. Its inverse is the Möbius function $μ$, defined by the recursion that inverting forces:

$$μ(x,x) = 1, \qquad μ(x,y) = -\sum_{x ≤ z < y} μ(x,z).$$

That single fact — $ζ * μ = δ$ — is Möbius inversion, and it is the test the whole package rests on, checked as a matrix identity on every poset here.

What makes it worth building is that specialising the poset recovers classical theorems.

The divisor lattice is number theory

Order the divisors of $n$ by divisibility, and the poset Möbius function of $[a,b]$ is exactly the classical $μ(b/a)$ — zero when a square divides it, $(-1)^k$ otherwise. Number theory's Möbius function is not an analogy here; it is this one, on this poset.

#μ on the divisors

30 = 2·3·5 is squarefree with three primes, so μ = −1. 12 is divisible by 4, so μ = 0.

In$\mathrm{MoebiusFunction}(\mathrm{DivisorLattice}(30), 1, 30)$Out$-1$In$\mathrm{MoebiusFunction}(\mathrm{DivisorLattice}(12), 1, 12)$Out$0$In$\mathrm{MoebiusFunction}(\mathrm{DivisorLattice}(30), 5, 30)$Out$1$

source · editable

<notatio-cell value="MoebiusFunction(DivisorLattice(30), 1, 30)" data-allow-mismatch="children" /> <notatio-cell value="MoebiusFunction(DivisorLattice(12), 1, 12)" data-allow-mismatch="children" /> <notatio-cell value="MoebiusFunction(DivisorLattice(30), 5, 30)" data-allow-mismatch="children" />

The tests check this against an independently written classical $μ$ for every interval of $D(12)$, $D(30)$, $D(36)$, $D(60)$ and $D(210)$.

The Boolean lattice is inclusion–exclusion

Order subsets of $\{1,\ldots,n\}$ by inclusion and $μ([S,T]) = (-1)^{|T ∖ S|}$. Möbius inversion over this poset is the inclusion–exclusion principle — the alternating signs everyone writes by hand are the Möbius function of the Boolean lattice.

#μ on subsets

Three elements added, so (−1)³. Adding two gives +1.

In$\mathrm{MoebiusFunction}(\mathrm{BooleanLattice}(3), \bigl\lbrack\bigr\rbrack, \bigl\lbrack1, 2, 3\bigr\rbrack)$Out$-1$In$\mathrm{MoebiusFunction}(\mathrm{BooleanLattice}(3), \bigl\lbrack\bigr\rbrack, \bigl\lbrack1, 2\bigr\rbrack)$Out$1$In$\mathrm{MoebiusFunction}(\mathrm{BooleanLattice}(3), \bigl\lbrack1\bigr\rbrack, \bigl\lbrack1, 2, 3\bigr\rbrack)$Out$1$

source · editable

<notatio-cell value="MoebiusFunction(BooleanLattice(3), [], [1, 2, 3])" data-allow-mismatch="children" /> <notatio-cell value="MoebiusFunction(BooleanLattice(3), [], [1, 2])" data-allow-mismatch="children" /> <notatio-cell value="MoebiusFunction(BooleanLattice(3), [1], [1, 2, 3])" data-allow-mismatch="children" />

Inversion, both ways

PosetSumDown computes $g(y) = \sum_{x ≤ y} f(x)$; MoebiusInvert undoes it. The two are inverse on every poset here, which is the theorem in executable form.

#Möbius inversion

Sum down the chain, then invert: the original comes back. On a chain the inversion is just first differences.

In$\mathrm{PosetSumDown}(\mathrm{Chain}(4), \bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$\bigl\lbrack1, 3, 6, 10\bigr\rbrack$In$\mathrm{MoebiusInvert}(\mathrm{Chain}(4), \mathrm{PosetSumDown}(\mathrm{Chain}(4), \bigl\lbrack1, 2, 3, 4\bigr\rbrack))$Out$\bigl\lbrack1, 2, 3, 4\bigr\rbrack$

source · editable

<notatio-cell value="PosetSumDown(Chain(4), [1, 2, 3, 4])" data-allow-mismatch="children" /> <notatio-cell value="MoebiusInvert(Chain(4), PosetSumDown(Chain(4), [1, 2, 3, 4]))" data-allow-mismatch="children" />

Dimension counts intervals

#How big is the algebra?

A chain on n has C(n+1,2) intervals; the Boolean lattice on n has 3ⁿ — for each element, it is in S, in T\S, or in neither.

In$\mathrm{AlgebraDimension}(\mathrm{IncidenceAlgebra}(\mathrm{Chain}(4)))$Out$10$In$\mathrm{AlgebraDimension}(\mathrm{IncidenceAlgebra}(\mathrm{BooleanLattice}(3)))$Out$27$In$\mathrm{AlgebraDimension}(\mathrm{IncidenceAlgebra}(\mathrm{DivisorLattice}(12)))$Out$18$

source · editable

<notatio-cell value="AlgebraDimension(IncidenceAlgebra(Chain(4)))" data-allow-mismatch="children" /> <notatio-cell value="AlgebraDimension(IncidenceAlgebra(BooleanLattice(3)))" data-allow-mismatch="children" /> <notatio-cell value="AlgebraDimension(IncidenceAlgebra(DivisorLattice(12)))" data-allow-mismatch="children" />

Things worth knowing

The linear extension is load-bearing, and it is easy to get wrong. Elements are stored so that $i ≤ j$ whenever element $i ≤$ element $j$; that is what makes $ζ$ triangular and therefore invertible over ℤ. Sorting with "is $a ≤ b$?" as a comparator does not produce one — on a genuine partial order that comparator is not transitive, and DivisorLattice(60) came out with 12 before 3. Sorting by how many elements lie below each one does work, because $x < y$ forces a strictly larger down-set.

Posets available: Chain(n), BooleanLattice(n) (elements are subsets), DivisorLattice(n) (elements are divisors). The element type differs per poset, and each one reads and prints its own.

Not built yet. The partition lattice — whose Möbius function is $(-1)^{k-1}(k-1)!$, and which would connect this page to the diagram algebras and set partitions. Also the characteristic polynomial, and general element arithmetic: only the interval basis and the two named functions $ζ$ and $μ$ are here, not arbitrary elements of the algebra.