質問が少し技術的ではないかと思いますが、誰かが同様の主題に出くわしたり、何らかのポインタをくれたりすることを願っています.
G が (代数構造の意味で) 群であり、g 1 , ..., g nが G の元である場合、アルゴリズム (または GAP などの専用プログラムの関数) があるかどうかを判断します。は、これらの要素が部分群の剰余類の代表の集合を形成するような G の部分群ですか? (G は置換群であり、おそらく完全な対称群であると仮定することもできます。)
(もちろん、Todd-Coxeter アルゴリズムのように、特定のサブグループの剰余類を見つけるアルゴリズムはいくつかあります。これは一種の逆問題です。)
ありがとう、ダニエレ
あなたが決定しようとしているのは、{g 1 , ..., g n } がH の剰余類の横断であるような G のサブグループ H があるかどうかです。つまり、 H.の剰余類
まず、ラグランジュの定理 |G|により = |G:H| * |G|、ここで |G:H| = |G|/|H| {g 1 , ..., g n } が実際に横断型である場合、|G:H|は G の部分群 H のインデックスです。= |{g 1 , ..., g n }| なので、アルゴリズムの最初のテストは、n が |G| を除算するかどうかです。
さらに、 g i g j -1が H にある場合にのみ、g iと g jが同じ右剰余類にあるため、インデックス n のサブグループをチェックして、それらが g i g j -1を回避するかどうかを確認できます。また、(g i g j -1 )(g j g k -1 ) = g i g k -1であるため、g iの任意の組み合わせを選択できることに注意してください。
n が |G| に比べて小さい場合、これで十分です。
もう 1 つのアプローチは、H を自明群として開始し、集合 H * = {h in G : h k != g i g j -1、すべての i、j、k の要素を追加することです。i != j} を H のジェネレーターに、これ以上追加できなくなるまで (つまり、サブグループでなくなるまで) 追加します。次に、H は、H が H *のサブセットであるような G の最大サブグループです。そのような H をすべて取得できる (そしてそれらが十分に大きい) 場合、探しているサブグループはそれらの 1 つに違いありません。
このアプローチは、n が大きいほどうまく機能します。
いずれにせよ、非指数時間アプローチは明らかではありません。
編集:このトピックに関する議論をここで見つけました: http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2009_April_18#Is_a_given_set_of_group_elements_a_set_of_coset_representatives.3F
Il-Bhimaが提案したように、インデックスnのすべてのサブグループを列挙し、各サブグループについて、各 x i * x j -1をチェックして、それがサブグループに含まれているかどうかを確認します。
要素 x1、...、xn がサブグループの代表となるのは、すべての製品が
x i * x j -1ここで (i != j)
サブグループに属していません。
このタイプのチェックは、すべての剰余類を生成するよりも単純であり、計算も高速です。