Gröbner Bases

Neither specialist knowledge nor extensive investment of time is required in order for a nonspecialist to learn fundamentals on Gröbner bases. The purpose of this chapter is to provide the reader with sufficient understanding of the theory of Gröbner bases as quickly as possible with the assumption of only a minimum of background knowledge. In Sect. 1.1, the story starts with Dickson’s Lemma, which is a classical result in combinatorics. The Gröbner basis is then introduced and Hilbert Basis Theorem follows. With considering the reader who is unfamiliar with the polynomial ring, an elementary theory of ideals of the polynomial ring is also reviewed. In Sect. 1.2, the division algorithm, which is the framework of Gröbner bases, is discussed with a focus on the importance of the remainder when performing division. The highlights of the fundamental theory of Gröbner bases are, without doubt, Buchberger criterion and Buchberger algorithm. In Sect. 1.3 the groundwork of these two items are studied. Now, to read Sects. 1.1–1.3 is indispensable for being a user of Gröbner bases. Furthermore, in Sect. 1.4, the elimination theory, which is effective technique for solving simultaneous equations, is discussed. The toric ideal introduced in Sect. 1.5 is a powerful weapon for the application of Gröbner bases to combinatorics on convex polytopes. Clearly, without toric ideals, the results of Chaps. 4 and 4 could not exist. The Hilbert function studied in Sect. 1.6 is the most fundamental tool for developing computational commutative algebra and computational algebraic geometry. Section 1.6 supplies the reader with sufficient preliminary knowledge to read Chaps. 5 and  6. However, since the basic knowledge of linear algebra is required for reading Sect. 1.6, the reader who is unfamiliar with linear algebra may wish to skip Sect. 1.6 in his/her first reading. Finally, in Sect. 1.7, the historical background of Gröbner bases is surveyed with providing references for further study.

In Chap. 1, we studied the basic theory of Gröbner bases. Our goal is to use mathematical software to further our research. In this chapter, we will begin with warm-up drills in order to learn the basic ideas necessary for using mathematical software. We will use MathLibre, a mathematical software environment. It is a collection of mathematical software and free documents which form a kind of Live Linux system. The Linux operating system is compatible with UNIX, and many mathematical research systems have been developed on a UNIX system. It is thus important to know the command line interface, Emacs editor, and the fundamental ideas of the UNIX environment. If you are already familiar with this environment, you can skip this chapter; otherwise, please try and enjoy the world of MathLibre.

In Chap. 1, we presented the theoretical foundation of Gröbner bases, and many of our computations were carried out by hand. When we want to apply Gröbner bases to practical problems, however, in most cases, we will need the help of computers. There are many mathematical software systems which support the computation of Gröbner bases, but we will often encounter cases which require careful settings or preprocessing in order to be efficient. In this chapter, we explain various methods to efficiently use a computer to compute Gröbner bases. We also present some algorithms for performing operations on the ideals realized by Gröbner bases. These operations are implemented in several mathematical software systems: Singular, Macaulay2, CoCoA, and Risa/Asir. We will illustrate the usage of these systems mainly by example.

Gröbner bases of toric ideals have applications in many research areas. Among them, one of the most important topics is the correspondence to triangulations of convex polytopes. It is very interesting that, not only do Gröbner bases give triangulations, but also “good” Gröbner bases give “good” triangulations (unimodular triangulations). On the other hand, in order to use polytopes to study Gröbner bases of ideals of polynomial rings, we need the theory of Gröbner fans and state polytopes. The purpose of this chapter is to explain these topics in detail. First, we will explain convex polytopes, weight vectors, and monomial orders, all of which play a basic role in the rest of this chapter. Second, we will study the Gröbner fans of principal ideals, homogeneous ideals, and toric ideals; this will be useful when we analyze changes of Gröbner bases. Third, we will discuss the correspondence between the initial ideals of toric ideals and triangulations of convex polytopes, and the related ring-theoretic properties. Finally, we will consider the examples of configuration matrices that arise from finite graphs or contingency tables, and we will use them to verify the theory stated above. If you would like to pursue this topic beyond what is included in this chapter, we suggest the books [2, 7].

We introduce the theory and present some applications of Gröbner bases for the rings of differential operators with rational function coefficients R and for those with polynomial coefficients D. The discussion with R, in the first half, is elementary. In the ring of polynomials, zero-dimensional ideals form the biggest class, and this is also true in R. However, in D, there is no zero-dimensional ideal, and holonomic ideals form the biggest class. Most algorithms for D use holonomic ideals. As an application, we present an algorithm for finding local minimums of holonomic functions; it can be applied to the maximum-likelihood estimate. The last part of this chapter considers A-hypergeometric systems; topics covered in other chapters will reappear in the study of A-hypergeometric systems. We have provided many of the proofs, but some technical proofs in the second half of this chapter have been omitted; these may be found in the references at the end of this chapter.

There are two aspects to the study of Gröbner bases: theory and computation. For problems which are difficult to solve by theoretical approaches, it may be possible to obtain solutions by computation, using either brute force or more elegant methods. On the other hand, for problems for which the computational methods are difficult, it may be possible to obtain solutions by a combination of theoretical insight and calculations. This is one of the attractions of Gröbner bases. Chapters 4–6 emphasized the theoretical aspect. In this chapter, we present problems and answers which utilize various software systems. It is our hope that readers will perform the calculations on these software systems while studying this chapter. Following these problems and their answers, we provide easy exercises which will help the reader to understand how to use these software systems to study or apply Gröbner bases. We will use computer algebra systems, statistical software systems, and some expert systems for polytopes and toric ideals; this covers several areas related to the theory and applications of Gröbner bases.