Add the set of PrimitiveGroups

[sagetrac-trehn]

This patch implements the finite enumerated set of primitive permutation groups of a given degree, and the infinite enumerated set of all primitive permutation groups. It is based on the work done in #8500 for transitive permutation groups.

This allows a user to do:

sage: PrimitiveGroups(4).cardinality()

sage: for G in PrimitiveGroups(i):
...       any_test(G)  # any test over all primitive groups of a given degree

sage: for G in PrimitiveGroups():
...       other_test(G) # test over all primitive groups

This requires the optional database_gap which contains all the primitive permutation groups of degree <= 2499. Therefore, in practice, the enumeration stops with a NonImplementedError?

Apply attachment: trac_12407_primitive_permutation_groups.patch, attachment: trac_12407_review.patch, attachment: trac_12407_fix_testcases.patch

Component: group theory

Keywords: primitive groups

Author: Thomas Rehn

Reviewer: Vincent Delecroix, Volker Braun

Merged: sage-5.6.beta1

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

[videlec]

Reviewer: vdelecroix

[videlec]

comment:2

Hi,

Nice patch (I will need it ;-)).

0. The primitive groups are up to isomorphism which is not mentioned in the documentation!

1. Why do you use a specific class PrimitiveGroup? The simpler

sage: PermutationGroup(gap_group = gap.PrimitiveGroup(7,3))
Permutation Group with generators [(2,4,6)(3,5,7), (1,2,4,3,6,7,5)]

seems more natural to me. The only modifications I see in your new class are the inheritance from UniqueRepresentation and the method _repr_ (see also remark 3 below) and the inheritance from UniqueRepresentation.

2. To be complient with GAP you decide to start numerotation from 1 which, from my point of view, is better. However, there can be some confusion with Python convention of starting list from 0. In particular the following behavior may appear strange:

sage: P=PrimitiveGroups(4)
sage: p=P[2]
sage: p
Primitive group number 2 of degree 4
sage: P.rank(p)
1
sage: P.unrank(1)     
Primitive group number 2 of degree 4

Could you make it explicit in the documentation?

3. The names provided by GAP are by far more useful than "Primitive group number x of degree y":

sage: gap.PrimitiveGroup(3,2)
S(3)
sage: gap.PrimitiveGroup(5,2)
D(2*5)
sage: gap.PrimitiveGroup(10,3)
PSL(2, 9)

What do you think?

4. Moreover, GAP provides a very nice function to identify groups in the database

sage: P=PermutationGroup(('(4,5)(6,7)(8,9)(11,12)', '(1,2,3,4,6,8,10,5,7,11,9)'))
sage: P
Permutation Group with generators [(4,5)(6,7)(8,9)(11,12), (1,2,3,4,6,8,10,5,7,11,9)]
sage: gap.PrimitiveIdentification(P)
2
sage: gap.PrimitiveGroup(12, 2)
M(12)

Could you implement it as a method of PermutationGroup? For sure, if you decide to keep the class PrimitiveGroup the method should be overwritten. Notice that the method .group_id() and aliased as .id() of PermutationGroup returns the index of G in the database of all permutation groups. The method for primitive groups could hence be named group_id_primtive() aliased as .id_primitive().

[sagetrac-trehn]

comment:3

Thank you very much for your feedback. I think I can improve these issues.

For consistency I probably would also have to change the TransitiveGroups code, which I took as a basis for copy-and-paste.

[sagetrac-trehn]

comment:4

I decided to keep the PrimitiveGroup class because it is a convenient way to get a specific primitive group. Moreover, I updated the documentation and included the "GAP name" into repr. Now there also is a 'primitive_id()' method of PermutationGroup.

[videlec]

comment:5

Hello,

0. There are trailing whitespaces in your file (spaces at the end of the lines) that should be removed. All EXAMPLES statements should end with '::' and a whiteline. Otherwise the examples are not well compiled in the documentation. You put only one ':' at two places (line 1288, 1296). At many places in the file permgroup_named this is the case... I asked a question about this on sage-devel (http://groups.google.com/group/sage-devel/browse_thread/thread/110e8595c86a62b)

1. At the very begining of the file permgroup_named.py there is a list of all available groups. You should add yours.

2. In my previous remark 4), I claim that you should remove the very long "number x of degree y" as its mathematical content is irrelevant. As you can see the following list is ugly

sage: PrimitiveGroups(5).list()
[C(5), primitive group number 1 of degree 5, D(2*5), primitive group number 2 of degree 5, AGL(1, 5), primitive group number 3 of degree 5, A(5), primitive group number 4 of degree 5, S(5), primitive group number 5 of degree 5]

whereas calling gap directly we get the nicer

sage: [gap.PrimitiveGroup(5,i) for i in xrange(1,6)]
[C(5), D(2*5), AGL(1, 5), A(5), S(5)]

3. My previous remark 2) about naming convention is more dedicated for the documentation of PrimitiveGroups, PrimitiveGroupsAll and PrimitiveGroupsOfDegree than for PrimitiveGroup. As if a Sage user needs it, it would be before the group is created!

4. In the examples of PrimitiveGroupsOfDegree, the actual example should be simplified in the following way

sage: S = PrimitiveGroups(5); S       # requires optional database_gap
Primitive Groups of degree 5
sage: S.list()                          # requires optional database_gap
[Primitive group number 1 of degree 5, Primitive group number 2 of degree 5,
Primitive group number 3 of degree 5, Primitive group number 4 of degree 5,
Primitive group number 5 of degree 5]
sage: S.an_element() # requires optional database_gap
Primitive group number 1 of degree 5

