An Introduction to Grobner Bases
W.W. Adams and P. Loustaunau
Graduate Studies in Mathematics, Vol. 3
American Mathematical Society, 289 p., 1994.
Order Information

Table of Contents

Errata.

Preface
We wrote this book with two goals in mind:

1. To give a leisurely and fairly comprehensive introduction to the definition and construction of Grobner bases;
2. To discuss applications of Grobner bases by presenting computational methods to solve problems which involve rings of polynomials.

This book is designed to be a first course in the theory of Grobner bases suitable for an advanced undergraduate or a beginning graduate student. This book is also suitable for students of computer science, applied mathematics, and engineering who have some acquaintance with modern algebra. The book does not assume an extensive knowledge of algebra. Indeed, one of the attributes of this subject is that it is very accessible. In fact, all that is required is the notion of the ring of polynomials in several variables (and rings in general in a few places, in particular in Chapter 4) together with the ideals in this ring and the concepts of a quotient ring and of a vector space introduced at the level of an undergraduate abstract and linear algebra course. Except for linear algebra, even these ideas are reviewed in the text. Some topics in the later sections of Chapters 2, 3, and 4 require more advanced material. This is always clearly stated at the beginning of the section and references are given. Moreover, most of this material is reviewed and basic theorems are stated without proofs.

The book can be read without ever "computing" anything. The theory stands by itself and has important theoretical applications in its own right. However, the reader will not fully appreciate the power of, or get insight into, the methods introduced in the book without actually doing some of the computations in the examples and the exercises by hand or, more often, using a Computer Algebra System (there are over 120 worked-out examples and over 200 exercises). Computing is useful in producing and analyzing examples which illustrate a concept already understood, or which one hopes will give insight into a less well understood idea or technique. But the real point here is that computing is the very essence of the subject. This is why Grobner basis theory has become a major research area in computational algebra and computer science. Indeed, Grobner basis theory is generating increasing interest because of its usefulness in providing computational tools which are applicable to a wide range of problems in mathematics, science, engineering, and computer science.

Grobner bases were introduced in 1965 by Bruno Buchberger (Wolfgang Grobner was Bruno Buchberger's thesis advisor). The basic idea behind the theory can be described as a generalization of the theory of polynomials in one variable. In the polynomial ring k[x], where k is a field, any ideal I can be generated by a single element, namely the greatest common divisor of the elements of I. Given any set of generators f_1, f_2, ..., f_s for I, one can compute (using the Euclidean Algorithm) a single polynomial d=gcd(f_1,f_2,...,f_s) such that I= = . Then a polynomial f in k[x] is in I if and only if the remainder of the division of f by d is zero. Grobner bases are the analog of greatest common divisors in the multivariate case in the following sense. A Grobner basis for an ideal I in k[x_1,...,x_n] generates I and a polynomial f in k[x_1,...,x_n] is in I if and only if the remainder of the division of f by the polynomials in the Grobner basis is zero (the appropriate concept of division is a central aspect of the theory).

This abstract characterization of Grobner bases is only one side of the theory. In fact it falls far short of the true significance of Grobner bases and of the real contribution of Bruno Buchberger. Indeed, the ideas behind the abstract characterization of Grobner bases had been around before Buchberger's work. For example, Macaulay used some of these ideas at the beginning of the century to determine certain invariants of ideals in polynomial rings and Hironaka, in 1964, used similar ideas to study power series rings. But the true significance of Grobner bases is the fact that they can be computed. Bruno Buchberger's great contribution, and what gave Grobner basis theory the status as a subject in its own right, is his algorithm for computing these bases.

Our choice of topics is designed to give a broad introduction to the elementary aspects and applications of the subject. As is the case for most topics in commutative algebra, Grobner basis theory can be presented from a geometric point of view. We have kept our presentation algebraic except in Sections 1.1 and 2.5. For those interested in a geometric treatment of some of the theory we recommend the excellent book by D. Cox, J. Little and D. O'Shea. The reader who is interested in going beyond the contents of this book should use our list of references as a way to access other sources. We mention in particular the books by T. Becker and V. Weispfenning and by B. Mishra which contain a lot of material not in this book and have extensive lists of references on the subject.

Although this book is about computations in algebra, some of the issues which might be of interest to computer scientists are outside the scope of this book. For example, implementation of algorithms and their complexity are discussed only briefly in the book, primarily in Section 3.3. The interested reader should consult the references.

In Chapter 1 we give the basic introduction to the concept of a Grobner basis and show how to compute it using Buchberger's Algorithm. We are careful to give motivations for the definition and algorithm by giving the familiar examples of Gaussian elimination for linear polynomials and the Euclidean Algorithm for polynomials in one variable. In Chapter 2 we present the basic applications to algebra and elementary algebraic geometry. We close the chapter with three specialized applications to algebra, graph theory, and integer programming. In Chapter 3 we begin by using the concept of syzygy modules to give an improvement of Buchberger's Algorithm. We go on to show how to use Grobner bases to compute the syzygy module of a set of polynomials (this is solving diophantine equations over polynomial rings). We then develop the theory of Grobner bases for finitely generated modules over polynomial rings. With these, we extend the applications from the previous chapter, give more efficient methods for computing some of the objects from the previous chapter, and conclude by showing how to compute the Hom functor and free resolutions. In Chapter 4 we develop the theory of Grobner bases for polynomial rings when the coefficients are now allowed to be in a general Noetherian ring and we show how to compute these bases (given certain computability conditions on the coefficient ring). We show how the theory simplifies when the coefficient ring is a principal ideal domain. We also give applications to determining whether an ideal is prime and to computing the primary decomposition of ideals in polynomial rings in one variable over principal ideal domains.

There are exercises at the end of each section. Many of these exercises are computational in nature, some doable by hand while others require the use of a Computer Algebra System. Other exercises extend the theory presented in the book. A few harder exercises are marked with (*).

This book grew out of a series of lectures presented by the first author at the National Security Agency during the summer of 1991 and by the second author at the University of Calabria, Italy, during the summer of 1993.

We would like to thank many of our colleagues and students for their helpful comments and suggestions. In particular we would like to thank Beth Arnold, Ann Boyle, Garry Helzer, Karen Horn, Perpetua Kessy, Lyn Miller, Alyson Reeves, Elizabeth Rutman, Brian Williams, and Eric York. We also want to thank Sam Rankin, Julie Hawks and the AMS staff for their help in the preparation of the manuscript.

Table of Contents