#21046 closed enhancement (fixed)
Numerical modular symbols for elliptic curves
Reported by:  wuthrich  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  elliptic curves  Keywords:  modular symbols 
Cc:  cremona, mmasdeu, was, pbruin  Merged in:  
Authors:  Chris Wuthrich  Reviewers:  Varenyam Bakshi 
Report Upstream:  N/A  Work issues:  
Branch:  1a1a8ef (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
I propose here to add fast modular symbols for elliptic curves. The proposed changes would add a cython file containing the new code to work with numerical modular symbols and integrate them for using for elliptic curves and their padic Lfunctions.
The idea is similar to #6666, where "analytic modular symbols" were added to elliptic curves. However the code there is very slow and this ticket would replace that code completely.
So a modular symbol for a given elliptic curve can be computed using numerical integration on the upper half plane rather than using linear algebra to determine the space of all modular symbols of level N first. Unlike #6666, we use rigorous bounds on the error of computations to be certain that we get the correct rational number.
The code here compares in speed with eclib and is wayway faster than the python code within sage. When computing a single modular symbol or a few with small denominator, the code here is much faster than eclib and can cope with conductors in the millions. When computing all manin symbols for one curve, the speed is in the same order as for eclib for semistable curves, but sometimes slower.
The preprint explaining all is here.
Change History (43)
comment:1 Changed 5 years ago by
 Branch set to u/wuthrich/ticket/21046
 Commit set to 63c6606552ea3a256b90596b609539853cb46755
comment:2 Changed 5 years ago by
 Description modified (diff)
comment:3 Changed 5 years ago by
 Cc cremona mmasdeu was added
 Status changed from new to needs_review
comment:4 Changed 5 years ago by
 Cc pbruin added
comment:5 followup: ↓ 7 Changed 4 years ago by
comment:6 Changed 4 years ago by
This does not merge cleanly onto the current branch at #10256 and I suggest that we get that one finished, then merge that onto this, fixing any conflicts, before getting back to reviewing this.
comment:7 in reply to: ↑ 5 Changed 4 years ago by
Hi John,
I am rebasing it now and I am trying to put in your comments already. I hope I have a new version soon.
Replying to cremona:
 in one place you talk about making the precision "small" where there is a default prec=53, so haps that should be "large".
I am trying to find that.
 After "The Manin constant for the
X_0
optimal curve should be1
if the curve lies outside the Cremona tables" you could add that with the range of the tables this is proved! (That is perhaps implicit anyway, but not explicit.)
done.
 since you can call M(r) with a sign other than the one with which M was created, why specify a sign on creation at all? Is it just to set a default?
 the method M.value_r_to_rr() is rather a clumsy name. Can you not make this just M(r,rr), where rr defaults in infinity?
I modelled __call__
on the other modular symbols, so that E.modular_symbol(implementation...)
all have the same call function.
Hence the possibility for the user to specify the dafault sign.
On second thought, I decided to make value__r_to_rr
and value_r_to_ioo
inaccessible. The reason is that the function as implemented only works for unitary cusps anyway. I can not see a use of having M(r,rr). The origin is a canonincal basepoint for homology on E. Anyway, it would not take much longer to write M(r)M(rr).
Someone who knows cython should look at the code too (robertb?)
Sure, if we can motivate someone.
It seems a pity to me that you need a new class for your cusps rather than adding to the existing class.
Maybe the name is misleading. This is really a rational point on the boundary of the upper half plane, not a point on a modular curve. I did not want to load anything heavy just for computing W_r.
In one place you mention that I do not always guarantee the optimal curve, which is correct (though I always guarantee c=1, if necessary by computing the full modular symbol not just the plus symbol). See https://raw.githubusercontent.com/JohnCremona/ecdata/master/doc/manin.txt I am not sure what is going on where you multiply t0 by 2 "just in case".
There is not a unique maximal curve in the isogeny class. Any two maximal ones are linked by a two isogeny to a common curve. So if we had the wrong maximal curve then an extra factor 2 will guarantee that we only assume that the Manin constant for one of the curves in the class is trivial. Moreover the Manin constant for semistable curves is known to be 1 or 2, so it is really a harmless precaution.
In one place you divide D by the maximal power of a prime l. You could there use
sage: N=10^10 sage: N.prime_to_m_part(5) 1024
changed
The underlying summations to give the numerical values are of course also implemented in eclib (to arbitrary precision there too). One day it would be possible to add the relevant functions to the eclib interface and use that (compiled C, possibly fater than cython).
True. It would then make more sense to transport the whole code. But that is going to happen after my retirement, I fear.
In the function where it says that setup_twist needs to be called first, should there be a flag to indicate that that has been done (and calls the setup here if not set)? Safer?
The flag is that _D
is set to 1. That is change in _twisted_symbol
, too.
comment:8 Changed 4 years ago by
 Commit changed from 63c6606552ea3a256b90596b609539853cb46755 to 4de004a564c27368d3a1d2e6df97c251dd767f12
Branch pushed to git repo; I updated commit sha1. New commits:
cd85b8f  Merge branch sage 7.4.beta4 into ticket/21046_modsymnum

4dbfdef  Merge branch 'ticket/21046_modsymnum' of ssh://warrior.maths.nottingham.ac.uk/home/pmzcw/prog/sage into ticket/21046_modsymnum

cb3fd05  #22077 update eclib to v20170104

ee879ee  work in progress on modular symbols

0db2a00  trac #10256: reviewer patches: first part, highlight wrong values, references

49be7d8  10256: fix one doctest

9f376a6  Merge 10256 and sage 7.5

30f9cd3  Trac #21046: merge with new eclib version and sage 7.5

4de004a  trac #21046: review corrections

comment:9 Changed 4 years ago by
 Dependencies changed from #20864 to #20864 #10256 (and so the linked eclib version at #22077)
comment:10 Changed 4 years ago by
use py3 syntax for raise:
++ raise ValueError, "ECModularSymbol can only be created with signs +1 or 0, not {}".format(sign) +Oldstyle raise statement inserted on 1 nonempty lines
comment:11 Changed 4 years ago by
That slipped in at #10256. I will correct it here. But I wait to see if there is more to do.
comment:12 Changed 4 years ago by
 Branch changed from u/wuthrich/ticket/21046 to public/21046
 Commit changed from 4de004a564c27368d3a1d2e6df97c251dd767f12 to 0dfe075f42258fdba83e9c08fb9c51675ed73430
 Dependencies #20864 #10256 (and so the linked eclib version at #22077) deleted
comment:13 Changed 4 years ago by
 Milestone changed from sage7.3 to sage8.1
comment:14 Changed 4 years ago by
 Commit changed from 0dfe075f42258fdba83e9c08fb9c51675ed73430 to edf6e6dae2595468381bd40435fd4ddcea95e77e
Branch pushed to git repo; I updated commit sha1. New commits:
edf6e6d  convert EXAMPLE:: to EXAMPLES::

comment:15 Changed 4 years ago by
Thanks a lot for the help, especially because I would not have known about these changes. It seems to work just as before. So this is still up for a reviewer to review it....
comment:17 Changed 3 years ago by
 Commit changed from edf6e6dae2595468381bd40435fd4ddcea95e77e to 81ec21003234e9ce26e8e78564ffaa10e5888e57
Branch pushed to git repo; I updated commit sha1. New commits:
81ec210  Merge branch 'develop' at 8.2.rc4 into modsymnum

comment:18 Changed 3 years ago by
 Status changed from needs_work to needs_review
Interest in this seems low, but I did the merge and it would be ready for review again.
comment:19 Changed 3 years ago by
Sorry I am new to this, I think this should to be checked:
ainvs = [1, 1, 1, 1391, 25849] E = EllipticCurve(ainvs) M = E.modular_symbol(implementation="num") M(1/2), M(1/5) L = E.padic_lseries(5, implementation = 'num')
returns the following: (0, 12) Error in lines 44 Traceback (most recent call last):
File "/usr/local/lib/python2.7/distpackages/smc_sagews/sage_server.py", line 995, in execute
exec compile(block+'\n', , 'single') in namespace, locals
File "", line 1, in <module> File "sage/misc/cachefunc.pyx", line 2014, in sage.misc.cachefunc.CachedMethodCaller?.call (build/cythonized/sage/misc/cachefunc.c:10787)
w = self._instance_call(*args, kwds)
File "sage/misc/cachefunc.pyx", line 1890, in sage.misc.cachefunc.CachedMethodCaller?._instance_call (build/cythonized/sage/misc/cachefunc.c:10243)
return self.f(self._instance, *args, kwds)
File "/projects/d8842e1c6d954e6db45def46e7303532/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/padics.py", line 214, in padic_lseries
normalize = normalize, implementation = implementation)
File "/projects/d8842e1c6d954e6db45def46e7303532/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/padic_lseries.py", line 201, in init
crla = E.label()
File "/projects/d8842e1c6d954e6db45def46e7303532/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/ell_rational_field.py", line 3991, in cremona_label
label = self.database_attributes()cremona_label?
File "sage/misc/cachefunc.pyx", line 2377, in sage.misc.cachefunc.CachedMethodCallerNoArgs?.call (build/cythonized/sage/misc/cachefunc.c:13430)
self.cache = f(self._instance)
File "/projects/d8842e1c6d954e6db45def46e7303532/sage/local/lib/python2.7/sitepackages/sage/schemes/elliptic_curves/ell_rational_field.py", line 715, in database_attributes
raise LookupError?("Cremona database does not contain entry for " + repr(self))
LookupError?: Cremona database does not contain entry for Elliptic Curve defined by y^{2 + x*y + y = x}3  x^{2  1391*x  25849 over Rational Field }
comment:20 Changed 3 years ago by
 Status changed from needs_review to needs_work
