Is a given set of group elements a set of coset representatives?

Question

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 g₁, ..., g_n 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

Answer 1

The only solution I can come up with is naive. Basically if you have elements x1,...,xn, you would use GAP's LowIndexSubgroupsFpGroup to 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.

Answer 2

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 x_i * x_j^-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

x_i * x_j^-1 where (i != j)

is NOT in the subgroup.

This type of check seems both simpler than generating all cosets, and computationally faster.

Answer 3

What you're trying to determine is if there is a subgroup H of G such that {g₁, ..., g_n} 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 {g₁, ..., g_n} is indeed a transversal, then |G:H| = |{g₁, ..., g_n}|, so the first test in your algorithm should be whether n divides |G|.

Moreover, since g_i and g_j are in the same right coset only if g_ig_j^-1 is in H, you can then check subgroups with index n to see if they avoid g_ig_j^-1. Also, note that (g_ig_j^-1)(g_jg_k^-1) = g_ig_k^-1, so you can choose any pairing of the g_is.

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 : h^k != g_ig_j^-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