Posetに対するメビウスの反転公式

$(P, \leq)$ をposetとする(反射律・推移律・反対称律を満たす)。 $P$ が局所有限であるとは、任意の $x\leq y$ に対して $\{z\in P\mid x\leq z\leq y\}$ が有限集合であるときにいう。

局所有限なposet $P$ に対して、Möbius関数 $\mu(\cdot, \cdot)$ を

$\displaystyle \sum_{x\leq z \leq y}\mu(x,z)=\delta_{xy}$

が成り立つように定義する( $x\leq y$ に対してのみ $\mu(x, y)$ を定義する。 $\delta_{xy}$ はKroneckerのデルタ。well-defined)。

定理 (Möbiusの反転公式) $P$ を局所有限なposetとし、 $f, g$ を関数 $P\to\mathbb{C}$ とする。このとき、 $P_y:=\{x\in P \mid x\leq y\}$ が有限集合であるような $y \in P$ に対して

$\displaystyle g(y)=\sum_{x \leq y}f(x)$

が成り立つことと

$\displaystyle f(y)=\sum_{x \leq y}\mu(x,y)g(x)$

が成り立つことは同値である。

証明. $P_y$ が有限集合であるような $y \in P$ をとって固定する。 $P_y=\{x_1,\dots, x_n\}$ とする( $n=\#P_y$ )。横ベクトル $v, w$ , $(n\times n)$ -行列 $A, B$ を

$\displaystyle v:=(f(x_i) )_{1\leq i \leq n},\quad w:=(g(x_i) )_{1\leq i\leq n},\quad A:=(\epsilon_{ij})_{1\leq i,j\leq n},\quad B:=(\epsilon'_{ij})_{1\leq i,j\leq n}$

と定義する。ここで、

$\displaystyle \epsilon_{ij}:=\begin{cases}1 & (x_i\leq x_j) \\ 0 & (\text{otherwise})\end{cases},\quad \epsilon'_{ij}:=\begin{cases}\mu(x_i, x_j) & (x_i\leq x_j) \\ 0 & (\text{otherwise})\end{cases}$

である。

$\displaystyle vA=\Biggl(\sum_{x_i\leq x_j}f(x_i)\Biggr)_{1\leq j\leq n},\quad wB=\Biggl(\sum_{x_i\leq x_j}\mu(x_i, x_j)g(x_i)\Biggr)_{1\leq j\leq n}$

なので、 $y$ に対する主張の同値性を $y$ だけではなく $x_1, \dots, x_n$ 全てに対して同時に考えたものは

$w=vA \quad \Longleftrightarrow \quad v=wB$

という同値性で表すことができる。これは $A$ と $B$ が逆行列の関係にあれば成立するが、実際

$\displaystyle BA= \Biggl(\sum_{k=1}^n\epsilon'_{ik}\epsilon_{kj}\Biggr)_{1\leq i,j\leq n}= \Biggl(\sum_{x_i\leq x_k \leq x_j}\mu(x_i, x_k)\Biggr)_{1\leq i,j\leq n}=(\delta_{ij})_{1\leq i,j\leq n}$

なので証明が完了する。 Q.E.D.

$P=\mathbb{N}$ (正整数全体集合)のときを考える。整除関係によって順序を与えると、 $d\mid n$ であるとき

$\displaystyle \mu(d, n)=\mu\left(\frac{n}{d}\right)$

が成り立つ。ここで、右辺の $\mu$ は通常のMöbius関数である。過去記事
実際、過去記事の補題１より、

$\displaystyle \sum_{d\mid d' \mid n}\mu\left(\frac{d'}{d}\right)=\sum_{d''\mid \frac{n}{d}}\mu(d'')=\delta_{dn}$

が成り立っている。従って、この場合の定理は過去記事のMöbiusの反転公式(その一)を与える。

次に、通常の大小関係によって $\mathbb{N}$ に順序を与えると、正整数 $n$ に対して $\mu(n,n)=1$ であり、 $n\geq 2$ であれば $\mu(n-1,n)=-1$ 、 $n\geq 3$ であれば $\mu(m,n)=0$ ( $m\leq n-2$ )がわかる。よって、定理は数列 $a_n, b_n$ に対して