¿Es un conjunto dado de elementos de grupo un conjunto de representantes de coset?

Question

Me temo que la pregunta es un poco técnica, pero espero que alguien haya tropezado con un tema similar, o darme algún tipo de indicador.

Si G es un grupo (en el sentido de estructura algebraica), y si g , ..., g _n son elementos de G, hay un algoritmo (o una función en algún programa dedicado , como GAP) para determinar si hay un subgrupo de G tal que esos elementos forman un conjunto de representantes para los conjuntos del subgrupo. (Podemos suponer que G es un grupo de permutación, y probablemente incluso el grupo simétrico completo.)

(Por supuesto, hay varios algoritmos para encontrar las clases de un determinado subgrupo, como el algoritmo Todd-Coxeter; este es un tipo de la pregunta inversa.)

Gracias, Daniele

Answer 1

La única solución que puedo llegar a es ingenuo. Básicamente, si tiene los elementos x1,...,xn, debe usar GAP's LowIndexSubgroupsFpGroup para enumerar todos los subgrupos con índice n (descartando aquellos con índice < n). Luego examinaría cada uno de esos grupos, generaría los conjuntos y verificaría que cada coset contiene uno de los elementos.

Esto es todo lo que se me ocurrió. Me interesaría mucho si tuvieras un mejor enfoque.

Answer 2

un enfoque ligeramente menos bruta sería enumerar todos los subgrupos de índice n, como se sugiere Il-Bhima, y ​​luego para cada subgrupo, comprobar cada x _i * x _j ^-1 para ver si está contenido en el subgrupo.

La elementos x1, ..., xn habrá representantes para un subgrupo si y sólo si cada producto

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

NO está en el subgrupo.

Este tipo de verificación parece ser más simple que la generación de todos los conjuntos y más rápido desde el punto de vista computacional.

Answer 3

Lo que estamos tratando de determinar es si hay un subgrupo H de G tal que {g , ..., g _{n} es una}transversal de las clases laterales de H. es decir, un conjunto de representantes de la partición de G por los conjuntos de H.

Primero, por Lagrange's teorema, | G | = | G: H | * | G |, donde | G: H | = | G |/| H | es el índice del subgrupo H de G. Si {g , ..., g _n} es de hecho una transversal, entonces | G: H | = | {g , ..., g _n} |, por lo que la primera prueba en su algoritmo debe ser si n divide | G |.

Además, puesto que g _i y g _j están en la misma clase lateral derecha sólo si g _i g _j^-1 es en H, a continuación, puede comprobar subgrupos con el índice n para ver si evitan g _i g _j^-1. Además, observe que (g _i g _j^-1) (g _j g _k^-1) = g _i g _k^-1, para que pueda elegir cualquier emparejamiento del g _i s.

Esto debería ser suficiente si n es pequeño en comparación con | G |.

Otro enfoque consiste en comenzar con H siendo el grupo trivial y añadir elementos del conjunto H ^* = {h en G:! H ^k = g _i g _j^-1, para todo i, j, k; i! = j} a los generadores de H hasta que no pueda agregar más (es decir, hasta que ya no sea un subgrupo). H es entonces un subgrupo máximo de G tal que H es un subconjunto de H ^*. Si puede obtener todos esos H (y que sean lo suficientemente grandes), entonces el subgrupo que está buscando debe ser uno de ellos.

Este enfoque funcionaría mejor para n mayores.

De cualquier manera, un enfoque de tiempo no exponencial no es obvio.

EDIT: Acabo de encontrar una discusión de este tema tan aquí: 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