Vector space bases associated to vanishing ideals of points (Q2655003)

The author discusses four different constructions of vector space bases associated to vanishing ideals of points and he shows how to compute normal forms with respect to these bases giving new complexity bounds. Let \(k[x_1, \dots, x_n]\) be the polynomial ring in \(n\) variables over a field \(k\). The vanishing ideal \(I\) with respect to a set of points \(\{p_1, \dots, p_n\}\) in \(k^n\) is defined as the set of elements of \(k[x_1, \dots, x_n]\) that are zero on all of the \(p_i\)'s. The main tool that is used to compute vanishing ideals of points is the Buchberger-Möller algorithm which returns a Gröbner basis for the ideal vanishing on the set \(\{p_1, \dots, p_n\}\). A complementary result of the algorithm is a vector space basis for the quotient ring \(k[x_1, \dots, x_n]/I\). In several applications it turns out that the attention is more related on this vector space basis than in the Gröbner basis. For example, it may be preferable to compute normal forms using vector spaces methods instead of Gröbner basis techniques. Thus the author introduces four different approaches for the construction of the vector space basis, all of which perform better than the Buchberger-Möller algorithm. The first construction produces a vector space basis, for the quotient ring, given by a family of separators, that is, a family \(\{f_1, \dots, f_n\}\) of polynomials such that \(f_i(p_i)=1\) and \(f_i(p_j)=0\) if \(i\not= j\). The second construction is a \(k-\)basis formed by the residues \(1,f,\dots, f^{m-1}\), where \(f\) is a linear form. The third construction produces a set of monomials outside the initial ideal of \(I\) with respect to the lexicographical ordering, using only combinatorial methods. Finally, the fourth construction gives a \(k-\)basis which is the complement of the initial ideal with respect to a class of admissible monomial orders. A fundamental element for the effectiveness of these methods is a fast combinatorial algorithm which gives useful structure informations about the relations between the points. As an important application, the author drastically improves the computational algebra approach to the reverse engineering of gene regularity networks.