8
大学数学基礎解説
文献あり

トッド-コクセターの方法(Todd-Coxeter Algorithm)について

929
0

はじめに

本記事ではトッド-コクセターの方法を解説します. トッド-コクセターの方法とは, 一言で言えば群論における生成元と関係式で与えられる群の生成元をSnの元として具体的に決定するための表を用いた手続きのことです. つまり同じ関係式を満たすSnの元を求める行為です. この方法によって原理的にはいかなる有限の生成元と関係式で与えられた群もSnの部分群として決定できます.

最後の方には個人的に難しくなくかつ面白いと思った例を挙げようと思います.

ちなみに, 参考文献のArtin "Algebra"では「トッド-コクセターの方法」は"Todd-Coxeter Algorithm"と表記されています. 個人的にはどちらかというとTodd-Coxeter Algorithmの方が好みなので, 以下「トッド-コクセターの方法」は"Todd-Coxeter Algorithm"と表記することにします.

ここでは生成元と関係式で与えられる群についての群論的な解説は省略します.

Todd-Coxeter Algorithmの解説

一般的な方法を述べるだけでは分かりにくいので, 二面体群
D3=x,y | x3=y2=1, yxy1=x1
を例にとって実際に実行しながら解説することにします.

1.

関係式を全て=1の形に整理します. このとき1乗の形は使わないようにします.
x3=y2=xyxy=1  (y1=y)

2.

その関係式の左辺の積を構成する元を左から表の上部に書きます. このとき累乗の形は使わないようにします.

x x xy yx y x y

3.

生成元を1つ選び, それが生成する巡回部分群を作ります. これをHとおきます. ここではH=yとします. (後でここでH=xとした場合と比較してみたいと思います.)

4.

Hに対して右から表上部に書いた元を順番にかけていきます. 例えば表左上部のx x xだと以下のようになります.
H, Hx, Hxx, Hxxx

5.

4の操作によってできたものをそれぞれ右剰余類とみなします.便宜的にH1と書きます.そして上でできた右剰余類を左から順に比較し, それまでに見た剰余類と今注目している剰余類が異なれば新しい数字をふります. まずHxH=1と異なる剰余類であるから, Hx2と書きます. 次にHxxH=1, Hx=2と異なる剰余類であるから, Hxx3と書きます. 最後にHxxxですが, xxx=x3=1よりHxxx=HなのでHxxx=1です. 以上の操作をもって表に次のように記入します.

x x xy yx y x y
1 2 3 1

流れとしては表に書いてある文字を左から順にHの右にかけていって, 違う剰余類が出てきたら新しい数字, 同じものが出てきたら同じ数字を記入, ということになります.

6.

5でxでやったことを他の関係式についても繰り返します. 次にyでやってみると, H=yだったので, Hy=H,Hyy=Hです. つまりH=Hy=Hyy=1です. よって表には次のように記入することになります.

x x xy yx y x y
1 2 3 11 1 1

7.

次にx y x yについてやっていくのですが, まずHxは既に2だと分かっているからそれをそのまま流用します. 次にHxyはこれまでのどの右剰余類とも異なるから新たにHxy=4とします. Hxyxも同じ理由からHxyx=5とします. 最後にxyxy=1よりHxyxy=H=1です. 従って表は以下のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 4 5 1

8.

上の表をじっと眺めてみると, 真ん中では1yによって1から来ていますが, 一方で右側では1yによって5から来ています. このように, 同じ生成元によって同じ数字が違う数字から来ている, または同じ生成元によって同じ数字が違う数字に行く場合そこで異なっている数字は同じものとします. 今の場合, 同じyという生成元によって115の違う数字から来ているから, 1=5とします.そして番号は若い方にそろえます. つまり51に変更します.

x x xy yx y x y
1 2 3 11 1 11 2 4 1 1

これを群論的に解釈すると, 最終的にはHxyxy=Hとなることが分かったので, これに右からy1をかける(つまり1つ戻る)とHxyx=Hなので5=Hxyx=H=1, ということです.

9.

さっきはH=1を最初の基準として, どんどん操作を加えていきました. これは表の各関係式の両端が1から始まり1で終わるということに対応しています. 現時点で,数字は1,2,3,4が出てきているので, 次は2を基準にして同じ操作を繰り返します. 最初にx x xでやってみるとこれは既に行った操作から, x12に, 23に, 31に移すことが分かっているので表は次のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 4 1 1
2 3 1 2

10.

次にy yについても同じことをするのですが, 既にやった操作からy24に(右上参照)することが分かっていて, また2=Hxyを二回右からかけたものHxyyy2=1よりHxyy=Hx=2なので, 結局表は次のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 4 1 1
2 3 1 22 4 2

11.

x y x yについても同じことをします. 今x23にすることが分かっていますが, y3を何にするかは未知ですから, y35にするとします(さっき5=1だったことは気にせず, あくまで新たな数字として5を使います). 同様に, x5を何にするかは未知ですのでまた新しく6とします. 最後のy6を何にするかですが, これは一周してHx(xyxy)=Hx=2となるはずです. よって一旦表は次のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 4 1 1
2 3 1 22 4 22 3 5 6 2

しかし真ん中のy yに注目すると, 2yによって4からくるはずなので6=4です. よって表は訂正されて次のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 4 1 1
2 3 1 22 4 22 3 5 4 2

12.

