Blockseminar Groebner basis
Summersemester 2018
Introduction
Bases play an important role in Linear Algebra as a bridge between the abstract theory of linear maps between vector spaces and the concrete matrices, making down-to-earth computations to be possible. Groebner bases do the same job for ideals of commutative (as well as some non- commutative) rings, serving as a powerful tool in for example computational algebraic geometry and integer programming.Solving systems of polynomial equations is a challenging problem pushing the development of mathematics forward. Given a system of polynomial equations, we study the following problems:
(1). How to find exact solutions of this system?
(2). Given a polynomial, whether its zeros containing the solutions of the system?
These problems can be translated into the language of ideals in a polynomial ring.
Groebner bases, which are bases of these ideals, are introduced by Buchberger around 1965, as a mixture of the Euclidean division of polynomials, Gauss elimination of linear equations and Dantzig simplex algorithm in linear programming. Groebner bases give a "computational" answer to these problems.
The theory of Groebner bases has various applications in Algebraic Geometry, Computational Algebra, Representation Theory, Integral Programming, etc...
In this seminar we will study basics of Groebner basis: the motivation, basic properties and algorithms, as well as some applications.
To get the credit points, the participants are requested to give a talk in the seminar (circa 50 minutes), and submit an extended abstract of the talk (6-10 pages, preferred in LaTeX, good quality handwritten is also possible). The grade of the seminar is determined by the quality of the talk, the extended abstract and the participation.
Detailed schedule
The seminar will be held in Uebungsraum 2 (Gyrhofstrasse 8).15.06.2018 14h-14h50 Heidler: Monomial ordering and division algorithm
15.06.2018 15h10-16h Erdweg: Monomial ideal and Dickson lemma
15.06.2018 16h20-17h10 Bertram: Hilbert basis theorem and Gröbner basis
Attention! The seminar on 22.16.2018 starts at 13h30.
22.16.2018 13h30-14h20 Patel: Buchberger criterion22.16.2018 14h30-15h20 Obersheimer: Buchberger algorithm
22.16.2018 15h40-16h30 Frege: Integer programming (I)
22.16.2018 16h40-17h30 Heimendahl: Integer programming (II)
29.06.2018 14h-14h50 Garcia Morales: Applications of Gröbner basis
29.06.2018 15h10-16h Risse: Homogeneous Gröbner basis
Distribution of talks
Talk 1 (Heidler): Monomial ordering and division algorithmMonomial order, examples (lex order, graded lex order, graded reverse lex order). Division algorithm with respect to a monomial order, examples.
Reference: [1] Chapter 2, Section 2 and 3
Talk 2 (Erdweg): Monomial ideal and Dickson lemma
Monomial ideal and example. Dickson lemma and its proof, running example for the proof.
Reference: [1] Chapter 2, Section 4
Talk 3 (Bertram): Hilbert basis theorem and Gröbner basis
Hilbert basis theorem and its proof. Definition of Gröbner basis, existence. Ascending chain condition.
Reference: [1] Chapter 2, Section 5
Talk 4 (Patel): Buchberger criterion
Reminder w.r.t a Gröbner basis, S-polynomials, examples of S-polynomials, Buchberger criterion.
Reference: [1] Chapter 2, Section 6
Talk 5 (Obersheimer): Buchberger algorithm
Description of Buchberger algorithm, examples oft he algorithm. Why the algorithm terminates? Reduced Gröbner basis, uniqueness.
Reference: [1] Chapter 2, Section 7
Talk 6 (Garcia Morales): Applications of Gröbner basis
Ideal membership problem, solving polynomial equations, implicitization problem
Reference: [1] Chapter 2, Section 8
Talk 7 (Risse): Homogeneous Gröbner basis
Homogeneous ideal, homogenisation, homogeneous Gröbner basis and Buchberger algorithm for homogeneous ideals.
Reference: [1] Chapter 10, Section 1 (page 540-546)
Talk 8/9 (Frege/Heimendahl): Integer programming
What is integer programming? How can Gröbner basis be applied to solve integer programming problem? Explain the theory and examples.
Talk 8: Introducing the integer programming problem, examples, polynomial maps, Lemma 2.8.2 in [2], Chapter 2, Section 8 (one should recall polynomial maps in order to explain the proof of this lemma).
Talk 9: From the algorithm after Lemma 2.8.2 till the end of the section, examples (recall the necessary notions and results from polynomial maps).
Reference: [2] Chapter 2, Section 4 and 8 (see also Cox, Little, O’shea; Using algebraic geometry, GTM 185, Second edition, Section 8.1 and on)
Schedule
Schedule: Vorbesprechungstermin: 19.01.2018, 16.30-17Uhr, Hoersaal MI.Das Seminar findet als Blockveranstaltung am 15.06.2018, 22.06.2018 und 29.06.2018, 14--17.30 Uhr statt.
Deadline of submitting extended abstract: 20.07.2018 (late submission will not be considered).
Language
For bachelor students, there is a language alternative for talks: German or English. For master students, the talks should be given in English.Requirements
Linear algebra I and II, Algebra (basics on rings and ideals).Literatur
The seminar will base on early chapters of the following two books:[1]. Cox, David A.; Little, John; O Shea, Donal. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. Fourth edition. Undergraduate Texts in Mathematics. Springer, Cham, 2015. xvi+646 pp. ISBN: 978-3-319-16720-6; 978-3-319-16721-3.
[2]. Adams, William W.; Loustaunau, Philippe. An introduction to Groebner bases. Graduate Studies in Mathematics, 3. American Mathematical Society, Providence, RI, 1994. xiv+289 pp. ISBN: 0-8218-3804-0.
The following two introductory articles are useful for a global overview of Groebner basis.
[3]. Sturmfels, Bernd. “What is . . . a Groebner Basis?“, Notices of the American Mathematical Society, 52 (10): 1199–1200.
[4]. Buchberger, Bruno. Groebner Bases: A Short Introduction for Systems Theorists, in Proceedings of EUROCAST 2001. http://www.risc.jku.at/people/buchberg/papers/2001-02-19-A.pdf