Introduction

SAGBI-Gröbner bases are simply the counterparts in ideals of subalgebras of polynomial rings to Gröbner bases of ideals of the full polynomial ring. Our intrinsic development of SAGBI-Gröbner theory will mimic that of ordinary Gröbner bases, an approach that has a certain aesthetic appeal. In addition, this parallel development provides another point of view from which to study the mechanics of Gröbner basis theory, which was first presented in an algorithmic fashion by Buchberger (1965) (see also Buchberger (1985)).

We assume little experience with Gröbner bases on the part of the reader; an overview of the subject may be found in the texts of Adams and Loustaunau (1994), Becker and Weispfennig (1993), and Cox, Little, and O'Shea (1992).

Introduction: Some Motivating Examples

The main difficulty in the studying the finitely presented noncommutative algebras is that in general most of the problems are unsolvable. For an illustration, consider the following example.

Example 1(Tsejtin, 1958) Let

A = 〈a, b, c, d|ac = ca, ad = da, bc = cb, bd = db, eca = ce, edb = de, cca = ccae〉.

It is impossible to give an algorithm determining whether two given words in the alphabet a, b, c, d, e are equal in the algebra A.

Nevertheless rather often (e.g. in the commutative or finite-dimensional cases) we are able to solve the corresponding word problem. The reason for this is the regular behaviour of the Gröbner bases in those cases. The aim of this article is to describe how to construct, analyse and use Gröbner bases in noncommutative algebras.

Let A = 〈X|R〉 be a finitely presented associative algebra over the field K. If I is the ideal generated by R in the free algebra K〈X〉 then A is isomorphic to the factor-algebra K〈X〉/I and every element of A can be presented as a linear combination of words in the alphabet X. Example 1 shows that one of the most important questions – which linear combinations present the same element in A – is far from trivial.

Introduction

In this article, we study the initial ideals of generic and “almost generic” ideals with respect to the (total degree, then) reverse lexicographic term order. For a generic ideal I ⊂ K[x1,…, xn], generated by r ≤ n forms, there is a well-known conjecture on how gr(I) looks like. In particular, gr(I) is minimally generated in K[x1,…, xr]. We interpret this result in the setting of the ring R′, introduced in [12]: this ring, which is a proper subring on the power series ring on countably many variables, and which properly contains the polynomial ring on the same set of indeterminates, is the habitat of “generic forms in countably many indeterminates”.

Introduction

Whenever two branches of Science meet it is a great time for research. Sometimes such events are unexpected, sometimes they are more natural. In this survey I will try to set up a foundation for a fruitful interaction between Design of Experiments (DoE) on one side and Commutative Algebra, Algebraic Geometry and Computer Algebra on the other. DoE is a branch of Statistics, and in its history algebraic methods are not rare, so this kind of interaction falls into the category of natural events. Furthermore, it is now clear how strong was, and still is, the influence of Computer Algebra methods in Commutative Algebra and Algebraic Geometry: for instance Gröbner basis theory, which originated with the fundamental work by Buchberger (see Buchberger (1965), Buchberger (1970) and Buchberger (1985)), is nowadays recognized to be a basic tool applicable in several sectors of Science. From now on we can say that this influence extends into the realm of DoE.

Let us have a look at the main concepts in DoE by discussing an example. Suppose that a firm wants to introduce a new product, say a portable telephone, into the market. They need to obtain useful a priori information from the potential customers.

Introduction

In the late 1960's, Risch (1969, 1970) developed an algorithm for symbolic indefinite integration. The approach followed there consists in computing a tower of differential extensions in order to determine if an indefinite integral can be expressed in terms of elementary functions. Risch's algorithm became very popular and is now at the heart of the integration routines of many computer algebra systems. In the early 1980's, Karr (1981, 1985) appealed to similar ideas, namely difference extensions, in order to develop an algorithm for symbolic indefinite summation. Despite its indisputable algorithmic interest, Karr's algorithm has unfortunately not received as much attention as it deserves yet, due to its complexity and the difficulty to implement it.

In the early 1990's, Zeilberger (1990b) initiated a different approach to symbolic summation and integration. As opposed to the approach by differential or difference extensions, Zeilberger studies the action of algebras of differential or difference linear operators in order to compute special operators that determine the sum or integral under consideration.

Introduction

