modular subgroups

[vdelecroix]

This ticket aims to extend capability of the class ArithmeticSubgroup_Permutation in sage.modular.arithgroup_perm. This is now possible to deal with any subgroup of SL(2,Z) and many new methods are available (in particular equality of subgroups, conjugacy problem, ...)

I reimplement the method todd_coxeter of sage.modular.arithgroup.arithgroup_generic to be faster and with more output.

I also created a test file for arithmetic subgroup.

See details and documentation in the patch.

---

Apply

1. trac_11422-sl2z_subgroups.patch​
2. trac_11422-reviewerfix.patch​
3. trac_11422_unpicklefix.patch​

to the Sage library.

[davidloeffler]

This looks great -- I always meant to do some more work on this but never got around to it, and you are clearly much better equipped to do so than I. Sadly there are masses of doctest failures (48 of them on a clean 4.7.1.alpha3 build with just your patch applied). Almost all of them look like this:

TypeError: cycle_tuples() takes no keyword arguments

Also, some gripes:

• The English is a bit ropey in some of the docstrings (e.g. "vue", "canonic").

• Some more explanation of what a few of the functions are doing would be nice -- e.g. what is canonical about the canonical labels?

[vdelecroix]

Hello,

Thanks for starting to look at this.

Replying to davidloeffler:

This looks great -- I always meant to do some more work on this but never got around to it, and you are clearly much better equipped to do so than I. Sadly there are masses of doctest failures (48 of them on a clean 4.7.1.alpha3 build with just your patch applied). Almost all of them look like this:

TypeError: cycle_tuples() takes no keyword arguments

There was a dependancy problem with #10335 which is now in the description.

Also, some gripes:

• The English is a bit ropey in some of the docstrings (e.g. "vue", "canonic").

I'm not a native speaker and it's not easy to find where the errors are. In the new version I will post in few minutes, I have tried to be attentive to the language.

• Some more explanation of what a few of the functions are doing would be nice -- e.g. what is canonical about the canonical labels?

Could you be more precise ? In the new version, I expanded some of the documentations (especially the canonical labels).

[davidloeffler]

OK, I downloaded #10335 and its prerequisites and it works fine now.

Algorithm comments:

• For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:

• having a flag that remembers whether the group is already canonically labelled,

• when that's not the case, caching the canonically labelled version.

• At line 1019 of arithgroup.py, if check is True, won't this cause the check code to be run *twice*?

Corrections to docstrings:

In arithgroup_generic.py:

• The docstring for the todd_coxeter method is a bit vague: I'd suggest that you specify a bit more precisely what the lists l and s mean. "The action of the parabolic elements" is misleading; you mean the action of the specific parabolic element [[1, 1],[0,1]] .

• It is disrespectful to Todd and Coxeter to write their names in lowercase, as you do in the docstring for as_permutation_group -- better to write "This uses Todd-Coxeter enumeration".

In arithgroup_perm.py:

• "point of vue" --> "point of view" in the module docstring (as I pointed out above)

• Again in that docstring, you make it sound like all four of L, R, S2 and S3 are needed to generate the modular group -- explain that the "three couples which are of main interest" are of interest because each pair of elements generates the whole group.

• The "todo" list will look bizzarre: some LaTeX formatting is needed for the second item

• Line 328: "generator" --> "generators"

• Line 630 "numerotation" --> "numbering"

• 640: "defines" --> "define", "renumerote" --> "renumber" (the nonexistent word "numerote" appears twice more in the next few lines)

• 744: "Returns the smallest label among rooted label" -- do you seriously expect that anyone will have the foggiest clue what this means?

• 749: "canonic" --> "canonical". This occurs all over the place. Fix them all.

• 810: needs more explanation of what the argument j0 does.

• 812: "renumerotation" --> "renumbering" again.

• 908: "does not permutes" --> "does not permute"

• 947: "at the first times" --> "at the first time"

That's as far as I've got so far -- other duties call.

[vdelecroix]

Thanks for the detailed report.

Algorithm comments:

• For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:

• having a flag that remembers whether the group is already canonically labelled,

• when that's not the case, caching the canonically labelled version.

Totally right. I choose to add an attribute _canonical_label_group when the group with canonical renumbering has been computed.

• At line 1019 of arithgroup.py, if check is True, won't this cause the check code to be run *twice*?

I don't think so. The function call is called only once, the contains method does not call the constructor and the init method of ArithmeticSubgroupElement? does not care about wheter or not the element is in the subgroup "parent" given as argument.

Corrections to docstrings:

I made the corrections.

[davidloeffler]

Replying to vdelecroix:

Algorithm comments:

• For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:

• having a flag that remembers whether the group is already canonically labelled,

• when that's not the case, caching the canonically labelled version.

Totally right. I choose to add an attribute _canonical_label_group when the group with canonical renumbering has been computed.

There is an amusingly subtle bug here.

