cardinality_exhaustive incorrect in genus 1

[sagetrac-dmharvey]

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.

Component: elliptic curves

Author: Frédéric Chapoton

Branch/Commit: e99f57d

Reviewer: John Cremona

Issue created by migration from https://trac.sagemath.org/ticket/19122

[JohnCremona]

comment:1

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.

[fchapoton]

comment:2

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

[JohnCremona]

comment:3

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.

[fchapoton]

Commit: 06b321d

[fchapoton]

New commits:

09b62d5	first step
06b321d	trac #19122 correction for exhaustive cardinality of hyperelliptic curves

[fchapoton]

Branch: public/19122

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

comment:6

ping ?

[JohnCremona]

comment:7

OK, I can test now...

[pjbruin]

comment:8

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

[JohnCremona]

comment:9

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

[sagetrac-git]

Changed commit from 06b321d to 7588d79

[sagetrac-git]

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

5745b13	Merge branch 'public/19122' in 7.3
7588d79	trac #19122 better check for square leading term

[fchapoton]

comment:11

done, thanks

[fchapoton]

comment:12

ping ?

[JohnCremona]

comment:13

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

[sagetrac-git]

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

e99f57d

trac 19122 do not import legendre

[sagetrac-git]

Changed commit from 7588d79 to e99f57d

[JohnCremona]

comment:15

Good! I am happy with the code and tests, so positive reivew coming up.

[JohnCremona]

Reviewer: John Cremona

[pjbruin]

comment:17

A general hyperelliptic curve is given by C: y² + 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?

[JohnCremona]

comment:18

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).

[pjbruin]

comment:19

Replying to @JohnCremona:

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.

[pjbruin]

comment:20

Replying to @pjbruin:

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

This is now #21195.

[vbraun]

Changed branch from public/19122 to e99f57d