このプロセスは出てきた数字を全て基準とするまで続けます. 逆に言うと, このプロセスは出てきた数字が全て基準となり, かつこれ以上新しい数字が出てこなくなったら終了します. 従って次は3を基準にします. このときの表は一旦次のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 4 1 1
2 3 1 22 4 22 3 5 4 2
3 1 2 33 5 33 1 1 2 3

y y3yによって5からくるのに対して, x y x yでは3yによって2から来ています. なので5=2です. このとき二段目の5も訂正され2になるのですが, この5(=2)xによって4に行きます. 一方最初に2xによって3に行くことが分かっているので4=3です. これによって表は次のようになります.

x x xy yx y x y
1 2 3 11 1 11 2 3 1 1
2 3 1 22 3 22 3 2 3 2
3 1 2 33 2 33 1 1 2 3

今出てきている数字は1,2,3であり, それらすべてが既に基準となっている(新しい数字が出てきていない)ので表を作るプロセスはこれで終了です.

13.

この表をもとにx,yを具体的に決定します. この表を眺めるとx12に, 23に, 31に移していて, y11のままだが, 23に, 32に移しています.
このことから, x=(1 2 3), y=(2 3)とします. これは厳密にいうとTodd-Coxeter AlgorithmはD3H=yによる右剰余類全体の集合への作用を考えているのですが, 今Todd-Coxeter Algorithmを実行した結果右剰余類がH,Hx,Hxxの3つで尽くされる(例えば他にHxyなどもあるがそれはHxxと等しい, ということが4=3の意味です)ことが分かりました. よってこの作用は置換表現ρ:D3S3を定めます. そして今ρ(x)=(1 2 3), ρ(y)=(2 3)が分かっていますから, ρは準同型なのでρを省略してx=(1 2 3), y=(2 3)と書いても演算結果は双方で一致するということです. これによってx, yを具体的なS3の元として求めることができたので, Todd-Coxeter Algorithmは終了です.

14.

結局D3という群について何が言えるかということについて解説します. 今Todd-Coxeter Algorithmの結果として, D3からx=(1 2 3), y=(2 3)で生成されるS3の部分群への全射準同型ρが存在することが言えます(ρは置換表現なので準同型, また生成元を生成元に移しているので全射だから). しかしS3x=(1 2 3), y=(2 3)で生成されるので, 位数の比較(どちらも6)により結局D3S3が結論されます. Todd-Coxeter Algorithmの威力が分かってもらえたでしょうか?

色々な例

ここでは色々な生成元と関係式で与えられる群の例に対して, 表は最終的なものを提示するだけにします.

D3H=xとした場合

x x xy yx y x y
1 1 1 11 2 11 1 2 2 1
2 2 2 22 1 22 2 1 1 2

これよりx=1, y=(1 2)となり, さっきの結果に対してこれではD3からS2への(同型ではない)全射準同型が存在するということまでしかわかりません. この例から分かることとして, 最初の巡回部分群の取り方はまあまあ重要です. Todd-Coxeter Algorithmの結果今のようなつまらない結論しか出てこなかった場合, 巡回部分群Hを取り換えてみるとより詳しいことが分かるかもしれません.

Z/4Z

Z/4Zを背景に,
41=22=1+2+1=0
であることから, x=1,y=2と考えて
G=x,y | x4=y2=xyx=1
という群を作ってみたときこれは本当にZ/4Zと一致するだろうかということを考えてみます. H=xとしてTodd-Coxeter Algorithmを実行すると

x x x xy yx y x
1 1 1 1 11 1 11 1 1 1

という表が得られます. 実行していると一行目で2=1となって全部1になることが分かると思います. これはどういうことを意味するかというと, 今1=H=Hx=HyであるのだからGの任意の元xiyj(関係式から任意の元がこう表されると分かります)に対してHxiyj=H, すなわちGの任意の元ggHということです. つまりGHなのでH=Gということになります. 今H=xは位数4の巡回群なので結局G=H=Z/4Zが結論されます. 関係式に可換性の条件xy=yxを陽に挿入していないのにGが可換であることも含めて分かってしまうところは面白いと思います. H=yの場合を考えてみるとどうでしょうか?

A4

G=x,y | x3=y3=xyxy=1という群を考えてみます. H=xとしてTodd-Coxeter Algorithmを実行します.

x x xy y yx y x y
1 1 1 11 2 3 11 1 2 3 1
2 3 4 22 3 1 22 3 1 1 2
3 4 2 33 1 2 33 4 4 2 3
4 2 3 44 4 4 44 2 3 4 4

結果としてx=(2 3 4), y=(1 2 3)を得ます. ここでx,yS4の長さ3の巡回置換を全て生成し(証明は略), A4S4の長さ3の巡回置換によって生成されることを考えるとA4GS4が分かります. さらにGの生成元x,yのsgn(置換の符号)は全て1なのでGの任意の元のsgnは1です. A4S4のsgnが1の元を全て集めたものだったからGA4が分かります. 以上よりG=A4です.

参考文献

[1]
雪江明彦, 代数学1 群論入門, 日本評論社, 2010
[2]
M.Artin, Algebra, second edition, Addison Wesley, 2010
投稿日:202266
更新日:20241212
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

瓦
10
1833

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. Todd-Coxeter Algorithmの解説
  3. 色々な例
  4. D3H=xとした場合
  5. Z/4Z
  6. A4
  7. 参考文献