隣接代数 (順序理論)

数学の順序集合論において隣接代数^[1]（りんせつだいすう、英: incidence algebra）または接合環^[2]（せつごうかん）とは、任意の局所有限な半順序集合と単位元を持つ可換環に対して定義される結合多元環である。局所有界半順序集合の接続代数は、1964年のジャン・カルロ・ロタ(Gian-Carlo Rota)による論文^[3]に始まり、多くの組合せ論研究者により発展した。

定義

局所有限半順序とは、すべての閉区間

[a, b] = {x : a \leq x \leq b}

が有限集合であるような半順序集合である。

隣接代数の元は、空でない各区間 $[a, b]$ に対して（係数環とする単位的可換環に値を取る）スカラー $f (a, b)$ を対応させる関数である。この台集合上で、元ごとの和とスカラー倍が定義でき、また隣接代数の「積」は以下の畳み込みで定義する^[4]。

(f*g)(a,b)=\sum _{a\leq x\leq b}f(a,x)g(x,b).

隣接代数が有限次元であることと、それを定める半順序集合が有限であることは同値である。

特別な元

デルタ函数

隣接代数は乗法単位元をもち、それは以下で定義されるデルタ函数である。

\delta (a,b)={\begin{cases}1&{\text{if }}a=b\\0&{\textrm {otherwise}}.\end{cases}}

ゼータ函数

隣接代数の「ゼータ関数」とは、すべての空でない区間

[a, b]

に対し、

ζ(a, b) = 1

となるような関数である。

ζ

を掛けることは積分に相当する。

\zeta (a,b)={\begin{cases}{}\qquad 1&{\textrm {if}}\quad a\leq b\\[6pt]{}\qquad 0&{\textrm {otherwise}}.\end{cases}}

メビウス函数

ζ

は隣接代数において（上で定義した畳み込みに対して）可逆であることを示すことができる。（一般に、隣接代数の元

h

が可逆であるための必要十分条件は任意の

x

に対して

h (x, x)

が可逆であることである。）ゼータ関数の乗法逆元は、メビウス関数

μ(a, b)

である。メビウス関数の値は常に、係数環の単位元

1

の整数倍である。

メビウス関数は次のように帰納的に定義することもできる：

\mu (x,y)={\begin{cases}{}\qquad 1&{\textrm {if}}\quad x=y\\[6pt]\displaystyle -\sum _{z\,:\,x\leq z<y}\mu (x,z)&{\textrm {for}}\quad x<y\\[6pt]{}\qquad 0&{\textrm {otherwise}}.\end{cases}}

μ

を掛けることは微分に相当し、それはメビウス反転とも呼ばれる。

例

正整数全体の成す集合 $N$ に整除関係 $⊰$ で順序を入れた半順序集合の接合代数におけるメビウス関数は $a$ が $b$ を割り切る ( $a ⊰ b$ ) ような任意の $(a, b)$ に対して
$μ(a,b) = μ(.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}b⁄a)$
で与えられる。ただし右辺の $μ$ は、19世紀に数論に導入された古典的なメビウス関数である。メビウス反転はメビウスの反転公式として与えられる。
適当な集合 $E$ の有限部分集合全体の成す集合 $P fin (E)$ （これは幾何学的には超立方体 $2 E$ ）に包含関係 $\subseteq$ で順序を入れた半順序集合の接合代数におけるメビウス関数は $S \subseteq T$ なる $E$ の有限部分集合の任意の対に対して
$μ(S, T) = (-1) | T ∖ S |$
で与えられる。このときのメビウス反転は包含と切除の原理と呼ばれるものである^[5]。
自然数全体の成す集合 N に通常の大小関係 $\leq$ で順序を入れた半順序集合（これは幾何学的には離散数直線）の接合代数において、メビウス関数は
$\mu (x,y)={\begin{cases}1&{\text{if }}y-x=0,\\-1&{\text{if }}y-x=1,\\0&{\text{if }}y-x>1\end{cases}}$
で与えられる。このメビウス関数に関する反転は後退差分作用素と呼ばれる。
- 「数列の畳み込み」が「形式的冪級数の積」に対応するものであったことに注意しよう。するとこのメビウス関数は形式的冪級数 $1 - z$ の係数列 $(1, -1, 0, 0, 0, \dots)$ に対応し、ゼータ関数が逆数函数 $(1 - z) -1$ の級数展開の係数列 $(1, 1, 1, 1, \dots)$ に対応する。同様に、この隣接代数におけるデルタ関数は形式的冪級数としての $1$ に対応する。
上の3つの例は適当な多重集合 $E$ の有限部分多重集合全体に包含関係で順序を入れた半順序集合の場合に統合的に一般化できる。メビウス関数は多重集合 E の有限部分多重集合 S, T が S ⊆ T なるとき
$S ∖ T$ が集合でない真の多重集合（重複元を持つ）ならば $μ(S, T) = 0$ ,
$S ∖ T$ が集合（重複元を持たない）ならば $μ(S, T) = (-1) | T ∖ S |$
として与えられる。
- 最初の正整数と整除性の例は、この一般化された設定において整数をその重複度を込めて考えた素因数全体の成す多重集合と見做すことで与えられる。例えば整数 $12 = 2 2 ・3$ は多重集合 ${2,2,3$ } である。
- 三つ目の自然数と大小関係の例は、与えられた自然数に対し「属する元が $1$ でその重複度が与えられた自然数に等しい」ような多重集合を考えることで与えられる。例えば $3 = 1+1+1$ は多重集合 ${1,1,1$ } である。
- 二つ目の例は（真の多重集合の場合は現れないから）明らか。
有限 $p$ -群 $G$ の部分群全体の成す集合に包含関係で順序を入れた半順序集合のメビウス函数は $K$ が $H$ の正規部分群で $H / K ≅ (Z / p Z) k$ なるとき
$\mu _{G}(K,H)=(-1)^{k}p^{\binom {k}{2}},$
それ以外のとき $0$
となる。これはWeisner^[6]による定理である。
適当な有限集合の分割全体の成す集合に、 $σ \leq τ$ は $σ$ が $τ$ の細分となるときと定めた半順序集合の接合代数のメビウス函数は、 $σ$ の成分数 $n$ , $τ$ の成分数 $r$ , $σ \leq τ$ として、また $σ$ の成分をちょうど $i$ 個含むような $τ$ の成分の総数を $r i$ として
$\mu (\sigma ,\tau )=(-1)^{n-r}(2!)^{r_{3}}(3!)^{r_{4}}\cdots ((n-1)!)^{r_{n}}$
で与えられる。

