Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-06T11:42:22.888Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructing Gröbner bases for Noetherian rings†

Published online by Cambridge University Press:  08 October 2013

HERVÉ PERDRY  and
PETER SCHUSTER
HERVÉ PERDRY
Affiliation:
Université Paris-Sud UMR-S 669 and INSERM U 669, Villejuif F–94817, France Email: [email protected]
PETER SCHUSTER
Affiliation:
Department of Pure Mathematics, University of Leeds, Woodhouse Lane, Leeds LS2 9JT, United Kingdom Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We give a constructive proof showing that every finitely generated polynomial ideal has a Gröbner basis, provided the ring of coefficients is Noetherian in the sense of Richman and Seidenberg. That is, we give a constructive termination proof for a variant of the well-known algorithm for computing the Gröbner basis. In combination with a purely order-theoretic result we have proved in a separate paper, this yields a unified constructive proof of the Hilbert basis theorem for all Noether classes: if a ring belongs to a Noether class, then so does the polynomial ring. Our proof can be seen as a constructive reworking of one of the classical proofs, in the spirit of the partial realisation of Hilbert's programme in algebra put forward by Coquand and Lombardi. The rings under consideration need not be commutative, but are assumed to be coherent and strongly discrete: that is, they admit a membership test for every finitely generated ideal. As a complement to the proof, we provide a prime decomposition for commutative rings possessing the finite-depth property.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 24 , Issue 2 , April 2014 , e240206
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The final version of this paper was produced within a project funded by the Centre de Coopération Universitaire Franco-Bavarois, alias Bayerisch-Französisches Hochschulzentrum, when Peter Schuster was working at the Mathematisches Institut der Universität München.

References

Adams, W. W. and Loustaunau, P. (1994) An Introduction to Gröbner Bases, Graduate Studies in Mathematics 3, American Mathematical Society.CrossRefGoogle Scholar
Berger, U. (2004) A computational interpretation of open induction. In: Titsworth, F. (ed.) Proceedings of the Ninetenth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Publications 326–334.Google Scholar
Buchberger, B. (1965) Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Dissertation, Universität Innsbruck.Google Scholar
Coquand, T. (1992) Constructive topology and combinatorics. In: Myers, J. P. Jr. and O'Donnell, M. J. (eds.) Constructivity in Computer Science, Proceedings Summer Symposium San Antonio, TX, 1991. Springer-Verlag Lecture Notes in Computer Science 613 159–164.CrossRefGoogle Scholar
Coquand, T. and Lombardi, H. (2006) A logical approach to abstract algebra. Mathematical Structures in Computer Science 16 885–900.CrossRefGoogle Scholar
Coquand, T. and Persson, H. (1999) Gröbner bases in type theory. In: Altenkirch, T.et al. (eds.) Types for proofs and programs, Proceedings, TYPES, Irsee 1998. Springer-Verlag Lecture Notes in Computer Science 1657 33–46.Google Scholar
Edwards, H. M. (2005) Essays in Constructive Mathematics, Springer.Google Scholar
Glaz, S. (1989) Commutative Coherent Rings, Springer.CrossRefGoogle Scholar
Hadj Kacem, A. and Yengui, I. (2010) Dynamical Gröbner bases over Dedekind rings. Journal of Algebra 324 12–24.CrossRefGoogle Scholar
Hendtlass, M. and Schuster, P. (2012) A direct proof of Wiener's theorem. In: Cooper, S.et al. (eds.) How the World Computes: Proceedings, CiE 2012, Turing Centenary Conference and Eighth Conference on Computability in Europe, Cambridge. Springer-Verlag Lecture Notes in Computer Science 7318 294–303.Google Scholar
Jacobsson, C. and Löfwall, C. (1991) Standard bases for general coefficient rings and a new constructive proof of Hilbert's basis theorem. Journal of Symbolic Computation 12 (3)337–372.CrossRefGoogle Scholar
Kaplansky, I. (1974) Commutative Rings, Revised edition, The University of Chicago Press.Google Scholar
Lombardi, H. and Perdry, H. (1998) The Buchberger algorithm as a tool for ideal theory of polynomial rings in constructive mathematics. In: Buchberger, B. and Winkler, F. (eds.) Gröbner Bases and Applications, London Mathematical Society Lecture Note Series 251 393–407.CrossRefGoogle Scholar
Lombardi, H. and Quitté, C. (2011) Algèbre commutative. Méthodes constructives. Modules projectifs de type fini, Calvage et Mounet.Google Scholar
Lombardi, H., Yengui, I. and Schuster, P. (2012) The Gröbner ring conjecture in one variable. Mathematische Zeitschrift 270 1181–1185.CrossRefGoogle Scholar
Mines, R., Richman, F. and Ruitenburg, W. (1988) A Course in Constructive Algebra, Springer.CrossRefGoogle Scholar
Perdry, H. (2004) Strongly Noetherian rings and constructive ideal theory. Journal of Symbolic Computation 37 (4)511–535.CrossRefGoogle Scholar
Perdry, H. (2008) Lazy bases: a minimalist constructive theory of Noetherian rings. Mathematical Logic Quarterly 54 (1)70–82.CrossRefGoogle Scholar
Perdry, H. and Schuster, P. (2011) Noetherian orders. Mathematical Structures in Computer Science 21 111–124.CrossRefGoogle Scholar
Raoult, J.-C. (1988) Proving open properties by induction. Information Processing Letters 29 19–23.CrossRefGoogle Scholar
Richman, F. (1974) Constructive aspects of Noetherian rings. Proceedings of the American Mathematical Society 44 436–441.CrossRefGoogle Scholar
Richman, F. (2003) The ascending tree condition: constructive algebra without countable choice. Communications in Algebra 31 1993–2002.CrossRefGoogle Scholar
Schuster, P. (2012) Induction in algebra: a first case study. In: Proceedings 27th Annual ACM/IEEE Symposium on Logic in Computer Science: LICS 2012, IEEE Computer Society Publications 581–585CrossRefGoogle Scholar
Schuster, P. and Zappe, J. (2006) Do Noetherian rings have Noetherian basis functions? In: Beckmann, A.et al. (eds.) Logical Approaches to Computational Barriers: Proceedings Second Conference on Computability in Europe – CiE 2006. Springer-Verlag Lecture Notes in Computer Science 3988 481–489.CrossRefGoogle Scholar
Seidenberg, A. (1974) What is Noetherian? Rendiconti del Seminario Matemàtico e Fisico di Milano 44 55–61.CrossRefGoogle Scholar
Tennenbaum, J. (1973) A Constructive Version of Hilbert's Basis Theorem, Ph.D. thesis, University of California San Diego.Google Scholar
Yengui, I. (2006) Dynamical Gröbner bases. Journal of Algebra 301 447–458.CrossRefGoogle Scholar
Zariski, O. and Samuel, P. (1958) Commutative Algebra I, Van Nostrand.Google Scholar