Sage: Ticket #8829: Saturation for MW-groups of elliptic curves over number fields.
https://trac.sagemath.org/ticket/8829
<p>
Implementation of saturation of points on elliptic curves over number fields. Original patch by Robert Bradshaw in 2010, refactored and made into a git branch by John Cremona in 2015.
</p>
<p>
I also implemented the simple case of E.gens() for E(K) when E/Q and [K:Q] = 2.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8829
Trac 1.1.6robertwbFri, 30 Apr 2010 06:50:28 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:1
https://trac.sagemath.org/ticket/8829#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Some dependance on <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a>.
</p>
TicketcremonaFri, 30 Apr 2010 08:29:35 GMT
https://trac.sagemath.org/ticket/8829#comment:2
https://trac.sagemath.org/ticket/8829#comment:2
<p>
I have had a quick look and will go through this in more detail later (after <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a> is completed, probably). I spent a long time on my C++ implementation of this (over QQ but the algorithm is general) so am quite familiar with the details.
</p>
<p>
Here are two references you should give: [1] S. Siksek "Infinite descent on elliptic curves", Rocky Mountain J of M, Vol 25 No. 4 (1995), 1501-1538. [2] M. Prickett, "Saturation of Mordell-Weil groups of elliptic curves over number fields", U of Nottingham PhD thesis (2004), <a class="ext-link" href="http://etheses.nottingham.ac.uk/52/"><span class="icon"></span>http://etheses.nottingham.ac.uk/52/</a>.
</p>
<p>
Martin Prickett implemented this in Magma, but the code was very slow and hard to read so it never got incorporated into Magma releases.
</p>
<p>
Incidentally, it was for this that I implemented group structure for curves over GF(q) in the first place! In my C++ implementation I cache a lot of the information of this group structure so that when you do p-saturation for larger and larger p, the structures are already there. A good example is to take one of those curves of very high rank: I think I once successfully p-saturated the rank 24 curve at all p < <code>10^6</code> (the bound was totally out of reach, something like <code>10^100</code>).
</p>
<p>
Another point which might be useful over number fields: it suffices to use degree one primes to reduce modulo.
</p>
TicketrobertwbFri, 30 Apr 2010 08:39:16 GMTattachment set
https://trac.sagemath.org/ticket/8829
https://trac.sagemath.org/ticket/8829
<ul>
<li><strong>attachment</strong>
set to <em>8829-ec-nf-sat.patch</em>
</li>
</ul>
TicketrobertwbFri, 30 Apr 2010 08:46:39 GMT
https://trac.sagemath.org/ticket/8829#comment:3
https://trac.sagemath.org/ticket/8829#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8829#comment:2" title="Comment 2">cremona</a>:
</p>
<blockquote class="citation">
<p>
I have had a quick look and will go through this in more detail later (after <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a> is completed, probably). I spent a long time on my C++ implementation of this (over QQ but the algorithm is general) so am quite familiar with the details.
</p>
<p>
Here are two references you should give: [1] S. Siksek "Infinite descent on elliptic curves", Rocky Mountain J of M, Vol 25 No. 4 (1995), 1501-1538. [2] M. Prickett, "Saturation of Mordell-Weil groups of elliptic curves over number fields", U of Nottingham PhD thesis (2004), <a class="ext-link" href="http://etheses.nottingham.ac.uk/52/"><span class="icon"></span>http://etheses.nottingham.ac.uk/52/</a>.
</p>
</blockquote>
<p>
Ah, those look like good references to read too :).
</p>
<blockquote class="citation">
<p>
Martin Prickett implemented this in Magma, but the code was very slow and hard to read so it never got incorporated into Magma releases.
</p>
<p>
Incidentally, it was for this that I implemented group structure for curves over GF(q) in the first place! In my C++ implementation I cache a lot of the information of this group structure so that when you do p-saturation for larger and larger p, the structures are already there.
</p>
</blockquote>
<p>
The way I do it is consider many p at once, and for each curve over GF(q) I see which primes in my set it could help with, though this won't scale as far. I'm sure there's still lots of room for improvement.
</p>
<blockquote class="citation">
<p>
A good example is to take one of those curves of very high rank: I think I once successfully p-saturated the rank 24 curve at all p < <code>10^6</code> (the bound was totally out of reach, something like <code>10^100</code>).
</p>
</blockquote>
<p>
That reminds me--I was wondering if there's any way to go from min(h(P)) to a bound on the regulator for rank > 1.
</p>
<blockquote class="citation">
<p>
Another point which might be useful over number fields: it suffices to use degree one primes to reduce modulo.
</p>
</blockquote>
<p>
Good point. Those get pretty rare for large degree number fields though, right?
</p>
TicketcremonaFri, 30 Apr 2010 11:41:49 GMT
https://trac.sagemath.org/ticket/8829#comment:4
https://trac.sagemath.org/ticket/8829#comment:4
<p>
You might also like to look at my C++ code which is in eclib, in src/qcurves. I can point to the right files if it is not clear. In case you wonder, "TLSS" stands for "Tate-Lichtenbaum-Samir_Siksek" since I use the TL map when the p-torsion in E(GF(q)) is not cyclic and Samir's original method when it is. Samir only used reduction modulo primes where p exactly divided the order, and in particular for which the reduction had cyclic p-part. But Martin and I discovered that this can fail when there is a p-isogeny. Here, fail means in the sense that there can exist points which are not multiples of p in E(QQ) but which map to zero in E(GF(q))/p for all q.
</p>
<p>
In MP's thesis he proves that this cannot happen if you use all q, or all but a finite number, or all but a finite number of degree 1 primes, .... some of these results we then found had been proved elsewhere (3 or 4 times, independently, within 3 or 4 years!). But it can happen if you leave out the q for which the quotient has non-cyclic p-part.
</p>
TicketcremonaSun, 09 May 2010 17:49:06 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/8829#comment:5
https://trac.sagemath.org/ticket/8829#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>John Cremona</em>
</li>
<li><strong>author</strong>
set to <em>Robert Bradshaw</em>
</li>
</ul>
<p>
Patch applies fine to 4.4.1 and tests pass.
</p>
<p>
This functionality is badly needed!
</p>
<p>
We now have heights for points on curves defined over number_fields
but no associated regulator function. I suggest that the function
regulator_of_points() be moved up from ell_rational_field to
ell_number_field. This tcan then be called instead of the code in
lines 424-432 [line numbers are from the patched file, not the patch].
</p>
<p>
Line 439 uses a function self.height_function() which does not exist.
This block needs to be replaced by something sensible. If one has a lower bound on the height of non-torsion
points, then a bound on the index can be deduced from standard
geometry of numbers estimates. To get such a lower bound, see papers
of Cremona & Siksek (over Q) and Thongjunthug (over number fields) for
an algorithm which would need to be implemented. (Not hard over Q,
not much harder for totally real fields, quite a lot worse over fields
with a complex embedding). Until this is done, I don't think this
saturation function can allow maxprime==0.
</p>
<p>
In the rank one code: when large primes p (say, over 20!) are being
tested then the division_points code will be expensive since it
involves constructing the multiplication-by-p map. I would recommend
using a reduction strategy here just as in the general case. To check
p-saturation just find primes q such that #E(Fq) is divisible by p and
then see if the reduction of P mod q is a multiple of p. This will
almost always prove saturation very quickly. If it fails for several
(say 5) q then try to divide P by p; else use more q, and so on.
There is one theoretical drawback here: this strategy might fail if
there is a rational p-isogeny. Over Q, we know which p this might
happen for and I would first test for the existence of isogenies of
primes degree, and use the division test (as here) for any primes that
show up. Over number fields that's harder to deal with, but again we
can fall back on the division test to rpove that P cannot be divided
by p.
</p>
<p>
The function list_of_multiples(P,n) duplicated the generic function
multiples() which I wrote for just this sort of purpose!
</p>
<p>
I don't like the loop through all linear combinations for small
primes. Even with p=2 there are curves with 24 independent points out
there and <code>2^24</code> divisions is not nice to contemplate. If you want this
short cut, do it based on the size of <code>p^r</code>.
</p>
<p>
The main code with reduction etc looks fine to me (but I did not check
the logic rigorously).
</p>
<p>
The gens function for E(K) when E is defined over Q and [K:Q]=2 looks
fine. For a more general case we could always try using
simon_two_descent (followed by saturation). Trying such an examples
led me to:
</p>
<pre class="wiki">sage: K.<a> = NumberField(x^2-2)
sage: E = EllipticCurve([a,0])
sage: P = E(0,0)
sage: P.has_finite_order()
True
sage: P.order()
2
sage: P.height()
0
sage: E.saturation([P], verbose=True, max_prime=5)
## infinite loop
</pre><p>
This is caused as follows: The height matrix is [0] with det=0 but
reg / min(heights) is NaN so reg / min(heights) < 1e-6 is False!.
This will need fixing. At the very least, I would discard any points
of finite order before doing anything else with them. Then
min(heights) will never be 0.
</p>
<p>
Most of the above is easy to deal with. The hard part is computing a
suitable max_prime form a lower height bound on points. I suggest
that for now you make it compulsory to have a positive max_prime and
add a TODO.
</p>
TicketrobertwbTue, 11 May 2010 18:17:49 GMT
https://trac.sagemath.org/ticket/8829#comment:6
https://trac.sagemath.org/ticket/8829#comment:6
<p>
Thank you for all your input. <code>self.height_function</code> comes from <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a>, though as you suggest we could make max_prime mandatory for now (and for rank > 1 once that goes in). That's a good point about large primes in the rank one case. I found the loop through all linear combinations to be much faster in practice for small primes, but the hard coded <code>p == 2</code> case was left by accident, I meant to cap that on <code>p^r</code> as I did the others.
</p>
<p>
I probably won't fix and polish this up before finishing my thesis, but at the latest we should be able to get it done during the workshop at MSRI next month.
</p>
TicketcremonaTue, 11 May 2010 20:48:47 GMT
https://trac.sagemath.org/ticket/8829#comment:7
https://trac.sagemath.org/ticket/8829#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8829#comment:6" title="Comment 6">robertwb</a>:
</p>
<blockquote class="citation">
<p>
Thank you for all your input. <code>self.height_function</code> comes from <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a>, though as you suggest we could make max_prime mandatory for now (and for rank > 1 once that goes in). That's a good point about large primes in the rank one case. I found the loop through all linear combinations to be much faster in practice for small primes, but the hard coded <code>p == 2</code> case was left by accident, I meant to cap that on <code>p^r</code> as I did the others.
</p>
<p>
I probably won't fix and polish this up before finishing my thesis, but at the latest we should be able to get it done during the workshop at MSRI next month.
</p>
</blockquote>
<p>
OK -- looking forward to it! I'll take a look at <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a> by then as well.
</p>
TicketcremonaTue, 29 Jun 2010 04:54:59 GMT
https://trac.sagemath.org/ticket/8829#comment:8
https://trac.sagemath.org/ticket/8829#comment:8
<p>
Since rwb is now busy at Google, and I want this functionality, I am now implementing the changes I suggested above!
</p>
TicketcremonaTue, 29 Jun 2010 04:59:02 GMT
https://trac.sagemath.org/ticket/8829#comment:9
https://trac.sagemath.org/ticket/8829#comment:9
<p>
I made a separate ticket for the regulator functions. See <a class="closed ticket" href="https://trac.sagemath.org/ticket/9372" title="enhancement: implement regulator function for elliptic curves over number fields (closed: fixed)">#9372</a>.
</p>
TicketroedMon, 15 Oct 2012 09:36:35 GMT
https://trac.sagemath.org/ticket/8829#comment:10
https://trac.sagemath.org/ticket/8829#comment:10
<p>
How is this going John? It seems to have been awhile....
</p>
TicketcremonaTue, 08 Jan 2013 09:28:53 GMT
https://trac.sagemath.org/ticket/8829#comment:11
https://trac.sagemath.org/ticket/8829#comment:11
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/12509" title="defect: computation of height of point on elliptic curve over Q(sqrt(5)) is WRONG (closed: fixed)">#12509</a>: until we can fix the height computation, saturation cannot be carried out properly. It's still on my to-do list though.
</p>
TicketcremonaThu, 10 Jan 2013 09:30:38 GMT
https://trac.sagemath.org/ticket/8829#comment:12
https://trac.sagemath.org/ticket/8829#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8829#comment:11" title="Comment 11">cremona</a>:
</p>
<blockquote class="citation">
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/12509" title="defect: computation of height of point on elliptic curve over Q(sqrt(5)) is WRONG (closed: fixed)">#12509</a>: until we can fix the height computation, saturation cannot be carried out properly. It's still on my to-do list though.
</p>
</blockquote>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/12509" title="defect: computation of height of point on elliptic curve over Q(sqrt(5)) is WRONG (closed: fixed)">#12509</a> is now up for review.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/8829#comment:13
https://trac.sagemath.org/ticket/8829#comment:13
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketcremonaTue, 07 Jan 2014 14:48:27 GMTdependencies set
https://trac.sagemath.org/ticket/8829#comment:14
https://trac.sagemath.org/ticket/8829#comment:14
<ul>
<li><strong>dependencies</strong>
set to <em>#8828</em>
</li>
</ul>
TicketnbruinWed, 08 Jan 2014 15:28:11 GMTsummary changed
https://trac.sagemath.org/ticket/8829#comment:15
https://trac.sagemath.org/ticket/8829#comment:15
<ul>
<li><strong>summary</strong>
changed from <em>Saturation for curves over number fields.</em> to <em>Saturation for MW-groups of elliptic curves over number fields.</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/8829#comment:16
https://trac.sagemath.org/ticket/8829#comment:16
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketpbruinFri, 28 Feb 2014 13:54:07 GMTcc set
https://trac.sagemath.org/ticket/8829#comment:17
https://trac.sagemath.org/ticket/8829#comment:17
<ul>
<li><strong>cc</strong>
<em>pbruin</em> added
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/8829#comment:18
https://trac.sagemath.org/ticket/8829#comment:18
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/8829#comment:19
https://trac.sagemath.org/ticket/8829#comment:19
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketcremonaThu, 13 Aug 2015 16:05:47 GMT
https://trac.sagemath.org/ticket/8829#comment:20
https://trac.sagemath.org/ticket/8829#comment:20
<p>
I do not know why this was left drifting, but I really need it myself now so will look at it again, rebase on 6.8 and see what we can do. But I only have one day before a week off, so...
</p>
TicketcremonaFri, 11 Sep 2015 16:16:06 GMTdescription, author changed; keywords, commit, branch set
https://trac.sagemath.org/ticket/8829#comment:21
https://trac.sagemath.org/ticket/8829#comment:21
<ul>
<li><strong>keywords</strong>
<em>saturation</em> added
</li>
<li><strong>commit</strong>
set to <em>0e1e35f624edb087d3fb1ddc21226fec7acfafad</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8829?action=diff&version=21">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>u/cremona/8829</em>
</li>
<li><strong>author</strong>
changed from <em>Robert Bradshaw</em> to <em>Robert Bradshaw, John Cremona</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=be41e01ce73b35489e0deb11e13740a9a5b2944e"><span class="icon"></span>be41e01</a></td><td><code>first work on updating #9929 to a working branch (not done yet)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4b4fc2157b2e514d27a3458a86dcfff2620df967"><span class="icon"></span>4b4fc21</a></td><td><code>#8829: ell_height now passes its doctests...</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0e1e35f624edb087d3fb1ddc21226fec7acfafad"><span class="icon"></span>0e1e35f</a></td><td><code>#8829: refactored saturation; ell_number_field passes its doctests but more testing and tests needed...</code>
</td></tr></table>
TicketcremonaFri, 11 Sep 2015 16:18:50 GMT
https://trac.sagemath.org/ticket/8829#comment:22
https://trac.sagemath.org/ticket/8829#comment:22
<p>
Current branch works but more doctests and testing are needed; so not ready for review yet.
</p>
<p>
I did a lot of rewriting of the main saturation routine, separating off p-saturation and also allowing saturation to be done at just one prime. This is a useful special case, since if you take the images of some saturated points under a p-isogeny the images may not be p-saturated but will still be saturated at all other primes.
</p>
<p>
The code for computing E(K) when K is quadratic and E is a base change has been completely rewritten and will now work in many more cases (not just when the coefficients of E are in Q).
</p>
TicketgitMon, 14 Sep 2015 16:09:59 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:23
https://trac.sagemath.org/ticket/8829#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>0e1e35f624edb087d3fb1ddc21226fec7acfafad</em> to <em>a85f40629df89da829e3a38d9e0443576bced01d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a85f40629df89da829e3a38d9e0443576bced01d"><span class="icon"></span>a85f406</a></td><td><code>#8829: finished doctests for ec/nf saturation</code>
</td></tr></table>
TicketcremonaMon, 14 Sep 2015 16:16:53 GMT
https://trac.sagemath.org/ticket/8829#comment:24
https://trac.sagemath.org/ticket/8829#comment:24
<p>
The latest commit involves more than adding more doctests to the new functions, since bugs were revealed which led to a rewrite of the sieving code for the two cases where the p-rank of the reduction is 1 or 2; the former uses discrete log in the reduction, the latter uses Weil pairing and discrte log in the multiplicative group. In the sieve I restrict to primes of degree 1. It is a Theorem (see <a class="ext-link" href="http://eprints.nottingham.ac.uk/10052/"><span class="icon"></span>http://eprints.nottingham.ac.uk/10052/</a>) that this will suffice to prove p-saturation, provided that one does use reductions with p-rank 2 and not just those of p-rank 1 as originally suggested by Siksek in <a class="ext-link" href="https://ore.exeter.ac.uk/repository/handle/10871/8323"><span class="icon"></span>https://ore.exeter.ac.uk/repository/handle/10871/8323</a> .
</p>
<p>
I will mark this as ready for review so the bots get to work on it, and of course humans are welcome to look at the new code, but I will now test it thoroughly on the LMFDB curves and report back.
</p>
TicketcremonaMon, 14 Sep 2015 16:17:16 GMTstatus changed; reviewer deleted
https://trac.sagemath.org/ticket/8829#comment:25
https://trac.sagemath.org/ticket/8829#comment:25
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
<em>John Cremona</em> deleted
</li>
</ul>
TicketchapotonMon, 14 Sep 2015 17:52:14 GMT
https://trac.sagemath.org/ticket/8829#comment:26
https://trac.sagemath.org/ticket/8829#comment:26
<p>
Hello,
</p>
<p>
1) indent correctly the INPUT and OUTPUT fields:
</p>
<pre class="wiki">INPUT:
- first thing
goes one there (note the shift of 2 characters)
</pre><p>
2) use the new syntax for raise:
</p>
<pre class="wiki">raise MyError("is rich")
</pre><p>
Point 1 may be the source of the doc build failure found by the bot:
</p>
<p>
OSError: [plane_cur] /home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py:docstring of sage.schemes.elliptic_curves.ell_number_field.EllipticCurve_number_field.saturation:9: WARNING: Bullet list ends without a blank line; unexpected unindent.
</p>
TicketcremonaMon, 14 Sep 2015 18:34:30 GMT
https://trac.sagemath.org/ticket/8829#comment:27
https://trac.sagemath.org/ticket/8829#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8829#comment:26" title="Comment 26">chapoton</a>:
</p>
<blockquote class="citation">
<p>
Hello,
</p>
<p>
1) indent correctly the INPUT and OUTPUT fields:
</p>
<pre class="wiki">INPUT:
- first thing
goes one there (note the shift of 2 characters)
</pre><p>
2) use the new syntax for raise:
</p>
<pre class="wiki">raise MyError("is rich")
</pre><p>
Point 1 may be the source of the doc build failure found by the bot:
</p>
<p>
OSError: [plane_cur] /home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py:docstring of sage.schemes.elliptic_curves.ell_number_field.EllipticCurve_number_field.saturation:9: WARNING: Bullet list ends without a blank line; unexpected unindent.
</p>
</blockquote>
<p>
Thanks, I will fix those.
</p>
TicketgitMon, 14 Sep 2015 19:01:14 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:28
https://trac.sagemath.org/ticket/8829#comment:28
<ul>
<li><strong>commit</strong>
changed from <em>a85f40629df89da829e3a38d9e0443576bced01d</em> to <em>4f511b89fd199d070bad0d1054efa148d765fdf6</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4f511b89fd199d070bad0d1054efa148d765fdf6"><span class="icon"></span>4f511b8</a></td><td><code>fixup doc errors and raise() syntax</code>
</td></tr></table>
TicketchapotonTue, 15 Sep 2015 09:57:24 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:29
https://trac.sagemath.org/ticket/8829#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
many failing doctests, see bot report
</p>
TicketcremonaTue, 15 Sep 2015 10:33:37 GMT
https://trac.sagemath.org/ticket/8829#comment:30
https://trac.sagemath.org/ticket/8829#comment:30
<p>
Apologies, it was a mistake to set this to needs_review prematurely. Next time I do, I will mean it.
</p>
TicketgitTue, 15 Sep 2015 11:09:14 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:31
https://trac.sagemath.org/ticket/8829#comment:31
<ul>
<li><strong>commit</strong>
changed from <em>4f511b89fd199d070bad0d1054efa148d765fdf6</em> to <em>2f20f7373a13e2267bc5ae3d2a7cae93278a76c4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1647ce23fc11efbeb62cb64e1d6f8fe0984d47e3"><span class="icon"></span>1647ce2</a></td><td><code>#8829: rewrote projections() so dlogs computed in smaller subgroups</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2f20f7373a13e2267bc5ae3d2a7cae93278a76c4"><span class="icon"></span>2f20f73</a></td><td><code>Merge branch 'develop' (6.9.beta6) into saturate</code>
</td></tr></table>
TicketcremonaWed, 16 Sep 2015 11:38:42 GMT
https://trac.sagemath.org/ticket/8829#comment:32
https://trac.sagemath.org/ticket/8829#comment:32
<p>
Progress report: I am currently running the p-saturation (for single primes) on lots of LMFDB curves and all is well so far. This is almost always for very small p (mainly 2 and 3) though, since I am starting with some saturated points on one curve (provided by Magma) and using p-isogenies to map to other curves in the isogeny class. Higher degree isogenies are not so common.
</p>
<p>
I did start to veryify that the points from Magma were fully saturated, but ran into problems computing the saturation index, using (line 3717) the lower bound on the height of all non-torsion points -- previously implemented and merged i n6.3 (see <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a>). For example, I had a curve where the value of 5 in that line was insufficient *and led to an infinite loop in the call to min()*, while 10 worked fine, but now I have a curve where I have not yet found a value which gives anything. For the record I will give that example here:
</p>
<pre class="wiki">K.<phi> = NumberField(x^2-x-1) # Q(sqrt(5))
E = EllipticCurve([phi + 1, -phi + 1, 1, 20*phi - 39, 196*phi + 237])
H = E.height_function()
H.min(.1,10,verbose=True) # does not appear to terminate
</pre><p>
Strictly this is about the code merged in <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a>, but it will need fixing here before we can let this (useful!) function out into the world.
</p>
TicketgitThu, 17 Sep 2015 13:55:22 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:33
https://trac.sagemath.org/ticket/8829#comment:33
<ul>
<li><strong>commit</strong>
changed from <em>2f20f7373a13e2267bc5ae3d2a7cae93278a76c4</em> to <em>8686677fa5cdf4359fd6f6b8d8e25925f6893a4c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7dbb186ac35a7b1ac71040d404717d36406c5a0d"><span class="icon"></span>7dbb186</a></td><td><code>Merge branch 'develop' of trac.sagemath.org:sage into isogs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c66d49f8c804718e083f042dcb8af46db9174f6b"><span class="icon"></span>c66d49f</a></td><td><code>Merge branch 'develop' of trac.sagemath.org:sage into isogs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ce2472b51bc712f4568eccd9abef26cef3f400da"><span class="icon"></span>ce2472b</a></td><td><code>Merge branch 'isogs' into sat+isogs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8c80b6fc455a9c512a07f0e4686f38d5b5ba71aa"><span class="icon"></span>8c80b6f</a></td><td><code>Merge branch 'saturate' into sat+isogs</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8686677fa5cdf4359fd6f6b8d8e25925f6893a4c"><span class="icon"></span>8686677</a></td><td><code>8829: two bug fixes, more tests</code>
</td></tr></table>
TicketcremonaThu, 17 Sep 2015 14:06:04 GMT
https://trac.sagemath.org/ticket/8829#comment:34
https://trac.sagemath.org/ticket/8829#comment:34
<p>
The latest branch I just pushed has some merges in it which were not intended but I hope that will not cause any problems -- as well as merging 6.9.beta6 I also merged by branch 'isogs' which has been merged into beta7.
</p>
<p>
One bug fix addresses the previous comment -- after re-reading my own 2006 paper I found that the original implementer from <a class="closed ticket" href="https://trac.sagemath.org/ticket/8828" title="enhancement: Lower height bound for elliptic curves (closed: fixed)">#8828</a> had missed one point (when mu is halved one must increment n_max in order to guarantee termination). A small additional improvement in the same place (the method min_gr() in height.py) now gives a small improvement in the bound, which is why one doctest there has been changed.
</p>
<p>
The second bug was to do with mutability of lists giving unwanted side effects, and is commented at the point in the source which has changed.
</p>
<p>
It is likely that users who call the saturation() method will also want to lll_reduce() the output but I have not made that automatic.
</p>
<p>
I will set this to needs_review once my own full test has completed.
</p>
TicketcremonaThu, 17 Sep 2015 14:13:55 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:35
https://trac.sagemath.org/ticket/8829#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketcremonaSat, 19 Sep 2015 09:00:54 GMTstatus, description changed
https://trac.sagemath.org/ticket/8829#comment:36
https://trac.sagemath.org/ticket/8829#comment:36
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8829?action=diff&version=36">diff</a>)
</li>
</ul>
<p>
After further testing (on many thousands of curves but only p-saturating for small p) I saw that it was bad to use discrete_log_lambda() for the dlog in the multiplcative group (in the rarer case where the p-rank of the reduction is 2 and the Weil pairing is used), both unnecessary and less efficient than simply w.log(zeta).
One additional commit coming up...
</p>
TicketgitSat, 19 Sep 2015 10:35:24 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:37
https://trac.sagemath.org/ticket/8829#comment:37
<ul>
<li><strong>commit</strong>
changed from <em>8686677fa5cdf4359fd6f6b8d8e25925f6893a4c</em> to <em>99158817c3895207ebae8f3dc06e83f0b7c6a1cb</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=99158817c3895207ebae8f3dc06e83f0b7c6a1cb"><span class="icon"></span>9915881</a></td><td><code>changed multiplicative dlog to not use discrte_log_lambda</code>
</td></tr></table>
TicketcremonaSat, 19 Sep 2015 10:37:31 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:38
https://trac.sagemath.org/ticket/8829#comment:38
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketcremonaFri, 25 Sep 2015 17:09:18 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:39
https://trac.sagemath.org/ticket/8829#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There's some bug in the Weil pairing section which I don't have time to fix now, and this has missed 6.9 anyway.
</p>
TicketcremonaThu, 10 Dec 2015 16:43:54 GMT
https://trac.sagemath.org/ticket/8829#comment:40
https://trac.sagemath.org/ticket/8829#comment:40
<p>
I did do more work on that but did not get to the bottom of it. Just keeping the ticket alive!
</p>
TicketgitMon, 28 Dec 2015 13:53:25 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:41
https://trac.sagemath.org/ticket/8829#comment:41
<ul>
<li><strong>commit</strong>
changed from <em>99158817c3895207ebae8f3dc06e83f0b7c6a1cb</em> to <em>f3eb76aaffcd66e55aa48a0ca3fce51f1a4d3a19</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e481c40e132acee0fe35d8a6ebcacfc9ddd4f893"><span class="icon"></span>e481c40</a></td><td><code>first work on updating #9929 to a working branch (not done yet)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=00b6ac6ea2d4d516add0c751494a326d0fae26c8"><span class="icon"></span>00b6ac6</a></td><td><code>#8829: ell_height now passes its doctests...</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8c44155ad2e84a7d1901e13166faa0681722537e"><span class="icon"></span>8c44155</a></td><td><code>#8829: refactored saturation; ell_number_field passes its doctests but more testing and tests needed...</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a64e3c93f4ad7f305a5c4d8de538909a0acad5d1"><span class="icon"></span>a64e3c9</a></td><td><code>#8829: finished doctests for ec/nf saturation</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=573d4b7124ccc199975ab4244621796755ed8082"><span class="icon"></span>573d4b7</a></td><td><code>fixup doc errors and raise() syntax</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7b2f1de2e720172e7abb6a1e0d82ddb14d2b00d0"><span class="icon"></span>7b2f1de</a></td><td><code>#8829: rewrote projections() so dlogs computed in smaller subgroups</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f3eb76aaffcd66e55aa48a0ca3fce51f1a4d3a19"><span class="icon"></span>f3eb76a</a></td><td><code>added check to catch Weil pairing errors during saturation</code>
</td></tr></table>
TicketgitMon, 04 Jan 2016 15:25:50 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:42
https://trac.sagemath.org/ticket/8829#comment:42
<ul>
<li><strong>commit</strong>
changed from <em>f3eb76aaffcd66e55aa48a0ca3fce51f1a4d3a19</em> to <em>a135224f6a7b28c913b4fbe77ade7ed1d15094c3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e986230ada9dee6162e88183d23efea87ff3880f"><span class="icon"></span>e986230</a></td><td><code>8829: two bug fixes, more tests</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a135224f6a7b28c913b4fbe77ade7ed1d15094c3"><span class="icon"></span>a135224</a></td><td><code>changed multiplicative dlog to not use discrete_log_lambda</code>
</td></tr></table>
TicketcremonaWed, 17 Feb 2016 13:20:31 GMT
https://trac.sagemath.org/ticket/8829#comment:43
https://trac.sagemath.org/ticket/8829#comment:43
<p>
Merging with 7.1.beta3....
</p>
TicketgitWed, 17 Feb 2016 16:49:24 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:44
https://trac.sagemath.org/ticket/8829#comment:44
<ul>
<li><strong>commit</strong>
changed from <em>a135224f6a7b28c913b4fbe77ade7ed1d15094c3</em> to <em>70bb203a14669ff411b2035e33112462c7053707</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=70bb203a14669ff411b2035e33112462c7053707"><span class="icon"></span>70bb203</a></td><td><code>fix merge conflicts in ell_number_field</code>
</td></tr></table>
TicketchapotonSun, 20 Nov 2016 08:23:25 GMTcommit, branch changed
https://trac.sagemath.org/ticket/8829#comment:45
https://trac.sagemath.org/ticket/8829#comment:45
<ul>
<li><strong>commit</strong>
changed from <em>70bb203a14669ff411b2035e33112462c7053707</em> to <em>4a7bdc29883e72ceb8e65a8608c6ea3deef4b5fd</em>
</li>
<li><strong>branch</strong>
changed from <em>u/cremona/8829</em> to <em>public/8829</em>
</li>
</ul>
<p>
just rebased on 7.5.b3
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=4a7bdc29883e72ceb8e65a8608c6ea3deef4b5fd"><span class="icon"></span>4a7bdc2</a></td><td><code>Merge branch 'u/cremona/8829' in 7.5.b3</code>
</td></tr></table>
TicketgitSun, 11 Dec 2016 11:36:34 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:46
https://trac.sagemath.org/ticket/8829#comment:46
<ul>
<li><strong>commit</strong>
changed from <em>4a7bdc29883e72ceb8e65a8608c6ea3deef4b5fd</em> to <em>9d66f355dfcba972495f8a459928aeb9488a4baa</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=47b7d2b5b90e34f2707c5db98a84f6982e8bfe2f"><span class="icon"></span>47b7d2b</a></td><td><code>Merge branch 'public/8829' in 7.5.b6</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=9d66f355dfcba972495f8a459928aeb9488a4baa"><span class="icon"></span>9d66f35</a></td><td><code>trac 8829 fix for py3</code>
</td></tr></table>
TicketgitSun, 06 Aug 2017 15:58:17 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:47
https://trac.sagemath.org/ticket/8829#comment:47
<ul>
<li><strong>commit</strong>
changed from <em>9d66f355dfcba972495f8a459928aeb9488a4baa</em> to <em>a2f50232fc1289a9beec3a488a1cec9907f25f59</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=a2f50232fc1289a9beec3a488a1cec9907f25f59"><span class="icon"></span>a2f5023</a></td><td><code>Merge branch 'develop' into 8829</code>
</td></tr></table>
TicketcremonaSun, 06 Aug 2017 15:59:08 GMT
https://trac.sagemath.org/ticket/8829#comment:48
https://trac.sagemath.org/ticket/8829#comment:48
<p>
I just merged 8,0 into the branch prior to looking at it again.
</p>
TicketgitSun, 06 Aug 2017 20:05:33 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:49
https://trac.sagemath.org/ticket/8829#comment:49
<ul>
<li><strong>commit</strong>
changed from <em>a2f50232fc1289a9beec3a488a1cec9907f25f59</em> to <em>5b40a83c70bee0fc21e1057c2b50475fca5f8a5b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=5b40a83c70bee0fc21e1057c2b50475fca5f8a5b"><span class="icon"></span>5b40a83</a></td><td><code>#8829: move p-saturation code to a new file and fix tests and imports</code>
</td></tr></table>
TicketcremonaSun, 06 Aug 2017 20:08:19 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:50
https://trac.sagemath.org/ticket/8829#comment:50
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
After merging into 8.0 I fixed some newly failing doctests (trivial things caused by the usual pari number field changes). I moved the two p-saturation functions to a new file saturation.py, and added that to the reference manual.
Ready for review. I intend to use this a lot soon over number fields of degree up to 6 for the LMFDB and it would be most helpful to have it merged into 8.1.
</p>
TicketchapotonSun, 06 Aug 2017 20:09:13 GMTmilestone changed; dependencies deleted
https://trac.sagemath.org/ticket/8829#comment:51
https://trac.sagemath.org/ticket/8829#comment:51
<ul>
<li><strong>dependencies</strong>
<em>#8828</em> deleted
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-8.1</em>
</li>
</ul>
TicketchapotonSun, 06 Aug 2017 20:13:14 GMT
https://trac.sagemath.org/ticket/8829#comment:52
https://trac.sagemath.org/ticket/8829#comment:52
<p>
Quick comments :
</p>
<ul><li>dot not use $ but backticks
</li></ul><ul><li>every function must be doctested
</li></ul>
TicketcremonaSun, 06 Aug 2017 20:16:38 GMT
https://trac.sagemath.org/ticket/8829#comment:53
https://trac.sagemath.org/ticket/8829#comment:53
<p>
!!! New docstrings use backticks, and new functions are doctested. !!! The file ell_number_field is 3800 lines long. Both the files I just worked on have 100% coverage.
</p>
TicketchapotonMon, 07 Aug 2017 06:16:25 GMT
https://trac.sagemath.org/ticket/8829#comment:54
https://trac.sagemath.org/ticket/8829#comment:54
<p>
Hello ! some dollars there :
</p>
<pre class="wiki">+ For rank 1 subgroups, simply do trial divison up to the maximal
+ prime divisor. For higher rank subgroups, perform trial divison
+ on all linear combinations for small primes, and look for
+ projections $E(K) \rightarrow \oplus E(k) \otimes \FF_p$ which
+ are either full rank or provide p-divisble linear combinations,
+ where the $k$ here are residue fields of $K$.
</pre><p>
and no doc for
</p>
<pre class="wiki">+ def projections(Q, p):
</pre><p>
which is indeed an inner function, but quite a complicated one. Maybe just explain its input and output ?
</p>
TicketcremonaMon, 07 Aug 2017 08:18:42 GMT
https://trac.sagemath.org/ticket/8829#comment:55
https://trac.sagemath.org/ticket/8829#comment:55
<p>
I stand corrected and will see to this.
</p>
TicketcremonaMon, 07 Aug 2017 08:39:49 GMT
https://trac.sagemath.org/ticket/8829#comment:56
https://trac.sagemath.org/ticket/8829#comment:56
<p>
For the inner function projections(Q, p) there is already a docstring:
</p>
<pre class="wiki"> Project points onto (E mod Q)(K mod Q) \otimes \F_p.
Returns a list of 0, 1 or 2 vectors in \F_p^n
</pre><p>
which explains what it does. I'll make sure that all the other inner functions are explained.
</p>
TicketgitMon, 07 Aug 2017 11:33:12 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:57
https://trac.sagemath.org/ticket/8829#comment:57
<ul>
<li><strong>commit</strong>
changed from <em>5b40a83c70bee0fc21e1057c2b50475fca5f8a5b</em> to <em>8c715855e54b1b1a12d82364a004f428c9a80097</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=8abe3dcf12c2e096cdc563cd5e071a8c35564501"><span class="icon"></span>8abe3dc</a></td><td><code>#8829 fix some docstrings and remove some internal functions</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=847d27665a592638b7767a2a88d1575e5f5544b1"><span class="icon"></span>847d276</a></td><td><code>#8829 fix a bug (typo n for p)</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=8c715855e54b1b1a12d82364a004f428c9a80097"><span class="icon"></span>8c71585</a></td><td><code>#8829: put back a one-line internal function</code>
</td></tr></table>
TicketcremonaMon, 07 Aug 2017 11:34:49 GMT
https://trac.sagemath.org/ticket/8829#comment:58
https://trac.sagemath.org/ticket/8829#comment:58
<p>
I hope the latest commits do what was wanted for docstrings. I did remove some rather unnecessary one-liner internal functions.
In the course of doing this I found at least 2 bugs ;) which is good because the reason this was not finished with 18 months ago was the existence of a bug.
</p>
<p>
Please review!
</p>
TicketchapotonMon, 07 Aug 2017 11:47:35 GMT
https://trac.sagemath.org/ticket/8829#comment:59
https://trac.sagemath.org/ticket/8829#comment:59
<p>
a typo here:
</p>
<pre class="wiki">trial divison
</pre><p>
and also a missing line break here after <code>r"""</code>:
</p>
<pre class="wiki">+ r""" Given a list of rational points on `E` over `K`, compute the
</pre><p>
same here:
</p>
<pre class="wiki"> """Return generators for the Mordell-Weil group modulo torsion, for a
</pre><p>
same there:
</p>
<pre class="wiki">+ r""" Checks whether the list of points is `p`-saturated.
</pre><p>
and
</p>
<pre class="wiki">+ r""" Full `p`-saturation of ``Plist``.
</pre><p>
another typo:
</p>
<pre class="wiki">divisble
</pre><p>
This :
</p>
<pre class="wiki">+ if len(EE)==0:
</pre><p>
can be replaced by <code>if not EE</code>
</p>
<p>
another typo:
</p>
<pre class="wiki">algirithm
</pre>
TicketgitMon, 07 Aug 2017 12:15:37 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:60
https://trac.sagemath.org/ticket/8829#comment:60
<ul>
<li><strong>commit</strong>
changed from <em>8c715855e54b1b1a12d82364a004f428c9a80097</em> to <em>7b3c1886b7dbd481f7248c2271233c73ca483c01</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=7b3c1886b7dbd481f7248c2271233c73ca483c01"><span class="icon"></span>7b3c188</a></td><td><code>#8829 fix docstring typos</code>
</td></tr></table>
TicketcremonaMon, 07 Aug 2017 12:16:13 GMT
https://trac.sagemath.org/ticket/8829#comment:61
https://trac.sagemath.org/ticket/8829#comment:61
<p>
I fixed those, and at least one more. Thanks
</p>
TicketchapotonMon, 07 Aug 2017 20:21:24 GMT
https://trac.sagemath.org/ticket/8829#comment:62
https://trac.sagemath.org/ticket/8829#comment:62
<p>
"trial divison" is still there
</p>
TicketgitTue, 08 Aug 2017 16:46:07 GMTcommit changed
https://trac.sagemath.org/ticket/8829#comment:63
https://trac.sagemath.org/ticket/8829#comment:63
<ul>
<li><strong>commit</strong>
changed from <em>7b3c1886b7dbd481f7248c2271233c73ca483c01</em> to <em>d2421238e6f1f174d90f8f81cbbc0606e79171b3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=d2421238e6f1f174d90f8f81cbbc0606e79171b3"><span class="icon"></span>d242123</a></td><td><code>#8829 correct spelling divison (*4)</code>
</td></tr></table>
TicketcremonaTue, 08 Aug 2017 16:47:06 GMT
https://trac.sagemath.org/ticket/8829#comment:64
https://trac.sagemath.org/ticket/8829#comment:64
<p>
Not now it isn't. I also used "grep -r" to catch 3 more (not mine).
</p>
<p>
One day I might get a review of the <span class="underline">code</span>!
</p>
TicketkedlayaTue, 22 Aug 2017 21:48:44 GMTcc changed
https://trac.sagemath.org/ticket/8829#comment:65
https://trac.sagemath.org/ticket/8829#comment:65
<ul>
<li><strong>cc</strong>
<em>kedlaya</em> added
</li>
</ul>
TicketroedTue, 22 Aug 2017 22:23:30 GMT
https://trac.sagemath.org/ticket/8829#comment:66
https://trac.sagemath.org/ticket/8829#comment:66
<p>
Some comments on code:
</p>
<ul><li>There's something weird with the indentation at <code>for Q in K.primes_above(q, degree=1):</code> in <code>p_saturation</code> (it looks only indented one space).
</li><li>There are various points where you don't have spaces around <code>==</code> and <code>+=</code>. If you feel like fixing it, I think that spaces are the Python coding standard.
</li><li>At various points you add commented out code (either verbose print statements or the definition of <code>pair_max</code>). I'm fine with what you have, but I could also see just deleting it. I just wanted to make sure that the decision to include it, commented out, was conscious.
</li></ul><p>
There are also test failures.
</p>
<p>
Other than these comments, the code looks good to me and I'm happy to give it a positive review once they're addressed.
</p>
TicketkedlayaWed, 23 Aug 2017 00:42:18 GMT
https://trac.sagemath.org/ticket/8829#comment:67
https://trac.sagemath.org/ticket/8829#comment:67
<p>
Also, the example from comment 5 still seems to go into an infinite loop.
</p>
TicketcremonaWed, 23 Aug 2017 08:21:00 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:68
https://trac.sagemath.org/ticket/8829#comment:68
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Thanks to both for the reviews. I'll look into the spacing issues and the example. I really really want to get finished with this!
</p>
TicketcremonaWed, 23 Aug 2017 08:59:01 GMT
https://trac.sagemath.org/ticket/8829#comment:69
https://trac.sagemath.org/ticket/8829#comment:69
<p>
I first merged in the current develop (and fixed one small conflict). this required a rebuild (i.e. 'make' not just './sage -b' which failed).
</p>
<p>
I fixed that indentation issue -- logically correct but of course non-standard to have just one space of indentation. I hope the result is OK, that indented block was very long and had a lot of subsidiary indented parts.
</p>
<p>
I have fixed all (I hope) the == and += spacing.
</p>
<p>
I changed some commented-out debugging print statements into comments. I like having lots of comments since the logic is quite complicated (and if further bugs are found it may well be me who has to fix them so I might as well be helpful).
</p>
<p>
I'll test the example from comment 5 once the rebuild has finished.
</p>
TicketcremonaWed, 23 Aug 2017 11:38:36 GMT
https://trac.sagemath.org/ticket/8829#comment:70
https://trac.sagemath.org/ticket/8829#comment:70
<p>
Dammit, I always use trac branch names of the form u/cremona/nnnnn where nnnnn is the ticket number, but at some point the branch here became public/8829, so I have just been fixing the wrong version. What a waste of time. Back soon.
</p>
TicketcremonaWed, 23 Aug 2017 11:43:18 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/8829#comment:71
https://trac.sagemath.org/ticket/8829#comment:71
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>d2421238e6f1f174d90f8f81cbbc0606e79171b3</em> to <em>cd2b023195b23ff4fcf753f67a9acff9c5d87d6b</em>
</li>
<li><strong>branch</strong>
changed from <em>public/8829</em> to <em>u/cremona/8829</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=c93717d95b90638eec426528b7da527d158cde2f"><span class="icon"></span>c93717d</a></td><td><code>Merge branch 'develop' into 8829</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=cd2b023195b23ff4fcf753f67a9acff9c5d87d6b"><span class="icon"></span>cd2b023</a></td><td><code>#8829 edits after review</code>
</td></tr></table>
TicketcremonaWed, 23 Aug 2017 11:47:56 GMT
https://trac.sagemath.org/ticket/8829#comment:72
https://trac.sagemath.org/ticket/8829#comment:72
<p>
OK, back to review. Note that the branch is now u/cremona/8829.
</p>
TicketchapotonWed, 23 Aug 2017 11:51:00 GMT
https://trac.sagemath.org/ticket/8829#comment:73
https://trac.sagemath.org/ticket/8829#comment:73
<p>
"trial divison" is back, and probably all the other fixes went away.... Sorry for nitpicking, really..
</p>
TicketcremonaWed, 23 Aug 2017 12:19:20 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:74
https://trac.sagemath.org/ticket/8829#comment:74
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
!@$#!. OK, I will check out commit d242123 by hash to be sure that is what was most recently reviewed, and redo the work I did before. It's the only way to be certain.
</p>
TicketcremonaWed, 23 Aug 2017 14:05:29 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/8829#comment:75
https://trac.sagemath.org/ticket/8829#comment:75
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>cd2b023195b23ff4fcf753f67a9acff9c5d87d6b</em> to <em>37e22852ecaf466e9d9ce22bc66ffa94f2d7f652</em>
</li>
<li><strong>branch</strong>
changed from <em>u/cremona/8829</em> to <em>public/8829</em>
</li>
</ul>
<p>
I hope I got it right this time. The correct branch is public/8829 and I basically redid the edits I had already done this morning on the wrong branch.
</p>
<hr />
<p>
Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=9d66f355dfcba972495f8a459928aeb9488a4baa"><span class="icon"></span>9d66f35</a></td><td><code>trac 8829 fix for py3</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=a2f50232fc1289a9beec3a488a1cec9907f25f59"><span class="icon"></span>a2f5023</a></td><td><code>Merge branch 'develop' into 8829</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=5b40a83c70bee0fc21e1057c2b50475fca5f8a5b"><span class="icon"></span>5b40a83</a></td><td><code>#8829: move p-saturation code to a new file and fix tests and imports</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=8abe3dcf12c2e096cdc563cd5e071a8c35564501"><span class="icon"></span>8abe3dc</a></td><td><code>#8829 fix some docstrings and remove some internal functions</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=847d27665a592638b7767a2a88d1575e5f5544b1"><span class="icon"></span>847d276</a></td><td><code>#8829 fix a bug (typo n for p)</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=8c715855e54b1b1a12d82364a004f428c9a80097"><span class="icon"></span>8c71585</a></td><td><code>#8829: put back a one-line internal function</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=7b3c1886b7dbd481f7248c2271233c73ca483c01"><span class="icon"></span>7b3c188</a></td><td><code>#8829 fix docstring typos</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=d2421238e6f1f174d90f8f81cbbc0606e79171b3"><span class="icon"></span>d242123</a></td><td><code>#8829 correct spelling divison (*4)</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=63770c349a6688f74cfe7ac654f61e3334f3292a"><span class="icon"></span>63770c3</a></td><td><code>Merge branch 'develop' into 8829-new</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=37e22852ecaf466e9d9ce22bc66ffa94f2d7f652"><span class="icon"></span>37e2285</a></td><td><code>#8829 after review (2)</code>
</td></tr></table>
TicketroedWed, 23 Aug 2017 15:28:19 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/8829#comment:76
https://trac.sagemath.org/ticket/8829#comment:76
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Roe, Kiran Kedlaya, Frédéric Chapoton</em>
</li>
</ul>
<p>
It looks like you've addressed everything. I ran all tests and checked that the loop in comment 5 is no longer a problem.
</p>
TicketcremonaWed, 23 Aug 2017 15:38:00 GMT
https://trac.sagemath.org/ticket/8829#comment:77
https://trac.sagemath.org/ticket/8829#comment:77
<p>
Thanks a lot! This ticket was opened in 2010, so I'll be celebrating. Now, if any of you would like to head on over to <a class="closed ticket" href="https://trac.sagemath.org/ticket/22345" title="enhancement: Elliptic curve isogenies over number fields II: implement Billerey's ... (closed: fixed)">#22345</a>...
</p>
TicketchapotonWed, 23 Aug 2017 18:07:09 GMT
https://trac.sagemath.org/ticket/8829#comment:78
https://trac.sagemath.org/ticket/8829#comment:78
<p>
Very well, and I share your joy, but you introduced a .next(), which is not compatible with python3 (see patchbot plugin report). To be fixed in a later ticket, please.
</p>
TicketcremonaWed, 23 Aug 2017 18:39:25 GMT
https://trac.sagemath.org/ticket/8829#comment:79
https://trac.sagemath.org/ticket/8829#comment:79
<p>
That's a pity I thought the next () was rather neat. You can fix it here if you want.
</p>
TicketchapotonWed, 23 Aug 2017 18:40:05 GMT
https://trac.sagemath.org/ticket/8829#comment:80
https://trac.sagemath.org/ticket/8829#comment:80
<p>
no, no, let us wait and do that later
</p>
TicketchapotonWed, 23 Aug 2017 18:51:30 GMT
https://trac.sagemath.org/ticket/8829#comment:81
https://trac.sagemath.org/ticket/8829#comment:81
<p>
By the way, John, could you tell LMFDB people about <a class="closed ticket" href="https://trac.sagemath.org/ticket/23671" title="enhancement: hypergeometric motives (closed: fixed)">#23671</a>, please ?
</p>
TicketgitWed, 23 Aug 2017 20:45:59 GMTstatus, commit changed
https://trac.sagemath.org/ticket/8829#comment:82
https://trac.sagemath.org/ticket/8829#comment:82
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>37e22852ecaf466e9d9ce22bc66ffa94f2d7f652</em> to <em>ae6b11c67e43a3a9ffeb3b34d2b46b627967d432</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=ae6b11c67e43a3a9ffeb3b34d2b46b627967d432"><span class="icon"></span>ae6b11c</a></td><td><code>Changed .next() to next() in saturation.py for py3 compatibility</code>
</td></tr></table>
TicketkedlayaWed, 23 Aug 2017 20:46:53 GMT
https://trac.sagemath.org/ticket/8829#comment:83
https://trac.sagemath.org/ticket/8829#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8829#comment:80" title="Comment 80">chapoton</a>:
</p>
<blockquote class="citation">
<p>
no, no, let us wait and do that later
</p>
</blockquote>
<p>
Isn't it just this one-line change? If so, no reason to postpone it...
</p>
TicketroedWed, 23 Aug 2017 22:58:11 GMTstatus changed
https://trac.sagemath.org/ticket/8829#comment:84
https://trac.sagemath.org/ticket/8829#comment:84
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks good to me!
</p>
TicketvbraunTue, 29 Aug 2017 19:51:22 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/8829#comment:85
https://trac.sagemath.org/ticket/8829#comment:85
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/8829</em> to <em>ae6b11c67e43a3a9ffeb3b34d2b46b627967d432</em>
</li>
</ul>
TicketjdemeyerTue, 12 Sep 2017 14:03:36 GMTcommit deleted
https://trac.sagemath.org/ticket/8829#comment:86
https://trac.sagemath.org/ticket/8829#comment:86
<ul>
<li><strong>commit</strong>
<em>ae6b11c67e43a3a9ffeb3b34d2b46b627967d432</em> deleted
</li>
</ul>
<p>
This is causing doctest failures: <a class="closed ticket" href="https://trac.sagemath.org/ticket/23840" title="defect: Doctest failures in ell_number_field.py (closed: fixed)">#23840</a>.
</p>
TicketcremonaTue, 12 Sep 2017 14:40:17 GMT
https://trac.sagemath.org/ticket/8829#comment:87
https://trac.sagemath.org/ticket/8829#comment:87
<p>
I'm pretty certain it will be the usual nonsense of mathematically equivalent outputs. I'll look at <a class="closed ticket" href="https://trac.sagemath.org/ticket/23840" title="defect: Doctest failures in ell_number_field.py (closed: fixed)">#23840</a> and judge properly.
</p>
Ticket