Algoritmo eficiente para encontrar Transversal (derecha o izquierda) en un grupo

Question

Me pregunto si alguien conoce un algoritmo para encontrar una a la izquierda o a la derecha transversal en un grupo de manera eficiente. La definición es que se les da un subgrupo $H$ de un grupo de $G$, y desea encontrar un representante de cada coset de $H$$G$.

Recordar el coset de la prueba: $x, y \in G$ están en la misma coset iff $x^{-1}y \in H$. Esto produce un trivial $O(|G|)$ algoritmo. Simplemente prueba a cada elemento de a $G$ hasta encontrar $|H : G|$ únicos representantes.

Me pregunto si hay una manera más eficiente de hacer esto, de preferencia de manera determinista. También, si la búsqueda de una base o fuertemente de generación del sistema es necesario de antemano, el costo de tales deben ser incluidos en la eficiencia del algoritmo.

Estoy interesada en un algoritmo para cualquier grupo, pero si un algoritmo especial que existe al $G = S_n$ $H$ es una permutación de grupo, posiblemente $S_k$ algunos $k < n$, yo estaría encantado de aprender de esto.

Yo también agradecería cualquier referencia a los libros de texto o artículos que puedan ayudar a resolver este problema.

Gracias!

Answer 1

Una referencia general sobre los algoritmos en la teoría de grupos es el libro "Manual de cálculo de Teoría de grupos" por Holt, Eick y O'Brien.

Algoritmos para la búsqueda de las transversales de los subgrupos de permutación de grupos se describen en la Sección 4.6.7. Esto requiere de una base fuerte y set de generación de energía, pero, para un subgrupo de índice, la búsqueda de la BSGS se suele ser más rápida que la búsqueda de la transversal. La complejidad está determinada principalmente por el tamaño de la salida, que depende del índice.

Un método para subgrupos de solucionable grupos definidos por el poder del conjugado de presentaciones se describe en el Lema 8.33.