Opened 5 years ago
Closed 4 years ago
#24091 closed defect (fixed)
Bug in order of points on elliptic curves
Reported by:  cremona  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  elliptic curves  Keywords:  
Cc:  Merged in:  
Authors:  John Cremona  Reviewers:  David Roe 
Report Upstream:  N/A  Work issues:  
Branch:  d273702 (Commits, GitHub, GitLab)  Commit:  d27370265f82a525966ef95b0d71d696b7eb88dc 
Dependencies:  Stopgaps: 
Description
In this example we construct a point of order 2 which thinks its order is infinity:
sage: E = EllipticCurve([0,0,0,0,2]) sage: E.torsion_order() 1 sage: K.<a> = NumberField(x^32) sage: P = E.lift_x(a) sage: P.order() +Infinity sage: 2*P (0 : 1 : 0)
It's fine if we construct the point differently:
sage: EK = E.change_ring(K) sage: P = EK([a,0]) sage: P.order() 2
and arises since in the first construction P.curve() is the curve over QQ, not the extension. Hence the error is in the lift_x() function. Which means that it is probably my fault since I think I wrote that.
Change History (21)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
 Component changed from PLEASE CHANGE to elliptic curves
comment:3 Changed 5 years ago by
I can easily fix this by adding lines of the form
K = self.base_ring() try: x = K(x) except TypeError: raise TypeError('x must be coercible into the base ring of the curve')
but then 2 tests fail since the tests include a couple where the x supplied is in an extension of the base field. However these examples, such as
sage: E = EllipticCurve('37a'); sage: P = E.lift_x(pAdicField(17, 5)(6))
are bad since the resulting point has the wrong parent:
sage: P.parent() Abelian group of points on Elliptic Curve defined by y^2 + y = x^3  x over Rational Field
A good way to fix this would be to allow the user to give an x which lies in some extension, tested by checking (if the x=K(x) fails) that E1 = E.change_ring(x.parent()) works and if so running lift_x() there, giving the same point as before but with the correct parent. Note that the problem arises in the first place since the point returned is constructed with check=False.
If this is deemed to be useful (as I think it is), should we make it automatic, or require an additional parameter extend=False and only do the basechange when it is set to True? This could be misleading since we must distinguish between cases where a basechange is needed to include x, and one where the ycoordinate is in a further extension. So it's really a 3way division: extend=False could result in failure unless both the given x and the computed y are in the original base_ring K; extend='x' allows any x with parent L such that self.change_ring(L) is possible and returns a point over L provided that the y coordinate is also in L; and extend='xy' would be like extend='x' except that a further basechange would be made to include the ycoordinates. Actually there's a 4th case extend='y' where we require x in the base ring but will make a quadratic extension if necessary to include the ycoordinates.
I am beginning to think that we should leave the lift_x() as it is (with the stricter test that x=K(x) works, and removing the two subsequently failing tests) and add a new method with these 4 options.
Comments?
comment:4 Changed 5 years ago by
 Branch set to u/cremona/24091
 Commit set to a0cd1923164b95e52fa898c52d520b7ad8c9091e
 Status changed from new to needs_review
Fixed the bug and added all the optional extension possibilities described above, with more examples.
New commits:
a0cd192  #24091 fix the bug and add several baseextension options to the elliptic curve lift_x() method

comment:5 Changed 5 years ago by
A couple comments:
 I think the right condition to check is what you have in the code: that there is a coercion from
K
toL
. But it's not what you describe in the documentation: thatx
is converted into the base ring. The difference occurs for padics for example:
sage: a = Qp(5)(82748127); a 2 + 2*5^4 + 4*5^5 + 4*5^7 + 5^8 + 2*5^9 + 3*5^10 + 5^11 + O(5^20) sage: QQ(a) 639974/5762513
 When there is an extension, the right ring should probably be the pushout of the parent of
