Introduction to Gröbner bases, TCD 2015/16
Lectures
Tue, 11:00 - 11:50 Salmon Lecture TheatreTue, 16:00 - 16:50 Synge Lecture Theatre
Thu, 11:00 - 11:50 Lecture Theatre M4 (Museum Building)
Summary of classes
| Lecture | Topics covered | References | Handouts |
|---|---|---|---|
| 1 (19/01) | Motivation and intuition for Gröbner bases. Brief history. Partial orders, total orders, well-orders. | [BD, Sec. 1.1.1] | |
| 2 (19/01) | First steps in developing the formalism of normal forms. Monomials. Polynomials. Linearly reduced elements. Every subspace has a unique linearly reduced basis. | [BD, Sec. 1.1.2, 1.2.1] | |
| 3 (21/01) | Cosets of linearly reduced monomials form a basis of the quotient vector space. Interpretation via reduced row echelon form. Proof that F[x] is a UFD using the developed formalism. Definition of F[x1,...,xn] and F⟨x1,...,xn ⟩. | [BD, Sec. 1.2.1, 1.2.2, 2.2.1, 7.2.2] | |
| 4 (26/01) | Universal properties of F[x1,...,xn] and F⟨x1,...,xn ⟩. Presentation of algebras by generators and relations. Admissible orders. Examples. | [BD, Sec. 2.2.2, 2.3.1, 7.2.3] | |
| 5 (26/01) | Divisibility of monomials. Reduced elements. Reduction. Long division for multivariate polynomials and for noncommutative polynomials, and its non-unique result. Gröbner bases. | [BD, Sec. 2.3.2, 2.3.3, 7.3.2] | |
| 6 (28/01) | Definition of a Gröbner bases using the ideal of leading terms. Equivalence to definition via normal forms. Example of a Gröbner basis: F[x,y] as a quotient of F⟨x,y⟩. Long division by a Gröbner basis does not depend on choices of reductions. Reduced Gröbner bases. Uniqueness of a reduced Gröbner basis (statement). | [BD, Sec. 2.3.3] | |
| 7 (02/02) | Uniqueness of a reduced Gröbner basis (proof). Special features of commutative Gröbner bases: Dickson's lemma. Hilbert's basis theorem. Hilbert's Nullstellensatz (statement). | [BD, Sec. 2.3.3] [CLO, 2.4] | |
| 8 (02/02) | Hilbert's Nullstellensatz (proof over complex numbers). Equivalent conditions for finiteness of the zero set. Shape lemma. | [BD, Sec. 7.5.1] | |
| 9 (04/02) | Basics of elimination theory. Examples of computer based calculations in the commutative and the noncommutative case (clickable for screenshots): elimination of variables in Magma, circumcentre of a triangle in Singular, group algebra of S3 in GAP. | [CLO, 3.1] | |
| No classes on February 9 and 11. Use the time provided to familiarise yourself with Gröbner bases implementation in various computer algebra programs (GBNP package for GAP, Singular, online calculator for Magma, etc.) | |||
| 10 (16/02) | Overlaps. S-polynomials. Diamond lemma (simple implications). | [BD, Sec. 2.4.1] | |
| 11 (16/02) | Diamond lemma (the nontrivial implication). | [BD, Sec. 2.4.1] | |
| 12 (18/02) | Noncommutative Buchberger's algorithm. Examples: the ideal (x2+y2) in F⟨x,y⟩, a finitely generated ideal whose reduced Gröbner basis is infinite for every admissible order, presentation of Q8 as a semigroup. | [BD, Sec. 2.4.2, 2.5.1, 2.5.6] | |
| No classes on February 23 and 25. There will be replacement classes in the last week of the term. | |||
| 13 (08/03) | Hilbert series of associative algebras. Examples of computations. Rational functions and recurrence relations. Graph of reduced words for an algebra with a finite Gröbner basis. | [BD, Sec. 2.5.1] | |
| 14 (08/03) | Graph of reduced words and rationality of Hilbert series. | [BD, Sec. 2.5.1] | |
| 15 (10/03) | Lie algebras and their universal enveloping algebras. The Poincaré-Birkhoff-Witt theorem. | [BD, Sec. 2.5.3] | |
| 16 (15/03) | Elimination theory. Elimination ideals and their Gröbner bases. Examples of extension of partial solutions. Resultant (definition). | [CLO, Sec. 3.1] | |
| 17 (15/03) | Resultants and common factors of univariate polynomials. The resultant of f and g is in the ideal (f,g). Extension of these statements to multivariate polynomials. | [CLO, Sec. 3.5, 3.6] | |
| No class on 17/03 (St Patrick's Day) | |||
| 18 (22/03) | Extension of a root of the resultant to a common root of f and g. Extension theorem for two equations. Generalised resultants. | [CLO, Sec. 3.6] | |
| 19 (22/03) | Extension theorem for arbitrary number of equations. Summary of results for solutions of systems of polynomial equations. | [CLO, Sec. 3.6] | |
| 20 (24/03) | Examples of applications of commutative Gröbner bases. | L20 [PDF] | |
| 21 (29/03) | Conditions xi>1 imply the well-order property in the commutative case. Examples of commutative monomial orders. Matrix orders. All monomial orders are matrix orders (statement). Equivalent matrices. Matrices inducing the lex order are lower triangular. Examples. | [BD, Sec. 7.4.1, 7.4.2] [CLO, Sec. 2.4] | |
| 22 (29/03) | Definition of a universal Gröbner basis. Proof using König's lemma. A topology on the set of total orders of a given set; its metrisability for a countable set. Compactness of the set of total orders. | ||
| 23 (31/03) | Topological proof of existence of a universal Gröbner basis. Triangle lemma (statement). | ||
| 24 (05/04) | Triangle lemma (proof). Abstract rewriting systems: joinability, termination, confluence. | [BD, Sec. 2.4.3 and 2.6.1] | |
| 25 (05/04) | Abstract rewriting systems: local confluence, Diamond lemma, convergence. Relationship to Gröbner bases. Ordered rewriting systems. Example of a convergent rewriting system that does not rely on Gröbner bases. Revision of the module. | [BD, Sec. 2.6.1 and 2.6.2] | |
| There will be no class on April 7. Hand in your homeworks to the School of Maths office before midday on that day. |
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 (since at least 1900), 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 unknowns) 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, Buchberger's algorithm. Speeding up the algorithm: "Triangle lemma".
- Using Gröbner bases for solving systems of arbitrary polynomial equations. "Shape lemma."
- Dickson's lemma. Finiteness, universal Gröbner bases. Classification of monomial orders.
- Noncommutative associative algebras. Growth. Hilbert series. Examples.
- Gröbner bases for associative algebras. Diamond lemma. Examples. Exotic monomial orders. Criteria of termination in the non-commutative case.
- Applications of commutative and noncommutative Gröbner bases.
Textbooks
The main recommended textbooks are:- [BD] Murray Bremner and Vladimir Dotsenko. Algebraic Operads: An Algorithmic Companion, final draft of the book currently available via this link.
- [CLO] 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.
- [St1] Bernd Sturmfels, Algorithms in Invariant Theory. Springer, 1993. (Applications.)
- [St2] Bernd Sturmfels, Gröbner Bases and Convex Polytopes.. AMS University Lecture Series, Volume 8. AMS, 1996. (Applications.)