Opened 12 years ago

Closed 4 years ago

Last modified 4 years ago

#8829 closed enhancement (fixed)

Saturation for MW-groups of elliptic curves over number fields.

Reported by: robertwb Owned by: cremona
Priority: major Milestone: sage-8.1
Component: elliptic curves Keywords: saturation
Cc: pbruin, kedlaya Merged in:
Authors: Robert Bradshaw, John Cremona Reviewers: David Roe, Kiran Kedlaya, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: ae6b11c (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by cremona)

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.

I also implemented the simple case of E.gens() for E(K) when E/Q and [K:Q] = 2.

Attachments (1)

8829-ec-nf-sat.patch (20.5 KB) - added by robertwb 12 years ago.

Download all attachments as: .zip

Change History (88)

comment:1 Changed 12 years ago by robertwb

  • Status changed from new to needs_review

Some dependance on #8828.

comment:2 follow-up: Changed 12 years ago by cremona

I have had a quick look and will go through this in more detail later (after #8828 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.

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), http://etheses.nottingham.ac.uk/52/.

Martin Prickett implemented this in Magma, but the code was very slow and hard to read so it never got incorporated into Magma releases.

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 < 10^6 (the bound was totally out of reach, something like 10^100).

Another point which might be useful over number fields: it suffices to use degree one primes to reduce modulo.

Changed 12 years ago by robertwb

comment:3 in reply to: ↑ 2 Changed 12 years ago by robertwb

Replying to cremona:

I have had a quick look and will go through this in more detail later (after #8828 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.

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), http://etheses.nottingham.ac.uk/52/.

Ah, those look like good references to read too :).

Martin Prickett implemented this in Magma, but the code was very slow and hard to read so it never got incorporated into Magma releases.

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.

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.

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 < 10^6 (the bound was totally out of reach, something like 10^100).

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.

Another point which might be useful over number fields: it suffices to use degree one primes to reduce modulo.

Good point. Those get pretty rare for large degree number fields though, right?

comment:4 Changed 12 years ago by cremona

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.

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.

comment:5 Changed 12 years ago by cremona

  • Authors set to Robert Bradshaw
  • Reviewers set to John Cremona
  • Status changed from needs_review to needs_work

Patch applies fine to 4.4.1 and tests pass.

This functionality is badly needed!

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

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.

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.

The function list_of_multiples(P,n) duplicated the generic function multiples() which I wrote for just this sort of purpose!

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 2^24 divisions is not nice to contemplate. If you want this short cut, do it based on the size of p^r.

The main code with reduction etc looks fine to me (but I did not check the logic rigorously).

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:

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

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.

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.

comment:6 follow-up: Changed 12 years ago by robertwb

Thank you for all your input. self.height_function comes from #8828, 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 p == 2 case was left by accident, I meant to cap that on p^r as I did the others.

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.

comment:7 in reply to: ↑ 6 Changed 12 years ago by cremona

Replying to robertwb:

Thank you for all your input. self.height_function comes from #8828, 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 p == 2 case was left by accident, I meant to cap that on p^r as I did the others.

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.

OK -- looking forward to it! I'll take a look at #8828 by then as well.

comment:8 Changed 11 years ago by cremona

Since rwb is now busy at Google, and I want this functionality, I am now implementing the changes I suggested above!

comment:9 Changed 11 years ago by cremona

I made a separate ticket for the regulator functions. See #9372.

comment:10 Changed 9 years ago by roed

How is this going John? It seems to have been awhile....

comment:11 follow-up: Changed 9 years ago by cremona

See #12509: until we can fix the height computation, saturation cannot be carried out properly. It's still on my to-do list though.

comment:12 in reply to: ↑ 11 Changed 9 years ago by cremona

Replying to cremona:

See #12509: until we can fix the height computation, saturation cannot be carried out properly. It's still on my to-do list though.

#12509 is now up for review.

comment:13 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:14 Changed 8 years ago by cremona

  • Dependencies set to #8828

comment:15 Changed 8 years ago by nbruin

  • Summary changed from Saturation for curves over number fields. to Saturation for MW-groups of elliptic curves over number fields.

comment:16 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 8 years ago by pbruin

  • Cc pbruin added

comment:18 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:19 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:20 Changed 6 years ago by cremona

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

comment:21 Changed 6 years ago by cremona

  • Authors changed from Robert Bradshaw to Robert Bradshaw, John Cremona
  • Branch set to u/cremona/8829
  • Commit set to 0e1e35f624edb087d3fb1ddc21226fec7acfafad
  • Description modified (diff)
  • Keywords saturation added

New commits:

be41e01first work on updating #9929 to a working branch (not done yet)
4b4fc21#8829: ell_height now passes its doctests...
0e1e35f#8829: refactored saturation; ell_number_field passes its doctests but more testing and tests needed...

