テトリス代数とupho半順序集合2 〜色付けとupho束〜
前回の記事( upho半順序集合とテトリス代数 )に引き続き，以下の対応関係にある代数的組合せ論の概念を扱います．前回の記事を読んでいなくても読めると思います．
| しーた らの呼称 (2024) | Fu-Peng-Zhang らの呼称 (2024) |
|---|---|
| フラクタル順序集合 | upho半順序集合 |
| フラクタル束 | upho束 |
| テトリス代数 | LCIFモノイド |
今回は，次のようなトピックについて紹介します．
- upho半順序集合とLCIFモノイドの対応の深堀り:
- 前回紹介しなかった具体例
- モノイドを与えることが「色付け」という操作に等しいこと
- upho束のcoreとよばれる有限束の性質:
- 「ランクごとの元の個数」はcoreのみで決まる．
- 有限束$L$に対して，それをcoreとするようなLCIFモノイドの個数は有限個
- 未解決問題「任意のupho束はLCIFモノイドから得られるか」の重要性
ところどころに演習問題を散りばめました．
upho半順序集合
upho半順序集合とLCIFモノイドの定義
まずはupho半順序集合とLCIFモノイドの概念を復習しておきます．
空でない半順序集合$\mathcal{P}$がupho半順序集合，あるいはフラクタル順序集合であるとは，任意の$a \in \mathcal{P}$に対して，
$$
\mathcal{P}_{\geq a} := \{ x \in \mathcal{P} \mid x \geq a \}
$$
が$\mathcal{P}$と順序同型であることをいう．
今回は，次のような有限性の仮定を置いたもののみ考えます．
$\mathcal{P}$がfinitaryであるとは，任意の$a \in \mathcal{P}$に対してそのheight
$$
\mathrm{ht}(a) := \sup\{ n \in \mathbb{N} \mid x_0 < x_1 < \cdots < x_n = a \}
$$
が有限であることをいう
モノイド$(M,*,e)$がLCIFモノイド，あるいはテトリス代数であるとは，次の条件を満たすことをいう．
- 左簡約律
$$ x * y = x*z \Longrightarrow y = z \quad (\forall x,y,z \in M) $$ - 可逆元が単位元のみ
$$ x*y = e \Longrightarrow x = y = e \quad (\forall x,y \in M) $$
$M$がLCIFモノイドのとき，$M$上の順序を
$$
x \leq y \Longleftrightarrow \exists z \in M, x*z = y
$$
と定めると，$M$はupho半順序集合になる．
代表的なLCIFモノイドとupho半順序集合の対応を書いておきます．
| 生成元 (モノイド) | 関係式 (モノイド) | 集合 (半順序) | 順序 (半順序) |
|---|---|---|---|
| $s_1,s_2 \cdots, s_k$ | $s_i s_j = s_j s_i$ | $\mathbb{N}^k$ | 積順序 |
| $s_1,s_2,\cdots,s_k$ | $s_i s_{j-1} = s_j s_i$ | $\{ \text{finite}\ S \subset \{1,2,\cdots\} \mid \max(S) \leq \# S + k \}$ | 包含順序 |
| $a_1,a_2,\cdots,a_k$ | なし($\emptyset$) | 無限$k$分木$T_k$ | 自然な順序 |
| $a,b,c$ | $ac = ba, bc=ca$ | Stern poset | 自然な順序 |
| 有限群$G$の生成集合$S$ | $G$上の長さの等しい関係式 | Cayleyグラフ上のwalk全体 | 自然な順序 |
| $a,b$ | $aba = bab$ | Braidモノイド | 左整除関係 |
| $a,b,c$ | $ab = bc = ca$ | 双対Braidモノイド | 左整除関係 |
Stern poset
LCIFモノイドの例を1つ与え，対応するupho半順序のHasse図を描け
色付け
finitaryなupho半順序集合を与えたとき，それにLCIFモノイドの構造(積付け)を入れることは，「Hasse図の辺に色を塗る」という操作に言い換えることができます．そこでまずは，色付けを定義しましょう．
$\mathcal{P}$を最小元$\widehat{0}$をもつfinitaryなupho半順序集合とします．
$$
x \lessdot y \iff x < y \text{ かつ } x < z < y \text{ なる } z \text{ が存在しない}
$$
とし，$\mathcal{P}$の部分集合を
$$
A_{\mathcal{P}} := \{ x \in \mathcal{P} \mid \widehat{0} \lessdot x \}
$$
とします．$A_{\mathcal{P}}$の元をatomといいます．もし$\mathcal{P}$が積付け$*$をもてば，atom全体がそのモノイドの生成元となります．また，
$$
E_\mathcal{P} := \{ (x,y) \mid x \lessdot y \}
$$
とします．有向グラフ$(\mathcal{P}, E_\mathcal{P})$のことをHasse図といいます．$(x,y) \in E_\mathcal{P}$のことをしばしば$(x \lessdot y) \in E_\mathcal{P}$と書きます．
finitaryなupho半順序$\mathcal{P}$の色付けとは，写像
$$
\mathrm{col} : E_\mathcal{P} \to A_\mathcal{P}
$$
で，次を満たすもののことをいう．
- アトム$a \in A_\mathcal{P}$に対して，$\mathrm{col}(\widehat{0} \lessdot a) = a$
- 任意の$x \in \mathcal{P}$に対して，$\mathcal{P}_{\geq x}$が$\mathcal{P}$と色を込めて同型になる．すなわち，順序同型$\phi_x : \mathcal{P} \to \mathcal{P}_{\geq x}$が存在し，
$$ \mathrm{col}(y \lessdot z) = \mathrm{col}(\phi_x(y) \lessdot \phi_x(z)) \quad (\forall (y \lessdot z) \in E_{\mathcal{P}}) $$
なお，色を保つ順序同型$\phi_x : \mathcal{P} \to \mathcal{P}_{\geq x}$は，存在すれば一意であることが証明できます．
upho半順序$\mathcal{P}$はfinitaryであると仮定する．次の間に1対1対応がある．
(1) $\mathcal{P}$上のLCIFモノイドの構造
(2) $\mathcal{P}$の色付け
$\mathcal{P}$にLCIFモノイドの構造$*$が与えられたとき，$a \in A_\mathcal{P}$に対して，$x * a = y$のとき，$\mathrm{col}(x \lessdot y) = a$と定めることで，(1)から(2)への対応が得られる．また，色付け$\mathrm{col}$が与えられたとき，$\phi_x : \mathcal{P} \to\mathcal{P}_{\geq x}$を色を保つ同型とし，
$$
x * y := \phi_x(y)
$$
と定めることで，(2)から(1)への対応が得られる．
upho半順序の色付け
upho半順序の例を1つ与え，その色付けを与えよ．対応するモノイドがどうなるか調べよ．
upho半順序$\mathcal{P}$が非自明な自己同型をもたないとき，一意的な色付けが可能であることを示せ．
階数母関数
以下では，次のようなクラスを考えます．
$\mathcal{P}$を最小元$\widehat{0}$をもつ半順序集合とする．
$\mathcal{P}$がfinite-type $\mathbb{N}$-gradedであるとは，$\mathcal{P}$がfinitaryであり，rank関数$\rho : \mathcal{P} \to \mathbb{N}$が定義され
$$
a \lessdot b \Longrightarrow \rho(b) = \rho(a) + 1, \quad \rho(\widehat{0}) = 0
$$
が成り立ち，任意の$n \in \mathbb{N}$に対して
$$
\mathcal{P}_n := \{ x \in \mathcal{P} \mid \rho(x) = n \}
$$
が有限集合であることをいう．
$\mathcal{P}$がfinite-type $\mathbb{N}$-gradedな半順序集合のとき，
$$
F(\mathcal{P}, q) := \sum_{n=0}^{\infty} |\mathcal{P}_n| q^n = \sum_{x \in \mathcal{P}} q^{\rho(x)}
$$
と定義する．
- 積順序を入れた$\mathbb{N}^k$の階数母関数は
$$ F(\mathbb{N}^k, q) = \sum_{x = (x_1,x_2,\cdots,x_k) \in \mathbb{N}^k} q^{x_1 + x_2 + \cdots + x_k} = \prod_{i=1}^k\sum_{x_i \in \mathbb{N}} q^{x_i} = \frac{1}{(1-q)^k} $$ - 無限$k$分木$T_k$の階数母関数は
$$ F(T_k, q) = \sum_{n=0}^{\infty} k^n q^n = \frac{1}{1-kq} $$ - Stern posetの階数母関数は
$$ F(\text{Stern}, q) = \sum_{n=0}^{\infty} (2^{n+1} - 1) q^n = \frac{1}{(1-q)(1-2q)} $$
階数母関数については，次のような事実が知られています．証明は省略します．
upho半順序集合の階数母関数として現れる冪級数は非可算個あり，したがって計算不可能なものも存在する
ハッセ図が平面に描けるupho半順序集合の階数母関数は有理関数
upho束の階数母関数は分子が$1$の有理関数で，coreと呼ばれる有限束によって完全に決まる(後述)
upho束
upho束とそのcore
半順序集合$\mathcal{L}$が束(lattice)であるとは，任意の$a,b \in \mathcal{L}$に対して，次で定義されるmeet $a \wedge b$とjoin $a \vee b$が存在することをいう．
\begin{align}
a \vee b &:= \sup\{a, b\} = \min\{ x \in \mathcal{L} \mid x \geq a, x \geq b \} \\
a \wedge b &:= \inf\{a, b\} = \max\{ x \in \mathcal{L} \mid x \leq a, x \leq b \}
\end{align}
特に束であるようなupho半順序集合をupho束と呼ぶ．
以下，upho束といえば finite-type $\mathbb{N}$-gradedであると仮定する．
joinとmeetが存在すると言いましたが，今回の設定(finitary)ではmeetの存在は不要です．次は簡単な束論の演習問題です．
finitaryな半順序集合において，任意の二元にjoinが存在すれば，meetも存在する．
特に，(有限生成な)LCIFモノイド$M$が束であるための条件は，$M$の任意の2元が「右最小公倍元」をもつことです．
このようなモノイドを
しーた
らはかつて「和付きテトリス代数」と読んでいました(
テトリス代数の覚書
)
upho束$\mathcal{L}$に対して，そのatomを$\{a_1, \dots, a_n\}$とし，
\begin{align}
\widehat{0} := \min \mathcal{L}, \quad \widehat{1} := a_1 \vee a_2 \vee \dots \vee a_n
\end{align}
とする．$\mathcal{L}$のcoreとは，
\begin{align}
L := [\widehat{0}, \widehat{1}] = \{ x \in \mathcal{L} \mid \widehat{0} \leq x \leq \widehat{1} \}
\end{align}
によって定義される有限束である．
coreのイメージ
有限束coreは，upho束$\mathcal{L}$全体の情報をかなり統制しています．
upho束の階数母関数
驚くべきことに，upho束の階数母関数は，そのcoreという有限束の情報から完全に決定されることがわかります．
$\mathcal{L}$をupho束とし，$L$をそのcoreとする．$\mu : \{(x,y) \in \mathcal{L}^2 \mid x \leq y\} \to \mathbb{Z}$をMöbius関数とする．すなわち，
$$
\mu(x,x) = 1, \quad \mu(x,y) = -\sum_{x \leq z < y} \mu(x,z)
$$
また，多項式$\chi(L, q) \in \mathbb{Z}[q]$を
\begin{align}
\chi(L, q) := \sum_{x \in L} \mu(\widehat{0}, x) q^{\rho(x)}
\end{align}
とすると，次の関係が成り立つ．
\begin{align}
F(\mathcal{L}, q) = \frac{1}{\chi(L, q)}
\end{align}
証明は省略します．
upho束の個数の有限性
coreを$L$とするupho束は，階数母関数は決まるものの，その構造が完全に決まるわけではありません．例えば，次の2つのupho束はどちらもcoreとして4要素のブール束 $M_2$ を持ちますが，大域的な構造は異なります．また，どちらも同じ階数母関数である$1/ (1-q)^2$を持ちます．
- $\mathbb{N}^2$ (積順序)
- $L_2 := \{ \text{finite } S \subseteq \{1, 2, \dots\} \mid \max(S) \leq \#S + 1 \}$ (包含順序)
![!FORMULA[113][35633544][0]をcoreとする2つのupho束](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2F1aUBkPxUceA5Vwv9APCz.png?alt=media)
$M_2$をcoreとする2つのupho束
しかしながら，次の予想があります．2026年7月現在，未解決です．
有限束$L$に対し，$L$をcoreとするupho束の同型を除いた個数$\kappa(L)$は有限である．
この予想については次のような進展があります．
$L$を有限束とする．
(1) $L$をcoreとする色付きupho束(=LCIFモノイド)の個数は有限である．(後述)
(2) $L$が非自明な自己同型を持たない場合，$L$をcoreとするupho束は色付け可能であり，したがって$\kappa(L) < \infty$
(3) ブール束$M_2$をcoreとするupho束は上で挙げた2つのみである．
一方で，これ以外の場合にはほとんど分かっておらず，次のような単純な束$M_3$に対しても，$\kappa(M_3)$が有限かどうかは分かっていません．
![束!FORMULA[125][35633575][0]](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2F0WtAVXU4tS3VZzfibhWE.png?alt=media)
束$M_3$
さて，上記の定理の(1)について説明しましょう．実は色付きupho束に対応するモノイドの関係式は，そのcoreの色付けによって完全に決定されることがわかります．
$(\mathcal{L}, \mathrm{col})$を色付きupho束とし，$\mathcal{L}$のcoreを$L$とする．$(\mathcal{L}, \mathrm{col})$に対応するモノイド$M$は次のように与えられる．
\begin{align}
M = \langle s_1, s_2, \cdots, s_r \mid \mathrm{col}(\widehat{0} = x_0 \lessdot x_1) \mathrm{col}(x_1 \lessdot x_2) \cdots \mathrm{col}(x_{k-1} \lessdot x_k = x_1 \vee y_1) \\
= \mathrm{col}(\widehat{0} = y_0 \lessdot y_1) \mathrm{col}(y_1 \lessdot y_2) \cdots \mathrm{col}(y_{k-1} \lessdot y_k = x_1 \vee y_1) \rangle
\end{align}
ここで，$s_1, s_2, \dots, s_r$はcoreのatomである．関係式については，すべてのatomの組$(x_1,y_1)$と，
\begin{align}
\widehat{0} &= x_0 \lessdot x_1 \lessdot x_2 \lessdot \cdots \lessdot x_k = x_1 \vee y_1, \\
\widehat{0} &= y_0 \lessdot y_1 \lessdot y_2 \lessdot \cdots \lessdot y_k = x_1 \vee y_1
\end{align}
という形のすべてのmaximal chainに対して，対応する関係式を課している．
関係式
$M$はアトムで生成される．任意の$x \in \mathcal{L}$に対し，maximal chain
\begin{align}
\widehat{0} = z_0 \lessdot z_1 \lessdot \cdots \lessdot z_n = x
\end{align}
を取れば，
\begin{align}
x =
\mathrm{col}(z_0 \lessdot z_1)
\mathrm{col}(z_1 \lessdot z_2)
\cdots
\mathrm{col}(z_{n-1} \lessdot z_n) =: \mathrm{word}(z_0 \lessdot z_1 \lessdot \cdots \lessdot z_n)
\end{align}
したがって，$M$の関係式はすべて，同じ元に至る2つのmaximal chainの色の語の等式から得られる．定理に書かれた関係式は，$z$がアトム$x_1,y_1$を用いて$z = x_1 \vee y_1$と表される場合に対応する．よって示すべきことは，同じ元$z \in \mathcal{L}$に至る2つのmaximal chainの色の語が，定理に書かれた関係式のみから従うことである．
\begin{align}
C &: \widehat{0} = x_0 \lessdot x_1 \lessdot \cdots \lessdot x_n = z, \\
D &: \widehat{0} = y_0 \lessdot y_1 \lessdot \cdots \lessdot y_n = z
\end{align}
を同じ元$z$に至る2つのmaximal chainとする．$z$のrankに関する帰納法で，$\mathrm{word}(C)=\mathrm{word}(D)$が定理中の関係式から従うことを示す．$x_1 = y_1$なら，$\phi_{x_1}^{-1} : \mathcal{L}_{\geq x_1} \to \mathcal{L}$により，$x_1$より上の部分に帰納法を適用すればよい．$x_1 \neq y_1$とする．このときlattice性より$q := x_1 \vee y_1$が存在し，$q \leq z$である．
$x_1$を通って$q$に至るmaximal chainと，$y_1$を通って$q$に至るmaximal chainを
\begin{align}
E_x &: \widehat{0} \lessdot x_1 \lessdot \cdots \lessdot q, \\
E_y &: \widehat{0} \lessdot y_1 \lessdot \cdots \lessdot q
\end{align}
とし，さらに$q$から$z$へのmaximal chainを$T$とする．定理中の関係式より
\begin{align}
\mathrm{word}(E_x) = \mathrm{word}(E_y)
\end{align}
であるから，
\begin{align}
\mathrm{word}(E_x)\mathrm{word}(T) = \mathrm{word}(E_y)\mathrm{word}(T)
\end{align}
である．一方，$C$と$E_xT$はどちらも$x_1$を通って$z$に至るmaximal chainなので，
$x_1=y_1$の場合より
\begin{align}
\mathrm{word}(C) = \mathrm{word}(E_x)\mathrm{word}(T)
\end{align}
である．同様に
\begin{align}
\mathrm{word}(D) = \mathrm{word}(E_y)\mathrm{word}(T)
\end{align}
である．したがって
\begin{align}
\mathrm{word}(C) = \mathrm{word}(D)
\end{align}
が従う．よって，同じ元に至る任意の2つのmaximal chainの色の語の等式は，$x_1 \vee y_1$までの関係式から生成される．したがって，$M$は定理に書かれた表示をもつ．
core $L$は有限束であり，coreの辺に色を塗る方法も有限個しかないので，当然対応するモノイドも有限個であり，次の系が得られます．
$L$をcoreとする色付きupho束の個数は有限である．
未解決問題
最後に，2026年7月現在，upho束に関する最大の未解決問題と呼べるであろうものを紹介しておきます．
任意のfinite-type $\mathbb{N}$-gradedなupho束は色付け可能，すなわちLCIFモノイドから得られるか
もしこの予想が正しければ，上記の系から直ちに，すべての有限束$L$に対して$\kappa(L) < \infty$であることが導けます．これはupho束という無限の自己相似構造の分類問題が，すべて色付きcoreという有限の組み合わせ問題に帰着することを意味し，非常に強力な結果を含んでいます．ここまで読んでくれた読者の方にもぜひ取り組んでほしいです．
upho束が色付け可能であることの証明に使えそうなアイディアを考えよ．あるいは，反例になりそうなupho束の例を考えよ．
