Re: [sage-combinat-devel] Canonical form for permutation groups

2013-04-11 Thread 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)  

-- 
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-combinat-devel] Canonical form for permutation groups

2013-04-10 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-combinat-devel] Canonical form for permutation groups

2013-04-10 Thread Nicolas M. Thiery 
On Thu, Apr 11, 2013 at 01:09:59AM +0200, Borie Nicolas 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.
> If I would have to do it myself, I will use the following process :
> a strong generating system (s.g.s.) identify uniquely a permutation
> group. building a s.g.s. is a polynomial algorithm and allow after
> to have a lot of nice features for close to free (cardinality,
> contains tests, ...). Unfortunately, a s.g.s is not unique but
> exploiting the fact that the lexicographic order is a total order
> over permutations, you can define a minimal s.g.s for a group. Now,
> two permutation groups (define by whatever : generators, list of
> elements, ...) would be isomorphic if and only if they have the same
> minimal s.g.s. (for information, the symmetric group of degree n S_n
> have s.g.s. of size maximum among all subgroup of S_n and you need
> to keep in memory binomial(n,2) permutations of size n).

If I understood Christian's question right, he does not only want to
test if the two groups are equals as sets of permutations, but if they
are isomorphic as groups. So for him the following groups generated by
permutations would all be "the same":

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

Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" 
http://Nicolas.Thiery.name/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-combinat-devel] Canonical form for permutation groups

2013-04-10 Thread Jason B. Hill 
Unfortunately, I think you will have to require specific conditions in
order to make a canonical form possible, even when considering a minimal
SGS as Nicolas suggests. The conditions are likely along the lines of
requiring a reduction to a primitive, or at least transitive, group. You
may also have to require that the group action be represented a specific
way.

For instance, with the example of S_6, one could consider the degree 6
natural action and obtain a strong generating set from a minimal base of
length 5 ... or one could consider the (right) regular representation of
S_6 acting on itself in degree 720 and obtain a minimal base of length 1
... which will give a substantially different base and strong generating
set. In either case, it's the same group ... but the action is defined
entirely differently. Determining the underlying group can be very
challenging.

The first place may be in constructing a composition series for the given
representation, which for permutation groups usually involves isomorphisms
to a primitive group of specific degree... it is the primitive
representations that are more easily classified up to a given degree. That
is, more than likely, the only place where such a canonical representation
has any hope in my mind.

Jason



On Wed, Apr 10, 2013 at 5:09 PM, Borie Nicolas  wrote:

> Le 10/04/2013 14:59, Christian Stump a écrit :
>
>  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.
>>
> If I would have to do it myself, I will use the following process : a
> strong generating system (s.g.s.) identify uniquely a permutation group.
> building a s.g.s. is a polynomial algorithm and allow after to have a lot
> of nice features for close to free (cardinality, contains tests, ...).
> Unfortunately, a s.g.s is not unique but exploiting the fact that the
> lexicographic order is a total order over permutations, you can define a
> minimal s.g.s for a group. Now, two permutation groups (define by whatever
> : generators, list of elements, ...) would be isomorphic if and only if
> they have the same minimal s.g.s. (for information, the symmetric group of
> degree n S_n have s.g.s. of size maximum among all subgroup of S_n and you
> need to keep in memory binomial(n,2) permutations of size n).
>
> I don't think this would be very hard to do it in sage as much of
> algorithm are already available in sage. To get a minimal s.g.s., you first
> compute a s.g.s. and the method strong_generating_system() is just wrapped
> from Gap inside Sage. After you can probably reduce it using from bottom to
> top by reducing permutations generating transversal fixing the n-first
> position using the (n+1)-th stabilizer group and the feature
> IntegerVectorModPermGroup already in Sage. Now, I do not much know about
> the complexity of all of that (I guess 10 seconds max until any subgroup of
> S_6 (98% of time will come from the fact that the Gap interface use
> pexpect)). This is not perfect and I am not a group expert. You really
> should ask on a Gap mailing list ; this proposition is just my small
> impression not really hard to test currently in Sage...
>
> Whit a clever algorithm I have in head (which doesn't use
> IntegerVectorModPermGroup), the reduction of an s.g.s. can be very very
> light in fact (just quadratic in the size of the s.g.s of the permutation
> group (i.e. (binomial(n,2)^2 in the worst case which is less than computing
> the non minimal s.g.s.))). So, if I don't say something wrong you can
> probably compute a minimal s.g.s. for any subgroup of S_15 in less than 10
> seconds even the interface with Gap is not perfect.
>
> Anyway, if you want to try my option (and nobody give an objection about
> what I propose), you should begin to read : http://en.wikipedia.org/wiki/*
> *Schreier%E2%80%93Sims_**algorithm
>
> Guys from Gap could also say my proposition is horrible for any reason I
> did not see yet...
>
> For general group, I think the memory needed would just be too much... Or
> you just keep small cardinality groups.
>
> Best regards,
> Nicolas B.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-combinat-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to 
> sage-combinat-devel+**unsubscr...@googlegroups.com
> .
> To post to this group, send email to sage-combinat-devel@**
> googlegroups.com .
> Visit this group at http://groups.google.com/**
> group/sage-combinat-devel?hl=**en
> .
> For more options, visit 
> https://groups.google.com/**groups/opt_out

