MoebiusInvert

Möbius inversion: given $g(y) = \sum_{x \le y} f(x)$, recover $f$. The inverse of PosetSumDown, and the reason the incidence algebra is worth having.

WikipediaMöbius inversion formula↗MathWorldMoebiusInversionFormula↗MoebiusTransform↗WikidataQ1072771↗Britannicatopic/Mobius-inversion-theorem↗

MoebiusInvert(poset, values)$f(y) = \sum_{x \le y} \mu(x,y)\,g(x)$

PosetSumDown(poset, values)the map it undoes, $g(y) = \sum_{x \le y} f(x)$

Typed signatures

Type	Package	Applies
(expression<BooleanLattice> | expression<Chain> | expression<DivisorLattice>, list<number>) -> list<number>	incidence	always

Domain: Incidence algebras

Details

• Values are given in the poset's own order — see PosetElements for that listing
• On a chain this is first differences; on the Boolean lattice it is inclusion–exclusion; on the divisor lattice it is classical Möbius inversion
• The two directions are inverse on every poset, which is the theorem

Examples

Basic #

partial sums along the chain

live ↗

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

…and back again

live ↗

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

Properties #

inclusion–exclusion, round-tripped

live ↗

In$\mathrm{MoebiusInvert}(\mathrm{BooleanLattice}(2), \mathrm{PosetSumDown}(\mathrm{BooleanLattice}(2), \bigl\lbrack5, 1, 2, 7\bigr\rbrack))$Out$\bigl\lbrack5, 1, 2, 7\bigr\rbrack$

About

Examples	3
Crosswalk	WikipediaMathWorld ×2WikidataBritannica

See also: MoebiusFunction, PosetElements