A simplified proof of the characterization theorem for Gröbner-bases

ABSTRACT

In /2/ a certain type of bases ("Gröbner-Bases") for polynomial ideals has been introduced whose usefulness stems from the fact that a number of important computability problems in the theory of polynomial ideals are reducible to the construction of bases of this type. The key to an algorithmic construction of Gröbner-bases is a characterization theorem for Gröbner-bases whose proof in /2/is rather complex.In this paper a simplified proof is given. The simplification is based on two new lemmas that are of some interest in themselves. The first lemma characterizes the congruence relation modulo a polynomial ideal as the reflexive-transitive closure of a particular reduction relation ("M-reduction") used in the definition of Gröbner-bases and its inverse. The second lemma is a lemma on general reduction relations, which allows to guarantee the Church-Rosser property under very weak assumptions.

REFERENCES

• 1: B. Buchberger, Ph.D. Thesis, Univ. Innsbruck, 1965 (see also Aequationes mathematicae, Vol. 4/3, pp. 374--383, 1970).
• 2: B. Buchberger, A theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bulletin, v.10 n.3, p.19-29, August 1976 [doi>10.1145/1088216.1088219]
• 3: Bruno Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.3-21, June 01, 1979
• 4: B. Buchberger, F. Winkler, Miscellaneous Results on the Construction of Gröbner-Bases for Polynomial Ideals, Bericht Nr. 137, Institut für Mathematik, Universität Linz, 1979.
• 5: G. Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems, 18th IEEE Symp. on Found. Comp. Scie, 30--45, 1977.
• 6: D. Knuth, P. Bendix, Simple word problems in universal algebras, Computational problems in abstract algebra, Ed. J. Leech, Pergamon Press, pp. 263--297, 1970.
• 7: C. Kollreider, B. Buchberger, An Improved Algorithmic Construction of Gröbner-Bases for Polynomial Ideals, Bericht Nr. 110, Institut für Mathematik, Universität Linz, 1978.
• 8: R. Loos, personal communication, 1979.