cardinality_exhaustive incorrect in genus 1

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

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

[chapoton]

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

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

[chapoton]

New commits:

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

[chapoton]

ping ?

[cremona]

OK, I can test now...

[pbruin]

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

[cremona]

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

[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

[chapoton]

done, thanks

[chapoton]

ping ?

[cremona]

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

[git]

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

​e99f57d

trac 19122 do not import legendre

[cremona]

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

[pbruin]

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?

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

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

[pbruin]

Replying to pbruin:

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

This is now #21195.