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

はじめに

本記事ではトッド-コクセターの方法を解説します. トッド-コクセターの方法とは, 一言で言えば群論における生成元と関係式で与えられる群の生成元を$\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$に(右上参照)することが分かっていて, また$2=Hx$に$y$を二回右からかけたもの$Hxyy$は$y^{2}=1$より$Hxyy=Hx=2$なので, 結局表は次のようになります.

11.

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

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

12.

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

$y \ y$で$3$は$y$によって$5$からくるのに対して, $x \ y \ x \ y$では$3$は$y$によって$2$から来ています. なので$5=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$に移しています.
このことから, $x=(1 \ 2 \ 3), \ y=(2 \ 3)$とします. これは厳密にいうとTodd-Coxeter Algorithmは$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を実行すると

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