GAP code related to supersoluble abnormal subgroups

Question

The property I want to check is whether there exists a finite non-supersoluble group $G$ which admits a triple factorisation $G=AB=AC=BC$, where $A, B, C$ are abnormal supersoluble subgroups of $G$. (A subgroup $H$ of $G$ is called abnormal if for all $x \in G$ we have $x \in \langle H, H^x \rangle$.)

I have begun testing for this property with the following GAP routines:

#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;;

and

# 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;;

Next,

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;;

Perhaps someone could suggest some concrete code to improve efficiency?

---

I have updated the code to account for suggestions and have simplified things in a couple of places, although I am not totally sure that the test function is correct.

Answer 1

A few remarks on coding for speed. Nothing changes the algorithms fundamentally or uses new mathematical ideas:

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

Normalizer is a comparatively expensive operation, while Centralizer is often much faster. It might (but that is something one would have to try out in examples) give a speedup to test first (before computing the normalizer) whether the centralizer gives anything new:

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

Next, you run through all elements of $G$:

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

Running through all elements will take a long time and since you call this from within loops you want to be as efficient as possible here. A first reduction would be to run instead through cosets of $h$, that is through representatives of $h\cap g$.

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

Even better would be to run over cosets of $N_g(h)$ first, and then test one representative of every coset of $g\cap h$ therein in a double loop.

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

Next:

#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]);

It would be faster to test only one representative in each conjugacy class. That is:

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

Aside, though not needed here any longer, instead of Append(list,[h]); use Add(list,h); as it does not create an unneccessary list.

In your test

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

I think testing supersolvability will typically be faster then testing abnormality (which needs a normalizer). So I would use:

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

instead since GAP does "lazy" left-to right evaluation, skipping parts that will not change the logical value.

# 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

If the test for permutability is more expensive, it would be sufficient to run through subgroups b up to conjugacy by $N_G(a)$. You could do so by taking b only up to conjugacy (i.e. change SubgroupsOfInterest) and calculate representatives of the double cosets $N_G(b)\setminus G/N_G(a)$ and then run through conjugates $b^r$ for the representatives $r$. You can also move rge Closure test outside this new innermost loop

  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

In your main loop you have the same situation:

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

You could run for k up to conjugacy by $N_G(h)$ and for j up to conjugacy by $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

Again I expect the Closure tests to be cheaper than the IsPermutable tests. So do them before. Even more, move tests that only involve h and k outside the inner j loop, so you avoid repeated testing.

All these changes together should give you one, maybe even two magnitudes of speedup.

As for a more systematic description of such techniques, there is an old book: Jon Louis Bentley, Writing Efficient Programs, Prentice Hall, 1982 that I found useful.