Opened 11 years ago

Closed 11 years ago

#3377 closed enhancement (fixed)

[with new patch, positive review] torsion and other functions for elliptic curves over number fields

Reported by: wuthrich Owned by: was
Priority: minor Milestone: sage-3.1.2
Component: number theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

It computes the torsion subgroup of an elliptic curve over a number field. The method is the usual idea: Find an upper bound for the order, by considering a few reductions of the elliptic curve at places of small residue fields. Then construct the points by finding roots of the division polynomials over the number field.

This patch changes the file ell_number_field.py and adds a file ell_nf_torsion.py.

(sorry, if I am doing something wrong here : I am a trac-newbie !)

Attachments (8)

elliptic_curve_torsion_number_field.patch (7.5 KB) - added by wuthrich 11 years ago.
ell_nf_torsion.py (6.2 KB) - added by wuthrich 11 years ago.
ell_nf_torsion.patch (6.8 KB) - added by cremona 11 years ago.
Replacement for previous .py file (as a proper hg patch)
trac3377-extra1.patch (6.7 KB) - added by cremona 11 years ago.
Apply after previous
trac3377.extra2.patch (1.2 KB) - added by wuthrich 11 years ago.
trac3377.extra3.patch (86.3 KB) - added by cremona 11 years ago.
3377-torsion_nf.patch (85.0 KB) - added by AlexGhitza 11 years ago.
apply only this patch
3377-torsion_nf-1.patch (3.3 KB) - added by cremona 11 years ago.

Download all attachments as: .zip

Change History (27)

Changed 11 years ago by wuthrich

Changed 11 years ago by wuthrich

comment:1 Changed 11 years ago by cremona

I'll be very happy to review this over the weekend. Thanks, Chris!

comment:2 Changed 11 years ago by mabshoff

  • Milestone set to sage-3.0.3

Changed 11 years ago by cremona

Replacement for previous .py file (as a proper hg patch)

comment:3 Changed 11 years ago by cremona

  • Summary changed from [with patch, needs review] torsion for elliptic curves over number fields to [with patch, with preliminary review] torsion for elliptic curves over number fields
  1. I applied the first patch ok to 3.0.3.alpha1, then copied the second non-patch .py file into place, added it to the repository and re-exported it to make the second genuine patch attached (ell_nf_torsion.patch).
  1. Doctests passed except for one error caused by a missing blank line at line 165 of ell_number_field.py.
  1. The new file ell_nf_torsion.py and old file rational_torsion.py should probably be merged; and certainly delete from the latter the lines
    TODO:
        -- Torsion subgroups over number fields!
    
  1. The function reduce() to reduce an e.c. at a place is very useful. But it doesn't work for e.c.s defined over Q. Rather than hack this code to work over Q I suggest adding a reduction method (function) in ell_rational_field.py just like the new one. I can do this.

More to follow.... I am planning to add a further patch with some minor changes.

Changed 11 years ago by cremona

Apply after previous

comment:4 Changed 11 years ago by cremona

  • Summary changed from [with patch, with preliminary review] torsion for elliptic curves over number fields to [with patch, with further review] torsion for elliptic curves over number fields

