Added functionality to compute zeta functions of nondegenerate hypersurfaces over finite fields

[2a94e3c6-bd33-45f8-8db1-79636006ea7d]

As part of his Ph.D. thesis, Malcolm Kotok implemented a function to compute zeta functions of nondegenerate hypersurfaces over finite fields, based on a paper of Sperber and Voight. We wish to incorporate this into Sage. For more information see: http://arxiv.org/abs/1112.4881

CC: @sagetrac-malcolmkotok @sagetrac-ursula @kedlaya

Component: number theory

Keywords: zeta, L-function, sd87, sd91

Author: Heidi Goodson, Malcolm Kotok, Renate Scheidler, Mckenzie West, Ursula Whitcher

Branch/Commit: public/ticket/19865 @ f6f615f

Issue created by migration from https://trac.sagemath.org/ticket/19865

[2a94e3c6-bd33-45f8-8db1-79636006ea7d]

Author: Malcolm Kotok

[kedlaya]

comment:2

There is also a project by Costa, Harvey, and myself to do a different computation of zeta functions of nondegenerate toric hypersurfaces, using Monsky-Washnitzer cohomology in place of Dwork's series method. It's not yet clear how these two methods will compare (the Sperber-Voight method is optimized towards sparse hypersurfaces somewhat more than our approach), so it would be valuable to have both!

[kedlaya]

comment:3

Note also ticket #15239 regarding testing for nondegeneracy, which might be worth dealing with first.

[roed314]

Changed keywords from zeta, L-function to zeta, L-function, sd87

[kedlaya]

comment:5

For (my own) convenience, the link to the code is http://hdl.handle.net/1802/30832.

Related projects: #20265, #23863.

[kedlaya]

Changed keywords from zeta, L-function, sd87 to zeta, L-function, sd87, sd91

[cd756ef5-7187-4c75-ba26-b9b3d6a11074]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-As part of my Ph.D. thesis I am implementing a function to compute zeta functions of nondegenerate hypersurfaces over finite fields. I wish to incorporate this into Sage. For more information see: http://arxiv.org/abs/1112.4881
+As part of his Ph.D. thesis, Malcolm Kotok implemented a function to compute zeta functions of nondegenerate hypersurfaces over finite fields, based on a paper of Sperber and Voight. We wish to incorporate this into Sage. For more information see: http://arxiv.org/abs/1112.4881

[cd756ef5-7187-4c75-ba26-b9b3d6a11074]

Changed author from Malcolm Kotok to Heidi Goodson, Malcolm Kotok, Renate Scheidler, Mckenzie West, Ursula Whitcher

[08206545-11f8-4a5c-83fa-e86572ba7c8c]

comment:8

I tried this code about a year ago and it seemed to have some serious problems like it not finishing for a plane quartic curve over F_p (for any p). I wrote to Kotok about this, but never heard back from him. It could be some trivial issue, but it is hard to say.

[kedlaya]

comment:9

My understanding is that some successful experiments with the code were made at SD91. Maybe someone can push the result to trac so that the rest of us can help with stress-testing?

[08206545-11f8-4a5c-83fa-e86572ba7c8c]

comment:10

Ok, here is what I'm talking about:

load("ffzeta.sage");
R.<x,y>=PolynomialRing(ZZ,2);

# does work:
Q=y^2-(x^3+x+1); p=13;
ffzeta(Q,p,verbose=True);

# does not work:
Q=y^4+(5*x-4)*y^3+(3*x^2+2*x-3)*y^2+(x^3+4*x^2-2*x+3)*y+(3*x^4-2*x^3-4*x^2+2*x+2); p=11;
ffzeta(Q,p,verbose=True);

[kedlaya]

comment:11

The Sperber-Voight algorithm being implemented here has as a complexity parameter the number of interior monomials, so it probably doesn't stand much of a chance for dense equations (although descending it from Sage to Cython might help near the borderline).

For smooth projective hypersurfaces, we also have tickets #20265 (deformation) and #23863 (controlled reduction). For nondegenerate toric hypersurfaces, Edgar Costa has functioning C code doing controlled reduction, but I believe it is not yet available for public consumption.

[mckenziewest]

Branch: u/mwest/ticket_19865

[mckenziewest]

comment:13

We have some debugging to make this a method for polynomials. There are definitely errors in the computation in the multivariate example at the beginning of the function.

---

New commits:

30f7aef	New function zeta_function has been added to multi_polynomial
c6c8c8e	Kotok code added, zeta_function is a method of polynomials

[mckenziewest]

Commit: c6c8c8e

[fchapoton]

Changed branch from u/mwest/ticket_19865 to public/ticket/19865

[fchapoton]

Changed commit from c6c8c8e to 250c900

[fchapoton]

New commits:

2422fb1	New function zeta_function has been added to multi_polynomial
250c900	Kotok code added, zeta_function is a method of polynomials

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 250c900 to 85b7c27

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

365349c	Kotok code added, zeta_function is a method of polynomials
015104f	details
85b7c27	moving to another file

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f6f615f

details

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 85b7c27 to f6f615f

[fchapoton]

comment:17

Maybe this could be saved ?

[kedlaya]

comment:18

Just tried this and there is still something wrong:

File "src/sage/rings/polynomial/multi_polynomial.pyx", line 2494, in sage.rings.polynomial.multi_polynomial.MPolynomial.zeta_function
Failed example:
    (x^3+x+1-y^2).zeta_function(7)
Expected:
    (7*T^7 - 17*T^6 + 14*T^5 - 12*T^4 + 18*T^3 - 14*T^2 + 5*T - 1)/(7*T - 1)
Got:
    (-3*T^4 + 2*T^3 + 4*T^2 - 2*T - 1)/(7*T - 1)

I was not one of the people working on this at sd91, so I wouldn't know what the issue is.

[embray]

comment:19

Ticket retargeted after milestone closed

[mkoeppe]

comment:20

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[kedlaya]

comment:21

Still not sure what is going on here. This passage in zeta_function.py is nonsensical:

            # Reduce remaining part
            meta = Gm.parent()(m * eta[i])
            x_i = Gm.parent()(x[i])
            Gmbar = -sum([x_i * meta.derivative(x_i) for i in range(n + 1)])

but fixing it doesn't have any effect on the doctests (the terms in the sum are all zero anyway).

Another data point: the ratio of the answers with affine=True and affine=False is not correct either.

[mkoeppe]

comment:23

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.