x
and the base ring of the curve.
Otherwise, I'm pretty happy with these changes.
comment:6 followup: ↓ 10 Changed 5 years ago by
Thanks for looking at this. I can correct the docstring.
I did think of pushouts but decided that was overkill, though at present this fails:
sage: E = EllipticCurve([0,0,0,0,2]) sage: x = polygen(ZZ) sage: E.lift_x(x, extend='xy') ... TypeError: Unable to basechange from Rational Field to Univariate Polynomial Ring in x over Integer Ring
After more thought I was also wondering whether it would not be simpler to to the xextension always and let the extend parameter just be True or False and control whether or not to make the quadratic extension to include the ycoordinate where necessary. That way you could give any reasonable x with no additional stuff and get a point defined over an extension (assuming that the ycoordinate exists in the pushout of the base ring and x's parent).
I'll try out the pushout idea anyway, making sure that everything still works, only using the pushout construction when sef.base_ring() and x.parent() are different.
comment:7 followup: ↓ 9 Changed 5 years ago by
Using pushout is not so great. If you take the pushout of two real quadratic number fields it returns Algebraic Real Field but with no coercion from the two fields into it. Firstly I was expecting the pushout to be another number field, and secondly I thought th whole point of pushouts was that there would be maps from the constituents into it?
comment:8 Changed 5 years ago by
 Status changed from needs_review to needs_work
I had only tested the one file but clearly need to do more.
comment:9 in reply to: ↑ 7 Changed 5 years ago by
Replying to cremona:
Using pushout is not so great. If you take the pushout of two real quadratic number fields it returns Algebraic Real Field but with no coercion from the two fields into it. Firstly I was expecting the pushout to be another number field, and secondly I thought th whole point of pushouts was that there would be maps from the constituents into it?
Yeah, that sounds like a problem with pushout. I don't think it's unreasonable for the pushout to be Algebraic Real Field, since in general there's not a canonical choice for the number field and we don't have general tensor products of number fields. There should be coercions, but I can also see why it would be hard in this case. Each number field can only have one embedding, and adding coercion maps to Algebraic Real Field will be tricky. Maybe real quadratic fields could be special cased, since there's not really a problem choosing a number field as a pushout....
Anyway, feel free to drop the pushout idea if you like.
comment:10 in reply to: ↑ 6 ; followup: ↓ 11 Changed 5 years ago by
Replying to cremona:
After more thought I was also wondering whether it would not be simpler to to the xextension always and let the extend parameter just be True or False and control whether or not to make the quadratic extension to include the ycoordinate where necessary. That way you could give any reasonable x with no additional stuff and get a point defined over an extension (assuming that the ycoordinate exists in the pushout of the base ring and x's parent).
Yeah, I think this would be reasonable. If someone provides an xcoordinate that's not in the field, there's some chance that they'll have an error somewhere else and will be glad to learn about it. But I think it's more likely that they'd rather have it just work.
comment:11 in reply to: ↑ 10 Changed 5 years ago by
Replying to roed:
Replying to cremona:
After more thought I was also wondering whether it would not be simpler to to the xextension always and let the extend parameter just be True or False and control whether or not to make the quadratic extension to include the ycoordinate where necessary. That way you could give any reasonable x with no additional stuff and get a point defined over an extension (assuming that the ycoordinate exists in the pushout of the base ring and x's parent).
Yeah, I think this would be reasonable. If someone provides an xcoordinate that's not in the field, there's some chance that they'll have an error somewhere else and will be glad to learn about it. But I think it's more likely that they'd rather have it just work.
There are two different use cases really. Interactively we would like things to be simple with helpful defaults, but this method is used in several places in the library where silently changing the point's parent from the original curve is possibly dangerous.
What Magma does is to make the point's parent something like E(L) where L is an extension of the base rather than E itself. For Sage to switch to that philosophy would be a lot of work.
comment:12 Changed 5 years ago by
 Commit changed from a0cd1923164b95e52fa898c52d520b7ad8c9091e to bcd750e3b3aaaabe3b0a9a9dfd7c242ff42fa74e
comment:13 Changed 5 years ago by
The latest version removes pushout stuff (in the previous commit) and simplifies the extend parameter to True/False?, indicating whether or not to make a quadratic extension to include the ycoordinates. Unlike the first commit here, the base will always be extended to include x if there is a coercion from x.parent() into self.base_ring() (unless there is a coercion from x.parent() into the original base ring), with no option needing to be set. This is closer to the old behaviour, but certainly better since the returned point will always be a curve over a base containing the point's coordinates, which was not true before (and was the cause of the bug).
Before setting this to needs review again I'll do more testing since there are minor issues in other places, hopefully noting worse than points being listed in a different order compared with the old code.
comment:14 Changed 5 years ago by
 Commit changed from bcd750e3b3aaaabe3b0a9a9dfd7c242ff42fa74e to cb34112e61f481a7e3bc4dc0a8204113524a5250
Branch pushed to git repo; I updated commit sha1. New commits:
cb34112  #24091 fix formatting bug and a couple of tests where output now trivially different

comment:15 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:16 Changed 4 years ago by
 Status changed from needs_review to needs_work
I am working on the 3 broken doctests.
comment:17 Changed 4 years ago by
 Commit changed from cb34112e61f481a7e3bc4dc0a8204113524a5250 to d27370265f82a525966ef95b0d71d696b7eb88dc
comment:18 Changed 4 years ago by
 Status changed from needs_work to needs_review
2 of the broken doctests were due to E.lift_x(x0) returning the other point with the same xcoordinate, which have been fixed. The 3rd failure reported by a patchbot were timeouts on lines 277 and 279 of src/sage/doctest/external.py which is a patchbot issue nothing to do with this ticket, so I'll put it back to "needs review".
comment:19 Changed 4 years ago by
OK, patchbot is happy so all I need is a positive review!
comment:20 Changed 4 years ago by
 Reviewers set to David Roe
 Status changed from needs_review to positive_review
Looks good to me!
comment:21 Changed 4 years ago by
 Branch changed from u/cremona/24091 to d27370265f82a525966ef95b0d71d696b7eb88dc
 Resolution set to fixed
 Status changed from positive_review to closed
What happens is that the code correctly computes the ycoordinate (in the example it is 0 ) and then constructs the points using self.point(coords, check=False). Switching off the check is to save time testing that the corordinates satisfy the equation of the curve. But we should check that the xcoordinate given lies in the base field of the curve.
In the example it would be better if an error was raised; to construct this point the user should first construct the basechange of E from QQ to K and then construct the point on that.