Opened 4 years ago

Closed 3 years ago

#20391 closed defect (fixed)

count_points breaks on even-degree hyperelliptic curves

Reported by: kedlaya Owned by:
Priority: major Milestone: sage-7.5
Component: algebraic geometry Keywords: hyperelliptic curve, number of points
Cc: cremona Merged in:
Authors: Kiran Kedlaya Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: dabfdd8 (Commits) Commit: dabfdd8c05077107b64d4c038fe20f6609f893c3
Dependencies: #18916 Stopgaps:

Description

The following is currently broken:

sage: x = polygen(GF(4099))
sage: H = HyperellipticCurve(x^6 + x + 1)
sage: H.count_points(1)
...
ValueError: Q must be a monic polynomial of odd degree >= 3

The problem is that ultimately this is trying to call hypellfrob, which is only implemented for odd degree polynomials. One can patch around this using either PARI's hyperellcharpoly or the naive point counting code.

In the longer term, some more intelligent switching needs to be implemented for this method, as well as the related zeta_function and zeta_series methods; these do not all optimize the same way. See #965, #16931, #18916, #20309 for related discussions.

Change History (11)

comment:1 Changed 4 years ago by kedlaya

There is a commit on #18916 that addresses this breakage.

comment:2 Changed 4 years ago by kedlaya

  • Dependencies set to #18916

comment:3 Changed 4 years ago by kedlaya

Please close after #18916 is merged.

comment:4 Changed 4 years ago by kedlaya

  • Milestone changed from sage-7.2 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

comment:5 Changed 3 years ago by kedlaya

  • Status changed from needs_review to needs_work

As reported by cremona, this is not completely resolved by #18916 after all. This call syntax should also be covered:

sage: F=GF(23) 
sage: x=polygen(F) 
sage: C=HyperellipticCurve(x^8+1) 
sage: C.cardinality()
... 
ValueError: Q must be a monic polynomial of odd degree >= 3 

comment:6 Changed 3 years ago by kedlaya

  • Cc cremona added
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.5

comment:7 Changed 3 years ago by cremona

Thanks for the update -- I had not noticed this ticket before.

comment:8 Changed 3 years ago by kedlaya

This is ultimately a dispatching issue: the code in #18916 includes some updated decision-making about what algorithm to use, but the cardinality method doesn't currently route through this decision point. This should be easy to fix!

comment:9 Changed 3 years ago by kedlaya

  • Branch set to u/kedlaya/count_points_breaks_on_even-degree_hyperelliptic_curves
  • Commit set to dabfdd8c05077107b64d4c038fe20f6609f893c3
  • Status changed from needs_work to needs_review

Apparently what I did for count_points was the trivial patch: in the even-degree case, just drop down to counting points. This is of course not the correct solution long-term, but it does fix the reported bug. Anyway, I copied that trivial fix over to cardinality.


New commits:

dabfdd8Avoid breakage of cardinality for even-degree curves

comment:10 Changed 3 years ago by jpflori

  • Authors set to Kiran Kedlaya
  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to positive_review

Ok let's go with this at the moment.

comment:11 Changed 3 years ago by vbraun

  • Branch changed from u/kedlaya/count_points_breaks_on_even-degree_hyperelliptic_curves to dabfdd8c05077107b64d4c038fe20f6609f893c3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.