Opened 4 years ago
Closed 3 weeks ago
#20264 closed enhancement (fixed)
HasseWeil Zeta function of a cyclic cover of P1 over finite fields.
Reported by:  edgarcosta  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  algebraic geometry  Keywords:  days71, sd87, days88 
Cc:  alexjbest  Merged in:  
Authors:  Vishal Arul, Edgar Costa, Richard Magner, Nicholas Triantafillou  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  612fca5 (Commits)  Commit:  612fca550e9bef381f5e8b447f71bbe5175a345f 
Dependencies:  #25366  Stopgaps: 
Description (last modified by )
We add a new method to compute the zeta function of a cyclic cover of P^1
, this is the result of a forthcoming paper generalizing the work of Kedlaya, Harvey, Minzlaff and Gonçalves.
In particular, we add two classes for cyclic covers, one over a generic ring and a specialized one over finite fields.
This requires wrapping David Harvey's code for computing products of matrices already in Sage but not accessible to Sage, see #25366
Here is a quick example:
sage: p = 4999; sage: x = PolynomialRing(GF(p),"x").gen(); sage: C = CyclicCover(5, x^5 + 1) sage: C Cyclic Cover of P^1 over Finite Field of size 4999 defined by y^5 = x^5 + 1 sage: C.frobenius_polynomial() x^12 + 29994*x^10 + 374850015*x^8 + 2498500299980*x^6 + 9367502249700015*x^4 + 18731257498500149994*x^2 + 15606259372500374970001 sage: C.genus() 6
Change History (53)
comment:1 Changed 2 years ago by
 Keywords sd87 added
comment:2 Changed 2 years ago by
 Keywords days88 added
comment:3 Changed 18 months ago by
 Cc alexjbest added
 Dependencies set to #25366
 Description modified (diff)
 Milestone changed from sage7.2 to sage8.3
 Summary changed from HasseWeil Zeta function of a superelliptic curve over finite fields. to HasseWeil Zeta function of a cyclic cover of P1 over finite fields.
comment:4 Changed 18 months ago by
 Branch set to u/edgarcosta/cycliccovers
 Commit set to 5706cca0599155736f262d6d8d31ee44f31514b0
 Status changed from new to needs_info
comment:5 Changed 18 months ago by
 Commit changed from 5706cca0599155736f262d6d8d31ee44f31514b0 to 7b51922af08c4002fc36f565025fcad8955cfe12
Branch pushed to git repo; I updated commit sha1. New commits:
7b51922  more examples at the top

comment:6 Changed 18 months ago by
comment:7 Changed 18 months ago by
 Status changed from needs_info to needs_review
comment:8 Changed 18 months ago by
 Description modified (diff)
comment:9 Changed 16 months ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:10 Changed 12 months ago by
 Branch changed from u/edgarcosta/cycliccovers to public/zetacyclic
 Commit changed from 7b51922af08c4002fc36f565025fcad8955cfe12 to 30d61b5987424de767facbcd6abd9ed82a5562ef
Last 10 new commits:
7c86227  began reviewing zeta functions of cyclic covers

05199c0  removed many semicolons

91ddb8e  small fix

e91fb3c  rename folder

ed9eca9  finish move

cdca59d  delete unused function

df1216f  more style fixes last bit of move

c4e7788  move check squarefree

c0df121  add to main reference

30d61b5  more cleanup

comment:11 Changed 12 months ago by
 Milestone changed from sage8.4 to sage8.5
comment:12 Changed 11 months ago by
 Branch changed from public/zetacyclic to public/zetanowrap
 Commit changed from 30d61b5987424de767facbcd6abd9ed82a5562ef to d7a885cb085673a6f7531a765bd0e7405d81b1f4
Last 10 new commits:
9b89e3a  removed many semicolons

2493a73  small fix

5a8afa8  rename folder

3fb8aa1  finish move

e5fe996  delete unused function

198943f  more style fixes last bit of move

cd05163  move check squarefree

b78a04d  add to main reference

3883347  more cleanup

d7a885c  fixed lots of docs with edgar

