Faster p-adic feasibility for certain multivariate sparse polynomials

Abstract: We present algorithms revealing new families of polynomials allowing sub-exponential detection of p-adic rational roots, relative to the sparse encoding. For instance, we show that the case of honest n-variate (n+1)-nomials is doable in NP and, for p exceeding the Newton polytope volume and not dividing any coefficient, in constant time. Furthermore, using the theory of linear forms in p-adic logarithms, we prove that the case of trinomials in one variable can be done in NP. The best previous complexity bounds for these problems were EXPTIME or worse. Finally, we prove that detecting p-adic rational roots for sparse polynomials in one variable is NP-hard with respect to randomized reductions. The last proof makes use of an efficient construction of primes in certain arithmetic progressions. The smallest n where detecting p-adic rational roots for n-variate sparse polynomials is NP-hard appears to have been unknown.

Review text

For an input Laurent polynomial system \(F \in \bigcup_{k,n \in \mathbb{N}}( \mathbb{Z}[x_1^{\pm 1},\dots,x_n^{\pm 1}])^k\), let \(\text{FEAS}_{\mathbb{Q}_{\text{primes}}}\) denote the problem of deciding whether \(F\) has a \(p\)-adic rational root. If \(f(x) := \sum_{j=1}^m c_jx^{a_j}\), with \(c_j \in \mathbb{R}\setminus \{0\}\) for all \(j\), and \(x^{a_j} = x_1^{a_{1j}}\cdots x_n^{a_{nj}}\), then size(\(f\)) := \(\sum_{i=1}^m \log_2[(2+|c_i|)(2+|a_{1j}|) \cdots (2+|a_{nj}|)\). When the prime \(p\) is fixed, the input size will be size(\(f\)), but when the prime \(p\) is allowed to range over all or a subfamily of primes, the input size will be \(\text{size}(f)+\log(p)\). Size\((F)\) is the sum of the sizes of the polynomials defining \(F\). If the \(a_j\) are pairwise distinct, \(f\) is an \textit{\(n\)-variate \(m\)-nomial}. If, additionally, the volume of the Newton polytope of \(f\) is positive, \(f\) is said to be an \textit{honest \(n\)-variate \(m\)-nomial}. Only honest \(n\)-variate \(m\)-nomials are considered in the paper. NEWLINENEWLINENEWLINE NEWLINEGiven the above definitions, the authors prove that the detection of \(p\)-adic rational roots is: NEWLINE{\parindent=7mmNEWLINE\begin{itemize}\item[{\(*\)}]\textbf{NP}-complete for honest \(n\)-variate (\(n+1\))-nomials,NEWLINE\item[{\(*\)}]of constant-time complexity for certain special families of \(n\)-variate (\(n+1\))-nomials when \(p\) exceeds the Newton polytope volume NEWLINE\item[{\(*\)}]\textbf{NP} for trinomials in one variable NEWLINE\item[{\(*\)}]\textbf{NP}-hard for sparse polynomials in one variable with respect to randomized reductions. NEWLINENEWLINENEWLINE\end{itemize}} NEWLINEAdditionally, the authors prove that, for \(f \in \mathbb{Z}[x_1]\), if there were randomized algorithms of expected complexity polynomial in \(\text{size}(f)+\log(p)\) for factoring \(f\) over \(\mathbb{Q}_p[x_1]\), then \textbf{NP} \(\subseteq\) \textbf{ZPP}.NEWLINENEWLINEThe univariate \textbf{NP}-hardness proof requires the efficient construction of primes in certain arithmetic progressions, which the authors also prove possible.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Faster \(p\)-adic feasibility for certain multivariate sparse polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412210)