ゲーム・アルゴリズム・表現論
川中 宣明 (大阪大学・情報科学研究科)
抽象アルゴリズム
1
理論計算機科学で基本的な非決定性(non-deterministic )アルゴリズムの
概念を次のように抽象化し, 以下これを単に「アルゴリズム」ということに
する.
定義1 P を集合, 2P を P の部分集合全体の集合とする. P と写像 φ : P −→
2P との対 (P, φ) をアルゴリズムという.
P の元はアルゴリズムの途中の状態を表す. 状態 p ∈ P から次に移り得る
状態全体の集合が φ(p) である. φ(p) = ∅ のとき p は終状態であるという.
ある状態 p0 から出発して p1 ∈ φ(p0 ), p2 ∈ φ(p1 ), . . . と次々に状態を選んで
進んで行き, 終状態に到達したとき, この(非決定性)アルゴリズムは終了す
る. どのような p ∈ P から出発し, どのような経路をたどっても, 必ず有限ス
テップで終状態に到達するような (P, φ) を有限アルゴリズムといい, 任意の
p ∈ P に対し、次に選択できる状態の集合 φ(p) が有限であるような (P, φ) を
有限選択的アルゴリズムという. 選択肢が一般には複数あって「どちらを選
ぶか分からない」ので「非決定性」アルゴリズムという.
(P, φ), (Q, ψ) を2つのアルゴリズムとする. 1対1かつ上への写像 f : P −→
Q が f (φ(p)) = ψ(f (p)) (p ∈ P ) を満たすとき f はアルゴリズムの同型写像
であるといい (P, φ) ∼
= (Q, ψ) とかく.
Q ⊂ P のとき, φQ (q) = φ(q) ∩ Q (q ∈ Q) とおくと (Q, φQ ) はアルゴリズム
になる. これを (P, φ) の部分アルゴリズムといい, とくに φ(q) ⊂ Q (q ∈ Q)
が成り立つとき, 充満部分アルゴリズムという. p ∈ P を含むような充満部分
アルゴリズムのうち最小のものを ⟨p⟩ で表し(p で生成された)単項アルゴリ
ズムという. 状態 p から出発して有限ステップ後に到達し得る状態の全体が
(集合としての)⟨p⟩ である. 単項アルゴリズムは出発点 p を指定したアルゴ
リズムと考えてよい. 一般のアルゴリズムは単項アルゴリズムを「貼りあわ
せて」得られる.
2つのアルゴリズム (P, φ) と (Q, ψ) の和 (P + Q, φ + ψ) とは, 次で定義され
るアルゴリズムのことである.
P + Q = {(p, q) | p ∈ P, q ∈ Q},
(φ + ψ)(p, q) = {(p′ , q) | p′ ∈ φ(p)} ∪ {(p, q ′ ) | q ′ ∈ ψ(q)}, p ∈ P, q ∈ Q.
2つの仕事 P と Q を並列させておいて, 気の向くままにあるときは P をあ
るときは Q を1ステップ進めるアルゴリズムが P + Q である.
注意1 有限アルゴリズム (P, φ) は非決定性アルゴリズムのモデルと解釈で
きるが, これとは別の重要な解釈がある. まず、非決定性アルゴリズムと1
人ゲームは抽象的には同じものと考えられる. また, 状態 p0 ∈ P から始め
て2人のプレイヤーが交互に p1 ∈ φ(p0 ), p2 ∈ φ(p1 ), . . . と状態を選択して
いくとし, 終状態を選んだプレイヤーを勝利者と認定すれば (P, φ) を(ある
種の)2人ゲームのモデルとみなすことができる.(このとき写像 φ はゲー
ムのルールを規定している. )一方, アルゴリズムとしての解釈のもとで, 各
φ(p) (p ∈ P ) に確率測度を与えておき, その確率に従って次の状態に移ると
考えると, 確率アルゴリズム(或いは、確率的1人ゲーム)のモデルが得られ
る. 一般の(有限でない)アルゴリズムは非決定性 (或いは、確率的)力学系
のモデルと考えることができる.
例1 P = {p, q} (p ̸= q), φ(p) = {q}, φ(q) = ∅ のとき (P, φ) を1次元立
方体という. n 個の1次元立方体の和を n 次元立方体という. (とくに2次
元立方体のことを正方形という. )言い換えれば [n] = {1, 2, . . . , n} とし
Cn = {cX | X ⊂ [n]} を 2n 個の元からなる集合とするとき φn : Cn −→ 2Cn
を φn (cX ) = {cY | Y ⊂ X, |X \ Y | = 1} で定義して得られる (Cn , φn )(と
同型なアルゴリズム)が n 次元立方体である. c[n] , c∅ をそれぞれ Cn の始点,
終点という. また { cX | |X| = n − 1} を Cn の基底という. n 次元立方体は
有限で有限選択的なアルゴリズムである.
例2 S を半順序集合とし P = 2S とする. T ∈ P (つまり T ⊂ S) に対して
φ(T ) = {(T \ {t}) ∪ {t′ } | t ∈ T, t′ ̸∈ T, t′ < t} とおく. アルゴリズム (P, φ)
は一般には有限でなく有限選択的でもないが, 例えば S = N = 非負整数全体
とし T をその有限部分集合とすると ⟨T ⟩ は有限かつ有限選択的なアルゴリズ
ムになる. また, ある超限順序数 θ に対し S を θ 以下の順序数全体, T をそ
の有限部分集合とすると ⟨T ⟩ は有限だが有限選択的ではないアルゴリズムに
なる.
2
平明アルゴリズムの公理系
以下の5つの公理 (P1)-(P5) を満たすアルゴリズム (P, φ) を平明 (plain) ア
ルゴリズムという.
(P1) (P, φ) はサイクルを含まない. すなわち
p ̸∈ φn (p) ( p ∈ P, n = 1, 2, 3, . . .). ただし
φ0 (p) = {p},
φn (p) = { r ∈ φ(q) | q ∈ φn−1 (p) } (n = 1, 2, 3, . . .).
(P2) p ∈ P, q1 , . . . , qn ∈ φ(p) で qi ̸= qj (i ̸= j), qi ̸∈ φ(qj ) (1 ≤ i, j ≤ n) と
する. このとき p を始点とし, {q1 , . . . , qn } を基底とする n 次元立方体が P の
部分アルゴリズムとして唯一つ存在する.
(P3) p, q, s ∈ P, q ∈ φ(p), s ∈ φ(q), s ̸∈ φ(p) とする. このとき {p, q, r, s} が
正方形であるような r ∈ P が唯一つ存在する.
(P4) p, q, r1 , r2 , s1 , s2 ∈ P について {p, q, r1 , s1 }, {p, q, r2 , s2 } が共に正方形
で q ∈ φ(p), s1 ∈ φ(r1 ), s2 ∈ φ(r2 ) であるとする. もし r1 ∈ φ(r2 ), r2 ∈
φ(r1 ), s1 ∈ φ(s2 ), s2 ∈ φ(s1 ) の4条件のうちのどれかが成り立っているなら
{r1 , r2 , s1 , s2 } は正方形である.
(P5) q, r, s ∈ P とし s ∈ φ(q) ∩ φ(r) とする. このとき {p, q, r, s} が正方形で
あるような p ∈ P は(存在するなら)唯一つである.
感覚的にいえば, 平明アルゴリズムとは多くの正方形 (←「可喚な部分」を
意味する)を含み, それらが互いに調和しているようなアルゴリズムである.
例3 第1節の例1の n 次元立方体は平明アルゴリズムである.
例4 第1節の例2において S を全順序集合とすると (S, φ) は平明アルゴリ
ズムである.
平明アルゴリズムの基本的な性質を幾つか述べる.
命題1 平明アルゴリズムの充満部分アルゴリズムは平明である.
命題2 2つの平明アルゴリズムの和は平明アルゴリズムである.
平明アルゴリズムの部分集合 A が連結とは, A の任意の2点 a, b (a ̸= b)
に対し, A の元の列 a = a0 , a1 , . . . , an = b で, 任意の 1 ≤ i ≤ n に対し
ai−1 ∈ φ(ai ) または ai ∈ φ(ai−1 ) が成り立つようなものがとれることである.
命題3 平明アルゴリズムの1つの連結成分に含まれる終状態は(存在すれば)
唯一つである. とくに, 単項平明アルゴリズムの終状態は一意的である.
命題4 平明アルゴリズムにおいては有限選択的なら必ず有限である.
3
平明アルゴリズムの基本定理,
ダイアグラムとフックの概念
次の定理を平明アルゴリズムの基本定理という.
定理1 (P = ⟨p⟩, φ) を単項平明アルゴリズムとする. 次が成り立つ.
(i) 部分アルゴリズム Y = φ(p) (⊂ P ) は平明である.
(ii) (P, φ) の同型類は Y の同型類によって一意的に定まる.
定義2 定理1の Y を単項平明アルゴリズム P のダイアグラムという. ある
単項平明アルゴリズムのダイアグラムに同型であるようなアルゴリズム(←
定理1により平明)を単にダイアグラムという. ダイアグラム Y の元 x に対
し, 集合 H(x) = {x} ∪ {a ∈ Y | x ∈ φ(a)} を x のフックという.
注意2 集合としての Y にフック構造 {H(x) | x ∈ Y } を付け加えたものとア
ルゴリズムとしての(すなわちダイアグラムとしての)Y は同値である.
例5 第1節の例2(および第2節の例4)において S = N とし T をその有
限部分集合とする. このとき ⟨T ⟩ のダイアグラムはヤング図形(文末の図参
照)になり, 定義2のフックはヤング図形におけるフック概念に一致する. さ
らに T ′ ∈ φ(T ) とするとき ⟨T ′ ⟩ のダイアグラム Y ′ は Y からあるフックを
「抜いて」得られるヤング図形に一致する. ただしヤング図形 Y はその「箱」
の集合と考え, Y のアルゴリズム構造 φ は
φ(x) = { 箱 x と同じ列で上, または同じ行で左に位置する箱 }
によって定義するものとする. 第1節の例2(および第2節の例4)におい
て S を非負実数の全体 R≥0 とし T をその部分集合としたとき ⟨T ⟩ のダイア
グラムはヤング図形の連続ヴァージョンになる. 第1節の例2のように超限
順序数を使えばヤング図形の超限ヴァージョンも得られる.
例6 Y を任意の x ∈ Y に対し Y (> x) = {y ∈ Y | y > x} が全順序集合であ
るような半順序集合とする. このとき x ∈ Y に対し φ(x) = Y (> x) とすれば
(Y, φ) はダイアグラムである.
4
有限選択的な単項平明アルゴリズムの分類
第3節の基本定理により, 単項平明アルゴリズムの分類はダイアグラムの
分類に帰着される. ダイアグラムは非常に特別な平明アルゴリズムなので, こ
れにより分類問題は本質的に簡易化される. さて, ダイアグラムの中で基礎と
なるのは単項ダイアグラム (=単項アルゴリズムであるようなダイアグラム)
である. 再び, 基本定理により, 単項ダイアグラムの分類は基礎ダイアグラム
(=単項ダイアグラムのダイアグラム)の分類に帰着する. 基礎ダイアグラム
はダイアグラムの中でも, かなり特別のものなので, 分類問題はさらに簡易化
される. このプロセスは何回でも繰り返せるが, 元々の単項平明アルゴリズム
が有限選択的であるという仮定の下では何回か繰り返すと必ず (∅, ∅)(=空な
アルゴリズム)に到達してしまう. これを逆転させ, 下の命題5に注意すると
空なアルゴリズムから出発して全ての有限選択的な単項平明アルゴリズムを
構成・分類することができる. (分類結果については第7節の定理4を参照.)
例7 第3節の例5のように, ヤング図形 Y をダイアグラムと考える. Y が単
項ダイアグラムであることと長方形タイプであることとは同値である. m × n
型の長方形ヤング図形の基礎ダイアグラムは (m − 1) × 1 長方形ヤング図形
と 1 × (n − 1) 長方形ヤング図形の(アルゴリズムとしての)和に同型である.
命題5 (i) (Y, φ) をダイアグラムとする. w, z1 , z2 , z3 ∈ Y とし, zi ̸= zj , zi ̸∈
φ(zj ) (1 ≤ i, j ≤ 3) かつ任意の 1 ≤ i ≤ 3 に対し w ∈ φ(zi ) または zi ∈ φ(w)
のどちらかが成り立つとする. このとき {w, z1 , z2 , v} が正方形になるような
v ∈ Y は存在しない. とくに, ダイアグラムは3次元立方体を含まない.
(ii) (Z, ψ) を基礎ダイアグラムとする. zi ̸= zj , zi ̸∈ φ(zj ) (1 ≤ i, j ≤ 3) であ
るような z1 , z2 , z3 ∈ Z は存在しない.
Greene-Nijenhuis-Wilf の確率アルゴリズム
から色付きフック公式へ
5
箱の数 n のヤング図形 Y が与えられたとき, ひとつの箱 x を等確率
1
n
で
選び, フック H(x) が x 以外の元を含むときには H(x) \ {x} の元 y を等確率
1
|H(x)|−1
で選び, H(y) ̸= {y} なら z ∈ H(y) \ {y} を等確率で選び・
・
・と繰
り返していくと, いつかは H(w) = {w} であるような箱 w(←ヤング図形の
右下カドにある箱)に到達する. Y から箱 w を取り除いて得られるヤング図
形を Y ′ とし, Y の代わりに Y ′ に対して同じ手順を繰り返す。これが Greene
と Nijenhuis と Wilf による確率アルゴリズム (GNW アルゴリズム)である.
与えられたヤング図形 Y から右下カドの箱を1個ずつ落としていき, 最終的
には空なヤング図形 ∅ に至る道筋のことを Y の標準盤という. GNW アルゴ
リズムは与えられたヤング図形の標準盤を選び出す確率アルゴリズムである.
次の驚くべき結果が成立する.
定理 (Greene, Nijenhuis, Wilf [Adv. in Math. 31(1979)])
ヤング図形 Y にお
Q
ける GNW アルゴリズムは Y の任意の標準盤を等確率
|H(x)|
n!
x∈Y
で選び出
す. とくに Y の標準盤の個数は上の確率の逆数に等しい.
注意3 この定理の後半は標準盤の個数に対するフック公式 (←対称群の既約
表現の次数公式でもある)の別証明になっている.
(P, φ) をアルゴリズムとする. p, q ∈ P が φ(p) ∋ q を満たすとき p → q と
かき, 遷移という. また p0 , p1 , . . . , pk ∈ P (k ≥ 0) が p0 → p1 → · · · → pk
を満たすとき長さ k の路という. 遷移 p → q が φn (p) ̸∋ q (n ≥ 2) を満
たすなら単純遷移といい, すべての pi−1 → pi が単純遷移であるような路
p0 → p1 → · · · → pk を単純路という. 単純路は標準盤の概念の一般化であ
る. 第3節の定義2で述べた一般のダイアグラムにおけるフックの概念を用
いると, GNW アルゴリズムを一般化して, 平明アルゴリズムの状態 p を与え
られたとき p から終状態(←第2節の命題3により一意に決まる)に至る単
純路を選び出す確率アルゴリズムを構成することができる.
定理 (岡村修志 [大阪大学修士論文 (2003)]) 平明アルゴリズムにおいて GNW
の定理の類似が成り立ち, とくに単純路の個数に関するフック公式が成立す
る.
岡村の結果は平明アルゴリズムの基本定理(第3節の定理1)が得られる
前に証明された. その後, 岡村と筆者で基本定理を用いて GNW-岡村の結果
の意味を検討したところ, これらの結果は本質的にはダイアグラム(←単項
平明アルゴリズムと等価)についての性質ではなく, ずっと特殊な基礎ダイ
アグラムについての性質であることがわかった. (とくに, 元の GNW の定理
は驚くべき結果であるにも関わらず, 本質的には第4節の例7で述べた殆ど
trivial な基礎ダイアグラムについての結果であることが明らかになった.)当
然, 同じ性質が一般のダイアグラムについても成り立つ筈であるということ
から次の色付きフック公式(Colored Hook Formula)の予想へと導かれ, そ
れが仲田によって証明され, 定理となった.
定理 (仲田研登 [to appear in Osaka J.Math.]) 任意のダイアグラムについて
成立するが, 簡単のため, ヤング図形の場合(第3節の例5)に限定して述べ
る. ヤング図形 Y の左上隅の箱のフックに含まれる一つ一つの箱に相異なる
変数(色変数)を割り振っておく. それ以外の( Y および Y より小さいヤン
グ図形の)箱には, その箱から左上 45 °の方向にある箱と同じ色変数を割り
振る. Y をダイアグラムとする単項平明アルゴリズム ⟨p⟩ における(単純と
は限らない)長さ k の路 (p = p0 , p1 , . . . , pk ) の集合は Y から次々と k 個の
フックを抜いていく操作の集合と正確に対応している. ( Y および Y より
小さいヤング図形の)各フックにはそれに含まれる箱の色変数の和(フック
式)を対応させ, 長さ k の路には次のような路式を対応させる. まず, 長さ 0
の路の路式は 1 とし, 長さが k ≥ 1 の路 p = (p = p0 → · · · → pk ) の路式は,
p′ = (p = p0 → · · · → pk−1 ) の路式を用いて帰納的に
(p′ の路式) × (p で除かれる k 個のフックのフック式の和)−1
で定義する. このとき 路式全体の総和 =
∏
{1 + (H(x) のフック式)}−1
(色付きフック公式)
x∈Y
が成り立つ.
注意4 (i) 上の色付きフック公式の左辺には Y から次々とフックを抜くこと
で得られる多数の小さいヤング図形のフックがすべて関連しているが, 右辺
は Y 自身のフックしか関係していない. 一見, 不思議なこの事実は平明アル
ゴリズムの基本定理(第3節の定理1)の反映である.
(ii) ヤング図形に対する色付きフック公式の両辺において, 分母の次数が最
大である項のみを取り出して等置し, その上ですべての色変数に 1 を代入す
れば, 通常のフック公式が得られる.
(iii) 仲田の定理を基礎ダイアグラムに適用すれば, 岡村の定理の証明で鍵と
なることを全て導くことができる.
6
佐藤のゲームと平明アルゴリズム
第1節の注意1で述べたように, 単項な有限選択的平明アルゴリズム ⟨p⟩ を
p を最初の局面とする2人ゲームと考える. 主要な問題は局面 p が先手必勝
か後手必勝かを少ない計算量で判定することである. 計算量が多くても良い
のなら, ゲームの可能な進行をずっと先まで全て追いかけることにより, 判定
ができることは自明である. しかし, 平明アルゴリズムの場合は基本定理(第
3節の定理1)により, ゲームの進行の全体がダイアグラム(ゲームの初期
についての条件)により統制され, ダイアグラムはフック構造により記述さ
れるので, ダイアグラムのフックについての情報のみで, どちらが必勝かを具
体的に判定できるはずである. (第5節の注意4 (i) を参照. )
定理2 任意のダイアグラムで成立するが, 簡単のため, ヤング図形の場合に
限定して述べる. ヤング図形 Y をダイアグラムとする単項平明アルゴリズム
(第3節の例5)を2人ゲームと考える. (Y から始めて2人のプレイヤーが
交互にフックを抜いていくゲームと考えてよい.)このゲームは次の値が0の
とき後手が, 0でないときには先手が必勝である.
E(Y ) = ⊕x∈Y n(|H(x)|).
ただし, ⊕ は自然数を2進法で表した後, 桁ごとに mod 2 で(繰り上がり
なしで)加える(ニム和, あるいは排他的論理和と呼ばれる) 算法であり,
n(a) = a ⊕ (a − 1) である.
注意5 定理2のヤング図形の場合と同値な結果は C.P. Welter(Indag. Math.
16(1954))により証明された. ただし, そこではヤング図形やフックの概念
との関係については気付かれていない. J.H. Conway の “On Numbers and
Games, Academic Press, 1976” には Welter の論文の解説がある. 佐藤幹夫
(第12回代数分科会シンポジウム報告集 (1968), 数学のあゆみ 15-1(1970))
は, これらとは独立に同一の結果を証明し, ヤング図形との関係も指摘した.
このような事情から, ヤング図形の場合のゲームは Sato-Welter game と呼ぶ
のが良いように思われる.
7
鏡映アルゴリズム
(Coxeter 群・ルート系との関係)
非可換群のクラスの中で, ある意味で最も単純なものが Coxeter 群である.
この節では Coxeter 群についての標準的な教科書 J.E. Humphreys, Reflection
Groups and Coxeter Groups, Cambridge Univ. Press を参照文献とする.
(W, S) を Coxeter 系とする. このとき S は群 W の生成系であり, 単純な形
の基本関係式を満たす. S の元を単純鏡映という. S の元と共役な W の元を
鏡映といい, 鏡映の全体を T とかく. l(·) を S に関する W 上の長さとする.
w ∈ W に対し N (w) = {t ∈ T | l(wt) < l(w)} とおく. W ′ を T のある部
分集合で生成された W の部分群とする. このような W ′ を W の鏡映部分群
という. Dyer と Deodhar の結果により, S ′ = { t ∈ T | N (t) ∩ W ′ = {t} }
とおくと, (W ′ , S ′ ) は Coxeter 系であり, その鏡映の全体 T ′ は T ∩ W ′ と一
致する. J ⊂ S に対し J で生成される W の部分群を WJ とかく. 任意の
WJ w ∈ WJ \W に対し, WJ w の元 w̄ で長さ最小のものが一意的に存在する.
上の記号のもとで PJ = WJ \W とおき, ΦJ : PJ −→ 2PJ を
ΦJ (WJ w) = { WJ wt | t ∈ N (w̄) }
で定義する. こうして得られるアルゴリズム (PJ , ΦJ ) とその充満部分アルゴ
リズムを鏡映アルゴリズムという. また, W ′ を W の鏡映部分群とするとき,
ΦJ,W ′ : PJ −→ 2PJ を
ΦJ,W ′ (WJ w) = { WJ wt | t ∈ N (w̄) ∩ T ′ }
で定義し, (PJ , ΦJ,W ′ ) とその充満部分アルゴリズムを W ′ 制限付き鏡映アル
ゴリズムという. (制限付き)鏡映アルゴリズムはルート系のことばで記述
することもできる.
注意6 鏡映アルゴリズムは有限かつ有限選択的なアルゴリズムでもある.
例8 W を n 対称群とし, S をその隣接互換 si = (i, i + 1) (1 ≤ i ≤ n − 1) の
集合とすると (W, S) は Coxeter 系である. J = S \ {si } とおくと WJ \W は
i × (n − i) 型の長方形ヤング図形に含まれるようなヤング図形の全体と自然
に対応する. この対応により, 単項アルゴリズム ⟨WJ w⟩ (w ∈ W ) はヤング図
形をダイアグラムとする平明アルゴリズム(第3節の例5)に同型となる.
定理3 ある Coxeter 系 (W, S) における W ′ 制限付きの単項な鏡映アルゴリ
ズムは Coxeter 系 (W ′ , S ′ ) における(制限なしの)単項な鏡映アルゴリズム
と同型である.
例9 (W, S) を例8の通りとし, W ′ を互換(=鏡映)の集合
{ (i, j) | j − i ≡ 0 mod p, 1 ≤ i < j ≤ n } ( p は与えられた自然数)
で生成された W の鏡映部分群とする. このとき, 定理3の主張は対称群のモ
ジュラー表現論における「中山予想」に関連して導入された p-core, p-quotient
の理論に他ならない.
定理4 (i) 鏡映アルゴリズム ⟨WJ w⟩ が平明であるための必要十分条件は ⟨WJ w⟩
における単純遷移がすべて
WJ v → WJ vs
(WJ v ∈ ⟨WJ w⟩, s ∈ N (v̄) ∩ S)
で与えられることである.
(ii) 単項な平明アルゴリズムはすべて simply-laced な Coxeter 系 (W, S) に
おける鏡映アルゴリズムとして実現できる.
(iii) 平明アルゴリズムの分類は R.A. Proctor(J. Algebra 213(1999), J.
Algebraic Comb. 9(1999))の d-complete poset の分類に一致する.
注意7 上の (iii) で言及した Proctor の研究は D. Peterson による Kac-Moody
Lie 代数の minuscule 元の概念の組み合わせ的側面を扱ったものである. 第
5節の岡村の定理の後半は Peterson による minuscule 元の最短表示の個数定
理(未発表)の別証明になっており, 仲田の定理はそれよりずっと強い主張に
なっている.
ダウンロード

ゲーム・アルゴリズム・表現論