Möbius Inversion

On a locally finite partially-ordered-set the incidence algebra consists of functions of pairs under convolution . Its unit is the Kronecker , the constant is the zeta function, and its convolution inverse is the Möbius function , fixed by .

Möbius inversion is the resulting equivalence between a quantity and its “new content” increments: for ,

The second sum is alternating and therefore ill-conditioned. Small errors in can be amplified rather than cancelled.

Proposition on the meet-semilattice cancellation-free form

Suppose is a meet-semilattice generated under intersection, so any two elements have a greatest lower bound, and suppose sums an additive observable over the indices contained in . Then every visible index has a unique minimal containing it, so the indices partition. Assigning to that minimal gives with all coefficients and no cancellation. This agrees with the alternating Möbius sum, and the unique-minimum property is the latching, or Reedy, condition on .

References

• Rota, “On the Foundations of Combinatorial Theory I: Theory of Mobius Functions,” Zeitschrift fur Wahrscheinlichkeitstheorie (1964)