Opened 9 years ago
Closed 7 years ago
#11905 closed enhancement (fixed)
Implement division_field() for elliptic curves
Reported by:  jdemeyer  Owned by:  cremona 

Priority:  major  Milestone:  sage6.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, GitHub, GitLab)  Commit:  bb388718023f3eaeec59d97673152996c53f9efb 
Dependencies:  #2217, #15626, #11271  Stopgaps: 
Description (last modified by )
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)
Change History (35)
comment:1 Changed 9 years ago by
 Dependencies set to #11891
comment:2 Changed 9 years ago by
 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 9 years ago by
 Summary changed from Move _splitting_field from elliptic curves to rings to Remove _splitting_field() from elliptic curves
comment:4 followup: ↓ 7 Changed 9 years ago by
comment:5 Changed 9 years ago by
This is still very much work in progress by the way.
comment:6 Changed 9 years ago by
 Description modified (diff)
comment:7 in reply to: ↑ 4 Changed 9 years ago by
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 9 years ago by
comment:8 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:9 Changed 7 years ago by
#2217 is ready for review
comment:10 Changed 7 years ago by
 Description modified (diff)
comment:11 Changed 7 years ago by
 Branch set to u/jdemeyer/ticket/11905
 Modified changed from 01/03/14 17:00:10 to 01/03/14 17:00:10
comment:12 Changed 7 years ago by
 Commit set to a76a510907abe23c0d1bc188ae8f5fb16b0dfdf6
Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:
a76a510  Implement division_field() for elliptic curves

c50eb3e  No need to specify caller_name in verbose()

6df69b6  Add comments, small cosmetic changes

9e2dd44  Make q monic before computing cubic resolvent

9b5558e  Implement splitting fields for number fields

comment:13 Changed 7 years ago by
 Dependencies changed from #11904, #11995, #2217 to #2217
comment:14 Changed 7 years ago by
 Dependencies changed from #2217 to #2217, #15626
comment:15 Changed 7 years ago by
 Commit changed from a76a510907abe23c0d1bc188ae8f5fb16b0dfdf6 to d6a7f3cd497cd3ff24241201ef079912dcf41d85
Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:
d6a7f3c  Implement division_field() for elliptic curves

776795d  Do polynomial consistency check only for minimal dm

df52508  Further improvements to splitting_field()

c50eb3e  No need to specify caller_name in verbose()

6df69b6  Add comments, small cosmetic changes

comment:16 Changed 7 years ago by
 Commit changed from d6a7f3cd497cd3ff24241201ef079912dcf41d85 to 387216c0e072a504ba19753570e99ac45378e1b7
Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:
387216c  Implement division_field() for elliptic curves

776795d  Do polynomial consistency check only for minimal dm

df52508  Further improvements to splitting_field()

c50eb3e  No need to specify caller_name in verbose()

6df69b6  Add comments, small cosmetic changes

comment:17 Changed 7 years ago by
 Commit changed from 387216c0e072a504ba19753570e99ac45378e1b7 to 810ceecec7f6d507c5392fe2f2d00af18778f473
Branch pushed to git repo; I updated commit sha1. This was a forced push. Recent commits:
810ceec  Implement division_field() for elliptic curves

776795d  Do polynomial consistency check only for minimal dm

df52508  Further improvements to splitting_field()

c50eb3e  No need to specify caller_name in verbose()

6df69b6  Add comments, small cosmetic changes

comment:18 Changed 7 years ago by
 Dependencies changed from #2217, #15626 to #2217, #15626, #11271
comment:19 followup: ↓ 20 Changed 7 years ago by
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 xcoordinates of the pdivision points, *either* you have the full division field already, i.e. you have all the ycoordinates, *or* you have none, i.e. you have none of the ycoordinates. 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 xcoordinates of a pdivision point and solving for y.
comment:20 in reply to: ↑ 19 ; followup: ↓ 21 Changed 7 years ago by
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 xcoordinates of the pdivision points, *either* you have the full division field already, i.e. you have all the ycoordinates, *or* you have none, i.e. you have none of the ycoordinates. 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 xcoordinates of a pdivision 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 7 years ago by
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 xcoordinates of the pdivision points, *either* you have the full division field already, i.e. you have all the ycoordinates, *or* you have none, i.e. you have none of the ycoordinates. 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 xcoordinates of a pdivision 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 Kbar 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 nontrivial 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 7 years ago by
 Commit changed from 810ceecec7f6d507c5392fe2f2d00af18778f473 to 3661e4443e6b11438e5adcc62e9beb66e5092ac2
comment:23 Changed 7 years ago by
 Commit changed from 3661e4443e6b11438e5adcc62e9beb66e5092ac2 to 9b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9b406d0  Implement division_field() for elliptic curves

comment:24 Changed 7 years ago by
 Commit changed from 9b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c to 4d450f1b3438b26c11ee5e6f0fa517f8c9a73042
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
4d450f1  Implement division_field() for elliptic curves

comment:25 Changed 7 years ago by
 Commit changed from 4d450f1b3438b26c11ee5e6f0fa517f8c9a73042 to 8b96090cc593f5906573af49409d7e1c9521aa63
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8b96090  Implement division_field() for elliptic curves

comment:26 Changed 7 years ago by
 Commit changed from 8b96090cc593f5906573af49409d7e1c9521aa63 to 05c57d2a031f34ac4d95ca5a13448c92206f0f41
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
05c57d2  Implement division_field() for elliptic curves

comment:27 Changed 7 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:28 Changed 7 years ago by
Note that only 05c57d2 needs to be reviewed.
comment:29 Changed 7 years ago by
 Description modified (diff)
 Summary changed from Remove _splitting_field() from elliptic curves to Implement division_field() from elliptic curves
comment:30 Changed 7 years ago by
Looking good! Can we have an example where the Xdivision 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 7 years ago by
 Commit changed from 05c57d2a031f34ac4d95ca5a13448c92206f0f41 to bb388718023f3eaeec59d97673152996c53f9efb
Branch pushed to git repo; I updated commit sha1. New commits:
bb38871  division_field(): use map_coefficients() and add more examples

comment:32 Changed 7 years ago by
 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 7 years ago by
 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 7 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
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.