Congruence testing for odd modular subgroups

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

The new functionality added in ticket #11422 makes it possible to manipulate arbitrary finite index (not necessarily congruence) subgroups of SL2Z. This massively extends my old code which only worked for subgroups containing -1.

The "is_congruence" method in the new code, though, defines a subgroup to be congruence if its image modulo -1 is a congruence subgroup of PSL2Z. This is not the same as the conventional definition of a congruence subgroup of SL2Z. The patch below modifies the algorithm so it uses the conventional notion of "congruence". It also adds functionality for enumerating all the liftings of a projective modular subgroup.

Part of a series of tickets: #10335 - #11422 - this one - #5048 - #10453 - #11601.

Apply:

attachment: trac_11598-foldedrebased.patch

Depends on #11422

CC: @videlec

Component: modular forms

Keywords: modular congruence subgroup

Author: David Loeffler

Reviewer: Vincent Delecroix

Merged: sage-4.7.2.alpha3

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

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:1

Hi Vincent,

Any chance you could take a look at this? I don't think we should go changing the definition of "congruence"! I missed this issue when I reviewed #11422, so I did this little patch to change it.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Changed dependencies from 11422 to #11422

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:2

Just realised that, since the new algorithm in the odd case is extremely slow, it is better to not call it from the generic test routine! Here's a new patch.

videlec commented 13 years ago

comment:3

Replying to @loefflerd:

I was asking myself what should be the definition of congruence subgroup. In order to use Wohlfart's theorem it is necessary to use the projective definition and that's why it was implemented that way. For all standard congruence groups it makes no difference. Could you explain me a concrete case where the difference matter ?

In any case, you should add an example of an odd arithmetic subgroup which is not of congruence but which becomes one when we add the element -id.

Do you know a method, given an even subgroup, to build all odd subgroups it may come from ?

Just realised that, since the new algorithm in the odd case is extremely slow, it is better to not call it from the generic test routine! Here's a new patch.

For that particular question, it should be possible, following Hsu method (who produces uniform presentation for PSL(Z,Z/pZ)), to get a congruence test method for odd subgroups.

videlec commented 13 years ago

Reviewer: Vincent Delecroix

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:4

Replying to @videlec:

Replying to @loefflerd:

I was asking myself what should be the definition of congruence subgroup. In order to use Wohlfart's theorem it is necessary to use the projective definition and that's why it was implemented that way. For all standard congruence groups it makes no difference. Could you explain me a concrete case where the difference matter ?

Here's one: the group of index 24 with S2 = (1,3,13,15)(2,4,14,16)(5,7,17,19)(6,10,18,22)(8,12,20,24)(9,11,21,23), S3 = (1,14,15,13,2,3)(4,5,6,16,17,18)(7,8,9,19,20,21)(10,11,12,22,23,24). This is taken from the paper of Kiming, Schuett and Verrill in J. London Math Soc (2010) which is all about this problem of finding noncongruence odd subgroups whose projective image is congruence.

In any case, you should add an example of an odd arithmetic subgroup which is not of congruence but which becomes one when we add the element -id.

Do you know a method, given an even subgroup, to build all odd subgroups it may come from ?

There is one in the K-S-V paper but it uses Farey symbols heavily. I can think of an algorithm which produces some examples of such subgroups using the permutation representation (which is how I found the one above) but it's not totally obvious to me if it produces all of them.

Just realised that, since the new algorithm in the odd case is extremely slow, it is better to not call it from the generic test routine! Here's a new patch.

For that particular question, it should be possible, following Hsu method (who produces uniform presentation for PSL(Z,Z/pZ)), to get a congruence test method for odd subgroups.

I've actually thought of another approach, which is slower and less elegant than Hsu's approach but much better than the patch I just made :-). Rather than finding generators for Gamma(N), which is hideously slow if N is more than about 8, one can just look at the subgroup of SL(2, Z / NZ) generated by the reductions mod n of the generators of self. Then self is congruence of level N iff this subgroup has the same index in SL(2, Z/NZ) as self does in SL(2,Z); and we can always take N to be twice the generalised level.

Better still, if G isn't congruence, then this algorithm calculates the smallest congruence subgroup containing G (the congruence closure), which is an interesting thing to calculate in itself.

I will do a new patch tomorrow.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Attachment: trac_11598-odd_congroup_change.patch.gz

patch against 4.7.1.alpha4 + #10335 + #11422

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:5

Here's a new patch, which:

implements a congruence test for odd subgroups, using only calculations in finite matrix groups (much faster than the previous version);
implements enumeration of the index 2 odd subgroups of an even subgroup;
corrects a few typos etc in the documentation.

There are probably far better ways of doing the congruence test, as you suggest; but I'd rather get something that works in quickly, rather than having to release a Sage version that uses a different definition and then change it back to the conventional definition later.

