Problem with points at infinity in hyperelliptic curves

[sagetrac-gaudry]

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

• attachment: trac_11800_allow_conics.patch
• attachment: 11800-reviewer.patch

CC: @sagetrac-nestibal @jpflori

Component: algebraic geometry

Keywords: ecc2011, sd35, hyperelliptic curve, conic

Author: David Eklund

Reviewer: Marco Streng

Merged: sage-5.0.beta11

Issue created by migration from https://trac.sagemath.org/ticket/11800

[nexttime]

comment:1

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.

[zimmermann6]

Changed author from Pierrick Gaudry, Paul Zimmermann to none

[zimmermann6]

Changed keywords from none to ecc2011

[sagetrac-davideklund]

The patch bans defining polynomials of degree two for hyperelliptic curves, and corrects two typos.

[sagetrac-davideklund]

comment:5

Attachment: trac_11800_ban_degree_two.patch.gz

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.

[sagetrac-davideklund]

Author: David Eklund

[mstreng]

Work Issues: rebase

[mstreng]

comment:7

A big rewrite of the hyperelliptic curve constructor has happened at #11930 and is not completely compatible with the patch here. It is easy to rebase the current patch to apply after #11930, but not the other way around. I'll upload a rebase.

[mstreng]

Dependencies: #11930

[mstreng]

Attachment: 11800.patch.gz

rebase to apply after #11930

[mstreng]

comment:8

apply attachment: 11800.patch

[mstreng]

Changed work issues from rebase to none

[mstreng]

Changed keywords from ecc2011 to ecc2011, sd35, hyperelliptic curve, conic

[mstreng]

comment:10

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.

[sagetrac-davideklund]

comment:11

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.

[sagetrac-davideklund]

comment:12

I changed the description to a simpler example (to include in the documentation) which illustrates the same issue.

[mstreng]

comment:14

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

[mstreng]

comment:15

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.

[mstreng]

Reviewer: Marco Streng

[sagetrac-davideklund]

comment:16

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).

[mstreng]

comment:17

Replying to @sagetrac-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.

[mstreng]

comment:18

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.

[sagetrac-davideklund]

comment:19

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.

[sagetrac-davideklund]

Patch updated. More efficient method to find the points at infinity and added documentation.

[sagetrac-davideklund]

comment:20

Attachment: trac_11800_allow_conics.patch.gz

[mstreng]

comment:21

for patchbot:

apply trac_11800_allow_conics.patch

[mstreng]

Attachment: 11800-reviewer.patch.gz

break at 79 characters, shortened polynomial coefficient access

[mstreng]

Changed dependencies from #11930 to none

[mstreng]

comment:23

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".

[sagetrac-davideklund]

comment:24

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.

[jdemeyer]

Merged: sage-5.0.beta11

[mstreng]

comment:26

See #15115 for getting the correct points at infinity in general.