Re: [sage-combinat-devel] Canonical form for permutation groups

2013-04-10 Thread Borie Nicolas 

Le 10/04/2013 14:59, Christian Stump a écrit :

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.
If I would have to do it myself, I will use the following process : a 
strong generating system (s.g.s.) identify uniquely a permutation group. 
building a s.g.s. is a polynomial algorithm and allow after to have a 
lot of nice features for close to free (cardinality, contains tests, 
...). Unfortunately, a s.g.s is not unique but exploiting the fact that 
the lexicographic order is a total order over permutations, you can 
define a minimal s.g.s for a group. Now, two permutation groups (define 
by whatever : generators, list of elements, ...) would be isomorphic if 
and only if they have the same minimal s.g.s. (for information, the 
symmetric group of degree n S_n have s.g.s. of size maximum among all 
subgroup of S_n and you need to keep in memory binomial(n,2) 
permutations of size n).


I don't think this would be very hard to do it in sage as much of 
algorithm are already available in sage. To get a minimal s.g.s., you 
first compute a s.g.s. and the method strong_generating_system() is just 
wrapped from Gap inside Sage. After you can probably reduce it using 
from bottom to top by reducing permutations generating transversal 
fixing the n-first position using the (n+1)-th stabilizer group and the 
feature IntegerVectorModPermGroup already in Sage. Now, I do not much 
know about the complexity of all of that (I guess 10 seconds max until 
any subgroup of S_6 (98% of time will come from the fact that the Gap 
interface use pexpect)). This is not perfect and I am not a group 
expert. You really should ask on a Gap mailing list ; this proposition 
is just my small impression not really hard to test currently in Sage...


Whit a clever algorithm I have in head (which doesn't use 
IntegerVectorModPermGroup), the reduction of an s.g.s. can be very very 
light in fact (just quadratic in the size of the s.g.s of the 
permutation group (i.e. (binomial(n,2)^2 in the worst case which is less 
than computing the non minimal s.g.s.))). So, if I don't say something 
wrong you can probably compute a minimal s.g.s. for any subgroup of S_15 
in less than 10 seconds even the interface with Gap is not perfect.


Anyway, if you want to try my option (and nobody give an objection about 
what I propose), you should begin to read : 
http://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm


Guys from Gap could also say my proposition is horrible for any reason I 
did not see yet...


For general group, I think the memory needed would just be too much... 
Or you just keep small cardinality groups.


Best regards,
Nicolas B.

--
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-combinat-devel] Canonical form for permutation groups

2013-04-10 Thread 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" 
http://Nicolas.Thiery.name/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[sage-combinat-devel] Canonical form for permutation groups

2013-04-10 Thread 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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.