On the complexity of \(p\)-adic basic semi-algebraic sets (Q883331)

The authors study the analogue of semi-algebraic sets in the \(p\)-adic case and analyze the complexity of an algorithm to decide whether a given set is nonempty. For this study they look at the Macintyre predicate \[ P_t(x) \Leftrightarrow \exists y \in Q_p\,[y^t = x] \] where \(t\) is a nonzero integer and \(Q_p\) is the completion of the rational numbers with respect to the evaluation \(\nu_p\). Here \(\nu_p\) determines the power of the prime \(p\) in the rational; for example, \(\nu_3(3^2\cdot 5^3 \cdot 7^{-4})=2\). A basic semialgebraic set \(S\) over \(Q_p\) is given by polynomials \(f,g_1,g_2,\ldots,g_m\) in one variable over \(Q_p\) and nonzero integers \(t_1,t_2,\ldots,t_m\) in the way that \[ S = \{x: f(x)=0 \wedge \forall j \in \{1,2,\ldots,m\}\, [P_{t_j}(g_j(x))]\}. \] The basic question is now whether \(S\) is empty. This problem is called FSAS where the abbreviation stands for ``feasibility of \(p\)-adic basic semi-algebraic sets'' and ``feasible'' means ``not empty''. The authors provide an algorithm with a running time of the order \[ m \cdot N^2 + m \cdot n \cdot N + m \cdot n \cdot T^2 + m \cdot n \cdot \log^2(n) + n^5\cdot p\cdot \log(L) + n^7 \cdot p \] where the authors use in this term sometimes a maximum instead of a sum, but this makes no difference as only the order is considered. The complexity is measured in the \(Q_p\)-analogue of the BSS-complexity model named after Blum, Shub and Smale; it includes the valuation \(\nu_p\) as a basic operation. The parameters have the following meaning: \(m\) is the number of the \(g_j,t_j\); \(n\) is the degree of the polynomial \(f\); \(N\) the maximum of the degrees of the polynomials \(g_j\); \(p\) is the prime number defining the set \(Q_p\) of \(p\)-adic numbers considered; \(T = \max\{t_1^2,t_2^2,\ldots,t_m^2\}\); \(L = \max\{L(f),L(g_1),L(g_2),\ldots,L(g_m)\}\) where the \(L\) of a polynomial is computed from the valuation \(\nu_p\) of the discriminant and some coefficients. \(L\) is used as an additional measure for the complexity of the polynomials involved and determines the precision needed for the \(p\)-adic computations in some part of the algorithm. The authors deal only with the case of polynomials in one variable in \(Q_p\) while the corresponding study of semi-algebraic sets for real numbers involves also multi-variate polynomials.