Efficiently computing Igusa's local-zeta function

Nitin Saxena (CSE@IIT Kanpur, India)‏

​

(ANTS-XIV'20 ; with Ashish Dwivedi)

​

Indo-European Maths Conference

Jan 2026, SPPU & IISER Pune

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

Zeta functions

• For function N_k there's generating-function G(t):= ∑_k≥0 N_k t^k .
• This carries comprehensive information about N_k .
• Eg. the growth of N_k decides how the power-series converges.

​

• Riemann zeta-fn: ζ(s) = ∑_k≥1 1/k^s .
• What's it encoding?

​

• Inspired many other zeta functions:
• Selberg zeta fn of a manifold
• Ruelle zeta fn of a dynamical system
• Ihara zeta fn of a graph

​

• Local-zeta functions (based on a prime p):
• Hasse-Weil zeta fn
• Igusa local-zeta fn

​

Riemann 1826-66

To count points

Galois field vs ring Z/p^kZ

E.g. Ramanujan tau-function t·∏_m≥1(1-t^m)²⁴

PRIMES

Geodesics, Orbits, Cycles

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

Igusa's local-zeta function

• Let Z_p denote p-adic integers.
• Elements are ∑_i≥0 a_i pⁱ (a_i ∊ [0,p-1]) .
• Let f = f(x₁,...,x_n) be n-variate integral polynomial.

​

• Defn.1: Igusa's local-zeta fn Z_f,p(s) = ∫_{(Z_p)^n} |f(x)|_p^s ·|dx|.
• Integrate using p-adic metric and Haar measure.

​

• This converges to a rational function in Q(p^s).
• (Igusa'74) by resolving singularities.
• (Denef'84) by p-adic cell decomposition.

​

• Counts roots f(x) mod p^k & `multiplies' by p^-ks.

​

• So, we can give an easier definition:

Igusa 1924-2013

infinite sum

For all k

Igusa's local-zeta function

• Define N_k(f) := # roots of f(x) mod p^k .

​

• Defn.2: Poincaré Series P_f,p(t) = ∑_k≥0 N_k(f)/p^nk ·t^k .
• Eg. P_0,p(t) = ∑_k≥0 t^k = 1/(1-t) .
• (Igusa'74) connected them at t=p^-s : P(t)·(1-t) = 1 - t·Z(s) .

​

• (Igusa'74) P_f,p(t) converges to a rational function in Q(t).

​

• This means that N_k(f) is rather special !
• Generally, power-series don't converge in Q(t).
• Eg. ∑_k≥0 (1/k!) ·t^k is irrational !

​

• Convergence proofs are quite non-explicit.
• What do we learn about N_k(f) , for small k ?

Two Defns: Analytic vs Discrete

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

Algorithmic questions

• Qn: Could N_k(f) be computed efficiently?

​

• Trivially, in p^kn time.
• Much faster unlikely.
• It's NP-hard; even Permanent-hard !

​

• Could N_k(f) be computed efficiently, for univariate f(x)?
• Qn: In poly(deg(f), log p^k) time?

​

• Or, try to compute the analytic-integral defining Z_f,p(s).

​

• (Chistov'87) gave a randomized algorithm to factor f(x) over Z_p.
• Using this one could factor f into roots,
• and attempt the integration ...?

​

• Qn: But, a deterministic poly-time algorithm for N_k(f) ?

In p-adic extensions

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

Root-finding mod p^k

​

• Instead of integration, we take the route of roots mod p^k.

​

• Let f mod p^k be degree d univariate polynomial.

​

• (Berthomieu,Lecerf,Quintin'13) Roots of f mod p^k arrange as representative-roots:
• a =: ∑_0≤i<ℓ a_i pⁱ + *p^ℓ (a_i ∊ [0,p-1] , * ∊ Z) .
• a is minimal & f(a) = 0 mod p^k .
• At most d rep.roots.

​

• Proof is inductive, based on the transformation:
• g(x) := f(∑_0≤i<m a_i pⁱ + x·p^m) / p^v mod p^k-v .
• Root of g(x) mod p gives a_m .
• Continue with ∑_0≤i≤m a_i ·pⁱ .

Reduces char p^k to p

Why are rep.roots a few?

​

​

Many a_m’s ⇒ slower growth of m.

​

Root-finding mod p^k

​

• Rep.roots are few, but roots may be exponentially many!
• Eg. f := px mod p² has p roots,
• but just one rep.root a =: 0 + *p !

​

• (BLQ'13) yields fast randomized algorithm to find roots mod p^k.
• Counting is easy, as rep.root a means p^k-ℓ roots.
• a = ∑_0≤i<ℓ a_i ·pⁱ + *p^ℓ .
• Summing up over rep.roots, gives all roots.

​

• How to make it deterministic poly-time?

​

• Rep.roots yield N_k(f) = ∑_i p^{k - ℓ_i} .
• What does it say about Poincaré series P_f,p(t) ?

ℓ_i depends on i, k

Root-finding mod p^k

​

• (Dwivedi,Mittal,S '19) gave fast deterministic algorithm to implicitly find roots mod p^k.

​

• Idea: Store rep.roots a = ∑_0≤i<ℓ a_i ·pⁱ + *p^ℓ in maximal split ideals.
• I = <h₀(x₀) , h₁(x₀,x₁) ,..., h_ℓ-1(x₀,...,x_ℓ-1)> .
• Each zero of I in F_p^ℓ defines a rep.root.
• Essentially, run (BLQ'13) mod I (without randomization!).
• Keep `growing' I.

​

• (DMS'19) yields fast deterministic algorithm to count roots f mod p^k.

Yet N_k(f) remains a mystery !

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

Root-counting mod p^k

​

• Intuitively, N_k(f) = ∑_i p^{k - ℓ_i} should behave better for large k .
• Since, large k is like studying roots in Z_p .

​

• We show, for large k : ℓ_i is linear in k.

​

Details:

​

• k > k₀ := deg(f) · val_p(disc( rad(f) )) .

​

• ℓ_i = ⌈ ( k – val_p(f_i(α_i)) ) / mult(α_i) ⌉ .
• Where, α_i are all p-adic integer roots of f(x) .

​

​

Roots uniquely

lift as

k grows.

Constant (k-ℓ_i)/k =: u_i

Curiously, squarefree f & large k ⇨ N_k(f) independent of k .

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

Compute Poincaré Series

​

• Got : N_k(f) = ∑_i p^k·u_i for k > k₀ .

​

• So, P(t) = ∑_k≥0 N_k(f)/p^k ·t^k ,

=: P₀(t) + ∑_{k≥k_0} N_k(f)/p^k ·t^k ,

= P₀(t) + ∑_{k≥k_0} ∑_i p^k·(u_i-1) ·t^k .

​

• The infinite sum converges to a rational, in Q(t).

​

• Thus, P(t) is a rational function.

​

• Our algorithm computes N_k(f) function;

hence, both P₀(t) and the infinite sum are known.

• In poly(|f|, log p) time.

Contents

• Zeta functions
• Igusa's local-zeta fn

​

• Algorithmic questions
• Root finding mod p^k

​

• Root counting mod p^k
• Compute Poincaré Series

​

• Conclusion

​

At the end …

• Det.poly-time algorithm for Igusa's local-zeta function.
• For univariate polynomial f.

​

• Could we do this for bivariate polynomial f(x₁, x₂) ?

​

• Relevant Questions:

​

1. Estimating the count N_k(f(x₁, x₂)) = ? (Chakrabarti, S., ISSAC'23)

​

1. Counting factors of f(x) mod p^k ?
• Irreducibility-testing of f(x) mod p⁵ ? (Mahapatra, S., WIP)
• GCD of f(x), g(x) mod p⁵ ?

​

1. Hasse-Weil Zeta fn of a variety mod p? (S., Madhavan V., WIP)

​

​

Thank you!