Igusa’s local zeta function
is the generating function that counts the number of integral roots,
, of
, for
all
.
It is a famous result, in analytic number theory, that
is a rational
function in
.
We give an elementary proof of this fact for a univariate polynomial
. Our
proof is constructive as it gives a closed-form expression for the number of roots
.
Our proof, when combined with the recent root-counting algorithm of Dwivedi, Mittal
and Saxena (Computational Complexity Conference, 2019), yields the first deterministic
poly()-time algorithm
to compute
.
Previously, an algorithm was known only in the case when
completely
splits over
;
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