# GAP code related to supersoluble abnormal subgroups

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.

• My first suggestion would be to indent the code so that the structure is easier understood when looking at it. (I will comment on the question once that is done.) Jun 26, 2020 at 15:49
• I am not really sure what the correct format is for indenting code so I've done what makes sense to me. It should look a little better now. Also, I could put in an extra paragraph explaining what each bit aims for if you think that would help. Jun 26, 2020 at 17:19
• Also, just in case it is of any interest: this is problem 19.100 in the Kourovka notebook (p. 154 in the latest edition). Actually, the problem asks if whenever $G$ admits such a triple factorisation then $G$ is itself supersoluble, so my code is basically searching for a counterexample. Jun 26, 2020 at 17:37
• @the_fox I took the liberty of updating indentation - usually, the body of loops and if statements is indented, but not for ... od and if ... fi themselves. You can see some indentation examples in the GAP library. They may vary from time to time (e.g. some authors also will indent the body of the function; I don't as it requires too much efforts, I think). I also used triple backticks to display the code - this markup now works here, so you don't have to indent it by 4 more spaces, when pasting to this site! Jun 26, 2020 at 17:38
• Ah, thanks! I think this looks better than what I did before. Jun 26, 2020 at 17:39

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.

  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.

• One question related to the fourth point. Instead of  for x in g do if not x in ClosureGroup(h,ConjugateGroup(h,x)) then return false; fi; od;  are you suggesting that I put  for x in GeneratorsOfGroup(g) do if not IsSubset(ClosureGroup(h,h^x),g) then return false; fi; od;  or something else? Jun 26, 2020 at 20:04
• @the_fox triple backticks does not work for inline code fragments - use single backticks here, for example this is code in single backticks. Jun 26, 2020 at 22:42
• Sorry for my silliness, but I don't understand this point. Putting #Checks if the subgroup h is abnormal in the group g IsAbnormalSubgroup:=function(g,h) local norm, x; if not IsSubset(h,Centralizer(g,h)) then return false; fi; norm:=Normalizer(g,h); if Order(norm)>Order(h) then return false; fi; if not IsSubset(ClosureGroup(h,h^x),g) then return false; fi; return true; end;;  results in an error when trying e.g. g=SymmetricGroup(4) and h=CarterSubgroup(s4). Jun 27, 2020 at 3:52
• You're right, sorry, I had overlooked that conjugacy is by the same element.. I've changed to a loop over cosets of $g\cap h$. Jun 27, 2020 at 15:05
• No problem, thanks. I hope the first two routines are ok now. By the way, using SubgroupsOfInterest now results in an error message: SubgroupsOfInterest(s4); Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for IsSupersolvableGroup on 1 arguments at /Applications/gap-4.10.2/lib/methsel2.g:250 called from IsSupersolvableGroup( h ) at *stdin*:112 called from <function "SubgroupsOfInterest">( <arguments> ) called from read-eval loop at *stdin*:118 type quit; to quit to outer loop brk>  Jun 27, 2020 at 17:12