The patch trac3377-extra1.patch adds some doctests (not yet complete) and a few minor changes to the code just for clarity.

  • I think that it might be cleaner to use the P.division_points() functionality recently added by William instead of using the division polynomials directly. But when I tried this I hit a bug (#3383) so this idea will have to wait until that is fixed. For example, where the p-torsion is cyclic (the usual case) one could just pick a p-torsion point and keep dividing it by p until that is no longer possible, to get the one generator.
  • The has_x() function would be useful as a member function of the generic elliptic curve class
  • The torsion_bound() function is perhaps more naturally a member of the ell_number_field class?
  • Is the intention for this to replace the code in rational_torsion.py? That is not clear. I would say that there should be special code for the rational field, but that the two cases could be included in the same file; however that would need rewriting the class definitions a bit since at present the same class name is used in both files. It would work fine to have one class EllipticCurveTorsionSubgroup whose constructor used different code depending on whether the base_ring was or was not QQ.

Changed 11 years ago by wuthrich

comment:5 Changed 11 years ago by wuthrich

trac3377.extra2.patch has to be applied after trac3377-extra1.patch

It corrects .div to .quo_rem, since it seems that the .div no longer exists for these polynomials.

Changed 11 years ago by cremona

comment:6 Changed 11 years ago by cremona

  • Summary changed from [with patch, with further review] torsion for elliptic curves over number fields to [with new patch, needs review] torsion and other functions for elliptic curves over number fields

Another patch attached (trac3377.extra3.patch) -- sorry to do this so late in the release cycle, this can wait until the next one after 3.1.2 unless there's a quick review.

This patch adds quite a lot of new functionality as well as refactoring what was done already. Apply all the patches in order (omit the one whose name ends .py) to 3.1.2.alpha2 or later. (It will not apply to 3.1.1 unless the division-polynomials patches are applied first so best to use 3.1.2.alpha2). I tested that this does work and all tests in sage.schemes.elliptic_curves pass.

In the new patch I deleted the new file ell_nf_torsion.py and also the old file rational_torsion.py, replacing them with a new file ell_torsion.py which unifies the code for Q and number fields.

There's a new class !EllipticCurvePoint_number_field derived from !EllipticCurvePoint_field, and functions specific to number fields have been moved down there; this class also handles points on curves over Q, for which there is a bit more functionality -- but the gap is closing!

I moved Chris's p-primary-torsion into ell_generic.py, as it does work more generally. I also moved the torsion_bound function into ell_number_field.py since it can be used to determine whether points have finite order or not, and find their order, even if the full torsion_subgroup() function is not used. The bound is cached.

In going over the code for points over number fields I have made several things work which only used to work over Q, such as period_lattice and elliptic_logarithm -- provided that one supplies a real embedding of the number field. Precision issues are dealt with intelligently (I hope). That required a function refine_embedding() which I put in sage.rings.number_field.numer_field.py. At some point someone will implement period lattices and elliptic logs for complex (non-real) embeddings -- I know how to do the former using complex AGM, but have never worked out the latter.

There you are -- I changed the ticket's title to reflect the fact that a lot more than torsion is covered. I would certainly like Chris to review this as he started it, but we need an independent 3rd party too, such as Nick Alexander?

comment:7 Changed 11 years ago by wuthrich

  • Cc john.cremona@… added

Great work. This patch contains quite a lot of things and it should be reviewed carefully and independently, I agree.

I ran into the following problem, which is probably unrelated to this.

E = EllipticCurve('37a1')
K = Qp(7,10)
EK = E.base_extend(K)

Then

EK._p_primary_torsion_basis(3)

fails with

AttributeError: 'Polynomial_padic_flat' object has no attribute '__coeffs'

because this fails already

g = EK.division_polynomial_0(3)
g.roots()

Chris

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

Thanks. Alex Ghitza has agreed to review this too. I'll look into why g.roots() fails for a p-adic polynomial.

By the way, there's no need to add me to the CC, since anyone who contributes to a ticket is automatically CC'd.

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

  • Cc john.cremona@… removed

By the way, there's no need to add me to the CC, since anyone who contributes to a ticket is automatically CC'd.

Oh I didn't know. So you are saying I should get your posts cc'd ? i don't !??

comment:10 in reply to: ↑ 9 Changed 11 years ago by mabshoff

Replying to wuthrich:

By the way, there's no need to add me to the CC, since anyone who contributes to a ticket is automatically CC'd.

Oh I didn't know. So you are saying I should get your posts cc'd ? i don't !??

Chris,

in "Settings" you can add an email address for your account that is used. In case you did that already you should get emails from all comments by anybody commenting on any ticket you are involved in. If it does not work let me know.

If you want to add people to the CC field it is sufficient to add their trac account name, i.e. "cremona" would work here.

Cheers,

Michael

comment:11 Changed 11 years ago by wuthrich

ok i got it, thanks.

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

Replying to cremona:

Thanks. Alex Ghitza has agreed to review this too. I'll look into why g.roots() fails for a p-adic polynomial.

This is now trac # 4038.

Changed 11 years ago by AlexGhitza

apply only this patch

comment:13 Changed 11 years ago by AlexGhitza

  • Summary changed from [with new patch, needs review] torsion and other functions for elliptic curves over number fields to [with new patch, positive review] torsion and other functions for elliptic curves over number fields

Chris and John,

This is good stuff. I was having trouble looking at the changes over all the different patches, so I folded all your patches into one. While reading the code, I made a number of minor changes, described below:

  1. file: number_field.py, function refine_embedding(): added a doctest
  1. file: ell_number_field.py, function reduction(): added a type check to throw an exception if the parameter place is not a fractional ideal of K. As an added bonus, one can now do E.reduction(2*i+3) and the function automatically makes 2*i+3 into the appropriate fractional ideal
  1. file: ell_point.py, function _divide_out(): added doctests
  1. various typos in various files (some of them predating these patches)

CONCLUSION: apply only the last patch (3377-torsion_nf.patch); credit goes to Chris Wuthrich and John Cremona

comment:14 Changed 11 years ago by mabshoff

  • Summary changed from [with new patch, positive review] torsion and other functions for elliptic curves over number fields to [with new patch, needs work] torsion and other functions for elliptic curves over number fields

I am seeing two doctest failures on 3.1.2.alpha4+three merged patches:

mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.1.2.rc0$ ./sage -t -long devel/sage/sage/schemes/elliptic_curves/ell_point.py
sage -t -long devel/sage/sage/schemes/elliptic_curves/ell_point.py
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.1.2.rc0/tmp/ell_point.py", line 946:
    sage: e1 <= e(P[0]) <= e2 < e3
Expected:
    True
Got:
    False
**********************************************************************

And some numerical noise it seems:

mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.1.2.rc0$ ./sage -t -long devel/sage/sage/schemes/elliptic_curves/ell_number_field.py
sage -t -long devel/sage/sage/schemes/elliptic_curves/ell_number_field.py
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.1.2.rc0/tmp/ell_number_field.py", line 1123:
    sage: L.basis()
Expected:
    (4.13107185270501681, -2.06553592635250840 + 0.988630424469107767*I)
Got:
    (4.13107185270501680, -2.06553592635250840 + 0.988630424469107767*I)
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.1.2.rc0/tmp/ell_number_field.py", line 1125:
    sage: L.basis(prec=75)
Expected:
    (4.131071852705016774309696920,
    -2.065535926352508387154848460 + 0.9886304244691077723690104516*I)
Got:
    (4.1310718527050167743096969215298790187, -2.0655359263525083871548484607649395093 + 0.98863042446910777236901045157674201375*I)
**********************************************************************

comment:15 Changed 11 years ago by AlexGhitza

I cannot reproduce any of these in my pristine 3.1.2.alpha4 (on 32bit ubuntu).

AFAIK (i.e. trac tells me) that the only patches merged in rc0 so far are #4043 (which has no way of interacting with this) and #3885. I applied #3885 to my alpha4, then the patch here, and I'm still not getting any of these failures.

So I don't know what's going on.

comment:16 Changed 11 years ago by cremona

Many thanks to Alex for his review, his additions, and for rolling all our patches into one -- something I avoid doing since I always mess it up.

I'll try out his new single patch and see if I can sort out mabshoff's issues.

Changed 11 years ago by cremona

comment:17 Changed 11 years ago by cremona

  • Summary changed from [with new patch, needs work] torsion and other functions for elliptic curves over number fields to [with new patch, needs review (easy)] torsion and other functions for elliptic curves over number fields

Alex's patch applies fine to 3.1.2.alpha4. I get the same doctest issues as Michael on a 64-bit machine. Both are fixed in 3377-torsion_nf-1.patch.

In the first e1 <= e(P[0]) <= e2 < e3 is really true since e(P[0])==e2==-1 but rounding error caused e(P[0]) <= e2 to give false sometimes. I fixed this by checking it differently.

In the second it's just numerical fuzz in the last decimal place, so I replces the last 3 digits by ... in the doctest.

The result passes all doctests in sage.schemes.elliptic_curves on both 32-bit and 64-bit machines. I would not be that surprised if on some other machines we saw more of the same, though: several bits of the patches are about computing some numbers to arbitrary precision, so I did want to include some decimal numbers in the output, and I have not (sorry) gone through each and every one replacing the final digits by dots.

comment:18 Changed 11 years ago by AlexGhitza

  • Summary changed from [with new patch, needs review (easy)] torsion and other functions for elliptic curves over number fields to [with new patch, positive review] torsion and other functions for elliptic curves over number fields

This looks good and passes all tests on my machine.

One should apply 3377-torsion_nf.patch followed by 3377-torsion_nf-1.patch.

comment:19 Changed 11 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged 3377-torsion_nf.patch and 3377-torsion_nf-1.patch in Sage 3.1.2.rc0. Now everything works for me.

Cheers,

Michael

Note: See TracTickets for help on using tickets.