Código GAP relacionado con los subgrupos anormales supersolubles

Question

La propiedad que quiero comprobar es si existe un grupo finito no supersoluble $G$ que admite una triple factorización $G=AB=AC=BC$ , donde $A, B, C$ son subgrupos anormales supersolubles de $G$ . (Un subgrupo $H$ de $G$ se llama anormal si para todo $x \in G$ tenemos $x \in \langle H, H^x \rangle$ .)

He empezado a probar esta propiedad con las siguientes rutinas GAP:

#Checks if g=hk
IsProductOf:=function(g,h,k)
if Order(g)*Order(Intersection(h,k)) = Order(h)*Order(k) then
  return true;
fi;
return false;
end;;

#Checks if the subgroup h is abnormal in the group g
IsAbnormalSubgroup:=function(g,h)
local norm, y, closure;
if not IsSubset(h,Centralizer(g,h)) then 
  return false;
fi;
norm:=Normalizer(g,h);
if Order(norm)>Order(h) then
  return false;
fi;
for y in RightTransversal(g,h) do
  closure:=ClosureGroup(h,ConjugateGroup(h,y));
    if not ForAll(TrivialSubgroup(g),x->x*y in closure) then
      return false;
    fi;
od;
return true;
end;;

y

# Checks whether the group g can be written as a product g=ab where a, b 
# are abnormal supersoluble subgroups of g, and whether g has at least three conjugacy
# classes of such subgroups
IsCandidateGroup:=function(g)
local list, a, b, brep, r, reps, i, j;
list:=Filtered(List(ConjugacyClassesSubgroups(g),Representative),
                    x->IsSupersolvableGroup(x) and IsAbnormalSubgroup(g,x));
if Size(list)<3 then
  return false;
fi;
for i in [1..Length(list)] do
a:=list[i]; 
  for j in [i+1..Length(list)] do
    brep:=list[j];  
    reps:=List(DoubleCosetRepsAndSizes(g,brep,a),x->x[1]);
      for r in reps do
        b:=brep^r;
          if IsProductOf(g,a,b) then
             return true;
          fi;
      od;
  od;
od;
return false;
end;;

Siguiente,

test:=function(g)
local i, j, k, list, h, m, n, mrep, nrep, reps, r, s, Reps;
list:=Filtered(List(ConjugacyClassesSubgroups(g),Representative),
                    x->IsSupersolvableGroup(x) and IsAbnormalSubgroup(g,x));
for i in [1..Length(list)] do
h:=list[i];
  for j in [i+1..Length(list)] do
  mrep:=list[j];
  reps:=List(DoubleCosetRepsAndSizes(g,mrep,h),x->x[1]);
    for r in reps do
    m:=mrep^r;
      if IsProductOf(g,h,m) then
        for k in [j+1..Length(list)] do
        nrep:=list[k];
        Reps:=List(DoubleCosetRepsAndSizes(g,Normalizer(h,m),nrep),x->x[1]);
          for s in Reps do
          n:=nrep^s;
            if IsProductOf(g,h,n) and IsProductOf(g,m,n) then
              return true;
            fi;
          od;
        od;
      fi;
    od;
  od;
od;
return false;
end;;

¿Quizás alguien pueda sugerir algún código concreto para mejorar la eficiencia?

---

He actualizado el código para tener en cuenta las sugerencias y he simplificado las cosas en un par de lugares, aunque no estoy totalmente seguro de que el test es correcta.

Answer 1

Algunas observaciones sobre la codificación para la velocidad. Nada cambia fundamentalmente los algoritmos ni utiliza nuevas ideas matemáticas:

IsAbnormalSubgroup:=function(g,h)
local norm, x;
norm:=Normalizer(g,h);
if Order(norm)>Order(h) then
  return false;

Normalizer es una operación comparativamente cara, mientras que Centralizer suele ser mucho más rápido. Podría (pero eso es algo que habría que probar en ejemplos) dar una aceleración para probar primero (antes de calcular el normalizador) si el centralizador da algo nuevo:

  if not IsSubset(h,Centralizer(g,h)) then return false;fi;

A continuación, se recorren todos los elementos de $G$ :

for x in g do
  if not x  in ClosureGroup(h,ConjugateGroup(h,x)) then

