Gröbner Bases: A Computational Approach to Commutative Algebra

The origins of the mathematics in this book date back more than two thou­ sand years, as can be seen from the fact that one of the most important algorithms presented here bears the name of the Greek mathematician Eu­ clid. The word "algorithm" as well as the key word "algebra" in the title of this book come from the name and the work of the ninth-century scientist Mohammed ibn Musa al-Khowarizmi, who was born in what is now Uzbek­ istan and worked in Baghdad at the court of Harun al-Rashid's son. The word "algorithm" is actually a westernization of al-Khowarizmi's name, while "algebra" derives from "al-jabr," a term that appears in the title of his book Kitab al-jabr wa'l muqabala, where he discusses symbolic methods for the solution of equations. This close connection between algebra and al­ gorithms lasted roughly up to the beginning of this century; until then, the primary goal of algebra was the design of constructive methods for solving equations by means of symbolic transformations. During the second half of the nineteenth century, a new line of thought began to enter algebra from the realm of geometry, where it had been successful since Euclid's time, namely, the axiomatic method.

Table of Contents:
0 Basics.- 0.1 Natural Numbers and Integers.- 0.2 Maps.- 0.3 Mathematical Algorithms.- Notes.- 1 Commutative Rings with Unity.- 1.1 Why Abstract Algebra?.- 1.2 Groups.- 1.3 Rings.- 1.4 Subrings and Homomorphisms.- 1.5 Ideals and Residue Class Rings.- 1.6 The Homomorphism Theorem.- 1.7 Gcd’s, Lcm’s, and Principal Ideal Domains.- 1.8 Maximal and Prime Ideals.- 1.9 Prime Rings and Characteristic.- 1.10 Adjunction, Products, and Quotient Rings.- Notes.- 2 Polynomial Rings.- 2.1 Definitions.- 2.2 Euclidean Domains.- 2.3 Unique Factorization Domains.- 2.4 The Gaussian Lemma.- 2.5 Polynomial Gcd’s.- 2.6 Squarefree Decomposition of Polynomials.- 2.7 Factorization of Polynomials.- 2.8 The Chinese Remainder Theorem.- Notes.- 3 Vector Spaces and Modules.- 3.1 Vector Spaces.- 3.2 Independent Sets and Dimension.- 3.3 Modules.- Notes.- 4 Orders and Abstract Reduction Relations.- 4.1 The Axiom of Choice and Some Consequences in Algebra.- 4.2 Relations.- 4.3 Foundedness Properties.- 4.4 Some Special Orders.- 4.5 Reduction Relations.- 4.6 Computing in Algebraic Structures.- Notes.- 5 Gröbner Bases.- 5.1 Term Orders and Polynomial Reductions.- 5.2 Gröbner Bases—Existence and Uniqueness.- 5.3 Gröbner Bases—Construction.- 5.4 Standard Representations.- 5.5 Improved Gröbner Basis Algorithms.- 5.6 The Extended Gröbner Basis Algorithm.- Notes.- 6 First Applications of Gröbner Bases.- 6.1 Computation of Syzygies.- 6.2 Basic Algorithms in Ideal Theory.- 6.3 Dimension of Ideals.- 6.4 Uniform Word Problems.- Notes.- 7 Field Extensions and the Hilbert Nullstellensatz.- 7.1 Field Extensions.- 7.2 The Algebraic Closure of a Field.- 7.3 Separable Polynomials and Perfect Fields.- 7.4 The Hilbert Nullstellensatz.- 7.5 Height and Depth of Prime Ideals.- 7.6 Implicitization of RationalParametrizations.- 7.7 Invertibility of Polynomial Maps.- Notes.- 8 Decomposition, Radical, and Zeroes of Ideals.- 8.1 Preliminaries.- 8.2 The Radical of a Zero-Dimensional Ideal.- 8.3 The Number of Zeroes of an Ideal.- 8.4 Primary Ideals.- 8.5 Primary Decomposition in Noetherian Rings.- 8.6 Primary Decomposition of Zero-Dimensional Ideals.- 8.7 Radical and Decomposition in Higher Dimensions.- 8.8 Computing Real Zeroes of Polynomial Systems.- Notes.- 9 Linear Algebra in Residue Class Rings.- 9.1 Gröbner Bases and Reduced Terms.- 9.2 Computing in Finitely Generated Algebras.- 9.3 Dimensions and the Hilbert Function.- Notes.- 10 Variations on Gröbner Bases.- 10.1 Gröbner Bases over PID’s and Euclidean Domains.- 10.2 Homogeneous Gröbner Bases.- 10.3 Homogenization.- 10.4 Gröbner Bases for Polynomial Modules.- 10.5 Systems of Linear Equations.- 10.6 Standard Bases and the Tangent Cone.- 10.7 Symmetric Functions.- Notes.- Appendix: Outlook on Advanced and Related Topics.- Complexity of Gröbner Basis Constructions.- Term Orders and Universal Gröbner Bases.- Comprehensive Gröbner Bases.- Gröbner Bases and Automatic Theorem Proving.- Characteristic Sets and Wu-Ritt Reduction.- Term Rewriting.- Standard Bases in Power Series Rings.- Non-Commutative Gröbner Bases.- Gröbner Bases and Differential Algebra.- Selected Bibliography.- Conference Proceedings.- Books and Monographs.- Articles.- List of Symbols.