Se dice que dos grupos y son isomórficos si existe un homomorfismo de a que es biyectivo. El problema del isomorfismo grupal es el siguiente: dados dos grupos, verifique si son isomorfos o no. Hay diferentes formas de ingresar un grupo, las dos más utilizadas son una tabla de Cayley y un grupo electrógeno. Aquí estoy asumiendo que los grupos de entrada están dados por su tabla Cayley. Más formalmente:
dos grupos y.
¿Es ?
Supongamos que
El problema de isomorfismo grupal cuando no se sabe que los grupos de entrada provienen de la tabla Cayley en en general. Aunque hay clases grupales como la clase de grupo abeliano para la que se sabe que el problema se encuentra en el tiempo polinómico, grupos que son la extensión de un grupo abeliano, grupos simples, etc. Incluso para grupos de clase dos nilpotentes, no hay algoritmo mejor que la fuerza bruta. conocido.
Tarjan proporciona un algoritmo de fuerza bruta para el isomorfismo grupal, que es el siguiente. Deje y son dos grupos de entrada, y dejar que sea un grupo electrógeno del grupo . Es un hecho bien conocido que cada grupo finito admite un conjunto generador de tamaño y que se puede encontrar en el tiempo polinómico. El número de imágenes del grupo electrógeno en el homomorfismo de a es muchas. Ahora, verifique si cada posible homomorfismo es biyectivo o no. El tiempo de ejecución general será .
Permítanme definir primero el centro del grupo :
G G / Z ( G ) denota los elementos del grupo que conmuta con todos los demás elementos del grupo . Los grupos para los cuales (/ usado para cociente) es abeliano se conocen como grupos nilpotentes de clase dos. Para mí, parece que los grupos nilpotentes de clase dos son los casos más difíciles de resolver el problema del isomorfismo grupal. El significado de "instancias más difíciles" es: resolver ese caso permitirá a los investigadores que trabajan en teoría de grupos resolver el problema del isomorfismo de un gran número de grupos.
Inicialmente, pensé que los grupos simples son las instancias más difíciles, ya que son bloques de construcción de todos los grupos, pero luego supe que el problema del isomorfismo para los grupos simples está en .
Pregunta : ¿Cuál es la instancia más difícil para el problema del isomorfismo grupal?
Respuestas:
0) Experiencia práctica (ver documentos de Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... que dan los algoritmos que se implementan en GAP y MAGMA).
0.5) [EDITAR: añadido 8/7/19] Reducciones. Cuando tales grupospag se generan generando conjuntos de matrices sobre Fpag , el problema es T I -complete [ G.-Qiao '19 ]. Además (véase el punto (4) a continuación), el isomorfismo de los grupos pag del exponente pag y la clase c < p reduce en el tiempo poli al isomorfismo de los grupos pag del exponente pag clase 2 (ibid.).
1) Estructura (reducir a solucionable, luego a grupopag ). Cada grupo finito contiene un subgrupo normal máximo solucionable único, llamado radical resoluble, denotado R a d( G ) . G / R a d( G ) no contiene subgrupos normales abelianos, y el isomorfismo de dichos grupos puede manejarse eficientemente en la práctica ( Cannon-Holt J. Symb. Comput. 2003 ) y en teoría ( Babai-Codenotti-Qiao ICALP 2012 ). Incluso para grupos donde R a d( G ) es abeliano, algunos de estos pueden manejarse en norteO ( logIniciar sesiónn ) tiempo (G-Qiao CCC '14, SICOMP '17), por lo tanto, no del todo polinomial, pero mucho más cerca quenorteIniciar sesiónnorte . Por lo tanto, el principal obstáculo parece ser los grupos solucionables (sub) normales. Ahora, dentro de los grupos solucionables, hay mucha estructura, comenzando con el hecho de que cada grupo solucionable es unproductodepuntode sus subgrupos Sylowpag , y parece que los casos más difíciles son losgrupospag .
2) contando. El número de grupos de ordennorte es ≤ n( 227+ o ( 1 ) ) μ ( n )2 , dondeμ ( n ) es el mayor exponente de cualquier división primitivanorte (Pyber 1993). El número degrupospag de ordenn = pmetro es al menospag( 227+ o ( 1 ) ) m2 (Higman 1960). Entonces ves que el coeficiente de los términos principales en los exponentes coincide. En este sentido, "la mayoría" de los grupos songrupospag (incluso de clase 2 y exponentepag ). Existe una conjetura de larga data que dice que "la mayoría" en el sentido débil precedente puede fortalecerse para decir que la proporción de grupos de orden≤ n que songrupospag tiende a 1 comon → ∞ .
3) Universalidad (/ lo salvaje). Dar una clasificación de grupospag implicaría una clasificación de todas las representaciones modulares de cualquier grupo finito (o incluso álgebra artiniana) en la característica pag ( Sergeichuk 1977 ).
4) Flexibilidad. ¿Por quépag -grupos de clase 2 y no de clase superior? (Tenga en cuenta que pag -grupos de clase casi-máxima, la llamada "pequeña coclase", básicamente se han clasificado, Eick y Leedham-Verde 2006 , ver también algunas de las respuestas aquí .) Para cualquier pag -grupo uno puede asociar un anillo de Lie calificado, donde el corchete en el anillo de Lie corresponde al conmutador en el grupo. La asociatividad en el grupo implica la identidad de Jacobi para el grupo, lo que da lugar a un verdadero anillo de mentira. Sin embargo, tenga en cuenta que cuando el grupo es de clase 2, la identidad de Jacobi se cumple trivialmente (todos sus términos son automáticamente 0), por lo que esto no impone restricciones adicionales en la estructura. Básicamente corresponde a un mapa bilineal simétrico sesgado arbitrario. Para los grupos pag del exponente pag , incluso hay una reducción de la clase c < p a la clase 2.
fuente