Opened 3 years ago

Closed 8 months ago

#11905 closed enhancement (fixed)

Implement division_field() for elliptic curves

Reported by: jdemeyer Owned by: cremona
Priority: major Milestone: sage-6.1
Component: elliptic curves Keywords:
Cc: cremona Merged in:
Authors: Jeroen Demeyer Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: u/jdemeyer/ticket/11905 (Commits) Commit: bb388718023f3eaeec59d97673152996c53f9efb
Dependencies: #2217, #15626, #11271 Stopgaps:

Description (last modified by jdemeyer)

sage/schemes/elliptic_curves/gal_reps.py has code to compute a splitting field, but that clearly does not belong to elliptic curves. This is used to compute the division field. We should use the new splitting_field() function from #2217 to implement this. We should make it work also over number fields.

Attachments (1)

11905_splitting_field.patch (15.6 KB) - added by jdemeyer 3 years ago.

Download all attachments as: .zip

Change History (35)

comment:1 Changed 3 years ago by jdemeyer

  • Dependencies set to #11891

comment:2 Changed 3 years ago by jdemeyer

  • Component changed from number fields to elliptic curves
  • Dependencies changed from #11891 to #11904, #11995, #2217
  • Description modified (diff)
  • Owner changed from davidloeffler to cremona

comment:3 Changed 3 years ago by jdemeyer

  • Summary changed from Move _splitting_field from elliptic curves to rings to Remove _splitting_field() from elliptic curves

comment:4 follow-up: Changed 3 years ago by wuthrich

Thanks for spotting and changing this. One could even argue that the division field should be available to all elliptic curves, not just the ones over QQ. But this could be changed later.

comment:5 Changed 3 years ago by jdemeyer

This is still very much work in progress by the way.

comment:6 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:7 in reply to: ↑ 4 Changed 3 years ago by jdemeyer

Replying to wuthrich:

Thanks for spotting and changing this. One could even argue that the division field should be available to all elliptic curves, not just the ones over QQ. But this could be changed later.

I can easily do number fields, very general fields would be harder.

Changed 3 years ago by jdemeyer

comment:8 Changed 13 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 10 months ago by chapoton

#2217 is ready for review

comment:10 Changed 8 months ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)

comment:11 Changed 8 months ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/11905
  • Modified changed from 01/03/14 09:00:10 to 01/03/14 09:00:10

comment:12 Changed 8 months ago by git

  • Commit set to a76a510907abe23c0d1bc188ae8f5fb16b0dfdf6

Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:

a76a510Implement division_field() for elliptic curves
c50eb3eNo need to specify caller_name in verbose()
6df69b6Add comments, small cosmetic changes
9e2dd44Make q monic before computing cubic resolvent
9b5558eImplement splitting fields for number fields

comment:13 Changed 8 months ago by jdemeyer

  • Dependencies changed from #11904, #11995, #2217 to #2217

comment:14 Changed 8 months ago by jdemeyer

  • Dependencies changed from #2217 to #2217, #15626

comment:15 Changed 8 months ago by git

  • Commit changed from a76a510907abe23c0d1bc188ae8f5fb16b0dfdf6 to d6a7f3cd497cd3ff24241201ef079912dcf41d85

Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:

d6a7f3cImplement division_field() for elliptic curves
776795dDo polynomial consistency check only for minimal dm
df52508Further improvements to splitting_field()
c50eb3eNo need to specify caller_name in verbose()
6df69b6Add comments, small cosmetic changes

comment:16 Changed 8 months ago by git

  • Commit changed from d6a7f3cd497cd3ff24241201ef079912dcf41d85 to 387216c0e072a504ba19753570e99ac45378e1b7

Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:

387216cImplement division_field() for elliptic curves
776795dDo polynomial consistency check only for minimal dm
df52508Further improvements to splitting_field()
c50eb3eNo need to specify caller_name in verbose()
6df69b6Add comments, small cosmetic changes

comment:17 Changed 8 months ago by git

  • Commit changed from 387216c0e072a504ba19753570e99ac45378e1b7 to 810ceecec7f6d507c5392fe2f2d00af18778f473

Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:

810ceecImplement division_field() for elliptic curves
776795dDo polynomial consistency check only for minimal dm
df52508Further improvements to splitting_field()
c50eb3eNo need to specify caller_name in verbose()
6df69b6Add comments, small cosmetic changes

comment:18 Changed 8 months ago by jdemeyer

  • Dependencies changed from #2217, #15626 to #2217, #15626, #11271

comment:19 follow-up: Changed 8 months ago by cremona

I know that this is not yet marked as ready for review, but I did look at the code anyway. One minor remark: after adjoining all the x-coordinates of the p-division points, *either* you have the full division field already, i.e. you have all the y-coordinates, *or* you have none, i.e. you have none of the y-coordinates. This could be used, possibly, to simplify that last part of the division field code. But it is not clear to me that there is a quicker way of determining that final quadratic extension than picking any of the x-coordinates of a p-division point and solving for y.

comment:20 in reply to: ↑ 19 ; follow-up: Changed 8 months ago by jdemeyer

