トッド-コクセターの方法(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.

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

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$です. 以上の操作をもって, 表に次のように記入します.

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

6.

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

7.

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

8.

上の表をじっと眺めてみると, 真ん中では, 1は$y$によって1から来ていますが, 一方で, 右側では1が$y$によって5から来ています. このように, 同じ生成元によって,同じ数字が違う数字から来ている, または同じ数字が違う数字に行く場合, そこで異なっている数字は同じものとします. 今の場合, 同じ$y$という生成元によって1という数字が1と5の違う数字から来ているから, $1=5$とします.そして番号は若い方にそろえます. つまり5を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に移すことが分かっているので, 表は次のようになります.

10.

次に$y \ y$についても同じことをするのですが, 既にやった操作から, $y$は2を4に(右上参照)することが分かっていて(つまり$(Hy)y=Hyy=4$), また$2=Hy$に$y$を二回右からかけたもの$Hyyy$は$y^{2}=1$より$Hyyy=Hy=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$となるはずです. よって一旦表は次のようになります.

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

12.

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

今,出てきている数字は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=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を実行すると,

という表が得られます. 実行していると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=(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}$です.