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

Status badges

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^3-2)
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 cremona

What happens is that the code correctly computes the y-coordinate (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 x-coordinate 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 base-change of E from QQ to K and then construct the point on that.

comment:2 Changed 5 years ago by roed

  • Component changed from PLEASE CHANGE to elliptic curves

comment:3 Changed 5 years ago by cremona

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 base-change when it is set to True? This could be misleading since we must distinguish between cases where a base-change is needed to include x, and one where the y-coordinate is in a further extension. So it's really a 3-way 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 base-change would be made to include the y-coordinates. 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 y-coordinates.

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 cremona

  • Authors set to John Cremona
  • 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 base-extension options to the elliptic curve lift_x() method

comment:5 Changed 5 years ago by roed

A couple comments:

  • I think the right condition to check is what you have in the code: that there is a coercion from K to L. But it's not what you describe in the documentation: that x is converted into the base ring. The difference occurs for p-adics 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 follow-up: Changed 5 years ago by cremona

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 base-change 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 x-extension always and let the extend parameter just be True or False and control whether or not to make the quadratic extension to include the y-coordinate 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 y-coordinate 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 follow-up: Changed 5 years ago by 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?

comment:8 Changed 5 years ago by cremona

  • 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 roed

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 ; follow-up: Changed 5 years ago by roed

Replying to cremona:

After more thought I was also wondering whether it would not be simpler to to the x-extension always and let the extend parameter just be True or False and control whether or not to make the quadratic extension to include the y-coordinate 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 y-coordinate exists in the pushout of the base ring and x's parent).

Yeah, I think this would be reasonable. If someone provides an x-coordinate 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 cremona

Replying to roed:

Replying to cremona:

After more thought I was also wondering whether it would not be simpler to to the x-extension always and let the extend parameter just be True or False and control whether or not to make the quadratic extension to include the y-coordinate 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 y-coordinate exists in the pushout of the base ring and x's parent).

Yeah, I think this would be reasonable. If someone provides an x-coordinate 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 git

  • Commit changed from a0cd1923164b95e52fa898c52d520b7ad8c9091e to bcd750e3b3aaaabe3b0a9a9dfd7c242ff42fa74e

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

119f3c1#24091: add pushout to methods attempted when extending x
bcd750e#24091: simplify extend options to True/False for y (always extend to include x), remove pushout code

comment:13 Changed 5 years ago by cremona

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 y-coordinates. 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 git

  • 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 cremona

  • Status changed from needs_work to needs_review

comment:16 Changed 4 years ago by cremona

  • Status changed from needs_review to needs_work

I am working on the 3 broken doctests.

comment:17 Changed 4 years ago by git

  • Commit changed from cb34112e61f481a7e3bc4dc0a8204113524a5250 to d27370265f82a525966ef95b0d71d696b7eb88dc

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

9542496Merge branch 'develop' into 24091
d273702#24091: fixed two doctests

comment:18 Changed 4 years ago by cremona

  • 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 x-coordinate, 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 cremona

OK, patchbot is happy so all I need is a positive review!

comment:20 Changed 4 years ago by roed

  • Reviewers set to David Roe
  • Status changed from needs_review to positive_review

Looks good to me!

comment:21 Changed 4 years ago by vbraun

  • Branch changed from u/cremona/24091 to d27370265f82a525966ef95b0d71d696b7eb88dc
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.