Comprehensive Gröbner bases (Q1199704): Difference between revisions

The method of Gröbner bases is one of the fundamental algorithmic tools in polynomial algebra and algebraic geometry. The construction of a Gröbner basis of the ideal generated by a finite set of polynomials is very unstable under variation of the coefficients of the input polynomials. With the aim of solving parametric problems, the author introduces the notion of a ``comprehensive Gröbner basis'': Let \(K\) be an integral domain and \(S\) be the polynomial ring \(K[U_ 1,\ldots,U_ m;X_ 1,\ldots,X_ n]\). Given a finite set \(F\subseteq S\) and a term order \(\leq\) in the main variables \(X_ 1,\ldots,X_ n\), a comprehensive Gröbner basis \(G\) of the ideal \(Id(F)\) is a finite ideal basis of \(Id(F)\) that is a Gröbner basis of \(Id(F)\) in \(K'[X_ 1,\ldots,X_ n]\) (with respect to the term order \(\leq)\), for every specialization of the parameters \(U_ 1,\ldots,U_ m\) in an arbitrary field \(K'\). The main result of the paper is an explicit algorithmic construction over a computable ring \(K\) of a comprehensive Gröbner basis \(G\) from any finite set \(F\) and any decidable term order \(\leq\). The author shows that this construction can be performed with the same worst case degree bounds in the main variables as for ordinary Gröbner bases and presents some examples computed in an ALDES/SAC-2 implementation. Applications of comprehensive Gröbner bases are given to several parametric problems in polynomial algebra and algebraic geometry; in particular, to ``fast'' elimination of quantifier blocks in algebraically closed fields.