Installing a new function in GAP

Question

I have written the following snippet of code to compute the subgroup permutability degree of a finite group $G$.

spd := function(G)
local allsubs, subreps, count, H, K, index;
subreps := Flat(List(ConjugacyClassesSubgroups(G),Representative)); 
allsubs := Flat(List(ConjugacyClassesSubgroups(G),Elements)); 
count:=0;
for H in subreps do
  index := Index(G,Normalizer(G,H));
  for K in allsubs do
    if ArePermutableSubgroups(H,K) then 
      count := count+index; 
    fi;
  od;
od;
return Float(count/(Size(allsubs)^2));
end;

I want to ask two things: first, whether this can be slightly improved to run faster, and second, how to install this as a function in GAP so that I don't have to define it every time I run the programme.

Regarding the 2nd question, see The gap.ini and gaprc files. You can put this function (or command Read("file-with-this-function") into your gaprc file. — Olexandr Konovalov, Mar 08 '15 at 14:59
An obvious improvement is that subreps and allsubs, they only create some overhead. I will try to think of more. For which groups are you calculating this, and what can you say about the performance that you observe? I think most of the time would be spent in ConjugacyClassesSubgroups and that's unavoidable. — Olexandr Konovalov, Mar 08 '15 at 15:04
Sometimes I use it for computing the spd of "named" groups, and sometimes to compute the spd of all small groups of certain order. In the second case, I could probably save some time by checking whether spd=1 beforehand. If iterating over groups of prime power order I can use the 'IsTGroup' command of the Permut package (if true then spd is 1); for composite orders I could check if every Sylow subgroup is a T-group. — the_fox, Mar 08 '15 at 15:49
I noticed a slight difference in time when computing the spd of $A_5$ as AlternatingGroup(5) and SmallGroup(60,5) and I thought that this might generalise, but for $A_6$ times are nearly identical. The question is though, whether a certain representation yields better times. — the_fox, Mar 08 '15 at 15:53
By the way, I'd like to check whether the number of permuting pairs among all $p$-subgroups of $G$ relates to the number of pairs of permuting $p$-subgroups which lie in a single Sylow. Any suggestions how to filter the lists in my code to do that? — the_fox, Jul 16 '15 at 16:44

score 2 · Accepted Answer · answered Mar 15 '15 at 15:44

2

The first comment by Alexander Konovalov already tells you how you could make the function available in every run automatically.

Unless all your groups are solvable (in which case PC groups would be the choice), and assuming they can be represented by permutations of plausible degree, permutation groups are as good as it gets.

As for further improvements, you could replace `allsubs' with representatives of the orbits of the normalizer of H. These are parameterized by double cosets. That is your code would have the structure:

cl:=ConjugacyClassesSubgroups(G);
for i in cl do
  H:=Representative(i);
  HN:=Normalizer(G,i); # or StabilizerOfExternalSet(i) should also work.
  for j in cl do
    Kr:=Representative(j);
    KN:=Normalizer(G,Kr);
    dc:=DoubleCosets(G,KN,HN);
    for d in dc do
      K:=Kr^Representative(d);

and then go on as you have. This will not imprve the complexity, but the number of permutability tests by a factor.

answered Mar 15 '15 at 15:44

ahulpke

18,416
1
21
38

Many thanks... By the way, I take it that if the group is solvable, then it is automatically represented as a pc-group? That might depend on how one inputs the group though, I am not sure. – the_fox Mar 16 '15 at 14:12
As an example, I'd like to compute the first, three say, instances of (the spd of) $Q_8^n$, but for $n=3$ the computation fails to complete. I realise this is a heavy calculation in itself, but perhaps I can do slighlty better than DirectProduct(DirectProduct(Q8,Q8),Q8). – the_fox Mar 16 '15 at 14:20
@the_fox Solvable groups are not automatically represented as PC groups, but many libraries (in particular the small groups library) do so. The DirectProduct construction will keep the representation if possible. The issue is that $Q8^3$ has an abelian factor $2^6$ and $19371$ classes of subgroups. (you might want to add print functions to your code tat report on progress.) Fusing under the automorphism group (i.e. considering subgroups up do action of $Aut(G)$) should help -- My guess is that it will reduce subgroups by a factor $50$. – ahulpke Mar 16 '15 at 15:32

Installing a new function in GAP

1 Answers1