トッド-コクセターの方法(Todd-Coxeter Algorithm)について
はじめに
本記事ではトッド-コクセターの方法を解説します.トッド-コクセターの方法とは,一言で言えば,群論における生成元と関係式で与えられる群の,その生成元を$\mathfrak{S}_{n}$の元として具体的に決定するための,表を用いた手続きのことです.つまり,同じ関係式を満たす$\mathfrak{S}_{n}$の元を求める行為です.この方法によって,原理的にはいかなる有限の自由群も$\mathfrak{S}_{n}$の部分群または$\mathfrak{S}_{n}$自体として決定できます.慣れれば楽しくかつ容易にすごいことが分かる方法なので,是非やってみて欲しいと思います.
最後の方には個人的に難しくなく,かつ面白いと思った例を挙げようと思います.
ちなみに,参考文献のArtin "Algebra"では,「トッド-コクセターの方法」は"Todd-Coxeter Algorithm"と表記されています.個人的にはどちらかというとTodd-Coxeter Algorithmの方が好みなので,以下「トッド-コクセターの方法」は"Todd-Coxeter Algorithm"と表記することにします.
ここでは,自由群についての群論的な解説は省略します.
Todd-Coxeter Algorithmの解説
一般的な方法を述べるだけでは分かりにくいので,二面体群
$$
D_{3}=\langle x,y \ | \ x^{3}=y^{2}=1, yxy^{-1}=x^{-1} \rangle
$$
を例にとって実際に実行しながら解説することにします.
1.
関係式を全て$=1$の形に整理します.このとき,$-1$乗の形は使わないようにします.
$$
x^{3}=y^{2}=xyxy=1 \ \ (\because y^{-1}=y)
$$
2.
その関係式の左辺の積を構成する元を左から表の上部に書きます.このとき累乗の形は使わないようにします.
| x x x | y y | x y x y |
|---|---|---|
3.
生成元を1つ選び,それが生成する巡回部分群を作ります.これを$H$とおきます.ここでは$H=\langle y \rangle$とします.(後で,ここで$H=\langle x \rangle$とした場合と比較してみたいと思います.)
4.
$H$に対して,右から表上部に書いた元を順番にかけていきます.例えば,表左上部の$x \ x \ x$だと,以下のようになります.
$$
H, \ Hx, \ Hxx, \ Hxxx
$$
5.
4の操作によってできたものをそれぞれ右剰余類とみなします.便宜的に$H$を1と書きます.そして上でできた右剰余類を左から順に比較し,それまでに見た剰余類と今注目している剰余類が異なれば,新しい数字をふります.まず,$Hx$は$H=1$と異なる剰余類であるから,$Hx$を2と書きます.次に$Hxx$は$H=1,Hx=2$と異なる剰余類であるから,$Hxx$を3と書きます.最後に$Hxxx$ですが,$xxx=x^{3}=1$より,$Hxxx=H$なので,$Hxxx=1$です.以上の操作をもって,表に次のように記入します.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 |
流れ的には,表に書いてある文字を左から順に$H$の右にかけていって,違う剰余類が出てきたら新しい数字,同じものが出てきたら同じ数字を記入,ということになります.
6.
5でxでやったことを他の関係式についても繰り返します.次にyでやってみると,$H=\langle y\rangle$だったので,$Hy=H,Hyy=H$です.つまり$H=Hy=Hyy=1$です.よって表には次のように記入することになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 |
7.
次に$x \ y \ x \ y$についてやっていくのですが,まず$Hx$は既に2だと分かっているから,それをそのまま流用します.次に$Hxy$はこれまでのどの右剰余類とも異なるから新たに$Hxy=4$とします.$Hxyx$も同じ理由から$Hxyx=5$とします.最後に$xyxy=1$より$Hxyxy=H=1$です.従って表は以下のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 5 1 |
8.
上の表をじっと眺めてみると,真ん中では,1はyによって1から来ていますが,一方で,右側では1がyによって5から来ています.このように,同じ生成元によって,同じ数字が違う数字から来ている,または同じ数字が違う数字に行く場合,そこで異なっている数字は同じものとします.今の場合,同じyという生成元によって1という数字が1と5の違う数字から来ているから,$1=5$とします.そして**番号は若い方にそろえます.**つまり5を1に変更します.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
これを群論的に解釈すると,最終的には$Hxyxy=H$となることが分かったので,これに右から$y^{-1}$をかける(つまり1つ戻る)と$Hxyx=H$なので$5=Hxyx=H=1$,ということです.
9.
さっきは$H=1$を最初の基準として,どんどん操作を加えていきました.これは表の各関係式の両端が1から始まり1で終わるということに対応しています.現時点で,数字は1,2,3,4が出てきているので,次は2を基準にして同じ操作を繰り返します.最初に$x \ x \ x$でやってみると,これは既に行った操作から,xは1を2に,2を3に,3を1に移すことが分かっているので,表は次のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
| 2 3 1 2 |
10.
次に$y \ y$についても同じことをするのですが,既にやった操作から,yは2を4に(右上参照)することが分かっていて(つまり$(Hy)y=Hyy=4$),また$2=Hy$にyを二回右からかけたもの$Hyyy$は$y^{2}=1$より$Hyyy=Hy=2$なので,結局表は次のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
| 2 3 1 2 | 2 4 2 |
11.
$x \ y \ x \ y$についても同じことをします.今xは2を3にすることが分かっていますが,yが3を何にするかは未知ですから,yは3を5にするとします($5=1$だったことは気にせず,あくまで新たな数字として5を使います).同様に,xが5を何にするかは未知ですのでまた新しく6とします.最後のyが6を何にするかですが,これは一周して$Hy(xyxy)=Hy=2$となるはずです.よって一旦表は次のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
| 2 3 1 2 | 2 4 2 | 2 3 5 6 2 |
しかし真ん中の$y \ y$に注目すると,2はyによって4からくるはずなので,$6=4$です.よって表は訂正されて次のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
| 2 3 1 2 | 2 4 2 | 2 3 5 4 2 |
12.
**このプロセスは出てきた数字を全て基準とするまで続けます.逆に言うと,このプロセスは出てきた数字が全て基準となり,かつ,これ以上新しい数字が出てこなくなったら終了します.**従って次は3を基準にします.このときの表は一旦次のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
| 2 3 1 2 | 2 4 2 | 2 3 5 4 2 |
| 3 1 2 3 | 3 5 3 | 3 1 1 2 3 |
$y \ y$で3はyによって5からくるのに対して,$x \ y \ x \ y$では3はyによって2から来ています.なので$5=2$です.このとき2段目の5も訂正され2になるのですが,この5($=2$)はxによって4に行きます.一方最初に2はxによって3に行くことが分かっているので,$4=3$です.これによって表は次のようになります.
| x x x | y y | x y x y |
|---|---|---|
| 1 2 3 1 | 1 1 1 | 1 2 3 1 1 |
| 2 3 1 2 | 2 3 2 | 2 3 2 3 2 |
| 3 1 2 3 | 3 2 3 | 3 1 1 2 3 |
今,出てきている数字は1,2,3であり,それらすべてが既に基準となっている(新しい数字が出てきていない)ので,表を作るプロセスはこれで終了です.
13.
この表をもとに,$x,y$を具体的に決定します.この表を眺めると,xは1を2に,2を3に,3を1に移していて,yは1は1のままだが,2を3に,3を2に移しています.
このことから,$\mathbf{x=(1 \ 2 \ 3), \ y=(2 \ 3)}$とします.ただもしこの言い方が気に入らなければ,これは厳密に言うと,$D_{3}$の$H=\langle y\rangle$による右剰余類全体の集合への作用を考えているのですが,今Todd-Coxeter Algorithmを実行した結果,右剰余類が$H,Hx,Hxx$の3つで尽くされる(例えば他に$Hxy$などもあるがそれは$Hxx$と等しい,ということが$4=3$の意味です)ことが分かりました.なので,この作用は置換表現$\rho:D_{3}\longrightarrow\mathfrak{S}_{3}$を定めます.そして今$\rho(x)=(1 \ 2 \ 3), \ \rho(y)=(2 \ 3)$が分かっていますから,$\rho$は準同型なので$\rho$を省略して$x=(1 \ 2 \ 3), \ y=(2 \ 3)$と書いても演算結果は双方で一致するということです.これによって,x,yを具体的な$\mathfrak{S}_{3}$の元として求めることができたので,Todd-Coxeter Algorithmは終了です.
14.
結局,$D_{3}$という群について何が言えるかということについて解説します.今,Todd-Coxeter Algorithmの結果として,$D_{3}$から$x=(1 \ 2 \ 3), \ y=(2 \ 3)$で生成される$\mathfrak{S}_{3}$の部分群への全射準同型$\rho$が存在することが言えます($\rho$は置換表現なので準同型,また生成元を生成元に移しているので全射だから).しかし,$\mathfrak{S}_{3}$は$x=(1 \ 2 \ 3), \ y=(2 \ 3)$で生成されるので,位数の比較(どちらも6)により結局,$\underline{D_{3}\cong\mathfrak{S}_{3}}$が結論されます.Todd-Coxeter Algorithmの威力が分かってもらえたでしょうか？
色々な例
ここでは色々な自由群の例に対して,表は最終的なものを提示するだけにします.
$D_{3}$で$H=\langle x\rangle$とした場合
| x x x | y y | x y x y |
|---|---|---|
| 1 1 1 1 | 1 2 1 | 1 1 2 2 1 |
| 2 2 2 2 | 2 1 2 | 2 2 1 1 2 |
これより$x=1, \ y=(1 \ 2)$となり,さっきの結果に対して,これでは$D_{3}$から$\mathfrak{S}_{2}$への(同型ではない)全射準同型が存在する,ということまでしかわかりません.この例から分かることとして,最初の巡回部分群の取り方はまあまあ重要です.Todd-Coxeter Algorithmの結果,今のようなつまらない結論しか出てこなかった場合,巡回部分群$H$を取り換えてみるとより詳しいことが分かるかもしれません.
$\mathbb{Z}/4\mathbb{Z}$
$\mathbb{Z}/4\mathbb{Z}$を背景に,
$4\cdot\overline{1}=2\cdot\overline{2}
=\overline{1}+\overline{2}+\overline{1}=\overline{0}$
であることから,$x=\overline{1},y=\overline{2}$と考えて,
$$
G=\langle x,y \ | \ x^{4}=y^{2}=xyx=1\rangle
$$
という自由群を作ってみたとき,これは本当に$\mathbb{Z}/4\mathbb{Z}$と一致するだろうかということを考えてみます.$H=\langle x\rangle$としてTodd-Coxeter Algorithmを実行すると,
| x x x x | y y | x y x |
|---|---|---|
| 1 1 1 1 1 | 1 1 1 | 1 1 1 1 |
という表が得られます.実行していると1行目で$2=1$となって全部1になることが分かると思います.これはどういうことを意味するかというと,今$1=H=Hx=Hy$であるのだから$G$の任意の元$x^{i}y^{j}$(関係式から任意の元がこう表されると分かります)に対して$Hx^{i}y^{j}=H$,すなわち$G$の任意の元$g$は$g\in H$ということです.つまり$G\subset H$なので$H=G$ということになります.今,$H=\langle x\rangle$は位数4の巡回群ですから,結局$G=H=\mathbb{Z}/4\mathbb{Z}$が結論されます.関係式に可換性の条件$xy=yx$を陽に挿入していないのに,$G$が可換であることも含めて分かってしまうところは,面白いと思います.$H=\langle y\rangle$の場合を考えてみるとどうでしょうか?
$A_{4}$
$G=\langle x,y \ | \ x^{3}=y^{3}=xyxy=1\rangle$という自由群を考えてみます.$H=\langle x\rangle$としてTodd-Coxeter Algorithmを実行します.
| x x x | y y y | x y x y |
|---|---|---|
| 1 1 1 1 | 1 2 3 1 | 1 1 2 3 1 |
| 2 3 4 2 | 2 3 1 2 | 2 3 1 1 2 |
| 3 4 2 3 | 3 1 2 3 | 3 4 4 2 3 |
| 4 2 3 4 | 4 4 4 4 | 4 2 3 4 4 |
結果として,$x=(2 \ 3 \ 4), \ y=(1 \ 2 \ 3)$を得ます.ここで,$x,y$は$\mathfrak{S}_{4}$の長さ3の巡回置換を全て生成し(証明は略),$A_{4}$は$\mathfrak{S}_{4}$の長さ3の巡回置換によって生成されることを考えると,$A_{4}\subset G\subset \mathfrak{S}_{4}$が分かります.さらに$G$の生成元$x,y$のsgn(置換の符号)は全て1なので,$G$の任意の元のsgnは1です.$A_{4}$は$\mathfrak{S}_{4}$のsgnが1の元を全て集めたものだったから,$G\subset A_{4}$が分かります.以上より$G=A_{4}$です.