# Ticket #10506(closed enhancement: fixed)

Opened 2 years ago

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

Reported by: Owned by: rje John Cremona minor sage-4.6.2 modular forms cusps, ncusps(), Gamma(n), principal congruence subgroup N/A Ron Evans Ron Evans, John Cremona sage-4.6.2.alpha2

### 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()]))

## Change History

### Changed 2 years ago by cremona

applies to 4.6.1.alpha3

### comment:1 Changed 2 years ago by cremona

• Status changed from new to needs_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 2 years ago by rje

• Status changed from needs_review to positive_review
• Reviewers set to Ron Evans
• Authors changed from Ron Evans to Ron Evans / John Cremona

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 2 years ago by jdemeyer

• Milestone changed from sage-4.6.1 to sage-4.6.2

### comment:4 Changed 2 years ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-4.6.2.alpha2

### comment:5 Changed 2 years ago by jdemeyer

• Authors changed from Ron Evans / John Cremona to Ron Evans, John Cremona
Note: See TracTickets for help on using tickets.