We look at a presentation for the sporadic group Fi_{22}, given by the Coxeter diagram:
put(0,1.4)line(1,0)2 multiput(0,1.4)(1,0)3circle0.1 put(2.7,2.1)circle0.1 put(3.7,2.1)circle0.1 put(4.4,1.4)circle0.1 put(2.7,0.7)circle0.1 put(3.7,0.7)circle0.1 put(4.4,0)circle0.1 put(2,1.4)line(1,1)0.7 put(2,1.4)line(1,-1)0.7 put(2.7,2.1)line(1,0)1 put(2.7,0.7)line(1,0)1 put(3.7,2.1)line(1,-1)0.7 put(3.7,0.7)line(1,1)0.7 put(3.7,0.7)line(1,-1)0.7 put(0,1.55)makebox(0,0)[b]scriptstyle(1,2) put(1,1.55)makebox(0,0)[b]scriptstyle(2,3) put(2.1,1.55)makebox(0,0)[br]scriptstyle(3,4) put(2.7,2.25)makebox(0,0)[b]scriptstyle(4,5) put(3.7,2.25)makebox(0,0)[b]scriptstyle(5,6) put(4.5,1.45)makebox(0,0)[l]scriptstyle(6,7) put(2.7,0.6)makebox(0,0)[t]a put(4.5,0)makebox(0,0)[l]g put(3.7,0.6)makebox(0,0)[tr]f
with the additional relation (f(4,5)(6,7)(3,4)(5,6)a)^4 =1 (the ``hexagon'' relation).
As indicated by the labels on the diagram we take K=S_7. The subgroup generated by all the nodes except the left-most has index 3510. An enumeration over that subgroup is coded as:
gap> k := SymmetricGroup(7);
Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) )
gap>
gap> aname := AbstractGenerator("a");; a := DCEWord(k,aname);
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[a])
gap> fname := AbstractGenerator("f");; f := DCEWord(k,fname);
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[f])
gap> gname := AbstractGenerator("g");; g := DCEWord(k,gname);
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[g])
gap>
gap> hexagon := (f*DCEWord(k,(4,5)*(6,7)*(3,4)*(5,6))*a)^4;
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7),
(6,7) ),[f, (3,4,6,7,5), a])^4
gap> hexagon.name := "hex";
"hex"
gap>
gap> rel1 := (a*DCEWord(k,(3,4)))^3;
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[a, (3,4)])^
3
gap> rel2 := (f*DCEWord(k,(6,7)))^3;
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[f, (6,7)])^
3
gap> rel3 := (a*g)^2;
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[a, g])^2
gap> rel4 := (f*g)^3;
DCEWord(Group( (1,7), (2,7), (3,7), (4,7), (5,7), (6,7) ),[f, g])^3
gap>
gap> F22Pres := rec(
> groupK := k,
> gainGroups := [ rec(), rec(dom := 7, op := OnPoints),
> rec(dom := [1,2,3], op := OnSets)],
> gens := [ rec( name := aname, invol := true, wgg := 3),
> rec (name := fname, invol := true, wgg := 2),
> rec (name := gname, invol := true, wgg := 1)],
> relators := [rel1,rel2,rel4,rel3,hexagon],
> subgens := [(2,3,4,5,6,7),(3,2),f,a,g] );;
HLT Strategy
As given, this presentation will use the default HLT strategy. On a SparcStation 10-41 this enumeration takes 60.8 CPU seconds and defines a total of 95 double cosets (for a final total of 24).
Since we know the correct index in this example, we can use early-closing, by setting
gap> F22Pres.strategy := rec(EC := [3510]);
rec(
EC := [ 3510 ] )
gap> DCE(F22Pres);
#I Set up generators and inverses
#I Set up column structure: 43 columns
#I Pre-processed relators
#I Done subgroup generators
#I Also done relators in subgroup
#I Pushing at weight 3
#I 1 double 7 single 2 blanks
#I 1 DCEWord(K,[a, (3,4)])^3
#I 4 cases
...
The calculation proceeds identically until, after 40 seconds, it reaches a table with 3510 single cosets and only four blank entries. The program then changes strategies and attempts to fill the blanks as seen in the following piece of output:
...
#I 13 hex
#I 70 cases
#I 22 DCEWord(K,[a, (3,4)])^3
#I 39 cases
#I 22 DCEWord(K,[f, (6,7)])^3
#I 9 cases
#I 22 DCEWord(K,[f, g])^3
#I 3 cases
#I 22 DCEWord(K,[a, g])^2
#I 8 cases
#I 15 hex
#I 90 cases
#I Entering Pre-early closing 24 3510 4
#I 48 DCEWord(K,[a, (3,4)])^3
#I 29 cases
#I 48 DCEWord(K,[f, (6,7)])^3
#I 5 cases
<< Double coset table "No name" early-closed 24 double 3510 single >>
This succeeds after a further 2 seconds, producing a closed table. This method actually defines more double cosets (97), but is much faster.
We can cause the change of strategies to occur a little earlier by widening the range of acceptable indices. With:
gap> F22Pres.strategy := rec(EC := [3500..3600]);
rec(
EC := [ 3500 .. 3600 ] )
gap> u := DCE(F22Pres);
#I Set up generators and inverses
#I Set up column structure: 43 columns
#I Pre-processed relators
#I Done subgroup generators
#I Also done relators in subgroup
#I Pushing at weight 3
#I 1 double 7 single 2 blanks
#I 1 DCEWord(K,[a, (3,4)])^3
#I 4 cases
...
With this option we see:
...
#I 13 hex
#I 70 cases
#I Entering Pre-early closing 24 3516 18
#I 22 DCEWord(K,[a, (3,4)])^3
#I 39 cases
#I 22 DCEWord(K,[f, (6,7)])^3
#I 9 cases
#I 22 DCEWord(K,[f, g])^3
#I 3 cases
#I 22 DCEWord(K,[a, g])^2
#I 8 cases
#I 22 hex
#I 130 cases
#I 22 DCEWord(K,[a, a])
#I 8 cases
#I 22 DCEWord(K,[f, f])
#I 3 cases
#I 22 DCEWord(K,[g, g])
#I 1 cases
#I 36 DCEWord(K,[a, (3,4)])^3
#I 39 cases
#I 36 DCEWord(K,[f, (6,7)])^3
#I 9 cases
#I 36 DCEWord(K,[f, g])^3
#I 3 cases
#I 36 DCEWord(K,[a, g])^2
#I 8 cases
#I 36 hex
#I 130 cases
<< Double coset table "No name" early-closed 24 double 3510 single >>
and a run time of about 37 seconds.
Apart from the early-closing criteria, we can tune the behaviour of the HLT algorithm by varying the relator weights. We can see the default weights by doing:
gap> List(u.relators,r->[r,r.weight]);
[ [ DCEWord(K,[a, (3,4)])^3, 2 ], [ DCEWord(K,[f, (6,7)])^3, 2 ],
[ DCEWord(K,[f, g])^3, 2 ], [ DCEWord(K,[a, g])^2, 2 ], [ hex, 3 ],
[ DCEWord(K,[a, a]), 100 ], [ DCEWord(K,[f, f]), 100 ],
[ DCEWord(K,[g, g]), 100 ] ]
The relators with weight 100 are simply added automatically to ensure that the algorithm cannot terminate without closing the table.
We could emulate the unweighted HLT algorithm by setting
hexagon.weight:= 2;
This produces significantly worse performance, as the long hexagon relation is pushed more often than necessary. On the other hand increasing its weight to 4 also produces worse performance than the default, because unnecessarily much of the infinite hyperbolic reflection group (defined by the other relations) is constructed.
Felsch Strategies
We can try this presentation with the Felsch strategy by simply setting:
F22Pres.strategy := rec(whichStrategy := "Felsch",EC := [3500..3600]);
Using this strategy the enumeration takes longer (92 seconds), but
defines only 35 double cosets in total. The Felsch algorithm can often be
improved by adding the longer relators as redundant subgroup
generators. We can try this by setting hexagon.insg := true; but the
improvement is very slight (to 91 seconds and 35 double cosets).
Hybrid strategy
We can access the hybrid methods be setting
F22Pres.strategy.whichStrategy := "Havas";
We first look at the preferred definition list alone, by setting
gap> strat := F22Pres.strategy;
rec(
EC := [ 3500 .. 3600 ] )
gap> strat.FF := 5;
5
gap> strat.HavN := 100;
100
gap> strat.HavK := 0;
0
This turns out to be significantly worse than the simple Felsch
algorithm, defining 56 double cosets and taking 145 seconds. Smaller
values for FF produce performance closer to the simple Felsch.
By setting
gap> strat.FF := 1;
1
gap> strat.HavN := 5;
5
gap> strat.HavK := 2;
2
We can try a hybrid strategies (without the PDL). This runs in about 100 seconds, making 41 definitions.
GAP 3.4.4