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

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

MENU
トップ > ★大学数学 > 【組合せ論】メビウスの反転公式3　「 Poset における zeta function(ゼータ関数)とMöbius function(メビウス関数)」

【組合せ論】メビウスの反転公式3　「 Poset における zeta function(ゼータ関数)とMöbius function(メビウス関数)」

★大学数学 *【組合せ論】メビウスの反転公式 ・組合せ論

Posetでのメビウスの反転公式に向けて、最後の準備を行います。

今回は前回定義した incidence algebra (隣接代数)の元としての zeta function (ゼータ関数、ζ関数)を導入し、その"逆元"として Möbius function (メビウス関数)を構成します。

 

用語に関しては前回の記事を踏襲しますので、ご参照ください。 

math-topology.hatenablog.com

 

 

 

隣接代数の積に関する「単位元」「逆元」

 

補題1(\delta関数)

Locally finite poset P における incidence algebra I(P) の元 \delta を以下で定義する。

Interval [ x,y] に対して、

\delta (x,y)=\left\{ \begin{array}{ll}1　　(x=y) \\0　　(otherwise)\end{array} \right.

 

このとき任意の f\in I(P) に関して以下の等式が成り立つ。

f\ast \delta =f

\delta\ast f =f

( \ast は convolution を表す。)

 

証明は convolution の定義 ( (f\ast g)(x,y)=\displaystyle\sum_{x\le z\le y}f(x,z)g(z,y) ) に従って計算することで即座に得られます。

この \delta が incidence algebra の積に関する単位元の役割を果たしています。

定義から分かるようにいわゆる Kronecker delta のようなものとも言えます。

( P が有限の場合は隣接代数の元は行列で書けますが、convolution は行列の積、 \delta関数は単位行列に対応します。)

 

命題2(Incidence algebra の「逆元」)

P を locally finite poset とする。

f\in I(P) について、任意の x\in P に対し f(x,x)\ne 0 が成り立つとき、以下の等式を満たす g \in I(P) が一意的に定まる。

f\ast g=g \ast f =\delta

 

アイデアとしては、 P が有限集合の場合に f と同一視できる上三角行列について逆行列を考えるときと近くなります。

f(x,x)\ne 0 という条件も「対角成分が 0 でない」という上三角行列が逆行列を持つための条件の類似という見方もできますね。

さて証明を行います。

(証明)

まず g\ast f=\delta となる g を"順序良く"定義していきます。

 

Step1 g(x,x) の定義

x\in P に対して、

g(x,x)=\dfrac{1}{f(x,x)} 

と定義します。

 

Step2 g(x,y) の定義

x\lt y となる P の2元に対して g(x,y) を次のように帰納的に定義していきます。

x\le z\lt y となる任意の z\in P について g(x,z) が定義されているとき、

g(x,y)=-g(y,y)\displaystyle\sum_{x\le z\lt y}g(x,z)f(z,y)

と定義します。

突然降ってきたような定義に見えますが、右辺は convolution の有限和から z=y のときだけを抜いた形になっており、convolution の結果が \delta になるように無理矢理 有限和を調整しているような定義となっています。

また locally finite poset という P の性質からこの定義により、 g(x,y) が一意に定まるようになっています。

 

さて、このようにして定義が完了した  g について、 f との convolution を計算します。

(g\ast f )(x,x)= g(x,x)f(x,x) =1

となり、 x\lt y について

g(x,y)=-g(y,y)\displaystyle\sum_{x\le z\lt y}g(x,z)f(z,y)

を順次変形していくと

g(x,y)f(y,y)=-\displaystyle\sum_{x\le z\lt y}g(x,z)f(z,y)

g(x,y)f(y,y)+\displaystyle\sum_{x\le z\lt y}g(x,z)f(z,y)=0

\displaystyle\sum_{x\le z\le y}g(x,z)f(z,y)=0

(g\ast f)(x,y)=0

を得ます。*1

以上により、 g\ast f=\delta となります。

 

次に f\ast h=\delta となる h を g と同様に帰納的に与えます。

h(x,x)=\dfrac{1}{f(x,x)}

h(x,y)=-h(x,x)\displaystyle\sum_{x\lt z\le y}f(x,z)h(z,y)

すると、このとき g と同様の計算により

f\ast h =\delta となります。

 

 g=h となることを、よくある手法で示します。

いまわかっていることは g\ast f=\delta および  f\ast h =\delta ですから

補題1を用いると

(g\ast f)\ast h=\delta \ast h =h

g\ast (f\ast h)=g\ast \delta =g

となります。

これら2つは前回示した convolution の associativity により一致するので

g=h となります。

これにより

g\ast f=f\ast g= \delta

となることが分かりました。

 

最後に g の一意性を示します。

g\ast f= g' \ast f= \delta

となる g' が存在したとしましょう。

するとこのとき

(g\ast f)\ast g= (g' \ast f)\ast g

g\ast (f\ast g)=g'\ast (f\ast g)

g=g'

となります。

よって g はただ一つに定まります。

 

(証明終わり)

 

Zeta function と Möbius function 

いよいよメビウスの反転公式に用いる最後の道具の準備です。

 

命題3(Zeta function と Möbius function)

P を locally finite poset とする。

Zeta function \zeta \in I(P) を以下で定義する。

任意のinterval [x,y] に対して \zeta(x,y)=1. *2

このとき zeta function \zeta に対して

\mu \ast \zeta = \zeta \ast \mu =\delta 

となる \mu\in I(P) が一意的に定まる。

この \mu を Möbius function と呼ぶ。

 

証明は言うまでもありませんが命題2を使うだけです。*3

 

さて、これで Möbius function は定義されたのですが、このままだと \mu の具体的な形が分からないので、命題2の証明で出てきた g の構成を再利用しておきます。

すると以下のように書けます。

\mu (x,x) =1 

x\lt y のとき、

\mu(x,y)=-\displaystyle\sum_{x\le z \lt y} \mu(x,z)

 

参考文献

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

まとめ

 今回は証明メインになってしまいましたが、次回は今回導入した zeta function と Möbius function を Poset 上の関数に「作用」させることでメビウスの反転公式を証明することになります。

「つなぎの回」でしたが帰納的に関数を定義するなど、locally finite poset 特有の関数の作り方にも出会えました。

 

それでは今回も最後までお読みいただきありがとうございました。

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

次の記事

 

 

math-topology.hatenablog.com

 

*1:わざとらしい定義のおかげでこのようにできます。

*2:定値関数です。

*3:定義から特に \zeta(x,x)\ne 0 が言えるので命題2が使えます。