Gröbner bases and convex polytopes.

*(English)*Zbl 0856.13020
University Lecture Series. 8. Providece, RI: American Mathematical Society (AMS). xi, 162 p. (1996).

Gröbner bases are distinguished bases of ideals in polynomial rings. Let \(k\) be a field, \(k[X]\) the polynomial ring with variables \(X_1, \dots, X_n\). The polynomial ring can be identified with the semigroup ring of \(\mathbb{N}^n\) with coefficients in \(k\); the set of monomials is then identified with the set of lattice points \(\mathbb{N}^n \subseteq \mathbb{R}^n\). The definition of a Gröbner basis refers to an admissible order of \(\mathbb{N}^n\), i.e., a total order of the semigroup \(\mathbb{N}^n\) with 0 as the smallest element. A finite subset \(G \subseteq I\), \(I \subset k[X]\) an ideal, is a universal Gröbner basis of \(I\) if it is a Gröbner basis with respect to every admissible order. Gröbner bases were first introduced as a computational tool in algebra and algebraic geometry. By now they have developed into a thriving branch of commutative algebra. The message of the book is that even beyond commutative algebra there is a wide range of substantial connections with other mathematical topics, such as combinatorics, convexity, algebraic topology, probability, and integer programming.

Most of the book is concerned with toric ideals: Any homomorphism \(\pi:\mathbb{N}^n \to \mathbb{Z}^d\) of semigroups induces a homomorphism \(\widehat \pi:k[X] \to k[\mathbb{Z}^d]\) of semigroup rings. The kernels of such homomorphisms are toric ideals. They are generated by differences of two monomials. There is a close relationship with toric varieties; one chapter is devoted to a careful analysis of this relationship. Gröbner bases can be used to develop algorithms for some natural equations concerning the homomorphism \(\pi\) (What is the cardinality of a fibre? Find a random point in a fibre! Find a point in a fibre which is optimal with respect to some cost functional!). The basic method of the book is to associate geometric objects, such as convex polytopes or simplicial complexes, with toric ideals or, more generally, ideals in \(k[X]\). Gröbner bases can be used to study these geometric objects, and vice versa. One example for the beautiful results that can be found in this area is the following:

Theorem. Suppose that \(\pi (\mathbb{N}^n) \subseteq \mathbb{N}^d \backslash \{0\}\), that \(u,v\in \mathbb{N}^n\) have disjoint support, that the components of \(u-v\) are relatively prime and that \(\pi(u) = \pi(v)\). Then \(X^u-X^v\) belongs to the universal Gröbner basis of \(\ker (\widehat \pi)\) if and only if the line segment \([u,v]\) is an edge of the convex hull of \(\pi^{-1} (\pi (u))\) in \(\mathbb{R}^n\).

Results such as this show that the methods discussed in the book lead to substantial conceptual insights. On the other hand, plentiful algorithms and explicit computations are evidence that the subject of Gröbner bases has firm roots in a tradition of practical computations.

The book is not entirely free of errors. In the early chapters, in particular in connection with the introduction of the state polytope, the author is a bit careless about the basic ingredients of Gröbner bases. As pointed out, a Gröbner basis always refers to an admissible order of \(\mathbb{N}^n\). In the proofs of proposition 1.13 and proposition 2.3, for example, Gröbner bases are being used with respect to relations that, in general, are definitely not admissible orders.

Most of the book is concerned with toric ideals: Any homomorphism \(\pi:\mathbb{N}^n \to \mathbb{Z}^d\) of semigroups induces a homomorphism \(\widehat \pi:k[X] \to k[\mathbb{Z}^d]\) of semigroup rings. The kernels of such homomorphisms are toric ideals. They are generated by differences of two monomials. There is a close relationship with toric varieties; one chapter is devoted to a careful analysis of this relationship. Gröbner bases can be used to develop algorithms for some natural equations concerning the homomorphism \(\pi\) (What is the cardinality of a fibre? Find a random point in a fibre! Find a point in a fibre which is optimal with respect to some cost functional!). The basic method of the book is to associate geometric objects, such as convex polytopes or simplicial complexes, with toric ideals or, more generally, ideals in \(k[X]\). Gröbner bases can be used to study these geometric objects, and vice versa. One example for the beautiful results that can be found in this area is the following:

Theorem. Suppose that \(\pi (\mathbb{N}^n) \subseteq \mathbb{N}^d \backslash \{0\}\), that \(u,v\in \mathbb{N}^n\) have disjoint support, that the components of \(u-v\) are relatively prime and that \(\pi(u) = \pi(v)\). Then \(X^u-X^v\) belongs to the universal Gröbner basis of \(\ker (\widehat \pi)\) if and only if the line segment \([u,v]\) is an edge of the convex hull of \(\pi^{-1} (\pi (u))\) in \(\mathbb{R}^n\).

Results such as this show that the methods discussed in the book lead to substantial conceptual insights. On the other hand, plentiful algorithms and explicit computations are evidence that the subject of Gröbner bases has firm roots in a tradition of practical computations.

The book is not entirely free of errors. In the early chapters, in particular in connection with the introduction of the state polytope, the author is a bit careless about the basic ingredients of Gröbner bases. As pointed out, a Gröbner basis always refers to an admissible order of \(\mathbb{N}^n\). In the proofs of proposition 1.13 and proposition 2.3, for example, Gröbner bases are being used with respect to relations that, in general, are definitely not admissible orders.

Reviewer: N.Schwartz (Passau)

##### MSC:

13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |

14M25 | Toric varieties, Newton polyhedra, Okounkov bodies |

52B20 | Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) |

90C10 | Integer programming |

13-02 | Research exposition (monographs, survey articles) pertaining to commutative algebra |