Replying to cremona:

I know that this is not yet marked as ready for review, but I did look at the code anyway. One minor remark: after adjoining all the x-coordinates of the p-division points, *either* you have the full division field already, i.e. you have all the y-coordinates, *or* you have none, i.e. you have none of the y-coordinates. This could be used, possibly, to simplify that last part of the division field code. But it is not clear to me that there is a quicker way of determining that final quadratic extension than picking any of the x-coordinates of a p-division point and solving for y.

Not that I don't believe you, but do you have a reference for this? At least I could add it as a comment in the code.

comment:21 in reply to: ↑ 20 Changed 8 months ago by cremona

Replying to jdemeyer:

Replying to cremona:

I know that this is not yet marked as ready for review, but I did look at the code anyway. One minor remark: after adjoining all the x-coordinates of the p-division points, *either* you have the full division field already, i.e. you have all the y-coordinates, *or* you have none, i.e. you have none of the y-coordinates. This could be used, possibly, to simplify that last part of the division field code. But it is not clear to me that there is a quicker way of determining that final quadratic extension than picking any of the x-coordinates of a p-division point and solving for y.

Not that I don't believe you, but do you have a reference for this? At least I could add it as a comment in the code.

Proof. For all P in E[p] and all Galois autos sigma (of K-bar over K) we have sigma(P)=+/-P since x(sigma(P))=sigma(x(P))=x(P). Let P1, P2 be a basis for E[p]. For each sigma we have sigma(P1)=+/-P1 and sigma(P2)=+/-P2 and the signs are the *same* otherwise sigma(P1+P2) could not equal either +(P1+P2) or -(P1+P2). So the image of sigma in the mod p Galois representation is either the identity or minus the identity. In the first case, sigma fixes all points in E[p], in the second case it negates all of them. So if the Galois rep is not trivial, its image has order 2 and its kernel cuts out a quadratic extension, say L/K. In the latter case the non-trivial element sigma of Gal(L/K) maps to -1 which means that sigma(P)=-P for *all* P in E[p].

I don't know a reference!

comment:22 Changed 8 months ago by git

  • Commit changed from 810ceecec7f6d507c5392fe2f2d00af18778f473 to 3661e4443e6b11438e5adcc62e9beb66e5092ac2

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3661e44Implement division_field() for elliptic curves
ca46e2bDo polynomial consistency check only for minimal dm
7830eabFurther improvements to splitting_field()

comment:23 Changed 8 months ago by git

  • Commit changed from 3661e4443e6b11438e5adcc62e9beb66e5092ac2 to 9b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9b406d0Implement division_field() for elliptic curves

comment:24 Changed 8 months ago by git

  • Commit changed from 9b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c to 4d450f1b3438b26c11ee5e6f0fa517f8c9a73042

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4d450f1Implement division_field() for elliptic curves

comment:25 Changed 8 months ago by git

  • Commit changed from 4d450f1b3438b26c11ee5e6f0fa517f8c9a73042 to 8b96090cc593f5906573af49409d7e1c9521aa63

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8b96090Implement division_field() for elliptic curves

comment:26 Changed 8 months ago by git

  • Commit changed from 8b96090cc593f5906573af49409d7e1c9521aa63 to 05c57d2a031f34ac4d95ca5a13448c92206f0f41

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

05c57d2Implement division_field() for elliptic curves

comment:27 Changed 8 months ago by jdemeyer

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

comment:28 Changed 8 months ago by jdemeyer

Note that only 05c57d2 needs to be reviewed.

comment:29 Changed 8 months ago by jdemeyer

  • Description modified (diff)
  • Summary changed from Remove _splitting_field() from elliptic curves to Implement division_field() from elliptic curves

comment:30 Changed 8 months ago by cremona

Looking good! Can we have an example where the X-division field equals the division field, i.e. where the final step is not necessary? And also an example (from the ones you give) showing that the splitting field of the division polynomial has half the degree of the division field? I think that this would be instructive to see in the reference manual. I see that in the code for the final step you again call splitting field with a quadratic; very efficient!

I think it says a lot for the good way in which you implemented splitting fields that this now becomes so simple!

comment:31 Changed 8 months ago by git

  • Commit changed from 05c57d2a031f34ac4d95ca5a13448c92206f0f41 to bb388718023f3eaeec59d97673152996c53f9efb

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

bb38871division_field(): use map_coefficients() and add more examples

comment:32 Changed 8 months ago by cremona

  • Reviewers set to John Cremona
  • Status changed from needs_review to positive_review

I was expecting to be able to pull the new commit on top of the old one, but that failed (merge conflict I think). I just deleted the branch I had and made a new one.

Thanks for the new example, which do exactly what I wanted. I read through the code again, and like it, and tested all of Sage with this commit as well as some of my own examples.

comment:33 Changed 8 months ago by jdemeyer

  • Summary changed from Implement division_field() from elliptic curves to Implement division_field() for elliptic curves

Thanks again for the quick review!

comment:34 Changed 8 months ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.