Todd–Coxeterのアルゴリズム(Todd–Coxeter algorithm)とは、有限表示された群 $G$ と語で与えられた部分群 $H$ から、右剰余類の全体と $G$ の作用を表にして数え上げる手順である。関係子と $H$ の生成元が課す等式を表に書き込み、同じ剰余類についた番号を併合していき、表が完成すれば点の個数は指数 $[G:H]$ に等しく、置換表現も得られる。指数が有限なら公平な手順は有限回で止まり、指数が無限なら止まらない。$H=\{1\}$ とすれば、止まったときの点の個数が $G$ の位数である。
Todd–Coxeterのアルゴリズム(Todd–Coxeter algorithm、coset enumeration)は、有限表示 $G=\langle X\mid R\rangle$ と、語で与えられた部分群 $H$ から、右剰余類 $Hg$ の全体とその上の $G$ の作用を表にして数え上げる手順である。1936 年に Todd と Coxeter が与えた(TC36、BC76 p. 73)。
群を生成元と関係子で書くと、その位数さえ一目では分からない。この手順は、名前のついていない剰余類に番号を振り、関係子と $H$ の生成元が課す等式を表に書き込み、同じ剰余類に 2 つの番号がついていると分かれば併合する、という作業を繰り返す。表が閉じれば、指数 $[G:H]$ と置換表現が同時に得られる。指数が有限なら、公平に作業を進めるかぎり必ず止まる。
| 結果 | 内容 |
|---|---|
| thm-tc-complete | 完成した健全な表の点は $H\backslash G$ と 1 対 1 に対応する。止まったときの答えはつねに正しい |
| thm-tc-termination | $[G:H]< \infty$ なら、公平な手順は有限回で止まる。無限指数なら止まらない |
| cor-tc-applications | 指数・置換表現・$H$ への所属の判定 |
$G=F/\langle\langle R\rangle\rangle$ を、有限集合 $X$ 上の自由群 $F$ の商、$R\subset F$ を有限集合とする(群の表示)。$S$ を語の有限集合とし、$H\subset G$ を $S$ の像で生成される部分群とする。$A=X\sqcup X^{-1}$ を文字の集合とし、$H\backslash G=\{Hg\}$ に $G$ を右からの積で作用させる。
剰余類表とは、正の整数の有限集合 $\Omega\ni 1$(元を点という)と、部分写像 $\Omega\times A\to\Omega$、$(\omega,a)\mapsto\omega\cdot a$ の組で、
$$
\omega\cdot a=\omega'\iff\omega'\cdot a^{-1}=\omega
$$
を満たすものである。語 $w=a_1\cdots a_m$ について $\omega\cdot w$ は左から順に適用した結果で、途中で未定義なら未定義とする。$\omega\cdot w=\omega$ のとき、$w$ は $\omega$ で閉じるという。
点は剰余類につけた仮の番号である。別の番号が同じ剰余類を指していてもよい。
剰余類表について、次のように定める。
連結な表では、$\varphi$ はあれば $\varphi(1\cdot w)=Hw$ で決まる。健全性は「番号の付け方が本当の剰余類と矛盾しない」という条件で、これを外すと完成の判定は意味を失う(ex-tc-unsound)。
始めの表は $\Omega=\{1\}$ で、何も定義しない。次の操作を繰り返す。
| 状況 | すること |
|---|---|
| $i=j$、$\alpha=\beta$ | $w$ は $\omega$ で閉じている |
| $i=j$、$\alpha\ne\beta$ | $\alpha,\beta$ を併合する($\varphi(\alpha)=\varphi(\beta)$) |
| $j=i+1$ | $\alpha\cdot a_j=\beta$ を記入する |
| $j\ge i+2$ | $\alpha\cdot a_{i+1}$ を定義して走査を続ける |
上の操作は連結性と健全性を保つ。併合の前後の表を $\pi\colon\Omega\to\Omega'$(各点を類の代表へ送る写像)で結ぶと、$\omega\cdot a=\omega'$ なら $\pi(\omega)\cdot a=\pi(\omega')$ である。とくに、ある語がある点で閉じていれば、以後の表でも対応する点で閉じている。点 $1$ は消えない。
定義については、$\varphi(\omega')=\varphi(\omega)a$ と延ばせばよい。新しい点は $1\cdot wa$ の形なので連結である。記入については $\varphi$ を変えずに関係が成り立つ。走査による記入の正しさは、上の式 $\varphi(\alpha)a_j=\varphi(\beta)$ による。
併合については、$\varphi$ が同値類の上で一定であることを示す。生成元の組 $(\omega,\omega')$ で等しく、$\varphi(u)=\varphi(u')$ なら $\varphi(u\cdot a)=\varphi(u)a=\varphi(u')a=\varphi(u'\cdot a)$ だからである。規則により、商の上で $u\cdot a$ は一意で、$\omega\cdot a=\omega'\iff\omega'\cdot a^{-1}=\omega$ も保たれる。経路は $\pi$ で経路に移るので、連結性と閉じていることは保たれる。$1$ は最小の番号なので代表として残る。$\square$
連結かつ健全で完成した剰余類表について、$\varphi\colon\Omega\to H\backslash G$ は $G$ の作用と両立する全単射である。とくに $\lvert\Omega\rvert=[G:H]$ であり、各 $x\in X$ を点の置換 $\omega\mapsto\omega\cdot x$ に送る写像は、$H\backslash G$ への $G$ の置換表現を与える。
完成しているので、各 $x\in X$ は $\Omega$ の全単射を与え(逆写像は $x^{-1}$ の列)、自由群 $F$ が $\Omega$ に右から作用する。各 $r\in R$ はすべての点を固定するので、その正規閉包も自明に作用する($\omega\cdot(grg^{-1})=((\omega\cdot g)\cdot r)\cdot g^{-1}=\omega$)。よって $G$ が $\Omega$ に作用する。$s\in S$ は点 $1$ を固定するので、$H$ は点 $1$ を固定する。
健全性により $\varphi(\omega\cdot g)=\varphi(\omega)g$($g\in G$)である。全射性:$\varphi(1\cdot g)=Hg$ なので、すべての剰余類が像に入る。単射性:連結性により 2 点は $1\cdot g$、$1\cdot g'$ と書ける。$Hg=Hg'$ なら $g'=hg$($h\in H$)で、$1\cdot g'=(1\cdot h)\cdot g=1\cdot g$ である。$\square$
$G=\langle a\mid\ \rangle\cong\mathbb{Z}$、$H=\{1\}$ とする。$\Omega=\{1\}$、$1\cdot a=1$ の表は連結で、完成の条件をすべて満たす(関係子も $S$ の語もない)。しかし $[G:H]=\infty$ である。$\varphi(1)=H$ と $\varphi(1\cdot a)=Ha$ が両立しないので、この表は健全でない。3 つの操作だけで作った表は lem-tc-invariant によりつねに健全なので、このような表は現れない。
公平な手順とは、操作の列であって、完成した表に達したときにかつそのときに限って止まり、止まらないなら次を満たすものをいう:永久に残る点 $\omega$ と $a\in A$、$r\in R$ について、$\omega\cdot a$ はいつか定義され、$r$ はいつか $\omega$ で閉じる。また $s\in S$ はいつか点 $1$ で閉じる。
たとえば次の手順は公平である。まず $S$ の語を点 $1$ に走査で閉じる。次に点の番号の小さい順に、生きている点 $\omega$ について、すべての $r\in R$ を走査で閉じ、未定義の $\omega\cdot a$ をすべて定義する。1 回の走査は有限回の操作で終わり、番号の小さい順に見ていくので、永久に残る点には必ず順番が来る。閉じたことは lem-tc-invariant により保たれる。
公平な手順について、次が成り立つ。
1 は lem-tc-invariant と thm-tc-complete による。2 を示す。手順が止まらないと仮定する。永久に残る点の集合を $\Omega_\infty$ とする($1\in\Omega_\infty$)。
極限の表. $\omega\in\Omega_\infty$、$a\in A$ について、公平性により $\omega\cdot a$ はいつか定義される。以後この値は、併合で最小の番号の代表へ替わるときにだけ変わり、そのつど番号は真に減るので、有限回で一定になる。一定になった値 $u$ の点が後で消えれば値が変わるので、$u\in\Omega_\infty$ である。この一定の値を改めて $\omega\cdot a$ とすれば、$\Omega_\infty$ の上にすべて定義された剰余類表を得る($\Omega_\infty$ が有限かはまだ分からないので、def-tc-table の有限の条件は外して考える)。lem-tc-invariant により、$r\in R$ は $\Omega_\infty$ の各点で、$s\in S$ は点 $1$ で、この表でも閉じる。
連結で健全. ある時刻の表で $\omega=1\cdot w$ とすると、以後の表でも $\omega=1\cdot w$ である。$w$ の経路に現れる有限個の値が一定になった時刻で見ると、極限の表でも $\omega=1\cdot w$ である。各時刻の $\varphi$ は $\varphi(1\cdot w)=Hw$ で決まるので、$\Omega_\infty$ の上で時刻によらず、極限の表の健全性を与える。
結論. thm-tc-complete の証明は $\Omega$ の有限性を使っていないので、$\Omega_\infty$ は $H\backslash G$ と 1 対 1 に対応し、$\lvert\Omega_\infty\rvert=[G:H]< \infty$ である。よって、極限の表の有限個のデータ(値と閉じていること)がすべて実現し一定になった時刻 $T$ がある。時刻 $T$ の表で $\Omega_\infty$ はすべての文字で閉じているので、連結性により点 $1$ から届く点は $\Omega_\infty$ の中にしかなく、生きている点は $\Omega_\infty$ だけである。したがって時刻 $T$ の表は完成しており、手順はそこで止まる。これは仮定に反する。$\square$
BC76 Theorem 3(p. 76)は別の見方をとり、固定した 1 つの手順について、$H$ の元を $S$ の語と関係子の共役の積に分解する見方で停止を示している。
途中の点の個数は指数を超えることがある(ex-tc-collapse)。BC76 p. 77 は、指数と、語の長さ・個数から、必要な点の個数の上界は得られないと注意している。この記事ではこの主張を証明しない。止まっていない途中の表だけからは、指数が無限だと結論できない。
$G=\langle a,b\mid a^2,\ b^3,\ (ab)^2\rangle$、$H=\langle a\rangle$ とする。
| 点 | $a$ | $b$ |
|---|---|---|
| $1$ | $1$ | $2$ |
| $2$ | $3$ | $3$ |
| $3$ | $2$ | $1$ |
$G=\langle a,b\mid a^2,\ b^3,\ (ab)^3\rangle$、$H=\langle b\rangle$ とする。同じ手順で次の表を得る($1\cdot b=1$、$1\cdot a=2$、$2\cdot a=1$ の後、$(ab)^3$ を点 $1$ で走査して $2\cdot b=3$、$3\cdot a=4$ を定義し $4\cdot b=2$ を記入する。さらに $b^3$ を点 $2$ で走査して $3\cdot b=4$、$a^2$ を点 $3$ で走査して $4\cdot a=3$ を得る)。
| 点 | $a$ | $b$ |
|---|---|---|
| $1$ | $2$ | $1$ |
| $2$ | $1$ | $3$ |
| $3$ | $4$ | $4$ |
| $4$ | $3$ | $2$ |
$[G:H]=4$、$\lvert H\rvert\le3$ より $\lvert G\rvert\le12$ である。置換 $a\mapsto(1\,2)(3\,4)$、$b\mapsto(2\,3\,4)$ は $A_4$ を生成するので、$G\cong A_4$ である。
$G=\langle a\mid a^4,\ a^6\rangle$、$H=\{1\}$ とする。$a^4$ を点 $1$ で走査すると $1\to2\to3\to4\to1$ となる。$a^6$ を点 $1$ で走査すると前向きに $1\to2\to3\to4\to1\to2\to3$ となり、結果の $3$ と出発点の $1$ が同じ剰余類を指す。$1,3$ を併合すると、$1\cdot a=2$、$3\cdot a=4$ から $2,4$ も併合され、$\Omega=\{1,2\}$ で完成する。$\lvert G\rvert=2$ である。途中で点は 4 個あった。
大きな例では、この差はさらに広がる。$\langle a,b\mid a^2,b^3,(ab)^5\rangle$、$H=\{1\}$ を上の公平な手順で数え上げると、位数 $60$ を得るまでに 82 個の点を定義した(関係子をこの順に走査したときの計算機による数値で、関係子や文字の順序によって変わる)。
手順が止まったとする。
1 は Lagrange の定理である。2:thm-tc-complete により、$1\cdot w=1$ は $\varphi(1\cdot w)=Hw=H$ と同値である。3:$g$ が表現の核に入ることは、すべての $k\in G$ で $Hkg=Hk$、すなわち $g\in k^{-1}Hk$ となることと同値である。$\square$
2 から、$G$ が有限群であることが分かっている有限表示については、$H=\{1\}$ の数え上げが語の問題を解く。一般の有限表示群の語の問題については 語の問題(群論) を見よ。
表を保ったまま、定義した点の代表の語を記録すれば、$H$ の表示が読み取れる。BC76 Theorem 4(p. 77)は、この追加の記録が $H$ の表示を与え、指数が有限なら有限な表示になることを述べる(この記事では証明しない)。
| 外す条件 | 反例 | 起きること |
|---|---|---|
| 有限指数(thm-tc-termination の 2) | $\langle a\mid\ \rangle$、$H=\{1\}$ | $1\cdot a^k$ が定義され続け、公平な手順は止まらない |
| 公平性(同) | $\langle a,b\mid b\rangle\cong\mathbb{Z}$、$H=\langle a\rangle$ | 指数は $1$ だが、$b$ を点 $1$ で走査せず $1\cdot b$、$(1\cdot b)\cdot b,\dots$ を定義し続ける列は止まらない |
| 健全性(thm-tc-complete) | ex-tc-unsound | 完成の条件を満たすのに点の個数は指数と異なる |
1 行目:停止すれば thm-tc-termination の 1 により指数は有限となるが、$[\mathbb{Z}:\{0\}]=\infty$ である。2 行目:$\varphi$ はどの点でも $H$ なので($H=G$)この列は健全で、定義の操作だけからなる。$a$ と $b$ を点 $1$ で走査すれば $1\cdot a=1$、$1\cdot b=1$ となり($1\cdot b$ を定義した後なら併合による)、すぐ止まる。公平性はこの走査がいつか行われることを要求している。3 行目は ex-tc-unsound のとおりである。
$G$ が無限群であることと手順が止まらないことは同じではない。2 行目の群は無限群だが、走査を行えば指数が有限なので止まる。
有限表示から位数を確かめる場面(cor-tc-applications の 1)と、有限指数の部分群の置換表現を作る場面(同 3)で使う。ex-tc-s3 と ex-tc-a4 のように、表の与える置換群と位数の上界を比べれば、与えられた表示が特定の有限群を定めることの証明になる。$G$ の有限性は仮定しないので、無限群の有限指数の部分群にも使える(ex-tc-table-check の 2 行目)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する