ポセットと隣接代数
Abstract
ポセット上の関数に対するMöbius反転公式を示す.
Explanation
ポセット
定義
まずはポセットに関して用語の定義を確認しておく.
Definition (半順序, ポセット)
集合$ Pにおける二項関係$ {\le} \subseteq P \times Pが次の(1) - (3)を満たすとき, $ \leを$ Pの半順序 (partial order) といい, $ (P, \le)を半順序集合あるいはポセット (partially ordered set: poset) という:
(1) (反射律) 任意の$ a \in Pに対し, $ a \le a.
(2) (推移律) 任意の$ a, b, c \in Pに対し, $ a \le bかつ$ b \le cならば$ a \le c.
(3) (反対称律) 任意の$ a, b \in Pに対し, $ a \le bかつ$ b \le aならば$ a = b.
また, $ Pをポセット$ (P, \le)の台 (support) という.
文脈上半順序が明らかな場合は, 「ポセット$ (P, \le)」と書く代わりに「ポセット$ P」と略記する.
ポセットの要素$ a, b \in Pに対し, $ a \le bまたは$ b \le aが成立するとき, $ a, bは比較可能 (comparable) といい, そうでないとき比較不能 (incomparable) という. 特に, ポセット$ Pの任意の要素が比較可能なとき, 二項関係$ \leは全順序 (total order) であるといい, $ Pを全順序集合 (totally ordered set) あるいは鎖 (chain) という.
Remark
ポセット$ P = \{ p_1, \dots, p_n \}は次のように全順序化できる:DAGのトポロジカルソートと同様の操作. 実際, ポセット$ PのHasse図を書くとそれは (多重有向辺のない) DAGになっている. $ Pの極小元$ pを任意にとり, これを$ Pの最小元と設定する.
$ P \setminus \{ p \}についてもこの操作を再帰的に行う.
ポセットの要素$ a, b \in P に対し, $ a \le b かつ$ a \neq b であることを$ a < b と書く. また, ポセット上の区間は, (実数における区間と同様に) $ [x, y] := \{ z \mid x \le z \le y \} \subseteq P , $ [x, y) := \{ z \mid x \le z < y \} \subseteq P などと書く.
Definition (局所有限)
ポセット$ P が局所有限 (locally finite) であるとは, $ P の任意の閉区間$ [x, y] \subseteq P が有限集合になることをいう.
ポセットの例
Example 1
整数の集合$ \Zや実数の集合$ \Rは, 通常の大小関係$ \leについてポセットをなす. とくに, 鎖である.
Example 2
集合$ Sの冪集合$ \mathscr{P}(S)は, 包含関係$ \subseteqについてポセットをなす. $ A, B \in \mathscr{P}(S)で, $ A \not \subseteq Bかつ$ B \not \subseteq Aであることがあるため, $ \subseteqは一般には全順序ではない.
Example 3
正整数$ n \in \Z_{> 0}の正の約数の集合$ D_n := \{ m \in \Z_{> 0} \mid ~ m \mid n \}は, 整除関係$ \midについてポセットをなす. 一般には$ \midは全順序でない.
隣接代数とその性質
定義
隣接代数を定義しよう.
Definition (隣接代数)
局所有限なポセット$ Pと, 体$ Kに対し, 集合$ \mathbb{I}_K(P)を次で定める:$ x \not \le y は必ずしも$ x > y を意味しないことに注意. $ x と$ y が比較不能な場合がある.
$ \mathbb{I}_K(P) := \{ \alpha \colon P \times P \to K \mid x, y \in P, x \not \le y \Rightarrow \alpha (x, y) = 0 \}
和, スカラー倍, 積を以下で定義する:
(和) $ \alpha, \beta \in \mathbb{I}_K(P)と$ x, y \in Pに対し, $ (\alpha + \beta) (x, y) := \alpha(x, y) + \beta(x, y).
(スカラー倍) $ \alpha \in \mathbb{I}_K(P)と$ x, y \in P, $ c \in Kに対し, $ (c \alpha)(x, y) := c \alpha(x, y).
(積) $ \alpha, \beta \in \mathbb{I}_K(P) と$ x, y \in P に対し,$ (\alpha * \beta)(x, y) := \begin{cases} \sum_{z \in [x, y] } \alpha(x, z) \beta(z, y) & (x \le y) \\ 0 & (x \not \le y) \end{cases}
$ \mathbb{I}_K(P)を$ Pについての$ K上の隣接代数 (incidence algebra) という.
Remark
ポセット$ Pは局所有限なので, 積の定義における和は有限和. (これにより積はwell-defined.)
ポセット$ Pが有限集合$ P = \{ p_1, \dots, p_n \}であるとする. このとき, 写像$ \alpha \in \mathbb{I}_K(P)を$ i行$ j列に$ \alpha(p_i, p_j)を並べた行列とみなすことができる. 上で定義した演算は行列の演算と同じになっている. とくに, 全順序集合$ Pについては$ p_1 \le \dots \le p_nと順に並べ替えると, 行列が上三角行列になる.
積演算$ *は一般には可換でない. 行列積が可換でないのと同様である.
$ \mathbb{I}_K(P) の定義は, $ \alpha \in \mathbb{I}_K(P) で$ P の各閉区間$ \lbrack x, y \rbrack \subseteq P にスカラー$ \alpha(x, y) \in K を対応させていると見ることができる. (ただし, 区間にならないような組$ (x, y)の値は$ 0としている.)
以下では, $ \mathbb{I}_K(P)が代数をなすことを確認しよう. まず, $ \mathbb{I}_K(P)が体$ K上のベクトル空間になっていることは容易に確認できるので, 後は積$ *について性質を確認していく.
Lemma 1 (積の双線形性)
隣接代数$ \mathbb{I}_K(P)の積$ *は双線形写像である, i.e., 任意の$ \alpha, \beta, \gamma \in \mathbb{I}_K(P)と任意の$ k, l \in Kに対し,
$ (k \alpha + l \beta) * \gamma = k (\alpha * \gamma) + l (\beta * \gamma) かつ $ \alpha * (k \beta + l \gamma) = k (\alpha * \beta) + l (\alpha * \gamma).
Proof
総和$ \sumの線形性から成り立つ. $ \blacksquare
Lemma 2 (積の結合性)
隣接代数$ \mathbb{I}_K(P)の積$ *は結合的である, i.e., 任意の$ \alpha, \beta, \gamma \in \mathbb{I}_K(P)に対し,
$ \alpha * (\beta * \gamma) = (\alpha * \beta) * \gamma.
Proof
$ x, y \in Pを任意にとる. $ x \not \le yのときの成立は明らかなので, $ x \le yとする.
$ (\alpha * (\beta * \gamma))(x, y)
$ = \sum_{z \in [x, y]} \alpha(x, z) (\beta * \gamma)(z, y)
$ = \sum_{z \in [x, y]} \alpha(x, z) \left( \sum_{w \in [z, y]}\beta(z, w) \gamma(w, y) \right)
$ = \sum_{z \in [x, y]} \sum_{w \in [z, y]} \alpha(x, z) \beta(z, w) \gamma(w, y)
$ = \sum_{w \in [x, y]} \left( \sum_{z \in [x, w]} \alpha(x, z) \beta(z, w)\right) \gamma(w, y) ($ x \le z \le w \le yに注意して和の順序を変えた.)
$ = \sum_{w \in [x, y]} (\alpha * \beta)(x, w) \gamma(w, y)
$ = ((\alpha * \beta) * \gamma)(x, y) . $ \blacksquare
次のKroneckerのデルタ$ \deltaは, 隣接代数$ \mathbb{I}_K(P)の積の単位元である.
Definition (Kroneckerのデルタ)
関数$ \delta (x, y) := \begin{cases} 1 & (x = y) \\ 0 & (\mathrm{otherwise}) \end{cases}は$ \mathbb{I}_K(P)の元であり, Kroneckerのデルタ (Kronecker delta) という.
Lemma 3 (積の単位元)
Kroneckerのデルタ$ \delta \in \mathbb{I}_K(P)は, $ \mathbb{I}_K(P)の積の (両側) 単位元である, i.e.,
$ \alpha * \delta = \delta * \alpha = \alpha.
Proof
定義から明らか.$ \blacksquare
以上のLemma 1〜3より, $ \mathbb{I}_K(P)が代数であることがわかった. 命題としてまとめておく.
Proposition 4
$ (\mathbb{I}_K(P), *, \delta)は, 代数である.
積の逆元
隣接代数$ \mathbb{I}_K(P)の積$ *の逆元が存在するための必要十分条件を示しておく.
Theorem 5 (積の逆元)
$ \alpha \in \mathbb{I}_K(P)とする. 以下の(1) - (4)は同値:
(1) $ \alphaは左逆元をもつ, i.e., $ \exists \beta \in \mathbb{I}_K(P), \beta * \alpha = \delta.
(2) $ \alphaは右逆元をもつ, i.e., $ \exists \gamma \in \mathbb{I}_K(P), \alpha * \gamma = \delta.
(3) $ \alphaは両側逆元をもつ, i.e., $ \exists \alpha^{-1} \in \mathbb{I}_K(P), \alpha^{-1} * \alpha = \alpha * \alpha^{-1} = \delta.
(4) 任意の$ x \in Pに対し, $ \alpha(x, x) \neq 0.
Proof
まず, (2)と(4)が同値であることを示す.
(2) $ \Longleftrightarrow $ \begin{cases} (\alpha * \gamma)(x, x) = \alpha (x, x) \gamma (x, x) = 1 & (x \in P) \\ (\alpha * \gamma)(x, y) = \alpha(x, x) \gamma(x, y) + \sum_{z \in (x, y \rbrack} \alpha(x, z) \gamma(z, y) = 0 & (x < y) \end{cases}
$ \Longleftrightarrow$ \begin{cases} \alpha (x, x) \gamma (x, x) = 1 & (x \in P) \\ \alpha(x, x) \gamma(x, y) = - \sum_{z \in (x, y \rbrack} \alpha(x, z) \gamma(z, y) & (x < y) \end{cases} — (★)
とくに一つ目の等式より$ \alpha(x, x) \neq 0 ~ (x \in P)がわかる. さらに,
(★)$ \Longleftrightarrow$ \begin{cases} \gamma (x, x) = \cfrac{1}{\alpha(x, x)} & (x \in P) \\ \gamma(x, y) = - \cfrac{1}{\alpha(x, x)} \sum_{z \in (x, y \rbrack} \alpha(x, z) \gamma(z, y) & (x < y) \end{cases}
であり, $ \gammaは$ \alphaに対して一意的な表示をもつ.
(1)と(4)の同値性も同様である.
両側逆元は片側逆元でもあるから, (4)から(3)を示せば証明が完了する. 任意の$ x \in Pに対し, $ \alpha(x, x) \neq 0なので, $ \exists \beta \in \mathbb{I}_K(P), \beta * \alpha = \deltaと$ \exists \gamma \in \mathbb{I}_K(P), \alpha * \gamma = \deltaが成立する. $ \beta * \alpha = \deltaの両辺に右から$ \gammaをかければ, $ \beta = \gammaを得るので, $ \alpha^{-1} = \beta = \gammaである.$ \blacksquare
証明中に得られた逆元の表示を, 以下に系としてまとめておく.
Corollary 6 (逆元の表示)
$ \alpha \in \mathbb{I}_K(P)が逆元$ \alpha^{-1}をもつとき, 逆元は次式で表示される:
$ \alpha^{-1} (x, y) = \begin{cases} \cfrac{1}{\alpha(x, x)} & (x = y) \\ - \cfrac{1}{\alpha(x, x)} \sum_{z \in (x, y \rbrack} \alpha(x, z) \alpha^{-1}(z, y) & (x < y) \\ 0 & (\mathrm{otherwise}) \end{cases}
Remark
$ x < yのときは, $ x < z \le yに対する$ \alpha^{-1}(z, y)が全て求まっていれば求まることに注意する.
上の証明では$ \gamma = \alpha^{-1}が右逆元であるという条件から逆元の表示を求めたが, 左逆元であると考えて同様の操作をすることで, $ x < yのときは以下のようにも表示できる.
$ \alpha^{-1} (x, y) = - \cfrac{1}{\alpha(y, y)} \sum_{z \in [x, y)} \alpha^{-1}(x, z) \alpha(z, y) \pod{x < y}
やはりこれも, $ x \le z < yに対する$ \alpha^{-1}(x, z)が全て求まっていれば求まる.
以下では, $ \mathbb{I}_K(P)の元であって, 積の逆元をもつものの集合を$ \mathbb{I}_K(P)^{\times}と書く.
ゼータ関数とMöbius関数
隣接代数には, ゼータ関数と呼ばれる有用な元がある.
Definition (ゼータ関数)
関数$ \zeta(x, y) := \begin{cases} 1 & (x \le y) \\ 0 & (\mathrm{otherwise}) \end{cases}は$ \mathbb{I}_K(P)の元であり, ゼータ関数 (zeta function) という.
$ \zeta(x, x) = 1 ~ (x \in P)であるから, Theorem 5よりゼータ関数$ \zetaには積の逆元$ \mu = \zeta^{-1}が存在する. $ \muはMöbius関数と呼ばれる:
Definition (Möbius関数)
関数$ \mu(x, y) := \zeta^{-1}(x, y) = \begin{cases} 1 & (x = y) \\ - \sum_{z \in [x, y)} \mu(x, z) & (x < y) \\ 0 & (\mathrm{otherwise}) \end{cases}は$ \mathbb{I}_K(P)の元であり, Möbius関数 (Möbius function) という.
$ \mu(x, y)の表示については, Corollary 6のRemarkで述べたとおりである.
隣接代数上での反転公式
まず, 隣接代数上での一般形の反転公式を示す.
Theorem 7 (隣接代数上での一般形の反転公式)
ポセット$ Pについての体$ K上の隣接代数$ \mathbb{I}_K(P)を考える. 積の逆元を持つ$ \alpha \in \mathbb{I}_K(P)^{\times}と, $ f, g \in \mathbb{I}_K(P)に対して, 次式が成立する:
$ f = g * \alpha \Longleftrightarrow g = f * \alpha^{-1}.
和の形で明示的に表すと, 次式がすべての$ x \le y ~ (x, y \in P)に対して成立する:
$ f(x, y) = \sum_{z \in \lbrack x, y \rbrack} g(x, z) \alpha (z, y) \Longleftrightarrow g(x, y) = \sum_{z \in \lbrack x, y \rbrack} f(x, z) \alpha^{-1} (z, y).
Proof
$ f = g * \alpha \Longleftrightarrow f * \alpha^{-1} = g * (\alpha * \alpha^{-1}) \Longleftrightarrow f * \alpha^{-1} = g * \delta \Longleftrightarrow f * \alpha^{-1} = g. $ \blacksquare
Remark
同様に, $ f = \alpha * g \Longleftrightarrow g = \alpha^{-1} * fも成立する.
この系として, 隣接代数上のMöbius反転公式が成立する.
Corollary 8 (隣接代数上のMöbius反転公式)
ポセット$ Pについての体$ K上の隣接代数$ \mathbb{I}_K(P)を考える. $ f, g \in \mathbb{I}_K(P)に対して, 次式が成立する:
$ f = g * \zeta \Longleftrightarrow g = f * \mu.
和の形で明示的に表すと, 次式がすべての$ x \le y ~ (x, y \in P)に対して成立する:
$ f(x, y) = \sum_{z \in \lbrack x, y \rbrack} g(x, z) \Longleftrightarrow g(x, y) = \sum_{z \in \lbrack x, y \rbrack} f(x, z) \mu (z, y).
ポセット上の関数に対する反転公式
以下では, 上で示した隣接代数上のMöbius反転公式を, 「特定の条件」を持ったポセット上の関数についてのMöbius反転公式に拡張する. このために, ポセット$ Pについて, 隣接代数$ \mathbb{I}_K(P)の$ P上の関数集合$ K^{P} = \{ f \colon P \to K\}への作用を考えよう.
隣接代数のポセット上の関数集合への右作用
まず「特定の条件」を表現するために主順序イデアルを定義してから, (右) 作用の定義を与える.
Definition (主順序イデアル)
ポセット$ Pと, $ p \in Pに対し, 集合
$ \downarrow p := \{ q \in P \mid q \le p \}
を, $ pによって生成される主順序イデアル (principal order ideal) という.
つまり, 主順序イデアルは$ p以下の元をすべて集めた集合である.
Definition (ポセット上の関数集合への隣接代数の右作用)
任意の主順序イデアルが有限集合となるポセット$ Pと体$ Kを考える.
隣接代数$ \mathbb{I}_K(P)の集合$ K^Pへの右作用$ \bullet \colon K^P \times \mathbb{I}_K(P) \to K^Pを以下で定義する:
$ f \in K^Pと$ \alpha \in \mathbb{I}_K(P)に対し,$ (f \bullet \alpha)(x) := \sum_{z \in \downarrow x} f(z) \alpha (z, x) \pod{x \in P}.
Remark
任意の主順序イデアルが有限集合となるポセットは, とくに, 局所有限である (ゆえに隣接代数の定義は正しく意味を持つ). 実際, 区間$ [x, y] = \downarrow y \setminus \downarrow x \cup \{ x \} は有限集合である.
ポセット$ Pの任意の主順序イデアルが有限なので, 作用の定義における和は有限和. (これにより作用はwell-defined.)
ポセット$ Pが有限集合$ P = \{ p_1, \dots, p_n \}であるとする. このとき, 隣接代数の元$ \alphaは行列とみなせるのであった. 同様に, 写像$ f \in K^Pを, 第$ i番目の要素が$ f(p_i)となる横ベクトルとみなすことができる. 上で定義した演算は, 横ベクトルに左から行列$ \alphaを掛ける演算になっている ($ z \not \le xの部分は$ \alpha (z, x) = 0であることから, $ z \in \downarrow xの部分のみが足し合わされる).
定義した$ \bulletが確かに作用になっていることを確認しておこう.
Lemma 9
任意の主順序イデアルが有限集合となるポセット$ Pと体$ Kを考える.
隣接代数$ \mathbb{I}_K(P)の集合$ K^Pへの右作用$ \bullet \colon K^P \times \mathbb{I}_K(P) \to K^Pは, モノイド$ (\mathbb{I}_K(P), *)のモノイド作用である, i.e., 次が成立する: $ f \in K^P, $ \alpha, \beta \in \mathbb{I}_K(P)とすると.
(1) $ (f \bullet \alpha) \bullet \beta = f \bullet (\alpha * \beta).
(2) $ f \bullet \delta = f.
Proof
$ x \in Pを任意に取る.
(1) 定義より,
$ ((f \bullet \alpha) \bullet \beta)(x) = \sum_{y \in \downarrow x} (f \bullet \alpha)(y) \beta (y, x)
$ = \sum_{y \in \downarrow x} \left( \sum_{z \in \downarrow y} f(z) \alpha(z, y) \right) \beta (y, x).
$ = \sum_{z \in \downarrow x} f(z) \left( \sum_{y \in [z, x]} \alpha(z, y) \beta (y, x) \right) ($ z \le y \le xであることに注意する.)
$ = \sum_{z \in \downarrow x} f(z) (\alpha * \beta) (z, x)
$ = (f \bullet (\alpha * \beta))(x).
(2) $ (f \bullet \delta) (x) = \sum_{z \in \downarrow x} f(z) \delta (z, x) = f(x).$ \blacksquare
反転公式
作用の性質を利用して, ポセット上の関数に対する一般化された反転公式を示そう.
Theorem 10 (ポセット上の関数に対する一般化された反転公式)
任意の主順序イデアルが有限集合となるポセット$ Pと体$ Kを考える.
$ f, g \in K^Pと, $ \alpha \in \mathbb{I}_K(P)^{\times}に対して, 次式が成立する:
$ f = g \bullet \alpha \Longleftrightarrow g = f \bullet \alpha^{-1}.
和の形で明示的に表すと, 次式がすべての$ x \in Pに対して成立する:
$ f(x) = \sum_{z \in \downarrow x} g(z) \alpha(z, x) \Longleftrightarrow g(x) = \sum_{z \in \downarrow x} f(z) \alpha^{-1}(z, x).
Proof
Lemma 9より,
$ f = g \bullet \alpha \Longleftrightarrow f \bullet \alpha^{-1} = (g \bullet \alpha) \bullet \alpha^{-1} \Longleftrightarrow f \bullet \alpha^{-1} = g \bullet (\alpha * \alpha^{-1})
$ \Longleftrightarrow f \bullet \alpha^{-1} = g \bullet \delta \Longleftrightarrow f \bullet \alpha^{-1} = g
となり, 成立する.$ \blacksquare
とくに, $ \alpha = \zeta \in \mathbb{I}_K(P)^{\times}とすることで, ポセット上の関数に対するMöbius反転公式が得られる.
Corollary 11 (ポセット上の関数に対するMöbius反転公式)
任意の主順序イデアルが有限集合となるポセット$ Pと体$ Kを考える.
$ f, g \in K^Pに対して, 次式が成立する:
$ f = g \bullet \zeta \Longleftrightarrow g = f \bullet \mu.
和の形で明示的に表すと, 次式がすべての$ x \in Pに対して成立する:
$ f(x) = \sum_{z \in \downarrow x} g(z) \Longleftrightarrow g(x) = \sum_{z \in \downarrow x} f(z) \mu(z, x).
なお, Corollary 11の状況で, $ gに$ \zetaを作用させて$ fを得ることをゼータ変換 (zeta transformation), $ fに$ \muを作用させて$ gを復元することをMöbius反転 (Möbius inversion) などと呼ぶこともある.Möbius反転のことを「Möbius変換」と呼ぶことも多いが, 複素関数論の方のMöbius変換とかぶっているので微妙な用語だと思う. しかし, ゼータ「変換」に対する逆変換なので, Möbius変換のほうがMöbius反転という用語よりも対応が取れているようにも思う. なお, 「逆ゼータ変換」とはあまり言わないらしい (これは信号処理で利用される「逆Z変換」を指すようだ).
双対ポセットと双対形の反転公式
上では, 隣接代数$ \mathbb{I}_K(P)のポセット$ (P, \le)上の関数集合$ K^{P} = \{ f \colon P \to K\}への右作用を考えた. ところで, このポセットに対して, 次で定義される双対ポセットも考えられる:
Definition (双対ポセット)
ポセット$ (P, \le_P)に対し, $ Pと台を同じくし, $ Pの半順序$ \le_Pを反転させることで得られる, i.e., $ p, q \in Pに対して
$ p \le q \stackrel{\mathrm{def}}{\iff} q \le_{P} p
で定義される半順序$ \leをもつポセット$ (P, \le)を$ Pの双対ポセット (dual poset) といい, $ P^*で表す.
上で定義した双対ポセット$ P^*がポセットになっていることは明らかである (半順序の定義にある不等号をすべて反転させればわかる). よって, 双対ポセット$ P^*についても, やはり上で示したポセットに関する諸性質が成立する. 双対ポセット$ P^*は, 元のポセット$ Pの半順序だけが反転しているものだから, 双対ポセット$ P^*に関して成立する性質を元のポセット$ Pの性質に翻訳するには, 現れる半順序$ \leをすべて反転させてやればよい. 以下に, 主要なものだけ双対形を列挙しておく.
TODO 隣接代数の元の対応.
主順序イデアルには双対主順序イデアルが対応する. 主順序イデアルが$ p以下の元をすべて集めた集合であったのに対し, 双対主順序イデアルは$ p以上の元をすべて集めた集合である.
Definition (双対主順序イデアル)
ポセット$ Pと, $ p \in Pに対し, 集合
$ \uparrow p := \{ q \in P \mid p \le q \}
を, $ pによって生成される双対主順序イデアル (principal dual order ideal) という.
そして右作用$ \bulletは, 双対をとると左作用$ \diamondに変わる.
Definition (ポセット上の関数集合への隣接代数の左作用)
任意の双対主順序イデアルが有限集合となるポセット$ Pと体$ Kを考える.
隣接代数$ \mathbb{I}_K(P)の集合$ K^Pへの左作用$ \diamond \colon \mathbb{I}_K(P) \times K^P \to K^Pを以下で定義する:
$ f \in K^Pと$ \alpha \in \mathbb{I}_K(P)に対し,$ (\alpha \diamond f)(x) := \sum_{z \in \uparrow x} \alpha (x, z) f(z) \pod{x \in P}.
TODO 書く.
反転公式の応用例
TODO 書く.
References
J. H. van Lint and R. M. Wilson, 『組合せ論 上・下』, 丸善出版, 2018.
R. P. Stanley, "Enumerative Combinatorics, Volume I", Cambridge University Press, 2012
G. C. Rota, "On the foundations of combinatorial theory I. Theory of Möbius functions." Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2.4, 1964.