# 61.19 Example of Double Coset Enumeration Strategies

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
April 1997