A general framework for Noetherian well ordered polynomial reductions

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Parametrization (Chow and Hilbert schemes) (14C05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Symbolic computation and algebraic computation (68W30)

Abstract: Polynomial reduction is one of the main tools in computational algebra with innumerable applications in many areas, both pure and applied. Since many years both the theory and an efficient design of the related algorithm have been solidly established. This paper presents a general definition of polynomial reduction structure, studies its features and highlights the aspects needed in order to grant and to efficiently test the main properties (noetherianity, confluence, ideal membership). The most significant aspect of this analysis is a negative reappraisal of the role of the notion of term order which is usually considered a central and crucial tool in the theory. In fact, as it was already established in the computer science context in relation with termination of algorithms, most of the properties can be obtained simply considering a well-founded ordering, while the classical requirement that it be preserved by multiplication is irrelevant. The last part of the paper shows how the polynomial basis concepts present in literature are interpreted in our language and their properties are consequences of the general results established in the first part of the paper.

Review text

The notion of division may be traced back to \textit{P. Gordan} [Nachr. Ges. Wiss. Göttingen, Math.-Phys. Kl. 1899, 240--242 (1899; JFM 30.0113.01)] when he used it as a technical tool in his proof of Hilbert's Basissatz. The main aim of this paper is to give a more general structure for concept of polynomial reduction. Let \(R= K[x_1,\ldots ,x_n]\) be a polynomial ring over the base field \(K\) and \(T\) the set of all power products of \(R\). A reduction structure (RS for short) \(\mathcal{J}\) is a triple \((M,\lambda = \{\lambda_{\alpha} , x^{\alpha} \in M\}, \tau := \{\tau_{\alpha} , x^{\alpha} \in M\})\) satisfying the following conditions: \begin{itemize} \item \(M\subset T\) is a finite set, \item for all \(x^{\alpha} \in M\), \(\tau_{x^{\alpha}} \) is an order ideal, \item for all \(x^{\alpha} \), \(\lambda_{\alpha}\) is a finite subset of \(T\setminus \{ x^{\alpha+\beta} \ | \ x^{\beta}\in \tau_{\alpha}\}\). \end{itemize} Let us consider an RS \(\mathcal{J} = (M, \lambda, \tau )\). A marked set \(F=\{f_{\alpha}\}_{x^{\alpha}\in M}\) over \(\mathcal{J}\) is a set of monic marked polynomials so that for each \(x^{\alpha}\in M\), the head power product of \(f_{\alpha}\) is \(x^{\alpha}\) and \(\mathrm{Supp}( f_{\alpha}-x^{\alpha}) \subset \lambda_{\alpha}\). Let \(F\) be a finite marked set of polynomials over an RS. Then, the division process by \(F\) is called Noetherian if the division of any polynomial by \(F\) is terminated in finitely many steps. An RS \(\mathcal{J}\) is said ordered if there is a well founded order \(\prec\) on \(T\) so that for each \(x^{\alpha}\in M\), \(x^{\gamma} \in \lambda_{\alpha}\) and \(x^{\eta} \in \tau_{\alpha}\) it holds \(x^{\alpha+\gamma}\prec x^{\alpha+\eta}\). From a well-known result due to Manna and Ness, it is deduced that an RS \(\mathcal{J}\) is ordered iff the division process by any marked set over \(\mathcal{J}\) is Noetherian. In the rest of the paper, it is shown how the well-known polynomial bases (like Gröbner bases, involutive bases and border bases) are interpreted in this setting.

Recommendations

Cites work

Cited in

(7)

Describes a project that uses

Uses Software

Plural

This page was built for publication: A general framework for Noetherian well ordered polynomial reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000264)