Opened 8 years ago

Closed 8 years ago

#8044 closed enhancement (fixed)

Categories for finite/permutation/symmetric groups

Reported by: nthiery Owned by: nthiery
Priority: major Milestone: sage-4.3.3
Component: group theory Keywords: Finite groups, permutation groups, symmetric groups
Cc: sage-combinat, vengoroso@… Merged in: sage-4.3.3.alpha0
Authors: Nicolas M. Thiéry Reviewers: David Joyner, Javier López Peña
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by nthiery)

This patch:

  • Puts all pari, permutation, and matrix groups in the corresponding categories. There remains to handle Galois groups in sage/rings/number_field/.
  • Deprecates the abstract class sage.groups.group.FiniteGroup?. Content moved to the FiniteGroups? category (see cayley_graph). It is not used anymore anywhere in Sage's library.
  • Merges cayley_graph with that for FiniteSemigroups?:
    • Generalization to any Semigroups with an elements option (should this be vertices?) to handle large/infinite semigroups
    • The call:

sage: G.cayley_graph(connecting_set = [a,b,c])

is deprecated in favor of:

sage: G.cayley_graph(generators = [a,b,c])

  • The following feature is removed:

sage: G.cayley_graph(connecting_set = a)

  • side = "right" is now the default (was "twosided" for semigroups).
  • Removed forcing implementation = "networkx" in the produced graph. Note: this changed the order of the edges, which required fixing a test in sage.graphs.generic_graphs (color_by_label)
  • Adds cool examples of Cayley graphs plots, courtesy of Sebastien Labbe
  • Provides group_generators defined from gens, as well as semigroup_generators defined from group_generators in the finite and coxeter cases.
  • Puts the SymmetricGroup? in the FiniteWeylGroups? category. Beware: as all Sage's permutation groups, this uses GAP's product convention coming from left-to-right composition of permutations, which can be surprising for combinatorists. Beware: the generators of SymmetricGroup?(n) are now its canonical Weyl group generators, namely the elementary transpositions
  • Adds an has_descent method to permutation group elements
  • Makes more systematic use of TestSuite?(...).run()
  • Makes a minor improvement to FiniteEnumeratedSets? tests for large finite enumerated sets
  • Strips away some unused imports
  • Updates a couple doctests here and there

Further debatable changes:

  • The underlying set of an alternating or symmetric group is now a tuple. This is safer and helps UniqueRepresentation?. However, this could break backward compatibility. Also, the repr is now of the form SymmetricGroup?((1,3,4)) instead of SymmetricGroup?([1,3,4]).

sage: F = GF(3); MS = MatrixSpace?(F,2,2) sage: gens = [MS(0,1],[1,0?),MS(1,1],[0,1?)] sage: G = MatrixGroup?(gens) sage: H = GL(2,F)

the following equality test fails:

sage: H == G True

Do we really want this feature? If yes, than the equality test inherited from UniqueRepresentation? will have to be fixed.

Attachments (2)

trac_8044_cayley_graph-sl.patch (3.3 KB) - added by slabbe 8 years ago.
Applies over the precedent patch.
trac_8044-categories_finite_groups-nt.patch (78.3 KB) - added by nthiery 8 years ago.
Apply only this one

Download all attachments as: .zip

Change History (16)

comment:2 Changed 8 years ago by nthiery

  • Description modified (diff)
  • Milestone set to sage-4.3.2
  • Status changed from new to needs_review
  • Summary changed from Categories for finite (permutation) groups to Categories for finite/permutation/symmetric groups
  • Type changed from defect to enhancement

comment:3 Changed 8 years ago by nthiery

  • Keywords symmetric added

The attached patch passes all tests on 4.3.1 + the sage-combinat patches already merged in 4.3.2: #7976 #7921 #7938 #8028 #8001 #5524

comment:4 Changed 8 years ago by nthiery

  • Description modified (diff)

Changed 8 years ago by slabbe

Applies over the precedent patch.

comment:5 Changed 8 years ago by slabbe

I just added a patch which adds some examples of cayley graphs.

It also adds FiniteGroup to the base classes of MatrixGroup_gap_finite_field.

comment:6 Changed 8 years ago by nthiery

  • Description modified (diff)

comment:7 follow-up: Changed 8 years ago by wdj

  • Reviewers set to wdj

Applies fine to 4.3.2.a0 and passes sage -t (except those 2 apparently singular-related tests which failed before).

I did not test sage -optional nor did I look carefully at how the category framework fits in with the rest of the category stuff (eg, Weyl groups). I did look at the permutation group aspect and positive review for that part. Was someone else going to look at the rest (Javier, vengoroso@…)? If not, please let me know.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 8 years ago by nthiery

  • Cc vengoroso@… added