Recorrer todos los elementos tomará mucho tiempo y dado que se llama a esto desde dentro de los bucles se quiere ser lo más eficiente posible aquí. Una primera reducción sería ejecutar en su lugar a través de cosets de $h$ es decir, a través de los representantes de $h\cap g$ .

  for x in RightTransversal(g,Intersection(g,h)) do

Aún mejor sería recorrer los cosets de $N_g(h)$ primero, y luego probar un representante de cada coset de $g\cap h$ en un bucle doble.

  no:=Normalizer(g,h);  
  tra:=RightTransversal(no,Intersection(g,h));
  for x1 in RightTransversal(g,no) do
    clo:=ClosureGroup(h,ConjugateGroup(h,x1));
    if not ForAll(tra,x->x*x1 in clo) then ...

Siguiente:

#Creates a list of all abnormal supersoluble subgroups of the group g
SubgroupsOfInterest:=function(g)
local list, h;
list:=[];
for h in AllSubgroups(g) do
  if [...]
    Append(list,[h]);

Sería más rápido probar sólo un representante en cada clase de conjugación. Es decir:

  for hcl in ConjugacyClassesSubgroups(g) do
    h:=Representative(hcl);
    if [...]
      Append(list,AsList(hcl));

Además, aunque ya no es necesario aquí, en lugar de Append(list,[h]); utilice Add(list,h); ya que no crea una lista innecesaria.

En su prueba

  if IsAbnormalSubgroup(g,h) and IsSupersolvableGroup(h) then

Creo que probar la supersolubilidad será normalmente más rápido que probar la anormalidad (que necesita un normalizador). Así que yo usaría:

  if IsSupersolvableGroup(h) and IsAbnormalSubgroup(g,h) then

ya que GAP hace una evaluación "perezosa" de izquierda a derecha, saltándose las partes que no cambiarán el valor lógico.

# Checks whether the group g can be written as a product g=ab where a, b 
# are subgroups of interest, and whether g has at least three conjugacy
# classes of supersoluble abnormal subgroups
IsCandidateGroup:=function(g)
local list, a, b;
list:=Filtered(List(ConjugacyClassesSubgroups(g),Representative),
                    x->IsSupersolvableGroup(x) and IsAbnormalSubgroup(g,x));
if Size(list)<3 then
  return false;
fi;
for a in list do
  for b in SubgroupsOfInterest(g) do
    if ArePermutableSubgroups(g,a,b) and ClosureGroup(a,b)=g then

Si la prueba de permutabilidad es más costosa, bastaría con recorrer los subgrupos b hasta la conjugación por $N_G(a)$ . Puede hacerlo tomando b sólo hasta la conjugación (es decir, el cambio SubgroupsOfInterest ) y calcular los representantes de los cosets dobles $N_G(b)\setminus G/N_G(a)$ y luego pasar por los conjugados $b^r$ para los representantes $r$ . También puede mover rge Closure prueba fuera de este nuevo bucle interior

  for a in list do
    na:=Normalizer(G,a);
    for brep in SubgroupsOfInterestUpToConjugacy(g) do
      if ClosureGroup(a,brep)=g then
        reps:=List(DoubleCosetsRepsAndSizes(G,Normalizer(G,brep),na),x->x[1]);
        for r in reps do
          b:=brep^r;
          if ArePermutableSubs(g,a,b) then

En tu bucle principal tienes la misma situación:

  for h in list do
    for k in subs do
      for j in subs do

Podrías presentarte para k hasta la conjugación por $N_G(h)$ y para j hasta la conjugación por $N_{N_G(h)}(k)$ .

        if ArePermutableSubgroups(g,h,k) and
           ArePermutableSubgroups(g,k,j) and
           ArePermutableSubgroups(g,h,j) then
          if ClosureGroup(h,k)=g and 
             ClosureGroup(k,j)=g and 
             ClosureGroup(h,j)=g then

De nuevo espero que el Closure pruebas para ser más barato que el IsPermutable pruebas. Así que hágalas antes. Más aún, mueva las pruebas que sólo implican h y k fuera del interior j para evitar la repetición de las pruebas.

Todos estos cambios juntos deberían proporcionarle una, o incluso dos, magnitudes de aceleración.

En cuanto a una descripción más sistemática de dichas técnicas, existe un libro antiguo: Jon Louis Bentley, Escribir programas eficientes Prentice Hall, 1982, que he encontrado útil.