Degeneracy loci and polynomial equation solving (Q2340506)

The purpose of this paper is to give a new algorithm that solves elimination tasks in uniform, bounded-error probabilistic pseudo-polynomial time in the case of the vector bundles formed by the couple \((V,F)\), where \(V\) is a complex quasi-affine equidimensional smooth variety of dimension \(r\) and \(F:=[f_{k,l}]_{1\leq k\leq p, 1\leq l \leq s }\) a matrix of coordinate functions of \(V\). The maximal degree of the descending chain of the degeneracy loci of the vector bundle is the main ingredient for the algorithm. The first of the algorithms computes an algebraic description of locally closed algebraic varieties \(W(a_{r})\), the degeneracy locus of the pair \((V,F)\). This algorithm is implemented within the \(C++\) library \texttt{geomsolvex} of \texttt{MATHEMAGIX}. The second algorithm checks the membership in a degeneracy locus. It is proven that the degeneracy loci are empty or equidimensional, normal and Cohen-Macaulay. Let \(n,p,q,r,s,L\) be integers with \(r=n-q\) and \(s\geq p+r\). Let \(G_{1}, \dots, G_{q}, H, F_{k,l}\) for \(1\leq k \leq p\) and \(1\leq l \leq s\) be polynomials of \(n\) variables, with rational coefficients given as outputs of an essentially division-free arithmetic circuit \(\beta\) of size \(L\). Let \(d\) be an upper bound for the degrees of the polynomials \(G_{1}, \dots, G_{q}\) and \(F_{k,l}\). One supposes that the two following conditions hold: -- \(G_{1}, \dots, G_{q}\) form a reduced regular sequence outside of \(\{H=0\}\); -- \(V:=\{G_{1}=0, \dots, G_{q}=0\}_{H}\) is a smooth quasi-affine variety. Let \(f_{k,l}\in \mathbb{C}[V]\) be the restriction of \(F_{k,l}\) to \(V\). The system degree of the polynomials \(G_{1}, \dots, G_{q}, H\neq 0\) and \(F\) is the maximal degree of the set \(\{\delta_{G}, \delta^{*}\}\) where \(\delta^{*}\) is the degree of the point-finding problem associated with the pair \((V,F)\) and \(\delta_{G}:=\max\{\deg\overline{\{G_{1}=0, \dots, G_{q}=0\}_{H}} | 1\leq j\leq q\}\) is the maximal degree of the Zariski closures of all degeneracy loci \(W(a_{i})\). The main result states that, for \(a\) being a generic matrix, there exists a uniform bounded-error probabilistic algorithm over the field of rational numbers that decides from the input \(\beta\) in time \(L(snd)^{O(1)}\delta^2= (s(nd)^{n})^{O(1)}\) whether \(W(a_{r})\) is empty. If not, then it computes a geometric resolution of \(W(a_{r})\). The second algorithm decides whether \(x \in \mathbb{A}^{n}\) belongs to \(W(a_{i})\), for \(1 \leq i\leq r\). The result states that for an algebraic extension \(\mathbb{Q}[\alpha]\) of \(\mathbb{Q}\) of degree \(e\), there exists a bounded-error probabilistic algorithm \(\mathcal{B}\) that decides, for any point \(x\in\mathbb{Q}[\alpha]^{n}\) whether \(x\) belongs to \( W(a_{i})\), in sequential time \(O(e(L+s^{O(1)})\log^{O(1)}e)=(esd^{n})^{O(1)}\). This paper provides examples and applications of these algorithms.