Opened 8 years ago

Closed 8 years ago

#11930 closed defect (fixed)

disallow non-smooth hyperelliptic curves, and let hyperelliptic curves know they are not singular

Reported by: dkrenn Owned by: cremona
Priority: major Milestone: sage-5.1
Component: elliptic curves Keywords: hyperelliptic curve singular smooth sd35
Cc: D.Testa@…, jpflori, davideklund Merged in: sage-5.1.beta2
Authors: Daniel Krenn, Marco Streng, Damiano Testa Reviewers: Marco Streng, Damiano Testa, David Eklund
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mstreng)

Hyperelliptic curves are smooth curves mathematically. These patches add a check for this to the constructor and implement is_singular to always return False

Example

sage: R.<x> = PolynomialRing(GF(3))
sage: H=HyperellipticCurve(x^5+1)
sage: H.is_singular()
# used to return True, now returns False
sage: H.is_smooth()
# used to return False, now returns True
sage: HyperellipticCurve(x^5)
# used to return a curve y^2 = x^5, now raises an error

Apply

Attachments (8)

trac_11930_is_singular_hec.patch (6.2 KB) - added by dkrenn 8 years ago.
11930_singular_hyperelliptic.patch (2.6 KB) - added by mstreng 8 years ago.
change the constructor of hyperelliptic curve to check if the input makes sense
11930b.patch (9.9 KB) - added by mstreng 8 years ago.
new version, fixes doctests
resultant.py (483 bytes) - added by mstreng 8 years ago.
11930c.patch (11.6 KB) - added by mstreng 8 years ago.
disallow non-smooth hyperelliptic curves
11930_is_singular.patch (1.6 KB) - added by mstreng 8 years ago.
is_singular always returns False for hyperelliptic curves
11930_is_singular2.patch (2.5 KB) - added by mstreng 8 years ago.
use this instead of 11930_is_singular.patch
11930d.patch (11.9 KB) - added by mstreng 8 years ago.
replaces 11930c.patch: rebased on top of 5.0.beta14, removed trailing whitespaces, clarified examples

Download all attachments as: .zip

Change History (49)

comment:1 Changed 8 years ago by cremona

This is a good idea. When we implemented the one-line test for nonsingularity of general curves over finite fields last year (after discovering to our surprise that it was not implemented) we did not think of this special case. The generic is_singular() method is defined in sage/schemes/plane_curves/projective_curve.py as a method of class ProjectiveCurve_generic. Your H is of a derived class, so it would be possible to write a different is_singular() method for that subclass.

Changed 8 years ago by dkrenn

comment:2 Changed 8 years ago by dkrenn

  • Status changed from new to needs_review

comment:3 Changed 8 years ago by dkrenn

  • Authors set to dkrenn

comment:4 Changed 8 years ago by dkrenn

  • Authors changed from dkrenn to Daniel Krenn

comment:5 Changed 8 years ago by mstreng

The cause is of course the computationally convenient, but mathematically inaccurate, ambient space. The curve is smooth and projective, but not in P^2:

sage: R.<x> = GF(3)[]
sage: H = HyperellipticCurve(x^5+1)
sage: H.ambient_space()
Projective Space of dimension 2 over Finite Field of size 3

comment:6 Changed 8 years ago by mstreng

There is a much faster way to get the same answer for fields of characteristic not 2:

sage: R.<x> = GF(3)[]
sage: H = HyperellipticCurve(x^5+1)
sage: timeit('H.is_singular()')
125 loops, best of 3: 5.14 ms per loop
sage: timeit('H.hyperelliptic_polynomials()[0].discriminant()!=0')
625 loops, best of 3: 266 µs per loop

comment:7 Changed 8 years ago by mstreng

  • Keywords sd35 added
  • Reviewers set to Marco Streng, Damiano Testa
  • Status changed from needs_review to needs_work
  • Summary changed from function to check if hyperelliptitc curve is singular in the sense of hyperelliptic curves to function to check if hyperelliptic curve is singular in the sense of hyperelliptic curves

Disagreement with Magma, there should still be some condition at infinity for this to be a nice hyperelliptic curve. We are now figuring out what that condition should be.

