[GAP Forum] Low Index Subgroups Process.

Michael Hartley Michael.Hartley at nottingham.edu.my
Thu Jun 9 05:28:21 BST 2005


Dear GAPpers. 

One thing I miss from CAYLEY (now MAGMA) is the existence of a
collection of functions that returns the low index subgroups of a
finitely presented group one by one instead of all at once. This was
particularly useful in situations where one is searching for an example
of a low index subgroup with certain properties, but returning the
complete list of subgroups up to the required index would just take far
too long.

Well, I have hacked the source code of the LowIndexSubgroupsFpGroup
function, and created two functions 
"LowIndexSubgroupsStream" and "GetNextLowIndexSubgroup". They are in
the attached file, and may be used as follows:

# set up the (infinite) fp group of a tesselation of hyperbolic space
by octagons.
p := 8;
q := 8;
F := FreeGroup("a","b","c");;
a := F.1;; b := F.2;; c := F.3;;
W := F / [a^2, b^2, c^2, (a*b)^p, (b*c)^q, (a*c)^2];;
# We want some status info as we go along...
SetInfoLevel(InfoFpGroup,2);
# Create a low index subgroups stream.
lix := LowIndexSubgroupsStream(W,TrivialSubgroup(W),120);;  # <-- DON'T
FORGET THE ';;' !!!
# retrieve the subgroups one by one
sub := GetNextLowIndexSubgroup(lix);
while not (sub = fail) do
# test sub to see if it has some desirable propety
  quo := W / Core(W,sub);
  gens := GeneratorsOfGroup(quo);
  g1 := Group(gens[1],gens[2]);
  g2 := Group(gens[2],gens[3]);
  if Size(g1)=16 and Size(g2)=16 and Size(Intersection(g1,g2))=2 then
    Print("Found!!\n");
    break;
  fi;
# test failed, so get the next subgroup
  sub := GetNextLowIndexSubgroup(lix);
od;


This returns an answer in 62 milliseconds on my machine.
Finding all the low index subgroups even only down to index 17 took
19328 milliseconds (and returned 4167 classes). Testing them took longer
still (54219 ms).

Since GAP is GPL, the attached code is also GPL.

Feature request : I also miss being able to ask for low index subgroups
of particular indices, not just all with index up to some limit, eg
"GAP, give me all subgroups of index 3,5 or 20."

Yorus, Mike H...

-------------- next part --------------
BEGIN:VCARD
VERSION:2.1
X-GWTYPE:USER
FN:Michael Hartley
ORG:University of Nottingham;Computer Science and IT
EMAIL;WORK;PREF;NGW:Michael.Hartley at nottingham.edu.my
N:Hartley;Michael
END:VCARD



More information about the Forum mailing list