At line 769, the code sets the attribute _canonical_labelel_group, which is clearly a typo. This means that a subsequent hasattr check for _canonical_label_group returns False, leading to the following:

sage: S2 = "(1,2)(3,4)(5,6)"
sage: S3 = "(1,3,5)(2,4,6)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: H = G.relabel(inplace=False)
sage: G.has_canonical_labels()
False

I don't think this is what you intended, is it?

The reason I said it's complicated is that naming the method "has_canonical_labels" is slightly misleading. I would have assumed that "G.has_canonical_labels() == True" means that the labels G is using are the canonical ones. Although it's not what you intended, the typo has meant that the function is now *almost* doing what I feel the name suggests it should do! ("Almost" because it might return False in some cases even if the labels actually are the canonical ones.)

I would advocate correcting the typo at line 769 but also changing the has_canonical_labels function so it does what I said, i.e. so returns True if and only if self._canonical_rooted_labels() == range(self.index()), with a docstring to match.

• At line 1019 of arithgroup.py, if check is True, won't this cause the check code to be run *twice*?

I don't think so.

You're right, of course; sorry.

[vdelecroix]

Replying to davidloeffler:

Replying to vdelecroix:

Algorithm comments:

• For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:

• having a flag that remembers whether the group is already canonically labelled,

• when that's not the case, caching the canonically labelled version.

Totally right. I choose to add an attribute _canonical_label_group when the group with canonical renumbering has been computed.

There is an amusingly subtle bug here.

Hopefully, you find that crazy bug! Thanks! I had a supplementary doctest for this method.

I would advocate correcting the typo at line 769 but also changing the has_canonical_labels function so it does what I said, i.e. so returns True if and only if self._canonical_rooted_labels() == range(self.index()), with a docstring to match.

I removed the function has_canonical_labels which is not useful at all.

[davidloeffler]

Excellent -- good stuff. Positive review. Sadly this is probably too late for 4.7.1, but it should get into 4.7.2.

(Now I will have to rebase #5048, and not for the first time. I should stop giving positive reviews to patches that conflict with my own ;-) )

[davidloeffler]

Hang on, there's something wrong with to_even_subgroup.

sage: H = ArithmeticSubgroup_Permutation(S2 = '(1,4,11,14)(2,7,12,17)(3,5,13,15)(6,9,16,19)(8,10,18,20)', S3 = '(1,2,3,11,12,13)(4,5,6,14,15,16)(7,8,9,17,18,19)(10,20)')
sage: G = H.to_even_subgroup()
sage: H.is_subgroup(G)
False

[davidloeffler]

apply over previous patch

[davidloeffler]

Here's a patch. The problem was the use of a python set type: you can certainly enumerate sets, but you shouldn't expect the enumeration order to be consistent! I changed the code slightly to use lists, combining two loops into one.

Vincent: if you're happy with my change, you can restore the positive review.

[vdelecroix]

Replying to davidloeffler:

Here's a patch. The problem was the use of a python set type: you can certainly enumerate sets, but you shouldn't expect the enumeration order to be consistent! I changed the code slightly to use lists, combining two loops into one.

Vincent: if you're happy with my change, you can restore the positive review.

Thanks for debugging (it seems that you're using the code... cool!).

[davidloeffler]

Hang on, this isn't good:

sage -t -long -force_lib "devel/sage/sage/structure/sage_object.pyx"
**********************************************************************
File "/storage/masiao/sage-4.7.1.alpha4/devel/sage/sage/structure/sage_object.pyx", line 1077:
    sage: sage.structure.sage_object.unpickle_all()  # (4s on sage.math, 2011)
Expected:
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got: 
     * unpickle failure: load('/home/masiao/.sage/temp/selmer/23062/dir_2/pickle_jar/_class__sage_modular_arithgroup_arithgroup_perm_ArithmeticSubgroup_Permutation__.sobj')
    Failed:
    _class__sage_modular_arithgroup_arithgroup_perm_ArithmeticSubgroup_Permutation__.sobj
    Successfully unpickled 586 objects.
    Failed to unpickle 1 objects.
**********************************************************************
1 items had failures:
   1 of   7 in __main__.example_25
***Test Failed*** 1 failures.
For whitespace errors, see the file /home/masiao/.sage//tmp/.doctest_sage_object.py
         [8.2 s]

This is because sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation was a class before and is now a factory function, so Python doesn't know how to unpickle pickled objects of that class.

[davidloeffler]

apply over the two preceding patches

[davidloeffler]

It turns out the unpickling problems can be sorted out by ensuring that sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation can be called with two positional arguments corresponding to L and R. All tests now pass on my system.

[vdelecroix]

Replying to davidloeffler:

It turns out the unpickling problems can be sorted out by ensuring that sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation can be called with two positional arguments corresponding to L and R. All tests now pass on my system.

All tests and backward compatibility with pickling also pass on my computer. I put a positive review.