Computing Gröbner bases, syzygies, and finite free resolutions of ideals and of submodules of finitely generated free modules over polynomial rings is a fundamental task in Computational Commutative Algebra. Nowadays there are several specialized computer algebra systems, developed by researchers in the field, which efficiently perform such computations, for instance Asir (Noro and Takeshima 1992), CoCoA (Capani et al. 1996), Macaulay (Bayer and Stillman 1992), Macaulay 2 (Grayson and Stillman 1996), Singular (Greuel et al. 1996).

The cornerstone in this area has been the (now) classical algorithm due to Buchberger (1965) which produces a Gröbner basis of an ideal in a polynomial ring R over a field, starting from any of its possible finite sets of generators. This algorithm can be suitably modified (Schreyer 1980, Spear 1977) in such a way that it also computes the syzygy module of a list of polynomials.

Introduction

The notion of Gröbner basis and related techniques are remarkable contributions to the solution of problems by algorithmic way in polynomial ideal theory. The greatest number of applications of the Gröbner bases method have been, for the time being, in commutative polynomial algebras. In Mora F. (1986), the concept of Gröbner basis has been generalized to noncommutative free algebras, allowing to extend the field of applications. Many Gröbner bases results, for the commutative case, are based on the well known Elimination Ideal Property of these bases; Buchberger B. (1987), Gianni P. et al. (1988), Shannon D. et al. (1988), Kalkbrener M. (1991), are some examples. In this paper we show how this property can be gene- ralized to free associative K-algebras and, by means of some applications, illustrate that this generalized property could become similarly applicable as its starting point in commutative polynomial rings.

Introduction

Reasoning and computing in finitely presented algebraic structures is wide-spread in many fields in mathematics, physics and computer science. Reduction in the sense of simplification combined with appropriate completion methods is one general technique which is often successfully applied in this context, e.g. to solve the word problem and hence to compute effectively in the structure.

One fundamental application of this technique to polynomial rings was provided by B. Buchberger (1965) in his uniform effective solution of the ideal membership problem establishing the theory of Gröbner bases. These bases can be characterized in various manners, e.g. by properties of a reduction relation associated with polynomials (confluence or all elements in the ideal reduce to zero) or by special representations for the ideal elements with respect to a Gröbner basis (standard representations).

Outline

A comprehensive treatment of Gröbner bases theory is far beyond what can be done in one article in a book. Recent text books on Gröbner bases like (Becker, Weispfenning 1993) and (Cox, Little, O'Shea 1992) present the material on several hundred pages. However, there are only a few key ideas behind Gröbner bases theory. It is the objective of this introduction to explain these ideas as simply as possible and to give an overview of the immediate applications. More advanced applications are described in the other tutorial articles in this book.

The concept of Gröbner bases together with the characterization theorem (by “S-polynomials”) on which an algorithm for constructing Gröbner bases hinges has been introduced in the author's PhD thesis (Buchberger 1965), see also the journal publication (Buchberger 1970). In these early papers we also gave some first applications (computation in residue class rings modulo polynomial ideal congruence, algebraic equations, and Hilbert function computation), a computer implementation (in the assembler language of the ZUSE Z23V computer), and some first remarks on complexity. Later work by the author and by many other authors has mainly added generalizations of the method and quite a few new applications for the algorithmic solution of various fundamental problems in algebraic geometry (polynomial ideal theory, commutative algebra).

Introduction

In the 33 years since their introduction by Buchberger (1965, 1970), Gröbner bases have been applied successfully in various fields of Mathematics and to many types of problems. This paper wants to go the opposite way by presenting a different approach to Gröbner bases for zero dimensional ideals from the quite recent theory of polynomial interpolation of minimal degree. The latter one is an approach introduced by de Boor and Ron (1990, 1992) to solve interpolation problems defined by a finite number of linear functionals using appropriate polynomial spaces with certain useful properties.

Let me briefly explain this with the example of Lagrange interpolation in ℝd. Suppose that a finite set of pairwise disjoint points {x0, …, xN} ∈ ℝd is given. The Lagrange interpolation problem consists of finding, for any y0, …, yN, a polynomial p such that p(xj) = yi, j = 0,…, N. Clearly, this problem is always solvable and even has infinitely many solutions. The “real” question, however, is to find a polynomial subspace P such that for any given data the Lagrange interpolation problem has a unique solution in P and to choose P “as simple as possible”.

Introduction

The problem of decomposing a function f into functions g and h such that f = g o h is the functional composition hereof has been studied by various authors, as Dickerson (1989) for the case when f is a multivariate polynomial over a field, Zippel (1991) for f a univariate rational function or Kozen et al. (1996) for f a univariate algebraic function.