Gröbner Bases and Their Applications

Master's thesis defense by Ella Evers Tusvik and Maike Sander Rechnagel

Title: Gröbner Bases and Their Applications

Abstract: This thesis presents Gröbner bases and their applications, aiming for a comprehensive yet self-contained presentation. To achieve this, we introduce Hilbert’s Basis Theorem, which implies the existence of Gröbner bases for polynomial ideals, together with the multivariable division algorithm, where division by a Gröbner basis yields a unique remainder. These results naturally lead to Buchberger’s Criterion and Buchberger’s Algorithm for the explicit computation of Gröbner bases. We present The Ideal-Variety Correspondence, and thereby proving The Strong Nullstellensatz. Using the Finiteness Theorem and the quotient ring, we develop a theory showing that for radical ideals and an algebraically closed coefficient field, the number of elements in an affine variety equals the dimension of the quotient ring as a vector space. The Elimination Theorem and the extension Theorem play an essential role throughout this thesis, providing methods for solving arbitrary systems of polynomial equations. Based on this theory, we investigate applications of Gr¨obner bases to Sudoku and graph colouring, where the reduced Gröbner basis yields the explicit solutions and the number of solutions for the problems arising in Sudoku and graph colouring. Moreover, we introduce polynomial and rational implicitization, in which we prove the Rational Implicitization Theorem and show that the variety of the (m+ 1)-th elimination ideal is the smallest variety containing a given parametrization. Finally, we present invariant theory of finite matrix groups. We introduce the Reynolds operator, which leads to the determination of the fundamental invariants of the ring of invariants as a finite set of homogeneous invariants. Furthermore, we show how Gröbner bases can be used to represent polynomials in terms of the fundamental invariants. Lastly, an isomorphism between the quotient ring over the ideal of relations and the ring of invariants enables Gröbner bases to define a canonical representation of invariants in terms of fundamental invariants.