Implement conjugacy classes

[sagetrac-jlopez]

GAP has several functions concerning conjugacy classes of groups. This patch include a wrapper for gap conjugacy classes for groups in which they are available and a (kind of) naive fallback method based on TransitiveIdeal for the remaining cases.

Apply:

• attachment: trac_7886_conjugacy_classes_combined.patch
• attachment: trac_7886-conjugacy_classes-review-ts.patch

Depends on #6495

CC: @wdjoyner @jdemeyer @sagetrac-jlopez

Component: group theory

Author: Javier López Peña

Reviewer: David Joyner, Travis Scrimshaw

Merged: sage-5.8.beta2

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

[sagetrac-jlopez]

Implementation of a python class for conjugacy classes, wrapping some GAP functions and some native python methods.

[sagetrac-jlopez]

Attachment: conjugacy_classes.patch.gz

Attachment: trac_7886_conjugacy_classes.patch.gz

Conjugacy classes code

[sagetrac-jlopez]

comment:1

Patch submitted. All tests pass on my machine (OX-X 10.6.8) with the exception of the ConjugacyClass Testsuite, which fails testing equality. I have no idea how the testsuite works, so could use some help here.

[sagetrac-jlopez]

comment:2

For the patchbot:

Apply trac_7886_conjugacy_classes.patch

[sagetrac-jlopez]

comment:3

Oops! Forgot to add the new module to the patch, here it is!

[sagetrac-jlopez]

comment:4

Apply trac_7886_conjugacy_classes_module.patch, trac_7886_conjugacy_classes.patch

[sagetrac-jlopez]

conjugacy_classes.py module with passing Testsuite

[sagetrac-jlopez]

comment:5

Attachment: trac_7886_conjugacy_classes_module.patch.gz

Updated the conjugacy_classes.py module with the fixed _cmp_ method so that the testsuite passes. All test pass on my machine, so ready for review.

[wdjoyner]

comment:8

The code looks fine to me. I tested it on a 10.6.8 mac under sage-4.8.a3 and on a Ubuntu 10.04 (Lucid Lynx) machine under sage-4.8.a1.

There was a discussion of cached methods in sage-devel, but I'm not sure how that relates to this ticket, so I'm giving this a positive review. Maybe changes, if any, from that thread can go in a separate ticket.

[jdemeyer]

comment:10

In the file sage/groups/perm_gps/permgroup.py, you use Unicode but the encoding has not been declared to be utf-8.

See http://www.python.org/dev/peps/pep-0263/

[jdemeyer]

Work Issues: PEP 0263

[sagetrac-jlopez]

Fixed encoding and improvement of naive set method.

[sagetrac-jlopez]

comment:11

Attachment: trac_7886_conjugacy_classes_encoding_fix.patch.gz

Sorry, I thought we were using utf-8 by default. Fixed the encoding in permgroup.py and conjugacy_classes.py
Also implemented a more efficient fallback method using TransitiveIdeal.
Needs review.

[sagetrac-jlopez]

Changed work issues from PEP 0263 to none

[sagetrac-jlopez]

comment:17

patchbot: apply trac_7886_conjugacy_classes_combined.patch

[tscrim]

comment:18

Hey,

Thank you for working on this. However there are multiple docstring issues you will need to address. More specifically, you will need to change (for example)

EXAMPLES:
    sage: H = MatrixGroup([matrix(GF(5),2,[1,2, -1, 1]), matrix(GF(5),2, [1,1, 0,1])])
    sage: h = H(matrix(GF(5),2,[1,2, -1, 1]))
    sage: H.conjugacy_class(h)
    ...

#####

TODO:
    - Implement a non-naive fallback method for computing all the elements of
    the conjugacy class when the group is not defined in GAP, as the one in
    Butler's paper.
    - Define a sage method for gap matrices so that groups of matrices can
    use the quicker GAP algorithm rather than the naive one.

EXAMPLES::

- Conjugacy classes for groups of permutations 

    sage: G = SymmetricGroup(4) 
    ...

to

EXAMPLES::

    sage: H = MatrixGroup([matrix(GF(5),2,[1,2, -1, 1]), matrix(GF(5),2, [1,1, 0,1])])
    sage: h = H(matrix(GF(5),2,[1,2, -1, 1]))
    sage: H.conjugacy_class(h)
    ...

####


.. TODO::

    - Implement a non-naive fallback method for computing all the elements of
      the conjugacy class when the group is not defined in GAP, as the one in
      Butler's paper.
    - Define a sage method for gap matrices so that groups of matrices can
      use the quicker GAP algorithm rather than the naive one.

EXAMPLES:

Conjugacy classes for groups of permutations::

    sage: G = SymmetricGroup(4) 
    ...

otherwise the formatting will be incorrect (the convention is not to use bullet points for different examples). For a full description, see the conventions page.

Also you will need to cleanup the patch's header message.

Thanks,

Travis

[KPanComputes]

comment:19

This patch needs to address referee's comments. I am changing this to needs_work in the meanwhile.

[sagetrac-jlopez]

comment:20

Thanks for looking at my patch! I have a complicated work situation during the week, but will fix the docstring style and rebase again over sage 5.7 on Friday or Saturday.

