#### Vol. 4, No. 1, 2020

 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 (electronic): 2329-907X ISSN (print): 2329-9061 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 ${Z}_{f,p}\left(s\right)$ is the generating function that counts the number of integral roots, ${N}_{k}\left(f\right)$, of $f\left(x\right)\phantom{\rule{0.2em}{0ex}}mod\phantom{\rule{0.2em}{0ex}}{p}^{k}$, for all $k$. It is a famous result, in analytic number theory, that ${Z}_{f,p}$ is a rational function in $ℚ\left({p}^{s}\right)$. 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 ${N}_{k}\left(f\right)$.

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 ${Z}_{f,p}\left(s\right)$. 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