Non-commutative Gröbner bases and improvements of Buchberger\u27s algorithm

Namen tega magistrskega dela je predstaviti teorijo Gröbnerjevih baz idealov v kolobarju nekomutativnih polinomov in tri glavne algoritme za njihov izračun, Buchbergerjev algoritem ter Faugèrjeva algoritma $F_4$ in $F_5$. Začnemo pri osnovah teorije nekomutativnih polinomov, predstavimo algoritem deljenja, definiramo Gröbnerjeve baze idealov nekomutativnih polinomov in dokažemo nekaj njihovih temeljnih lastnosti. Nadaljujemo s klasičnim Buchbergerjevim algoritmom, vpeljemo pojem ovire in nato sledimo korakom Tea More do nekomutativne različice algoritma. Pri tem z Dicksonovo lemo pokažemo končnost prvotnega komutativnega Buchbergerjevega algoritma ter dokažemo nekomutativno različico Buchbergerjevega kriterija in pravilnost nekomutativnega Buchbergerjevega algoritma. Pokažemo, kako množice polinomov pretvoriti v matrike ter hkrati formuliramo komutativen in nekomutativen algoritem $F_4$. Dokažemo pravilnost algoritma $F_4$ in pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo končnost algoritma F4. Definiramo modul vezi množice polinomov in dokažemo nekaj osnovnih lastnosti. Buchbergerjevo teorijo dvignemo v prosti modul nad kolobarjem komutativnih polinomov in definiramo polinomske podpise. Predstavimo osnovnega predstavnika družine podpisnih algoritmov ter dokažemo njegovo pravilnost in končnost. Vpeljemo kriterij $F_5$ in podpisni algoritem uporabimo, da formuliramo algoritem $F_5$. Za konec ponovimo prejšnje korake in predstavimo podpisni algoritem za nekomutativne polinome in dokažemo pravilnost nekomutativnega algoritma $F_5$. Pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo še njegovo končnost.The goal of this Master\u27s thesis is to present the theory of Gröbner bases of ideals in the ring of non-commutative polynomials, and the three main algorithms for computing them, Buchberger\u27s algorithm and Faugère\u27s $F_4$ and $F_5$ algorithms. We start with the basic theory of non-commutative polynomials, present the division algorithm, define Gröbner bases of ideals of non-commutative polynomials, and prove some of their fundamental properties. We continue with the classical Buchberger\u27s algorithm, introduce the concept of obstruction sets, and follow the steps of Teo Mora to the non-commutative version of the algorithm. Doing so, we use Dickson\u27s lemma to show that the original Buchberger\u27s algorithm terminates, and we prove the non-commutative version of Bucherger\u27s Criterion and correctness of the non-commutative version of Buchberger\u27s algorithm. We show how to transform sets of polynomials into matrices, and simultaneously formulate the commutative and non-commutative $F_4$ algorithm. We prove the correctness of the $F_4$ algorithm, and we prove it terminates if a finite Gröbner basis exists for the given ideal. For a finite set of polynomials, we define the syzygy module and prove some of its basic properties. We lift Buchberger\u27s theory into a free module over the ring of commutative polynomials and define polynomial signatures. We present the principal representative of the family of signature-based algorithms and prove its correctness and termination. We introduce the $F_5$ Criterion and use the signature-based algorithm to formulate the $F_5$ algorithm. We conclude by repeating the previous steps to arrive at a non-commutative signature-based algorithm and show the correctness of the non-commutative version of the $F_5$ algorithm. We prove this algorithm terminates if a finite Gröbner bases exists for the given ideal