Title: Computing Igusa's local zeta function of univariates in deterministic polynomial-time

Abstract:

Igusa's local zeta function Z_{f,p}(s) is the generating function that counts the number of integral roots, N_k(f), of f(x_1,...,x_n) mod p^k, for all k. It is a famous result, in analytic number theory, that Z_{f,p} is a rational function in Q(p^s). We give an elementary proof of this fact for a univariate polynomial f(x_1).

Our proof, when combined with the recent root-counting algorithm of (Dwivedi, Mittal, Saxena, CCC, 2019), yields the *first* poly(|f|, log p) time algorithm to compute Z_{f,p}(s). We leave the same question for n=2 open.

The talk is based on the joint work with Ashish Dwivedi, published in "14th Biannual Algorithmic Number Theory Symposium",  ANTS-XIV, 2020. Additionally, I will overview the earlier methods, and state the major open questions, in the area of factoring modulo prime-powers.