I haven't implemented congruence closure yet, because I'm working on a patch that will introduce a new class for generic congruence subgroups defined by a finite group of matrices in SL(2, Z / N), and I'll include congruence closure in that.

Thanks Vincent for the helpful feedback on my previous patch!

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 The new functionality added in ticket #11422 makes it possible to manipulate arbitrary finite index (not necessarily congruence) subgroups of SL2Z. This massively extends my old code which only worked for subgroups containing -1.

-The "is_congruence" method in the new code, though, *defines* a subgroup to be congruence if its image modulo -1 is a congruence subgroup of PSL2Z. This is not the same as the conventional definition of a congruence subgroup of SL2Z. The patch below modifies the algorithm so it uses the conventional notion of "congruence".
+The "is_congruence" method in the new code, though, *defines* a subgroup to be congruence if its image modulo -1 is a congruence subgroup of PSL2Z. This is not the same as the conventional definition of a congruence subgroup of SL2Z. The patch below modifies the algorithm so it uses the conventional notion of "congruence". It also adds functionality for enumerating all the liftings of a projective modular subgroup.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,6 @@
 The new functionality added in ticket #11422 makes it possible to manipulate arbitrary finite index (not necessarily congruence) subgroups of SL2Z. This massively extends my old code which only worked for subgroups containing -1.

 The "is_congruence" method in the new code, though, *defines* a subgroup to be congruence if its image modulo -1 is a congruence subgroup of PSL2Z. This is not the same as the conventional definition of a congruence subgroup of SL2Z. The patch below modifies the algorithm so it uses the conventional notion of "congruence". It also adds functionality for enumerating all the liftings of a projective modular subgroup.
+
+Part of a series of tickets: #10335 - #11422 - this one - #5048 - #10453 - #11601.
+

videlec commented 13 years ago

comment:7

Replying to @loefflerd:

Very nice!

implements enumeration of the index 2 odd subgroups of an even subgroup;

I modified details of your implementation (not the algorithm). There are some redundancy, but the code is by far much faster.
I added a method one_odd_subgroup which is a copy of the first lines of your function and a randomization of the end. The randomization is optional (see in the "reviewer" patch).
With the above function, I added a random_odd_subgroup in the testing file and make tests compatible with odd subgroups.

There are probably far better ways of doing the congruence test, as you suggest; but I'd rather get something that works in quickly, rather than having to release a Sage version that uses a different definition and then change it back to the conventional definition later.

I definitely agree.

If you are OK, with my changes, you can put the ticket in positive review.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:8

I've done some tests. You made several changes: setting "check=False" in the constructor; adding a custom __hash__ function; and using a set and a list at the same time. The combined effect of these is dramatic:

BEFORE

sage: time [len(Gamma0(N).as_permutation_group().odd_subgroups()) for N in [11..20]]
CPU times: user 14.26 s, sys: 2.34 s, total: 16.60 s
Wall time: 38.00 s
[8, 32, 0, 32, 32, 32, 0, 128, 8, 128]

AFTER

sage: time [len(Gamma0(N).as_permutation_group().odd_subgroups()) for N in [11..20]]
CPU times: user 3.35 s, sys: 0.49 s, total: 3.84 s
Wall time: 4.32 s
[8, 32, 0, 32, 32, 32, 0, 128, 8, 128]

But one part puzzles me a little. I can see that the first two changes lead to a dramatic speedup, but it's not totally clear to me what the advantage of using a set type for the bucket variable is. Could you explain? Moreover, if the set leads to some speedup, then why keep the list as well -- why not just return list(bucket) at the end?

