Opened 4 years ago
Closed 18 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)
Change History (35)
comment:1 Changed 4 years ago by jdemeyer
- Dependencies set to #11891
comment:2 Changed 4 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 4 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: ↓ 7 Changed 4 years ago by wuthrich
comment:5 Changed 4 years ago by jdemeyer
This is still very much work in progress by the way.
comment:6 Changed 4 years ago by jdemeyer
- Description modified (diff)
comment:7 in reply to: ↑ 4 Changed 4 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 4 years ago by jdemeyer
comment:8 Changed 23 months ago by jdemeyer
- Milestone changed from sage-5.11 to sage-5.12
comment:9 Changed 20 months ago by chapoton
#2217 is ready for review
comment:10 Changed 18 months ago by jdemeyer
- Description modified (diff)
comment:11 Changed 18 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 18 months ago by git
- 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 18 months ago by jdemeyer
- Dependencies changed from #11904, #11995, #2217 to #2217
comment:14 Changed 18 months ago by jdemeyer
- Dependencies changed from #2217 to #2217, #15626
comment:15 Changed 18 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:
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 18 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:
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 18 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:
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 18 months ago by jdemeyer
- Dependencies changed from #2217, #15626 to #2217, #15626, #11271
comment:19 follow-up: ↓ 20 Changed 18 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: ↓ 21 Changed 18 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 18 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 18 months ago by git
- Commit changed from 810ceecec7f6d507c5392fe2f2d00af18778f473 to 3661e4443e6b11438e5adcc62e9beb66e5092ac2
comment:23 Changed 18 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:
9b406d0 | Implement division_field() for elliptic curves |
comment:24 Changed 18 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:
4d450f1 | Implement division_field() for elliptic curves |
comment:25 Changed 18 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:
8b96090 | Implement division_field() for elliptic curves |
comment:26 Changed 18 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:
05c57d2 | Implement division_field() for elliptic curves |
comment:27 Changed 18 months ago by jdemeyer
- Description modified (diff)
- Status changed from new to needs_review
comment:28 Changed 18 months ago by jdemeyer
Note that only 05c57d2 needs to be reviewed.
comment:29 Changed 18 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 18 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 18 months ago by git
- 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 18 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 18 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 18 months ago by vbraun
- 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.