恐怕这个问题有点技术性，但我希望有人可能偶然发现了类似的主题，或者给我一些指示。
如果 G 是一个群（在代数结构的意义上），并且如果 g 1 , ..., g n是 G 的元素，是否有算法（或某些专用程序中的函数，如 GAP）来确定是否存在是 G 的一个子群，使得这些元素构成该子群陪集的一组代表？（我们可以假设 G 是一个置换群，甚至可能是完全对称群。）
（当然有几种算法可以找到给定子群的陪集，例如 Todd-Coxeter 算法；这是一种逆问题。）
谢谢，丹尼尔
问问题
881 次
3 回答
1
我能想出的唯一解决方案是幼稚的。基本上，如果您有元素x1,...,xn，您将使用 GAPLowIndexSubgroupsFpGroup来枚举索引为 n 的所有子组（丢弃索引 < n 的子组）。然后你会遍历每个这样的组，生成陪集，并检查每个陪集是否包含其中一个元素。
这就是我能想到的。如果您提出更好的方法，我会非常感兴趣。
于 2009-04-13T20:16:50.010 回答
1
您要确定的是是否存在 G 的子群 H 使得 {g 1 , ..., g n } 是H 的陪集的横向。即 G 的划分的一组代表H的陪集。
首先，根据拉格朗日定理，|G| = |G:H| * |G|，其中 |G:H| = |G|/|H| 是 G 的子群 H 的索引。如果 {g 1 , ..., g n } 确实是横向的，则 |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| 小，这就足够了。
另一种方法是从 H 作为平凡群开始并添加集合 H * = {h in G : h k != g i g j -1的元素，对于所有 i, j, k; i != j} 到 H 的生成器，直到你不能再添加（即直到它不再是子组）。H 是 G 的最大子群，使得 H 是 H *的子集。如果你能得到所有这样的 H（并且让它们足够大），那么你正在寻找的子组必须是其中之一。
这种方法对于较大的 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
于 2009-06-11T19:29:12.040 回答
0
正如 Il-Bhima 建议的那样，一种稍微不那么粗暴的方法是枚举索引 n 的所有子组，然后对于每个子组，检查每个 x i * x j -1以查看它是否包含在子组中。
元素 x1, ..., xn 将是子组的代表当且仅当每个产品
x i * x j -1其中 (i != j)
不在子组中。
这种类型的检查似乎比生成所有陪集更简单，并且计算速度更快。
于 2009-04-23T16:06:19.140 回答