[GAP Forum] order of conjugacy classes?

[Max Horn]

Dear all,

> On 20. Jun 2022, at 09:45, Russ Woodroofe <rsw9 at cornell.edu> wrote:
> 
> 
> 
> Dear Keith, all,
> Did you try using
> Set(ConjugacyClassesMaximalSubgroups(G));
> ?
> 
> That sorts them by the < order (see 4.2 from the docs), and I believe that it should be consistent.  (I'm shocked that this isn't already applied -- you can check whether they are already sorted with IsSet.)

Defining a total ordering on conjugacy classes is very expensive -- at least in the generic case, it is implemented by converting the two classes into sets and comparing them element-wise, which of course is extremely inefficient and even infeasible for large classes.

A better algorithm would be to first compare some invariants (e.g. decide that short classes should come before longer; then that classes with smaller representative come first; etc.), but at some point you'll have two classes with equal length and even isomorphic representatives, and now you have to pick which one is "first". How do you do that? You could compute a "canonical" representative for each class and compare those, but then you still face the problem of computing that "canonical" representative (and if we are talking about classes of groups: how to order *group* generically).

In any case, this is not currently what GAP does. May point just is: what GAP does is relatively stupid, but it's not clear that you can do much better in general.

So in general this is a difficult problem. Since many (I'd even say: most) applications of conjugacy classes don't require such a sorting, GAP applies the best optimization one can apply to any given problem: just skip it. Don't slow down work of most people by trying to solve a hard problem they don't care about.

In this spirit, I propose that even if one wants a "fixed order", it is still best to not solve it by "sorting" but instead by modifying the setup to get GAP to produce a stable ordering from the start: The reason one gets different results for this computation (and many others in GAP) is that the algorithms being applied involved randomization; it's just a fact that many of the best algorithms in computational group theory are Las Vegas or Monte Carlo, and are fast *because* they use randomization.


So a possible workaround for Keith would be to reset the random number generator to a specific state before starting his computations. But careful: the state of the input groups also matter, so if e.g. a stabilizer chain was already computed (which also involves randomization), then the results will still differ. A way to avoid that would be to create a pristine new group with the same generators but no computed information...

That would suggest something like this, assuming G is the group you want to compute data about. (The code should work if G is a permutation group; for other kinds of groups, it may  be necessary to slightly tweak it, but I hope the gist is clear).

   # create a "pristine copy" of G
   H := GroupWithGenerators(GeneratorsOfGroup(G), One(G));
   # reset the random number generator state
   Reset(GlobalRandomSource, 0);;
   # compute classes in the copy
   cc := ConjugacyClassesMaximalSubgroups(H);;
   # Now either work with cc, or transfer it to G
   ccG := List(cc, c -> ConjugacyClassSubgroups(G, Representative(c)));
   SetConjugacyClasses(G, ccG);

One can write similar code for `ConjugacyClassesMaximalSubgroups` etc.

One caveat remains: if the algorithm employed by GAP changes, even with the above the resulting order could change. So, if you need long term reproducibility of your results, make sure to record and publish the precise version of GAP and any GAP packages you may have used.


A different "solution" would be to us an algorithm which is completely deterministic and in particular also does not depend on other possibly randomized data previously computed for the group. E.g. if G is a symmetric group in its natural permutation representation, then the conjugacy classes are well known and could be written down in a deterministic fashion.

But I don't know a way to do that in general.


Best wishes
Max