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

[Max Horn]

Dear Martin,

> On 19 Dec 2017, at 09:48, Martin Rubey <martin.rubey at tuwien.ac.at> wrote:
> 
> "Nicolas M. Thiery" <Nicolas.Thiery at u-psud.fr> writes:
> 
>> On Mon, Dec 18, 2017 at 01:57:04PM +0100, Martin Rubey wrote:
>>> I admit I am not completely sure right now: can we associate a conjugacy
>>> class of subgroups of S_n, isomorphic to the Weyl group, in a sensible
>>> way to a finite Cartan type?
>> 
>> The permutation action on the roots would be a rather natural choice.
>> This could be extended to affine Weyl groups using affine
>> permutations.

Note that even different (finite) Cartan types can lead to isomorphic Weyl
groups, unless you restrict to irreducible ones. And if you also permit
infinite Weyl groups, then even for the irreducible ones, there are pairs of
different irreducible types which have isomorphic Weyl groups; but from all
you write, I guess you are only interested in finite groups.

But of course they induce distinct "permutation isomorphism classes", to use
the nomenclature Thomas' described. Which to me suggests that what Thomas
describes really is a better fit for what you want to do.


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". But OK, that can be done, perhaps you
are even doing it already.

But now to identify permutation group with your "canonical form", you need
to solve a subgroup conjugacy problem, which can be hard.

Moreover, it is not clear to me how to, given a permutation group, you'd
compute its "canonical form" intrinsically (i.e. other than going through
your whole database, then trying to compute a permutation isomorphism with
each "canonical form" in the database, which of course is kinda against the
whole point in defining a canonical form in the first place.)

So I'd be very hesitant to call this a "canonical form", because to me, the
name suggests that it should be possible to compute it intrinsically (i.e.
w/o referring to a big table of "canonical forms"), and somewhat efficiently
(as otherwise, there is little use).  Of course that's just my point of
view, you can disagree, but then I wonder what the point behind having those
"canonical forms" really is?


> 
> Indeed! This leaves the question whether there we can compute a
> canonical form for permutation groups up to conjugacy.  I just noticed
> that this is a mathoverflow question, too:
> 
> https://mathoverflow.net/q/90107/3032
> 
> Unfortunately, as of today it doesn't have a straight answer, but maybe
> things have changed?

No. This is still an incredibly tough problem.


Cheers,
Max