Sage: Ticket #11800: Problem with points at infinity in hyperelliptic curves
https://trac.sagemath.org/ticket/11800
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
Apply
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11800/trac_11800_allow_conics.patch" title="Attachment 'trac_11800_allow_conics.patch' in Ticket #11800">trac_11800_allow_conics.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11800/trac_11800_allow_conics.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11800/11800-reviewer.patch" title="Attachment '11800-reviewer.patch' in Ticket #11800">11800-reviewer.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11800/11800-reviewer.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11800
Trac 1.1.6leifWed, 14 Sep 2011 17:32:42 GMT
https://trac.sagemath.org/ticket/11800#comment:1
https://trac.sagemath.org/ticket/11800#comment:1
<p>
The <em>Author(s)</em> field refers to authors of attached code, e.g. patches fixing a bug, not (necessarily the same as) those who opened a ticket.
</p>
<p>
In short, if there's no code, the <em>Author(s)</em> field should be empty.
</p>
TicketzimmermaThu, 15 Sep 2011 10:00:43 GMTauthor deleted
https://trac.sagemath.org/ticket/11800#comment:2
https://trac.sagemath.org/ticket/11800#comment:2
<ul>
<li><strong>author</strong>
<em>Pierrick Gaudry, Paul Zimmermann</em> deleted
</li>
</ul>
TicketzimmermaFri, 16 Sep 2011 12:33:24 GMTkeywords set
https://trac.sagemath.org/ticket/11800#comment:3
https://trac.sagemath.org/ticket/11800#comment:3
<ul>
<li><strong>keywords</strong>
<em>ecc2011</em> added
</li>
</ul>
TicketnestibalFri, 16 Sep 2011 12:56:48 GMTcc set
https://trac.sagemath.org/ticket/11800#comment:4
https://trac.sagemath.org/ticket/11800#comment:4
<ul>
<li><strong>cc</strong>
<em>nestibal</em> added
</li>
</ul>
TicketdavideklundSat, 17 Dec 2011 12:46:27 GMTattachment set
https://trac.sagemath.org/ticket/11800
https://trac.sagemath.org/ticket/11800
<ul>
<li><strong>attachment</strong>
set to <em>trac_11800_ban_degree_two.patch</em>
</li>
</ul>
<p>
The patch bans defining polynomials of degree two for hyperelliptic curves, and corrects two typos.
</p>
TicketdavideklundSat, 17 Dec 2011 12:59:27 GMTstatus changed; author set
https://trac.sagemath.org/ticket/11800#comment:5
https://trac.sagemath.org/ticket/11800#comment:5
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>David Eklund</em>
</li>
</ul>
<p>
The problem arises exactly when <code>F=y^2+h*y-f</code> 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 <code>y^2+h*y-f</code> 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 <a class="missing wiki">TypeError?</a> when <code>h=0</code> and <code>f=x+1</code>.
</p>
<p>
As far as I can tell, it is not checked at the moment whether the curve defined by <code>y^2+h*y-f</code> has any singularities away from infinity, or whether it is irreducible or reduced.
</p>
TicketmstrengSun, 18 Dec 2011 22:05:07 GMTcc changed
https://trac.sagemath.org/ticket/11800#comment:6
https://trac.sagemath.org/ticket/11800#comment:6
<ul>
<li><strong>cc</strong>
<em>mstreng</em> added
</li>
</ul>
TicketmstrengSun, 18 Dec 2011 22:09:11 GMTcc changed; dependencies, work_issues set
https://trac.sagemath.org/ticket/11800#comment:7
https://trac.sagemath.org/ticket/11800#comment:7
<ul>
<li><strong>cc</strong>
<em>mstreng</em> removed
</li>
<li><strong>dependencies</strong>
set to <em>#11930</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase</em>
</li>
</ul>
<p>
A big rewrite of the hyperelliptic curve constructor has happened at <a class="closed ticket" href="https://trac.sagemath.org/ticket/11930" title="defect: disallow non-smooth hyperelliptic curves, and let hyperelliptic curves ... (closed: fixed)">#11930</a> and is not completely compatible with the patch here. It is easy to rebase the current patch to apply after <a class="closed ticket" href="https://trac.sagemath.org/ticket/11930" title="defect: disallow non-smooth hyperelliptic curves, and let hyperelliptic curves ... (closed: fixed)">#11930</a>, but not the other way around. I'll upload a rebase.
</p>
TicketmstrengSun, 18 Dec 2011 22:09:35 GMTattachment set
https://trac.sagemath.org/ticket/11800
https://trac.sagemath.org/ticket/11800
<ul>
<li><strong>attachment</strong>
set to <em>11800.patch</em>
</li>
</ul>
<p>
rebase to apply after <a class="closed ticket" href="https://trac.sagemath.org/ticket/11930" title="defect: disallow non-smooth hyperelliptic curves, and let hyperelliptic curves ... (closed: fixed)">#11930</a>
</p>
TicketmstrengSun, 18 Dec 2011 22:10:48 GMTdescription changed; work_issues deleted
https://trac.sagemath.org/ticket/11800#comment:8
https://trac.sagemath.org/ticket/11800#comment:8
<ul>
<li><strong>work_issues</strong>
<em>rebase</em> deleted
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11800?action=diff&version=8">diff</a>)
</li>
</ul>
<p>
apply <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11800/11800.patch" title="Attachment '11800.patch' in Ticket #11800">attachment:11800.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11800/11800.patch" title="Download"></a>
</p>
TicketmstrengSun, 18 Dec 2011 22:12:13 GMTkeywords changed
https://trac.sagemath.org/ticket/11800#comment:9
https://trac.sagemath.org/ticket/11800#comment:9
<ul>
<li><strong>keywords</strong>
<em>sd35</em> <em>hyperelliptic</em> <em>curve</em> <em>conic</em> added
</li>
</ul>
TicketmstrengSun, 18 Dec 2011 23:10:05 GMTstatus changed
https://trac.sagemath.org/ticket/11800#comment:10
https://trac.sagemath.org/ticket/11800#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
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 <a class="missing wiki">HyperelllipticCurve?</a> classes for lower-genus curves. For example, a user may have some loop going on where curves sometimes have genus 0, but sometimes higher.
</p>
<p>
The point <code>(0:1:0)</code> 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.
</p>
<p>
Rather than disallowing conics, we could make a separate case in the <code>points</code> function instead.
</p>
TicketdavideklundMon, 19 Dec 2011 14:27:01 GMT
https://trac.sagemath.org/ticket/11800#comment:11
https://trac.sagemath.org/ticket/11800#comment:11
<p>
Ok thanks, I will watch out for consistency with <a class="closed ticket" href="https://trac.sagemath.org/ticket/11930" title="defect: disallow non-smooth hyperelliptic curves, and let hyperelliptic curves ... (closed: fixed)">#11930</a>.
</p>
<p>
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).
</p>
<p>
The problem when f is of degree 1 and h=0 (or more generally h=constant) stems from issues in the homogenization of <code>y^2+h*y-f</code> in the init method of HyperellipticCurve_generic. I will try to deal with these issues, probably opening a new ticket.
</p>
TicketdavideklundWed, 21 Dec 2011 11:08:16 GMTstatus, description changed
https://trac.sagemath.org/ticket/11800#comment:12
https://trac.sagemath.org/ticket/11800#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11800?action=diff&version=12">diff</a>)
</li>
</ul>
<p>
I changed the description to a simpler example (to include in the documentation) which illustrates the same issue.
</p>
TicketjpfloriThu, 29 Dec 2011 12:14:59 GMTcc changed
https://trac.sagemath.org/ticket/11800#comment:13
https://trac.sagemath.org/ticket/11800#comment:13
<ul>
<li><strong>cc</strong>
<em>jpflori</em> added
</li>
</ul>
TicketmstrengTue, 03 Jan 2012 09:19:41 GMT
https://trac.sagemath.org/ticket/11800#comment:14
https://trac.sagemath.org/ticket/11800#comment:14
<p>
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?
</p>
<ul><li>The affine model in <code>_repr_</code> means no points at infinity.
</li><li>The plane projective model (currently underlying the implementation) is not the natural thing to look at at infinity, it always has one point <code>(0:1:0)</code> at infinity, which is singular (assuming genus > 1).
</li><li>The smooth projective model (the actual hyperelliptic curve) is what you get when you desingularize <code>(0:1:0)</code>. 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?
</li></ul><p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/11980" title="enhancement: Improve naive point counting and implement zeta_function for ... (closed: fixed)">#11980</a>
</p>
TicketmstrengTue, 03 Jan 2012 09:52:44 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/11800#comment:15
https://trac.sagemath.org/ticket/11800#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>reviewer</strong>
set to <em>Marco Streng</em>
</li>
</ul>
<p>
Points at infinity are counted incorrectly for degree 2 by this patch.
</p>
<pre class="wiki">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)
</pre><p>
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.
</p>
<p>
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.
</p>
TicketdavideklundMon, 13 Feb 2012 02:45:03 GMT
https://trac.sagemath.org/ticket/11800#comment:16
https://trac.sagemath.org/ticket/11800#comment:16
<p>
In the present patch, the points() method returns all the rational points on the plane projective model, including those on the line at infinity.
</p>
<p>
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:
</p>
<p>
The approach of Magma is to use weighted projective space which allows one to represent two points at infinity (when the degree of <code>f + h^2/4</code> is even). In this case one gets two points at infinity rather than one (singular when g > 0).
</p>
TicketmstrengMon, 13 Feb 2012 09:40:03 GMT
https://trac.sagemath.org/ticket/11800#comment:17
https://trac.sagemath.org/ticket/11800#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11800#comment:16" title="Comment 16">davideklund</a>:
</p>
<blockquote class="citation">
<p>
The approach of Magma is to use weighted projective space which allows one to represent two points at infinity (when the degree of <code>f + h^2/4</code> is even). In this case one gets two points at infinity rather than one (singular when g > 0).
</p>
</blockquote>
<p>
Yes, this is a standard textbook approach to hyperelliptic curves. It is requested in the documentation of <a href="http://www.sagemath.org/doc/reference/sage/schemes/generic/algebraic_scheme.html#sage.schemes.generic.algebraic_scheme.AlgebraicScheme_subscheme.rational_points">rational_points</a> 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 <code>WeightedProjectiveSpace</code>) would be a first step.
</p>
<p>
Anyway, your patch looks good. I'll test it now.
</p>
TicketmstrengMon, 13 Feb 2012 10:18:37 GMT
https://trac.sagemath.org/ticket/11800#comment:18
https://trac.sagemath.org/ticket/11800#comment:18
<p>
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?
</p>
<p>
"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.
</p>
<p>
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.
</p>
TicketdavideklundSat, 25 Feb 2012 19:28:25 GMT
https://trac.sagemath.org/ticket/11800#comment:19
https://trac.sagemath.org/ticket/11800#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11800#comment:18" title="Comment 18">mstreng</a>:
</p>
<blockquote class="citation">
<p>
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?
</p>
<p>
"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.
</p>
<p>
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.
</p>
</blockquote>
<p>
Thank you for your comments! I hoped to attend to this earlier. I think I will get some time to work on it soon.
</p>
<p>
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.
</p>
TicketdavideklundSat, 17 Mar 2012 01:16:40 GMTattachment set
https://trac.sagemath.org/ticket/11800
https://trac.sagemath.org/ticket/11800
<ul>
<li><strong>attachment</strong>
set to <em>trac_11800_allow_conics.patch</em>
</li>
</ul>
<p>
Patch updated. More efficient method to find the points at infinity and added documentation.
</p>
TicketdavideklundSat, 17 Mar 2012 01:17:56 GMTstatus changed
https://trac.sagemath.org/ticket/11800#comment:20
https://trac.sagemath.org/ticket/11800#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketmstrengSat, 17 Mar 2012 14:29:36 GMT
https://trac.sagemath.org/ticket/11800#comment:21
https://trac.sagemath.org/ticket/11800#comment:21
<p>
for patchbot:
</p>
<p>
apply trac_11800_allow_conics.patch
</p>
TicketmstrengSat, 17 Mar 2012 20:52:51 GMTattachment set
https://trac.sagemath.org/ticket/11800
https://trac.sagemath.org/ticket/11800
<ul>
<li><strong>attachment</strong>
set to <em>11800-reviewer.patch</em>
</li>
</ul>
<p>
break at 79 characters, shortened polynomial coefficient access
</p>
TicketmstrengSat, 17 Mar 2012 20:57:58 GMTdescription changed; dependencies deleted
https://trac.sagemath.org/ticket/11800#comment:22
https://trac.sagemath.org/ticket/11800#comment:22
<ul>
<li><strong>dependencies</strong>
<em>#11930</em> deleted
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11800?action=diff&version=22">diff</a>)
</li>
</ul>
TicketmstrengSat, 17 Mar 2012 21:08:25 GMT
https://trac.sagemath.org/ticket/11800#comment:23
https://trac.sagemath.org/ticket/11800#comment:23
<p>
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".
</p>
TicketdavideklundSun, 18 Mar 2012 17:36:17 GMTstatus changed
https://trac.sagemath.org/ticket/11800#comment:24
https://trac.sagemath.org/ticket/11800#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11800#comment:23" title="Comment 23">mstreng</a>:
</p>
<blockquote class="citation">
<p>
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".
</p>
</blockquote>
<p>
Ok, thanks! I agree with your changes.
</p>
TicketjdemeyerWed, 28 Mar 2012 10:03:54 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11800#comment:25
https://trac.sagemath.org/ticket/11800#comment:25
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta11</em>
</li>
</ul>
TicketmstrengWed, 28 Aug 2013 12:41:09 GMT
https://trac.sagemath.org/ticket/11800#comment:26
https://trac.sagemath.org/ticket/11800#comment:26
<p>
See <a class="new ticket" href="https://trac.sagemath.org/ticket/15115" title="defect: correct set of points at infinity for hyperelliptic curve (new)">#15115</a> for getting the correct points at infinity in general.
</p>
Ticket