Opened 4 years ago

Closed 3 weeks ago

#20264 closed enhancement (fixed)

Hasse-Weil Zeta function of a cyclic cover of P1 over finite fields.

Reported by: edgarcosta Owned by:
Priority: major Milestone: sage-9.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 edgarcosta)

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 roed

  • Keywords sd87 added

comment:2 Changed 2 years ago by edgarcosta

  • Keywords days88 added

comment:3 Changed 18 months ago by edgarcosta

  • Authors changed from Edgar Costa, Chris Nicholls to Vishal Arul, Edgar Costa, Richard Magner, and Nicholas Triantafillou
  • Cc alexjbest added
  • Dependencies set to #25366
  • Description modified (diff)
  • Milestone changed from sage-7.2 to sage-8.3
  • Summary changed from Hasse-Weil Zeta function of a superelliptic curve over finite fields. to Hasse-Weil Zeta function of a cyclic cover of P1 over finite fields.

comment:4 Changed 18 months ago by edgarcosta

  • Branch set to u/edgarcosta/cycliccovers
  • Commit set to 5706cca0599155736f262d6d8d31ee44f31514b0
  • Status changed from new to needs_info

New commits:

3e1041dwrap ntl_mat_ZZ_p functionality
96e0783wrap harvey's intervalproducts
d91d387merge w/develop
5706ccainitial commit for cyclic covers

comment:5 Changed 18 months ago by git

  • Commit changed from 5706cca0599155736f262d6d8d31ee44f31514b0 to 7b51922af08c4002fc36f565025fcad8955cfe12

Branch pushed to git repo; I updated commit sha1. New commits:

7b51922more examples at the top

comment:6 Changed 18 months ago by edgarcosta

Last edited 18 months ago by edgarcosta (previous) (diff)

comment:7 Changed 18 months ago by edgarcosta

  • Status changed from needs_info to needs_review

comment:8 Changed 18 months ago by edgarcosta

  • Description modified (diff)

comment:9 Changed 16 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:10 Changed 12 months ago by alexjbest

  • Branch changed from u/edgarcosta/cycliccovers to public/zeta-cyclic
  • Commit changed from 7b51922af08c4002fc36f565025fcad8955cfe12 to 30d61b5987424de767facbcd6abd9ed82a5562ef

Last 10 new commits:

7c86227began reviewing zeta functions of cyclic covers
05199c0removed many semicolons
91ddb8esmall fix
e91fb3crename folder
ed9eca9finish move
cdca59ddelete unused function
df1216fmore style fixes last bit of move
c4e7788move check squarefree
c0df121add to main reference
30d61b5more cleanup

comment:11 Changed 12 months ago by alexjbest

  • Milestone changed from sage-8.4 to sage-8.5

comment:12 Changed 11 months ago by edgarcosta

  • Branch changed from public/zeta-cyclic to public/zeta-no-wrap
  • Commit changed from 30d61b5987424de767facbcd6abd9ed82a5562ef to d7a885cb085673a6f7531a765bd0e7405d81b1f4

Last 10 new commits:

9b89e3aremoved many semicolons
2493a73small fix
5a8afa8rename folder
3fb8aa1finish move
e5fe996delete unused function
198943fmore style fixes last bit of move
cd05163move check squarefree
b78a04dadd to main reference
3883347more cleanup
d7a885cfixed lots of docs with edgar

comment:13 Changed 11 months ago by alexjbest

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 edgarcosta

Vishal Arul spotted some bugs.

