Categories for finite/permutation/symmetric groups

[nthiery]

This patch:

• Introduces two new categories: FiniteGroups? and FinitePermutationGroups?
• As a result, this standardizes the interface of those groups (cardinality, one, ...).

• 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 all named permutation groups, as well as GL and SL have UniqueRepresentation?,

• 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]).

• Due to the switch to UniqueRepresentation?, with:

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.

[nthiery]

Non finalized patch on:  http://combinat.sagemath.org/hgwebdir.cgi/patches/file/tip/trac_8044-categories_finite_groups-nt.patch

[nthiery]

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

[slabbe]

Applies over the precedent patch.

[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.

[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.

[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? Javier: could you look at the category part?

[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?

[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.

[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.

[nthiery]

Apply only this one

[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!

[jlopez]

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.