# 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