Replying to wdj:

Applies fine to 4.3.2.a0 and passes sage -t (except those 2 apparently singular-related tests which failed before).

I did not test sage -optional nor did I look carefully at how the category framework fits in with the rest of the category stuff (eg, Weyl groups). I did look at the permutation group aspect and positive review for that part. Was someone else going to look at the rest (Javier, vengoroso@…)? If not, please let me know.

Thanks much for your review!

Florent: could you have a look at the Weyl group + Cayley graph part? David: did you check the matrix part? If not, do you mind handling it? Javier: could you look at the category part?

comment:9 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by wdj

Replying to nthiery:

Replying to wdj:

Applies fine to 4.3.2.a0 and passes sage -t (except those 2 apparently singular-related tests which failed before).

I did not test sage -optional nor did I look carefully at how the category framework fits in with the rest of the category stuff (eg, Weyl groups). I did look at the permutation group aspect and positive review for that part. Was someone else going to look at the rest (Javier, vengoroso@…)? If not, please let me know.

Thanks much for your review!

Florent: could you have a look at the Weyl group + Cayley graph part? David: did you check the matrix part? If not, do you mind handling it?

Yes, I looked at it and also give that part a positive review. I like the way you handled over different fields.

Javier: could you look at the category part?

comment:10 in reply to: ↑ 9 Changed 8 years ago by nthiery

Replying to wdj:

David: did you check the matrix part? If not, do you mind handling it?

Yes, I looked at it and also give that part a positive review.

Thanks!

I like the way you handled over different fields.

:-)

Being able to choose at run time the category, and therefore the class hierarchy, as we could do in MuPAD, was one of my big incentive for writing the category code, and going for dynamic classes.

comment:11 follow-up: Changed 8 years ago by jlopez

  • Reviewers changed from wdj to wdj, jlopez

The category part looks fine to me. This is an amazing patch, btw!

I am getting some doctests failures:

----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage/doc/en/tutorial/tour_advanced.rst"
        sage -t  "devel/sage/doc/fr/tutorial/tour_advanced.rst"
        sage -t  "devel/sage/sage/categories/finite_groups.py"
        sage -t  "devel/sage/sage/categories/finite_permutation_groups.py"
        sage -t  "devel/sage/sage/groups/pari_group.py"
        sage -t  "devel/sage/sage/groups/perm_gps/permgroup_named.py"
        sage -t  "devel/sage/sage/interfaces/r.py"
        sage -t  "devel/sage/sage/rings/polynomial/groebner_fan.py"
        sage -t  "devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py"

though they don't seem too serious.

There are a couple of "The category of (multiplicative) finite semigroups" in the docstrings that should be corrected.

For the rest, assuming that the doctest pass (it might be something with my sage, will try with a clean install at the office in a couple of hours), positive review.

Changed 8 years ago by nthiery

Apply only this one

comment:12 in reply to: ↑ 11 Changed 8 years ago by nthiery

Replying to jlopez:

The category part looks fine to me. This is an amazing patch, btw!

:-)

I am getting some doctests failures:

----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage/doc/en/tutorial/tour_advanced.rst"
        sage -t  "devel/sage/doc/fr/tutorial/tour_advanced.rst"
        sage -t  "devel/sage/sage/categories/finite_groups.py"
        sage -t  "devel/sage/sage/categories/finite_permutation_groups.py"
        sage -t  "devel/sage/sage/groups/pari_group.py"
        sage -t  "devel/sage/sage/groups/perm_gps/permgroup_named.py"
        sage -t  "devel/sage/sage/interfaces/r.py"
        sage -t  "devel/sage/sage/rings/polynomial/groebner_fan.py"
        sage -t  "devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py"

though they don't seem too serious. (it might be something with my sage, will try with a clean install at the office in a couple of hours),

For the record, could you please post or attach here the complete log of the failures, even if it works at your office?

There are a couple of "The category of (multiplicative) finite semigroups" in the docstrings that should be corrected.

Oops, good catch. The updated patch fixes this.

For the rest, assuming that the doctest pass positive review.

Thanks!

comment:13 Changed 8 years ago by jlopez

  • Status changed from needs_review to positive_review

All tests pass on a clean install, so most probably my previous failure was due to too much fiddling with patches and source files (will upload the failures later anyway). Postive review.

comment:14 Changed 8 years ago by mpatel

  • Merged in set to sage-4.3.3.alpha0
  • Resolution set to fixed
  • Reviewers changed from wdj, jlopez to David Joyner, Javier López Peña
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.