Efficient p-adic cell decompositions for univariate polynomials
Efficient \(p\)-adic cell decompositions for univariate polynomials
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]\).
- An inequality for the discriminant of a polynomial
- Computational complexity over the \(p\)-adic numbers
- Computing Rational Zeros of Integral Polynomials by p-Adic Expansion
- Decision procedures for real and p‐adic fields
- scientific article; zbMATH DE number 3141365 (Why is no real title available?)
- scientific article; zbMATH DE number 3957242 (Why is no real title available?)
- scientific article; zbMATH DE number 3566956 (Why is no real title available?)
- scientific article; zbMATH DE number 953031 (Why is no real title available?)
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- p-adic semi-algebraic sets and cell decomposition.
This page was built for publication: Efficient \(p\)-adic cell decompositions for univariate polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1578508)
