[GAP Forum] Canonical form for some small groups and efficient characterisation of the generalized symmetric groups

[Rubey Martin]

>>>>> The permutation action on the roots would be a rather natural choice.
>>
>>> Regarding Nicolas' suggestion: While it is a "natural" choice, it is not
>>> necessarily a "canonical" choice. At the very least, you'd have to define
>>> how to label the roots "canonically".
>>
>> let me ask: are you saying that that there are both "bad" but also
>> "canonical labellings" of the roots?  (let's consider only finite type)
>>
>> Or put differently: do you have an example at hand where different labellings
>> of the roots yield non-conjugate permutation groups?

> No, that's not what I meant. Of course any labeling with numbers 1..n can be
> transformed into any other by a permutation, hence the resulting permutation
> groups are conjugate in Sym(n).

> Thus any choice of such a labeling determines a conjugacy class -- but
> *only* that. It does not determine a representative of such a class.

This is *very* reassuring - I was hoping for that and a bit puzzled by what just
turned out to be a misunderstanding on my part.

> The question then is: How useful is that? Since you are talking about a
> database and finding things in it, I assumed you wanted a "canonical form"
> which is a string, or perhaps a tuple of integers and strings, or something
> "simple" like that. A conjugacy class of subgroups isn't that, though.

There are two questions:

* should findstat have a collection "finite groups" (up to isomorphism),
   and if so, is it possible?
* should findstat have a collection "permutation groups" (up to conjugacy),
   and if so, is it possible?

To answer the "should" part, I need to consider whether there are "natural,
interesting" maps between other collections (that should be) in the database
(currently or in future) and the collection I am proposing right now,
"finite groups" (or "permutation groups").

As it turns out that the maps I had in mind so far actually all make sense for
permutation groups (up to conjugacy), in particular the automorphism group
of a graph and the map from a finite Cartan type to its Weyl group.

This is the good news. (In the sense that it opens up a new possibility!)

The bad news is that there is apparently no canonical form for permutation
groups up to conjugacy.

Indeed, the best thing would be what you called an "intrinsic" canonical form:
a function f: permutation groups up to conjugacy -> strings such that

* f(G) can be computed in sensible time
* f(G) = f(H) if and only if G and H are conjugate

It would be even better, if

* f has an inverse, that is, I can reconstruct G from f(G) in reasonable time
* f(G) is human readable

In principle it should be possible to get by even without a canonical form,
replacing it with a check for equality (in the case at hand: conjugacy), but
that would be an awful lot of work, both technically and socially - not
everybody in the findstat team is a big fan of having groups as a collection.

To make "sensible time" a little more concrete, it would be completely OK
to compute the canonical form of the smallest 1000 groups in about a minute.
For graphs it takes 15 seconds on my laptop.

Thank you for your interest!

Martin