Opened 5 years ago

Closed 4 years ago

# cardinality_exhaustive incorrect in genus 1

Reported by: Owned by: dmharvey major sage-7.4 elliptic curves Frédéric Chapoton John Cremona N/A e99f57d (Commits) e99f57ded539e2c9bd4a5f0e5d71b5b4f383022c

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

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

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

### comment:3 Changed 4 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 4 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:

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

### comment:5 Changed 4 years ago by chapoton

• Milestone changed from sage-6.9 to sage-7.4

ping ?

### comment:7 Changed 4 years ago by cremona

OK, I can test now...

### comment:8 Changed 4 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 4 years ago by cremona

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

### comment:10 Changed 4 years ago by git

• Commit changed from 06b321d0e7dd6733075f7e55c6778e83da11dea6 to 7588d791376e069f7faaa63c81fe309d3d324f5e

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`

### comment:11 Changed 4 years ago by chapoton

• Status changed from needs_work to needs_review

done, thanks

ping ?

### comment:13 Changed 4 years ago by cremona

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

### comment:14 Changed 4 years ago by git

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

• Reviewers set to John Cremona

### comment:17 Changed 4 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)

sage: test_D(2)

sage: test_C(3)

sage: test_D(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 4 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: ↓ 20 Changed 4 years ago by pbruin

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

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