comment:22 Changed 6 years ago by cremona

Current branch works but more doctests and testing are needed; so not ready for review yet.

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.

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

comment:23 Changed 6 years ago by git

  • Commit changed from 0e1e35f624edb087d3fb1ddc21226fec7acfafad to a85f40629df89da829e3a38d9e0443576bced01d

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

a85f406#8829: finished doctests for ec/nf saturation

comment:24 Changed 6 years ago by cremona

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 http://eprints.nottingham.ac.uk/10052/) 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 https://ore.exeter.ac.uk/repository/handle/10871/8323 .

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.

comment:25 Changed 6 years ago by cremona

  • Reviewers John Cremona deleted
  • Status changed from needs_work to needs_review

comment:26 follow-up: Changed 6 years ago by chapoton

Hello,

1) indent correctly the INPUT and OUTPUT fields:

INPUT:

- first thing
  goes one there (note the shift of 2 characters)

2) use the new syntax for raise:

raise MyError("is rich")

Point 1 may be the source of the doc build failure found by the bot:

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.

Last edited 6 years ago by chapoton (previous) (diff)

comment:27 in reply to: ↑ 26 Changed 6 years ago by cremona

Replying to chapoton:

Hello,

1) indent correctly the INPUT and OUTPUT fields:

INPUT:

- first thing
  goes one there (note the shift of 2 characters)

2) use the new syntax for raise:

raise MyError("is rich")

Point 1 may be the source of the doc build failure found by the bot:

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.

Thanks, I will fix those.

comment:28 Changed 6 years ago by git

  • Commit changed from a85f40629df89da829e3a38d9e0443576bced01d to 4f511b89fd199d070bad0d1054efa148d765fdf6

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

4f511b8fixup doc errors and raise() syntax

comment:29 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

many failing doctests, see bot report

comment:30 Changed 6 years ago by cremona

Apologies, it was a mistake to set this to needs_review prematurely. Next time I do, I will mean it.

comment:31 Changed 6 years ago by git

  • Commit changed from 4f511b89fd199d070bad0d1054efa148d765fdf6 to 2f20f7373a13e2267bc5ae3d2a7cae93278a76c4

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

1647ce2#8829: rewrote projections() so dlogs computed in smaller subgroups
2f20f73Merge branch 'develop' (6.9.beta6) into saturate

comment:32 Changed 6 years ago by cremona

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.

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 #8828). 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:

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

Strictly this is about the code merged in #8828, but it will need fixing here before we can let this (useful!) function out into the world.

comment:33 Changed 6 years ago by git

  • Commit changed from 2f20f7373a13e2267bc5ae3d2a7cae93278a76c4 to 8686677fa5cdf4359fd6f6b8d8e25925f6893a4c

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

7dbb186Merge branch 'develop' of trac.sagemath.org:sage into isogs
c66d49fMerge branch 'develop' of trac.sagemath.org:sage into isogs
ce2472bMerge branch 'isogs' into sat+isogs
8c80b6fMerge branch 'saturate' into sat+isogs
86866778829: two bug fixes, more tests

comment:34 Changed 6 years ago by cremona

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.

One bug fix addresses the previous comment -- after re-reading my own 2006 paper I found that the original implementer from #8828 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.

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.

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.

I will set this to needs_review once my own full test has completed.

comment:35 Changed 6 years ago by cremona

  • Status changed from needs_work to needs_review

comment:36 Changed 6 years ago by cremona

  • Description modified (diff)
  • Status changed from needs_review to needs_work

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

comment:37 Changed 6 years ago by git

  • Commit changed from 8686677fa5cdf4359fd6f6b8d8e25925f6893a4c to 99158817c3895207ebae8f3dc06e83f0b7c6a1cb

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

9915881changed multiplicative dlog to not use discrte_log_lambda

comment:38 Changed 6 years ago by cremona

  • Status changed from needs_work to needs_review

comment:39 Changed 6 years ago by cremona

  • Status changed from needs_review to needs_work

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.

comment:40 Changed 6 years ago by cremona

I did do more work on that but did not get to the bottom of it. Just keeping the ticket alive!

comment:41 Changed 6 years ago by git

  • Commit changed from 99158817c3895207ebae8f3dc06e83f0b7c6a1cb to f3eb76aaffcd66e55aa48a0ca3fce51f1a4d3a19

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

e481c40first work on updating #9929 to a working branch (not done yet)
00b6ac6#8829: ell_height now passes its doctests...
8c44155#8829: refactored saturation; ell_number_field passes its doctests but more testing and tests needed...
a64e3c9#8829: finished doctests for ec/nf saturation
573d4b7fixup doc errors and raise() syntax
7b2f1de#8829: rewrote projections() so dlogs computed in smaller subgroups
f3eb76aadded check to catch Weil pairing errors during saturation

