a, b

non-composable
arrow networks
generalized
Young diagrams
Noriaki Kawanaka （川中宣明）
The Open University of Japan,
Osaka University
Arrows in Math. 1
A
B
C
logical implications
Arows in Math. 2
f
A
B
g
g f
○
C
mappings
Composition law
A
B
C
Associative law
h (g f ) = (h g) f
○
B
f
○
○
g
○
C
h
A
D
Unit law
A
A
A
ι
tautology
A identity map
Category Theory （圏論）:
Theory of arrow networks
satisfying :
composition law,
associative law, and
unit law
Arrows in daily life 1
B
D
building
A
C
Arrows in daily life 2
E
D
C
algorithms
B
A
Arrows in daily life 3
兵
moves of
a game
Group Theoretical Formulation 1
G : group, G = < T >, G acts on X
For A, B ∈ X,
A
B
def.
tA=B
for some t ∈
T
Group Theoretical Formulation 2
Example:
G = < a, b >, ab = ba, T={ a, b }
2
G acts on Z by a = , b =
b
Then
a
a
b
Thus we recover the picture :
B
D
building
A
C
Edges of octahedron
F
D
E
B
C
正八面体
A
untidy bookshelf
M
C
M
M
C
C ＝ comic book
C
C
M
M
M ＝ math. book
Interchange M with C, if M is to the right of C.
MMC C
Algorithmic
octahedron
C MMC
MC MC
C MC M
MC C M
C CMM
G = S4 = < a, b, c >
a = (1,2), b = (2,3), c = (3,4)
a 2 = b 2 = c 2 = id.
aba = bab, bcb = cbc, ac = ca
We put:
X = G/H, where H = < a, c >
T = the set of transpositions∈ G
= { a, b, c, aba, cbc, acbca }
Group theoretical octahedron
bacbH
cbc
H = < a, c >
b
acbca
a
acbH
‘longer’ coset
cbH c
bH
a
c
acbca
aba
abH
b
cbc
aba
H
‘shorter’ coset
A non-composable arrow network
Call this an (abstract) algorithm.
Is it possible to create a theory
for a special class of algorithms?
Plain algorithms （１）
（「数学」 2011年秋）
Charcterized by 3 axioms.
（Axiom 1）
or
square
∃!
Plain algorithms （２）
（Axiom 2）
Plain algorithms （３）
（Axiom 3）
square
square
D (s) = the diagram at s
s
・・・
・・・
In a plain algorithm,
def.
< s > = the set of positions reachable
from s via a successive arrows
def.
D(s) = the set of positions reachable
from s via just one arrow
< s > and D(s) are plain algorithms,
which might contain infinite arrows.
Example :
<A> =
{
F
D
E
B
}
C
D(A)
A
E
C
D
B
2×2 Young diagram
Young diagram
visualization of a partition
(8,8,5,4,3,3,1)
A hook of a Young diagram
due to Tadasi Nakayama (中山正)
box x
Ｈｘ = the hook at x
the length of Ｈｘ＝ 7
Subtracting a hook
from a Young diagram
（中山正）
subtraction
process
the result of
subtraction
Arrow & hook
t
s
Each arrow represents
a hook subtraction process
in a generalized Young
diagram.
D(t) is obtained from D(s)
via a hook subtraction.
Hook subtraction &
Φ octahedron
The fundamental theorem
of plain algorithms
The isomorphism class of < s > is
uniquely determined by that of D(s).
In other words：
All the information of < s > is
contained in D(s).
D(s)
s
〈s〉
Examples
1．Colored hook formula
( K. Nakada :
Osaka J. Math. 45, 2008 )
2．( Generalized ) Sato’s game
: talk at ECNU
Colored Hook Formula (1)
With an arrow α＝ (s → t),
we associate an element
F(α) of a field K
in such a way that :
Colored Hook Formula (2)
γ
β
α
α’
β
F(α) = F(β) + F(γ)
square
α
β’
F(α) = F(α’)
F(β) = F(β’)
Colored Hook Formula (3)
With a path
γ
α
β
p = (s → t → u → ・・・ )
of finite length l(p) , we associate
F(p) = F(α)+F(β)+F(γ)+ ・・・
( F(p) = 1, if l(p) = 0. )
Colored Hook Formula (4)
Let P(s) be the set of
paths of finite length starting at s .
∑t
l(p)
p∈P(s )
-1
F(p ) =
∏ (1+ t F(s→x)
-1
x∈D(s)
： a generalization of K. Nakada’s
Colored Hook Formula (Osaka J.Math. 2008)
to a not-necessarily-finite plain algorithm
)
Example
c－ b = d－ a
b
c
c+a=d+b
a
d
c
d
a
b
Colored hook formula
for 2×2 Young diagram
1 + t/a + t/b + t/c + t/d
+t 2/ba+t 2/bc +t2/ad +t2/cd + t 2/{b(b+d)}+ t 2/{d(d+b)}
2
2
+ t /{a(a+c)} + t /{c(c+a)}
3
3
3
3
+ t /bad + t /bcd + t /{ba(a+c)} + t /{bc(a+c)}
+ t3/{ad(d+b)} + t3/{cd(d+b)}
4
4
+ t /{bad(d+b)} + t /{bcd(d+b)}
= (1+ t/a)(1+ t/b)(1+ t/c)(1+ t/d),
where c+a = d+b.
Classical hook-length formula
for a Young diagram
The number of standard tableaux
for a given Young diagram Y
= n! / Π hx
( n = #Y, hx = #Hx )
x∈Y
: A specialization of a special case of
Nakada’s formula
Sato’s game
Given a Young diagram,
2 players alternatively
subtract a hook.
A player who produce the empty
diagram is the winner.
Generalized Sato’s game
There exists a nice theory for
a generalization of Sato’s game
based on the theory of
plain algorithms.
( talk at ECNU )
謝謝
Thank you.
同値な矢印
B
B
D
A
D
square
～
A
C
C
既約な矢印
A
B が可約とは
A
B
・・・
（2本以上の矢印の合成）
可約でないとき既約
Jordan-Hölder型定理
（有限性の仮定の下で）
平明アルゴリズムにおいて
矢印の既約分解は
同値を除いて一意的
平明アルゴリズムの
群による表現
群 G とその生成元集合 S を指定
既約矢印の同値類に
S の元を対応させ
st・・・uv
s
t
・・・
v
u
とする
Weyl 群と Klein の 4元群
1. Weyl 群による faithful な表現
（平明アルゴリズムの群論的構成：
対称群の場合が、佐藤のゲーム）
2. Klein の4元群による表現
（ゲームとしての平明アルゴリズム
の性質を取り出す）
Klein の 4元群 G = <A, B>
AB = BA,
A2 = B2 = E
：最も易しい非巡回アーベル群
であり, Weyl 群でもある
G の生成元 A, B を
交互にハコに入れる
AA
Y＝
A B
A
B
A
B
A
B
A B
A
B
A
B
A
A
B
A
B
A
B
A
B
A
A
B
A
B
A
B
B
A
≡ 0 mod 2
a0 ＝ 0
フック内の元の積を計算
A B
A
B
A
B
A
B
A B
A
B
A
B
A
A
B
A
B
A
B
A
B
A
A
B
A
B
A
B
B
Y＝
A
A B
B
A
B
AB
フックに入っている元の積を記入
Y＝
AB
E
A
E
AB
E
A
AB
AE
A
B
B
AB
B
A
B
AB
A
A
B
AB
B
A
B
A
E
A
A
B
AB
E
AB
B
A
G の非自明な部分群 (≠ G)
HAB = { E, AB }
HA = { E, A }
HB = { E, B }
部分群 HAB = {E, AB} に対応する商
AB
AE
Y＝
E
A
AB
B
B AB
E
AB
E
A
AB
B
A
B
AB
A
A
A
B
AB
B
B
A
E
A
A
B
AB
E
AB
B
A
ヤング図形 Y の HAB 商
YAB ＝
≡ 1 mod 2
∴ a1 ＝ 1
YAB の HAB 商
A
AB
AB A
1
A
AB B
B
A
AB
B
＝
B
の HAB 商
Y(AB)(AB)
≡ 1 mod 2
∴ a2 ＝ 1, a3 ＝1
ヤング図形 Y の AB 展開
Y＝
の AB 展開
a3 a2 a1 a0
E(Y) ＝ 000・・・01110
（一般化）佐藤のゲームの基本定理
ダイアグラム D(s) の
AB 展開 E( D(s) ) ＝・・・ 0000
局面 s において
後手に必勝戦術がある
（具体的な戦術も A 商, B 商も用いることで
綺麗に記述できる）
skew Young 図形
赤い部分は完全に残すような「手」
だけを許すゲームを考える。
最も簡単な skew ダイアグラム
A完全ダイアグラム
Y の HA 商の HA 商の HA 商の・・・
に含まれるような箱を「A完全な箱」
Y の「A完全な箱」のフックを次々
引いていって Φ になるとき
Y は「A完全ダイアグラム」
YがA完全でない ⇒
E(Y) = ・・・ 0000 が後手必勝の
必要十分条件
Y=
YがA完全 ⇒
E(Y) = ・・・ 0001
が後手必勝の
必要十分条件
その次に簡単な skew ゲーム
または
を残す「手」
のみを許すゲーム
定理（必勝法計算手順）
まず , Y の <AB> 展開を計算:
・・・・・・ a2 a1 a0
① a0 = 0 のとき
② a0 ≠ 0, a1 = 0 のとき
③ a0 ≠ 0, a1 ≠ 0 のとき
HAB 商へ
HA 商へ
HB 商へ
・・・ 01110
AB
AE
Y＝
E
Y の HAB　商
A
B
AB
B AB
E
AB
E
A
AB
B
A
B
AB
A
A
A
B
AB
B
B
A
E
A
A
B
AB
E
AB
B
A
YAB の HB 商　A
AB
AB
1 A
AB
B
B
B
の HB 商
A
A
AB
Y(AB)(B)
B
＝
AB
B
A
B
B
B
B
B
文
献
C.P. Welter : Indag. Math. 16, 1954
佐藤幹夫：代数幾何Sympo報告集, 1968
数学のあゆみ 15-1 , 1970
J.H. Conway : On Numbers and Games,
Ch.13, 1976
今日の話：フック構造をもつ
ゲームとアルゴリズム,
「数学」 2011
Sato のゲームの１行表示
β 数の箇所に「石」をおく
0
1
2 3
4 5
6
7 8
9 10 11 12 13 14 15
左へ移す＝フックを引く
石の移動距離＝フック長
Sato-Welter のゲーム
２人ゲーム：盤に有限個の石を配置
0
1
2 3
4 5
6
7 8
9 10 11 12 13 14 15
左へ
交互に石を１コ選び、より左で石のない
マス目へ移す。移せなくなったら負け。
同じことをヤング図形でも・・・
ヤング図形÷ 2 の商
÷2 の商
＝
ヤング図形 Y の 2進展開（1）
Y＝
≡ 1 mod 2
∴ a0 ＝ 1
G の部分群 HB = { E, B } に対応する商
Y＝
AB
E
A
E
AB
E
A
E
A
B
AB
E
AB
B
A
B
AB
B
A
B
A
E
A
A
B
AB
E
AB
B
A
B
必勝手順を構成できるか？
答できる。
ＳＷＣの定理より
ずっと強い結果
一般に, 佐藤のゲーム
とその仲間について
（公理系で定義,
Coxeter 群を使って実現）
非決定的な力学系
２人ゲーム、１人ゲーム
（非決定性）アルゴリズム
確率アルゴリズム
マルコフ連鎖
力学系
（今日は「２人ゲーム」に集中した）

Download Report