Opened 4 years ago

Closed 3 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)

trac_10546-gamma_cusps.patch (6.4 KB) - added by davidloeffler 3 years ago.
Patch against 4.7.1.alpha4 + #11601 and its prerequisites

Download all attachments as: .zip

Change History (8)

Changed 3 years ago by davidloeffler

Patch against 4.7.1.alpha4 + #11601 and its prerequisites

comment:1 Changed 3 years ago by davidloeffler

  • Authors changed from rje to Ron Evans, David Loeffler
  • 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 3 years ago by janv

  • Status changed from needs_review to positive_review

This works perfectly.

comment:3 Changed 3 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 3 years ago by jdemeyer

  • Milestone changed from sage-4.8 to sage-5.0

comment:5 Changed 3 years ago by davidloeffler

  • Keywords sd35 added

comment:6 Changed 3 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 3 years ago by jdemeyer

  • Merged in set to sage-5.0.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.