Incidence Algebras and Möbius Inversion — Examples

Let $[3]=\{1,2,3\}$ and order $2^{[3]}$ by inclusion (The Boolean lattice of subsets of a finite set and its rank levels). The complete table is determined by

$\mu (A,B)=(-1{)}^{\mathrm{\mid }B\setminus A\mathrm{\mid }}(A\subseteq B)$

(For $A\subseteq B$ in a finite Boolean lattice, $\mu (A,B)=(-1{)}^{\mid B\setminus A\mid }$). Thus the value is $1$ on the diagonal, $-1$ when $B$ adds one element, $1$ when it adds two elements, and $-1$ from $\mathrm{\varnothing }$ to $[3]$.

Equivalently, the comparable pairs split as follows:

| $\mathrm{\mid }B\setminus A\mathrm{\mid }$ | number of pairs | $\mu (A,B)$ | |---:|---:|---:| | $0$ | $8$ | $1$ | | $1$ | $12$ | $-1$ | | $2$ | $6$ | $1$ | | $3$ | $1$ | $-1$ |

For a cover $A\subset A\cup \{i\}$ the recurrence reads $1+(-1)=0$. For the top interval it reads $1+3(-1)+3(1)+(-1)=0$, in agreement with The Möbius recurrence: ${\mu }_P(x,x)=1$ and both interval sums of ${\mu }_P$ vanish when $x<y$.

For the chain $c_0<c_1<c_2<c_3$, the complete upper-triangular table is

This is On a finite chain, the Möbius function is $1$ on the diagonal, $-1$ on covers and $0$ on longer intervals: diagonal entries are $1$, cover entries are $-1$, and entries spanning more than one cover are $0$. For example, the recurrence gives $\mu (c_0,c_2)=-(1-1)=0$, then $\mu (c_0,c_3)=-(1-1+0)=0$ (The Möbius recurrence: ${\mu }_P(x,x)=1$ and both interval sums of ${\mu }_P$ vanish when $x<y$).

The positive divisors of $12$ are $1,2,3,4,6,12$. In the divisibility order (The divisibility poset of positive integers), the covers are

$1⋖2,1⋖3,2⋖4,2⋖6,3⋖6,4⋖12,6⋖12.$

For every comparable $a\mid b$, The number-theoretic Möbius function is the poset Möbius function of divisibility: $\mu (n)={\mu }_{\mid }(1,n)$ gives ${\mu }_{\mid }(a,b)=\mu (b\mathrm{/}a)$. Hence the full table is obtained from

$\mu (1)=1,\mu (2)=-1,\mu (3)=-1,\mu (4)=0,\mu (6)=1,\mu (12)=0.$

In particular, the row from $1$ is $(1,-1,-1,0,1,0)$ in the divisor order listed above. The recurrence checks the less immediate values: $1-1-1+\mu (1,6)=0$ gives $\mu (1,6)=1$, and $1-1-1+0+1+\mu (1,12)=0$ gives $\mu (1,12)=0$ (The Möbius recurrence: ${\mu }_P(x,x)=1$ and both interval sums of ${\mu }_P$ vanish when $x<y$).

Let the diamond have bottom $\mathrm{\perp }$, top $\mathrm{\top }$, and incomparable middle elements $a,b$. It is the Boolean lattice on a two-element set, so For $A\subseteq B$ in a finite Boolean lattice, $\mu (A,B)=(-1{)}^{\mid B\setminus A\mid }$ gives

$\mu (\mathrm{\perp },\mathrm{\perp })=1,\mu (\mathrm{\perp },a)=\mu (\mathrm{\perp },b)=-1,\mu (\mathrm{\perp },\mathrm{\top })=1.$

The endpoint recurrence displays the same computation directly:

$1-1-1+\mu (\mathrm{\perp },\mathrm{\top })=0,$

and hence $\mu (\mathrm{\perp },\mathrm{\top })=1$ (The Möbius recurrence: ${\mu }_P(x,x)=1$ and both interval sums of ${\mu }_P$ vanish when $x<y$).

The divisor-sum theorem from the CRT development states

$n={\sum }_{d\mid n}\phi (d)$

for every positive integer $n$ (For every positive integer $n$, ${\sum }_{d\mid n,d>0}\phi (d)=n$). Apply Classical Möbius inversion over positive divisors with $g(n)=n$ and $f(n)=\phi (n)$. The form indexed by the complementary divisor gives

$\phi (n)={\sum }_{d\mid n}\mu (d)g(n\mathrm{/}d)={\sum }_{d\mid n}\mu (d)\frac{n}{d}\mathrm{.}$

At $n=12$, the values from The number-theoretic Möbius function $\mu (n)$ from prime factorisation give

$\phi (12)=12-6-4+0+2+0=4,$

where the terms correspond to $d=1,2,3,4,6,12$. Thus Möbius inversion recovers $\phi (12)=4$ directly from the CRT divisor-sum theorem.

Convolution of incidence functions is defined on every poset, even without local finiteness (False: convolution defines an incidence algebra for every poset).

\draw[gray!65] (bot)--(m0) (bot)--(m1) (bot)--(m2) (bot)--(mn) (m0)--(top) (m1)--(top) (m2)--(top) (mn)--(top); \draw[gray!55,densely dotted] (bot)--(dots)--(top);

\node[anchor=west] at (5.15,2.05) {countably many incomparable}; \node[anchor=west] at (5.15,1.55) {middle elements}; \node[anchor=west] at (5.15,.75) {$[\bot,\top]=P$ is infinite}; \end{tikzpicture} ```

Every incidence function on a finite poset is convolution-invertible.

The endpoint Möbius value of a finite interval is determined by the number of elements in that interval (False: ${\mu }_P(x,y)$ depends only on the cardinality of $[x,y]$).

\node[elt] (c0) at (-2.7,0) {$c_0$}; \node[elt] (c1) at (-2.7,1.05) {$c_1$}; \node[elt] (c2) at (-2.7,2.1) {$c_2$}; \node[elt] (c3) at (-2.7,3.15) {$c_3$}; \draw[gray!70] (c0)--(c1)--(c2)--(c3);

\node[elt] (bot) at (2.7,0) {$\bot$}; \node[elt] (a) at (1.65,1.55) {$a$}; \node[elt] (b) at (3.75,1.55) {$b$}; \node[elt] (top) at (2.7,3.15) {$\top$}; \draw[gray!70] (bot)--(a)--(top) (bot)--(b)--(top);

\node[font=\small] at (-2.7,-.75) {$\mu(c_0,c_3)=0$}; \node[font=\small] at (2.7,-.75) {$\mu(\bot,\top)=1$}; \end{tikzpicture} ```