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.

CC: @sagetrac-sage-combinat [email protected]

Component: group theory

Keywords: Finite groups, permutation groups, symmetric groups

Author: Nicolas M. Thiéry

Reviewer: David Joyner, Javier López Peña

Merged: sage-4.3.3.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/8044

[nthiery]

comment:1

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

[nthiery]

Changed keywords from Finite groups, permutation groups to Finite groups, permutation groups, symmetric groups

[nthiery]

comment:3

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

[seblabbe]

Applies over the precedent patch.

[seblabbe]

comment:5

Attachment: trac_8044_cayley_graph-sl.patch.gz

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.

[wdjoyner]

comment:7

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, [email protected])? If not, please let me know.

[wdjoyner]

Reviewer: wdj

[nthiery]

comment:8

Replying to @wdjoyner:

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, [email protected])? 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?

[wdjoyner]

comment:9

Replying to @nthiery:

Replying to @wdjoyner:

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, [email protected])? 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]

comment:10

Replying to @wdjoyner:

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.

[sagetrac-jlopez]

comment:11

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.

[sagetrac-jlopez]

Changed reviewer from wdj to wdj, jlopez

[nthiery]

Attachment: trac_8044-categories_finite_groups-nt.patch.gz

Apply only this one

[nthiery]

comment:12

Replying to @sagetrac-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!

[sagetrac-jlopez]

comment:13

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.

[qed777]

Changed reviewer from wdj, jlopez to David Joyner, Javier López Peña

[qed777]

Merged: sage-4.3.3.alpha0