Listado de elementos que cumplen una propiedad

Question

Un subgrupo $H$ de $G$ se dice que es pronormal en $G$ si para cada $g \in G$ existe $x\in \langle H, H^g \rangle$ tal que $H^x = H^g$ .

La prueba de pronormalidad de un subgrupo viene dada por el siguiente código GAP:

IsPronormal := function(G,H)
               return(ForAll(Set(G),g->IsConjugate(Group(Union(H,H^g)),H,H^g)));
               end;;

Ahora para un subgrupo no pronormal $H$ quiero encontrar explícitamente su pronormalizador en el grupo $G$ es decir, el conjunto de todos los $g\in G$ tal que $H$ et $H^g$ son conjugados en $\langle H, H^g \rangle$ . ¿Cómo utilizo GAP para enumerar estos elementos?

Answer 1

Empezaré con la revisión del código, examinando IsPronormal función dada en la pregunta.

La versión inicial hace efectivamente lo que pone en la caja. Coincide exactamente con la definición dada. Es un buen punto de partida siguiendo el paradigma "Hazlo bien, luego hazlo rápido".

Yo sólo lo reformatearía de otra manera - no hay necesidad de hacer una sangría tan redundante, y además return es una palabra clave y no una función, por lo que no es necesario utilizar entre paréntesis en return(...) :

IsPronormal := function(G,H)
return ForAll( Set(G), g -> IsConjugate( Group( Union(H,H^g) ), H, H^g ) );
end;

(para que quede claro, GAP no es sensible a la indentación, y las preferencias individuales de formato pueden variar, pero es bueno utilizar un estilo coherente, por ejemplo, siguiendo el estilo utilizado en la página Biblioteca GAP ).

Creemos ahora algún grupo, por ejemplo $S_6$ :

gap> S:=SymmetricGroup(6);
Sym( [ 1 .. 6 ] )
gap> Size(S);
720

Se trata de una lista de representantes de clases de conjugación de sus subgrupos:

gap> ccr:=List(ConjugacyClassesSubgroups(S),Representative);;
gap> Length(ccr);
56
gap> ccr[42];
Group([ (4,5), (3,5,6) ])

Ahora comprobaremos para cada subgrupo si es pronormal en $S_6$ . Tarda casi un minuto:

gap> r:=List(ccr,g -> IsPronormal(S,g));
[ true, false, false, false, false, false, true, true, false, false, false, true, 
  true, true, false, false, false, false, false, false, true, true, true, true, 
  true, true, true, true, true, true, true, false, false, true, true, false, false, 
  true, true, true, true, true, true, true, true, true, true, true, true, true, 
  true, true, true, true, true, true ]
gap> time;
58821

La primera mejora consiste en sustituir Set(G) por G . GAP "sabe" enumerar todos los elementos de este grupo, por lo que no es necesario crear un conjunto de sus elementos. No sólo eso lleva algo de tiempo, sino que además GAP puede quedarse sin memoria para grupos grandes, mientras que puede ser perfectamente capaz de enumerar sus elementos uno a uno:

IsPronormal := function(G,H)
return ForAll( G, g -> IsConjugate( Group( Union(H,H^g) ), H, H^g ) );
end;

Esto ayuda un poco al rendimiento. Además, el nuevo resultado coincide con el anterior:

gap> r1:=List(ccr,g -> IsPronormal(S,g));;
gap> time;
53658
gap> r1=r;
true

El siguiente paso es examinar Group( Union(H,H^g) ) . Esto genera un nuevo grupo que toma una unión set-teórica de todos elementos de H et H^g como generadores. Esta lista de generadores es redundante (de hecho, la respuesta a esta pregunta utiliza generadores de grupos, no sus listas de elementos).

IsPronormal := function(G,H)
return ForAll( G, g -> IsConjugate( 
  ClosureGroup( H, GeneratorsOfGroup(H^g) ), H, H^g ) );
end;

Ahora obtenemos los mismos resultados casi el doble de rápido:

gap> r2:=List(ccr,g -> IsPronormal(S,g));;
gap> time;
34142
gap> r2=r;
true

Aquí hay otro cálculo redundante: H^g se calcula dos veces. Para evitarlo, debemos reescribir la función de la siguiente manera:

IsPronormal := function(G,H)
local g, K;
for g in G do
  K:=H^g;
  if not IsConjugate( ClosureGroup( H, GeneratorsOfGroup(K) ), H, K ) then
    return false;
  fi;
od;
return true;
end;

Almacenamiento en caché H^g en K ayuda a reducir el tiempo de ejecución a menos de medio minuto:

gap> r3:=List(ccr,g -> IsPronormal(S,g));;
gap> time;
29717
gap> r3=r;
true

Más pasos:

• si necesitamos comprobar la condición para todos elementos $g \in G$ . Por ejemplo, se pueden excluir todos los elementos centrales $g$ (no será útil en el caso del grupo simétrico, pero sí en el caso general)

• obviamente, no tenemos que comprobar la condición para $g \in H$

• podemos en lugar de iterar sobre todos $g \in G$ comprobar sólo representantes de clases de conjugación de elementos de $G$ ? Parece que no es el caso, pero es un consejo útil a tener en cuenta para el futuro.

Ahora, para calcular el pronormalizador, se podría empezar con el siguiente prototipo (básicamente, sustituir ForAll por Filtered en una de las versiones de IsPronormal más arriba):

Pronormaliser:=function(G,H)
return Filtered(G,g -> IsConjugate( ClosureGroup( H, GeneratorsOfGroup(H^g) ), H, H^g ) );
end;

Para un determinado $G$ et $H$ devuelve una lista de todos los elementos $g\in G$ tal que $H$ et $H^g$ son conjugados en $\langle H, H^g \rangle$ . A continuación, puede mejorarse siguiendo el mismo planteamiento anterior.

---

Observación : He utilizado un enfoque rudimentario de las pruebas para comprobar que cada nueva versión del código devuelve el mismo resultado que las anteriores. Hay una mejor manera de automatizar las pruebas - por favor vea "Utilización de pruebas de regresión" en la lección de Carpintería de Software sobre GAP para más detalles.

Answer 2

Obviamente, en una prueba de pronormalidad hay que considerar cada conjugado de H una sola vez, es decir, basta con recorrer una transversal derecha del normalizador de H en G:

IsPronormal := function ( G, H )
    local g, K;
    for g in RightTransversal( G, Normalizer( G, H ) ) do
        K := H ^ g;
        if not IsConjugate( ClosureGroup( H, GeneratorsOfGroup( K ) ), H, K )
            then
            return false;
        fi;
    od;
    return true;
end;

Del mismo modo, lo que se denomina "pronormalizador" en la pregunta original puede calcularse como una lista de cosets derechos del normalizador de H en G:

Pronormaliser := function ( G, H )
    local g, K, N, res;
    N := Normalizer( G, H );
    res := [  ];
    for g in RightTransversal( G, N ) do
        K := H ^ g;
        if IsConjugate( ClosureGroup( H, GeneratorsOfGroup( K ) ), H, K ) then
            Add( res, N * g );
        fi;
    od;
    return res;
end;

Alternativamente, devuelva Union(res) pero esto puede ser una larga lista en grupos más grandes.

Pero dudo que la definición dada de "pronormalizador" sea una terminología correcta, ya que en general este conjunto no es un subgrupo. (Una definición natural sería el "mayor subgrupo de G en el que H es pronormal", si tal cosa existe).