Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#10506 closed enhancement (fixed)

efficient counting of cusps for the principal congruence subgroup Gamma(n)

Reported by: rje Owned by: John Cremona
Priority: minor Milestone: sage-4.6.2
Component: modular forms Keywords: cusps, ncusps(), Gamma(n), principal congruence subgroup
Cc: Merged in: sage-4.6.2.alpha2
Authors: Ron Evans, John Cremona Reviewers: Ron Evans
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

In the sage-support group, John Cremona suggested writing a ticket aimed at replacing the current code for G.ncusps, where G is the principal congruence subgroup Gamma(n), with more efficient code. Please make a patch using the following replacement code. This new code will compute say Gamma(15).ncusps() in less than a second, instead of the hours it takes with the current code.

n=self.level()

if n<=2:

return[None,1,3][n]

return ZZ((1/2)*sum([moebius(d)*(n/d)*(n/d) for d in n.divisors()]))

Attachments (1)

trac_10506-ncusps.patch (1.5 KB) - added by John Cremona 12 years ago.
applies to 4.6.1.alpha3

Download all attachments as: .zip

Change History (6)

Changed 12 years ago by John Cremona

Attachment: trac_10506-ncusps.patch added

applies to 4.6.1.alpha3

comment:1 Changed 12 years ago by John Cremona

Status: newneeds_review

The patch adds an implentation using the idea I posted on sage-support, namely using the formula (valid for n>2) that the number of cusps for Gamma(n) is half the index of Gamma1(n).

Some times:

sage: timeit('Gamma(15).ncusps()')
625 loops, best of 3: 174 µs per loop
sage: timeit('Gamma(115).ncusps()')
625 loops, best of 3: 176 µs per loop
sage: timeit('Gamma(12115).ncusps()')
625 loops, best of 3: 176 µs per loop
sage: timeit('Gamma(1312115).ncusps()')
625 loops, best of 3: 201 µs per loop

Note that the next job is to add a method to return a set of inequivalent cusps. The default implementation is stupidly slow (as proved by the fact that the old default for ncusps() was to find all the cusps and count them).

That should be on another ticket.

comment:2 Changed 12 years ago by rje

Authors: Ron EvansRon Evans / John Cremona
Reviewers: Ron Evans
Status: needs_reviewpositive_review

The product formula in the patch is equivalent to the summation formula in my ticket, and is faster! The examples given are all correct.

comment:3 Changed 12 years ago by Jeroen Demeyer

Milestone: sage-4.6.1sage-4.6.2

comment:4 Changed 12 years ago by Jeroen Demeyer

Merged in: sage-4.6.2.alpha2
Resolution: fixed
Status: positive_reviewclosed

comment:5 Changed 12 years ago by Jeroen Demeyer

Authors: Ron Evans / John CremonaRon Evans, John Cremona
Note: See TracTickets for help on using tickets.