Vol. 4, No. 1, 2020

Download this article
Download this article For screen
For printing
Recent Volumes
5: Gauge Theory and Low-Dimensional Topology
4: ANTS XIV
3: Hillman: Poincaré Duality
2: ANTS XIII
1: ANTS X
The Open Book Series
All Volumes
 
About the Series
Ethics Statement
Purchase Printed Copies
Author Index
 
ISSN 2329-907X (online)
ISSN 2329-9061 (print)
 
MSP Books and Monographs
Other MSP Publications
Computing Igusa's local zeta function of univariates in deterministic polynomial-time

Ashish Dwivedi and Nitin Saxena

Vol. 4 (2020), No. 1, 197–214
Abstract

Igusa’s local zeta function Zf,p(s) is the generating function that counts the number of integral roots, Nk(f), of f(x) mod pk, for all k. It is a famous result, in analytic number theory, that Zf,p is a rational function in (ps). We give an elementary proof of this fact for a univariate polynomial f. Our proof is constructive as it gives a closed-form expression for the number of roots Nk(f).

Our proof, when combined with the recent root-counting algorithm of Dwivedi, Mittal and Saxena (Computational Complexity Conference, 2019), yields the first deterministic poly(|f|,logp)-time algorithm to compute Zf,p(s). Previously, an algorithm was known only in the case when f completely splits over p; it required the rational roots to use the concept of generating function of a tree (Zúñiga-Galindo, J. Int. Seq., 2003).

Keywords
Igusa, local, zeta function, discriminant, valuation, deterministic, root, counting, modulo, prime power
Mathematical Subject Classification 2010
Primary: 11S40, 68Q01, 68W30
Secondary: 11Y16, 14G50
Milestones
Received: 22 February 2020
Revised: 24 February 2020
Accepted: 29 April 2020
Published: 29 December 2020
Authors
Ashish Dwivedi
Department of Computer Science and Engineering
Indian Institute of Technology Kanpur
Kanpur
India
Nitin Saxena
Department of Computer Science and Engineering
Indian Institute of Technology Kanpur
Kanpur
India