Gröbner bases of ideals defined by functionals with an application to ideals of projective points (Q2366274): Difference between revisions

The authors present a systematic approach to the computation of a Gröbner basis for 0-dimensional ideals defined as kernels of linear functionals of the polynomial ring. They construct two algorithms of polynomial complexity to compute such a basis which generalize the FGLM- algorithm and one due to Buchberger and Möller. For the description of the algorithms and different applications they introduce the notations of biorthogonal and triangular sequences representing the dual space of the linear functionals as diagonal or upper triangular matrix and of closed sets \(V\subset\text{Span}_ K(D)\) of differential conditions to describe primary ideals with linear functions given by these conditions. It is proved, that every 0-dimensional ideal is uniquely determined by a finite set of points \(\{y_ 1,\ldots,y_ s\}\subset\overline K^ n\) \((\overline K\) the algebraic closure of \(K)\) and a closed set \(\Delta_ i\subset\text{Span}_{K_ i}(DF)\) of differential conditions for every \(y_{i1}\) where \(y_ i=\{y_{i1},\ldots,y_{in}\}\) is the set of conjugate points and \(K_ i=K(y_{i1},\ldots,y_{in})\) the minimal field extension containing all coordinates of these points. The first of the two presented algorithms assigns iteratively all monomials to either the ideal \(T(G)\) of leading terms from the given ideal or to the set \(N\) of monomials outside \(T(G)\). The second one constructs inductively a Gröbner set \(F_ i\) for \(\text{Ker}(L_ 1,\ldots,L_ i)\) and a triangular sequence \(\{q_ 1,\ldots,q_ i\}\). Then it is shown in a detailed investigation, that both algorithms are of complexity \(O(ns^ 2+fns^ 2)\), where \(n=\#\{\text{variables}\}\), \(s=\#\{\text{functionals}\}\) and \(f=f(s,c)\) measures the evaluation of \(s\) functionals on \(c\) monomials for a concrete application. This function \(f\) is computed for different examples, so for simple and multiple, rational or algebraic points, for Border-basis and Gröbner- basis functionals. Finally a variant of the whole theory is developed for projective ideals and applied to the computation of a Gröbner-basis for simple projective points. Here it is added a polynomial algorithm to minimize a homogeneous basis.