sage: P.<x> = GF(2)[]
sage: H = HyperellipticCurve(x^6+1, 1)
sage: H.is_singular()
False
sage: magma(H)
TypeError: Error evaluating Magma code.
Runtime error in 'HyperellipticCurve': Curve is singular at infinity

Also, it seems from the code in HyperellipticCurve? that some partial check for singularity is performed there. Should that be a full check or no check at all?

Changed 8 years ago by mstreng

change the constructor of hyperelliptic curve to check if the input makes sense

comment:8 Changed 8 years ago by mstreng

  • Authors changed from Daniel Krenn to Daniel Krenn, Marco Streng, Damiano Testa
  • Description modified (diff)
  • Work issues set to add singular examples to the documentation of the constructor, do some tests

Apply 11930_singular_hyperelliptic.patch and 11930_is_singular.patch

The first of these patches (written by Damiano and I) adds tests to the HyperellipticCurve? constructor. It tests whether the input polynomials f(x) and h(x) really make sense. In other words, it checks if there is some g such that, when f and h are homogenized wrt x to degrees 2g+2 and g+1 respectively, one gets a smooth projective curve. We compared it with the independent implementation in Magma, and the test turns out to be equivalent to Magma's test for all input polynomials over GF(2) and GF(3) where deg(f) is 5 or 6 and deg(h) <= 3.

The second patch is Daniel's function, but with a simpler algorithm that uses the fact that only smooth curves are constructed.

comment:9 Changed 8 years ago by mstreng

See also #11800 and #11980

Changed 8 years ago by mstreng

new version, fixes doctests

comment:10 Changed 8 years ago by mstreng

  • Description modified (diff)
  • Work issues changed from add singular examples to the documentation of the constructor, do some tests to make resultants work for more general fields

Changed 8 years ago by mstreng

comment:11 Changed 8 years ago by mstreng

apply 11930b.patch and 11930_is_singular.patch

comment:12 Changed 8 years ago by zimmerma

