MoebiusFunction

The Möbius function $\mu(x,y)$ of a finite poset — the inverse of the zeta function in the incidence algebra. Specialising the poset recovers number theory's $\mu$ and inclusion–exclusion.

WikipediaIncidence algebra↗MathWorldMoebiusFunction↗WikidataQ371133↗

MoebiusFunction(poset, x, y)$\mu$ on the interval $[x,y]$, and 0 when $x \not\le y$

Typed signatures

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

Domain: Incidence algebras

Details

• Defined by $\mu(x,x) = 1$ and $\mu(x,y) = -\sum_{x \le z < y}\mu(x,z)$ — which is exactly the statement that $\mu$ inverts $\zeta$
• On DivisorLattice(n), $\mu([a,b])$ is the classical number-theoretic $\mu(b/a)$
• On BooleanLattice(n), $\mu([S,T]) = (-1)^{|T \setminus S|}$ — the signs of inclusion–exclusion
• On a chain, $\mu$ is 1 on a point, $-1$ on a cover, and 0 on anything longer
• Posets: Chain(n), BooleanLattice(n) (elements are subsets), DivisorLattice(n) (elements are divisors)

Examples

Basic #

$30 = 2\cdot3\cdot5$ is squarefree with three primes

live ↗

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

Properties #

4 divides 12, so $\mu$ vanishes

live ↗

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

$(-1)^3$ — inclusion–exclusion

live ↗

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

not a cover, so zero

live ↗

In$\mathrm{MoebiusFunction}(\mathrm{Chain}(5), 2, 4)$Out$0$

About

Examples	4
Crosswalk	WikipediaMathWorldWikidata

See also: MoebiusInvert, PosetZeta, PosetElements