Opened 4 years ago

Closed 3 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) 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 4 years ago by cremona

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.

comment:2 Changed 3 years ago by chapoton

@cremona: what should be done when q is even ?

comment:3 Changed 3 years ago by cremona

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 3 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to public/19122
  • Commit set to 06b321d0e7dd6733075f7e55c6778e83da11dea6
  • Status changed from new to needs_review

New commits:

09b62d5first step
06b321dtrac #19122 correction for exhaustive cardinality of hyperelliptic curves

comment:5 Changed 3 years ago by chapoton

  • Milestone changed from sage-6.9 to sage-7.4

comment:6 Changed 3 years ago by chapoton

ping ?

comment:7 Changed 3 years ago by cremona

OK, I can test now...

comment:8 Changed 3 years ago by pbruin

  • 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 3 years ago by cremona

Thanks Peter. Despite my good intentions other matters intervened...

comment:10 Changed 3 years ago by git

  • Commit changed from 06b321d0e7dd6733075f7e55c6778e83da11dea6 to 7588d791376e069f7faaa63c81fe309d3d324f5e

Branch pushed to git repo; I updated commit sha1. New commits:

5745b13Merge branch 'public/19122' in 7.3
7588d79trac #19122 better check for square leading term

comment:11 Changed 3 years ago by chapoton

  • Status changed from needs_work to needs_review

done, thanks

comment:12 Changed 3 years ago by chapoton

ping ?

comment:13 Changed 3 years ago by cremona

I am literally making the branch now. Meanwhile, there is no no need to import lefendre_symbol...

comment:14 Changed 3 years ago by git

  • Commit changed from 7588d791376e069f7faaa63c81fe309d3d324f5e to e99f57ded539e2c9bd4a5f0e5d71b5b4f383022c

Branch pushed to git repo; I updated commit sha1. New commits:

e99f57dtrac 19122 do not import legendre

comment:15 Changed 3 years ago by cremona

  • 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 3 years ago by cremona

  • Reviewers set to John Cremona

comment:17 Changed 3 years ago by pbruin

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: Changed 3 years ago by 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).

comment:19 in reply to: ↑ 18 ; follow-up: Changed 3 years ago by pbruin

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 3 years ago by pbruin

Replying to pbruin:

I will open a new ticket to treat the case h != 0.

This is now #21195.

comment:21 Changed 3 years ago by vbraun

  • Branch changed from public/19122 to e99f57ded539e2c9bd4a5f0e5d71b5b4f383022c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.