Algoritmo para encontrar clases conjugacy de los sub-grupos/elementos (en la matriz de grupos)?

Question

Estoy buscando un simple (=factibles de implementar por mí mismo) algoritmo para calcular la conjugacy clases de elementos y subconjuntos de un determinado subgrupo de $\text{P}{\Gamma}\text{L}(n,q)$. Así que, dado que un grupo de $G\le \text{P}{\Gamma}\text{L}(n,q)$, encuentre sus clases conjugacy de elementos, y/o de sus clases conjugacy de los subgrupos.

Sé que el GAP/Magma puede hacer esto, pero me gustaría hacer mi propia implementación (en Java), por diversas razones. Yo almacén de grupos por sus generadores, Schreier-los Sims de la cadena y de la acción en subespacios proyectivos de $\text{PG}(n-1,q)$, y ya tenemos el código para calcular conjunto de sabios estabilizadores, isomorphisms y órbitas (todo en subespacios proyectivos), por lo que el uso de estos en cualquier algoritmo es libre para mí.

Dado que una posible aplicación de la pena perder un $\mathcal O(\log|G|)$ factor (o similar) en comparación con la BRECHA/Magma, ¿qué algoritmo es el más adecuado para usar aquí? Una referencia a un algoritmo en pseudocódigo sería la mayoría de la recepción: Google no pudo encontrar cualquier cosa (incluso una hoja de papel), y tratando de entender lo que la BRECHA de hace internamente es.. bueno.. horrible.

Answer 1

Usted está realmente tratando de re-inventar la rueda. Hay un montón de literatura sobre este tema, y los algoritmos que se han sometido a sucesivos de refinamiento en los últimos 30-40 años, con la necesidad de manejar grandes y grupos más grandes.

Si desea controlar arbitraria subgrupos de ${\rm P \Gamma L}(n,q)$, entonces usted podría muy bien el uso general de permutación grupo de algoritmos. Dos estudios recientes sobre este tema son:

J. Cannon y D. Holt, Informática conjugacy clases en grupos de permutación. J. Álgebra, 300: 213-222, 2006.

A. Hulpke, clases de Computación en la permutación de grupos a través de homomórfica imágenes. De matemáticas. Comp. 69 no. 232, 1633-1651, 2000.

Para moderadamente pequeños grupos, el elemento aleatorio método es a menudo tan rápido como nada, y no debe ser difícil de implementar. Usted acaba de mantener la elección de elementos aleatorios, prueba de ellos para conjugacy con los representantes de la clase, y seguir adelante hasta que usted tiene un conjunto completo, donde para hacer la prueba de integridad mediante el cálculo de las órdenes de sus centralizadores. Por supuesto, para hacer eso, primero sería necesario implementar un algoritmos para calcular centralizadores de los elementos de la permutación de los grupos, lo cual implicaría un retroceso de búsqueda. Una debilidad de este método es que puede tomar un largo tiempo para encontrar elementos en clases que son pequeños en comparación con el orden del grupo. Generalmente funciona bien para grupos que están cerca de ser nonabelian simple, y muy mal para los grupos que están a punto de ser solucionable.

Los métodos más refinados que funcionan bien para muchos tipos de grupos de empezar por encontrar la mayor solucionable normal subgrupo $L$ de su grupo de $G$. A continuación, comenzar por la búsqueda de representantes de la clase del cociente grupo $G/L$ (para los que usted podría utilizar el elemento aleatorio método en la primera instancia, pero de nuevo hay métodos más refinados para grupos más grandes). Habiendo hecho de que las clases de $G$ sucesivamente "levantar" las clases a través de la primaria abelian capas de los términos en jefe de la serie para $G$ que se encuentran en $L$. Este levantamiento método ha sido utilizado para la solución de los grupos (el caso especial $G=L$) desde la década de 1980. Una referencia para que se

M. Mecky y J. Neubuser, Algunas observaciones sobre el cálculo de clases conjugacy de los solubles de los grupos. Bull. Austral. De matemáticas. Soc. 40:281-292, 1989.