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)^{|B\setminus A|}\qquad(A\subseteq B)$

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

Equivalently, the comparable pairs split as follows:

| $|B\setminus A|$ | 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\lessdot2,\quad1\lessdot3,\quad2\lessdot4,\quad2\lessdot6,\quad3\lessdot6,\quad4\lessdot12,\quad6\lessdot12.$

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/a)$. Hence the full table is obtained from

$\mu(1)=1,\quad \mu(2)=-1,\quad \mu(3)=-1,\quad \mu(4)=0,\quad \mu(6)=1,\quad \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 $\bot$, top $\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)^{\lvert B\setminus A\rvert}$ gives

$\mu(\bot,\bot)=1,\qquad \mu(\bot,a)=\mu(\bot,b)=-1,\qquad \mu(\bot,\top)=1.$

The endpoint recurrence displays the same computation directly:

$1-1-1+\mu(\bot,\top)=0,$

and hence $\mu(\bot,\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}\varphi(d)$

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

$\varphi(n)=\sum_{d\mid n}\mu(d)g(n/d)=\sum_{d\mid n}\mu(d)\frac nd.$

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

$\varphi(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 $\varphi(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).

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]$).