はじめに
本記事ではトッド-コクセターの方法を解説します. トッド-コクセターの方法とは, 一言で言えば群論における生成元と関係式で与えられる群の生成元をの元として具体的に決定するための表を用いた手続きのことです. つまり同じ関係式を満たすの元を求める行為です. この方法によって原理的にはいかなる有限の生成元と関係式で与えられた群もの部分群として決定できます.
最後の方には個人的に難しくなくかつ面白いと思った例を挙げようと思います.
ちなみに, 参考文献のArtin "Algebra"では「トッド-コクセターの方法」は"Todd-Coxeter Algorithm"と表記されています. 個人的にはどちらかというとTodd-Coxeter Algorithmの方が好みなので, 以下「トッド-コクセターの方法」は"Todd-Coxeter Algorithm"と表記することにします.
ここでは生成元と関係式で与えられる群についての群論的な解説は省略します.
Todd-Coxeter Algorithmの解説
一般的な方法を述べるだけでは分かりにくいので, 二面体群
を例にとって実際に実行しながら解説することにします.
1.
関係式を全ての形に整理します. このとき乗の形は使わないようにします.
2.
その関係式の左辺の積を構成する元を左から表の上部に書きます. このとき累乗の形は使わないようにします.
3.
生成元を1つ選び, それが生成する巡回部分群を作ります. これをとおきます. ここではとします. (後でここでとした場合と比較してみたいと思います.)
4.
に対して右から表上部に書いた元を順番にかけていきます. 例えば表左上部のだと以下のようになります.
5.
4の操作によってできたものをそれぞれ右剰余類とみなします.便宜的にをと書きます.そして上でできた右剰余類を左から順に比較し, それまでに見た剰余類と今注目している剰余類が異なれば新しい数字をふります. まずはと異なる剰余類であるから, をと書きます. 次には, と異なる剰余類であるから, をと書きます. 最後にですが, よりなのでです. 以上の操作をもって表に次のように記入します.
流れとしては表に書いてある文字を左から順にの右にかけていって, 違う剰余類が出てきたら新しい数字, 同じものが出てきたら同じ数字を記入, ということになります.
6.
5ででやったことを他の関係式についても繰り返します. 次にでやってみると, だったので, です. つまりです. よって表には次のように記入することになります.
x x x | y y | x y x y |
1 2 3 1 | 1 1 1 | |
7.
次にについてやっていくのですが, まずは既にだと分かっているからそれをそのまま流用します. 次にはこれまでのどの右剰余類とも異なるから新たにとします. も同じ理由からとします. 最後によりです. 従って表は以下のようになります.
x x x | y y | x y x y |
1 2 3 1 | 1 1 1 | 1 2 4 5 1 |
8.
上の表をじっと眺めてみると, 真ん中でははによって1から来ていますが, 一方で右側ではがによってから来ています. このように, 同じ生成元によって同じ数字が違う数字から来ている, または同じ生成元によって同じ数字が違う数字に行く場合そこで異なっている数字は同じものとします. 今の場合, 同じという生成元によってがとの違う数字から来ているから, とします.そして番号は若い方にそろえます. つまりをに変更します.
x x x | y y | x y x y |
1 2 3 1 | 1 1 1 | 1 2 4 1 1 |
これを群論的に解釈すると, 最終的にはとなることが分かったので, これに右からをかける(つまり1つ戻る)となので, ということです.
9.
さっきはを最初の基準として, どんどん操作を加えていきました. これは表の各関係式の両端がから始まりで終わるということに対応しています. 現時点で,数字はが出てきているので, 次はを基準にして同じ操作を繰り返します. 最初にでやってみるとこれは既に行った操作から, はをに, をに, をに移すことが分かっているので表は次のようになります.
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.
次にについても同じことをするのですが, 既にやった操作からはをに(右上参照)することが分かっていて, またにを二回右からかけたものはよりなので, 結局表は次のようになります.
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 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 |
しかし真ん中のに注目すると, はによってからくるはずなのでです. よって表は訂正されて次のようになります.
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.
このプロセスは出てきた数字を全て基準とするまで続けます. 逆に言うと, このプロセスは出てきた数字が全て基準となり, かつこれ以上新しい数字が出てこなくなったら終了します. 従って次はを基準にします. このときの表は一旦次のようになります.
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 |
ではによってからくるのに対して, でははによってから来ています. なのでです. このとき二段目のも訂正されになるのですが, このはによってに行きます. 一方最初にはによってに行くことが分かっているのでです. これによって表は次のようになります.
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 |
今出てきている数字はであり, それらすべてが既に基準となっている(新しい数字が出てきていない)ので表を作るプロセスはこれで終了です.
13.
この表をもとにを具体的に決定します. この表を眺めるとはをに, をに, をに移していて, ははのままだが, をに, をに移しています.
このことから, とします. これは厳密にいうとTodd-Coxeter Algorithmはのによる右剰余類全体の集合への作用を考えているのですが, 今Todd-Coxeter Algorithmを実行した結果右剰余類がの3つで尽くされる(例えば他になどもあるがそれはと等しい, ということがの意味です)ことが分かりました. よってこの作用は置換表現を定めます. そして今が分かっていますから, は準同型なのでを省略してと書いても演算結果は双方で一致するということです. これによって, を具体的なの元として求めることができたので, Todd-Coxeter Algorithmは終了です.
14.
結局という群について何が言えるかということについて解説します. 今Todd-Coxeter Algorithmの結果として, からで生成されるの部分群への全射準同型が存在することが言えます(は置換表現なので準同型, また生成元を生成元に移しているので全射だから). しかしはで生成されるので, 位数の比較(どちらも)により結局が結論されます. Todd-Coxeter Algorithmの威力が分かってもらえたでしょうか?
色々な例
ここでは色々な生成元と関係式で与えられる群の例に対して, 表は最終的なものを提示するだけにします.
でとした場合
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 |
これよりとなり, さっきの結果に対してこれではからへの(同型ではない)全射準同型が存在するということまでしかわかりません. この例から分かることとして, 最初の巡回部分群の取り方はまあまあ重要です. Todd-Coxeter Algorithmの結果今のようなつまらない結論しか出てこなかった場合, 巡回部分群を取り換えてみるとより詳しいことが分かるかもしれません.
を背景に,
であることから, と考えて
という群を作ってみたときこれは本当にと一致するだろうかということを考えてみます. としてTodd-Coxeter Algorithmを実行すると
x x x x | y y | x y x |
1 1 1 1 1 | 1 1 1 | 1 1 1 1 |
という表が得られます. 実行していると一行目でとなって全部になることが分かると思います. これはどういうことを意味するかというと, 今であるのだからの任意の元(関係式から任意の元がこう表されると分かります)に対して, すなわちの任意の元はということです. つまりなのでということになります. 今は位数の巡回群なので結局が結論されます. 関係式に可換性の条件を陽に挿入していないのにが可換であることも含めて分かってしまうところは面白いと思います. の場合を考えてみるとどうでしょうか?
という群を考えてみます. として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 |
結果としてを得ます. ここではの長さの巡回置換を全て生成し(証明は略), はの長さの巡回置換によって生成されることを考えるとが分かります. さらにの生成元のsgn(置換の符号)は全てなのでの任意の元のsgnは1です. はのsgnが1の元を全て集めたものだったからが分かります. 以上よりです.