Opened 11 years ago
Closed 9 years ago
#11905 closed enhancement (fixed)
Implement division_field() for elliptic curves
Reported by:  Jeroen Demeyer  Owned by:  John Cremona 

Priority:  major  Milestone:  sage6.1 
Component:  elliptic curves  Keywords:  
Cc:  John 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 11 years ago by
Dependencies:  → #11891 

comment:2 Changed 11 years ago by
Component:  number fields → elliptic curves 

Dependencies:  #11891 → #11904, #11995, #2217 
Description:  modified (diff) 
Owner:  changed from David Loeffler to John Cremona 
comment:3 Changed 11 years ago by
Summary:  Move _splitting_field from elliptic curves to rings → Remove _splitting_field() from elliptic curves 

comment:4 followup: 7 Changed 11 years ago by
comment:6 Changed 11 years ago by
Description:  modified (diff) 

comment:7 Changed 11 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 11 years ago by
Attachment:  11905_splitting_field.patch added 

comment:8 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:10 Changed 9 years ago by
Authors:  → Jeroen Demeyer 

Description:  modified (diff) 
comment:11 Changed 9 years ago by
Branch:  → u/jdemeyer/ticket/11905 

Modified:  Jan 3, 2014, 5:00:10 PM → Jan 3, 2014, 5:00:10 PM 
comment:12 Changed 9 years ago by
Commit:  → 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 9 years ago by
Dependencies:  #11904, #11995, #2217 → #2217 

comment:14 Changed 9 years ago by
Dependencies:  #2217 → #2217, #15626 

comment:15 Changed 9 years ago by
Commit:  a76a510907abe23c0d1bc188ae8f5fb16b0dfdf6 → 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 9 years ago by
Commit:  d6a7f3cd497cd3ff24241201ef079912dcf41d85 → 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 9 years ago by
Commit:  387216c0e072a504ba19753570e99ac45378e1b7 → 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 9 years ago by
Dependencies:  #2217, #15626 → #2217, #15626, #11271 

comment:19 followup: 20 Changed 9 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 followup: 21 Changed 9 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 Changed 9 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 9 years ago by
Commit:  810ceecec7f6d507c5392fe2f2d00af18778f473 → 3661e4443e6b11438e5adcc62e9beb66e5092ac2 

comment:23 Changed 9 years ago by
Commit:  3661e4443e6b11438e5adcc62e9beb66e5092ac2 → 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 9 years ago by
Commit:  9b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c → 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 9 years ago by
Commit:  4d450f1b3438b26c11ee5e6f0fa517f8c9a73042 → 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 9 years ago by
Commit:  8b96090cc593f5906573af49409d7e1c9521aa63 → 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 9 years ago by
Description:  modified (diff) 

Status:  new → needs_review 
comment:29 Changed 9 years ago by
Description:  modified (diff) 

Summary:  Remove _splitting_field() from elliptic curves → Implement division_field() from elliptic curves 
comment:30 Changed 9 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 9 years ago by
Commit:  05c57d2a031f34ac4d95ca5a13448c92206f0f41 → 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 9 years ago by
Reviewers:  → John Cremona 

Status:  needs_review → 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 9 years ago by
Summary:  Implement division_field() from elliptic curves → Implement division_field() for elliptic curves 

Thanks again for the quick review!
comment:34 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → 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.