Marco, I tried to apply this patch to 4.7.2 (this is needed to check #11800). However the example in the description still fails:

----------------------------------------------------------------------
| Sage Version 4.7.2, Release Date: 2011-10-29                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: 11800
sage: R.<x> = PolynomialRing(GF(3))
sage: H=HyperellipticCurve(x^5+1)
sage: H.is_singular()
True

Paul

comment:13 Changed 8 years ago by mstreng

Oops, sorry, yes. I wrote "True" in 11930_is_singular.patch where it should have been "False".

comment:14 Changed 8 years ago by mstreng

  • Cc D.Testa@… added
  • Work issues changed from make resultants work for more general fields to make resultants work for more general fields or (better) implement gcd for polynomial rings over fields and use that

I can finish this, but not in the next couple of weeks. If anyone wants to work on this, post to this ticket first.

comment:15 Changed 8 years ago by jpflori

  • Cc jpflori added

Changed 8 years ago by mstreng

disallow non-smooth hyperelliptic curves

Changed 8 years ago by mstreng

is_singular always returns False for hyperelliptic curves

comment:16 Changed 8 years ago by mstreng

  • Description modified (diff)
  • Priority changed from minor to major
  • Status changed from needs_work to needs_review
  • Summary changed from function to check if hyperelliptic curve is singular in the sense of hyperelliptic curves to disallow non-smooth hyperelliptic curves, and let hyperelliptic curves know they are not singular
  • Type changed from enhancement to defect
  • Work issues make resultants work for more general fields or (better) implement gcd for polynomial rings over fields and use that deleted

comment:17 Changed 8 years ago by mstreng

To check whether a polynomial has repeated roots, this patch uses both GCDs and resultants. It tries the GCD first, because that is fastest. If that fails, it tries the resultant.

The reason for needing both gcds and resultants is actually quite funny: Qp has no gcd currently implemented in Sage, while extensions of Qp have no resultants in Sage!

With 4.8.alpha4, I get

sage: P.<x> = Qp(5,7)[]
sage: x.gcd(x)
# AttributeError: 'Polynomial_padic_capped_relative_dense' object has no attribute 'gcd'
sage: x.resultant(x)
# 0
sage: K.<a> = Qp(5,7).extension(x^2-5)
sage: P.<x> = K[]
sage: x.gcd(x)
# (1 + O(a^14))*x
sage: x.resultant(x)
# TypeError: no conversion of this ring to a Singular ring defined

comment:18 Changed 8 years ago by mstreng

  • Keywords smooth added

Patch was written on top of 4.8.alpha4. Apply 11930c.patch and 11930_is_singular.patch

comment:19 follow-up: Changed 8 years ago by davidloeffler

  • Status changed from needs_review to needs_work

I'm not happy with this:

 	51	    .. NOTE:: 
 	52	 
 	53	        The words "hyperelliptic curve" are normally only used for curves of 
 	54	        genus at least two, but this class allows more general smooth double 
 	55	        covers of the projective line (conics and elliptic curves), even though 
 	56	        the class is not meant for those and some outputs may be incorrect.

I don't think we can merge this if we know or suspect that it gives incorrect results! We should either raise an error in these cases, or check that the results that are returned are correct.

comment:20 in reply to: ↑ 19 Changed 8 years ago by mstreng

Replying to davidloeffler:

I'm not happy with this:

...

I don't think we can merge this if we know or suspect that it gives incorrect results! We should either raise an error in these cases, or check that the results that are returned are correct.

Hi David,

This "NOTE" is just a warning that we added about the code as it was. It is not about a change that we are making. We decided to leave support for conics and elliptic curves intact, as people may be running a loop over general double covers, or not care too much.

Removing support for conics and elliptic curves would be something for a discussion on sage-nt, and then a new ticket. I can remove this note if you'd like, and leave the rest of the patch as it is. Would that be an improvement?

Marco

comment:21 Changed 8 years ago by mstreng

  • Cc davideklund added
  • Status changed from needs_work to needs_review

comment:22 follow-ups: Changed 8 years ago by davideklund

  • Reviewers changed from Marco Streng, Damiano Testa to Marco Streng, Damiano Testa, David Eklund

I tested this on Sage 4.8.

There is a method is_smooth() which can be applied to a hyperelliptic curve. With the patches applied:

sage: R.<x> = PolynomialRing(GF(3))
sage: H=HyperellipticCurve(x^5+1)
sage: H.is_singular()
False
sage: H.is_smooth()
False

Maybe these two methods should give consistent results. The is_smooth() method seems to be defined in the class AlgebraicScheme_subscheme_projective in algebraic_scheme.py.

comment:23 in reply to: ↑ 22 ; follow-up: Changed 8 years ago by mstreng

Replying to davideklund:

Maybe these two methods should give consistent results.

yes (go ahead)

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

Replying to mstreng:

Replying to davideklund:

Maybe these two methods should give consistent results.

yes (go ahead)

(to elaborate on this: I don't have time now, but yes, it would be good if is_smooth() always returns True for these curves)

Changed 8 years ago by mstreng

use this instead of 11930_is_singular.patch

comment:25 Changed 8 years ago by mstreng

  • Description modified (diff)

comment:26 in reply to: ↑ 22 ; follow-up: Changed 8 years ago by mstreng

Replying to davideklund:

Maybe these two methods should give consistent results.

Thanks, they do now. So the ticket needs review again.

comment:27 in reply to: ↑ 26 Changed 8 years ago by davideklund

Replying to mstreng:

Replying to davideklund:

Maybe these two methods should give consistent results.

Thanks, they do now. So the ticket needs review again.

Ok, nice. I'm on it!

comment:28 Changed 8 years ago by davideklund

Apply 11930c.patch and 11930_is_singular2.patch

comment:29 follow-up: Changed 8 years ago by davideklund

These patches look good. I'll be back in a few days after having looked a bit more on the details.

In the meantime, here is a question/issue: when I apply 11930c.patch using Sage 5.0 (on OS X lion 10.7.3) I get the following:

patching file sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py
Hunk #8 succeeded at 653 with fuzz 1 (offset 95 lines).

I'm not sure what this means or how to get rid off the fuzz.

comment:30 in reply to: ↑ 29 ; follow-up: Changed 8 years ago by mstreng

Replying to davideklund:

I'm not sure what this means or how to get rid off the fuzz.

When applying the patch, mercurial will look for a certain block of code and replace it by another. The code to look for also has three surrounding unchanged lines on each side. Fuzz means that there is a slight mismatch in the surrounding code, due to changes in Sage between after I wrote the patch. More precisely, fuzz n means that a block can only be matched if the outermost n lines of the surrounding code are ignored. I've seen patches be rejected because of fuzz 2, but I think fuzz 1 is fine: there are still 2 lines unchanged around every patched line.

In this particular case, it means that a doctest nearby one of the changed doctests in hyperelliptic_finite_field.py has changed since I wrote the patch.

To get rid of the fuzz, the patch can be rebased (apply to latest version, then qrefresh and export), but I don't think it is necessary with fuzz 1.

comment:31 in reply to: ↑ 30 Changed 8 years ago by davideklund

Replying to mstreng:

Ok. Thank you for that explanation.

Replying to davideklund:

I'm not sure what this means or how to get rid off the fuzz.

When applying the patch, mercurial will look for a certain block of code and replace it by another. The code to look for also has three surrounding unchanged lines on each side. Fuzz means that there is a slight mismatch in the surrounding code, due to changes in Sage between after I wrote the patch. More precisely, fuzz n means that a block can only be matched if the outermost n lines of the surrounding code are ignored. I've seen patches be rejected because of fuzz 2, but I think fuzz 1 is fine: there are still 2 lines unchanged around every patched line.

In this particular case, it means that a doctest nearby one of the changed doctests in hyperelliptic_finite_field.py has changed since I wrote the patch.

To get rid of the fuzz, the patch can be rebased (apply to latest version, then qrefresh and export), but I don't think it is necessary with fuzz 1.

comment:32 follow-up: Changed 8 years ago by davideklund

Here are two more beginner questions related to these patches:

I have a recurring doc-test failure (Sage 5.0 on Mac OS lion) so I can't really doc-test these patches locally without failures. But I interpret what the patch-bot has done on this ticket as sufficient for a positive review as far as doc-testing goes (it seems that all tests pass). Sounds reasonable?

The patch-bot's blue blob and the "plug-in failed" I believe is only about trailing white space, and therefore harmless. Sounds reasonable?

comment:33 in reply to: ↑ 32 Changed 8 years ago by mstreng

Replying to davideklund:

Here are two more beginner questions related to these patches:

It may be better to ask these in email or on the mailing lists, but I'll just answer them anyway.

I have a recurring doc-test failure (Sage 5.0 on Mac OS lion) so I can't really doc-test these patches locally without failures. But I interpret what the patch-bot has done on this ticket as sufficient for a positive review as far as doc-testing goes (it seems that all tests pass). Sounds reasonable?

I'm not sure whether just using the patchbot is ok. According to the developer's guide, you are supposed to run the tests marked "#long" as well, and I don't see where the patchbot does this.

As for your failing tests, any tests that fail on an unpatched Sage can be safely ignored, they are not due to the patch.

The patch-bot's blue blob and the "plug-in failed" I believe is only about trailing white space, and therefore harmless. Sounds reasonable?

In this particular case, it is ok.

In detail: it seems that many people are very annoyed by trailing whitespaces on non-empty lines (see here), hence don't want any new ones to be introduced. That's probably where the plugin came from in the first place. In any case, I just checked and this patch does not introduce any new trailing whitespaces on non-empty lines. I did change two lines that already had trailing whitespaces, which I didn't notice, so I did not remove them. That's where the plugin warning comes from.

comment:34 Changed 8 years ago by davideklund

All tests pass except one which fails on an unaltered Sage 5.0 (on OS X 10.7.3).

The failure was with "rings/polynomial/pbori.pyx" and the tests are not flagged # long time and so are covered by the tests run by the patchbot on this ticket.

comment:35 follow-ups: Changed 8 years ago by davideklund

This all looks good. If the other reviewers agree, we can change the status to positive review.

I only have two small comments on the patches:

About the example beginning with "A hyperelliptic curve should not be given by polynomials of degree greater than 2g+2, where g is the genus." I'm not sure I understand what this means. The genus of what? It is slightly unclear since I gather that in this example there is no hyperelliptic curve whose genus we could be referring to. Is it the genus of the desingularization of the corresponding plane curve? The way I view this, the equation y^2+hy=f, where h=x^100 and f=x^6+1-h^2/4 (appropriately homogenized with z) defines a curve in weighted projected space P(1,100,1) but that curve is singular at the point (x,y,z)=(1,-1/2,0).

About the example beginning "Input with integer coefficients creates objects with the integers as base ring, but only checks smoothness over QQ, not ZZ". Is this to be interpreted as saying that the example provided is not smooth as a scheme over Spec(ZZ)?

comment:36 in reply to: ↑ 35 Changed 8 years ago by mstreng

Replying to davideklund:

I only have two small comments on the patches:

I don't want the documentation to be confusing, so I'll address your comments and post a new patch.

About the example beginning with "A hyperelliptic curve should not be given by polynomials of degree greater than 2g+2, where g is the genus." I'm not sure I understand what this means. The genus of what? It is slightly unclear since I gather that in this example there is no hyperelliptic curve whose genus we could be referring to. Is it the genus of the desingularization of the corresponding plane curve?

Yes, I will explain that better.

The way I view this, the equation y^2+hy=f, where h=x^100 and f=x^6+1-h^2/4 (appropriately homogenized with z) defines a curve in weighted projected space P(1,100,1) but that curve is singular at the point (x,y,z)=(1,-1/2,0).

Yes, and we should not allow that.

About the example beginning "Input with integer coefficients creates objects with the integers as base ring, but only checks smoothness over QQ, not ZZ". Is this to be interpreted as saying that the example provided is not smooth as a scheme over Spec(ZZ)?

Yes. But I see that Spec(ZZ) may confuse or scare people, so I will clarify this.

Changed 8 years ago by mstreng

replaces 11930c.patch: rebased on top of 5.0.beta14, removed trailing whitespaces, clarified examples

comment:37 Changed 8 years ago by mstreng

  • Description modified (diff)

Here's a diff between the c and d patches, excluding changed line numbers and hashes:

< +    This class also allows curves of genus zero or one, which are stricly
> +    This class also allows curves of genus zero or one, which are strictly
126,127c126,130
< +    A hyperelliptic curve should not be given by polynomials of degree greater
< +    than `2g+2`, where `g` is the genus.::
> +    The input for a (smooth) hyperelliptic curve of genus `g` should not
> +    contain polynomials of degree greater than `2g+2`. In the following
> +    example, the hyperelliptic curve has genus 2 and there exists a model
> +    `y^2 = F` of degree 6, so the model `y^2 + yh = f` of degree 200 is not
> +    allowed.::
137c140
< +        
> +
152c155,157
< +    as base ring, but only checks smoothness over `QQ`, not `ZZ`::
---
> +    as base ring, but only checks smoothness over `\QQ`, not over Spec(`\ZZ`).
> +    In other words, it is checked that the discriminant is non-zero, but it is
> +    not checked whether the discriminant is a unit in `\ZZ^*`.::
155,156c160,161
< +        sage: HyperellipticCurve(4*x^7+8*x+8)
< +        Hyperelliptic Curve over Integer Ring defined by y^2 = 4*x^7 + 8*x + 8
> +        sage: HyperellipticCurve(3*x^7+6*x+6)
> +        Hyperelliptic Curve over Integer Ring defined by y^2 = 3*x^7 + 6*x + 6
264c269
< +            ValueError: curve is not smooth    
> +            ValueError: curve is not smooth
273c278
< +            raise ValueError, "curve is not smooth"   
> +            raise ValueError, "curve is not smooth"
308c313
<          #checking first that Cartier matrix is not already cached. Since it can be called by either Hasse_Witt or a_number
>          #checking first that Cartier matrix is not already cached. Since

Apply 11930d.patch and then 11930_is_singular2.patch

comment:38 in reply to: ↑ 35 Changed 8 years ago by mstreng

Replying to davideklund:

This all looks good. If the other reviewers agree, we can change the status to positive review.

The other reviewers are the authors of the current version, so you don't need to consult us (we are the ones who set this to "needs review" in the first place). If you agree with the new patch, you can set it to "positive review" yourself.

comment:39 follow-up: Changed 8 years ago by davideklund

  • Status changed from needs_review to positive_review

Nice! Those extra comments in the examples really clarified things (for me at least).

comment:40 in reply to: ↑ 39 Changed 8 years ago by mstreng

Replying to davideklund.

Thanks!

comment:41 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.1.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.