Better congruence testing for odd arithmetic subgroups

[loefflerd]

This patch relates to the is_congruence() method of arithmetic subgroups of SL2Z (described in terms of permutations, cf. sage.modular.arithgroup.arithgroup_perm). For even subgroups (containing -1), there is a very fast algorithm due to Tim Hsu, but for odd subgroups we were using a much, much slower brute-force algorithm.

My student Thomas Hamilton checked in his MMath thesis that Hsu's algorithm also works for odd subgroups with minor modifications. This patch implements this generalized Hsu algorithm, resulting in a speedup of about three orders of magnitude in all the examples I tried.

CC: @videlec

Component: modular forms

Author: David Loeffler

Branch/Commit: 27b7508

Reviewer: Vincent Delecroix

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

[loefflerd]

comment:2

Vincent: I'm ccing you on this ticket, since it was you who originally suggested that Hsu's algorithm should work for odd subgroups too (#11598 comment:3)

[videlec]

comment:3

Hello,

Sorry to answer lately. This is quite nice that it works!

I am starting the review...

[videlec]

Reviewer: Vincent Delecroix

[videlec]

Work Issues: bring back old code + minor doc

[videlec]

comment:4

I would prefer to keep both implementations (naive one vs checking relations with default to the latter one of course ;-). Then you may add a dedicated test comparing the results in sage.modular.arithgroup.tests. Otherwise the new implementation is well documented and everything works.

Is your result available to read ? A dissertation is a legitimate reference, but one may want to read it.

Why did you remove the reference of the article of Alexey G. Gorinov ? I do not claim that it is not a good idea but just that it was not the purpose of the ticket.

[loefflerd]

comment:5

Dear Vincent,

Nice to hear from you; sorry it's taken me so long to look at this in turn...

• I didn't remove the reference to Gorinov. I just moved it a little higher in the list so the references were listed in alphabetical order.

• Hamilton's dissertation isn't available publicly anywhere, sadly; Warwick doesn't maintain an archive of MMath dissertations, although it does for MSc and PhD degrees. If you want to check the result, I have a copy I can send to you personally, if you like.

• I'm not quite sure what you're suggesting re keeping both algorithms. At the moment we have one (fast) algorithm for even subgroups only, and another (much slower) algorithm for odd subgroups. It seems silly to distinguish needlessly between even/odd -- would you be happier with a setup where we have both algorithms available for both types of subgroups (with the fast one the default, of course)?

[videlec]

Changed work issues from bring back old code + minor doc to ref issue + test

[videlec]

comment:6

Hi,

Replying to @loefflerd:

• I didn't remove the reference to Gorinov. I just moved it a little higher in the list so the references were listed in alphabetical order.

My mistake.

• Hamilton's dissertation isn't available publicly anywhere, sadly; Warwick doesn't maintain an archive of MMath dissertations, although it does for MSc and PhD degrees. If you want to check the result, I have a copy I can send to you personally, if you like.

I would appreciate a copy but this is not the point. If you mention the Math dissertation as a reference for the algorithm it should be available for anyone. What about arXiv ?

• I'm not quite sure what you're suggesting re keeping both algorithms. At the moment we have one (fast) algorithm for even subgroups only, and another (much slower) algorithm for odd subgroups. It seems silly to distinguish needlessly between even/odd -- would you be happier with a setup where we have both algorithms available for both types of subgroups (with the fast one the default, of course)?

You are right. It would be better to keep the fast algorithm only and to implement the naive test within the Test class and check that the answers coincide.

Best
Vincent

[loefflerd]

comment:7

I'd need Hamilton's permission to put the work on the arxiv, I'll see if that can be got.

[loefflerd]

comment:8

Dear Vincent,

Hamilton gave his permission for the work to be put on the Arxiv, so here's a new patch that references the Arxiv preprint. There is also a test in "tests.py" which compares is_congruence against congruence_closure, and a slight tweak to the congruence subgroup initialization code that makes the test run a little faster.

Best regards, David

[loefflerd]

Changed work issues from ref issue + test to none

[videlec]

comment:9

patchbot is unhappy on 5.11.beta3. Is that normal?

[loefflerd]

Rebased to 5.11.beta3

[loefflerd]

comment:10

Attachment: trac_12949.patch.gz

It conflicted with #14014. I've rebased it.

[videlec]

comment:11

Great! I am really happy that it was possible to put it on arxiv. Everything looks fine except for the tests: sage -t on sage.modular.arithgroup.tests was around 10sec and is now 576.57sec which is not reasonable. When testing the congruence try to set index_max to a much smaller value. You should also add some # long time wherever appropriate.

I also notice that

• the Test class should be clean up (there is no reason to use print and there should be more occurences of tests inside the documentation)
• there is a broken link in the documentation (see this sage-devel thread)
  ... but this ticket has nothing to do with it ;-)

Best,
Vincent

[videlec]

Work Issues: test

[vbraun]

comment:36

Does this ticket really need super-long doctests to test things that absolutely cannot be tested by smaller parameters? Maximum time should be a few seconds, not minutes. There is no point in running huge computations if they don't test anyting that is already tested with smaller tests. Times out on slower buildbots.

[vbraun]

Changed commit from 337fc95 to none

[loefflerd]

Changed branch from 337fc95 to u/davidloeffler/337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3

[loefflerd]

Changed branch from u/davidloeffler/337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 to u/davidloeffler/12949

[loefflerd]

comment:40

I've uploaded a new version without the time-wasting tests.

(For some reason, this ticket had been linked to a Git branch which "git trac" refused to read, so I just spent the entire morning re-applying the changes by hand.)

---

New commits:

d8e4dea	Trac 12949: better congruence testing
a221151	Trac 12949: fixed ReST formatting errors

[loefflerd]

Commit: a221151

[videlec]

comment:42

Hello,

Replace ZZ(~Zmod(N)(2)) with ZZ(2).inverse_mod(N) (several occurrences).

Do you know why L.order() returns a Python int and not an Sage Integer? It looks like a bug to me as for example

sage: type(Zmod(5)(3).order())
<type 'sage.rings.integer.Integer'>

Vincent

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

27b7508

Trac 12949: changes suggested by reviewer

[sagetrac-git]

Changed commit from a221151 to 27b7508

[loefflerd]

comment:44

I made the changes you suggested. I agree that the return type of "order" for perm group elements looks like a bug, so I changed that, although it has nothing really to do with this ticket.

[videlec]

comment:45

Good!

[vbraun]

Changed dependencies from #12233 to none

[vbraun]

Changed branch from u/davidloeffler/12949 to 27b7508