1
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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.) $\endgroup$
    – ahulpke
    Jun 26, 2020 at 15:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – the_fox
    Jun 26, 2020 at 17:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – the_fox
    Jun 26, 2020 at 17:37
  • 1
    $\begingroup$ @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! $\endgroup$ Jun 26, 2020 at 17:38
  • $\begingroup$ Ah, thanks! I think this looks better than what I did before. $\endgroup$
    – the_fox
    Jun 26, 2020 at 17:39

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$
    – the_fox
    Jun 26, 2020 at 20:04
  • $\begingroup$ @the_fox triple backticks does not work for inline code fragments - use single backticks here, for example this is code in single backticks. $\endgroup$ Jun 26, 2020 at 22:42
  • $\begingroup$ 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). $\endgroup$
    – the_fox
    Jun 27, 2020 at 3:52
  • $\begingroup$ 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$. $\endgroup$
    – ahulpke
    Jun 27, 2020 at 15:05
  • $\begingroup$ 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> $\endgroup$
    – the_fox
    Jun 27, 2020 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .