Opened 12 years ago

Closed 11 years ago

# implement a custom cusps() method for principal congruence subgroups Gamma(N)

Reported by: Owned by: rje John Cremona minor sage-5.0 modular forms sd35 inequivalent cusps, principal congruence subgroup, Gamma(n), cusps() sage-5.0.beta1 Ron Evans, David Loeffler Jan Vonk N/A #10335, #11422, #11598, #5048, #10453, #11601

### 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

### Changed 11 years ago by David Loeffler

Patch against 4.7.1.alpha4 + #11601 and its prerequisites

### comment:1 Changed 11 years ago by David Loeffler

Authors: rje → Ron Evans, David Loeffler → #10335, #11422, #11598, #5048, #10453, #11601 new → 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 11 years ago by Jan Vonk

Status: needs_review → positive_review

This works perfectly.

### comment:3 Changed 11 years ago by Jeroen Demeyer

Reviewers: → 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 11 years ago by Jeroen Demeyer

Milestone: sage-4.8 → sage-5.0