[GAP Forum] IsomorphismPermGroup behaves nondeterministically?

[Max Horn]

Dear Ignat Soroko,

> On 24. Jul 2020, at 06:40, Ignat Soroko <ignat.soroko at gmail.com> wrote:
> 
> Hello everybody,
> 
> I have a finite quotient group Q of an infinite finitely presented
> group, which has order 2359296.

So Q is itself a finitely presented group, correct?

> I noticed that in different GAP
> sessions if I call IsomorphismPermGroup(Q) I get different results and
> different running times, ranging from
> 
> 1.2 seconds, modest memory usage, permutations of degree 64, to
> 25 min, 60Gb of memory(!) used, permutations of degree 192,
> and at some other times, I got permutations of degree 384.

Note that computing a permutation presentation for a finitely permutation group involves coset computations. You could try using "ACE" package, which installs an alternate coset enumerator, which may or may not improve performance. To do so, use 

  LoadPackage("ace");
  TCENUM:=ACETCENUM;

> 
> Is it an intended behavior or some sort of a bug?

Various algorithms in group theory are Monte Carlo or Las Vegas and as such rely on random choice
to produce their output; often these algorithms are very fast, but a bad random choice can indeed lead to a muuuch slower calculation. So in this regard this is "normal"

Then there are some algorithms which try one thing for a fixed amount of time, say 1 second; if that doesn't work, they try something else. Of course the behaviour of these algorithms also changes with the speed of your computer and also in general how busy your computer is doing other things.

Actually IsomorphismPermGroup for finitely presented groups falls into the latter category.


> Notice that I am not
> invoking a method SmallerDegreePermutationRepresentation, which is
> said to have randomized behavior.

It is by far not the only algorithm with random behaviour. Also, SmallerDegreePermutationRepresentation is itself called by some other functions.


> Is there a way to ensure
> deterministic results for this function which can be reproduced by
> others on different platforms?

You could set the random number generator to a specific seed before the calculation; and/or record the seed before the calculation so that others can reproduce it.

This won't help with code depending on timers. There is a way to change them to switch to
a fake deterministic timer, which we primarily added for our own use in automatic regression testing. I am reluctant to suggest it for regular use, but if you insist, you can activate this mode globally via

  SetUserPreference("ReproducibleBehaviour", true);

and turn it off again via

  SetUserPreference("ReproducibleBehaviour", false);


Best regards
Max