sage: %time CyclicCover(11, PolynomialRing(GF(1129), 'x')([-1] + [0]*(5-1) + [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 112911. 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]*(5-1) + [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]*(5-1) + [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 edgarcosta

  • Status changed from needs_review to needs_work

comment:16 Changed 5 weeks ago by git

  • Commit changed from d7a885cb085673a6f7531a765bd0e7405d81b1f4 to dd82e8f71a77baad4fb75849fcc4ef25c4c0e3d0

Branch pushed to git repo; I updated commit sha1. New commits:

dd82e8fMerge branch 'public/zeta-no-wrap' of git://trac.sagemath.org/sage into HEAD

comment:17 Changed 5 weeks ago by git

  • Commit changed from dd82e8f71a77baad4fb75849fcc4ef25c4c0e3d0 to b5d81b99edded9b0fbdf64e0e3a8d3c822797090

Branch pushed to git repo; I updated commit sha1. New commits:

b5d81b9fix deprecation, more idiomatic

comment:18 Changed 5 weeks ago by git

  • Commit changed from b5d81b99edded9b0fbdf64e0e3a8d3c822797090 to e2151877e38f5c8ad698ebe26ddb6b48a1928fc1

Branch pushed to git repo; I updated commit sha1. New commits:

f342349Merge branch 'develop' of git://github.com/sagemath/sage into HEAD
b707b2dMerge branch 'develop' of git://github.com/sagemath/sage into HEAD
4a10de1fixing bugs, adding tests, and some whitespace
e215187Merge branch 'public/zeta-no-wrap' of git://trac.sagemath.org/sage into t/20264/zeta

comment:19 Changed 5 weeks ago by edgarcosta

The bugs mentioned before have been fixed

comment:20 follow-up: Changed 4 weeks ago by 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 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

Last edited 4 weeks ago by chapoton (previous) (diff)

comment:21 Changed 4 weeks ago by chapoton

and many more tests should be tagged as #long

the longest one takes too long and should remain # not tested, very long

Last edited 4 weeks ago by chapoton (previous) (diff)

comment:22 Changed 4 weeks ago by chapoton

  • Milestone changed from sage-8.5 to sage-9.0

comment:23 in reply to: ↑ 20 Changed 4 weeks ago by alexjbest

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 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

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 git

  • Commit changed from e2151877e38f5c8ad698ebe26ddb6b48a1928fc1 to 6e76b1200b80b8c59fe4d909739d5009ed92749a

Branch pushed to git repo; I updated commit sha1. New commits:

6e76b12whitespace

comment:25 Changed 4 weeks ago by git

  • Commit changed from 6e76b1200b80b8c59fe4d909739d5009ed92749a to 68185103d8328a40d1b21dc7b803cdd813b62989

Branch pushed to git repo; I updated commit sha1. New commits:

6818510anglais

comment:26 Changed 4 weeks ago by git

  • Commit changed from 68185103d8328a40d1b21dc7b803cdd813b62989 to c541299cd3a8dcb467a746e0c03cbb17fe4a704f

Branch pushed to git repo; I updated commit sha1. New commits:

6f438b9white space
c541299white space

comment:27 Changed 4 weeks ago by chapoton

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 chapoton

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 git

  • Commit changed from c541299cd3a8dcb467a746e0c03cbb17fe4a704f to d773a8c358b01b7cd97546d3daca25f3157a951f

Branch pushed to git repo; I updated commit sha1. New commits:

d773a8cfix long time markers

comment:30 Changed 4 weeks ago by git

  • Commit changed from d773a8c358b01b7cd97546d3daca25f3157a951f to cf148c355ed7a38362193af19cdf7ef44254d4f4

Branch pushed to git repo; I updated commit sha1. New commits:

cf148c3chapotonify

comment:31 Changed 4 weeks ago by alexjbest

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 follow-up: Changed 4 weeks ago by chapoton

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 copy-paste:
    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 re-invent it in "check_squarefree":
    sage: g=(x-1)^2
    sage: g.is_squarefree()
    False
    sage: x = polygen(QQ)
    sage: g=(x-1)^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
    
Last edited 4 weeks ago by chapoton (previous) (diff)

comment:33 Changed 4 weeks ago by git

  • Commit changed from cf148c355ed7a38362193af19cdf7ef44254d4f4 to 6c8bd5debb31c26e9c4d9f4d79a1b139cd63e328

Branch pushed to git repo; I updated commit sha1. New commits:

a274638' ** ' -> '**'
546e7e6__init__ is now empty
3582a15Frobenius and \
b47dcecminor editing
aae5de6Merge branch 'public/zeta-no-wrap' of git://trac.sagemath.org/sage into t/20264/zeta
6c8bd5dMerge branch 'public/zeta-no-wrap' of git://trac.sagemath.org/sage into t/20264/zeta

comment:34 Changed 4 weeks ago by git

  • Commit changed from 6c8bd5debb31c26e9c4d9f4d79a1b139cd63e328 to 7a8e924dec64620f8ee1ba8e7ddabab118431456

Branch pushed to git repo; I updated commit sha1. New commits:

3325fadtypo
464a227removing traces of copy and paste
7a8e924blank lines after IN/OUTPUT:

comment:35 in reply to: ↑ 32 Changed 4 weeks ago by alexjbest

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.


Last edited 4 weeks ago by alexjbest (previous) (diff)

comment:36 Changed 4 weeks ago by git

  • Commit changed from 7a8e924dec64620f8ee1ba8e7ddabab118431456 to 20164bef9a55df704418f825551619c085519ca4

Branch pushed to git repo; I updated commit sha1. New commits:

516d088typo and bad copy and pasta
20164becheck_squarefree

comment:37 Changed 4 weeks ago by edgarcosta

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 --warn-long 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#documentation-strings

Last edited 4 weeks ago by chapoton (previous) (diff)

comment:38 Changed 4 weeks ago by chapoton

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]*(5-1) + [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]*(5-1) + [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 chapoton

There is a line

....:)

that is missing a white space after :

comment:40 Changed 4 weeks ago by git

  • Commit changed from 20164bef9a55df704418f825551619c085519ca4 to c871b103df34dcc7d76d40244b95ab667f4343a9

Branch pushed to git repo; I updated commit sha1. New commits:

e0411bfMerge remote-tracking branch 'origin/develop' into t/20264/zeta
c871b10remove empty line

comment:41 Changed 4 weeks ago by chapoton

  • 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 p-adic 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 q-adic 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

Last edited 4 weeks ago by chapoton (previous) (diff)

comment:42 Changed 4 weeks ago by git

  • Commit changed from c871b103df34dcc7d76d40244b95ab667f4343a9 to e809210909d3398b217c52d58ca94d2cd180be36

Branch pushed to git repo; I updated commit sha1. New commits:

e809210fix doctest

comment:43 Changed 4 weeks ago by alexjbest

  • Component changed from padics to algebraic geometry

comment:44 Changed 4 weeks ago by git

  • Commit changed from e809210909d3398b217c52d58ca94d2cd180be36 to a5d84ac7ec448c939a850f15f564578c012ff542

Branch pushed to git repo; I updated commit sha1. New commits:

a5d84acmore assorted fixes

comment:45 Changed 4 weeks ago by chapoton

You should call the added reference somewhere using [ABCMT2019]_, say in charpoly_frobenius

comment:46 Changed 4 weeks ago by chapoton

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 git

  • Commit changed from a5d84ac7ec448c939a850f15f564578c012ff542 to 7755bb0805df03970c12306d7eceadb007871247

Branch pushed to git repo; I updated commit sha1. New commits:

75b3e46typo import->from
4030d27move __future__ import
b1e0f99tests
20b3d04one more test and a try in charpoly
7755bb0better wording

comment:48 Changed 3 weeks ago by chapoton

+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 git

  • Commit changed from 7755bb0805df03970c12306d7eceadb007871247 to 612fca550e9bef381f5e8b447f71bbe5175a345f

Branch pushed to git repo; I updated commit sha1. New commits:

612fca5formatting references

comment:50 Changed 3 weeks ago by edgarcosta

  • Status changed from needs_work to needs_review

Thank you!

comment:51 Changed 3 weeks ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

my pleasure

comment:52 Changed 3 weeks ago by chapoton

  • Authors changed from Vishal Arul, Edgar Costa, Richard Magner, and Nicholas Triantafillou to Vishal Arul, Edgar Costa, Richard Magner, Nicholas Triantafillou

comment:53 Changed 3 weeks ago by vbraun

  • Branch changed from public/zeta-no-wrap to 612fca550e9bef381f5e8b447f71bbe5175a345f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.