置換のあみだくじ化
あみだくじはどんな置換も作れるか？
このワークシートはMath by Codeの一部です。
３本線のあみだは３つの番号{1,2,3}の順列、置換と同じであることはわかった。
たて線が4本以上のｎ本のときのｎ本あみだは,ｎ番号の置換になることは予想できる。
しかし、実際に任意のｎ！もある置換のすべてをあみだくじで表現できるのだろうか？
この問は、「あみだは置換」か？
ではなく、「置換はあみだ」か？
と言い換えることもできるね。
０．そもそも置換ってなんだっけ？
＜写像と演算＞
（写像）
要素、たとえば、番号の集めた集合を考えてみよう。
整数０からn-1まで集めた集合をZnと呼ぼう。
たとえば、Z5={0,1,2,3,4}だ。
X=Z5, Y=Z30とするとき、
Xの要素xを２乗したものをYの要素yに対応させる関数fを考えよう。
関数ｆは(x,y)のペアで表すことができるね。
(0,0),(1,1),(2,4),(3,9),(4,16}
数と数の対応を関数というけど、
数にかぎらず広げたものが写像です。
写像ｆ：X→Y
と対応する集合でかいたり、
写像ｆ：x→x2
と対応する要素の記号を数式でかいたりする。
Xを始域、定義域、Yを終域と呼ぶこともあるね。
写像はふつう、始域と終域がちがっていてもよい。
(全射と単射と全単射）
Yの中でXがｆで写った先、f(X)={y| x∈X, y=f(x)}= {0,1,4,9,16}を像image、値域といい、
imfとかいたりする。
ここで大切なことの１つめは、Xの要素が変わると、Yも変わることだ。
Xのお相手は別々であり、Xのお相手がYの中でかぶる、モテモテのYはない。
これを単射という。
さらに大切なのは、f(X)がYと一致するとはかぎらないということだ。
f(X)はYの中ではスカスカになっていて隙間がある。f(X)に関係ないYの要素がある。
それに対してちがう状況を作ってみよう。
X=Z5, Y=Z5として
id : x→xという何もしない写像、恒等写像を考えよう。
すると、f(X)=Yとなり、f(X)はYの全部に入っているから、
Yはぜんぶf(X)で写ってきているので全射という。
（逆写像）
写像ｆ：X→Yと写像ｇ：Y→Zを続けて行うと、
ｘ→f(x)→g(f(x))となる。この操作をまとめて、
x→g*f(x)とかくことにすると、
g*f：X→Z
g*f：x→g(f(x))
のように、写像が合成できる。
写像ｆ：X→Yと写像ｇ：Y→Xについて、
その合成が恒等写像になるとき、つまり、f*g=id で g*f=id
ｇはｆの逆写像(inverse)といい、ｆ-1とかくことがある。
ｆが全単射（全射で単射）であることと、ｆに逆写像があることは同値ですね。
（演算で閉じている）
集合Xの要素x,yから２つを選び、その演算*の結果の要素zを求めることは
要素かくと、x*y=zになるね。
これを要素の写像でかくと、
*： (x, y) →ｚ
とかけるね。
これを集合でかくと、同じ集合Xから任意の２要素を選ぶことは積の法則からn(X)2通りあるね。
要素の組自体をX×XとかX2とかき直積と呼ぶ。積集合は集合の重なりの意味で使うため。
*：X2→Z
演算結果がXに属するときは、演算で閉じているという。集合でもわかるようにかこう。
*：X2→X
（例）
たとえば、２項演算×、+は整数Zでは閉じているので次のようにかけるね。
+：Z2→Z
×：Z2→Z
（例）
たとえば、G={100,2000}, R={0.03, 0.05, 0.08, 0.1} Gが税抜き価格、Rが歴代の消費税率
それぞれの税額Yを計算すると、
×：G×R→Y
G×R={(100, 0.03),(100,0.05),(100,0.08),(100,0.1), (2000,0.03), (2000,0.05), (2000, 0.08),(2000,0.1)}
Y={3, 5, 8, 10, 60, 100, 160, 200}
（置換はどんな写像か？）
置換は、番号の集合から番号の集合への写像だ。
とくに、決まった数式で移しているわけでなくてもよいので、関数である必要はない。
ただ、始域の番号が、終域に移ればよいわけだ。
たとえば、巡回群(1 2 3)は
1→2, 2→3,3→1という動きをしているので、
写像としてとらえるとX={1,2,3}
f：X→X
f(1)=2, f(2)=3,f(3)=1
のように対応をはっきりとかくことができる。
だから、写像だ。
しかも、別ものが集中するようなf(1)=f(2)のようなこともないので単射だ。
そして、写ったあとのどの番号を逆にたどることもできるので全射だ。
全単射の写像だと言える。
ただし、恒等写像とは限らず、番号の置き換え、置換をさまざま表現できる写像だね。
だから、通常の番号や数の変換とちがって、
番号は順序や大きさを表すものというよりも、ただ、区別のための名前というイメージを
取り組もう。
関数のような簡単な数式をすぐに求めるのではなく、要素の関係性、集合の関係性を
ていねいに追いかけるという姿勢が必要でしょう。
１．置換を互換の積にする
＜置換→巡回置換の積→１要素共有互換の積＞
（置換は巡回置換の積に直せる）
どんな置換にも、１→a, a→b, b→.....→1のようなループサイクルがあるね。
X＝{1,2,3,....., n}
置換ｆ：X→X
とすると、ｎ個の要素の一部分ｍ個でループができる。つまり、ｍ個の巡回置換ができる。
こんどは、残ったn-m個の要素で同じようなループを探すことができる。
だから、これを繰り返すことで、
置換は互いにかぶらない巡回置換の積に直せる。・・・・★
（巡回置換は１要素共有の互換の積に直せる）
たとえば、
（実験）
巡回置換（2 4 6 8)を先頭が必ず含まれる互換(2 4),(2 6),(2 8)の積で表そう。
巡回置換は２→4, 4→6, 6→8,8→2の番号の入れ替えをサイクリックに行っている。
一方の互換は（2 a)は2→aとa→2の交換を同時におこなう。
巡回置換で終点か始点に２があるのは、2→4と8→2だ。
一方で、終点にも始点にも２がないのは、間に２をはさむと実現できる。
4→6は 4→2→6
6→8は、 6→2→8。
だからこの４つの巡回を実現するための互換の順番は(2 4),( 2 6), (2 8)の順に実行する。
2→4は 2→4
8→2は 8→2
4→6は 4→2→6
6→8は 6→2→8
つまり、(2 4 6 8)＝( 2 8)(2 6)(2 4) と互換を実行する順に右から並べる。
（一般化）
巡回置換（x a b c d e f )を１要素共有互換(x a),(x b),(x c),(x d),(x e),(x f)の積で表そう。
x→aは x→a
a→bは a→x→b
b→cは b→x→c
c→dは c→x→d
d→eは d→x→e
e→fは e→x→f
f→xは f→x
つまり、
巡回置換は１要素共有互換の積で実現できる
（x a b c d e f )=(x f)(x e)(x d)(x c)(x b)(x a)・・・・★０
質問：巡回置換は１要素共有互換の積をコードで確かめるにはどうしましょう。
基本となる巡回置換（リスト形式）を辞書に変えるami2dic関数、
置換aによるkの行先を返すami_go関数は前回と同じ。
リスト形式の互換、置換の辞書のリスト（のリスト）から互換・置換の積を辞書で返す
polymulti(gokan_Lst)、polymultiR(gokan_Lst)を新しく作ろう。
そして、たとえば、gokans=[[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]をamis2dicsで辞書リストにしてから、
polymultiRに入れる。
名前で比較するため、Nlist=rotdic(S,SN) をしておく。
g=[1,7,6,5,4,3,2]をami2dicに入れた結果の辞書が同じになることを確認してみよう。
[IN]Python================================================
def polymulti(gokan_Lst):
listsize=len(gokan_Lst)
a = gokan_Lst[0]
for num in range(1,listsize):
b = gokan_Lst[num]
a = conL(a,b)
dic = a
#空の辞書は形式的に単位元とする。
if len(dic)==0:
dic[1]=1
return dic
#互換の連続(互換辞書のリストgokan_lstをとり左から連続的に演算して名前を返す）
def polymultiR(gokan_Lst):
listsize=len(gokan_Lst)
a = gokan_Lst[0]
for num in range(1,listsize):
b = gokan_Lst[num]
a = conR(a,b)
dic = a
#空の辞書は形式的に単位元とする。
if len(dic)==0:
dic[1]=1
return dic
a=[1,2]
b=[1,3]
c=[1,4]
d=[1,5]
e=[1,6]
f=[1,7]
g=[1,7,6,5,4,3,2]
gokans =[a,b,c,d,e,f]
S=[a,b,c,d,e,f,g]
SN=["a","b","c","d","e","f","g"]
Nlist=rotdic(S,SN) # 名前表示のため
gokansdics=amis2dics(gokans)
print(name(polymultiR(gokansdics)))
print(name(ami2dic(g)))
#=============================================
[OUT]
g
g
3本だけのあみだくじを使って、置換と互換の法則を確認しよう。
2．どんな互換もあみだくじに直せるか
＜（１ｎ）互換を隣接互換（ヨコ線）の積で表す。＞
（実験）
あみだくじのヨコ線は隣接互換でした。
３本あみだくじの(12)(23)(12)が互換(13)になることも知りました。
そのときのかぎは、最初と最後が同じ隣接互換(12)だったことです。
だから、最初のヨコ線2→1のあと、最後に１→２があるから、１をつなぐと２→２になったのでした。
それに対して１回だけヨコ線ある３は真ん中で3→2となり最後に2→１となり、3→2→１です。
残りの１は次々の線を変えて１→2→３となります。結局（１３）となるのでした。
４本あみだで同じような積を作ってみましょう。
(12)(23)(34)(23)(12)はどうなるでしょう。
もちろん、２→1→2で２はもとに戻ります。
さらに、３→２→３で３ももとに戻ります。
４は４→3→2→１と１まで移動し、１は反対に1→２→３→4と４まで移動して終わります。
だから、（１４）になります。
（一般化）
あみだくじでは上下対称続く、隣接互換の積の式が左右対称に続くとき、
１はｎまで移動してから終わり、ｎは１まで移動して終わり、他はもとに戻るか動かない。
だから、
(12)(23)(34).......(n-2 n-1)(n-1 n) (n-2 n-1).........(34)(23)(12)＝（１ n） ・・・・★１
＜( i j )互換を隣接互換の積で表す＞
（実験）
たとえば、１０本あみだくじであっても互換（６ 10）は★１の考えで作れるはずだ。
１２３４５は動かす必要がなく、６７８９ 10の線だけ使う。
すると★１の１にあたるものを６の線にすればよいだろう。
10−６＝4で、１＋4＝5だから、６の位置を１番と思って★１の式をかこう。
(12)(23)(34)(45)(34)(23)(12)=(15)
６の位置を１番と思っている式だから、1が６になるように互換の番号を6-1=5増やそう。
(67)(78)(89)(9 10)(89)(78)(67)=(6 10)
となる。
（一般化）
(i j) 互換の作成は(1 n) 互換の作成（★１）の移し替えでできる。
(12)(23)(34).......(n-2 n-1)(n-1 n) (n-2 n-1).........(34)(23)(12)＝（１ n）
i-1=p とすると、n=j-pとなるから、互換の番号をｐだけ増やせばよい。
すると、1は1+p=1+i-1=iになる。
ヨコ線は、i番からj番まで右下がりで連続して引き、j番からi番まで反転して左下がりに引けばよいね。
(i i+1)(i+1 i+2).....(j-1 j) .....(i+1 i+2)(i i+1)= ( i j) ・・・・★２
質問：(12)(23)(34)(45)(34)(23)(12)=(15)、(67)(78)(89)(9 10)(89)(78)(67)=(6 10)をコードで確かめるにはどうしますか。
上で作ったpolymultiR関数に互換の辞書のリストを入れて、帰ってくる辞書を出力してみよう。
polymultiRにgokan=[[1,2],[2,3],[3,4],[4,5],[3,4],[2,3],[1,2]]を辞書に変換して入れて返ったものが
[1,5]をami2dicに入れて返る辞書と同じかどうかを調べてみよう。
polymultiRにgokan=[[6,7],[7,8],[8,9],[9,10],[8,9],[7,8],[6,7]]を入れて返ったものが
[6,10]をami2dicに入れて返る辞書と同じかどうかを調べてみよう。
互換どうしの比較は見た目でわかるので、名前づけしない。
[IN]Python
#==============================================
gokans=[[1,2],[2,3],[3,4],[4,5],[3,4],[2,3],[1,2]]
goal=[1,5]
print(polymultiR(amis2dics(gokans)))
print(ami2dic(goal))
gokans=[[6,7],[7,8],[8,9],[9,10],[8,9],[7,8],[6,7]]
goal=[6,10]
print(polymultiR(amis2dics(gokans)))
print(ami2dic(goal))
#================================================
[OUT]
{1: 5, 5: 1}
{1: 5, 5: 1}
{10: 6, 6: 10}
{6: 10, 10: 6}
同じ辞書になるので、同じ置換だとわかるね。
３．まとめと演習
ここまでわかったことをまとめよう。
・前回は「あみだくじが置換群だ」とわかった。
あみだくじが番号の置換を表し、たてにつなぐことを演算とみなすと、
あみだくじどうしの２項演算は群であることがわかったね。
群は閉じていて、なにもしない要素（単位元、零元）があり、逆もどしの要素（逆元）がある。
このようなつながりのある要素の集合が群だった。
・今回は「置換群はあみだくじにできる」とわかった。
どんな置換でも、つぎつぎと変換することで、最終的には隣接互換の積、つまり
あみだくじに直せることがわかったね。
具体的には、次のステップで置換をあみだくじに表現できる。
置換
→互いに素な巡回置換の積
→１要素共有互換の積の積
→任意の互換の積の積の積
→隣接互換の積の積の積の積
具体的にはよこ線の本数がものすごいことになってしまう。
しかし、理論的に可能だということが、今の段階では大切にしたいことだね。
（例）８本のあみだくじを互いに素な巡回置換の積で表そう。
上を始点、下を終点の→でつなぐ、→の終点が別の→の始点になるものをさがして→を連結しよう。
1→3→4→1 から、(1 3 4)の巡回、2→6→8→7→2から、(2 6 8 7 ) の巡回、5→5から、(5)の巡回。
(1 3 4) (2 6 8 7) (5)
（例）巡回置換（2 6 8 10)を互換で表そう。
2→6が1番目だから(2 6),10→2が最後にくる(2 10)。
6→2→8にすると6→8になるから、2番めは2→8にくるから(2 8)
8→2→10にするには(2 8)のあとは(2 10)で、これが3番目。右から互換を順にならべる。
(2 10)(2 8)(2 6)
（例）互換(2 7)を１との互換の積で表そう。
2と７が1を経由して入れ替わるためには
2→1→7
7→1→2
のように、(1 2)(1 7)(1 2)とすればよい。
７と２は対等なので、(1 7)(1 2)(1 7)でもできるはず。
（例）互換(1 5)を隣接互換の積で表そう。
1→5は1→2→3→4→5で
5→1は5→4→3→2→1で実現できる。
しかし、2,3,4はもとに戻す必要がある。
1→5は1→2→3→4→5で
5→1は 5→4→3→2→1で
2→2は2→1 1→2で
3→3は 3→2 2→3で
4→4は 4→3 3→4で
実現できる。先にやる互換を右にかく。左右対称で、中央に(4 5)がくる。
(1 2)(2 3)(3 4)(4 5)(3 4)(2 3)(2 1)
（例）3次の置換はどれも、２つの互換b=(1 2)と巡回置換s=(1 2 3)の積を使って表せる？
s3=e, b2=eだから、eができる。
言い換えると、s-1=s2, b-1=b
s-1=(1 3 2)
b s-1=(1 2)(1 3 2)=(1 3)
s b s-1=(1 2 3)(1 3)=(2 3)
これで、３つの互換と２つ巡回置換と恒等置換eが表現できた。
ぜんぶで6個の置換を表すことがでできた。３次の置換は３！＝６個だからすべて作ることができる。
++記号の演習
＜数学の抽象化は概念化と切り離せない＞
数学の抽象化は概念化、
つまり「用語と記号」の「約束」の世界だ。
群の「約束記号と用語」になれるために、群の性質を記号・用語で確認する演習をしたい人はどうぞ。
「群表」群の要素どうしの演算結果を九九表のように行列表にしたものを
「ラテン方陣」群表はどの行にも演算結果が１回づつ漏れも重複もなく並ぶ。この特徴をもつ表のこと。
「巡回群」巡回置換とはちがう。同じ巡回でも置換は群の1要素だが、巡回群は条件を満たす要素の集合。
１つの要素ｇを０乗からｎ−１乗まですると、その群の全要素ｎ個がすべてならぶ群のこと。
ｇを生成元（generator)という。ｎを群の位数という。
C={e=g0,g1,g2,g3,.....,gn-1}のように、巡回群Gではジェネレーターをｇとすると、Gの要素は、
ｇのk乗としてえ指数表現できる。もちろん、演算を乗算に限る必要はないから加法群であっても
指数表現したりすることもあるね。
ジェネレーターがgの元をとかくこともよくある。
「群の位数(order)と要素の位数」位数ｎの群の各要素はｎ乗でeになるが、
nより小さいｍ乗でeになるｙもある。ｍをｙの位数という。
群Gの位数は、集合のザイズでもあるから、|G|とかくこともできる。
プログラミングのように、length(G),len(G)とかいても伝わる。#Gと書くことがよくある。
ｍはｎの約数になる。
（例）位数６の巡回群=C6={e=g6,g,g2,g3,g4,g5}={e,g,a,b,c,d}としよう。
g6=e,(g2)3=e, (g3)2=e,(g4)3=e,(g5)6=eとなるから、g,a,b,c,dの位数は6の約数で6,3,2,3,6になるね。
質問：位数６の巡回群をコードを使って作るにはどうしたらよいでしょうか。
6本のあみだは単位元e=[1],生成元g=[1,2,3,4,5,6]とすると、gを累乗するごとにgとは異なる別の要素ができて、6乗するとeになるはず。
リストgをami2dicで辞書にしてから、べき乗を計算する。
Gのn乗関数pow(G,n)を作るには、gの要素を１つずつ増やした辞書のリストを作り、polymultiRにgを入れるよう。中のgの個数n個だけかけ算するので、g^nを計算した結果の辞書を返してくれるでしょう。
逆元がそれぞれに一意に対応するから、群になることは明らかだね。
また、pow(G,n)の計算結果を、たとえば０乗から19乗までpgという名前のリストに入れておくと、
enumerateで、一気に計算結果を表示したり、pg[3],pg[12]のようにべき乗の結果を辞書で表示できますね。
[IN]Python
#=====================================
def pow(G,n):
return polymultiR([ G for x in range(1,n+1)]) if n>0 else {1:1}
g=[1,2,3,4,5,6]
pg=[pow(ami2dic(g),index) for index in range(20)]
for i,value in enumerate(pg):
print(f"g^{str(i)}={value}")
print(pg[3])
print(pg[12])
#=====================================
[OUT]
g^0={1: 1}
g^1={1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 1}
g^2={1: 3, 2: 4, 3: 5, 4: 6, 5: 1, 6: 2}
g^3={1: 4, 2: 5, 3: 6, 4: 1, 5: 2, 6: 3}
g^4={1: 5, 2: 6, 3: 1, 4: 2, 5: 3, 6: 4}
g^5={1: 6, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5}
g^6={1: 1}
g^7={1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 1}
g^8={1: 3, 2: 4, 3: 5, 4: 6, 5: 1, 6: 2}
g^9={1: 4, 2: 5, 3: 6, 4: 1, 5: 2, 6: 3}
g^10={1: 5, 2: 6, 3: 1, 4: 2, 5: 3, 6: 4}
g^11={1: 6, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5}
g^12={1: 1}
g^13={1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 1}
g^14={1: 3, 2: 4, 3: 5, 4: 6, 5: 1, 6: 2}
g^15={1: 4, 2: 5, 3: 6, 4: 1, 5: 2, 6: 3}
g^16={1: 5, 2: 6, 3: 1, 4: 2, 5: 3, 6: 4}
g^17={1: 6, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5}
g^18={1: 1}
g^19={1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 1}
{1: 4, 2: 5, 3: 6, 4: 1, 5: 2, 6: 3}
{1: 1}
さらに、g^n=eだから、要素pの逆元g^(-1)=g^(n-1)です。
Gの位数n=6ならば、生成元gの逆元はpg(5)のはずです。
だから、pg[5]*pg[1]=eになるはず。
[IN]python
#====================================
conL(pg[5],pg[1])
#====================================
[OUT]
{1: 1}
巡回群の指数による周期性を使えば、剰余系と同じなので、
指数が負の指定があれば群の位数をたして正になるようにすればよいね。
[IN]python
#====================================
def pow(G,n):
return polymultiR([ G for x in range(1,n+1)]) if n>0 else {1:1}
g=ami2dic([1,2,3,4,5,6])
def np(g,n):
if n>=0:
return pow(g,n)
else:
return np(g,n+len(g))
print(np(g,1))
print(np(g,3))
print(np(g,-1))
print(np(g,-30))
#=====================================
[OUT]
{1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 1}
{1: 4, 2: 5, 3: 6, 4: 1, 5: 2, 6: 3}
{1: 6, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5}
{1: 1}
これで、逆元を求めることがー1乗の指定で求めることができるようになったね。