How to compute the Mobius function

Question

I have no clue how to begin this problem. It involves computing the Mobius inversion function $\mu$. This problem comes from Stanley's $\textit{Enumerative Combinatorics}$, vol 1, problem 70, Chapter 3. I figured out that $|E_n|=2^{n-1}$, and supposedly that is necessary to figure out the problem. Any hints are greatly appreciated.

70. [2-]* Let $E_n$ denote the poset of all subsets of $\left[n\right]$ whose elements have even sum, ordered by inclusion.

(a) [2+]* Compute $\mu\left(S, T\right)$ for all $S \leq T$ in $E_n$.

(b) [3-] Generalize (a) as follows. Let $k \geq 3$, and let $P_k$ denote the poset of all subsets of $\mathbb{P}$ whose elements have sum divisible by $k$. Given $T \leq S$ in $P_k$, let

$i_j = \sharp \left\{ n \in T - S : n \equiv j \pmod k \right\}$.

Clearly $\mu\left(S, T\right)$ depends only on the $k$-tuple $\left(i_0, i_1, \ldots, i_{k-1}\right)$, so write $\mu\left(i_0, \ldots, i_{k-1}\right)$ for $\mu\left(S, T\right)$. Show that

$$\sum\limits_{i_0,\ldots,i_{k-1}\geq 0} \mu\left(i_0, \ldots, i_{k-1}\right) \dfrac{x_0^{i_0} \cdots x_{k-1}^{i_{k-1}}}{i_0! \cdots i_{k-1}!} = k \left[ \sum\limits_{j=0}^{k-1} \exp\left( x_0 + \zeta^j x_1 + \zeta^{2j} x_2 + \cdots + \zeta^{\left(k-1\right)j} x_{k-1} \right) \right]^{-1},$$

where $\zeta$ is a primitive $k$th root of unity.

As usual in Stanley's book, $\mathbb{P}$ denotes the set of all positive integers.

Answer 1

Here’s something to get you started on (a).

We know that $\mu(S,S)=1$. Suppose that $S\subsetneqq T$, so that

$$\mu(S,T)=-\sum_{S\subseteq U\subsetneqq T}\mu(S,U)\;.$$

For $S\subseteq U$ let $m_0(U)$ and $m_1(U)$ be the numbers of even and odd integers, respectively, in $U\setminus S$:

$$m_i=|\{k\in U\setminus S:k\equiv i\!\!\!\pmod2\}|$$

for $i=0,1$.

$U$ covers $S$ in $E_n$ if and only if either

• $m_0(U)=1$ and $m_1(U)=0$, or
• $m_0(U)=0$ and $m_1(U)=2$,

and in either case $\mu(S,U)=-\mu(S,S)=-1$.

$U$ covers some $V$ that covers $S$ if and only if one of the following holds:

• $m_0(U)=2$ and $m_1(U)=0$;
• $m_0(U)=1$ and $m_1(U)=2$; or
• $m_0(U)=0$ and $m_1(U)=4$.

In each case there are exactly two sets $V\in E_n$ such that $S\subsetneqq V\subsetneqq U$; if they are $V_0$ and $V_1$, then $$\mu(S,U)=-\big(\mu(S,S)+\mu(S,V_0)+\mu(S,V_1)\big)=-(1-2)=1\;.$$

In general let $d(U)=m_0(U)+\frac12m_1(U)$; we’ve just seen that $U$ covers $S$ if and only if $d(U)=1$, and $U$ covers some $V$ that covers $S$ if and only if $d(U)=2$.

• Show that $d(U)=\ell(S,U)$, the length of the interval $[S,U]$ in $E_n$.
• Prove by induction on $d(T)$ that $\mu(S,T)=(-1)^{d(T)}=(-1)^{\ell(S,T)}$ for $S\subseteq T$.

Added (revised): The second bullet point is wrong: I flat wasn’t thinking. For instance, $$\mu(\varnothing,\{1,3,5,7\})=-\left(1-\binom42\right)=5\;,$$ not $1$, and therefore $$\mu(\varnothing,\{1,3,5,7,9,11\})=-\left(1-\binom62+5\binom64\right)=-61\;,$$ not $-1$.

Let $A(T)$ be the set of even integers in $T\setminus S$ and $B(T)$ the set of odd integers in $T\setminus S$. Let $P(T)$ be the poset of all subsets of $A(T)$, and let $Q(T)$ be the poset of all subsets of $B(T)$ of even cardinality. Then $[S,T]$ is isomorphic to the direct product $P(T)\times Q(T)$, so Proposition $\mathbf{3.8.2}$ applies. In particular, $P(T)$ is just $B_{m_0(T)}$, the Boolean algebra of rank $m_0(T)$, and you have its Möbius function from Example $\mathbf{3.8.3}$. Finally, for $Q(T)$ you should look at Theorem $\mathbf{3.13.1}$, and at Theorem $\mathbf{3.6}$ of Stanley’s A Survey of Alternating Permutations [PDF].

The first bullet point is no longer really necessary, except to help in seeing that you’re dealing with a graded poset.

The poset $E_n$ of part (a) is just the poset $P_k$ of part (b) with $k=2$; my $m_0(T)$ and $m_1(T)$ are his $i_0$ and $i_1$. To get a handle on where the result in part (b) comes from, you should first look at the special case of it in which $k=1$, even though that’s not part of the problem: it says that

$$\sum_{i\ge 0}\mu(i)\frac{x^i}{i!}=e^{-x}\;.\tag{1}$$

If you work through the definitions carefully, you’ll find that $\mu(i)$ is just $\mu(S,T)$ when $|T\setminus S|=i$, which from Example $\mathbf{3.8.3}$ is $(-1)^i$, so that $(1)$ is just the familiar power series expansion of $e^{-x}$.