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 )
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)
Change History (49)
comment:1 Changed 8 years ago by
Changed 8 years ago by
comment:2 Changed 8 years ago by
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
comment:4 Changed 8 years ago by
comment:5 Changed 8 years ago by
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
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
- 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
change the constructor of hyperelliptic curve to check if the input makes sense
comment:8 Changed 8 years ago by
- 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
comment:10 Changed 8 years ago by
- 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
comment:11 Changed 8 years ago by
apply 11930b.patch and 11930_is_singular.patch
comment:12 Changed 8 years ago by
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
Oops, sorry, yes. I wrote "True" in 11930_is_singular.patch where it should have been "False".
comment:14 Changed 8 years ago by
- 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
- Cc jpflori added
comment:16 Changed 8 years ago by
- 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
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
- Keywords smooth added
Patch was written on top of 4.8.alpha4. Apply 11930c.patch and 11930_is_singular.patch
comment:19 follow-up: ↓ 20 Changed 8 years ago by
- 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
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
- Cc davideklund added
- Status changed from needs_work to needs_review
comment:22 follow-ups: ↓ 23 ↓ 26 Changed 8 years ago by
- 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: ↓ 24 Changed 8 years ago by
comment:24 in reply to: ↑ 23 Changed 8 years ago by
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)
comment:25 Changed 8 years ago by
- Description modified (diff)
comment:26 in reply to: ↑ 22 ; follow-up: ↓ 27 Changed 8 years ago by
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
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
Apply 11930c.patch and 11930_is_singular2.patch
comment:29 follow-up: ↓ 30 Changed 8 years ago by
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: ↓ 31 Changed 8 years ago by
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
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: ↓ 33 Changed 8 years ago by
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
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
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: ↓ 36 ↓ 38 Changed 8 years ago by
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
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
, whereg
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
, whereh=x^100
andf=x^6+1-h^2/4
(appropriately homogenized withz
) defines a curve in weighted projected spaceP(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
ZZ
". Is this to be interpreted as saying that the example provided is not smooth as a scheme overSpec(ZZ)
?
Yes. But I see that Spec(ZZ) may confuse or scare people, so I will clarify this.
Changed 8 years ago by
replaces 11930c.patch: rebased on top of 5.0.beta14, removed trailing whitespaces, clarified examples
comment:37 Changed 8 years ago by
- 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
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: ↓ 40 Changed 8 years ago by
- 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
Replying to davideklund.
Thanks!
comment:41 Changed 8 years ago by
- Merged in set to sage-5.1.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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.