This is not a bug introduced by this code, but it make sense to fix it here, too. Before this patch it did not make much sense to ask for a curve with that large conductor (700002). I shall fix that soon.
comment:21 Changed 3 years ago by
 Commit changed from 81ec21003234e9ce26e8e78564ffaa10e5888e57 to 00a8630855ad6d61bc31d7d5676fc535150e56c6
comment:22 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:24 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:25 Changed 3 years ago by
I am afraid, I won't update this until someone makes a sign that they are interested in reviewing the ticket.
comment:26 Changed 3 years ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:27 Changed 17 months ago by
 Branch changed from public/21046 to public/21046_new
 Commit changed from 00a8630855ad6d61bc31d7d5676fc535150e56c6 to 77e0af87a0a2b3cb393fcd064454c0bdb77e69ef
 Status changed from needs_work to needs_review
I needed the code again so I updated it to 9.0.beta8 and python3. It seems to work, but I am not too sure all coding is python3esque.
comment:28 Changed 17 months ago by
 Status changed from needs_review to needs_work
At the very least I have to move the references.
comment:29 Changed 17 months ago by
 Commit changed from 77e0af87a0a2b3cb393fcd064454c0bdb77e69ef to 5f79bbbcc5c0176632466dd301838fa29665a513
Branch pushed to git repo; I updated commit sha1. New commits:
5f79bbb  small edits, move biblio

