恐怕这个问题有点技术性，但我希望有人可能偶然发现了类似的主题，或者给我某种指示。
如果 G 是一个群（在代数结构的意义上），并且如果 g1, ..., gn 是 G 的元素，是否存在算法（或某些专用程序（例如 GAP）中的函数，用于确定 G 是否存在一个子群，使得这些元素形成该子群陪集的一组代表？ （我们可以假设 G 是一个置换群，甚至可能是完全对称群。）
（当然有几种算法可以找到给定子群的陪集，例如 Todd-Coxeter 算法；这是一种逆问题。 ）
谢谢，
丹尼尔
I am afraid the question is a bit technical, but I hope someone might have stumbled into a similar subject, or give me a pointer of some kind.
If G is a group (in the sense of algebraic structure), and if g1, ..., gn are elements of G, is there an algorithm (or a function in some dedicated program, like GAP) to determine whether there is a subgroup of G such that those elements form a set of representatives for the cosets of the subgroup? (We may assume that G is a permutation group, and probably even the full symmetric group.)
(There are of course several algorithms to find the cosets of a given subgroups, like Todd-Coxeter algorithm; this is a kind of inverse question.)
Thanks,
Daniele
发布评论
评论（3）
我能想到的唯一解决方案是天真的。 基本上，如果您有元素
x1,...,xn，您将使用 GAP 的LowIndexSubgroupsFpGroup枚举索引为 n 的所有子组（丢弃索引我能想到的就只有这些了。 如果您想出更好的方法，我会非常感兴趣。
The only solution I can come up with is naive. Basically if you have elements
x1,...,xn, you would use GAP'sLowIndexSubgroupsFpGroupto enumerate all subgroups with index n (discarding those with index < n). Then you would go through each such group, generate the cosets, and check that each coset contains one of the elements.This is all I could think of. I would be very interested if you came up with a better approach.
您想要确定的是 G 中是否存在一个子群 H，使得 {g1, ..., gn} 是 H 陪集的横向。即 G 通过 H 陪集划分的一组代表。
首先，通过拉格朗日定理，|G| = |G:H| * |G|，其中 |G:H| =|G|/|H| 是 G 的子群 H 的索引。如果 {g1, ..., gn} 确实是一个截群，则 |G:H| = |{g1, ..., gn}|，因此算法中的第一个测试应该是 n 是否整除 |G|。
此外，由于仅当 gigji 和 gj 位于同一右陪集中>-1 在 H 中，然后您可以检查索引为 n 的子组，看看它们是否避免 gigj-1。 另请注意 (gigj-1)(gjgk-1) = gigk-1，因此您可以选择 g 的任意配对我。
如果 n 与 |G| 相比较小，这应该足够了。
另一种方法是从平凡群 H 开始，添加集合 H* = {h in G : hk != gigj-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
What you're trying to determine is if there is a subgroup H of G such that {g1, ..., gn} is a transversal of the cosets of H. i.e. A set of representatives of the partitioning of G by the cosets of H.
First, by Lagrange's theorem, |G| = |G:H| * |G|, where |G:H| = |G|/|H| is the index of the subgroup H of G. If {g1, ..., gn} is indeed a transversal, then |G:H| = |{g1, ..., gn}|, so the first test in your algorithm should be whether n divides |G|.
Moreover, since gi and gj are in the same right coset only if gigj-1 is in H, you can then check subgroups with index n to see if they avoid gigj-1. Also, note that (gigj-1)(gjgk-1) = gigk-1, so you can choose any pairing of the gis.
This should be sufficient if n is small compared to |G|.
Another approach is to start with H being the trivial group and add elements of the set H* = {h in G : hk != gigj-1, for all i, j, k; i != j} to the generators of H until you can't add any more (i.e. until it's no longer a subgroup). H is then a maximal subgroup of G such that H is a subset of H*. If you can get all such H (and have them be large enough) then the subgroup you're looking for must be one of them.
This approach would work better for larger n.
Either way a non-exponential-time approach isn't obvious.
EDIT: I've just found a discussion of this very topic here: 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
一种不太粗暴的方法是枚举索引 n 的所有子组，如 Il-Bhima 建议的那样，然后对于每个子组，检查每个 xi * xj-1 查看它是否包含在子组中。
元素 x1, ..., xn 将代表子组当且仅当每个乘积
xi * xj-1 其中(i != j)
不在子组中。
这种类型的检查似乎比生成所有陪集更简单，而且计算速度更快。
A slightly less brute approach would be to enumerate all subgroups of index n, as Il-Bhima suggested, and then for each subgroup, check each xi * xj-1 to see if it is contained in the subgroup.
The elements x1, ..., xn will be representatives for a subgroup if and only if EVERY product
xi * xj-1 where (i != j)
is NOT in the subgroup.
This type of check seems both simpler than generating all cosets, and computationally faster.