comment:13 Changed 11 months ago by
This is looking pretty good now to me, so I intend to mark this as positive review once #25366 is reviewed.
comment:14 Changed 5 months ago by
Vishal Arul spotted some bugs.
sage: %time CyclicCover(11, PolynomialRing(GF(1129), 'x')([1] + [0]*(51) + [1])).frobenius_polynomial() CPU times: user 16.1 s, sys: 124 ms, total: 16.3 s Wall time: 16.5 s x^40 + 7337188909826596*x^30 + 3818873571673594702967652840943135*x^20 + 24687045654725446027864774006541463602997309796*x^10 + 11320844849639649951608809973589776933203136765026963553258401
So the discrepancy is in the t^20
coefficient  Minzlaff's code says it is
20187877911930897108199045855206 = 6 * 1129^10
while the current code says it is
3818873571673594702967652840943135 = 6 * 1129^10 + 1129^11.
the difference is exactly 1129^{11. So it does look like some kind of precision error... }
My bet is that error is either in working precision or the code to lift characteristic polynomial to ZZ
Another bug, that seems to be related with precision when using the slow method
sage: CyclicCover(3, PolynomialRing(GF(1009), 'x')([1] + [0]*(51) + [1])).frobenius_polynomial() x^8 + 266*x^6  1474149*x^4 + 270809546*x^2 + 1036488922561 sage: CyclicCover(3, PolynomialRing(GF(1009**2), 'x')([1] + [0]*(51) + [1])).frobenius_polynomial() x^8 + 1045817316825941*x^7 + 546866930086505850133464526551*x^6 + 190640968494636702312197540239024924597536618*x^5 + 49843906537040069873392691186784704861320520036908736885312*x^4 + 194087947845988228526704383964086734259184677590058*x^3 + 566821515149604163130057985174959967417111*x^2 + 1103577471286158480607964750564981*x + 1074309286591662654798721
It looks like the frobenius polynomial for GF(1009) is correct, but it is not correct for GF(1009**2)
. Comparing with Minzlaff's code, the right frobenius polynomial for GF(1009**2)
should be
x^8 + 532*x^7  2877542*x^6  242628176*x^5 + 4390163797795*x^4  247015136050256*x^3  2982540407204025062*x^2 + 561382189105547134612*x + 1074309286591662654798721
comment:15 Changed 5 months ago by
 Status changed from needs_review to needs_work
comment:16 Changed 5 weeks ago by
 Commit changed from d7a885cb085673a6f7531a765bd0e7405d81b1f4 to dd82e8f71a77baad4fb75849fcc4ef25c4c0e3d0
Branch pushed to git repo; I updated commit sha1. New commits:
dd82e8f  Merge branch 'public/zetanowrap' of git://trac.sagemath.org/sage into HEAD

comment:17 Changed 5 weeks ago by
 Commit changed from dd82e8f71a77baad4fb75849fcc4ef25c4c0e3d0 to b5d81b99edded9b0fbdf64e0e3a8d3c822797090
Branch pushed to git repo; I updated commit sha1. New commits:
b5d81b9  fix deprecation, more idiomatic

comment:18 Changed 5 weeks ago by
 Commit changed from b5d81b99edded9b0fbdf64e0e3a8d3c822797090 to e2151877e38f5c8ad698ebe26ddb6b48a1928fc1
Branch pushed to git repo; I updated commit sha1. New commits:
f342349  Merge branch 'develop' of git://github.com/sagemath/sage into HEAD

b707b2d  Merge branch 'develop' of git://github.com/sagemath/sage into HEAD

4a10de1  fixing bugs, adding tests, and some whitespace

e215187  Merge branch 'public/zetanowrap' of git://trac.sagemath.org/sage into t/20264/zeta

comment:19 Changed 5 weeks ago by
The bugs mentioned before have been fixed
comment:20 followup: ↓ 23 Changed 4 weeks ago by
 Use "Return" and not "Returns" in the first line of documentations ; same for "Computes", etc
 Do not end the lines by
\
when using....:
, they are not needed
 the
\
is also not needed to wrap lines inside the text of an Error, just write something like
raise BeautifulError("all the carrots " "belong to the rabbits")
 Use
https://www.gnu.org/licenses/
in the headers (with https instead of http)
 Capital F to Frobenius in the documentation
 Is the change to
src/sage/schemes/hyperelliptic_curves/hypellfrob.pyx
needed ?
 The file
