Opened 12 years ago

Closed 9 years ago

#9411 closed enhancement (fixed)

Given points on an elliptic curve, this finds a LLL reduced ZZ-independent set

Reported by: Alyson Deines Owned by: John Cremona
Priority: minor Milestone: sage-5.13
Component: elliptic curves Keywords: LLL, rank, sd35.5
Cc: Jeremy West, John Cremona Merged in: sage-5.13.beta5
Authors: Aly Deines, John Cremona Reviewers: John Cremona, Paul Zimmermann, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Frédéric Chapoton)

This is based on magma code from Cremona. It takes a set of points on an elliptic curve and uses LLL to return a ZZ-independent set with the same ZZ-span.

Apply:

Attachments (4)

trac_9411-LLL_points.patch (3.6 KB) - added by Alyson Deines 12 years ago.
trac_9411_lll_reduce_number_field.patch (2.9 KB) - added by Alyson Deines 12 years ago.
This replaces the previous patch. It applies to sage-4.6.1.rc1
trac_9411_lll_reduce_number_field.2.patch (10.5 KB) - added by John Cremona 9 years ago.
rebased on 5.12.beta1 and added 2 new doctests
trac_9411_review.patch (4.9 KB) - added by Frédéric Chapoton 9 years ago.

Download all attachments as: .zip

Change History (26)

Changed 12 years ago by Alyson Deines

Attachment: trac_9411-LLL_points.patch added

comment:1 Changed 12 years ago by John Cremona

Authors: Alyson Deines
Reviewers: John Cremona
Status: newneeds_work

Aly, would it not have been simpler to move the code of the function lll_reduce(self, points, height_matrix=None) from ell_rational_field to ell_number_field? That function was written when we only had heights over Q but it does the same thing, essentially.

Apologies if I should have told you about that function earlier...

There may well be other functions which can similarly be moved up; someone should go systematically through ell_rational_field functions to see which others there are.

On your patch, I see the following: (1) no tests over fields other than Q; (2) in defining E why not just E=self?; (3) better to use the pari library than the gp interface (when there's a choice). Otherwise it applies and builds fine.

comment:2 Changed 12 years ago by Alyson Deines

Knowing about the lll_reduce function and finally getting back to this ticket, I've just created a patch which simply moves the function lll_reduce to ell_number_field. I've also included doctests over quadratic number fields.

One note, this code isn't very robust. For example, in many cases the height pairing matrix is *not* positive definite. In this case "the output depends on the undocumented behaviour of PARI's lllgram() function", which means there is a divide by zero error. Here's an example:

            sage: Qrt5.<rt5>=NumberField(x^2-5)
            sage: E = EllipticCurve([0,5-rt5,0,rt5,0])
            sage: QuadraticForm(E.height_pairing_matrix(E.gens())).is_positive_definite()
            False
            sage: E.lll_reduce(E.gens())
            Exception raised:
            Traceback (most recent call last):
            File "/Users/aly/Desktop/sage-4.6.1.rc1/local/bin/ncadoctest.py", line 1231, in run_one_test
            self.run_one_example(test, example, filename, compileflags)
            File "/Users/aly/Desktop/sage-4.6.1.rc1/local/bin/sagedoctest.py", line 38, in run_one_example
            OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
            File "/Users/aly/Desktop/sage-4.6.1.rc1/local/bin/ncadoctest.py", line 1172, in run_one_example
            compileflags, 1) in test.globs
            File "<doctest __main__.example_39[8]>", line 1, in <module>
            E.lll_reduce(E.gens())###line 2106:
            sage: E.lll_reduce(E.gens())
            File "/Users/aly/Desktop/sage-4.6.1.rc1/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 2117, in lll_reduce
            U = pari(height_matrix).lllgram().python()
            File "gen.pyx", line 7749, in sage.libs.pari.gen.gen.lllgram (sage/libs/pari/gen.c:34364)
            File "gen.pyx", line 9851, in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:46022)
            PariError: division by zero (27)

Changed 12 years ago by Alyson Deines

This replaces the previous patch. It applies to sage-4.6.1.rc1

comment:3 Changed 12 years ago by John Cremona

Status: needs_workneeds_review

Thanks for putting more work into this. I have not time to re-review right now, but I do intend to.

About the robustness, a better long term solution would be to separate out two different aspects: (1) give some points, return a maximal independent subset (or, return an independent set which has the same ZZ-span, which is not the same thing); (2) given independent points, LLL-reduce them.

But for this ticket I suggest that we just do the best we can using the pari function and sufficient precision.

comment:4 Changed 12 years ago by Alyson Deines

Authors: Alyson DeinesAly Deines

comment:5 Changed 11 years ago by John Cremona

