In this survey I should like to introduce some concepts of algebraic geometry and try to demonstrate the fruitful interaction between algebraic geometry and computer algebra and, more generally, between mathematics and computer science. One of the aims of this article is to show, by means of examples, the usefulness of computer algebra to mathematical research.
Computer algebra itself is a highly diversified discipline with applications to various areas of mathematics; we find many of these in numerous research papers, in proceedings or in textbooks (cf. BWi,CCS,MGH,ISSAC). Here we concentrate mainly on Gröbner bases and leave aside many other topics of computer algebra (cf. DST,GG,GKW). In particular, we do not mention (multivariate) polynomial factorisation, another major and important tool in computational algebraic geometry. Gröbner bases were introduced originally by Buchberger as a computational tool for testing solvability of a system of polynomial equations, to count the number of solutions (with multiplicities) if this number is finite and, more algebraically, to compute in the quotient ring modulo the given polynomials. Since then, Gröbner bases have become the major computational tool, not only in algebraic geometry.
The importance of Gröbner bases for mathematical research in algebraic geometry is obvious and their use needs, nowadays, hardly any justification. Indeed, chapters on Gröbner bases and Buchberger's algorithm [Buchberger1965] have been incorporated in many new textbooks on algebraic geometry such as the books of CLO1,CLO2 or the recent books of Ei2,Va2, not to mention textbooks which are devoted exclusively to Gröbner bases, as AL,BWe,Fr.
Computational methods become increasingly important in pure mathematics and the above mentioned books have the effect that Gröbner bases and their applications become a standard part of university courses on algebraic geometry and commutative algebra. One of the reasons is that these methods, together with very efficient computers, allow the treatment of non-trivial examples and, moreover, are applicable to non-mathematical, industrial, technical or economical problems. Another reason is that there is a belief that algorithms can contribute to a deeper understanding of a problem. The human idea of ``understanding'' is clearly part of the historical, cultural and technical status of the society and nowadays understanding in mathematics requires more and more algorithmic treatment and computational mastering.
On the other hand, it is also obvious that many of the recent deepest achievements in algebraic and arithmetic geometry, such as string theory and mirror symmetry (coming from physics) or Wiles' proof of Fermat's last theorem, just to mention a few, were neither inspired by nor used computer algebra at all. I just mention this in order to stress that no computer algebra system can ever replace, in any significant way, mathematical thinking.
Generally speaking, algorithmic treatment and computational mastering marks not the beginning but the end of a development and already requires an advanced theoretical understanding. In many cases an algorithm is, however, much more than just a careful analysis of known results, it is really a new level of understanding, and an efficient implementation is, in addition, usually a highly nontrivial task. Furthermore, having a computer algebra system which has such algorithms implemented and which is easy to use, it then becomes a powerful tool for the working mathematician, like a calculator for the engineer.
In this connection I should like to stress that having Buchberger's algorithm for computing Gröbner bases of an ideal is, although indispensable, not much more than having +,-,*,/ on a calculator. Nowadays there exist efficient implementations of very involved and sophisticated algorithms (most of them use Gröbner bases in an essential way) allowing the computation of such things as
not to mention the standard operations like ideal and radical membership, ideal intersection, ideal quotient and elimination of variables. All the above-mentioned algorithms are implemented in SINGULAR [Greuel, Pfister and Schönemann1990-1998], some of them also in CoCoA [Capani, Niesi and Robbiano1995] and Macaulay, resp. Macaulay2 (Bayer and Stillmann, resp. Grayson and Stillmann), to mention computer algebra systems which are designed for use in algebraic geometry and commutative algebra. Even general purpose and commercial systems such as Mathematica, Maple, MuPad etc. offer Gröbner bases and, based on this, libraries treating special problems in algebra and geometry.
It is well-acknowledged that Gröbner bases and Buchberger's algorithm are responsible for the possibility to compute the above objects in affine resp. projective geometry, that is, for non-graded resp. graded ideals and modules over polynomial rings. It is, however, much less known that standard bases (``Gröbner bases`` for not necessarily well-orderings) can compute the above objects over the localisation of polynomial rings. This is basically due to Mora's modification of Buchberger's algorithm (Mo) which has been modified and extended to arbitrary (mixed) monomial orderings in SINGULAR since 1990 and was published in Getal and in GP1. We include a brief description in Section 5.
I shall explain how non-well-orderings are intrinsically associated with a ring which may be, for example, a local ring or a tensor product of a local and a polynomial ring. These ``mixed rings'' are by no means exotic but are necessary for certain algorithms which use tag-variables which have to be eliminated later. The extension of Buchberger's algorithm to non-well-orderings has important applications to problems in local algebraic geometry and singularity theory, such as the computation of
Moreover, I demonstrate, by means of examples, how some of the above algorithms were used to support mathematical research in a non-trivial manner. These examples belong to the main methods of applying computer algebra successfully:
The mathematical problems I present were, to a large extent, responsible for the development of SINGULAR, its functionality and speed.
Finally, I point out some open problems in mathematics and non-mathematical applications which are a challenge to computer algebra and where either the knowledge of an algorithm or an efficient implementation is highly desirable.
Acknowledgement: The author was partially supported by the DFG Schwerpunkt ``Effiziente Algorithmen für diskrete Probleme''. Special thanks to C. Lossen and, in particular, to T. Keilen for preparing the pictures. Finally, I should like to thank the referees for useful comments.