[GAP Forum] AllHomomorphismClasses too slow

[Hulpke,Alexander]

Dear Forum, Dear Ignat Soroko,

> I am trying to work with all homomorphisms from a finitely presented
> group to the symmetric groups of small degree. The following sequence
> of commands
> 
> F:=FreeGroup("a","b","c","d");;
> AssignGeneratorVariables(F);;
> rel:=[a*b*a*b^-1*a^-1*b^-1,b*c*b*c*b^-1*c^-1*b^-1*c^-1,c*d*c*d^-1*c^-1*d^-1,
> a*c*a^-1*c^-1,a*d*a^-1*d^-1,b*d*b^-1*d^-1,(a*b*c*d)^6];
> G:=F/rel;S3:=SymmetricGroup(3);
> AHC:=AllHomomorphismClasses(G,S3);
> 
> did not produce any result in more than 6 hours.

AllHomomomorphismClasses (which was added only to support a type of exercise posed in Gallian's Abstract Algebra textbook) will only terminate if both groups are finite. I will add a check and error message for this for future releases. In this way it is not an analog of magma's command for nonsurjective homomorphisms.

What exists, and has an effective implementation for finitely presented source groups, is a search for epimorphisms (i.e. surjective homomorphisms), this is provided by the operation `GQuotients`, and will work very quickly.

The reason for only offering a surjective version is that it is rare that one really searches for any homomorphism (and could not split it easily in multiple searches for surjective homomorphisms), the total number of homomorphisms (in particular with small images) might be unhandily large, and that restricting to surjective maps allows for further reduction of the search space.

The one exception is homomorphisms into the symmetric group. For this case, however, there is a complely different algorithm, `LowIndexSubgroups`, that finds all subgroups (up to conjugacy) up to a given index. From this, it is quick to determine their cores (kernels of the coset actions) and their intersections:

gap> l:=LowIndexSubgroups(G,3);;
gap> List(l,x->Index(G,x));
[ 1, 3, 2, 3, 3, 2, 3, 2, 3, 3 ]
gap> cores:=Unique(List(l,x->Core(G,x)));;  #Unique instead of Set, since sorting is expensive
gap> List(cores,x->Index(G,x));
[ 1, 6, 2, 3, 6, 2, 3, 2, 3, 3 ]
gap> c:=List(Combinations([2..10],2),x->Intersection(cores{x}));;
gap> cores:=Unique(Concatenation(cores,c));;
gap> List(cores,x->Index(G,x));
[ 1, 6, 2, 3, 6, 2, 3, 2, 3, 3, 18, 36, 12, 18, 18, 18, 6, 12, 4, 6, 6, 6, 18, 6, 9,
  6, 18, 18, 18, 6, 6, 6, 6, 6, 6 ]
gap> c:=List(Combinations([2..10],2),x->Intersection(cores{x}));;
gap> ForAll(c,x->x in cores);  # so nothing new and we can stop
true

Hope this helps,

   Alexander Hulpke