Serious bug in modular symbols for GammaH

[craigcitro]

There are currently serious problems with the computation of cuspidal subspaces on GammaH. Here's something fairly horrifying:

sage: M = ModularSymbols(GammaH(25,[6])) ; S = M.cuspidal_subspace() ; S
sage: S
Modular Symbols subspace of dimension 3 of Modular Symbols space of dimension 11 for Congruence Subgroup Gamma_H(25) with H generated by [6] of weight 2 with sign 0 and over Rational Field
sage: sage.modular.dims.dimension_cusp_forms_H(GammaH(25,[6]),2)
0
sage: S.decomposition()
---------------------------------------------------------------------------
<type 'exceptions.ArithmeticError'>       Traceback (most recent call last)
...
<type 'exceptions.ArithmeticError'>: subspace is not invariant under matrix

sage: S.basis_matrix()
[ 1 -1  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  1  0  0 -1]
sage: S.basis_matrix() * M.hecke_matrix(2)
[ 1 -1  2  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0  0  0  0  0  0]
[ 0  0 -2  1  0  0 -1  0  0  0  0]

Notice that at the bottom there, the cuspidal subspace isn't invariant under the Hecke operator T_2. Of course, that's because the cuspidal subspace should be 0. The problem was in the _reduce_cusp function -- basically the algorithm there had a number of problems. After some doing, I came up with a new algorithm that worked. (This isn't terribly hard, but is very delicate.) Of course, after writing the algorithm, I realized that we don't even need it -- we can just write is_gamma_h_equiv the same way we do the other congruence subgroups, because we have an explicit condition on when two cusps are equivalent. However, I left the code in for _reduce_cusp ... I don't know what one might use it for, but hey, it's already written. At the very least, it lets you compute the cusps in two distinct ways, which is always reassuring.

I've run a bunch of consistency checks, so I feel pretty confident about this code. In particular, we get the same answers for GammaH(N,[]) and Gamma1(N) for N up to about 100, and I checked (via consistency checks and checking dimensions against the dimension formulas in sage.modular.dims for spaces of modular symbols) on what I thought was a "representative set" of examples. That said, these bugs have been around for a while now -- so I'm happy to have the referee give this code a serious thrashing, and see if anything comes up.

I haven't worked too hard at optimizing any of this code -- I'm much more concerned with getting correct code in right away. I'm happy to file a ticket saying "optimize this," which I'll take care of in the next few weeks. We should also probably file a ticket that says "look over _reduce_coset" -- that code looks very similar to where this code started, so it's possibly producing some funky answers, too.

Since sage is actually producing wrong answers (as opposed to just throwing errors), I'm listing this as a blocker for 3.0.2.

Component: modular forms

Issue created by migration from https://trac.sagemath.org/ticket/3217

[craigcitro]

Attachment: trac-3217.patch.gz

[sagetrac-mabshoff]

comment:1

This looks like something for William to review.

Cheers,

Michael

[craigcitro]

comment:2

The _reduce_cusp function is longer and more complicated, but it's important to note that it's now not called anywhere in the Sage library. If need be, we could always just merge the new is_gamma_h_equiv in 3.0.2 (which is easy to review), kill the old _reduce_cusp, and then merge that in the next cycle when there's more time to read it.

[JohnCremona]

comment:3

The patch applies cleanly to 3.0.2 and passes doctests.

I have not tested the code apart from the above (and below). I do approve of the philosophy outlined, namely to rely on an equivalence test rather than a reduction to normal form, since the latter is notoriously hard to get right. But I see no harm in keeping cusp reduction in there.

Shouldn't there be an additional doctest showing that the specific reported problem is now solved: even

sage: ModularSymbols(GammaH(25,[6])).cuspidal_subspace().dimension()
0

perhaps?

[sagetrac-mabshoff]

comment:4

Merged in Sage 3.0.3.alpha0.

I would definitely merge an added doctest patch that tests the original issue even assuming it is already covered by the new doctests.

Cheers,

Michael

[craigcitro]

comment:5

John -- thanks very much for refereeing this! I should have realized to ask you earlier -- I was basically following a proof from your book.

I'm happy to add another doctest with the failure -- but it's basically already there. (See lines 613-614 in sage/modular/cusps.py.) Let me know if you think I should still add anything ...

[JohnCremona]

comment:6

Replying to @craigcitro:

John -- thanks very much for refereeing this! I should have realized to ask you earlier -- I was basically following a proof from your book.

I'm happy to add another doctest with the failure -- but it's basically already there. (See lines 613-614 in sage/modular/cusps.py.) Let me know if you think I should still add anything ...

You are quite right: those lines demonstrate precisely that the original problem case is now correct. So I don't believe any more is necessary, and this can remain closed and be resolved (or whatever the right term is to make it display with a line through!)