Efficient \(p\)-adic cell decompositions for univariate polynomials (Q1578508)

This paper follows the algebraic approach developed by \textit{Cohen} (1969). Cohen's cells are sets of the form \(C= \{x\in \mathbb{Q}_p\mid x= x_0+ p^a u\), \(u\in \mathbb{Z}_p\}\). Cell decompositions are a standard technique in the theory of \(p\)-adics: the \(p\)-adic numbers are covered by finite collections of cells, constructed so that on each cell the polynomial is ``well behaved'', in a specified way. In this paper cell decompositions are constructed for polynomials \(f(x)\in \mathbb{Z}_p[x]\) of degree \(n\), such that \(n< p\), using \(O(n^2)\) cells. When \(f\) is square-free this yields a polynomial-time algorithm for counting and approximating roots in \(\mathbb{Z}_p\). These results extend to give a polynomial-time algorithm in the model for \(f\in \mathbb{Z}[x]\).