comment:42 Changed 6 years ago by git

  • Commit changed from f3eb76aaffcd66e55aa48a0ca3fce51f1a4d3a19 to a135224f6a7b28c913b4fbe77ade7ed1d15094c3

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

e9862308829: two bug fixes, more tests
a135224changed multiplicative dlog to not use discrete_log_lambda

comment:43 Changed 6 years ago by cremona

Merging with 7.1.beta3....

comment:44 Changed 6 years ago by git

  • Commit changed from a135224f6a7b28c913b4fbe77ade7ed1d15094c3 to 70bb203a14669ff411b2035e33112462c7053707

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

70bb203fix merge conflicts in ell_number_field

comment:45 Changed 5 years ago by chapoton

  • Branch changed from u/cremona/8829 to public/8829
  • Commit changed from 70bb203a14669ff411b2035e33112462c7053707 to 4a7bdc29883e72ceb8e65a8608c6ea3deef4b5fd

just rebased on 7.5.b3


New commits:

4a7bdc2Merge branch 'u/cremona/8829' in 7.5.b3

comment:46 Changed 5 years ago by git

  • Commit changed from 4a7bdc29883e72ceb8e65a8608c6ea3deef4b5fd to 9d66f355dfcba972495f8a459928aeb9488a4baa

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

47b7d2bMerge branch 'public/8829' in 7.5.b6
9d66f35trac 8829 fix for py3

comment:47 Changed 4 years ago by git

  • Commit changed from 9d66f355dfcba972495f8a459928aeb9488a4baa to a2f50232fc1289a9beec3a488a1cec9907f25f59

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

a2f5023Merge branch 'develop' into 8829

comment:48 Changed 4 years ago by cremona

I just merged 8,0 into the branch prior to looking at it again.

comment:49 Changed 4 years ago by git

  • Commit changed from a2f50232fc1289a9beec3a488a1cec9907f25f59 to 5b40a83c70bee0fc21e1057c2b50475fca5f8a5b

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

5b40a83#8829: move p-saturation code to a new file and fix tests and imports

comment:50 Changed 4 years ago by cremona

  • Status changed from needs_work to needs_review

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.

comment:51 Changed 4 years ago by chapoton

  • Dependencies #8828 deleted
  • Milestone changed from sage-6.4 to sage-8.1

comment:52 Changed 4 years ago by chapoton

Quick comments :

  • dot not use $ but backticks
  • every function must be doctested

comment:53 Changed 4 years ago by cremona

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

comment:54 Changed 4 years ago by chapoton

Hello ! some dollars there :

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

and no doc for

+    def projections(Q, p):

which is indeed an inner function, but quite a complicated one. Maybe just explain its input and output ?

comment:55 Changed 4 years ago by cremona

I stand corrected and will see to this.

comment:56 Changed 4 years ago by cremona

For the inner function projections(Q, p) there is already a docstring:

        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

which explains what it does. I'll make sure that all the other inner functions are explained.

comment:57 Changed 4 years ago by git

  • Commit changed from 5b40a83c70bee0fc21e1057c2b50475fca5f8a5b to 8c715855e54b1b1a12d82364a004f428c9a80097

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

8abe3dc#8829 fix some docstrings and remove some internal functions
847d276#8829 fix a bug (typo n for p)
8c71585#8829: put back a one-line internal function

comment:58 Changed 4 years ago by cremona

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.

Please review!

comment:59 Changed 4 years ago by chapoton

a typo here:

trial divison

and also a missing line break here after r""":

+        r""" Given a list of rational points on `E` over `K`, compute the

same here:

        """Return generators for the Mordell-Weil group modulo torsion, for a

same there:

+    r""" Checks whether the list of points is `p`-saturated.

and

