Canonical form for permutation groups

[Christian Stump]

Hi,

I wonder if there is a way to get a canonical form of a subgroup of a
permutation group (or, even better, any group). This would be
something like a method "canonical_labeling" for permutation groups
that returns an isomorphic permutation group, and such that two groups
are isomorphic if and only if their "canonical labellings" coincide.

I don't think anything like that is currently implemented, right?

A "natural" implementation would be to compute the multiplication
table of the group, apply the canonical form algorithm from graphs (by
simultaneous row and column permutations of the multiplication table),
obtain a canoncial form of the multiplication table, and turn this
data into a canonical form of a permutation group.

@Nathann et al.: would this be doable without too much effort from the
current algorithm for graphs? How far is the current implementation
from the possibility to take any n*n array (or square matrix, but with
no/less restrictions on the entries) and get it into a canonical form
by simultaneous row and column permutations?

Cheers, Christian

[Volker Braun]

Clearly there is no canonical form for arbitrary groups/subgroups since there is no algorithm to compare finitely generated groups. For finite groups there is, of course. In GAP one would just IdGroup() to get a unique label. A GPL-ed clone of the finite groups database in GAP would be nice, then we could distribute it by default...

[Nicolas M. Thiery]

Hi Christian,

On Wed, Apr 10, 2013 at 07:59:49AM -0500, Christian Stump wrote:
> I wonder if there is a way to get a canonical form of a subgroup of a
> permutation group (or, even better, any group). This would be
> something like a method "canonical_labeling" for permutation groups
> that returns an isomorphic permutation group, and such that two groups
> are isomorphic if and only if their "canonical labellings" coincide.
>
> I don't think anything like that is currently implemented, right?

Not that I know of. I would suggest to ask on the GAP mailing list if
something like this is implemented in GAP.

> A "natural" implementation would be to compute the multiplication
> table of the group, apply the canonical form algorithm from graphs (by
> simultaneous row and column permutations of the multiplication table),
> obtain a canoncial form of the multiplication table, and turn this
> data into a canonical form of a permutation group.

You need to act not only on rows and columns but also on the values in
the table, don't you?

That being said, it should indeed be possible to handle this problem
by encoding the product as a ternary relation (a,b,ab), and encoding
the ternary relation itself using a graph. Something like:

Vertices: elements a of G, and pairs (a,b) of elements of G

Edges: a -> (a,b) with edge label "left"
b -> (a,b) with edge label "right"
(a,b) -> ab with edge label "result"
Loops: (a,b) -> (a,b)

The loops are just here to distinguish the two kinds of vertices; one
could instead specify a vertex bipartition to the canonical labeling
function.

Note that the above would work for any semigroup or even magma. But
one could hope for something vastly more efficient for groups.

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[John Cremona]

It may be relevant to look at the canonical labelling used for Galois
grousp (see for example http://www.lmfdb.org/GaloisGroup/ and click on
the word "label").

John

> Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
> http://Nicolas.Thiery.name/
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Christian Stump]

> In GAP one would just IdGroup() to get a unique label.

Is this given for any finite group in GAP, or is this depending on
http://www.gap-system.org/Packages/sgl.html ? It looks like there is
not much to do beyond these IdGroup in Sage since I guess they would
have gone beyond n=22 in Gap otherwise). On sage-devel, John Cremona
was basically suggesting the same as a unique labelling for small
groups.

> - < (1,2) >
> - < (2,3) >
> - < (1,2)(3,4) >
> - the multiplicative group ({-1,1}, *).

That is right, these should all result in the same group... and yes, I
forgot to add the action on the entries of the multiplication table.
So some canonical generating system on a particular subgroup of a
finite permutation group would not be enough.

Cheers, Christian

[Dima Pasechnik]

On Wednesday, 10 April 2013 20:59:49 UTC+8, Christian Stump wrote:

Hi,

I wonder if there is a way to get a canonical form of a subgroup of a
permutation group (or, even better, any group). This would be
something like a method "canonical_labeling" for permutation groups
that returns an isomorphic permutation group, and such that two groups
are isomorphic if and only if their "canonical labellings" coincide.

I don't think anything like that is currently implemented, right?

A "natural" implementation would be to compute the multiplication
table of the group, apply the canonical form algorithm from graphs (by
simultaneous row and column permutations of the multiplication table),
obtain a canoncial form of the multiplication table, and turn this
data into a canonical form of a permutation group.

no, no, that's not what you want to do, certainly. A much more efficient way

is to compute a strong generating set w.r.t. a "canonical" minimal base.

(A base of a permutation group  is a tuple of points (s_1,...,s_t) s.t. each group element g

is uniquely defined by (g(s_1),...,g(s_t))).

[Jason B. Hill]

no, no, that's not what you want to do, certainly. A much more efficient way

is to compute a strong generating set w.r.t. a "canonical" minimal base.

data into a canonical form of a permutation group.

There is no "canonical" minimal base, unless one specifies the group action to such an extent that most permutation group representations are excluded.

Seriously, if you need some sort of canonical form for permutation groups, you must restrict to primitive actions. In the real world, this just isn't a sensible approach. Each abstract group has infinitely many permutation group representations. ONLY the primitive representations are currently classified in any detail below a given degree, and as such those are the only canonical representations that would even be available.

Jaosn

[Dima Pasechnik]

On 2013-04-11, Jason B. Hill <ja...@jasonbhill.com> wrote:
> --e89a8f64674d73946104da0e3a61
> Content-Type: text/plain; charset=ISO-8859-1

perhaps a more sensible idea for a canonical form would be via
centralizer algebras. Centralizer algebras are easy to construct, and
checking that two of them are isomorphic is indeed a kind of coloured
graph isomorphism, except that the size of objects has a much nicer
dependence on the group order --- if we talk about transitive
permutation groups, at least.
In most cases you will have a suborbit on which the point stabilizer
acts faithfully, so this provides you some sort of reduction.
The full permutation group isomorphism test is still not there,
but this looks like a good way to limit the possible choices.

Dima

>
> Jaosn
>

[Volker Braun]

On Thursday, April 11, 2013 2:49:10 AM UTC+1, Christian Stump wrote:

> In GAP one would just IdGroup() to get a unique label.

Is this given for any finite group in GAP, or is this depending on
http://www.gap-system.org/Packages/sgl.html ?

This depends on the small groups library. IdGroup() returns the group's label in the sgl. The label is a pair (order, consecutive integer).

Identification is done by computing various invariants (e.g. Abelian, Solvable, Nilpotent, ...) and then doing isomorphism tests for the remaining possibilities. Plus extra rules for special classes of groups (e.g. if the order is a product of three primes)