Matrix-F5 algorithms over finite-precision complete discrete valuation fields (Q5891054): Difference between revisions

Let \(R\) be the ring of \(p\)-adic integers or power series in one indeterminate over a finite prime field, \(K\) the field of fractions and \(A=K[X_1,\dots, X_s]\). The elements of \(A\) have coefficients given by power series development and therefore in any symbolic manipulation one has to deal only with truncations up to a certain order. Consequently, direct computations do not suffice to decide whether a given element is zero or not. In order to circumvent this issue, the author introduces a definition for an approximate Gröbner basis with respect to some monomial order \(w\) as well as the notion of weakly-\(w\)-ideal in \(A\). The main result refers to homogeneous polynomials from \(A\) subject to two hypotheses: {\parindent=0.6cm\begin{itemize}\item[H1] \(f_1,\dots,f_s\) form a regular sequence, \item[H2] \(f_1,\dots,f_i\) generate a weakly-\(w\)-ideal in \(A\) for all \(i=1,\dots,s\). \end{itemize}} Let \(D\) be a positive integer and \(f_1',\dots,f_s'\) approximations of \(f_i\)'s with precision \(m\) on the coefficients. Then if \(m\) is sufficiently large, an approximate \(D\)-Gröbner basis of \(\langle f_1',\dots, f_s' \rangle\) with respect to \(w\) can be constructed by an analogue of Faugère's Matrix-F5 algorithm. Two specific bounds beyond which the main theorem holds are indicated. For each of them, an analysis of complexity of the resulting algorithm is performed. The paper contains two applications of such a result. The first one deals with the mapping sending a (finite) sequence of polynomials to its reduced Gröbner basis. It is shown that in a neighbourhood of \(f_1,\dots,f_s\) satisfying H1 and H2, the mapping in question is continuous and differentiable. An explicit formula for the differential is provided. In a different vein, it is shown that the essential hypotheses H1 and H2 ensure lifting of Gröbner bases from \(\mathbb Z/p^k \mathbb Z\) to \(\mathbb Z/p^{k+e} \mathbb Z\) (\(e \geq 1\)). Finally it is indicated how to extend the work to non-homogeneous polynomials whose leading homogeneous forms satisfy the critical hypotheses, in case the monomial ordering refines the total-degree order.