Opened 8 years ago
Closed 6 years ago
#11980 closed enhancement (fixed)
Improve naive point counting and implement zeta_function for hyperelliptic curves over finite fields
Reported by:  dkrenn  Owned by:  cremona 

Priority:  major  Milestone:  sage6.3 
Component:  elliptic curves  Keywords:  sd35 hyperelliptic curve sd53 
Cc:  jantuitman, minz, defeo, vbraun  Merged in:  
Authors:  Daniel Krenn, JeanPierre Flori  Reviewers:  Marco Streng, Volker Braun 
Report Upstream:  N/A  Work issues:  
Branch:  c5b2f5d (Commits)  Commit:  c5b2f5d92936577e517f3a871e8f673727f33b10 
Dependencies:  #15148  Stopgaps: 
Description (last modified by )
The following is not implemented (but can be done for hyperelliptic curves):
sage: P.<x> = PolynomialRing(GF(9,'a')) sage: H = HyperellipticCurve(x^5+x^2+1) sage: H.count_points(5) Traceback (most recent call last) ... NotImplementedError: Point counting only implemented for schemes over prime fields
Also, having a count_points
for all cases, the Frobenius polynomial can be calculated. At the moment, this is calculated via frobenius_matrix
, which is not always available:
sage: R.<t> = PolynomialRing(GF(8, 'a')) sage: H = HyperellipticCurve(t^5 + t + 2, t + 1) sage: H.frobenius_polynomial() Traceback (most recent call last): ... NotImplementedError: only implemented for curves y^2 = f(x)
Further, the zeta function can be calculated easily when the Frobenius polynomial is known.
Use git branch.
Attachments (1)
Change History (31)
Changed 8 years ago by
comment:1 Changed 8 years ago by
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Dependencies changed from [http://trac.sagemath.org/sage_trac/ticket/11930 11930] to 11930
comment:3 Changed 8 years ago by
 Dependencies changed from 11930 to #11930
comment:4 Changed 8 years ago by
 Dependencies #11930 deleted
 Status changed from needs_review to needs_work
comment:5 Changed 8 years ago by
 Keywords sd35 hyperelliptic curve added
 Reviewers set to Marco Streng
 Work issues set to correct number of points at infinity, examples for even degree
In case f has even degree, the points at infinity are counted incorrectly by this patch. To get the correct characteristic polynomial of Frobenius, we must consider the smooth model of the curve. This is what you get when you desingularize at infinity. This smooth curve has 0, 1 or 2 points at infinity defined over the base field, so instead of just with 1, the count must start with 0, 1 or 2. (The count will not always agree with the count from the base class, as the base class thinks about the singular curve. See also #11800.)
In case H : y^2 = f(x)
with degree(f) > 2, there are three cases:
 degree(f) is odd: there is a unique point at infinity over the base field (a rational Weierstrass point at infinity)
 degree(f) is even and its leading coefficient is a square: there are two points at infinity defined over the base field
 degree(f) is even and its leading coefficient is not a square: there is no point at infinity defined over the base field (there are two points over a quadratic extension, and they are conjugate to each other)
A similar list of cases can be written down in greater generality (including characteristic 2).
Alternative to get the patch in quickly: raise an error if the curve is not of the form y^2 = f(x)
with f of odd degree > 2.
comment:6 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:7 Changed 7 years ago by
 Dependencies set to #15115
comment:8 Changed 7 years ago by
 Dependencies changed from #15115 to #15115 #15148
 Keywords sd53 added
See also #15148 where we are modifying count_points to actually use hypellfrob. (The ticket is not uptodte, I should be uploading there this afternoon hopefully.)
comment:9 Changed 7 years ago by
Ok, so Ive finished #15148, and after looking at what was I suggested here, I think what has to be done here, on top of #15148:
 we should add the zeta_function method,
 enhance the naive point counting I introduced in #15148 with some ideas from this ticket, namely replace my use of the extension method of finite fields by that of embeddings of a subfield into a super field using the Hom functor and the embedding it computes.
comment:10 Changed 7 years ago by
 Dependencies changed from #15115 #15148 to #15148
comment:11 Changed 7 years ago by
 Branch set to u/jpflori/ticket/11980
 Description modified (diff)
 Status changed from needs_work to needs_review
 Summary changed from hyperelliptic curves: count_points and frobenius_polynomial do not work in all cases, not zeta_function available to Improve naive point counting and implement zeta_function for hyperelliptic curves over finite fields
 Work issues correct number of points at infinity, examples for even degree deleted
comment:12 Changed 7 years ago by
 Commit set to 534116b53fae0aae1919fb4d99ba4cee0ee20c44
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:534116b]  Improve naive point counting and implement zeta_function. 
[changeset:fc7a569]  First bunch of fixes and missing examples. 
[changeset:55cdcf3]  Refactor point counting code for hyperelliptic curves. 
[changeset:86261b1]  Improve count_points 
[changeset:a1f9bec]  Merge remotetracking branch 'origin/build_system' into build_system 
[changeset:4cb7db9]  Merge remotetracking branch 'origin' into build_system 
comment:13 Changed 7 years ago by
 Cc jantuitman added
comment:14 Changed 7 years ago by
 Cc minz added
comment:15 Changed 6 years ago by
 Cc defeo added
comment:16 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:17 Changed 6 years ago by
 Status changed from needs_review to needs_work
There are some failing doctests, see patchbot report.
comment:18 Changed 6 years ago by
Did the patchbot actually managed to use the latest version?
Last time I had a look at it it was stuck with an old comit, anyway, I'll give it a look tomorrow.
comment:19 Changed 6 years ago by
 Commit changed from 534116b53fae0aae1919fb4d99ba4cee0ee20c44 to 4f370fd3bedf021b68470b233806be83cbe12623
Branch pushed to git repo; I updated commit sha1. New commits:
63bf717  Rebase on top of #15108.

08bca28  Merge branch 'ticket/15148' into ticket/11980

c1e4ec7  Merge remotetracking branch 'trac/develop' into ticket/11980

8029bc6  Merge remotetracking branch 'trac/develop' into ticket/15148

824a500  Merge branch 'ticket/15148' into ticket/11980

4f370fd  Merge remotetracking branch 'trac/develop' into ticket/11980

comment:20 Changed 6 years ago by
I've merged the latest #15148 (hint: please review) and latest trac/develop (I don't know if the patchbot can make that alone, especially the former one using the dependencies field). No problem in the schemes directory, I'm running the full long testsuite now.
comment:21 Changed 6 years ago by
I only got one error in ppl.pyx, but I fear it is unrelated.
comment:22 Changed 6 years ago by
And not reproducible...
comment:23 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:24 Changed 6 years ago by
 Cc vbraun added
