Todd–Coxeterのアルゴリズム

同義語:Todd–Coxeter algorithmcoset enumeration

概要

Todd–Coxeterのアルゴリズム(Todd–Coxeter algorithm)とは、有限表示された群 $G$ と語で与えられた部分群 $H$ から、右剰余類の全体と $G$ の作用を表にして数え上げる手順である。関係子と $H$ の生成元が課す等式を表に書き込み、同じ剰余類についた番号を併合していき、表が完成すれば点の個数は指数 $[G:H]$ に等しく、置換表現も得られる。指数が有限なら公平な手順は有限回で止まり、指数が無限なら止まらない。$H=\{1\}$ とすれば、止まったときの点の個数が $G$ の位数である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 群の表示, 自由群, 剰余類, 群の作用

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$ で閉じるという。

点は剰余類につけた仮の番号である。別の番号が同じ剰余類を指していてもよい。

連結・健全・完成

剰余類表について、次のように定める。

  1. 連結:どの点も、ある語 $w$ で $1\cdot w$ と書ける。
  2. 健全:写像 $\varphi\colon\Omega\to H\backslash G$ で、$\varphi(1)=H$ かつ、$\omega\cdot a$ が定義されるとき $\varphi(\omega\cdot a)=\varphi(\omega)a$ となるものがある。
  3. 完成:すべての $\omega\cdot a$ が定義され、すべての $r\in R$ がすべての点で閉じ、すべての $s\in S$ が点 $1$ で閉じる。

連結な表では、$\varphi$ はあれば $\varphi(1\cdot w)=Hw$ で決まる。健全性は「番号の付け方が本当の剰余類と矛盾しない」という条件で、これを外すと完成の判定は意味を失う(ex-tc-unsound)。

3 つの操作

始めの表は $\Omega=\{1\}$ で、何も定義しない。次の操作を繰り返す。

  • 定義:$\omega\cdot a$ が未定義のとき、まだ使っていない最小の番号 $\omega'$ を点に加え、$\omega\cdot a=\omega'$ とする。
  • 記入:$\varphi(\omega)a=\varphi(\omega')$ が分かっていて、$\omega\cdot a$ と $\omega'\cdot a^{-1}$ がどちらも未定義のとき、$\omega\cdot a=\omega'$ とする。
  • 併合:$\varphi(\omega)=\varphi(\omega')$ が分かっている相異なる 2 点を同一視する。$u\sim u'$ で $u\cdot a$、$u'\cdot a$ がともに定義されるなら $u\cdot a\sim u'\cdot a$ とする、という規則で生成される最小の同値関係をとり、各類を最小の番号で代表させ、表を商に移す。
    等式を見つける手段が走査である。$r\in R$ と点 $\omega$、または $s\in S$ と点 $1$ の組 $(\omega,w)$ では、$G$ の中で $r=1$、$s\in H$ なので、健全な表の上で
    $$ \varphi(\omega)w=\varphi(\omega) $$
    が成り立つ。$w=a_1\cdots a_m$ を $\omega$ から前向きに、$\omega$ から $a_m^{-1},a_{m-1}^{-1},\dots$ で後ろ向きにたどり、定義された範囲を伸ばす。前向きに $a_1\cdots a_i$ まで、後ろ向きに $a_{j+1}\cdots a_m$ まで進み、到達点を $\alpha$、$\beta$ とすると、$\varphi(\alpha)a_{i+1}\cdots a_j=\varphi(\beta)$ である。
    状況すること
    $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. 手順が止まれば、そのときの表の点の個数は $[G:H]$ で、$[G:H]$ は有限である。
  2. $[G:H]$ が有限なら、手順は有限回で止まる。

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 は、指数と、語の長さ・個数から、必要な点の個数の上界は得られないと注意している。この記事ではこの主張を証明しない。止まっていない途中の表だけからは、指数が無限だと結論できない。

例

位数 6 の群の表示

$G=\langle a,b\mid a^2,\ b^3,\ (ab)^2\rangle$、$H=\langle a\rangle$ とする。

  1. $a\in S$ を点 $1$ で走査すると、前向き・後ろ向きとも進まず $j=i+1$ なので $1\cdot a=1$ を記入する。
  2. $b^3$ を点 $1$ で走査し、$1\cdot b=2$、$2\cdot b=3$ を定義すると、残り 1 文字なので $3\cdot b=1$ を記入する。
  3. $abab$ を点 $1$ で走査する。前向きに $1\xrightarrow{a}1\xrightarrow{b}2$、後ろ向きに最後の $b$ で $1\cdot b^{-1}=3$ となり、残り 1 文字なので $2\cdot a=3$ を記入する。
    点$a$$b$
    $1$$1$$2$
    $2$$3$$3$
    $3$$2$$1$
    どの関係子も全点で閉じる(たとえば $abab$ は $2\to3\to1\to1\to2$)ので、表は完成し、$[G:H]=3$ である。$\lvert H\rvert\le2$ より $\lvert G\rvert\le6$ である。一方、置換 $a\mapsto(2\,3)$、$b\mapsto(1\,2\,3)$ は $S_3$ を生成するので $\lvert G\rvert\ge6$ である。よって $G\cong S_3$ である。
位数 12 の群の表示

$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. $H$ が有限なら $\lvert G\rvert=[G:H]\lvert H\rvert$ である。とくに $H=\{1\}$ なら $\lvert G\rvert=\lvert\Omega\rvert$ である。
  2. 語 $w$ の表す元が $H$ に入ることと、$1\cdot w=1$ は同値である。
  3. 置換表現 $G\to\mathrm{Sym}(\Omega)$ の核は $\bigcap_{g\in G}g^{-1}Hg$ である。

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 行目)。

関連項目

参考文献

[1]
M. J. Beetham, C. M. Campbell, A note on the Todd-Coxeter coset enumeration algorithm, Proceedings of the Edinburgh Mathematical Society, 1976, 73–79(Theorem 3 p. 76、p. 77 の注意、Theorem 4 p. 77)
[2]
J. A. Todd, H. S. M. Coxeter, A practical method for enumerating cosets of a finite abstract group, Proceedings of the Edinburgh Mathematical Society, 1936, 26–34

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する