src/sage/schemes/cyclic_covers/__init__.py
should rather be empty
 src/sage/schemes/cyclic_covers/charpoly_frobenius.py:8: 'sage.matrix.constructor.matrix' imported but unused
 When testing that something mod 2 is not zero, you can write
if k % 2:
ok, enough for the moment
comment:21 Changed 4 weeks ago by
and many more tests should be tagged as #long
the longest one takes too long and should remain # not tested, very long
comment:22 Changed 4 weeks ago by
 Milestone changed from sage8.5 to sage9.0
comment:23 in reply to: ↑ 20 Changed 4 weeks ago by
Replying to chapoton:
 Use "Return" and not "Returns" in the first line of documentations ; same for "Computes", etc
 Do not end the lines by
\
when using....:
, they are not needed
 the
\
is also not needed to wrap lines inside the text of an Error, just write something likeraise BeautifulError("all the carrots " "belong to the rabbits")
 Use
https://www.gnu.org/licenses/
in the headers (with https instead of http)
 Capital F to Frobenius in the documentation
 Is the change to
src/sage/schemes/hyperelliptic_curves/hypellfrob.pyx
needed ?
 The file
src/sage/schemes/cyclic_covers/__init__.py
should rather be empty
 src/sage/schemes/cyclic_covers/charpoly_frobenius.py:8: 'sage.matrix.constructor.matrix' imported but unused
 When testing that something mod 2 is not zero, you can write
if k % 2:
ok, enough for the moment
Most of these are fine and I am happy to do, but I wonder if you know an automatic tool to fix these things, if not perhaps we should make one, it would save time fixing annoying single character changes.
As for k %2
I don't know why I would do that, to save keystrokes? It makes it less readable IMO and doesn't seem to have benefit.
As for the change to src/sage/schemes/hyperelliptic_curves/hypellfrob.pyx
I'm not sure how that appeared there, maybe a merge issue, if they don't break anything I'll remove them I suppose.
comment:24 Changed 4 weeks ago by
 Commit changed from e2151877e38f5c8ad698ebe26ddb6b48a1928fc1 to 6e76b1200b80b8c59fe4d909739d5009ed92749a
Branch pushed to git repo; I updated commit sha1. New commits:
6e76b12  whitespace

comment:25 Changed 4 weeks ago by
 Commit changed from 6e76b1200b80b8c59fe4d909739d5009ed92749a to 68185103d8328a40d1b21dc7b803cdd813b62989
Branch pushed to git repo; I updated commit sha1. New commits:
6818510  anglais

comment:26 Changed 4 weeks ago by
 Commit changed from 68185103d8328a40d1b21dc7b803cdd813b62989 to c541299cd3a8dcb467a746e0c03cbb17fe4a704f
comment:27 Changed 4 weeks ago by
Humm. not sure what you are doing, But I did not suggest anything about white space.
And you can write the Errors on two lines (not 4), exactly as I suggested before.
comment:28 Changed 4 weeks ago by
Usually, one does not put spaces around powers, so x**n
is fine.
If you want to know how you are supposed to write code exactly, you should use pycodestyle to check for pep8 correctness. This is not strongly required.
comment:29 Changed 4 weeks ago by
 Commit changed from c541299cd3a8dcb467a746e0c03cbb17fe4a704f to d773a8c358b01b7cd97546d3daca25f3157a951f
Branch pushed to git repo; I updated commit sha1. New commits:
d773a8c  fix long time markers

comment:30 Changed 4 weeks ago by
 Commit changed from d773a8c358b01b7cd97546d3daca25f3157a951f to cf148c355ed7a38362193af19cdf7ef44254d4f4
Branch pushed to git repo; I updated commit sha1. New commits:
cf148c3  chapotonify

comment:31 Changed 4 weeks ago by
I think we got all your suggestions now, thanks!
I'm still not sure which tests are too long now, sage t
already includes warn long and shows nothing on my laptop, is there a good way to determine this?
comment:32 followup: ↓ 35 Changed 4 weeks ago by
Not so amused by your commit titles, sorry to say. Your code has to meet Sage's standards, that's just the way it goes. I am really trying to help.
More fixes:
 Typo "instegral"
 Is there some reference article, either as preprint or published ? If yes, should be added.
 One spurious empty line here
