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: sage-6.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:

Status badges

Description (last modified by Jeroen Demeyer)

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 Jeroen Demeyer 11 years ago.

Download all attachments as: .zip

Change History (35)

comment:1 Changed 11 years ago by Jeroen Demeyer

Dependencies: #11891

comment:2 Changed 11 years ago by Jeroen Demeyer

Component: number fieldselliptic curves
Dependencies: #11891#11904, #11995, #2217
Description: modified (diff)
Owner: changed from David Loeffler to John Cremona

comment:3 Changed 11 years ago by Jeroen Demeyer

Summary: Move _splitting_field from elliptic curves to ringsRemove _splitting_field() from elliptic curves

comment:4 Changed 11 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 11 years ago by Jeroen Demeyer

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

comment:6 Changed 11 years ago by Jeroen Demeyer

Description: modified (diff)

comment:7 in reply to:  4 Changed 11 years ago by Jeroen Demeyer

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 Jeroen Demeyer

Attachment: 11905_splitting_field.patch added

comment:8 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:9 Changed 9 years ago by Frédéric Chapoton

#2217 is ready for review

comment:10 Changed 9 years ago by Jeroen Demeyer

Authors: Jeroen Demeyer
Description: modified (diff)

comment:11 Changed 9 years ago by Jeroen Demeyer

Branch: u/jdemeyer/ticket/11905
Modified: Jan 3, 2014, 5:00:10 PMJan 3, 2014, 5:00:10 PM

comment:12 Changed 9 years ago by git

Commit: 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 9 years ago by Jeroen Demeyer

Dependencies: #11904, #11995, #2217#2217

comment:14 Changed 9 years ago by Jeroen Demeyer

Dependencies: #2217#2217, #15626

comment:15 Changed 9 years ago by git

Commit: a76a510907abe23c0d1bc188ae8f5fb16b0dfdf6d6a7f3cd497cd3ff24241201ef079912dcf41d85

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 9 years ago by git

Commit: d6a7f3cd497cd3ff24241201ef079912dcf41d85387216c0e072a504ba19753570e99ac45378e1b7

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 9 years ago by git

Commit: 387216c0e072a504ba19753570e99ac45378e1b7810ceecec7f6d507c5392fe2f2d00af18778f473

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 9 years ago by Jeroen Demeyer

Dependencies: #2217, #15626#2217, #15626, #11271

comment:19 Changed 9 years ago by John 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 ; Changed 9 years ago by Jeroen Demeyer

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 9 years ago by John 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 9 years ago by git

Commit: 810ceecec7f6d507c5392fe2f2d00af18778f4733661e4443e6b11438e5adcc62e9beb66e5092ac2

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 9 years ago by git

Commit: 3661e4443e6b11438e5adcc62e9beb66e5092ac29b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c

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 9 years ago by git

Commit: 9b406d0b3bb48f8431b6fe0b99116fbaf9a66d7c4d450f1b3438b26c11ee5e6f0fa517f8c9a73042

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 9 years ago by git

Commit: 4d450f1b3438b26c11ee5e6f0fa517f8c9a730428b96090cc593f5906573af49409d7e1c9521aa63

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 9 years ago by git

Commit: 8b96090cc593f5906573af49409d7e1c9521aa6305c57d2a031f34ac4d95ca5a13448c92206f0f41

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 9 years ago by Jeroen Demeyer

Description: modified (diff)
Status: newneeds_review

comment:28 Changed 9 years ago by Jeroen Demeyer

Note that only 05c57d2 needs to be reviewed.

comment:29 Changed 9 years ago by Jeroen Demeyer

Description: modified (diff)
Summary: Remove _splitting_field() from elliptic curvesImplement division_field() from elliptic curves

comment:30 Changed 9 years ago by John 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 9 years ago by git

Commit: 05c57d2a031f34ac4d95ca5a13448c92206f0f41bb388718023f3eaeec59d97673152996c53f9efb

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

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

comment:32 Changed 9 years ago by John Cremona

Reviewers: John Cremona
Status: needs_reviewpositive_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 Jeroen Demeyer

Summary: Implement division_field() from elliptic curvesImplement division_field() for elliptic curves

Thanks again for the quick review!

comment:34 Changed 9 years ago by Volker Braun

Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.