Opened 4 years ago
Closed 3 years ago
#20391 closed defect (fixed)
count_points breaks on evendegree hyperelliptic curves
Reported by:  kedlaya  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  algebraic geometry  Keywords:  hyperelliptic curve, number of points 
Cc:  cremona  Merged in:  
Authors:  Kiran Kedlaya  Reviewers:  JeanPierre 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
comment:2 Changed 4 years ago by
 Dependencies set to #18916
comment:3 Changed 4 years ago by
Please close after #18916 is merged.
comment:4 Changed 4 years ago by
 Milestone changed from sage7.2 to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
comment:5 Changed 3 years ago by
 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
 Cc cremona added
 Milestone changed from sageduplicate/invalid/wontfix to sage7.5
comment:7 Changed 3 years ago by
Thanks for the update  I had not noticed this ticket before.
comment:8 Changed 3 years ago by
This is ultimately a dispatching issue: the code in #18916 includes some updated decisionmaking 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
 Branch set to u/kedlaya/count_points_breaks_on_evendegree_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 evendegree case, just drop down to counting points. This is of course not the correct solution longterm, but it does fix the reported bug. Anyway, I copied that trivial fix over to cardinality
.
New commits:
dabfdd8  Avoid breakage of cardinality for evendegree curves

comment:10 Changed 3 years ago by
 Reviewers set to JeanPierre 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
 Branch changed from u/kedlaya/count_points_breaks_on_evendegree_hyperelliptic_curves to dabfdd8c05077107b64d4c038fe20f6609f893c3
 Resolution set to fixed
 Status changed from positive_review to closed
There is a commit on #18916 that addresses this breakage.