comment:25 Changed 6 years ago by
 Commit changed from 4f370fd3bedf021b68470b233806be83cbe12623 to 279cdd006f7b4b6e9616fc992339aee7fb960039
Branch pushed to git repo; I updated commit sha1. New commits:
279cdd0  Merge remotetracking branch 'trac/develop' into ticket/11980

comment:26 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:27 Changed 6 years ago by
 Branch changed from u/jpflori/ticket/11980 to public/ticket/11980
 Commit changed from 279cdd006f7b4b6e9616fc992339aee7fb960039 to c5b2f5d92936577e517f3a871e8f673727f33b10
This looks good, as far as I can tell, but I am not competent to check that the new results are mathematically correct. I have made two tiny changes to the doc, and also taken the opportunity to run pyflakes on the changed file. Found three unused variable assignements. Two have been removed, the third one looks very suspect, so I have just added a comment besides it. I have also cleanedup a little bit the code formatting around the suspect variable assignement.
New commits:
317f67f  Merge branch 'u/jpflori/ticket/11980' of ssh://trac.sagemath.org:22/sage into 11980

c5b2f5d  trac #11980 minor doc changes + a little code formatting and pyflakes check

comment:28 Changed 6 years ago by
IIRC there is no deep mathematics introduced here.
Just need to use jacobi symbols to know how many ordinates go with an abscissa (0,1 or 2), the number of points at infinity (as here IIRC we're really computing the number of points on the desingularization of the curve).
The zeta funciton thing is just a very simple toy addition.
comment:29 Changed 6 years ago by
 Reviewers changed from Marco Streng to Marco Streng, Volker Braun
comment:30 Changed 6 years ago by
 Branch changed from public/ticket/11980 to c5b2f5d92936577e517f3a871e8f673727f33b10
 Resolution set to fixed
 Status changed from needs_review to closed
With the changes at #11930 it is no longer necessary to use is_singular, so that test could be removed.