15 votos

¿Representación explícita de permutaciones del grupo simple esporádico de Thompson?

El grupo Thompson Th de orden $90745943887872000$ es uno de los grupos simples esporádicos que aparecen en la clasificación de los grupos simples finitos.

Se conocen sus subgrupos maximales (véase http://brauer.maths.qmul.ac.uk/Atlas/v3/spor/Th/ ) y todos ellos son notablemente pequeños, lo que tiene como consecuencia que cualquier representación de permutación de Th tiene un grado muy grande.

En particular, la representación de permutación de Th de grado más bajo posible tiene grado $143127000$ .

Pregunta: ¿Alguien ha determinado explícitamente dos permutaciones de este grado que generen Th y, en caso afirmativo, están disponibles en línea estas dos permutaciones?

Google revela que algunos investigadores de CS han utilizado anteriormente este grupo como caso de prueba para desarrollar, perfeccionar y probar algoritmos para grupos de permutación de alto grado.

Por ejemplo, el documento

http://www.ccs.neu.edu/home/gene/papers/issac03.pdf

menciona explícitamente el grupo de Thompson, y más en general algoritmos para manipular grupos de permutación de grado superior a 100 millones. Comentan que cada permutación necesita aproximadamente 1/2 Gb para almacenarse, y que como los algoritmos habituales necesitan almacenar $\Omega(\log n)$ permutaciones ( $n$ es el grado) el espacio es un problema importante. Pero esto fue hace más de diez años, y hoy en día almacenar incluso unos cientos de permutaciones de este tamaño no supondría ningún problema en particular.

He enviado un correo electrónico a uno de los autores de este trabajo (Cooperman), pero después de esperar un tiempo razonable (una semana más o menos), no he tenido respuesta, así que ahora pregunto en esta lista.

14voto

Derek Holt Puntos 18358

El siguiente código Magma funcionó en menos de una hora. Está utilizando la idea sugerida por Dima Pasechnik trabajando con el grupo ${\rm Th} < {\rm GL}(248,2)$ actuando sobre una órbita de un subespacio de dimensión $2$ fijado por el subgrupo maximal $^3D_4(2):3$ . Utilizó unos 43 GB. El grupo procede de la base de datos ATLAS, que está disponible en Magma, y la definición de la función SS, que define los generadores del subgrupo, se tomó de aquí

Por supuesto, mientras se realiza este cálculo, es necesario almacenar los 143 millones de imágenes de la $2$ -que necesitará mucho espacio. Una vez calculadas las dos permutaciones, todo esto se puede desechar. Creo recordar de una charla en Aquisgrán hace varios años que se han desarrollado algunas técnicas para reducir el espacio necesario durante grandes cálculos orbitales de este tipo, posiblemente a costa de arriesgarse a cometer errores. No recuerdo los detalles, ¡pero puede que alguien lo haga!

G:=MatrixGroup("Th",1);
SS:=function(S)
   // WARNING! This is not an SLP!
   w1 := S.1;
   w2 := S.2;
   w3 := w1 * w2;
   w4 := w3 * w2;
   w5 := w3 * w4;
   w6 := w3 * w5;
   w7 := w6 * w3;
   w8 := w7 * w4;
   w9 := w3 * w8;
   w8 := w7 * w9;
   w2 := w8^5;
   w4 := w3^8;
   w3 := w4^-1;
   w5 := w3 * w1;
   w1 := w5 * w4;
   return [w1,w2];
end function;
H:=sub<Generic(G)|SS(G)>;
MH:=GModule(H);
C:=Submodules(MH);
V:=C[2];  //dimension 2
f:=Morphism(V,MH);
U:=VectorSpace(MH);
W:=sub<U|U!f(V.1),U!f(V.2)>; //setting up V as a subspace of U
I:=OrbitImage(G,W);
Degree(I); // 143127000

5voto

Dima Pasechnik Puntos 5894

Presumo que es un ejercicio calcular estas permutaciones, siempre que uno pueda encontrar una buena representación de pequeña dimensión (con suerte de dimensión 248 sobre un campo pequeño) de Th s.t. el subgrupo de índice mínimo (la información sobre cómo generarla se da en http://brauer.maths.qmul.ac.uk/Atlas/v3/subgroup/ThG1-max1W1 ) estabiliza allí algún subespacio de pequeña dimensión, y luego calcular la acción de los generadores sobre la órbita de estos subespacios.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X