Numerical modular symbols for elliptic curves

chriswuthrich commented 8 years ago

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 p-adic L-functions.

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.

CC: @JohnCremona @mmasdeu @williamstein @pjbruin

Component: elliptic curves

Keywords: modular symbols

Author: Chris Wuthrich

Branch: 1a1a8ef

Reviewer: Varenyam Bakshi

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

chriswuthrich commented 8 years ago

Branch: u/wuthrich/ticket/21046

chriswuthrich commented 8 years ago

Commit: 63c6606

chriswuthrich commented 8 years ago

Description changed:

--- 
+++ 
@@ -6,4 +6,4 @@

 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.

-A link to the preprint explaining all this will be added here.
+The preprint explaining all is [here](https://www.maths.nottingham.ac.uk/personal/cw/download/modsym.pdf).

JohnCremona commented 7 years ago

comment:5

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.

good documentation of the underlying mathematics!
in one place you talk about making the precision "small" where there is a default prec=53, so haps that should be "large".
"eclib" is "ec lib" in one place at least.
After "The Manin constant for the X_0-optimal curve should be 1 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.)
- 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?

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

sage: N=10^10 sage: N.prime_to_m_part(5) 1024

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!

JohnCremona commented 7 years ago

comment:6

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.

chriswuthrich commented 7 years ago

comment:7

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 @JohnCremona:

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 be 1 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 base-point 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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 63c6606 to 4de004a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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`

chriswuthrich commented 7 years ago

Changed dependencies from #20864 to #20864 #10256 (and so the linked eclib version at #22077)

fchapoton commented 7 years ago

comment:10

use py3 syntax for raise:

++           raise ValueError, "ECModularSymbol can only be created with signs +1 or 0, not {}".format(sign)
+Old-style raise statement inserted on 1 non-empty lines

chriswuthrich commented 7 years ago

comment:11

That slipped in at #10256. I will correct it here. But I wait to see if there is more to do.

fchapoton commented 7 years ago

Changed commit from 4de004a to 0dfe075

fchapoton commented 7 years ago

Changed branch from u/wuthrich/ticket/21046 to public/21046

fchapoton commented 7 years ago

Changed dependencies from #20864 #10256 (and so the linked eclib version at #22077) to none

fchapoton commented 7 years ago

comment:12

I just made it build again.

New commits:

`c495f75`	`Merge branch 'u/wuthrich/ticket/21046' in 8.1.b3`
`0dfe075`	`trac 21046 no more pxi`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

edf6e6d convert EXAMPLE:: to EXAMPLES::

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 0dfe075 to edf6e6d

chriswuthrich commented 7 years ago

comment:15

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....

fchapoton commented 6 years ago

comment:16

does not apply

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from edf6e6d to 81ec210

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

81ec210 Merge branch 'develop' at 8.2.rc4 into modsymnum

chriswuthrich commented 6 years ago

comment:18

Interest in this seems low, but I did the merge and it would be ready for review again.

d5d55a88-10b9-4e7b-aa54-b27720080ca8 commented 6 years ago

comment:19

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 4-4 Traceback (most recent call last): File "/usr/local/lib/python2.7/dist-packages/smc_sagews/sage_server.py", line 995, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in 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/d8842e1c-6d95-4e6d-b45d-ef46e7303532/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/padics.py", line 214, in padic_lseries normalize = normalize, implementation = implementation) File "/projects/d8842e1c-6d95-4e6d-b45d-ef46e7303532/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/padic_lseries.py", line 201, in __init__ crla = E.label() File "/projects/d8842e1c-6d95-4e6d-b45d-ef46e7303532/sage/local/lib/python2.7/site-packages/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/d8842e1c-6d95-4e6d-b45d-ef46e7303532/sage/local/lib/python2.7/site-packages/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 + xy + y = x^3 - x^2 - 1391*x - 25849 over Rational Field

chriswuthrich commented 6 years ago

comment:20

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`5522cf4`	`Merge branch sage 8.2 into modsymnum`
`00a8630`	`a different catch for cremona labels`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from 81ec210 to 00a8630

chriswuthrich commented 6 years ago

comment:22

fixed. The result, by the way, is L.series(3) = 2 + 2*5 + 3*5^2 + 5^3 + 4*5^4 + O(5^5) + (3 + 3*5 + O(5^2))*T + (3 + 5 + O(52))*T2 + (1 + O(52))*T3 + (2 + 3*5 + O(52))*T4 + O(T^5)

New commits:

`5522cf4`	`Merge branch sage 8.2 into modsymnum`
`00a8630`	`a different catch for cremona labels`

fchapoton commented 6 years ago

comment:23

branch does not apply

chriswuthrich commented 6 years ago

comment:25

I am afraid, I won't update this until someone makes a sign that they are interested in reviewing the ticket.

videlec commented 6 years ago

comment:26

update milestone 8.3 -> 8.4

chriswuthrich commented 4 years ago

Changed branch from public/21046 to public/21046_new

chriswuthrich commented 4 years ago

comment:27

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.

chriswuthrich commented 4 years ago

Changed commit from 00a8630 to 77e0af8

chriswuthrich commented 4 years ago

comment:28

At the very least I have to move the references.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

5f79bbb small edits, move biblio

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 77e0af8 to 5f79bbb

fchapoton commented 4 years ago

comment:30

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 use Return in the first-line descriptions)

chriswuthrich commented 4 years ago

comment:31

Thanks, Frédéric. Precisely what I wondered about. I will fix that soon.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 5f79bbb to ffe5df0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

ffe5df0 spacing and wording

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`d6e1436`	`Merge branch sage 9.0.beta9 into mod_num`
`1a1a8ef`	`delete some spaces`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from ffe5df0 to 1a1a8ef

fchapoton commented 4 years ago

comment:35

Do you need validation by an expert ? Otherwise, I can set to positive.

252a9631-90fd-4d3d-aafa-1c9c0f216f59 commented 4 years ago

Reviewer: gh-varenyamBakshi

fchapoton commented 4 years ago

comment:37

reviewer name should be your real full name, not your login

williamstein commented 4 years ago

comment:38

+1 to this, and I'm very happy this if finally going to get included in Sage! It's an extremely important contribution.

252a9631-90fd-4d3d-aafa-1c9c0f216f59 commented 4 years ago

Changed reviewer from gh-varenyamBakshi to Varenyam bakshi

252a9631-90fd-4d3d-aafa-1c9c0f216f59 commented 4 years ago

comment:40

Replying to @fchapoton:

reviewer name should be your real full name, not your login

yeah i forgot. thanks for reminding.

vbraun commented 4 years ago

Changed branch from public/21046_new to 1a1a8ef

mkoeppe commented 4 years ago

Changed reviewer from Varenyam bakshi to Varenyam Bakshi

sagemath / sage

Numerical modular symbols for elliptic curves #21046