+    r""" Full `p`-saturation of ``Plist``.

another typo:

divisble

This :

+        if len(EE)==0:

can be replaced by if not EE

another typo:

algirithm

comment:60 Changed 4 years ago by git

  • Commit changed from 8c715855e54b1b1a12d82364a004f428c9a80097 to 7b3c1886b7dbd481f7248c2271233c73ca483c01

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

7b3c188#8829 fix docstring typos

comment:61 Changed 4 years ago by cremona

I fixed those, and at least one more. Thanks

comment:62 Changed 4 years ago by chapoton

"trial divison" is still there

comment:63 Changed 4 years ago by git

  • Commit changed from 7b3c1886b7dbd481f7248c2271233c73ca483c01 to d2421238e6f1f174d90f8f81cbbc0606e79171b3

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

d242123#8829 correct spelling divison (*4)

comment:64 Changed 4 years ago by cremona

Not now it isn't. I also used "grep -r" to catch 3 more (not mine).

One day I might get a review of the code!

comment:65 Changed 4 years ago by kedlaya

  • Cc kedlaya added

comment:66 Changed 4 years ago by roed

Some comments on code:

  • There's something weird with the indentation at for Q in K.primes_above(q, degree=1): in p_saturation (it looks only indented one space).
  • There are various points where you don't have spaces around == and +=. If you feel like fixing it, I think that spaces are the Python coding standard.
  • At various points you add commented out code (either verbose print statements or the definition of pair_max). 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.

There are also test failures.

Other than these comments, the code looks good to me and I'm happy to give it a positive review once they're addressed.

comment:67 Changed 4 years ago by kedlaya

Also, the example from comment 5 still seems to go into an infinite loop.

comment:68 Changed 4 years ago by cremona

  • Status changed from needs_review to needs_work

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!

comment:69 Changed 4 years ago by cremona

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

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.

I have fixed all (I hope) the == and += spacing.

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

I'll test the example from comment 5 once the rebuild has finished.

comment:70 Changed 4 years ago by cremona

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.

comment:71 Changed 4 years ago by cremona

  • Branch changed from public/8829 to u/cremona/8829
  • Commit changed from d2421238e6f1f174d90f8f81cbbc0606e79171b3 to cd2b023195b23ff4fcf753f67a9acff9c5d87d6b
  • Status changed from needs_work to needs_review

New commits:

c93717dMerge branch 'develop' into 8829
cd2b023#8829 edits after review

comment:72 Changed 4 years ago by cremona

OK, back to review. Note that the branch is now u/cremona/8829.

comment:73 Changed 4 years ago by chapoton

"trial divison" is back, and probably all the other fixes went away.... Sorry for nitpicking, really..

comment:74 Changed 4 years ago by cremona

  • Status changed from needs_review to needs_work

!@$#!. 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.

comment:75 Changed 4 years ago by cremona

  • Branch changed from u/cremona/8829 to public/8829
  • Commit changed from cd2b023195b23ff4fcf753f67a9acff9c5d87d6b to 37e22852ecaf466e9d9ce22bc66ffa94f2d7f652
  • Status changed from needs_work to needs_review

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.


Last 10 new commits:

9d66f35trac 8829 fix for py3
a2f5023Merge branch 'develop' into 8829
5b40a83#8829: move p-saturation code to a new file and fix tests and imports
8abe3dc#8829 fix some docstrings and remove some internal functions
847d276#8829 fix a bug (typo n for p)
8c71585#8829: put back a one-line internal function
7b3c188#8829 fix docstring typos
d242123#8829 correct spelling divison (*4)
63770c3Merge branch 'develop' into 8829-new
37e2285#8829 after review (2)

comment:76 Changed 4 years ago by roed

  • Reviewers set to David Roe, Kiran Kedlaya, Frédéric Chapoton
  • Status changed from needs_review to positive_review

It looks like you've addressed everything. I ran all tests and checked that the loop in comment 5 is no longer a problem.

comment:77 Changed 4 years ago by cremona

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

comment:78 Changed 4 years ago by chapoton

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.

Last edited 4 years ago by chapoton (previous) (diff)

comment:79 Changed 4 years ago by cremona

That's a pity I thought the next () was rather neat. You can fix it here if you want.

comment:80 follow-up: Changed 4 years ago by chapoton

no, no, let us wait and do that later

comment:81 Changed 4 years ago by chapoton

By the way, John, could you tell LMFDB people about #23671, please ?

comment:82 Changed 4 years ago by git

  • Commit changed from 37e22852ecaf466e9d9ce22bc66ffa94f2d7f652 to ae6b11c67e43a3a9ffeb3b34d2b46b627967d432
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

ae6b11cChanged .next() to next() in saturation.py for py3 compatibility

comment:83 in reply to: ↑ 80 Changed 4 years ago by kedlaya

Replying to chapoton:

no, no, let us wait and do that later

Isn't it just this one-line change? If so, no reason to postpone it...

comment:84 Changed 4 years ago by roed

  • Status changed from needs_review to positive_review

Looks good to me!

comment:85 Changed 4 years ago by vbraun

  • Branch changed from public/8829 to ae6b11c67e43a3a9ffeb3b34d2b46b627967d432
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:86 Changed 4 years ago by jdemeyer

  • Commit ae6b11c67e43a3a9ffeb3b34d2b46b627967d432 deleted

This is causing doctest failures: #23840.

comment:87 Changed 4 years ago by cremona

I'm pretty certain it will be the usual nonsense of mathematically equivalent outputs. I'll look at #23840 and judge properly.

Note: See TracTickets for help on using tickets.