[sage-combinat-devel] Canonical form for permutation groups
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.
[sage-combinat-devel] Re: Canonical form for permutation groups
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... On Wednesday, April 10, 2013 1:59:49 PM UTC+1, 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. @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.
Re: [sage-combinat-devel] Free Algebra Element
I doubt this has ever worked: In fact, my message was not clear. I test if type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement With older versions, type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement which is not the case anymore. But your advice is good, thanks ! Matthieu De : Nicolas M. Thiery nicolas.thi...@u-psud.fr À : sage-combinat-devel@googlegroups.com Envoyé le : Mercredi 10 avril 2013 15h33 Objet : Re: [sage-combinat-devel] Free Algebra Element Bonjour Matthieu, On Wed, Apr 10, 2013 at 02:15:20PM +0100, Matthieu Deneufchatel wrote: Do I miss something or is there a bug : sage: R.a,b=FreeAlgebra(QQ,2) sage: a*b a*b sage: type(a*b) class 'sage.algebras.free_algebra_element.FreeAlgebra_generic_with_category.element_class' sage: type(a*b)==sage.algebras.free_algebra_element.FreeAlgebra_generic_with_category.element_class --- AttributeError Traceback (most recent call last) /home/deneufchatel/ipython console in module() AttributeError: 'module' object has no attribute 'FreeAlgebra_generic_with_category' The same code used to give something consistent with older versions of Sage (4.8 ?). I doubt this has ever worked: the class FreeAlgebra_generic_with_category is generated on the fly to add generic code from the categories to the code of FreeAlgebra and FreeAlgebraElement. For details, see: http://www.sagemath.org/doc/reference/categories/sage/categories/category.html On the other hand you can do something like: sage: type(a*b) == R.element_class Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net 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. -- 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] Free Algebra Element
On Wed, Apr 10, 2013 at 06:05:35PM +0100, Matthieu Deneufchatel wrote: I doubt this has ever worked: In fact, my message was not clear. I test if type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement With older versions, type(a*b) == sage.algebras.free_algebra_element.FreeAlgebraElement which is not the case anymore. Ok, this makes sense! So what has changed in Sage is that FreeAlgebra now uses categories which was not the case before. Note that the following still holds: sage: isinstance(a*b, sage.algebras.free_algebra_element.FreeAlgebraElement) Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net 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
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
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 pout...@gmail.com 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_**algorithmhttp://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.comsage-combinat-devel%2bunsubscr...@googlegroups.com . To post to this group, send email to sage-combinat-devel@** googlegroups.com sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/** group/sage-combinat-devel?hl=**enhttp://groups.google.com/group/sage-combinat-devel?hl=en . For more options, visit
Re: [sage-combinat-devel] Canonical form for permutation groups
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 nthi...@users.sf.net
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] The reading tableau of a partition
Good Morning! I have been distracted from sage for quite some time but this morning I started playing again and I came across the *reading_tableau *method of a partition. The documentation for this method reads: Return the reading tableau of the reading word under the Robinson-Schensted correspondence of the (standard) tableau `T` labeled down (in English convention) each column to the shape of ``self``. For an example of the tableau `T`, consider the partition `\lambda = (3,2,1)`, then we have:: 1 4 6 2 5 3 For more, see :func:`~sage.combinat.rsk.RSK()`. EXAMPLES:: sage: Partition([3,2,1]).reading_tableau() [[1, 3, 6], [2, 5], [4]] The example in the text and the example that is doc-test appear to disagree. My guess is that the example in the text is what is expected. Is this right? [In 5.8 the behaviour is as in the doc-test.] I suspect that this may have changed when partitions were made to play nicely with categories as I think that the order in which the partitions are generated may have changed then. All this aside, if some one can confirm that this is a bug then I will file a ticket, and probably even a patch. Andrew -- 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
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.
[sage-combinat-devel] Re: Canonical form for permutation groups
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))). @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.
