×

A combinatorial result on Gröbner fans with an application to universal Gröbner bases. (English) Zbl 0862.13010

Let \(I\) be an ideal in the ring \(R\) of polynomials in \(n\) indeterminates over a field. To each term order \(\prec\) on \(R\) there corresponds a rational cone \(C_\prec (I)\) contained in the positive orthant \(\mathbb{R}^n_+\) in \(\mathbb{R}^n\), the so-called Gröbner cone of \(I\) with respect to \(\prec\), and there is a one-to-one mapping between the set of the Gröbner cones of \(I\) and the set of all oriented reduced Gröbner bases of \(I\). (An oriented polynomial in \(R\) is a non-zero element \(f\in R\) together with the specification of one of the monomials occurring in \(f\) as its initial monomial, and a subset of \(R\) is called oriented if each of its element is oriented.) The set \({\mathcal F} (I)\) of the Gröbner cones of \(I\) is finite and is called the (restricted) Gröbner fan of \(I\) [cf T. Mora and L. Robbiano, J. Symb. Comput. 6, No. 2/3, 183-208 (1988; Zbl 0668.13017)].
In this paper the following theorem is proved: The Gröbner fan \({\mathcal F} (I)\) is a polyhedral tesselation of \(\mathbb{R}^n_+\) which is regular in the sense that the intersection of two Gröbner cones of \(I\) is a common face of these cones. The Gröbner fan \({\mathcal F} (I)\) is therefore a fan in the sense of the theory of toric varieties [cf. T. Oda, “Convex Bodies and algebraic geometry. An introduction to the theory of toric varieties” (1988; Zbl 0628.52002)]. – In the second part of this paper the regularity of \({\mathcal F} (I)\) is used to obtain an algorithm for the enumeration of all oriented reduced Gröbner bases of the ideal \(I\).

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alonso M. E., Mora T., Niesi G., Raimondo M.: An algorithm for computing analytic branches of space curves at singular points. In: Proc. 1992 Int. Workshop on Mathematics Mechanization, pp 135-166. Int. Acad. Publishers 1992
[2] Alonso M. E., Mora T., Raimondo M.: Local parameterization of space curves at singular points, in: Falcidieno B., Herman I., Pienovi C. (eds), Computer Graphics Mathematics, pp 61-90. Berlin, Heidelberg, New York, Springer 1992. Eurographic Seminar Series
[3] Assi A.: Standard bases, critical tropisms and flatness. AAECC 4, 197-215 (1993). · Zbl 0794.14021 · doi:10.1007/BF01202038
[4] BrØndsted A.: An Introduction to Convex Polytopes, vol 90 of Graduate Texts in Mathematics. Berlin, Heidelberg, New York: Springer 1983 · Zbl 0509.52001
[5] Buchberger B.: A theoretical basis for the reduction of polynomials to canonical forms. ACM SIGSAM Bull. 10(3), 19-29 (1976)
[6] Buchberger B.: Gröbner bases: An algorithmic method in polynomial ideal theory. In Bose N. K., Recent Trends in Multidimensional System Theory. Chap 6. Reidel Publ. 1985. · Zbl 0587.13009
[7] Collart S., Kalkbrener M., Mall D.: The Gröbner walk. Submitted, 1993 · Zbl 0908.13020
[8] Collart S., Mall D.: Algorithmic issues in the computation of universal Gröbner bases. Presented at the MAGMA Conference on Computational Algebra, Queen Mary and Westfield College, London, August 23rd to 27th 1993
[9] Collart S., Mall D.: Redundancies in the computation of the Gröbner system of a polynomial ideal. Technical report, Department of Mathematics, Federal Institute of Technology, Zurich, Switzerland, 1994
[10] Faugère J. C, Gianni P., Lazard D., Mora T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. (To appear) J. Symb. Comp. · Zbl 0805.13007
[11] Herfort W., Penz H.: A new notion of reduction: Generating universal Gröbner bases of ideals inK[x,y]. J. Symb. Comp., 12, 583-605 (1991) · Zbl 0805.13008 · doi:10.1016/S0747-7171(08)80143-5
[12] Macaulay F. S.: Some properties of enumeration in the theory of modular systems. Proc. London Math. Soc. 26, 531-555 (1927) · JFM 53.0104.01 · doi:10.1112/plms/s2-26.1.531
[13] Möller M., Mora F.: New constructive methods in classical ideal theory. J. Algebra 100, 138-178 (1986) · Zbl 0621.13007 · doi:10.1016/0021-8693(86)90071-2
[14] Mora T, Robbiano L.: The Gröbner fan of an ideal. J. Symb. Comp. 6, 183-208 (1988) · Zbl 0668.13017 · doi:10.1016/S0747-7171(88)80042-7
[15] Tadao Oda: Convex Bodies and Algebraic Geometry. An Introduction to the Theory of Toric Varieties, vol. 15, 3. Folge of Ergebnisse der Mathematik und ihrer Grenzgebiete. Berlin, Heidelberg, New York: Springer 1985. Translated from Totsutai to Diasukikagaku
[16] Robbiano L.: Term orderings on the polynomial ring. In: Caviness B. F. (ed) Proc. EUROCAL 85, pp 513-517. Berlin, Heidelberg, New York: Springer, 1985, Lecture Notes Comp. Sci. vol. 204 · Zbl 0584.13016
[17] Schemmel K.-P.: An extension of Buchberger’s algorithm to compute all reduced Gröbner bases of a polynomial ideal. In: Davenport J. H. (ed), Proc. EUROCAL ’87, pp 300-310. Berlin, Heidelberg, New York: Springer 1987. Lect. Notes Comp. Sci · Zbl 1209.13008
[18] Schwartz N.: Stability of Gröbner bases. J. Pure Appl. Algebra 53, 171-186 (1988) · Zbl 0664.13006 · doi:10.1016/0022-4049(88)90018-7
[19] Schwarz F.: Monomial orderings and Gröbner bases. SIGSAM Bulletin, 25(1), 10-23 (1991) · doi:10.1145/122525.122526
[20] Sturmfels B.: Gröbner bases and polytopes, Lectures presented at the Holiday Symposium at New Mexico State University. Manuscript, 1994
[21] Strumfels B., Thomas R.: Variation of cost functions in integer programming. Preprint, 1994
[22] Traverso C.: Computing the Hilbert-Poincaré series of monomial ideals, applications to Gröbner bases. Preprint
[23] Weispfenning V.: Admissible orders and linear forms. ACM SIGSAM Bulletin 21, 16-18 (1987) · Zbl 0655.13017 · doi:10.1145/24554.24557
[24] Weispfenning V.: Constructing universal Gröbner bases. In Huguet L., Poli A. (eds), Proc. AAECC-5, pp 408-417, Berlin, Heidelberg, New York: Springer 1987. Lect. Note Comp. Sci. vol. 356
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.