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: | sage-7.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 y2=f(x) above x=infinity are the points on y2=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 sage-6.9 to sage-7.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: y2 + 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 follow-up: ↓ 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 y2=g(x).
comment:19 in reply to: ↑ 18 ; follow-up: ↓ 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 y2=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.