Opened 5 years ago
Closed 4 years ago
#10546 closed enhancement (fixed)
implement a custom cusps() method for principal congruence subgroups Gamma(N)
Reported by: | rje | Owned by: | John Cremona |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.0 |
Component: | modular forms | Keywords: | sd35 inequivalent cusps, principal congruence subgroup, Gamma(n), cusps() |
Cc: | Merged in: | sage-5.0.beta1 | |
Authors: | Ron Evans, David Loeffler | Reviewers: | Jan Vonk |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10335, #11422, #11598, #5048, #10453, #11601 | Stopgaps: |
Description
The command "Gamma(n).cusps()" computes a complete list of inequivalent cusps for the congruence subgroup
Gamma(n), but it is very slow.
For example, look at the time required just for n=8:
sage: time Gamma(8).cusps()
CPU times: user 1086.11 s, sys: 5.60 s, total: 1091.71 s
Wall time: 1092.30 s
[Infinity, 0, 1, 2, 3, 4, 5, 6, 7, -1/2, -1/3, -1/4, -1/5, -1/6, 2/3, 3/4, 4/5, 5/6, 5/3, 11/6, 8/3, 11/3, 14/3, -3/8]
I've defined a function f(n) below that returns a complete list of inequivalent cusps for the group Gamma(n) (n>2). The elements of the list are in so-called "reduced_cusp form". The cusp 1/n in the list is the one equivalent to Infinity. Please use f(n) to make a patch for Gamma(n).cusps(), n>2.
def f(n):
C=[0..n-1]
n1=integer_floor((n-1)/2)
n0=integer_floor(n/2)
for r in [1..n1]:
if gcd(r,n)==1:
C.append(r/n)
if n0==n/2 and gcd(r,n0)==1:
C.append(r/n0)
for s in [2..n1]:
for r in [1..n]:
if gcd([s,r,n])==1:
m=r
while gcd(m,s)>1:
m=m+n
C.append(m/s)
return(C)
Here is an example for n=8:
sage: time f(8)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
[0, 1, 2, 3, 4, 5, 6, 7, 1/8, 1/4, 3/8, 3/4, 1/2, 3/2, 5/2, 7/2, 1/3, 2/3, 11/3, 4/3, 5/3, 14/3, 7/3, 8/3]
The following gives an idea of the speed of f(n):
sage: time len(f(1260))
CPU times: user 16.66 s, sys: 0.41 s, total: 17.07 s
Wall time: 17.07 s
497664
The following checks the length 497664 of the list of inequivalent cusps:
sage: prod([p(2*e) - p(2*e-2) for (p,e) in 1260.factor()])2
497664
Attachments (1)
Change History (8)
Changed 5 years ago by davidloeffler
comment:1 Changed 5 years ago by davidloeffler
- Dependencies set to #10335, #11422, #11598, #5048, #10453, #11601
- Status changed from new to needs_review
I made a patch based on the code by rje (Ron Evans, I presume?) above.
It implements cusps, and also are_equivalent and reduce_cusp. The cusps code is more or less identical to Ron's code but marginally faster; it also sorts its output, and returns infinity rather than 1/N in line with Sage's conventions for the definition of "reduced".
I built this on top of #11601, so it now depends on that and its prerequisites (the series of patches which goes #10335 - #11422 - #11598 - #5048 - #10453 - #11601). I'm hoping these will get positively reviewed soon (the first three already have been), but if not it would be easy to recreate the patch without the dependency on #11601.
comment:2 Changed 4 years ago by janv
- Status changed from needs_review to positive_review
This works perfectly.
comment:3 Changed 4 years ago by jdemeyer
- Reviewers set to Jan Vonk
Jan, in the future you should add your name as Reviewer. And please also add yourself to http://trac.sagemath.org/sage_trac/#AccountNamesMappedtoRealNames
comment:4 Changed 4 years ago by jdemeyer
- Milestone changed from sage-4.8 to sage-5.0
comment:5 Changed 4 years ago by davidloeffler
- Keywords sd35 added
comment:6 Changed 4 years ago by davidloeffler
- Keywords changed from sd35, inequivalent cusps, principal congruence subgroup, Gamma(n), cusps() to sd35 inequivalent cusps, principal congruence subgroup, Gamma(n), cusps()
comment:7 Changed 4 years ago by jdemeyer
- Merged in set to sage-5.0.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Patch against 4.7.1.alpha4 + #11601 and its prerequisites