¿Se sabe "a menudo" cómo calcular una lista de grupos?

Question

De la introducción del artículo Construcción de grupos finitos escrito por Hans Ulrich Besche y Bettina Eick:

Cuando se intenta determinar hasta el isomorfismo los grupos de un orden dado se suele se sabe cómo calcular una lista de grupos de este orden que contenga cada tipo de isomorfismo al menos una vez. El problema central es reducir a los representantes del tipo de isomorfismo.

¿Se sabe realmente cómo calcular una lista de grupos de un orden determinado que contenga cada tipo de isomorfismo al menos una vez? Si es así, por favor dígame dónde encontrar tal algoritmo.

Answer 1

Los algoritmos de Eick y O'Brien para calcular una lista completa de grupos de un orden dado no son algoritmos generales, porque hacen uso de propiedades conocidas (es decir, precalculadas) de los grupos simples finitos. Pero estas propiedades conocidas lo son para grupos simples de orden mucho más grande de lo que es remotamente factible encontrar una lista completa de grupos de ese orden, y es probable que siga siendo así. Curiosamente, para las potencias primos $p^n$ que es el caso más difícil, el algoritmo en cuestión es de propósito general. Tendría sentido preguntar si existe un algoritmo para hacer esto que sea polinómico en la longitud de la salida - ¡no tengo la respuesta!

Con respecto a las pruebas de grupos de orden $n$ para el isomorfismo, no se conoce ningún algoritmo para hacerlo que sea polinómico en $n$ Así que si has encontrado un algoritmo de este tipo, sin duda podrías publicarlo en una buena revista. Probablemente no hay mucha diferencia en cómo se dan los grupos, ya que se puede pasar de representaciones matriciales o de permutaciones a presentaciones finitas en tiempo polinomial en $n$ . Es fácil comprobar el isomorfismo en el tiempo $O(n^{{\rm log}\, n})$ (encontrar un conjunto generador de tamaño $O({\rm log}\, n)$ y probar cada conjunto posible de imágenes generadoras para inducir un isomorfismo) y no se conoce ningún método esencialmente mejor.

Por supuesto, los algoritmos implementados utilizan muchos trucos. Un artículo publicado sobre este tema es:

J. Cannon y D.F. Holt. Automorphism group computation and isomorphism testing in finite groups. J. Symbolic Computation 35, 241-267 (2003).

Answer 2

Por supuesto, es teóricamente posible "calcular una lista de grupos" en cualquier orden, si el tiempo y la memoria no están limitados. Basta con enumerar sobre todas las tablas de multiplicación posibles, o sobre subconjuntos de un grupo de permutación suficientemente grande. Supongo que lo que realmente preguntas es cómo hacer esto de forma eficiente, y por lo que sé es un problema difícil incluso para valores relativamente modestos de $n$ El tamaño requerido del grupo.

Paquetes informáticos como GAP son bastante buenos para conocer o calcular esas listas, y hay documentos de la gente que los escribió que detallan los algoritmos que han utilizado. Puedes encontrar algunas referencias en este cerrado Pregunta de MO (cerrado porque la pregunta está mal definida).

¿Qué es lo que realmente quiere conseguir? ¿Realmente te sirve la lista completa de grupos de orden 1024, por ejemplo? Hay más de 49 mil millones de ellos.