comment:30 Changed 17 months ago by
The patchbot is (since very recent changes in the patchbot) not happy about:
 lines ending with space then
:
(there should be no space before a colon)
 lines starting with
Returns
(one should useReturn
in the firstline descriptions)
comment:31 Changed 17 months ago by
Thanks, Frédéric. Precisely what I wondered about. I will fix that soon.
comment:32 Changed 17 months ago by
 Commit changed from 5f79bbbcc5c0176632466dd301838fa29665a513 to ffe5df066ed8b7782e6640652bc9d468eeee4e44
Branch pushed to git repo; I updated commit sha1. New commits:
ffe5df0  spacing and wording

comment:33 Changed 16 months ago by
 Commit changed from ffe5df066ed8b7782e6640652bc9d468eeee4e44 to 1a1a8ef6767c837428d04912bc4f7db79bfc058d
comment:34 Changed 16 months ago by
 Status changed from needs_work to needs_review
comment:35 Changed 16 months ago by
Do you need validation by an expert ? Otherwise, I can set to positive.
comment:36 Changed 14 months ago by
 Reviewers set to ghvarenyamBakshi
 Status changed from needs_review to positive_review
comment:37 followup: ↓ 40 Changed 14 months ago by
reviewer name should be your real full name, not your login
comment:38 Changed 14 months ago by
+1 to this, and I'm very happy this if finally going to get included in Sage! It's an extremely important contribution.
comment:39 Changed 14 months ago by
 Reviewers changed from ghvarenyamBakshi to Varenyam bakshi
comment:40 in reply to: ↑ 37 Changed 14 months ago by
Replying to chapoton:
reviewer name should be your real full name, not your login
yeah i forgot. thanks for reminding.
comment:41 Changed 14 months ago by
 Milestone changed from sage8.4 to sage9.1
comment:42 Changed 14 months ago by
 Branch changed from public/21046_new to 1a1a8ef6767c837428d04912bc4f7db79bfc058d
 Resolution set to fixed
 Status changed from positive_review to closed
comment:43 Changed 10 months ago by
 Commit 1a1a8ef6767c837428d04912bc4f7db79bfc058d deleted
 Reviewers changed from Varenyam bakshi to Varenyam Bakshi
I have started reading the code, as a first step to reviewing this. As I read I will note here some trivial things so they do not get lost.
X_0
optimal curve should be1
if the curve lies outside the Cremona tables" you could add that with the range of the tables this is proved! (That is perhaps implicit anyway, but not explicit.)Someone who knows cython should look at the code too (robertb?)
It seems a pity to me that you need a new class for your cusps rather than adding to the existing class.
In one place you mention that I do not always guarantee the optimal curve, which is correct (though I always guarantee c=1, if necessary by computing the full modular symbol not just the plus symbol). See https://raw.githubusercontent.com/JohnCremona/ecdata/master/doc/manin.txt I am not sure what is going on where you multiply t0 by 2 "just in case".
In one place you divide D by the maximal power of a prime l. You could there use
The underlying summations to give the numerical values are of course also implemented in eclib (to arbitrary precision there too). One day it would be possible to add the relevant functions to the eclib interface and use that (compiled C, possibly fater than cython).
In the function where it says that setup_twist needs to be called first, should there be a flag to indicate that that has been done (and calls the setup here if not set)? Safer?
That's all for now. I did read through all the code, but not that thoroughly, and have not started to build or test!