+ r""" + + Return if this curve is singular or not.
 INPUT: and OUTPUT: must be followed by empty lines
 Typo in the sentence
Return the polynomial of defining the cyclic cover.
: remove "of"
 Remain some traces of copypaste:
Return this HyperellipticCurve over a new base ring R.
and
String representation of hyperelliptic curves.
 you should probably use the existing "is_squarefree" method of polynomials and not reinvent it in "check_squarefree":
sage: g=(x1)^2 sage: g.is_squarefree() False sage: x = polygen(QQ) sage: g=(x1)^2 sage: g.is_squarefree() False sage: x = polygen(Qp(5)) sage: g = x^2 + 5 sage: g.is_squarefree() True sage: x = polygen(GF(2)) sage: g = x^2 + x + 1 sage: g.is_squarefree() True
comment:33 Changed 4 weeks ago by
 Commit changed from cf148c355ed7a38362193af19cdf7ef44254d4f4 to 6c8bd5debb31c26e9c4d9f4d79a1b139cd63e328
Branch pushed to git repo; I updated commit sha1. New commits:
a274638  ' ** ' > '**'

546e7e6  __init__ is now empty

3582a15  Frobenius and \

b47dcec  minor editing

aae5de6  Merge branch 'public/zetanowrap' of git://trac.sagemath.org/sage into t/20264/zeta

6c8bd5d  Merge branch 'public/zetanowrap' of git://trac.sagemath.org/sage into t/20264/zeta

comment:34 Changed 4 weeks ago by
 Commit changed from 6c8bd5debb31c26e9c4d9f4d79a1b139cd63e328 to 7a8e924dec64620f8ee1ba8e7ddabab118431456
comment:35 in reply to: ↑ 32 Changed 4 weeks ago by
Not so amused by your commit titles, sorry to say. Your code has to meet Sage's standards, that's just the way it goes. I am really trying to help.
Sorry that's more me being lazy than making a point! I appreciate the comments.
comment:36 Changed 4 weeks ago by
 Commit changed from 7a8e924dec64620f8ee1ba8e7ddabab118431456 to 20164bef9a55df704418f825551619c085519ca4
comment:37 Changed 4 weeks ago by
Thanks for your comments. I think I have addressed most of your comments, with the exception:
 When testing that something mod 2 is not zero, you can write
if k % 2:
which I disagree with
ok. That would be slightly faster.
 Is there some reference article, either as preprint or published ? If yes, should be added.
as the answer is yes, and I need to figure out how to add the reference properly.
The reference itself should be added in the master reference file:
src/doc/en/reference/references/index.rst
and called in your files somewhere using the usual syntax [Who2019]_
 long tests
How do we determine what is long?
using
./sage bt long warnlong src/sage/schemes/cyclic_covers/
Well, your machine may be too quick. Mine is slow. I will launch this command and report.
I also have an honest question, do you know the reason for not using the 3rd person in the documentation, e.g., return instead of returns? I know it is pep8 stuff, but I am confused about how should I be reading docstrings for this to make sense grammatically, as I always read them as the function F does something...
This is not pep8 stuff, but sage's own decision. The first line of the documentation is supposed to be in imperative mode (like when giving an order) as explained here:
http://doc.sagemath.org/html/en/developer/coding_basics.html#documentationstrings
comment:38 Changed 4 weeks ago by
Here are some timings
sage.schemes.cyclic_covers.cycliccover_finite_field.CyclicCover_finite_field.frobenius_polynomial Warning, slow doctest: CyclicCover(11, PolynomialRing(GF(1129), 'x')([1] + [0]*(51) + [1])).frobenius_polynomial() # long time Test ran for 27.69 s ********************************************************************** File "src/sage/schemes/cyclic_covers/cycliccover_finite_field.py", line 1122, in sage.schemes.cyclic_covers.cycliccover_finite_field.CyclicCover_finite_field.frobenius_polynomial Warning, slow doctest: CyclicCover(3, PolynomialRing(GF(1009^2), 'x')([1] + [0]*(51) + [1])).frobenius_polynomial() # long time Test ran for 135.69 s ********************************************************************** File "src/sage/schemes/cyclic_covers/cycliccover_finite_field.py", line 1131, in sage.schemes.cyclic_covers.cycliccover_finite_field.CyclicCover_finite_field.frobenius_polynomial Warning, slow doctest: C.frobenius_polynomial() Test ran for 26.42 s
I sugggest that at least the worst one become # not tested
comment:39 Changed 4 weeks ago by
There is a line
....:)
that is missing a white space after :
comment:40 Changed 4 weeks ago by
 Commit changed from 20164bef9a55df704418f825551619c085519ca4 to c871b103df34dcc7d76d40244b95ab667f4343a9
comment:41 Changed 4 weeks ago by
 The following
+ min_val = min( + [min([self._Qq(elt).valuation() for elt in row]) for row in F.rows()] + )
could be done in one loop
min_val = min(self._Qq(elt).valuation() for row in F.rows() for elt in row)
 In this
+ Compute padic Frobenius matrix to precision p^N. If N not + supplied, a default value is selected, which is the minimum needed + to recover the charpoly unambiguously.
the first sentence should be followed by an empty line.
 In all.py, do not use assert
 In this sentence
+  ``charpoly_prec``  a vector ai, such that, `frob_matrix.change_ring(ZZ).charpoly()[i]` + will be correct mod `p^ai`, this can be easily deduced from the hodge numbers and + knowing the qadic precision of `frob_matrix`
Hodge take a capital H, and the final frob_matrix should be between double backticks
 You could replace
import sage.schemes.curves.affine_curve as plane_curve
by
from sage.schemes.curves.affine_curve import AffinePlaneCurve
and then use that directly
 In src/sage/schemes/cyclic_covers/charpoly_frobenius.py, there are many divisions by 2. I would suggest to add
from __future__ import division
in order to make sure that the python3 behaviour will remain the same.
 this sentence does not make sense
+  ``f``  univariate polynomial + is not given, then it defaults to 0.
 do not use range(0, something) but range(something)
 still an empty line to be removed here:
+ def _horizontal_matrix_reduction(self, s): + r""" +
 this should not be indented
