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
_______________________________________________
Forum mailing list
[email protected]
https://mail.gap-system.org/mailman/listinfo/forum