5. In the method cardinality of PrimitiveGroups you used once ZZ and once Integer. I think that Integer is more dedicated. Could you remove ZZ from the import statement at the begining of the file and replace ZZ by Integer wherever it occurs (3 occurences counting yours).

6. The line 1508 (an_element = EnumeratedSets.ParentMethods.an_element) makes no sense. The category framework makes automatic import of ParentMethods. You may simply erase it.

7. Your example line 1259 is a bit irrelevant: the string that goes with the assertion error says "AssertionError: n should be in {1,..,1}".

8. In relation with my previous remark 4). You write a method group_primitive_id, but in the EXAMPLES I get 2 instead of 4. Moreover, you should complete it as

EXAMPLES::

    sage: G = PermutationGroup([[(1,2,3,4,5)], [(1,5),(2,4)]])
    sage: G.group_primitive_id()    # optional - database_gap
    2
    sage: G.degree()
    5

From the information of the degree and the identification number, 
you can recover the isomorphism class of your group in the GAP 
database::

    sage: H = PermutationGroup(5,2)  # optional - database_gap
    sage: G == H                                  # optional - database_gap
    False
    sage: G.is_isomorphic(H)                 # optional - database_gap
    True

9. Could you add a TODO in the documentation of PrimitiveGroups saying that there exists a command PrimitiveGroupsIterator in GAP which accept many arguments (nb. of moved points, size, transitivity, simple group, solvable, ...).

oo) Typo:

• the INPUT documentation of the init method of PrimitiveGroup does not follow the good syntax (PrimitiveGroups.init is OK). You can have a look at section 2.1.5 of the Developer Guide.
• how did you choose to break or not break lines in the documentation ? It seems to be pretty random.
• there are some non needed empty lines: at the end of PrimitiveGroups documentation and at the end of PrimitiveGroupsOfDegree documentation.
• line 1310, you wrote d up to isomorphism twice.
• Could you smartly write in all your classes that you wrap the GAP database (it is important for the user to see that Sage uses another software).

[sagetrac-trehn]

comment:6

Finally I have found time again to work on your suggestions. I think I could adapt almost everything.

Only your remark 3) is a bit unclear to me. I think the only place where 1-based ids are confusing is in the constructor of PrimitiveGroup, but there this is explicitly stated in the documentation.

sage -t -optional permgroup.py does not work, but the problems are not related to primitive groups.

[sagetrac-trehn]

patch, updated for v5.3

[vbraun]

Attachment: trac_12407_primitive_permutation_groups.patch.gz

Attachment: trac_12407_review.patch.gz

Initial patch

[vbraun]

Changed reviewer from vdelecroix to vdelecroix, Volker Braun

[vbraun]

comment:8

I've added some docstring fixes to follow Sage conventions more closely. E.g. imperative ("Return") instead of "Returns", indentation, keep line length finite, .... Also I don't think that we really need an alias primitive_id, just group_primitive_id is IMHO enough.

Please have a look at the reviewer patch. Positive review from me for everything else.

[sagetrac-trehn]

comment:9

Thank you for the improvements, I am happy with them.

[jdemeyer]

Changed reviewer from vdelecroix, Volker Braun to Vincent Delecroix, Volker Braun

[jdemeyer]

comment:12

There are various doctest errors:

sage -t  -force_lib devel/sage/sage/groups/perm_gps/permgroup_named.py
**********************************************************************
File "/release/merger/sage-5.5.beta2/devel/sage-main/sage/groups/perm_gps/permgroup_named.py", line 1515:
    sage: PrimitiveGroup(6,5)
Expected:
    Traceback (most recent call last):
    ...
    AssertionError: n should be in {1,..,4}
Got:
    verbose 0 (1813: permgroup_named.py, cardinality) Warning: PrimitiveGroups requires the GAP database package. Please install it with `
`sage -i database_gap``.
    [...]
**********************************************************************
File "/release/merger/sage-5.5.beta2/devel/sage-main/sage/groups/perm_gps/permgroup_named.py", line 1552:
    sage: G = PrimitiveGroup(5,1); G
Exception raised:
    [...]
    AssertionError: n should be in {1,..,None}
**********************************************************************
File "/release/merger/sage-5.5.beta2/devel/sage-main/sage/groups/perm_gps/permgroup_named.py", line 1569:
    sage: G = PrimitiveGroup(5,2); G.group_primitive_id()
Exception raised:
    [...]
    AssertionError: n should be in {1,..,None}
**********************************************************************

Besides that, you should not use assert for this. Only use "assert" to check for actual bugs, not for bad user input. If there is any way at all to reproduce an AssertionError using documented public functions, that is by definition a bug.

[sagetrac-trehn]

comment:13

I think this happens only if database_gap is not installed. I will look at this.

[sagetrac-trehn]

comment:14

Attachment: trac_12407_fix_testcases.patch.gz

With the third patch on top the tests should work with and without 'database_gap'. I have also replaced all assertions in permgroup_named.py by ValueErrors.

[vbraun]

comment:15

I've double-checked that the doctests now work with and without the database_gap. Positive review.

[jdemeyer]

comment:18

This patch uses assertions in a bad way. As discussed some time ago on sage-devel, public functions should never use assertions to signal bad user input. Any appearance of an AssertionError is by definition a bug.

[sagetrac-trehn]

comment:19

The last of the three patches should already remove all possible AssertionErrors in permgroup.py and permgroup_named.py that I introduced with my first patch or that had been there before.

I didn't merge the three patches into one since I am not the author of all three.

[jdemeyer]

comment:21

OK fine, I didn't realize that.

[jdemeyer]

Merged: sage-5.6.beta1