+ OUTPUT: + + A tuple of tuples ``( (D0, D1), (M0, M1) )`` + where MV_t = M0 + t * M1 and DV_t = D0 + t * D1 +
ok, enough for today
comment:42 Changed 4 weeks ago by
 Commit changed from c871b103df34dcc7d76d40244b95ab667f4343a9 to e809210909d3398b217c52d58ca94d2cd180be36
Branch pushed to git repo; I updated commit sha1. New commits:
e809210  fix doctest

comment:43 Changed 4 weeks ago by
 Component changed from padics to algebraic geometry
comment:44 Changed 4 weeks ago by
 Commit changed from e809210909d3398b217c52d58ca94d2cd180be36 to a5d84ac7ec448c939a850f15f564578c012ff542
Branch pushed to git repo; I updated commit sha1. New commits:
a5d84ac  more assorted fixes

comment:45 Changed 4 weeks ago by
You should call the added reference somewhere using [ABCMT2019]_
, say in charpoly_frobenius
comment:46 Changed 4 weeks ago by
This is wrong
import sage.schemes.curves.affine_curve import AffinePlaneCurve
The first "import" should be "from" instead.
comment:47 Changed 3 weeks ago by
 Commit changed from a5d84ac7ec448c939a850f15f564578c012ff542 to 7755bb0805df03970c12306d7eceadb007871247
comment:48 Changed 3 weeks ago by
+REFERENCES::
should end with a single colon, and be followed by an empty line.
Once done, I will give a positive review, if you set to "needs_review". It is better to make further changes in later tickets.
comment:49 Changed 3 weeks ago by
 Commit changed from 7755bb0805df03970c12306d7eceadb007871247 to 612fca550e9bef381f5e8b447f71bbe5175a345f
Branch pushed to git repo; I updated commit sha1. New commits:
612fca5  formatting references

comment:51 Changed 3 weeks ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
my pleasure
comment:52 Changed 3 weeks ago by
comment:53 Changed 3 weeks ago by
 Branch changed from public/zetanowrap to 612fca550e9bef381f5e8b447f71bbe5175a345f
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
wrap ntl_mat_ZZ_p functionality
wrap harvey's intervalproducts
merge w/develop
initial commit for cyclic covers