Problem set 4: General Möbius function

1 Generalized Möbius Function

1.1 Definition: Generalized Möbius Function

Let \((A,\leq)\) be a partially ordered set (poset) such that, for every \(a\in A\), there are only finitely many elements smaller than \(a\).

The generalized Möbius function \(\mu\) is defined on pairs of comparable elements \((a,b)\), where \(a\leq b\), by the recurrence

\[ \mu(a,b)= \begin{cases} 1, & a=b,\\[6pt] -\displaystyle\sum_{a\leq z<b}\mu(a,z), & a<b. \end{cases} \]

Throughout this problem set, we consider only posets satisfying the finiteness condition above.

1.2 Problems

Consider the partially ordered set consisting of five elements

\[ A=\{a,b,c,d,e\}, \]

with the order generated by the relations

\[ a\leq b,\qquad a\leq c,\qquad b\leq d,\qquad c\leq d,\qquad d\leq e. \]

Find the values

\[ \mu(a,b) \qquad\text{and}\qquad \mu(a,e). \]

For which integers \(n\in\mathbb Z\) does there exist a partially ordered set \((A,\leq)\) and elements \(a,b\in A\) such that

\[ \mu(a,b)=n? \]

Consider the partially ordered set \(\mathbb N\) with the divisibility relation:

\[ a\preceq b \iff a\mid b. \]

(a) Prove that

\[ \mu(a,b)=\mu^*\left(\frac ba\right), \]

where \(\mu^*\) denotes the classical number-theoretic Möbius function.

(b) How does the generalized Möbius function change if we replace \(\mathbb N\) with

\[ \mathbb N\setminus\{5\}, \]

while keeping the divisibility relation?

(c) How does the generalized Möbius function change if we replace \(\mathbb N\) with

\[ \mathbb N\setminus\{15\}, \]

while keeping the divisibility relation?

Let \((A,\leq)\) be a partially ordered set, and let \(\mu\) be its generalized Möbius function.

(a) Suppose \(a,b\in A\) and \(a<b\).

Prove that

\[ \sum_{a\leq z\leq b}\mu(z,b)=0. \]

(b) Suppose a function \(\mu'\) is defined on pairs of comparable elements \((a,b)\), where \(a\leq b\), by the recurrence

\[ \sum_{a\leq z\leq b}\mu'(z,b) = \begin{cases} 1, & a=b,\\ 0, & a<b. \end{cases} \]

Prove that

\[ \mu=\mu', \]

that is,

\[ \mu(a,b)=\mu'(a,b) \]

for every pair of comparable elements \(a\leq b\).

1.3 Generalized Möbius Inversion Formula

Let \((A,\leq)\) be a partially ordered set, and let \(\mu\) be its generalized Möbius function.

Suppose \(f:A\to\mathbb R\) is an arbitrary function, and define \(g:A\to\mathbb R\) by

\[ g(x)=\sum_{y\leq x}f(y). \]

Then the generalized Möbius inversion formula states that

\[ \boxed{ f(x)=\sum_{y\leq x}\mu(y,x)g(y). } \]

Consider the partially ordered set \(\mathbb N\) with the usual order \(\leq\).

(a) Find the generalized Möbius function for this poset.

(b) What does the generalized Möbius inversion formula look like in this case?

Let \(A\) be a finite set, and consider the partially ordered set

\[ (2^A,\supseteq), \]

where \(2^A\) denotes the set of all subsets of \(A\), ordered by reverse inclusion.

(a) Find the generalized Möbius function for this poset.

Consider separately the cases

\[ |A|=2 \qquad\text{and}\qquad |A|=3. \]

(b) Let \(U\) be a set, and let

\[ B_1,B_2,B_3\subseteq U. \]

For every subset of indices

\[ S\subseteq\{1,2,3\}, \]

define

\[ f(S) = \left| \left\{ a\in U: \begin{array}{ll} a\in B_i & \text{for all }i\in S,\\ a\notin B_i & \text{for all }i\notin S \end{array} \right\} \right|. \]

Apply the generalized Möbius inversion formula from part (a) to the function \(f(S)\).

What formula do you obtain?

Consider the partially ordered set \((X,\preceq)\), where \(X\) is the set of vertices of the four-dimensional cube:

\[ X=\{(v_1,v_2,v_3,v_4):v_i\in\{0,1\}\}. \]

The partial order is defined coordinatewise:

\[ (v_1,v_2,v_3,v_4) \preceq (w_1,w_2,w_3,w_4) \]

if and only if

\[ v_i\leq w_i \qquad \text{for every }i=1,2,3,4. \]

Let

\[ A=(0,0,0,0), \qquad B=(1,1,1,1). \]

Find

\[ \mu(A,B). \]

Let \((X,\preceq)\) be a partially ordered set.

Suppose

\[ A,B\subseteq X \]

and

\[ a,b\in A\cap B, \qquad a\preceq b. \]

It is known that

\[ \mu_A(a,b)=\mu_B(a,b)=1, \]

where \(\mu_S(x,y)\) denotes the generalized Möbius function of the induced poset on \(S\).

What values can

\[ \mu_{A\cap B}(a,b) \]

take?

Let \((A,\leq)\) be a partially ordered set, and let \(\mu\) be its generalized Möbius function.

For \(x,y\in A\), let \(p_k\) denote the number of chains of the form

\[ a_0=x<a_1<\cdots<a_k=y. \]

Prove that

\[ \boxed{ \mu(x,y) = p_0-p_1+p_2-p_3+\cdots. } \]