トッド・コクセターアルゴリズム

群論において、1936年にJ.A.トッドとH.S.M.コクセターによって考案されたトッド・コクセターアルゴリズムは、剰余類列挙問題を解くためのアルゴリズムである。生成元と関係による群Gの表現と、 Gの部分群Hが与えられた場合、このアルゴリズムはG上のHの剰余類を列挙し、剰余類の空間（左乗算作用によって与えられる）上でのGの置換表現を記述する。群Gの位数が比較的小さく、部分群Hが単純であることがわかっている場合（例えば、巡回群など）、このアルゴリズムは手作業で実行でき、群Gの妥当な記述が得られる。コクセターとトッドは、このアルゴリズムを用いて、既知の群の生成元間の特定の関係体系が完全である、すなわち定義関係体系を構成することを示した。

トッド・コクセターアルゴリズムは無限群にも適用可能であり、群GにおけるHのインデックスが有限であれば、有限ステップで終了することが知られている。一方、群表示と部分群からなる一般的なペアの場合、その実行時間は部分群のインデックスと入力データのサイズに関する計算可能な関数によって制限されない。

アルゴリズムの実装例の一つは、次のように進む。${\displaystyle G=\langle X\mid R\rangle }$、 どこ${\displaystyle X}$はジェネレーターのセットであり、${\displaystyle R}$は関係の集合であり、で表す。${\displaystyle X'}$ジェネレーターのセット${\displaystyle X}$およびそれらの逆関数。${\displaystyle H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle }$どこで${\displaystyle h_{i}}$は、${\displaystyle X'}$使用されるテーブルには 3 種類あります。コセット テーブル、各リレーションに対するリレーション テーブル、${\displaystyle R}$、各ジェネレーターのサブグループテーブル${\displaystyle h_{i}}$の${\displaystyle H}$これらの表には情報が徐々に追加され、すべて記入されると、すべての剰余類が列挙され、アルゴリズムが終了します。

コセットテーブルは、生成子を乗算する際の既知のコセット間の関係を格納するために使用されます。このテーブルには、次のコセットを表す行があります。${\displaystyle H}$そして各要素の列${\displaystyle X'}$。 させて${\displaystyle C_{i}}$を剰余類表のi番目の行の剰余類とし、${\displaystyle g_{j}\in X'}$j番目の列の生成元を表す。 i行目、j列目の剰余類表のエントリは(既知の場合) kと定義され、ここでkは、${\displaystyle C_{k}=C_{i}g_{j}}$。

関係テーブルは、見つかった剰余類の一部が実際に同等であるかどうかを検出するために使用されます。関係ごとに 1 つの関係テーブルがあります。${\displaystyle R}$維持されています。${\displaystyle 1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$関係である${\displaystyle R}$、 どこ${\displaystyle g_{n_{i}}\in X'}$関係テーブルには、以下の剰余類を表す行があります。${\displaystyle H}$剰余類表のように。t列あり、 i行j列目のエントリは(既知の場合) kと定義される。${\displaystyle C_{k}=C_{i}g_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$特に、${\displaystyle (i,t)}$'番目のエントリは最初はiです。${\displaystyle g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1}$。

最後に、サブグループテーブルは関係テーブルと似ていますが、ジェネレーターの可能な関係を追跡します。${\displaystyle H}$各ジェネレーターについて${\displaystyle h_{n}=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$の${\displaystyle H}$、 と${\displaystyle g_{n_{i}}\in X'}$サブグループテーブルを作成します。このテーブルには、の剰余類に対応する行が1つだけあります。${\displaystyle H}$それ自体。t 列あり、j番目の列のエントリは(既知の場合) kと定義され、ここで${\displaystyle C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$特に、最後の項目はHです。${\displaystyle Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=Hh_{n}=H}$。

リレーションテーブルまたはサブグループテーブルの行が完成すると、新しい情報が追加されます。${\displaystyle C_{i}=C_{j}g}$、${\displaystyle g\in X'}$が見つかります。これは演繹と呼ばれます。この演繹から、関係表と部分群表の追加のエントリを埋めることができ、その結果、追加の演繹が可能になります。方程式に対応する剰余類表のエントリを埋めることができます。${\displaystyle C_{i}=C_{j}g}$そして${\displaystyle C_{j}=C_{i}g^{-1}}$。

しかし、剰余類表を埋める際、既に方程式のエントリが存在するものの、そのエントリの値が異なる場合があります。この場合、2つの剰余類が実際には同じ値であることが判明し、これは一致と呼ばれます。${\displaystyle C_{i}=C_{j}}$、 と${\displaystyle i<j}$テーブル内のjのすべてのインスタンスをiに置き換えます。次に、テーブルの考えられるすべてのエントリを埋めます。これにより、さらなる推論や一致が見つかる可能性があります。

すべての控除と一致の処理が完了した後、テーブルに空のエントリがある場合は、テーブルに新しい剰余類を追加してプロセスを繰り返します。剰余類を追加する際には、Hxが既知の剰余類である場合、すべての場合においてHxg がどこかの時点で追加されるようにします。${\displaystyle g\in X'}$（これは、アルゴリズムが特定の条件を満たした場合に終了することを保証するために必要です。）${\displaystyle |G:H|}$（有限である。）

すべてのテーブルが満たされると、アルゴリズムは終了します。これで、アクションに関する必要な情報がすべて揃います。${\displaystyle G}$剰余類について${\displaystyle H}$。

• コクセターグループ

• Todd, JA ; Coxeter, HSM (1936). "有限抽象群の剰余類を列挙する実際的な方法" . Proceedings of the Edinburgh Mathematical Society . Series II. 5 : 26– 34. doi : 10.1017/S0013091500008221 . JFM 62.1094.02 . Zbl 0015.10103 .  
• コクセター, HSM ;モーザー、WOJ (1980)。離散グループのジェネレータとリレーション。Ergebnisse der Mathematik および ihrer Grenzgebiete。 Vol.  14（第4 版）。Springer- Verlag 1980.ISBN 3-540-09212-9MR 0562913 .​ 
• Seress, Ákos (1997). 「計算群論入門」(PDF) .アメリカ数学会報. 44 (6): 671– 679. MR 1452069 .