1
$\begingroup$

Let $G$ be a finite $p$-group and $d(G)$ be its minimal number of generators. We say that $G$ is $d$-maximal if $d(H) < d(G)$ for all $H < G$.

The following code determines weather $G$ is $d$-maximal or not.

IsDMaximal := function( G )
local nr;
nr := Length(Filtered(ConjugacyClassesSubgroups(G), x-> Length(MinimalGeneratingSet(Representative(x))) < Length(MinimalGeneratingSet(G))));
return nr = (Length(ConjugacyClassesSubgroups(G)) - 1);
end;

I realized that if $d(H) < d(G)$ for all subgroups $H$ containing the commutator subgroup of $G$, then then $G$ is $d$-maximal. The latter property allows us, in principle, to decrease the execution time for checking the $d$-maximality of $G$ (by testing less number of subgroups), I coded this "property" as follows:

IsDMaximalByComm := function(G)
local ContComms, H, HC;
 ContComms := [];
for H in AllSubgroups(G) do 
      if IsSubgroup(H, DerivedSubgroup(G)) then
         Add(ContComms, H);
         fi;       
od;
for HC in ContComms do 
  if Length(MinimalGeneratingSet(HC)) < Length(MinimalGeneratingSet(G)) then
return G;
fi;
od;
end;

Unfortunately, the execution time got longer!

How to improve my code?

Thanks in advance!

$\endgroup$
7
  • 1
    $\begingroup$ Your second code takes longer probably because you compute all subgroups and not just subgroups up to conjugacy. $\endgroup$ Oct 15, 2021 at 16:07
  • $\begingroup$ @BrauerSuzuki in fact, each of these subgroups are normal(I mean the ones containing the commutator subgroup). $\endgroup$
    – A.Messab
    Oct 15, 2021 at 16:10
  • $\begingroup$ but AllSubgroups(G) computes all subgroups and not just those which contain $G'$. Better use NormalSubgroups $\endgroup$ Oct 15, 2021 at 16:16
  • $\begingroup$ @BrauerSuzuki You're right, many thanks. $\endgroup$
    – A.Messab
    Oct 15, 2021 at 16:19
  • $\begingroup$ @BrauerSuzuki, But the real question is: How to exploit the fact that the subgroups containing the commutator determine $d$-maximality. $\endgroup$
    – A.Messab
    Oct 15, 2021 at 16:22

1 Answer 1

2
$\begingroup$

First (as already mentioned in the comments) you could replace

for H in AllSubgroups(G) do 
      if IsSubgroup(H, DerivedSubgroup(G)) then
         Add(ContComms, H);
         fi;       
od;

by

nat:=NaturalHomomorphismByNormalSubgroup(G,DerivedSubgroup(G));
ContComms:=AllSubgroups(Image(nat,G));
ContComms:=List(ContComms,x->PreImage(nat,x));

to only consider subgroups containing the derived subgroup.

The length of a minimal generating set of $G$ is fixed, so store

lm:=Length(MinimalGeneratingSet(G));

Then also you don't need an explicit minimal generating set, but only the length. Thus replace the test

Length(MinimalGeneratingSet(HC)) < Length(MinimalGeneratingSet(G)) then

by

LogInt(IndexNC(HC,DerivedSubgroup(HC)),p)

Finally your logic is wrong -- you return the group as soon as you have found one subgroup with a smaller generating set, but you want to test whether all have (or one is an opposite. Thus

for HC in ContComms do 
  if LogInt(IndexNC(HC,DerivedSubgroup(HC)),p)>lm then return false;fi;
od;
return true;
$\endgroup$
1
  • $\begingroup$ Is your code is faster than: IsDNMax:= function (G) local nor, max; nor := NormalSubgroups(G); nor := Filtered(nor, x -> Size(x)<Size(G) and IsSubgroup(x, DerivedSubgroup(G))); max := Maximum(List(nor, x -> RankPGroup(x))); return max < RankPGroup(G); end; $\endgroup$
    – A.Messab
    Oct 17, 2021 at 13:52

You must log in to answer this question.

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