meataxe interface

[wdjoyner]

This is a start for anyone interested in G-module decompositions using GAP's Meataxe implementations.

CC: @wdjoyner

Component: group theory

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

[wdjoyner]

comment:2

The patch 10104 contains all the changes, is based on 3.0.6.rc0, and passed sage -testall. It does not require 10092, so you should ignore that one. This patch adds module_composition_factors (an interface to GAP's meataxe implementation) and as_permutation_group (which returns an isomorphic PermutationGroup). The function module_composition_factors is needed for a research paper (in progress, joint with Amy Ksir and Darren Glass) which will probably be presented at the AMS national meeting in January 2009.

[simon-king-jena]

comment:3

Sorry that i was unable to look at this earlier. I'll wait for a patch based on a more recent sage-version before writing a full review.

Note, however, that patch 10104 doesn't do what it is supposed to do.

The doc-string says:
Returns a list of triples consisting of [base field, dimension, irreducibility],
for each of the Meataxe composition factors modules.

But it only returns a list, as can be seen in the example from the doc-string:

sage: G.module_composition_factors() 
[Finite Field of size 7, 2, True] 

The reason is the line 896:

L = L + [sage_eval(gap.eval("MCF.field")), eval(gap.eval("MCF.dimension")), sage_eval(gap.eval("MCF.IsIrreducible"))]

which should be

L = L + [[sage_eval(gap.eval("MCF.field")), eval(gap.eval("MCF.dimension")), sage_eval(gap.eval("MCF.IsIrreducible"))]]

[wdjoyner]

This is a new patch based on sage 3.1.alpha0. Does not require other patches.

[wdjoyner]

comment:4

Attachment: 10128.patch.gz

The attached patch 10128 fixes the bug Simon found (thanks Simon!).

[simon-king-jena]

comment:6

The patch applies cleanly to SAGE Version 3.1.alpha0, Release Date: 2008-08-01. It seems to do what it is supposed to do, and the doc-tests for matrix_group.py pass.

Therefore, i recommend inclusion of the patch.

However, i would be glad about "stronger" examples.

• Is there an example for as_permutation_group where the option method="smaller" actually yields a smaller result? Then it would be nice to include such example.

• It would be nice to see an example where module_composition_factors yields a non-trivial decomposition. Such as here:

sage: F=GF(3);MS=MatrixSpace(F,4,4)
sage: M=MS(0)
sage: M[0,1]=1;M[1,2]=1;M[2,3]=1;M[3,0]=1
sage: G.module_composition_factors()

[[Finite Field of size 3, 1, True],
 [Finite Field of size 3, 1, True],
 [Finite Field of size 3, 2, True]]

[wdjoyner]

comment:7

Definitely, I'm happy to add the example to the dcstring of module_composition_factors. Thanks for that.

Regarding a "better" "smaller" example, they are not so easy to find! I did find one though. The problem is that the generators are returned randomly. Michael Abshoff told me he doesn't like " # random output" comments in docstrings, so I added a the command current_randstate().set_seed_gap(). This does not work as I think it should, so I don't know the right way to proceed. I guess I'll post a patch that pases tests and worry about the random output stuff later.

[wdjoyner]

Attachment: 10129.patch.gz

based on 3.1.alpha0

[wdjoyner]

comment:8

This latest patch passes sage -testall and adds the examples suggested by the referee. Thanks Simon!

[simon-king-jena]

comment:9

Replying to @wdjoyner:

Regarding a "better" "smaller" example, they are not so easy to find! I did find one though. The problem is that the generators are returned randomly. Michael Abshoff told me he doesn't like " # random output" comments in docstrings,

Cc to Michael Abshoff.

I understand that Gap uses a randomized algorithm when getting method="smaller". Hence, if one wants to show the full functionality of a method to the user (which i find important!), one can not avoid to have #random in the doc-tests.

Michael, what do you think?

I think:

• Starting with 3.1.alpha0, applying patch 10128 and then applying patch 10129 works.
• The methods are useful.
• The doc-string shows the functionality
• The doc-tests pass
  Hence i give it a positive review, but make it dependent on Michael's opinion on random doc-tests and/or on the idea to use current_randstate().set_seed_gap().

[sagetrac-mabshoff]

comment:10

David,

no need to CC me, I read every ticket anyway.

About randomness: GAP should behave deterministically unless there is a third rng we do not know about. For now it seems fine to add the #random to the doctests, but you might want to raise the issue on sage-devel so that Carl Witty can give his input on the problem.

Cheers,

Michael

[simon-king-jena]

comment:11

Replying to @sagetrac-mabshoff:

no need to CC me, I read every ticket anyway.

Very impressive!

... For now it seems fine to add the #random to the doctests, ...

Then there is a positive review from my side and (if i am allowed to do so) I resolve the ticket as fixed (or is this only allowed to administrators?).

[wdjoyner]

based on sage-3.1.alpha0, as the others

[wdjoyner]

comment:12

Attachment: 10130.patch.gz

The last patch 10130 is a docstring change only.

Following Michael Abshoff's suggestion, I emailed sage-devel and mentioned the problem I was having with the random comments. It seems I was using the current_randstate().set_seed_gap() command incorrectly for the situation. I added some set_random_seed(n) statements (where n is chosen in a specific way) and removed the "# random output" comments. I did multiple test passes and this seems to work each time now.

Hopefully, with 10130, everyone is okay with this now.

[sagetrac-aginiewicz]

comment:13

Replying to @simon-king-jena:

Then there is a positive review from my side and (if i am allowed to do so) I resolve the ticket as fixed (or is this only allowed to administrators?).

iirc it was that only things that get merged in are closed by admins? :)

[sagetrac-mabshoff]

comment:14

Replying to @sagetrac-aginiewicz:

Replying to @simon-king-jena:

Then there is a positive review from my side and (if i am allowed to do so) I resolve the ticket as fixed (or is this only allowed to administrators?).

iirc it was that only things that get merged in are closed by admins? :)

Yes, the release manager closes tickets once the patch/spkg has been merged. How else would be keep track of all the patches?

Cheers,

Michael

[sagetrac-mabshoff]

comment:15

Merged 10128.patch, 10129.patch and 10130.patch in Sage 3.1.2.alpha0