#11800 closed defect (fixed)
Problem with points at infinity in hyperelliptic curves
Reported by: | gaudry | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.0 |
Component: | algebraic geometry | Keywords: | ecc2011, sd35, hyperelliptic curve, conic |
Cc: | nestibal, jpflori | Merged in: | sage-5.0.beta11 |
Authors: | David Eklund | Reviewers: | Marco Streng |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The function that lists the points on a hyperelliptic curve assumes that the point [0, 1, 0] is always valid. This is wrong and creates the following bug:
sage: R.<x> = GF(7)[] sage: H = HyperellipticCurve(3*x^2 + 5*x + 1) sage: H.points() ... TypeError: Coordinates [0, 1, 0] do not define a point on Hyperelliptic Curve over Finite Field of size 7 defined by y^2 = 3*x^2 + 5*x + 1
Apply
Attachments (4)
Change History (30)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
comment:3 Changed 11 years ago by
- Keywords ecc2011 added
comment:4 Changed 11 years ago by
- Cc nestibal added
Changed 11 years ago by
The patch bans defining polynomials of degree two for hyperelliptic curves, and corrects two typos.
comment:5 Changed 11 years ago by
- Status changed from new to needs_review
The problem arises exactly when F=y^2+h*y-f
has degree 2. But then F defines a conic! Even though the definition of hyperelliptic curve seems to vary (sometimes requiring genus > 1 and sometimes including the genus 1 case) I think that the case where y^2+h*y-f
has degree 2 should raise an error since it is rather confusing to call a rational curve hyperelliptic. Banning this case also seems to get rid of some additional weirdness such as for example the TypeError? when h=0
and f=x+1
.
As far as I can tell, it is not checked at the moment whether the curve defined by y^2+h*y-f
has any singularities away from infinity, or whether it is irreducible or reduced.
comment:6 Changed 11 years ago by
- Cc mstreng added
comment:7 Changed 11 years ago by
- Cc mstreng removed
- Dependencies set to #11930
- Work issues set to rebase
comment:8 Changed 11 years ago by
- Description modified (diff)
- Work issues rebase deleted
apply attachment:11800.patch
comment:9 Changed 11 years ago by
- Keywords sd35 hyperelliptic curve conic added
comment:10 Changed 11 years ago by
- Status changed from needs_review to needs_info
Actually, I don't see any reason to ban conics from being hyperelliptic curves in Sage. Mathematically, I would say that a hyperelliptic curve has genus >= 2, but I don't want to forbid people to use the HyperelllipticCurve? classes for lower-genus curves. For example, a user may have some loop going on where curves sometimes have genus 0, but sometimes higher.
The point (0:1:0)
is not a reason to change things: for genus >=2 it is a singular point that you are not really interested in anyway! Indeed, the 0, 1, or 2 rational points that you get when you resolve that singularity are much more interesting.
Rather than disallowing conics, we could make a separate case in the points
function instead.
comment:11 Changed 11 years ago by
Ok thanks, I will watch out for consistency with #11930.
I will start working on the points method so that it allows conics, that is the case where (0:1:0) does not lie on the curve. This appears to be the better option, since changing the points method seems perfectly safe and banning conics is controversial (at least to some degree).
The problem when f is of degree 1 and h=0 (or more generally h=constant) stems from issues in the homogenization of y^2+h*y-f
in the init method of HyperellipticCurve_generic. I will try to deal with these issues, probably opening a new ticket.
comment:12 Changed 11 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
I changed the description to a simpler example (to include in the documentation) which illustrates the same issue.
comment:13 Changed 11 years ago by
- Cc jpflori added
comment:14 Changed 11 years ago by
Not related to the example in the ticket description or to the patch, but very much related to the title of this ticket and the first line of the description: what is "points" supposed to mean? I assume it means points over the base field, but of which model?
- The affine model in
_repr_
means no points at infinity. - The plane projective model (currently underlying the implementation) is not the natural thing to look at at infinity, it always has one point
(0:1:0)
at infinity, which is singular (assuming genus > 1). - The smooth projective model (the actual hyperelliptic curve) is what you get when you desingularize
(0:1:0)
. It has 0, 1 or 2 points at infinity defined over the base field. Is there a framework in Sage that would make it possible to have 2 point objects representing the different points at infinity?
See #11980
comment:15 Changed 11 years ago by
- Reviewers set to Marco Streng
- Status changed from needs_review to needs_work
Points at infinity are counted incorrectly for degree 2 by this patch.
sage: C = Conic(GF(7), [1, 0, 0, -1, 0, 1]) sage: R.<x> = GF(7)[] sage: H = HyperellipticCurve(x^2+1) sage: C Projective Conic Curve over Finite Field of size 7 defined by x^2 - y^2 + z^2 sage: H Hyperelliptic Curve over Finite Field of size 7 defined by y^2 = x^2 + 1 sage: C.is_smooth() True sage: H.points() [(0 : 6 : 1), (0 : 1 : 1), (1 : 4 : 1), (1 : 3 : 1), (6 : 4 : 1), (6 : 3 : 1)] sage: H([1,1,0]) (1 : 1 : 0) sage: H([1,-1,0]) (6 : 1 : 0)
Here C and H represent the same curve. It is a smooth conic over a finite field of order 7, hence has 8 rational points, but only 6 are found.
In general, if H has degree 2, there are 0 or 2 rational points at infinity (as in my previous comment). Since H has degree < 4, the plane model equals the smooth model, so these points can be represented and returned correctly in Sage.
comment:16 follow-up: ↓ 17 Changed 11 years ago by
In the present patch, the points() method returns all the rational points on the plane projective model, including those on the line at infinity.
I agree that when the projective plane model is singular (the typical case) we really want the points() method to spit out points on a smooth model. Maybe the issue should be raised in a separate ticket. A comment on the matter by David Kohel:
The approach of Magma is to use weighted projective space which allows one to represent two points at infinity (when the degree of f + h^2/4
is even). In this case one gets two points at infinity rather than one (singular when g > 0).
comment:17 in reply to: ↑ 16 Changed 11 years ago by
Replying to davideklund:
The approach of Magma is to use weighted projective space which allows one to represent two points at infinity (when the degree of
f + h^2/4
is even). In this case one gets two points at infinity rather than one (singular when g > 0).
Yes, this is a standard textbook approach to hyperelliptic curves. It is requested in the documentation of rational_points as a way of representing two points at infinity. I don't think weighted projective spaces exist in Sage, so a minimal implementation of weighted projective spaces (like Magma's WeightedProjectiveSpace
) would be a first step.
Anyway, your patch looks good. I'll test it now.
comment:18 follow-up: ↓ 19 Changed 11 years ago by
I see that the new patch isn't set to "needs review" yet, but I'll comment on it anyway: I think some explanation of the situation at infinity is in order in the documentation. How about the following?
"This method currently lists points in the plane projective model, which means that one point (0:1:0) at infinity is returned if the degree of the curve is at least 4. Later implementations may consider the more mathematically correct desingularisation at infinity, replacing (0:1:0) by 0 or 2 smooth rational points if the degree is even." + EXAMPLE of degree 6.
Also, your method of finding points at infinity is linear in the field order, this can be improved by taking (1:y:0) and solving for y (i.e., extracting 1 square root), exactly as currently the affine points are found by taking (x:y:1) for each x and solving for y.
comment:19 in reply to: ↑ 18 Changed 10 years ago by
Replying to mstreng:
I see that the new patch isn't set to "needs review" yet, but I'll comment on it anyway: I think some explanation of the situation at infinity is in order in the documentation. How about the following?
"This method currently lists points in the plane projective model, which means that one point (0:1:0) at infinity is returned if the degree of the curve is at least 4. Later implementations may consider the more mathematically correct desingularisation at infinity, replacing (0:1:0) by 0 or 2 smooth rational points if the degree is even." + EXAMPLE of degree 6.
Also, your method of finding points at infinity is linear in the field order, this can be improved by taking (1:y:0) and solving for y (i.e., extracting 1 square root), exactly as currently the affine points are found by taking (x:y:1) for each x and solving for y.
Thank you for your comments! I hoped to attend to this earlier. I think I will get some time to work on it soon.
Yes, some comment like the one you supply would be in order in the documentation. About the method for finding points: I used brute force since I deliberately choose simple code before efficiency. But I will implement the refined approach you suggest.
Changed 10 years ago by
Patch updated. More efficient method to find the points at infinity and added documentation.
comment:20 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:21 Changed 10 years ago by
for patchbot:
apply trac_11800_allow_conics.patch
comment:22 Changed 10 years ago by
- Dependencies #11930 deleted
- Description modified (diff)
comment:23 follow-up: ↓ 24 Changed 10 years ago by
Python style guides ask for breaking of lines at 79 characters. Aside from that, the patch is good. If you agree with my reviewer patch, then feel free to set the ticket to "positive review".
comment:24 in reply to: ↑ 23 Changed 10 years ago by
- Status changed from needs_review to positive_review
Replying to mstreng:
Python style guides ask for breaking of lines at 79 characters. Aside from that, the patch is good. If you agree with my reviewer patch, then feel free to set the ticket to "positive review".
Ok, thanks! I agree with your changes.
comment:25 Changed 10 years ago by
- Merged in set to sage-5.0.beta11
- Resolution set to fixed
- Status changed from positive_review to closed
comment:26 Changed 9 years ago by
See #15115 for getting the correct points at infinity in general.
The Author(s) field refers to authors of attached code, e.g. patches fixing a bug, not (necessarily the same as) those who opened a ticket.
In short, if there's no code, the Author(s) field should be empty.