【組合せ論】メビウスの反転公式4　「 Poset におけるメビウスの反転公式の証明」

いよいよ今回は Poset におけるメビウスの反転公式を証明しようと思います。

証明の肝となるのは、 zeta function (ゼータ関数、ζ関数) の逆元として Möbius function (メビウス関数)が与えられることです。

このことは前回に詳細を紹介していますので、気になる方は前回の記事をどうぞ。

math-topology.hatenablog.com

メビウスの反転公式と証明
証明の気持ち
参考文献
まとめ
次の記事

メビウスの反転公式と証明

早速ですが、主張は以下のようになります。

定理(メビウスの反転公式)

$P$ を Poset とする。

任意の $P$ の元 $t$ に対して $P$ の部分集合 $I_{t}=\{ s\in P | s\le t \}$ が有限集合であるとする。(このとき特に $P$ は locally finite poset になります。)*1

このとき $P$ 上の関数 $f,g: P\longrightarrow \mathbb{C}$ について、以下の条件(1)(2)は同値である。

(1) 任意の $x\in P$ について $g(x)=\displaystyle\sum_{y\le x}f(y)$ となる。

(2) 任意の $x\in P$ について $f(x)=\displaystyle\sum_{y\le x}g(y)\mu (y,x)$ となる。　

具体例は次回の記事で紹介しますが、メビウスの反転公式の「気持ち」としては、関数 $f$ の和の形で表された関数 $g$ という関係性を"反転"させて $g$ の和の形で $f$ を復元できる！みたいな感じでしょうか。

まず、証明を述べたうえで「証明の気持ち」に関しても突っ込んでいこうと思います。

(証明)

準備として(1)を言いかえます。

$\displaystyle\sum_{y\le x}f(y)=\sum_{y\le x}f(y)\zeta (y,x)$

( (2)の形に寄せています。 )

( (1) $\Longrightarrow$ (2)について )

任意の $x$ について

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

が成り立つとき、

$\displaystyle\sum_{y\le x}g(y)\mu (y,x)$

$=\displaystyle\sum_{z\in I_{y} ,y \in [z,x] }f(z)\zeta (z,y) \mu (y,x)$ 　( $I_{x}$ が有限集合であることから有限和になります。)

$=\displaystyle\sum_{z\in I_{x} }f(z) (\zeta\ast\mu )(z,x)$ 　( $z$ を fix して $y$ から足し合わせています。有限和なので可能です。)

$=\displaystyle\sum_{z\in I_{x} }f(z) \delta (z,x)$ 　( $\delta(x,x)=1$ ですが、他は $0$ になります。)

$=f(x)$

となり(2)が成り立ちます。

( (1) $\Longleftarrow$ (2)について )

先ほどと同様の計算を行います。

任意の $x$ について

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

が成り立つとき、

$\displaystyle\sum_{y\le x}f(y)\zeta (y,x)$

$=\displaystyle\sum_{z\in I_{y} ,y \in [z,x] }g(z)\mu (z,y)\zeta (y,x)$

$=\displaystyle\sum_{z \in I_{x} }g(z)(\mu\ast\zeta) (z,x)$

$=\displaystyle\sum_{z \in I_{x} }g(z)\delta (z,x)$

$=g(x)$

となり(1)が成り立ちます。

(証明終わり)

証明の気持ち

証明を見ていると和の計算をがりがり進めているようにも見えてしまいます。

そこで、もっと応用が利く形で「証明の気持ち」というものにも触れておきます。

ただ、ここからの話は本題からは若干逸れます。

まず、メビウスの反転公式の主張は、実は「 $P$ 上の関数に incidence algebra (隣接代数)が作用している」といっているだけとも言えます。

$f$ に $\zeta$ を作用させたものが(1)の右辺であり、 $g$ に $\mu$ を作用させたものが(2)の右辺とみることが出来ますね。

したがって( (1) $\Longleftarrow$ (2)について )に関しては( (1) $\Longrightarrow$ (2)について )と全く同じ流れをとっているのも当然ですね。(逆元を作用させているだけです。)

また、別証明として $f$ や $g$ を incidence algebra の元として以下のように拡張することで、(1)(2)を convolution で書きかえることができ、前回導入した「逆元」の存在から攻めることも可能です。

$\tilde{f}(x,y)=f(y)\delta(x,y)$

ちなみに、参考文献[Sta]では incidence algebra の作用で証明を終わらせています。

参考文献

[Sta] Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press40 W. 20 St. New York, NYUnited States, 2012.

リンク

まとめ

今回はやや短めですが、メビウスの反転公式を証明しました。

古典的なメビウスの反転公式とも定理の主張は心なしか似ていますね。

しかし、今回は Poset *2に対して成り立つものなので、多くの Poset で役立ちそうです。

次回はメビウスの反転公式の具体的な応用に迫ります。

最後までお読みいただきありがとうございます。

次回もどうぞよろしくお願いいたします。

math-topology.hatenablog.com

*1:定理の条件は locally finite よりも強力な条件と言えます。また、locally finite かつ任意の元より小さいまたは一致するような最小元( initial )が存在することよりは弱い条件です。

*2:ある程度"良い"条件を満たした Poset ですが、locally finite かつ最小元があれば OK

とぽろじい　～大人の数学自由研究～

高校数学から分かる新しい数学、大学で学ぶ数学を少しずつまとめていくブログです。ゆくゆくは本にまとめたいと思っています。

【組合せ論】メビウスの反転公式4　「 Poset におけるメビウスの反転公式の証明」

メビウスの反転公式と証明

証明の気持ち

参考文献

まとめ

次の記事