Opened 7 years ago
Closed 6 years ago
#19122 closed defect (fixed)
cardinality_exhaustive incorrect in genus 1
Reported by:  dmharvey  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  elliptic curves  Keywords:  
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  e99f57d (Commits, GitHub, GitLab)  Commit:  e99f57ded539e2c9bd4a5f0e5d71b5b4f383022c 
Dependencies:  Stopgaps: 
Description
The cardinality_exhaustive
method can return incorrect results for genus 1 curves if they are given by y^2 = f(x)
where f(x) is a quartic polynomial whose leading coefficient is not a square:
sage: ZZX.<x> = PolynomialRing(ZZ) sage: f = 15*x^4 + 7*x^3 + 3*x^2 + 7*x + 18 sage: HyperellipticCurve(f.change_ring(GF(19))).cardinality_exhaustive(1) 20 sage: sum([legendre_symbol(u, 19) + 1 for u in [f(x) for x in range(19)] + [f[4]]]) # correct answer 19
Here is the offending code:
if g == 1: # elliptic curves always have one smooth point at infinity a += 1
The problem is that for the given model, the curve may not have a rational point at infinity.
Change History (21)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
@cremona: what should be done when q is even ?
comment:3 Changed 6 years ago by
Good question! The reasoning in odd characteristic is this: let f^{* be the reverse polynomial forced to have even degree if deg(f) is odd by adding an extra factor of x. Then the points on y}2=f(x) above x=infinity are the points on y^{2=f}*(x) above x=0. In char 2 this will always be 1.
Conclusion: when q is even always add 1, for all degrees.
comment:4 Changed 6 years ago by
 Branch set to public/19122
 Commit set to 06b321d0e7dd6733075f7e55c6778e83da11dea6
 Status changed from new to needs_review
comment:5 Changed 6 years ago by
 Milestone changed from sage6.9 to sage7.4
comment:6 Changed 6 years ago by
ping ?
comment:7 Changed 6 years ago by
OK, I can test now...
comment:8 Changed 6 years ago by
 Status changed from needs_review to needs_work
The formula involving the Legendre symbol seems to assume that K is a prime field. I guess it can be replaced by
a += 2 if f.leading_coefficient().is_square() else 0
comment:9 Changed 6 years ago by
Thanks Peter. Despite my good intentions other matters intervened...
comment:10 Changed 6 years ago by
 Commit changed from 06b321d0e7dd6733075f7e55c6778e83da11dea6 to 7588d791376e069f7faaa63c81fe309d3d324f5e
comment:12 Changed 6 years ago by
ping ?
comment:13 Changed 6 years ago by
I am literally making the branch now. Meanwhile, there is no no need to import lefendre_symbol...
comment:14 Changed 6 years ago by
 Commit changed from 7588d791376e069f7faaa63c81fe309d3d324f5e to e99f57ded539e2c9bd4a5f0e5d71b5b4f383022c
Branch pushed to git repo; I updated commit sha1. New commits:
e99f57d  trac 19122 do not import legendre

comment:15 Changed 6 years ago by
 Status changed from needs_review to positive_review
Good! I am happy with the code and tests, so positive reivew coming up.
comment:16 Changed 6 years ago by
 Reviewers set to John Cremona
comment:17 Changed 6 years ago by
A general hyperelliptic curve is given by C: y^{2} + h(x)y = f(x); it seems to me that this fix is only correct if h = 0. (Note: in characteristic 2 we cannot have h = 0, otherwise the curve would be singular everywhere.)
Take for example (over any finite field of characteristic not 11)
C: y^2 + y = x^3  x^2 # 11a3, my favourite elliptic curve D: w^2 + z^2*w = z^2 + z
Then C and D are isomorphic via the change of variables
z = 1/x, w = y/x^2
The curve C has two points at x = 0, so D has two points at z = infinity. Now consider
def test_C(p): R.<x> = GF(p)[] C = HyperellipticCurve(x^3  x^2, 1) return C.count_points_exhaustive() def test_D(p): S.<z> = GF(p)[] D = HyperellipticCurve(z^2 + z, z^2) return D.count_points_exhaustive()
Running this for p = 2 and p gives
sage: test_C(2) [5] sage: test_D(2) [4] sage: test_C(3) [5] sage: test_D(3) [3]
whereas all answers should be 5.
Should we fix this on this ticket or open a new one?
comment:18 followup: ↓ 19 Changed 6 years ago by
Do whatever you prefer. I do not use this code and have no intention to start implementing code for hyperelliptic curves in characteristic 2. I was asked a specific question about how many points there are at infinity on a curve of the form y^{2=g(x). }
comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 6 years ago by
Replying to cremona:
Do whatever you prefer. I do not use this code and have no intention to start implementing code for hyperelliptic curves in characteristic 2. I was asked a specific question about how many points there are at infinity on a curve of the form y^{2=g(x). }
Sure, it is clear from your comments that they were only meant for that case. Since this ticket fixes the bug in that case, and has positive review, I will open a new ticket to treat the case h != 0
.
comment:20 in reply to: ↑ 19 Changed 6 years ago by
comment:21 Changed 6 years ago by
 Branch changed from public/19122 to e99f57ded539e2c9bd4a5f0e5d71b5b4f383022c
 Resolution set to fixed
 Status changed from positive_review to closed
I agree. It should add 1 for odd degree and for even degree it should add 1+(a/q) where a is the leading coefficient and q the fields cardinality, assuming that q is odd.