Un ensemble donné d'éléments de groupe est-il un ensemble de représentants de coset?

Question

Je crains que la question ne soit un peu technique, mais j'espère que quelqu'un a trébuché sur un sujet similaire, ou me donner un indice quelconque.

Si G est un groupe (dans le sens de la structure algébrique), et si g , ..., g n sont des éléments de G, est-il un algorithme (ou une fonction dans un certain programme dédié , comme GAP) pour déterminer s'il existe un sous-groupe de G tel que ces éléments forment un ensemble de représentants pour les classes du sous-groupe? (On peut supposer que G est un groupe de permutation, et probablement même le groupe symétrique complet.)

(Il y a bien sûr plusieurs algorithmes pour trouver les classes d'un sous-groupe donné, comme l'algorithme de Todd-Coxeter; la question inverse.)

Merci, Daniele

Answer 1

La seule solution que je peux trouver est naïf. Fondamentalement, si vous avez des éléments x1,...,xn, vous utiliserez les LowIndexSubgroupsFpGroup de GAP pour énumérer tous les sous-groupes avec l'indice n (rejetant ceux avec l'index < n). Ensuite, vous passerez en revue chaque groupe, génèrerez les cosets et vérifierez que chaque coset contient l'un des éléments.

C'est tout ce que je pouvais penser. Je serais très intéressé si vous aviez une meilleure approche.

Answer 2

Une approche légèrement moins brutale serait d'énumérer tous les sous-groupes d'indice n, comme le suggère Il-Bhima, puis pour chaque sous-groupe, vérifier chaque x i * x _j ^-1 pour voir si elle est contenu dans le sous-groupe.

Les éléments x1, ..., xn aura des représentants pour un sous-groupe si et seulement si chaque produit

x _i * x _j ^-1 où (i! = J)

n'est pas dans le sous-groupe.

Ce type de vérification semble à la fois plus simple que de générer tous les compartiments et plus rapide en termes de calculs.

Answer 3

Qu'est-ce que vous essayez de déterminer est de savoir s'il y a un sous-groupe H de G tel que {g , ..., g _n} est un transversal des cosets de H. dire un ensemble de Représentation de la partition de G par les classes de H.

D'abord, par Lagrange's théorème, | G | = | G: H | * | G |, où | G: H | = | G |/| H | est l'indice du sous-groupe H de G. Si {g , ..., g _n} est en effet un transversal, alors | G: H | = | {g , ..., g _n}, donc le premier test dans votre algorithme devrait être si n divise | G |.

De plus, puisque g _i et g _j sont dans le même droit coset que si g _i g _j^-1 est dans H, vous pouvez alors vérifier les sous-groupes d'indice n pour voir s'ils évitent g _i g _j^-1. En outre, notez que (g _i g _j^-1) (g _j g _k^-1) = g _i g _k^-1, de sorte que vous pouvez choisir tout appariement du g _i s.

Ceci devrait être suffisant si n est petit comparé à | G |.

Une autre approche est de commencer avec H étant le groupe trivial et ajouter des éléments de l'ensemble H ^* = {h en G: h k = g i g _j^-1, pour tout, je, j, k; i! = j} aux générateurs de H jusqu'à ce que vous ne puissiez plus en ajouter (c'est-à-dire jusqu'à ce que ce ne soit plus un sous-groupe). H est alors un sous-groupe maximal de G tel que H est un sous-ensemble de H ^*. Si vous pouvez obtenir tous ces H (et les avoir assez grands) alors le sous-groupe que vous recherchez doit être l'un d'entre eux.

Cette approche fonctionnerait mieux pour un n plus grand.

Dans les deux cas, une approche non exponentielle n'est pas évidente.

EDIT: Je viens de trouver une discussion sur ce même sujet ici: 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