Introduction to Gröbner bases, TCD 2013/14

Lectures

Wed, 17:00 - 17:50 Salmon Lecture Theatre
Thu, 10:00 - 10:50 Salmon Lecture Theatre
Thu, 12:00 - 12:50 Westland Row 20, School of Maths New Seminar Room

Weekly summary

Week 1: Introduction. Famous particular cases of Gröbner bases (Gauss–Jordan elimination and Euclidean algorithm for univariate polynomials). Applications of Gröbner bases. Example: integer linear programming. Monomial orderings. The formal definition of a Gröbner basis.
Week 2: Examples of Gröbner bases. Dickson's Lemma. Hilbert Basis Theorem and the Ascending Chain Condition for ideals.
Week 3: Dickson's Lemma implies equivalence of two definitions of monomial orderings. Normal monomials form a basis of the quotient. Buchberger's Criterion. Buchberger's algorithm for computing Gröbner bases.
Week 4: Redundant S-polynomials in the Buchberger's algorithm. Reduced Gröbner bases, their uniqueness. Elimination ideals. Extension Theorem.
Week 5: Applications of Extension Theorem. Nullstellensatz. Solving systems of arbitrary polynomial equations. Finiteness of the number of zeros is equivalent to the finite dimensionality of the quotient ring. Implicitization of parametric presentations of surfaces.
Week 6: Other applications of Gröbner bases. Computing the least common multiple and the greatest common divisor of two multivariate polynomials. Universal Gröbner bases, their existence. Introduction to polynomials with noncommutative variables.
Week 7: Reading week, no classes.
Week 8: Gröbner bases in the noncommutative setting. Normal monomials. Homogeneous ideals and growth of noncommutative rings. The criterion for a system of polynomials to be a Gröbner basis, and a Buchberger-type "algorithm". Reduced Gröbner bases. Examples of Gröbner bases.
Week 9: Gröbner bases and power networks (lecture by Dr Eugene Kashdan). Application of Gröbner bases for computing growth of noncommutative rings. Diamond Lemma.
Week 10: Poincaré-Birkhoff-Witt theorem via Gröbner bases. Rewriting systems and Newman's Lemma. Comparison of rewriting systems and Gröbner bases: examples of rewriting rules xy→x²+y² and xyz→x³+y³+z³.

About this module

This module is intended as an introduction to an important computational method of algebra, Gröbner bases [for "systems of equations" in a reasonably wide sense]. This method, implicit in works of various mathematicians for a long time, has only been made into a general theory as recently as in 1965. It can be viewed as a generalisation of both long division and Gaussian elimination of variables from linear equations, leading to efficient methods of solving systems of polynomial equations, and hence applicable in a range of subjects across both pure mathematics and "real life" applications like robotics and image processing. The module will set out theoretical foundations for this theory, provide the students with examples to explore, and outline some applications of Gröbner bases in natural sciences.

Syllabus

Gröbner bases and elimination in the commutative case: long division, Gauss-Jordan elimination, general case of solving systems of arbitrary polynomial equations. Finiteness, universal Gröbner bases. Effective bounds.
Applications of Gröbner bases for commutative algebras outside abstract algebra.
Noncommutative associative algebras. Growth. Hilbert series. Examples.
Associative algebras. Free algebras. Algebras presented via generators and relations.
Gröbner bases for associative algebras. Diamond Lemma. Examples. Poincare-Birkhoff-Witt theorem via Gröbner bases.
Rewriting systems vs Gröbner bases.

Textbooks

The main recommended textbooks are:

Murray Bremner, Notes from a mini-course "Free associative algebras, noncommutative Grobner bases, and universal associative envelopes for nonassociative structures", available via http://arxiv.org/abs/1303.0920. (Noncommutative Gröbner bases, Diamond lemma.)
David Cox, John Little, and Don O'Shea, Ideals, Varieties, and Algorithms. 3rd edition, Springer, 2007. See also various notes, lists of typos, and links to computer packages on the homepage of David Cox. (Commutative Gröbner bases, Buchberger's algorithm, theoretical consequences.)
Bernd Sturmfels, Algorithms in Invariant Theory. Springer, 1993. (Applications.)
Bernd Sturmfels, Gröbner Bases and Convex Polytopes.. AMS University Lecture Series, Volume 8. AMS, 1996. (Applications.)
Victor Ufnarovski, Combinatorial and Asymptotic Methods of Algebra. In: Algebra VI (Encyclopaedia of Mathematical Sciences), Springer, 1995. (Noncommutative Gröbner bases. Growth of algebras.)

Assessment

There will be several home assignments (roughly every 2-3 weeks) that contribute 20% of your final mark. As an alternative, you can earn the same 20% by doing a small project, either implementing one of the algorithms related to the module (see Appendix D of Cox-Little-O'Shea) or learning and presenting in class some application of Gröbner bases.

Disclaimer

The person who is solely responsible for the choice of content on this page is Vladimir Dotsenko. Any views expressed here do not necessarily represent the official views of Trinity College Dublin.