Un insieme dato di elementi di gruppo è un insieme di rappresentanti di coset?

Question

Ho paura che la domanda sia un po 'tecnica, ma spero che qualcuno possa essersi imbattuto in un argomento simile, o darmi un puntatore di qualche tipo.

Se G è un gruppo (nel senso di struttura algebrica), e se g , ..., g _n sono elementi di G, esiste un algoritmo (o una funzione in qualche programma dedicato , come GAP) per determinare se esiste un sottogruppo di G tale che tali elementi formino un insieme di rappresentanti per i coseti del sottogruppo? (Possiamo supporre che G sia un gruppo di permutazione e probabilmente anche il gruppo simmetrico completo.)

(Esistono naturalmente diversi algoritmi per trovare i coseti di un determinato sottogruppo, come l'algoritmo Todd-Coxeter, questo è un tipo di domanda inversa.)

Grazie, Daniele

Answer 1

L'unica soluzione che posso venire con è ingenuo. Fondamentalmente se si hanno gli elementi x1,...,xn, si utilizza GAP LowIndexSubgroupsFpGroup per enumerare tutti i sottogruppi con l'indice n (scartando quelli con indice < n). Quindi passerai attraverso ciascun gruppo, genererai i coseti e controllerai che ogni coset contiene uno degli elementi.

Questo è tutto quello che potevo pensare. Sarei molto interessato se ti venisse in mente un approccio migliore.

Answer 2

Un approccio leggermente meno bruta sarebbe enumerare tutti i sottogruppi di indice n, come suggerito Il-Bhima, e quindi per ciascun sottogruppo, controllare ogni x _i * x _j ^-1 per vedere se è contenuto nel sottogruppo.

Gli elementi x1, ..., xn sarà rappresentanti per un sottogruppo se e solo se ogni prodotto

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

NON è nel sottogruppo.

Questo tipo di controllo sembra sia più semplice che generare tutti i coseti e più rapidamente dal punto di vista computazionale.

Answer 3

cosa si sta cercando di stabilire è se c'è un sottogruppo H di G tale che {g , ..., g _n} è una transversal dei cosets di H. vale a dire un insieme di rappresentanti del partizionamento di G dai coseti di H.

Primo, dal teorema Lagrange's, | G | = | G: H | * | G |, dove | G: H | = | G |/| H | è l'indice del sottogruppo H di G. Se {g , ..., g _n} è effettivamente un trasversale, quindi | G: H | = | {g , ..., g _n} |, quindi il primo test nell'algoritmo deve essere se n divide | G |.

Inoltre, poiché g _i e g _j sono nella stessa classe laterale destra solo se g _i g _j^-1 è in H, si può quindi controllare sottogruppi con indice n vedere se evitano g _i g _{j ^-1. Si noti inoltre che (g i g j^-1) (g j g k^-1) = g i g k^-1, in modo da poter scegliere qualsiasi abbinamento della g i s.}

Questo dovrebbe essere sufficiente se n è piccolo rispetto a | G |.

Un altro approccio è quello di iniziare con H essendo il gruppo banale e aggiungere elementi dell'insieme H ^* = {h in G: h ^{k = g} _i g _j^-1, per tutti i, j, k; i! = j} ai generatori di H fino a quando non puoi aggiungere altro (cioè finché non è più un sottogruppo). H è quindi un sottogruppo massimale di G tale che H è un sottoinsieme di H ^*. Se riesci a ottenere tutti questi H (e averli abbastanza grandi), il sottogruppo che stai cercando deve essere uno di questi.

Questo approccio funzionerebbe meglio per i più grandi n.

In entrambi i casi un approccio non esponenziale nel tempo non è ovvio.

EDIT: Ho appena trovato una discussione su questo argomento molto qui: mi 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