[GAP Forum] IsomorphismPermGroup behaves nondeterministically?

[Ignat Soroko]

Dear Max and Alexander,

Thank you for useful information and insights. It is good to know that
it is not an error and how to deal with it if I need a different
effect.

Best,
Ignat
https://www.math.lsu.edu/~ignatsoroko/

On Fri, Jul 24, 2020 at 10:34 AM Hulpke,Alexander
<Alexander.Hulpke at colostate.edu> wrote:
>
> Dear Forum, Dear Ignat Soroko,
>
> It is intended behavior, because (pseudo-)random elements are used. If you need reproducable results you would have to store the random seed, as Max Horn described.
>
> Currently, the default method for `IsomorphismPermGroup` for finitely presented groups (that is, if such a homomorphism has not yet been stored) is as follows:
>
> If the group does not yet know its `Size`, GAP takes subgroups generated by random elements and tries to have a coset enumeration complete. If this works (within the set parameters), it rewrites the presentation to the subgroup (easy, since cyclic, and will give subgroup order) and calculates the group order as product of subgroup index and subgroup order. It also has (from the coset table) a permutation representation on the cosets, and can check whether it is faithful.
>
> If the size is already known, or the permutation representation obtained this way is not faithful or of too large degree, it tries coset representations on subgroups generated b a few random elements, until it finds a faithful permutation rep (which might be regular).
>
> Finally `SmnallerDegreePermutationRepresentation` (with option `cheap`) is called to reduce the degree.
>
> The result thsu is heavily dependent on the random seed.For larger groups this whole process also might be more memory intensive.
>
> What you can do to speed things up is to use `SetSize(Q, 2359296);` if Q does not yet know its size.
>
> I have used other strategies in the past for finding permutation representations. A good one is calling:
>
> l:=LowIndexSubgroups(Q,20); # or whatever index works well
> k:=Intersection(l);
> q:=DefiningQuotientHomomorphism(k);
>
> and to check whether `Size(Image(q))` is correct -- then q is faithful, and you could store it with `SetIsomorphismPermGroup`.
>
> Even if q is not faithful, you could try to take a subgroup u of Image(q) of moderate index (using permutation group tools) and then try whether
>
> sub:=LargerQuotientBySubgroupAbelianization(q,u);
>
> returns a subgroup (not fail) and if so set
>
> k:=Intersection(k,sub);
> q:=DefiningQuotientHomomorphism(k);
>
> and repeat.
>
> The problem with implementing this approach for a generic method is that it can perform horribly badly for some particular cases, e.g. certain solvable groups or Schur Covers, and I can't think of a good heuristic to decide a priory if this alternate method is worth trying.
>
> Best,
>
>   Alexander Hulpke
>
> -- Colorado State University, Department of Mathematics,
> Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
> email: hulpke at colostate.edu,
> http://www.math.colostate.edu/~hulpke
>