Incidence Algebras

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

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 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:

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 by divisibility, and the poset Möbius function of is exactly the classical — zero when a square divides it, 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.

source

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

The tests check this against an independently written classical for every interval of , , , and .

The Boolean lattice is inclusion–exclusion

Order subsets of by inclusion and . 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.

source

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

Inversion, both ways

PosetSumDown computes ; 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.

source

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

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.

source

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

Things worth knowing

The linear extension is load-bearing, and it is easy to get wrong. Elements are stored so that whenever element element ; that is what makes triangular and therefore invertible over ℤ. Sorting with "is ?" 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 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 , 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.