I'm working on this now. First, I deleted the duplicate function still in ell_rational_field.py (but moved the examples there to ell_number_field.py). I also added a precision parameter to be passed to the height pairing matrix call, and am trying to make an example where it makes a difference!

comment:6 Changed 11 years ago by John Cremona

Authors: Aly DeinesAly Deines, John Cremona
Description: modified (diff)

I uploaded my patch which is a revision of Aly's, since I did not want it to get lost. It's fine for testing but I have not yet included an example where the precision parameter makes a difference.

comment:7 Changed 11 years ago by David Loeffler

What's the status of this ticket? It's marked as "needs review", but the last comment suggests that more work is needed.

comment:8 Changed 11 years ago by John Cremona

Well, I think it is ready for review. I certainly think that in principle the function ought to allow the user to set the precision which is used to compute the height-pairing matrix (which was not the case before). Secondly, we now have one function in ell_number_field instead of just one function on ell_rational_field, or two functions. So Sage is certainly enhanced by this!

Of course, the reviewer might insist on seeing an example where higher precision makes a difference....but I don't and I am listed as a reviewer though the latest patch was by me so we need a third party to have a look.

comment:9 Changed 11 years ago by Paul Zimmermann

Keywords: sd35.5 added
Reviewers: John CremonaJohn Cremona, Paul Zimmermann
Status: needs_reviewneeds_work
Work issues: improve documentation

all doctests pass on top of sage-4.8.alpha6.

However I suggest adding an example checking the relation between the input points, newpoints and the output matrix U:

sage: E = EllipticCurve([0, 1, 1, -2, 42])
sage: Pi = E.gens()
sage: Qi, U = E.lll_reduce(Pi)
sage: all(sum(U[i,j]*Pi[i] for i in range(4)) == Qi[j] for j in range(4))
True

And please add an example where an height_matrix is given, for example (this also gives an example where the precision matters):

sage: E = EllipticCurve([0, 1, 1, -2, 42])
sage: Pi = E.gens()
sage: H=E.height_pairing_matrix(Pi,3)
sage: E.lll_reduce(Pi,height_matrix=H)
([(-4 : 1 : 1), (-3 : 5 : 1), (-2 : 6 : 1), (1 : -7 : 1)], [1 0 0 1]
[0 1 0 1]
[0 0 0 1]
[0 0 1 1])

Also, I guess "number of bits of precision of result" should read "number of bits of precision of intermediate computations" (in fact the precision of the height matrix computation, which is given as input to Pari).

Paul

PS: the doctest coverage could be 100% if we could remove the deprecate function local_information. Can this be done?

comment:10 Changed 9 years ago by Frédéric Chapoton

apply only trac_9411_lll_reduce_number_field.2.patch

comment:11 Changed 9 years ago by Frédéric Chapoton

this needs to be rebased

comment:12 Changed 9 years ago by John Cremona

I volunteer to do that since I wrote the current patch. I think we can now remove that deprecated function too (if it is still there).

comment:13 Changed 9 years ago by John Cremona

I did the rebasing but am now also adding the tests suggested by Paul Zimmermann's comment 9.

Changed 9 years ago by John Cremona

rebased on 5.12.beta1 and added 2 new doctests

comment:14 in reply to:  13 Changed 9 years ago by John Cremona

Status: needs_workneeds_review

Replying to cremona:

I did the rebasing but am now also adding the tests suggested by Paul Zimmermann's comment 9.

Done, so back to "needs review".

comment:15 Changed 9 years ago by Frédéric Chapoton

apply only trac_9411_lll_reduce_number_field.2.patch

comment:16 Changed 9 years ago by Frédéric Chapoton

Description: modified (diff)

looks good to me.

I have made a review patch, mainly about details of the doc, but also removing the deprecated function local_information.

If the minor changes in my review patch are ok, this can be set to positive review

for the bot:

apply trac_9411_lll_reduce_number_field.2.patch, trac_9411_review.patch

Changed 9 years ago by Frédéric Chapoton

Attachment: trac_9411_review.patch added

comment:17 Changed 9 years ago by Frédéric Chapoton

rebased. Once again, if my minor changes are ok, you can set this to positive review

comment:18 Changed 9 years ago by John Cremona

Status: needs_reviewpositive_review

OK, I am happy to give chapoton's reviewer's patch +1 and set this to positive review. Since there have been other elliptic curve patches already merged into 5.14.beta4 I hope the rebasing is sufficient!

comment:19 Changed 9 years ago by Frédéric Chapoton

Reviewers: John Cremona, Paul ZimmermannJohn Cremona, Paul Zimmermann, Frédéric Chapoton

comment:20 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.13

comment:21 Changed 9 years ago by Jeroen Demeyer

Work issues: improve documentation

comment:22 Changed 9 years ago by Jeroen Demeyer

Merged in: sage-5.13.beta5
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.