Kreuzer, Martin; Robbiano, Lorenzo
Computational commutative algebra. 1. (English. English summary)
Springer-Verlag, Berlin, 2000. x+321 pp. $39.95. ISBN 3-540-67733-X

The past ten years have seen the publication of a number of textbooks and monographs containing treatments of the theory of Grobner bases, other aspects of computational commutative algebra, and applications of these topics to various problems in pure and applied mathematics. Several of these books, including those by T. Becker and V. Weispfenning [Grobner bases, Springer, New York, 1993; MR95e:13018], R. Froberg [An introduction to Grobner bases, Wiley, Chichester, 1997; MR99d:13032], and W. W. Adams and P. Loustaunau [ An introduction to Grobner bases, Amer. Math. Soc., Providence, RI, 1994; MR95g:13025] have focused on the theory of Grobner bases for polynomial ideals and modules over polynomial rings as a foundation for the algebra and have presented constructive approaches to basic algebraic problems such as deciding ideal or module membership, computing ideal or module intersections, homomorphisms, syzygies, and so forth, together with selected applications.

Several other texts such as those by B. Mishra [Algorithmic algebra, Springer, New York, 1993; MR94j:68127] and F. Winkler [Polynomial algorithms in computer algebra, Springer, Vienna, 1996; MR97j:68063] have covered many of the same topics, but have approached them as part of the repertoire of computer algebra. These books have presented Buchberger's algorithm for computing Grobner bases along with Wu's algorithm for characteristic sets, other techniques including resultants, factorization algorithms, and so forth.

One of the earliest of these books to appear, by D. A. Cox, J. B. Little and D. B. O'Shea [Ideals, varieties, and algorithms, Springer, New York, 1992; MR93j:13031; second edition, 1996, MR97h:13024], aimed specifically to make these ideas accessible to students at the (U.S.) undergraduate level, and presented Grobner bases, resultants, and other computational techniques in the context of elementary affine algebraic geometry and its applications. More advanced treatments tailored for applications to algebraic geometry appeared subsequently in Chapter 15 of the book by D. Eisenbud [Commutative algebra, Springer, New York, 1995; MR97a:13001] and in the book by W. V. Vasconcelos [Computational methods in commutative algebra and algebraic geometry, Springer, Berlin, 1998; MR99c:13048]. Even more recently, D. A. Cox, J. B. Little and D. B. O'Shea [Using algebraic geometry, Springer, New York, 1998; MR99h:13033] included presentations of the theory of standard bases for local rings, Grobner bases for modules, multipolynomial resultants, and additional applications.

The listing in the previous paragraphs is not intended to be exhaustive. For instance, it does not include Bernd Sturmfels' books on invariant theory and Grobner bases and convex polytopes where the theory is applied to other subjects. But it does show that the book under review faces some stiff "competition" from existing texts. In this situation, a new entrant in an already somewhat crowded field should ideally have a distinctive style or point of view. Kreuzer and Robbiano do not disappoint on this score.

Unlike most of the books above, Kreuzer and Robbiano begin from the important idea that Grobner basis theory is fundamentally a theory about modules over polynomial rings. For instance, as is well understood, even if one is primarily interested in computing Grobner bases for polynomial ideals, Buchberger's criterion (the statement that $G$ is a Grobner basis if and only if all the S-polynomials of pairs of elements of $G$ reduce to 0 on division by $G$) and hence the structure of Buchberger's algorithm for computing a Grobner basis from an arbitrary basis for an ideal, can perhaps be best understood by using the concept of syzygies. Hence modules over polynomial rings enter the picture almost immediately. For this reason, the authors choose to develop Grobner bases in one pass, treating the ideal and module cases simultaneously. This approach leads to an admirably unified presentation. However, it also requires a rather high level of sophistication on the part of potential readers, since the module theory comes with a higher overhead (both conceptually and in terms of notation). Even though the authors have tried to make their presentation largely self-contained, in the reviewer's opinion the mathematical maturity level provided by a solid abstract algebra course is a prerequisite for understanding some sections of this book. Nevertheless, readers who master the presentation in this text will have a varied and sophisticated toolkit of ideas to apply to further study. (The reviewer wonders why the authors did not facilitate such further study by providing a more extensive bibliography, however. Kreuzer and Robbiano have chosen not to give attributions for any of the results and not to provide pointers to the literature, so it would be difficult for a student reading this book to see where to go next to continue to learn about further developments.)

Another distinctive feature of Kreuzer and Robbiano's book is the inclusion of 44 "tutorials" based on the CoCoA computer algebra system throughout the book. (There is at least one, and often two or three, of these at the end of each section, together with a selection of more routine exercises.) The tutorials are essentially guided programming projects in which the reader is invited to implement algorithms described in the text or in the tutorial itself and to apply those programs to compute examples and explore. Some of the tutorials involve applications to topics such as graph colorings, integer programming, toric ideals, Grassmannians, primary decompositions, and even modern portfolio theory(!) Three appendices provide more details about the structure and syntax of CoCoA.

Finally, the style of this book merits a comment. As the authors point out in the introduction, each section of each chapter begins with a quotation and an overview section in which "Italian imagination overtakes German rigor". These introductions and the following main bodies of each section are well written, engaging, and often amusing. The book is a pleasure to read.

The structure of the book is as follows. Chapter 1 lays the algebraic foundations, starting with properties of polynomial rings. Monomial ideals and modules are studied next. Term orderings in the ideal and module cases are introduced almost simultaneously, following the philosophy that Grobner basis theory is inherently a theory about modules. The first chapter concludes with sections on the division algorithm and gradings on modules.

Chapter 2 is devoted to the theory of Grobner bases. Three different notions of a "special set of generators" $\{g_1,\dots,g_s\}$ for a submodule $M$ of a free module over a polynomial ring are introduced at the start. In Section 1, sets with the property that the leading terms of the $g_i$ generate the monomial submodule of leading terms of $M$ are studied. Then the division algorithm is reconsidered from the point of view of "rewrite rules" on polynomials and the sets of divisors for which the rewrite relation is confluent are singled out. Finally, sets of generators for which every syzygy on the leading terms of the generators "lifts" to a syzygy on the generators themselves are introduced. The equivalence of all three notions is proved and this provides the definition of a Grobner basis. Sections on Buchberger's algorithm and the Hilbert Nullstellensatz round out this chapter.

Chapter 3 is devoted to a selection of first applications of the theory from the previous chapters: computation of syzygy modules, intersections, colon ideals and colon modules, homomorphisms, elimination theory, localization and saturation, and solving systems of polynomial equations.

This is the first in a projected series of volumes on this subject. Numerous hints about the contents of Volume 2 are provided, and the reviewer looks forward with pleasure to reading the next installment.

Reviewed by John B. Little