¿Cuál es la instancia más difícil para el problema del isomorfismo grupal?

11

Se dice que dos grupos (G,) y (H,×) son isomórficos si existe un homomorfismo de G a H 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:

Group Isomorphism Problem

Input :  dos grupos(G,) y.(H,×)

Decide :  ¿Es ?GH

Supongamos quen=|G|=|H|

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.P

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á .GHSGO(logn)SGHnlognnorteIniciar sesiónnorte+O(1)

Permítanme definir primero el centro del grupo :sol

Z(sol)={solsolunasol=soluna,unasol}

Z(sol)G G / Z ( G ) denota los elementos del grupo sol 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.solsol/ /Z(sol)

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 .PAG

Pregunta : ¿Cuál es la instancia más difícil para el problema del isomorfismo grupal?

aaaa
fuente
Hola, ¿podría considerar ampliar un poco su pregunta para recapitular la definición del problema de isomorfismo grupal (cuál es la entrada, cuál es la salida) y / o una referencia? ¿Podría considerar también resumir la definición del centro de un grupo? Por último, ¿podría aclarar si "permitir como resolver" ("nosotros") es un reclamo sobre la existencia de una reducción?
a3nm

Respuestas:

15

pagSe cree ampliamente que losgrupos p de clase 2 y el exponentepag son el caso más difícil de isomorfismo grupal (pag>2 ). (Parapag=2 , debemos considerar el exponente 4, ya que todos los grupos del exponente 2 son abelianos: ejercicio fácil para el lector). Aunque todavía no hay una reducción del GpIso general a esta clase de grupos (aunque vea el punto 0.5 a continuación) ), hay varias razones para esta creencia. Permítanme describir algunos de ellos aquí.

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 grupos pag se generan generando conjuntos de matrices sobre Fpag , el problema es Tyo -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<pag reduce en el tiempo poli al isomorfismo de los grupos pag del exponente pag clase 2 (ibid.).

1) Estructura (reducir a solucionable, luego a grupo pag ). Cada grupo finito contiene un subgrupo normal máximo solucionable único, llamado radical resoluble, denotado Runare(sol) . sol/ /Runare(sol) 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 Runare(sol) es abeliano, algunos de estos pueden manejarse en norteO(Iniciar sesiónIniciar sesiónnorte) 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 orden norte es norte(227+o(1))μ(norte)2, dondeμ(norte)es el mayor exponente de cualquier división primitivanorte(Pyber 1993). El número degrupospagde ordennorte=pagmetroes al menospag(227+o(1))metro2(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 ordennorteque songrupospagtiende a 1 comonorte.

3) Universalidad (/ lo salvaje). Dar una clasificación de grupos pag 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<pag a la clase 2.

Joshua Grochow
fuente
¿Puedes editar la definición de la clase 2? La página de Wikipedia sobre grupos solo menciona la clase nilpotency, ¿es esa la misma noción de clase que tienes en mente? pag
Vincent
Sí, clase nilpotency.
Joshua Grochow
¡Gracias por la aclaración!
Vincent