Opened 11 years ago

Last modified 5 years ago

#10510 new defect

ModularSymbols(Gamma1(29), 2).cuspidal_subspace().hecke_algebra().basis() doesn't terminate

Reported by: mderickx Owned by: craigcitro
Priority: major Milestone:
Component: modular forms Keywords:
Cc: davidloeffler Merged in:
Authors: mderickx Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by was)

It also doesn't terminate for other primes then 29, but here is a more detailed example of the case 29 which should illustrate everything

The sourcecode which determines the basis is currently:

def basis(self):
    try:
        return self.__basis_cache
    except AttributeError:
        pass
    level = self.level()
    bound = self.__M.hecke_bound()
    dim = self.__M.rank()
    if dim == 0:
        basis = []
    elif dim == 1:
        basis = [self.hecke_operator(1)]
    else:
        span = [self.hecke_operator(n) for n in range(1, bound+1) if not self.is_anemic() or gcd(n, level) == 1]
        rand_max = 5
        while True:
            # Project the full Hecke module to a random submodule to ease the HNF reduction.
            v = (ZZ**dim).random_element(x=rand_max)
            proj_span = matrix([T.matrix()*v for T in span])._clear_denom()[0]
            proj_basis = proj_span.hermite_form()
            if proj_basis[dim-1] == 0:
                # We got unlucky, choose another projection.
                rand_max *= 2
                continue
            # Lift the projected basis to a basis in the Hecke algebra.
            trans = proj_span.solve_left(proj_basis)
            basis = [sum(c*T for c,T in zip(row,span) if c != 0) for row in trans[:dim]]
            break

    self.__basis_cache = tuple(basis)
    return basis

Now dim equals 44 and the hecke bound 140 in this example:

sage: G29=Gamma1(29)
sage: M=ModularSymbols(G29,2)
sage: m=M.cuspidal_subspace()
sage: m.rank()
44
sage: m.hecke_bound()
140

Now we see that the hecke algebra has rank 22 over ZZ

sage: HA=m.hecke_algebra()
sage: span = [HA.hecke_operator(n) for n in range(1, 140+1) if not HA.is_anemic() or gcd(n, 29) == 1]
sage: (ZZ^(44^2)).span([i.matrix().list() for i in span])
Free module of degree 1936 and rank 22 over Integer Ring
Echelon basis matrix:
22 x 1936 dense matrix over Rational Field

So as the comment say's we are unlucky since proj_basis[43] will always be zero since the hecke algebra has only rank 22

            if proj_basis[dim-1] == 0:
                # We got unlucky, choose another projection.
                rand_max *= 2
                continue

I suspect there is a problem in that the rank of m is 44 over QQ. But that the rank of the hecke algebra will be the dimension of m as a complex vector space so dim should actually be half of what it is now.

I don't know enough of modular symbols yet to know how it should be done in other weights and other modular groups but I suspect there will be problems there also.

Change History (4)

comment:1 Changed 11 years ago by was

  • Description modified (diff)

comment:2 Changed 11 years ago by was

  • Description modified (diff)

comment:3 Changed 5 years ago by kedlaya

Reawakening this moribund ticket: I just ran this in 7.3 and the behavior appears to be unchanged.

comment:4 Changed 5 years ago by kedlaya

  • Cc davidloeffler added

There is some other code for bases in the same file which doesn't seem to suffer from the same issue:

sage: from sage.modular.hecke.algebra import _heckebasis
sage: H = ModularSymbols(Gamma1(29), 2).cuspidal_subspace().hecke_algebra()
sage: _heckebasis(H.module())
[Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field,
 Hecke operator on Modular Symbols subspace of dimension 44 of Modular Symbols space of dimension 71 for Gamma_1(29) of weight 2 with sign 0 and over Rational Field defined by:
 44 x 44 dense matrix over Rational Field]

CC'ing davidloeffler since he appears to have worked on some of this code.

Note: See TracTickets for help on using tickets.