Complexity of Deciding Solvability of Polynomial Equations over p-adic Integers
Alexander L. Chistov, Marek Karpiński · 1997
Consider a system of polynomial equations in $n$ variables of degrees less than $d$ with integer coefficients with the lengths less than $M$. We show using the construction close to smooth stratification of algebraic varieties that an integer \[\Delta > 2^{Md^{2^{n(1+o(1))}}}\] corresponds to these polynomials such that for every prime $p$ the considered system has a solution in the ring of $p$-adic numbers if and only if it has a solution modulo $p^N$ for the least integer $N$ such that $p^N$ does not divide $\Delta$. This improves the previously known result by B.~J.~Birch and K.~McCann.