Also, you have a random ( in a comment at line 2478; it seems odd not to disable the check parameter in one_odd_subgroup; and the third and fourth lines in the "Testing randomness" doctest in one_odd_subgroup seem slightly pointless -- with a random routine, checking that it works is sensible, but running a test on the output and ignoring the result seems bizarre.

videlec commented 13 years ago

comment:9

Replying to @loefflerd:

I've done some tests. [...]

but it's not totally clear to me what the advantage of using a set type for the bucket variable is.

To check if an element is in a list is linear in the size of the list, but checking if an element is in a set is constant time (up to a critical size). The reason is that Python set are implemented using a hash table.

Now, the test "if HH not in bucket" is made exactly "n" times in your algorithm and bucket grows quite fast if the centralizer of G is small. The gain of complexity is dramatic.

why keep the list as well -- why not just return list(bucket) at the end?

The way you generate the odd subgroups is somewhat canonical and the output is sorted that way. If the returned value is "list(bucket)" then the output is randomized. But, I'm not too much convinced by having at the same time a list and a set containing exactly the same values. It's up to you to make the change.

it seems odd not to disable the check parameter in one_odd_subgroup;

It is not time critical if the function is called once. But if somebody want 100 random odd subgroups then it would be better to disable the check parameter (done in the reviewer patch).

and the third and fourth lines in the "Testing randomness" doctest in one_odd_subgroup seem slightly pointless -- with a random routine, checking that it works is sensible, but running a test on the output and ignoring the result seems bizarre.

Thanks, I changed the test (see the reviewer patch). I am not so familiar with how is tested the random stuff in Sage.

videlec commented 13 years ago

Attachment: trac_11598-reviewer.patch.gz

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:10

I'm not totally sold on the new version of the random doctest either, since it has a positive probability of failing! We can't have that, I'm afraid.

I'm about to upload a new patch. This incorporates all the changes from both my previous patch and yours, together with some more tiny changes: I've cleaned up the docstrings slightly, added a few more doctests (mostly to illustrate how things fail on invalid inputs), and rearranged the order of the validity checks in the constructor function slightly (mainly for code clarity, but also giving a tiny efficiency gain by doing the most expensive test last).

Let me know if you're happy with this version. I'm off to a conference tomorrow morning, so hopefully this will be the last iteration. Thanks for your patience with all this reviewing!

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Apply only this patch. Patch against 4.7.1.alpha0 + #10335 + #11422.

videlec commented 13 years ago

Work Issues: docstrings

videlec commented 13 years ago

comment:11

Attachment: trac_11598-all.patch.gz

Replying to @loefflerd:

I'm perfectly ok with your changes in the code.

I'm not totally sold on the new version of the random doctest either, since it has a positive probability of failing! We can't have that, I'm afraid.

Actually, it doesn't. Sage reinitialize the random seed with the same value before performing the tests. It is safe, but perhaps not pedagogic, to let it in the doctest. I vote for letting the current version.

Since you made some changes in the documentation. I quickly reread it and there are some misprints.

some docstrings start with "Returns bla bla..." and others with "Return bla bla...". It seems that the Developer guide recommands "Returns".
The first line of the file starts with "[...] described by the action of the generators of G ". The generators of the group are not attached to G. It would be better to set "some generators of G".
At the begining of the file "Three couples which which [...]"
since the file tests is not compiled in the reference manual, the link to the tests module does not appear. So it is not necessary to use the format :mod:....
I discussed with some people and the pair of generators which is involved in continued fractions is (l,s2) and not (l,r). Anyway, (l,r) is a nice pair because they generate the semi-group of matrix in SL(2,Z) with non-negative entries.
In the class ArithmeticSubgroup_Permutation_class, the list of generators does not appear as they should. There is a bug with the latex interpretor. If you write "s_2, s_3, l, r" then only s_2 is considered for latex compilation.

That's all.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Apply over trac_11598-all.patch

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:12

Attachment: trac_11598-docfixes.patch.gz

Here's a patch which corrects the docstrings as you suggest. If there are any further documentation fixes, can I suggest we agree to keep them for a future ticket?

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Description changed:

--- 
+++ 
@@ -4,3 +4,7 @@

 Part of a series of tickets: #10335 - #11422 - this one - #5048 - #10453 - #11601.

+**Apply:**
+1.  [attachment: trac_11598-all.patch](https://github.com/sagemath/sage-prod/files/10653330/trac_11598-all.patch.gz)
+2.  [attachment: trac_11598-docfixes.patch](https://github.com/sagemath/sage-prod/files/10653331/trac_11598-docfixes.patch.gz)
+

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Changed work issues from docstrings to none

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Rebased for latest patch at #11422. Apply only this patch.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

comment:15

Attachment: trac_11598-foldedrebased.patch.gz

The unpickling bug that I recently spotted and fixed at #11422 causes the patches here to fail to merge. I've rebased the relevant patches and qfolded them into a single patch. As there is no change to the actual code, I hope it's fair to leave this as positive review.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 13 years ago

Description changed:

--- 
+++ 
@@ -5,6 +5,5 @@
 Part of a series of tickets: #10335 - #11422 - this one - #5048 - #10453 - #11601.

 **Apply:**
-1.  [attachment: trac_11598-all.patch](https://github.com/sagemath/sage-prod/files/10653330/trac_11598-all.patch.gz)
-2.  [attachment: trac_11598-docfixes.patch](https://github.com/sagemath/sage-prod/files/10653331/trac_11598-docfixes.patch.gz)
+1.  [attachment: trac_11598-foldedrebased.patch](https://github.com/sagemath/sage-prod/files/10653333/trac_11598-foldedrebased.patch.gz)

83660e46-0051-498b-a8c1-f7a7bd232b5a commented 13 years ago

Merged: sage-4.7.2.alpha3

sagemath / sage

Congruence testing for odd modular subgroups #11598