#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 lauder):
Dear David
Many thanks for your message, and for looking so carefully at the code.
This is greatly appreciated!
I am a novice at the SAGE review process, so will wait to get advice from
Sebastian (Pancratz) on exactly what to do next with
the reviewer's patch. In the meantime though perhaps I could address your
comments.
On the Z versus Q basis, I was aware of that problem. In fact, when
modformsring=false the algorithm will not terminate
either if the space of modular forms in low weight does not "generate" a
certain Zp-space of modular forms. (In the magma implementation preamble I
mention that the algorithm is not guaranteed to terminate: I should have
made this more explicit in the sage one.) However, when modformsring=false
in practice if the algorithm does fail to terminate (which I have never
encountered with the default setting of weightbound = 6) then one can
increase "weightbound". (Also, the output is in any case I believe
provably correct, so it never terminates with a false output.)
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. 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).
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.
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).)
- 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.
- 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!
(I must learn how to use the sage profiler.)
- 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.
Best wishes
Alan.
Replying to [comment:6 davidloeffler]:
> Hi Alan,
>
> This is really nice code: I'm very happy that you chose to make this
Sage implementation available.
>
> I am preparing a second reviewer patch, to be applied on top of your
patch, which mainly cleans up the documentation and removes some functions
which already existed in Sage under different names (such as a lot of the
routine linear algebra stuff). However, I've not completed my review,
because I think there's a serious lurking bug.
>
> The problem is this. The code in {{{
sage/modular/modform/find_generators.py }}} is only guaranteed to return
generators for modular forms as a Q-algebra. You've carefully trapped and
dealt with the case when the generators aren't p-adically integral; but
even if the generators happen to be integral, there's no guarantee that
they generate the ring of p-adically integral modular forms as a Zp-
algebra. I experimented by making {{{ModularFormsRing.generators()}}}
multiply its output by 25 before returning it, which is completely
consistent with that function's specifications; and then doing 5-adic
computations with {{{modformsring=True}}} just looped forever. So I don't
think we can use this code without also adjusting
{{{ModularFormsRing.generators()}}} to add the option to do its linear
algebra integrally.
>
> There are a few other (relatively minor) things that puzzle me about
this implementation, as well, and I'd be grateful if you could explain
them to me.
>
> - Is the algorithm, and the implementation, still OK if k is a
*negative* integer? It seems to be, based on all of the tests I ran -- the
output for a negative k looks entirely consistent with the output for
positive integers p-adically close to k. If so, then what does it mean to
say that the run time is polynomial in the logarithm of the weight? Is it
polynomial in the absolute value of the weight?
>
> - Should the level N be prime to p? Jan Vonk made this observation at
the Sage Days a few weeks back. If you run the code with N divisible by p,
it doesn't complain, and returns the same output as for the prime-to-p
part of N, but much more slowly! So we should trap this case. I added code
to do this to my reviewer patch.
>
> - For N > 1, a great deal of time is wasted in the routine
"row_reduced_form". For instance, I ran "hecke_series(5, 3, 4, 15,
modformsring=True)" with the Sage profiler. The command took 29 seconds,
of which 24 seconds was spent in 213 calls to the method
"row_reduced_form". But only 0.052 seconds of that was spent in the matrix
echelon form routine (Sage's mod p linear algebra is pretty quick). The
rest is *all* spent, as far as I can see, in translating back and forth
between power series and vectors.
>
> - In the modformsring = False version of the algorithm, it seems to be
randomized twice over: firstly, the low weight bases are randomized (using
random_low_weight_bases); then a randomized algorithm using these as input
(random_new_basis_modp) is used to compute the complementary spaces. What
is the benefit of randomizing twice in this way?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12043#comment:8>
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.