Not sure what you mean about the patch header message. Do you mean the Spanish characters in my name? That is automatically added by my hg configuration, but it seems that trac does not support UTF-8; I added the appropriate encoding to the python files, but don't know how to do it for the patch (and don't feel inclined to change my name either). If it is about the cruft that came from patch folding, I will take care of that as well.

Cheers,
J

[tscrim]

comment:21

Hey Javier,

Replying to @sagetrac-jlopez:

Thanks for looking at my patch! I have a complicated work situation during the week, but will fix the docstring style and rebase again over sage 5.7 on Friday or Saturday.

Thank you! There's not a huge rush, just ping back when it's done and I'll give it a look-over.

Not sure what you mean about the patch header message. Do you mean the Spanish characters in my name? That is automatically added by my hg configuration, but it seems that trac does not support UTF-8; I added the appropriate encoding to the python files, but don't know how to do it for the patch (and don't feel inclined to change my name either). If it is about the cruft that came from patch folding, I will take care of that as well.

If you look at the beginning of the patch, you have the following:

# HG changeset patch
# User Javier López Peña <vengoroso@gmail.com>
# Date 1360004753 0
# Node ID 2782ba59f14a8dafdb44e05a67972e5a9d4db0cf
# Parent  fa8decac55338225dc33568ad600c261fc777b4c
* * *
Trac 7886: Conjugacy classes
* * *
Trac 7886: Created module for conjugacy classes of finite groups.
Added wrappers for GAP functions and naive fallback method.
* * *
Trac 7886: Conjugacy classes

In particular, the line right after the # Parent ... should be a one line summary of the patch with the ticket number (such as Trac 7886: Conjugacy classes which is probably what you originally had). This can get mangled when folding patches. You can change this by doing a qrefresh -e. I don't think the encoding for your name in the header is important.

Gracias por tu trabajo,

Travis

[tscrim]

Changed reviewer from David Joyner to David Joyner, Travis Scrimshaw

[sagetrac-jlopez]

comment:22

I think I fixed all the docstring formatting. Also removed some trailing whitespaces and rebased over sage 5.7. Needs review.

Patchbot apply trac_7886_conjugacy_classes_combined.patch

[tscrim]

comment:23

Hey Javier,

There are still many misformatted docstrings (did you forget to refresh the patch?) and the examples are still itemized. Also remove the * * * from the header. In case you are unaware, you can run sage -docbuild reference html (or reference/groups and/or reference/categories with #6495) to view the documentation.

Thanks,

Travis

[sagetrac-jlopez]

comment:24

Hi Travis,

refreshed, fixed the itemized examples. My docbuild refuses to work due to the presence of UTF8 characters in the docstring:

    reading sources... [ 75%] sage/groups/perm_gps/permgroup                        
    Sphinx error:
    'ascii' codec can't decode byte 0xc3 in position 3438: ordinal not in range(128)

Is there any way to tell sphinx to use the utf8 codec instead? I already included the

# coding = utf-8

in the python file, but the docbuild seems to ignore that.

[sagetrac-jlopez]

Docstring and whitespaces fixes, rebased for sage 5.7. Apply this patch only.

[tscrim]

Attachment: trac_7886_conjugacy_classes_combined.patch.gz

[tscrim]

comment:25

Attachment: trac_7886-conjugacy_classes-review-ts.patch.gz

Hey Javier,

I've attaching a review patch which fixes up the remaining documentation and adds the files to the docbuild (I had to do some extra tweaks in the categories/finite_groups.py since it wasn't in the docbuild prior to this patch). If everything works and looks good to you, you go ahead and set this to positive review.

Thanks,

Travis

For patchbot:

Apply: trac_7886_conjugacy_classes_combined.patch, trac_7886-conjugacy_classes-review-ts.patch

[sagetrac-jlopez]

comment:26

Hi Travis,

your reviewer patch fails to apply for me:

applying trac_7886-conjugacy_classes-review-ts.patch
unable to find 'doc/en/reference/categories/index.rst' for patching
1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/categories/index.rst.rej
unable to find 'doc/en/reference/groups/index.rst' for patching
1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/groups/index.rst.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_7886-conjugacy_classes-review-ts.patch

Are we working over the same version of sage (I'm on 5.7), or did you apply any previous patches that changed documentation files?

[tscrim]

Dependencies: #6495

[tscrim]

comment:27

Hey Javier,

Actually I have #6495 applied, it might be because of that. I've added it as a dependency. Try applying the patches with #6495.

Thanks,

Travis

[sagetrac-jlopez]

comment:28

Alright. WIth #6495 applied the reviewer patch applies and docs build properly. Tests pass, so I think this is good to go.
Thanks for your help with the reviewing and the docstring formatting!

[sagetrac-jlopez]

comment:29

Patchbot seems confused about what needs to be applied, so here it goes again:

Apply trac_7886_conjugacy_classes_combined.patch trac_7886-conjugacy_classes-review-ts.patch

[jdemeyer]

Merged: sage-5.8.beta2

[vbraun]

comment:31

You shouldn't return lists from @cached_method functions. If somebody mutates the output list then future calls return the wrong result! Always return tuples instead of lists unless you want the output to be mutable.

Also, ConjugacyClass is a parent without elements; Use SageObject as base for classes that do not use the parent/element pattern.