#12043: Hecke series for overconvergent modular forms
-----------------------------+----------------------------------------------
Reporter: lauder | Owner: craigcitro
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-4.8
Component: modular forms | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: lauder
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Comment(by davidloeffler):
Replying to [comment:8 lauder]:
> When modformsring=true, as you noticed the algorithm defaults to
modformsring = false when the ModularFormsRings.generators() gives non
p-adically integral generators. I did ask William (Stein) about
> the possibility of having an integral_generators() function in this
case: looking at the source code I could not see an
> obvious obstruction to this.
>
Are you asking for integral_generators to return (a) modular forms which
have integral q-expansions and are Q-algebra generators for the ring of
all modular forms, or (b) Z-algebra generators for the ring of integral
modular forms? The former would be completely trivial to do. The latter is
certainly possible, but would be harder; in fact it would be a great thing
to have anyway, but it would be much slower than the current
implementation of course.
>
> The key point for me though was the following: The generators() function
only gives a set
> of modular forms which generate over Q all forms up to maxweight
(default 20). If one increased maxweight to a value which
> guaranteed that (over Q at least) one had all the modular forms you need
(weight k0 + n(p-1) in the notation in my paper)
> then the generators() function would take much much longer. So even if
one had an integral_generators() function, to
> absolutely guarantee that the algorithm terminates one would need
"maxweight = k0 + n(p-1)" and this would seriously
> impact on the time taken to find the generators. So I thought it is
better to live with the possibility of the algorithm not terminating,
since it seems unobservably small (at least, I have not observed it when
modformsring = false and weightbound = 6, although I have not experimented
so much when modformsring = true).
>
I'm pretty sure it's true that for all N, the ring of modular forms of
level N is generated over Q by forms of weight at most 6. Working out the
details is a fiddly exercise which I should probably just sit down and do
one of these days. But of course to get integral generators you might need
larger weights.
Perhaps using some more algebraic geometry one can bound above the max
weight needed for generators over Zp (at least for p not dividing the
level). There is some yoga with ample line bundles that I've never quite
got my head around.
>
> That said though I think your point is a very good one. In particular,
if one had an integral_generators() function then
> one could just set modformsring = true "permanently" (and perhaps
replace the "weightbound" optional parameter
> with "maxweight" in the main function). In any case, the fact that the
algorithm may in principle fail to terminate needs to be clear in the
documentation.
I'm not sure what the policy is on including algorithms which aren't known
to terminate, I'd have to check. That would simplify the code a lot, which
would be nice. We can certainly make the generators code return generators
over Q which were integral (but not necessarily integral generators),
which would mean we could remove the fallback code.
>
> On your other points:
>
> - Yes, negative k is fine and the algorithm has running time polynomial
log(|k| + 1) . (I do clarify this point at the start of
> Section 3.2.2 in my paper, but have got into the habit of just writing
polynomial in log(k).)
>
OK, thanks; I missed that in the paper.
>
> - Yes, for the theoretical analysis of the algorithm I need N prime to
p, although as you observed it does seem to work in practice (and perhaps
in theory) regardless. Again, the magma implementation picks this up:
thanks for sorting it out here.
>
Well, thanks here are due to Jan, not me :-)
>
> - This is a very interesting observation: I had not realised so much
time was taken up doing this! I would have to think about this more
carefully, but I think the main point of the call to row_reduced_form is
simply to detect when one has increased the rank of the space of mod p
modular forms. Since "TotalBasisModp" was already in "echelon form" (as a
list of q-series)
> before "TotalBasisi" was appended, the fact that the matrix echelon form
is so quick is not surprising: only the final row needs to be done. It
sounds to me that it might be much better to avoid matrices altogether,
and just write a little function which
> given a list of q-series in "echelon form" modulo p, appends a new
q-series and "echelonises". Many thanks for spotting this!
>
There is a choice to be made here: one can either work consistently with
power series objects, or consistently with vectors. You seem to be
suggesting the first, but I'd strongly recommend the second: this allows
you to use Sage's very fast echelon form routines, which are written in C,
rather than using hand-rolled Python versions which would inevitably be
much slower. There is some code in modforms/find_generators.py which does
something quite similar to this, and that works with vectors where
possible.
>
> (I must learn how to use the sage profiler.)
>
It's really simple: all I did was to type
{{{
sage: %prun hecke_series(5, 3, 4, 15, modformsring=True)
}}}
and that does the job.
>
> - The problem I encountered when not randomising the low weight bases
was as follows: the low weight bases are given by default in echelon form,
at least a union of the cuspidal and eisenstein spaces in that form. When
you multiply random
> elements from such a basis together, they have a tendency to vanish (to
higher order) at q = 0. I noticed in an early
> implementation that I could generate the spaces more quickly by
randomising the bases to start with. So I have always done this: it is
probably worth checking again though whether it is really helping.
>
I see. Yes, that makes a lot of sense -- if your random products of the
basis in random_new_basis_modp are landing in a specific subspace with
high probability then it's clearly not good.
You'll notice that in the reviewer patch I got rid of a call to {{{ GL(n,
p).random_element()}}}, which was overwhelmingly dominating the run time
in the modformsring=False case; on my machine {{{ GL(4,
3).random_element()}}} takes nearly two whole seconds! This is a bug, and
should probably be reported as such.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12043#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