オイラー標数

→詳細は「オイラー標数」を参照

半順序集合が有界とは、それが最大元 $1$ と最小元 $0$ を持つときに言う（いま $0, 1$ は単に記号としてそう書くのであって係数環の $0, 1$ と混同してはならない）。有界有限半順序集合のオイラー標数とは、メビウス函数の値 $μ(0,1)$ のことを言う。このように言う理由は、 $P$ が最大元 $1$ と最小元 $0$ を持つとき、 $P ∖ {0, 1$ } に面を持つ単体的複体の被約オイラー標数が $μ(0,1)$ に一致するからである。

被約接合代数

ふたつの区間が半順序集合として同型となるならば必ず同じ値が割り当てられるような接合代数の任意の元は被約接合代数 (reduced incidence algebra) の元である。被約接合代数は接合代数の部分代数であって、明らかにもとの接合代数の単位元とゼータ函数を含む。被約接合代数の任意の元は、それが適当な接合代数の拡大において可逆ならば被約接合代数自身の中に逆元を持つ。従ってメビウス函数は常に被約接合代数の元として取れる。先に自然数と通常の大小関係の例で触れたように、被約接合代数は母函数の理論に光を当てるものである^[7]。

出典

^ 日比 (1997), p. 34
^ スタンレイ (1990), p. 133
^ Rota 1964
^ Doubilet et al. (1972), p. 271
^ スタンレイ (1990), p. 139
^ Weisner (1935a),Weisner (1935b)
^ Peter Doubilet, Gian-Carlo Rota and Richard Stanley: On the Foundations of Combinatorics (IV): The Idea of Generating Function, Berkeley Symp. on Math. Statist. and Prob. Proc. Sixth Berkeley Symp. on Math. Statist. and Prob., Vol. 2 (Univ. of Calif. Press, 1972), 267-318, available online in open access

参考文献

Rota, Gian-Carlo (1964), “On the Foundations of Combinatorial Theory I: Theory of Möbius Functions” (PDF), Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2 (4): 340–368, doi:10.1007/BF00531932 2015年2月17日閲覧。

Peter Doubilet, Gian-Carlo Rota, and Richard Stanley (1972). “On the Foundations of Combinatorics (IV): The Idea of Generating Function” (PDF). Berkeley Symp. on Math. Statist. and Prob. Proc. Sixth Berkeley Symp. on Math. Statist. and Prob. (Univ. of Calif. Press) 2: 267-318.
日比孝之著『数え上げ数学』 14巻、朝倉書店〈すうがくぶっくす〉、1997年。ISBN 978-4-254-11474-4。
リチャード・P. スタンレイ『数え上げ組合せ論〈1〉』日本評論社、1990年。ISBN 4535781729。

Louis Weisner (1935), “Abstract theory of inversion of finite series” (PDF), Transactions of the American Mathematical Society (American Mathematical Society) 38 (3): 474-484, doi:10.1090/S0002-9947-1935-1501822-0 2015年2月20日閲覧。
Louis Weisner (1935), “Some properties of prime-power groups” (PDF), Transactions of the American Mathematical Society (American Mathematical Society) 38 (3): 485-492, doi:10.1090/S0002-9947-1935-1501823-2 2015年2月20日閲覧。

Spiegel, Eugene; O'Donnell, Christopher J. (1997), Incidence algebras, Pure and Applied Mathematics, 206, Marcel Dekker, ISBN 0-8247-0036-8

[日比1997p34-1] 日比 (1997), p. 34

[スタンレイ1990p133-2] スタンレイ (1990), p. 133

[Rota1964-3] Rota 1964

[Doubilet_etal1972p271-4] Doubilet et al. (1972), p. 271

[スタンレイ1990p139-5] スタンレイ (1990), p. 139

[6] Weisner (1935a),Weisner (1935b)

[7] Peter Doubilet, Gian-Carlo Rota and Richard Stanley: On the Foundations of Combinatorics (IV): The Idea of Generating Function, Berkeley Symp. on Math. Statist. and Prob. Proc. Sixth Berkeley Symp. on Math. Statist. and Prob., Vol. 2 (Univ. of Calif. Press, 1972), 267-318, available online in open access

[1]

[2]

[3]

[4]

[5]

[6]

[7]

隣接代数 (順序理論)

目次

定義

関連する概念

特別な元

例

オイラー標数

被約接合代数

関連項目

出典

参考文献