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
$\mathbb{Q}\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 closedform expression for the number of roots
${N}_{k}\left(f\right)$.
Our proof, when combined with the recent rootcounting algorithm of Dwivedi, Mittal
and Saxena (Computational Complexity Conference, 2019), yields the first deterministic
poly($\leftf\right,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
${\mathbb{Q}}_{p}$;
it required the rational roots to use the concept of generating function of a tree
(ZúñigaGalindo, J. Int. Seq., 2003).
