Opened 9 years ago

Closed 8 years ago

Last modified 7 years ago

#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 mstreng)

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)

trac_11800_ban_degree_two.patch (2.1 KB) - added by davideklund 8 years ago.
The patch bans defining polynomials of degree two for hyperelliptic curves, and corrects two typos.
11800.patch (1.6 KB) - added by mstreng 8 years ago.
rebase to apply after #11930
trac_11800_allow_conics.patch (6.5 KB) - added by davideklund 8 years ago.
Patch updated. More efficient method to find the points at infinity and added documentation.
11800-reviewer.patch (6.8 KB) - added by mstreng 8 years ago.
break at 79 characters, shortened polynomial coefficient access

Download all attachments as: .zip

Change History (30)

comment:1 Changed 9 years ago by leif

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.

comment:2 Changed 9 years ago by zimmerma

  • Authors Pierrick Gaudry, Paul Zimmermann deleted

comment:3 Changed 9 years ago by zimmerma

  • Keywords ecc2011 added

comment:4 Changed 9 years ago by nestibal

  • Cc nestibal added

Changed 8 years ago by davideklund

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

comment:5 Changed 8 years ago by davideklund

  • Authors set to David Eklund
  • 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 8 years ago by mstreng

  • Cc mstreng added

comment:7 Changed 8 years ago by mstreng

  • Cc mstreng removed
  • Dependencies set to #11930
  • Work issues set to rebase

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.

Changed 8 years ago by mstreng

rebase to apply after #11930

comment:8 Changed 8 years ago by mstreng

  • Description modified (diff)
  • Work issues rebase deleted

comment:9 Changed 8 years ago by mstreng

  • Keywords sd35 hyperelliptic curve conic added

comment:10 Changed 8 years ago by mstreng

  • 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 8 years ago by davideklund

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 8 years ago by davideklund

  • 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 8 years ago by jpflori

  • Cc jpflori added

comment:14 Changed 8 years ago by mstreng

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 8 years ago by mstreng

  • 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: Changed 8 years ago by davideklund

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 8 years ago by mstreng

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: Changed 8 years ago by 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.

comment:19 in reply to: ↑ 18 Changed 8 years ago by davideklund

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 8 years ago by davideklund

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

comment:20 Changed 8 years ago by davideklund

  • Status changed from needs_work to needs_review

comment:21 Changed 8 years ago by mstreng

for patchbot:

apply trac_11800_allow_conics.patch

Changed 8 years ago by mstreng

break at 79 characters, shortened polynomial coefficient access

comment:22 Changed 8 years ago by mstreng

  • Dependencies #11930 deleted
  • Description modified (diff)

comment:23 follow-up: Changed 8 years ago by 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".

comment:24 in reply to: ↑ 23 Changed 8 years ago by davideklund

  • 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 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta11
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:26 Changed 7 years ago by mstreng

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

Note: See TracTickets for help on using tickets.