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.

Distribution of talks

Talk 1 (Heidler): Monomial ordering and division algorithm
Monomial 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
Arbeitsgruppe Algebra und Zahlentheorie, Mathematisches Institut, Universität zu Köln