UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika – 2. stopnja
Benjamin Benčina
NEKOMUTATIVNE GRÖBNERJEVE BAZE IN IZBOLJŠAVE BUCHBERGERJEVEGA
ALGORITMA
Magistrsko delo
Mentor: prof. dr. Igor Klep
Ljubljana, 2022
Zahvala
Zahvaljujem se mami za vso podporo tekom študija. Hvala prijateljem za družbo na prepogostih odmorih od pisanja; zdaj lahko znova pozabite, kaj je polinom.
Največja zahvala gre mentorju prof. dr. Igorju Klepu. V meni ste vzbudili močno zanimanje za računalniško algebro in me usmerjali, da je zraslo v to magistrsko delo.
Hvala za ves čas in voljo ter povsem nepovezane diskusije na najinih srečanjih. Brez vas bi se moje poznavanje tega čudovitega poglavja matematike začelo in končalo pri Gaussovi eliminaciji.
Kazalo
Program dela ix
1 Uvod 1
2 Osnovni pojmi 2
3 Nekomutativni polinomi in Gröbnerjeve baze 5
3.1 Nekomutativni polinomi . . . 5
3.2 Algoritem deljenja . . . 7
3.3 Gröbnerjeva baza ideala . . . 10
3.4 Reducirana Gröbnerjeva baza ideala . . . 13
4 Buchbergerjev algoritem 17 4.1 Komutativen Buchbergerjev algoritem . . . 17
4.1.1 Osnovna različica algoritma . . . 17
4.1.2 Izboljšana različica algoritma . . . 19
4.2 Nekomutativen Buchbergerjev algoritem . . . 22
4.2.1 Samoovire in minimalna množica ovir nekomutativnih polino- mov . . . 22
4.2.2 Nekomutativna različica algoritma . . . 27
4.2.3 Neodločljivost problema . . . 30
5 Algoritem F4 32 5.1 Matrike polinomov . . . 32
5.2 Homogeni polinomi . . . 35
5.3 Pomožni pojmi in izbirna funkcija . . . 38
5.4 Algoritem F4 . . . 39
6 Polinomske vezi 45 6.1 Definicija vezi . . . 45
6.2 Računanje Gröbnerjevih baz z vezmi . . . 47
7 Algoritem F5 50 7.1 Podpis polinoma . . . 50
7.2 Računanje Gröbnerjevih baz s podpisi . . . 53
7.3 Kriterij F5 . . . 57
7.4 Algoritem F5 . . . 60
7.5 Dokaz podpisnega Buchbergerjevega kriterija . . . 63
8 Nekomutativen algoritem F5 66 8.1 Posplošitev pomožnih pojmov . . . 66
8.2 Posplošitev redukcij in podpisne Gröbnerjeve baze . . . 67
8.3 Računanje Gröbnerjevih baz s podpisi . . . 68
8.4 Posplošitev kriterija F5 . . . 73
8.5 Nekomutativen algoritem F5 . . . 74
8.6 Dokaz podpisnega Buchbergerjevega kriterija . . . 77 8.7 Nadaljnje optimizacije in posplošitve . . . 81
Literatura 83
Kazalo algoritmov
1 Algoritem za levo deljenje polinomov . . . 8
2 Algoritem za dvostransko deljenje polinomov . . . 9
3 Algoritem za medsebojno redukcijo množice polinomov . . . 15
4 Buchbergerjev algoritem – osnovna različica . . . 18
5 Buchbergerjev algoritem – komutativna različica . . . 20
6 Minimalna množica ovir – nekomutativna različica . . . 26
7 Buchbergerjev algoritem – nekomutativna različica . . . 28
8 AlgoritemF4 . . . 39
9 AlgoritemF4 – funkcija Reduction . . . 40
10 Algoritem F4 – funkcija SymbolicPreprocessing . . . 40
11 Podpisni Buchbergerjev algoritem . . . 54
12 Algoritem F5 . . . 60
13 Algoritem F5 – funkcija Criterion . . . 60
14 Nekomutativen podpisni Buchbergerjev algoritem . . . 70
15 Nekomutativen algoritem F5 . . . 74
16 Nekomutativen algoritem F5 – funkcija Criterion . . . 75
Program dela
Kandidat naj predstavi teorijo komutativnih in nekomutativnih Gröbnerjevih baz.
Ob osnovnem Buchbergerjevem algoritmu naj predstavi tudi moderne algoritme, kot sta Faugèrjeva algoritmaF4 inF5, ter izpelje njune nekomutativne različice.
Osnovna literatura
[27] T. Mora, An introduction to commutative and noncommutative Gröbner ba- ses, Theoret. Comput. Sci.134(1) (1994) 131–173, doi: 10.1016/0304-3975(94) 90283-6
[12] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra 139(1-3) (1999) 61–88, doi: 10.1016/s0022-4049(99) 00005-5
[13] J.-C. Faugère,A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), v: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC ’02, ACM, 2002, doi: 10.1145/
780506.780516
[9] C. Eder in J.-C. Faugère,A survey on signature-based algorithms for computing Gröbner bases, J. Symbolic Comput. 80 (2017) 719–784, doi: 10.1016/j.jsc.
2016.07.031
Podpis mentorja:
Nekomutativne Gröbnerjeve baze in izboljšave Buchbergerjevega algoritma
Povzetek
Namen tega magistrskega dela je predstaviti teorijo Gröbnerjevih baz idealov v kolo- barju nekomutativnih polinomov in tri glavne algoritme za njihov izračun, Buchber- gerjev algoritem ter Faugèrjeva algoritma F4 in F5. Začnemo pri osnovah teorije nekomutativnih polinomov, predstavimo algoritem deljenja, definiramo Gröbner- jeve 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 Buchbergerje- vega 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 nekomutati- ven algoritem F4. Dokažemo pravilnost algoritma F4 in pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo končnost algoritma F4. Defini- ramo modul vezi množice polinomov in dokažemo nekaj osnovnih lastnosti. Buchber- gerjevo teorijo dvignemo v prosti modul nad kolobarjem komutativnih polinomov in definiramo polinomske podpise. Predstavimo osnovnega predstavnika družine pod- pisnih algoritmov ter dokažemo njegovo pravilnost in končnost. Vpeljemo kriterijF5 in podpisni algoritem uporabimo, da formuliramo algoritemF5. Za konec ponovimo prejšnje korake in predstavimo podpisni algoritem za nekomutativne polinome in dokažemo pravilnost nekomutativnega algoritmaF5. Pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo še njegovo končnost.
Math. Subj. Class. (2020): 13P10, 16Z05, 68W30
Ključne besede: nekomutativni polinomi, Gröbnerjeve baze, Buchbergerjev al- goritem, algoritem F4, algebraična vez, podpisni algoritmi, algoritemF5
Non-commutative Gröbner bases and improvements of Buchberger’s algorithm
Abstract
The goal of this Master’s 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 com- puting them, Buchberger’s algorithm and Faugère’sF4 and F5 algorithms. We start with the basic theory of non-commutative polynomials, present the division algo- rithm, define Gröbner bases of ideals of non-commutative polynomials, and prove some of their fundamental properties. We continue with the classical Buchberger’s 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’s lemma to show that the original Buchberger’s algorithm terminates, and we prove the non-commutative version of Bucherger’s Criterion and correctness of the non- commutative version of Buchberger’s algorithm. We show how to transform sets of polynomials into matrices, and simultaneously formulate the commutative and non- commutative F4 algorithm. We prove the correctness of the F4 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’s theory into a free module over the ring of commutative po- lynomials and define polynomial signatures. We present the principal representative of the family of signature-based algorithms and prove its correctness and termi- nation. We introduce the F5 Criterion and use the signature-based algorithm to formulate the F5 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 F5 algorithm. We prove this algorithm terminates if a finite Gröbner bases exists for the given ideal.
Math. Subj. Class. (2020): 13P10, 16Z05, 68W30
Keywords: non-commutative polynomials, Gröbner bases, Buchberger’s algori- thm, F4 algorithm, syzygy, signature-based algorithms, F5 algorithm
1 Uvod
Pojem Gröbnerjeve baze ideala polinomov je skupaj s primerom algoritma za njen iz- račun prvi predstavil in poimenoval avstrijski matematik Bruno Buchberger v svoji doktorski disertaciji [4]. Kljub svoji pomembni vlogi pri reševanju sistemov poli- nomskih enačb so zaradi počasne in predvsem težko dostopne računalniške opreme prevladale “klasične” metode komutativne algebre, kar pa se je spremenilo v 80-ih letih prejšnjega stoletja. Področje računalniške algebre in tako imenovane račun- ske teorije idealov je dodobra vzklilo in je še danes aktivno in bogato področje matematike. Gröbnerjeve baze in Buchbergerjev algoritem so postali nepogrešljivi pripomočki tako v računalniški algebri sami kot v komutativni algebri in algebraični geometriji.
Leta 1999 in 2002 je francoski matematik Jean-Charles Faugère zaporedoma predlagal dva povsem nova algoritma za izračun Gröbnerjevih baz idealov, algoritem F4 in algoritem F5, ki vsak na svoj način temeljita na Buchbergerjevem algoritmu.
Prav algoritem F5 je s svojo hitrostjo očaral matematično skupnost in vzpostavil Gröbnerjeve baze kot pomembno orodje še drugod po matematiki in računalništvu, na primer v algebraični kriptoanalizi [16, 15, 7] ter iskanju rešitev matričnih enačb in operatorskih identitet [21].
Kmalu po objavi Buchbergerjevega algoritma se je poleg želje po pohitritvi al- goritma pojavila tudi potreba po njegovi razširitvi na kolobarje nekomutativnih polinomov. Prvi, ki je vsaj v teoriji pokazal, da se da algoritem posplošiti na pro- ste algebre, je bil ameriški matematik George M. Bergman v [2] že leta 1978, leta 1985 pa je italijanski matematik Ferdinando “Teo” Mora v [26] opisal prvo različico nekomutativnega Buchbergerjevega algoritma. Drugi avtorji so v tem času Buchber- gerjev algoritem razširili na pomembne konkretne primere nekomutativnih algeber, na primer na Weylove algebre.
Namen tega magistrskega dela je podrobno opisati Gröbnerjeve baze idealov v kolobarjih komutativnih in nekomutativnih polinomov, Buchbergerjev algoritem, njegovo nekomutativno različico in si nato ogledati algoritmaF4 inF5 za nekomuta- tivne polinome ter dokazati njuno računsko pravilnost. V razdelku 2 bomo na hitro ponovili algebraične pojme in uvedli nekaj oznak. V razdelku 3 bomo uvedli pojem nekomutativnega polinoma ter vse pomožne pojme, ki jih ponavadi povezujemo s polinomi, in definirali Gröbnerjevo in reducirano Gröbnerjevo bazo. Razdelek 4 sledi korakom Ferdinanda More. Najprej bomo vpeljali osnovno različico Buchbergerje- vega algoritma, potem pa jo posplošili na nekomutativen Buchbergerjev algoritem.
V razdelku 5 se bomo hkrati lotili komutativne in nekomutativne različice algo- ritma F4. Nato si bomo vzeli kratek odmor od algoritmov in se posvetili povezavi med Gröbnerjevimi bazami in algebraičnimi vezmi. V razdelkih 7 in 8 se posvetimo algoritmu F5. Najprej bomo podrobno opisali komutativno različico algoritma F5 in družino podpisnih algoritmov za izračun Gröbnerjevih baz, potem pa bomo to družino prilagodili za delo z nekomutativnimi polinomi.
2 Osnovni pojmi
V tem razdelku bomo na kratko ponovili že znane pojme, predvsem s področja algebre.
MnožicaS, opremljena z asociativno operacijo množenja, za katero je S zaprta, definirapolgrupo. PodmnožiciA⊂Spravimolevi polgrupni ideal, če veljaS·A⊂A, indesni polgrupni ideal, če veljaA·S ⊂A. Podmnožica polgrupeS je (dvostranski) polgrupni ideal, če je hkrati levi in desni polgrupni ideal.
Posebni primer polgrupe jeprosta polgrupa nad množico generatorjevX. Defini- ramo jo kot množico končnih nizov, ki jim pravimobesede, sestavljenih iz elementov ali znakov iz množice X. Na tej množici definiramo binarno operacijo sklapljanja besed, ki iz dveh besed w1 =xi1· · ·xin in w2 =xj1· · ·xjm sestavi združeno besedo
w=w1w2 =xi1· · ·xinxj1· · ·xjm.
Če dodamo še prazno besedo (beseda ničelne dolžine), ki jo označimo zε, tej množici rečemo prosti monoid.
Množica skupaj z binarnima operacijama (R,+,·) je kolobar, če je (R,+) abe- lova grupa, (R,·) pa je monoid (za vse kolobarje privzemamo, da vsebujejo enico).
Seštevanje in množenje povezuje distributivnost, za vse x, y, z ∈R velja x·(y+z) = (x·y) + (x·z), (x+y)·z = (x·z) + (y·z).
Podgrupa za seštevanje I ≤ R je levi ideal kolobarja R, če je R ·I ⊆ I, in desni ideal kolobarjaR, če jeI·R⊆I. Če je množicaI levi in desni ideal kolobarja R, ji rečemo (dvostranski) ideal in označimo I ◁ R. Center kolobarja R definiramo kot Z(R) = {x∈R; ∀y∈R: xy=yx}. Kolobar je komutativen, če je enak svojemu centru. Če je poleg tega vsak od nič različen element v kolobarju obrnljiv, mu rečemo polje.
Levi ideal I kolobarja R je generiran z množico X ⊂ I, če lahko vsak element a∈I zapišemo kot končno vsoto
a=
s
∑︂
i=1
aixi
za neke elemente ai ∈ R, xi ∈ X, kjer i= 1, . . . , s, in s ∈ N. Na analogen način z množenjem z desne v zgornji vsoti definiramo desni ideal, generiran z neko množico X. Dvostranski ideal I kolobarja R je generiran z množico X ⊂ I, če lahko vsak element a∈I zapišemo kot končno vsoto
a=
s
∑︂
i=1 t
∑︂
j=1
aijxibij
za neke elementeaij, bij ∈Rinxi ∈X, kjeri= 1, . . . , sinj = 1, . . . , t. Levi in desni ideal I kolobarja R, generiran z množico X, zaporedoma označimo z I = RX in I =XR, dvostranski ideal pa zI = (X). MnožiciX pravimo množica generatorjev ideala I in ni enolično določena.
Algebra nad poljem k je kolobar R skupaj s homomorfizmom kolobarjevσ: k → Z(R). Homomorfizem σ kolobar R opremi z množenjem s skalarji iz polja k s predpisom ar=σ(a)·r za vsaka a∈k inr ∈R.
Kolobar R je levo noetherski, če se vsako strogo naraščajoče zaporedje levih idealovI1 ⊊I2 ⊊· · · vRustavi, torej obstajan ∈N, da jeIn=In+1 =· · ·. Na enak način z zaporedjem desnih idealov definiramo šedesno noetherski kolobar. Kolobar je noetherski, če je hkrati levo in desno noetherski. Brez dokaza se spomnimo, da so v levo noetherskem kolobarju vsi levi ideali končno generirani, simetrična trditev pa velja tudi za desno noetherske kolobarje.
Abelovi grupi (M,+), opremljeni z zunanjo operacijo ·:R×M →M množenja s skalarji iz kolobarjaR, za katero za vser, s∈R in x, y ∈M veljajo enakosti
r·(x+y) =r·x+r·y (r+s)·x=r·x+s·x
(rs)·x=r·(s·x) 1·x=x
pravimoleviR-modul. Na simetričen način z operacijo·: M×R →M definiramo še desni R-modul. Za kolobarjaRinS lahko definiramo(R, S)-bimodul M kot abelovo grupo, ki je hkrati levi R-modul in desni S-modul za operaciji ·: R×M → M in
∗: M×S →M, dodatno pa zahtevamo, da velja (r·x)∗s=r·(x∗s)
za vse elementer ∈R,s∈Sinx∈M. Če jeR=S, pogosto moduluM rečemo kar R-bimodul. Če je R komutativen kolobar, so levi in desni R-moduli enaki, zato jim rečemo leR-moduli. V posebnem primeru, ko jeR =k polje, je definicijak-modula očitno enaka definicijo vektorskega prostora nadk. V tem smislu je koncept modula posplošitev koncepta vektorskega prostora na koeficiente iz kolobarja. Levi ali desni R-modul M je prost, če obstaja množica R-linearno neodvisnih elementov B ⊂M, ki generirajo modul M. Tako kot v teoriji vektorskih prostorov, množici B rečemo baza modula M.
Iz desnega R-modula M in levega R-modula N lahko sestavimo njun tenzorski produkt M ⊗RN. To je abelova grupa, ki jo generirajo vsi pari oblike m⊗n, kjer m∈M inn ∈N, opremljeni z naslednjimi relacijami:
(m1+m2)⊗n=m1⊗n+m2⊗n m⊗(n1+n2) =m⊗n1+m⊗n2 (mr)⊗n=m⊗(rn)
za vse m, m1, m2 ∈ M, n, n1, n2 ∈ N in r ∈ R. Če je M R-bimodul, potem je M ⊗RN levi modul z zunanjo operacijo
r(m⊗n) = (rm)⊗n.
Podobno je v primeru, ko jeN R-bimodul,M⊗RN desniR-modul. V posebnem je M⊗N R-bimodul, če sta obaM inN R-bimodula. Če staM inN prostaR-modula končne dimenzije, velja
dimRM ⊗RN = dimRM·dimRN
Če je iz konteksta razvidno nad katerim kolobarjem delamo, namesto ⊗R pogosto pišemo kar ⊗.
Relacija ≤ na množici S je dobra ureditev, če je refleksivna, tranzitivna, antisi- metrična, poljubna elementa iz množice S sta primerljiva in vsaka podmnožica v S vsebuje najmanjši element. Relacija ≤nam poda tudi strogo ureditev<, definirano z a < b ⇐⇒ a ≤ b∧a ̸= b, ki se razlikuje od ≤ samo v temu, da je relacija <
irefleksivna. Velja tudi obratno, stroga ureditev z zgornjimi lastnostmi <nam poda ureditev ≤, definirano z a ≤ b ⇐⇒ a < b∨a = b. Dobro ureditev bomo zato označevali tako s simbolom ≤kot s simbolom <, zgornja povezava bo implicitna.
Tekom celotnega magistrskega dela bomo uporabljali običajno oznako za nene- gativna cela števila N0 = N∪ {0}. Pri množenju bomo znak za operacijo pogosto izpuščali.
3 Nekomutativni polinomi in Gröbnerjeve baze
V tem razdelku si bomo podrobneje ogledali kolobar polinomov in predvsem njegovo posplošitev na polinome z nekomutativnimi spremenljivkami. Spoznali bomo pojme, kot so monomska ureditev in vodilni monom, ter algoritem za deljenje polinomov.
Na koncu razdelka bomo definirali enega krovnih pojmov tega magistrskega dela - Gröbnerjevo bazo ideala polinomov.
3.1 Nekomutativni polinomi
Najprej si oglejmo, kako običajen kolobar komutativnih polinomov v spremenljivkah x1, . . . , xn posplošimo na kolobar nekomutativnih polinomov in na njem definiramo pojme, kot so stopnja polinoma, vodilni člen in vodilni koeficient.
Definicija 3.1. Naj bo k polje in S polgrupa. Polgrupni kolobar kS je abstrakten vektorski prostor nad poljemk z množico S za bazo. Množenje nakS definiramo s pomočjo množenja naS kot
(︄ k
∑︂
i=1
asisi )︄
· (︄ l
∑︂
j=1
btjtj )︄
=
m
∑︂
n=1
⎛
⎝
∑︂
sitj=rn
asibtj
⎞
⎠rn
kjer soasi, btj ∈k in si, tj ∈S za vse i= 1, . . . , k inj = 1, . . . , l.
Opomba 3.2. Ker je polgrupni kolobarkSpo definiciji vektorski prostor nad poljem k, je opremljen z množenjem s skalarji iz polja k, zato mu rečemo tudi polgrupna algebra.
Primer 3.3. Naj boS končno generiran prosti monoidS =⟨x1, . . . , xn⟩. Polgrupni kolobarkS označimo kar sk⟨x1, . . . , xn⟩in si ga predstavljamo kot kolobar nekomu- tativnih polinomov v spremenljivkah x1, . . . , xn, polgrupoS pa si predstavljamo kot množico (nekomutativnih) monomov. Res, naj bo Is,n ⊂ {1, . . . , n}s množica vseh multiindeksov dolžines in označimo xI =xi1· · ·xis za vsak I ∈Is,n. Potem je vsak element p∈k⟨x1, . . . , xn⟩ oblike
p=∑︂
I∈I′
aIxI+bε
za neko končno podmnožicoI′ ⊆⋃︁n
s=1Is,n. Simbol εoznačuje prazno besedo v S in se pogosto izpusti, torejbε predstavlja prosti člen v zgornjem polinomu.
Da je to res nekomutativna različica običajnih polinomov, vidimo preprosto tako, da tvorimo abelizacijo zgornje polgrupe, torej S = ⟨x1, . . . , xn | ∀i ̸= j: xixj = xjxi⟩. Potem je jasno kS ∼=k[y1, . . . , yn]z izomorfizmom, ki slika ε↦→1 in xs↦→ys
za vsaks = 1, . . . , n.
V naslednji definicijo posplošimo pojem stopnje na monome z več spremenljiv- kami.
Definicija 3.4. Naj bo k⟨x1, . . . , xn⟩ kolobar nekomutativnih polinomov. Stopnja monoma xαi11· · ·xαiss ∈S, kjer jeα = (α1, . . . , αs)∈Ns0, je enaka
deg(︁
xαi11· · ·xαiss)︁
=|α|=
s
∑︂
i=1
αi.
Zaradi prisotnosti več spremenljivk, stopnji pogosto rečemo tudi multistopnja.
Opomba 3.5. Alternativno lahko definiramo stopnjo monomaα∈S preprosto kot njegovo dolžino, če nanj gledamo kot besedo v prosti polgrupi ali monoidu S.
Kolobar polinomov z eno spremenljivko ima implicitno določen vrstni red mono- mov, ki ga enolično določa stopnja monoma. S pomočjo tega vrstnega reda lahko definiramo standardne pojme, kot so vodilni člen, vodilni koeficient, prosti člen itd., določa pa nam tudi kako dva polinoma med sabo delimo. V (nekomutativnih) po- linomskih kolobarjih z več spremenljivkami imamo nekoliko več svobode pri izbiri vrstnega reda monomov, izbrana relacija pa mora še vedno ustrezati določenim zah- tevam.
Definicija 3.6. Naj bo kS polgrupni kolobar. Monomska ureditev na polgrupi S je dobra ureditev <, ki je kompatibilna s produktom na S: za vse elemente l, r, t1, t2 ∈S velja implikacija
t1 < t2 =⇒ lt1r < lt2r.
Opomba 3.7. Za komutativne polinomske kolobarje je ta definicija ekvivalentna temu, da velja u < v =⇒ uw < uw in w≥1za vse monome u, v, w.
Primer 3.8. Za komutativen polinomski kolobar k[x1, . . . , xn] je ena izmed bolj uporabljenih monomskih ureditev leksikografska ureditev, ki jo označimo zlex. De- finiramo jo s predpisom
xαlex> xβ ⇐⇒ prvi neničelni element α−β ∈Zn je pozitiven. Z drugimi besedami, monome prve stopnje uredimo “po abecedi”
x1 lex> x2 lex> · · ·lex> xn.
Ureditev lexv nekomutativnem primeru seveda ni monomska ureditev, saj v splo- šnem ni kompatibilna s produktom na S. Res, če je S = ⟨x1, x2⟩, potem za vsak j ∈N0 velja xj+11 x2
lex< xj1x2.
Ureditev, ki deluje tako v komutativnem kot v nekomutativnem primeru, je stopničasto leksikografska ureditev, označimo jo zgrlex. Definirana je kot
xα grlex> xβ ⇐⇒ deg(xα)>deg(xβ)ali deg(xα) = deg(xβ) inxα lex> xβ Izbrana monomska ureditev na kS nam enolično določa urejeno obliko za vse elemente f ∈kS
f =
s
∑︂
i=1
citi, t1 > t2 >· · ·> ts, (3.1) kjer ci ∈k\ {0} in ti ∈S za vsaki= 1, . . . , s. Sedaj definiramo naslednje pojme.
Definicija 3.9. Naj bof ∈kS z urejeno obliko glede na monomsko ureditev<kot v enačbi (3.1). Definiramo
• vodilni monom elementa f: LM(f) =t1,
• vodilni koeficient elementa f: LC(f) =c1,
• vodilni člen elementa f: LT(f) = LC(f) LM(f) = c1t1,
• (če je S =⟨x1, . . . , xn⟩) stopnja polinoma f:
deg(f) = max{deg(ti); i= 1, . . . , s}.
3.2 Algoritem deljenja
Opremljeni z osnovnimi pojmi, nadaljujmo z algoritmom za deljenje nekomutativnih polinomov. Ker množenje z leve in z desne v splošnem nista enaka, moramo paziti že pri definicijah deljenja in večkratnosti.
Naj bo X = {x1, . . . , xn} končna množica spremenljivk. Od tukaj naprej se osredotočimo predvsem na primera, ko je bodisi S = ⟨x1, . . . , xn⟩ bodisi S =
⟨x1, . . . , xn | xixj = xjxi⟩, torej ko je naš kolobar enak bodisi kolobarju nekomu- tativnih polinomov k⟨X⟩ bodisi kolobarju komutativnih polinomov k[X]. V obeh primerih bo kolobar opremljen z monomsko ureditvijo≤.
Definicija 3.10. Naj bosta f, g ∈ k⟨X⟩ nekomutativna polinoma. Polinom f je levi večkratnik polinoma g, če obstaja h ∈k⟨X⟩, da je f =hg, in desni večkratnik, če f = gh. V tem primeru rečemo, da je f zaporedoma levo in desno deljiv z g. Polinomf je (dvostranski) večkratnik polinomag, če obstajata h1, h2 ∈k⟨X⟩, da je f =h1gh2.
Opomba 3.11. Levo/desno večkratnost definiramo zato, ker so levi ideali zaprti za levo množenje z elementi kolobarja, desni ideali pa za desno. Levi, desni in dvostranski večkratniki so v zaporedoma v skupnem levem, desnem in dvostranskem idealu kolobarja k⟨X⟩.
Naslednji algoritem nam pove, kako deliti polinome z več spremenljivkami. Pri- sotnost monomske ureditve je tukaj razvidna iz uporabe koncepta vodilnega člena polinoma.
Algoritem 1: Algoritem za levo deljenje polinomov Input: končna množica polinomov F ={f, f1, . . . , fs} Output: končna množica polinomov {a1, . . . , as, r}
d:=f r:= 0
for i= 1, . . . , s do ai := 0
repeat
if ∃i∈ {1, . . . , s}, ∃c∈k, ∃λ∈S: LT(d) =cλLT(fi)then ai :=ai+cλ
d :=d−cλfi else
r :=r+ LT(d) d :=d−LT(d) untild= 0;
Izrek 3.12. Naj bodo f1, . . . , fs ∈ k⟨X⟩ nekomutativni polinomi. Potem za vsak polinom f ∈k⟨X⟩ obstajajo polinomi a1, . . . , as, r∈k⟨X⟩, da velja
f =a1f1+· · ·+asfs+r
kjer je bodisi r = 0 bodisi je r vsota členov, ki niso deljivi z nobenim LT(fi), kjer i= 1, . . . , s. Algoritem 1 se ustavi in izračuna neznane polinome a1, . . . , as, r.
Opomba 3.13. Algoritem 1 in izrek 3.12 v povsem enaki obliki in analognim do- kazom delujeta tudi za komutativne polinome iz kolobarja k[X].
Opomba 3.14. Izrek 3.12 predstavlja nekakšen analog izreku o deljenju za cela števila. Pomembna razlika med izrekoma je, da izrek 3.12 ne zagotavlja enoličnosti ostanka r. Kakor bomo kasneje videli v primeru 3.17, ostanek ni nujno enoličen niti v primeru, ko so polinomi komutativni.
Dokaz izreka 3.12. Želimo preveriti končnost in pravilnost algoritma 1. Za končnost je dovolj opaziti, da v vsakem koraku zanke repeat (kjer še d ̸= 0) velja LM(d′)<
LM(d), kjer je d′ tisti iz konca koraka,d pa tisti iz začetka koraka. To je očitno, saj v obeh primerih pogoja od polinoma d odštejemo njegov vodilni člen. Po končno mnogo korakih bo d = 0, saj je ≤ dobra ureditev. Pravilnost je potem jasna iz navodila, v katerem spreminjamo polinom r.
Algoritem 1 uporablja levo deljenje. Izrek 3.12 bi veljal tudi, če koeficiente a1, . . . , as množimo s polinomi f1, . . . , fs z desne, torej za desno deljenje. Seveda moramo potem prilagoditi algoritem 1, da namesto množenja z leve uporablja mno- ženje z desne. Zlahka pa ga prilagodimo tudi tako, da delimo dvostransko.
Algoritem 2: Algoritem za dvostransko deljenje polinomov Input: končna množica polinomov F ={f, f1, . . . , fs} Output: končna množica {(cij, λij, ρij); i= 1, . . . , s, j ∈N} d:=f
r := 0
for i= 1, . . . , sdo Ai :=∅
repeat
if ∃i∈ {1, . . . , s}, ∃c∈k, ∃λ, ρ∈S: LT(d) =cλLT(fi)ρ then Ai :=Ai∪ {(c, λ, ρ)}
d:=d−cλfiρ else
r:=r+ LT(d) d:=d−LT(d) until d= 0;
Posledica 3.15. Naj bodo f1, . . . , fs ∈ k⟨X⟩ polinomi. Potem za vsak polinom f ∈ k⟨X⟩ obstaja polinom r ∈ k⟨X⟩ in končno mnogo koeficientov cij ∈ k ter monomov λij, ρij ∈S za i= 1, . . . , s in j ∈N, da velja
f =
s
∑︂
i=1
∑︂
j∈N
cijλijfiρij +r (3.2) kjer je bodisi r = 0 bodisi je r vsota členov, ki niso dvostransko deljivi z nobenim LT(fi), kjer i= 1, . . . , s.
Dokaz. Opazimo, da element množice (c, λ, ρ)∈Ai v algoritmu 2 predstavlja točno enega od členov cijλijfiρij v enačbi (3.2) za nek j ∈ N. Nato sledimo dokazu izreka 3.12.
Opomba 3.16. Ostanek pri deljenju polinoma f z množico F označimo z fF. Pri pisanju psevdokode se uporablja tudi oznaka f mod F, zato bomo pri pisanju algoritmov pogosto uporabili tudi to.
Oglejmo si preprost primer deljenja komutativnih polinomov v dveh spremen- ljivkah, ki hkrati ponazarja, da je ostanek pri deljenju odvisen od vrstnega reda deljenja.
Primer 3.17. Kolobar k[x, y] opremimo z ureditvijo lex in naj bodo f = xy2 − x, g1 = xy + 1, g2 = y2 + 1 polinomi v k[x, y]. Če polinom f najprej delimo s polinomom g1 in nato z g2, dobimo naslednje:
Ker jeLT(d) = xy2 deljiv zLT(g1) =xy zag =y, nam prvi korak zanke repeat v algoritmu 1 nastavi a1 = y, a2 = 0 in d = −x−y. V drugem koraku zanke ni LT(d) = −x deljiv niti z LT(g1) = xy niti z LT(g2) = y2, torej dobimo ostanek r=−x−y in zapis
xy2−x=y·(xy+ 1) + 0·(y2−1) + (−x−y)
Obratni vrstni red deljenja nam vrne popolnoma drugačen rezultat. Prvi korak zanke repeat nam nastavi a1 = 0, a2 = x in takoj d = 0, torej je ostanek r = 0. Dobimo zapis
xy2−x= 0·(xy+ 1) +x·(y2−1) + 0, kar v posebnem pomeni, da je f ∈(g1, g2).
3.3 Gröbnerjeva baza ideala
Definicija 3.18. Naj bo kS polgrupni kolobar in I ⊂ kS njegov levi, desni ali dvostranski ideal. Definiramo ideal vodilnih monomov ideala I kot
LM(I) ={LM(f); f ∈I} ⊂S.
Opomba 3.19. Če jeIlevi, desni ali dvostranski ideal, potem je očitnoLM(I)zapo- redoma levi, desni ali dvostranski polgrupni ideal polgrupeS, saj jeLM(f) LM(g) = LM(f g).
Ključen rezultat, ki bo zagotavljal, da se algoritem za izračun Gröbnerjevih baz v komutativnem primeru res ustavi, je naslednji izrek, ki trdi, da so vsi monomski ideali končno generirani z množico monomov. Prej dokažimo še kratko lemo, ki jo bomo potrebovali v dokazu izreka.
Lema 3.20. Naj bo I = (xα; α ∈ A) monomski ideal kolobarja R =k[x1, . . . , xn]. Za vsak monom xβ ∈R velja, da je xβ ∈I natanko tedaj, ko obstaja α∈ A, da xα deli xβ.
Dokaz. Denimo, da jexβ ∈I, torej ga lahko zapišemo kot končno vsoto xβ =
m
∑︂
i=1
hixαi
zaα1, . . . , αm ∈ Ainh1, . . . , hm ∈R. Če zapišemo vsak hi zai= 1, . . . , mkot vsoto monomov in razpišemo vsoto na desni strani enačbe, dobimo na desni strani (končno) linearno kombinacijo monomov, vsak od njih pa je deljiv z xαi za nek i= 1, . . . , m. Ker sta polinoma enaka natanko tedaj, ko imata enake člene v linearni kombinaciji monomov, mora biti xβ enak nekemu členu na desni strani enačbe, torej je deljiv z xαi za nek i= 1, . . . , m. Obratna implikacija je očitna.
Izrek 3.21 (Dicksonova lema). Naj bo R = k[x1, . . . , xn] kolobar komutativnih po- linomov v spremenljivkah x1, . . . , xn in naj bo I = (xα; α ∈ A) ◁ R monomski ideal. Tedaj je I končno generiran in obstaja končno mnogo α1, . . . , αk ∈ A, da je I = (xα1, . . . , xαk).
Dokaz. Lemo dokažemo z indukcijo na število spremenljivkn. Najprej privzamemo n = 1, torej R =k[x]. Ideal I je potem oblikeI = (xni; ni ∈N0) za neko (ne nujno končno) zaporedje nenegativnih celih številA = (ni)i∈N. Očitno jeI = (xm), kjer je m = min{ni; ni ∈ A}.
Naj bo n > 1 in naj lema drži za k[x1, . . . , xk] za vse k < n. Preimenujmo spremenljivko xn v y, torej je R = k[x1, . . . , xn−1, y]. Vsak monom v R lahko po
novem zapišemo kot xαym, kjer je m ∈ N0, α = (α1, . . . , αn−1) ∈ Nn−10 in xα = xα11· · ·xαn−1n−1. Definiramo ideal J ◁k[x1, . . . , xn−1], generiran z vsemi monomi xα ∈ k[x1, . . . , xn−1], za katere obstaja tak m ∈ N0, da je xαym ∈ I. Ideal J je po konstrukciji monomski ideal v kolobarju polinomov z n −1 spremenljivkami, zato po indukcijski predpostavki obstaja s∈N in α(1), . . . , α(s), da je
J = (xα(1), . . . , xα(s))
Po definiciji ideala J nato obstajajo m1, . . . , ms, da so xα(1)ym1, . . . , xα(s)yms ∈ I. Označimo m = max{m1, . . . , ms}. Za vsak k = 0, . . . , m−1 znova konstruiramo ideal Jk ◁ k[x1, . . . , xn−1], generiran z vsemi monomi xα ∈ k[x1, . . . , xn−1], da je xαyk ∈I. Po indukcijski predpostavki so vsi idealJkkončno generirani in obstajajo takis0, . . . , sm−1 ∈N, da je
Jk = (xαk(1), . . . , xαk(sk)) Trdimo, da je I generiran z naslednjimi elementi
xα(1)ym, . . . , xα(s)ym ∈J xα0(1), . . . , xα0(s0) ∈J0
xα1(1)y, . . . , xα1(s1)y ∈J1
· · · ...
xαm−1(1)ym−1, . . . , xαm−1(sm−1)ym−1 ∈Jm−1
Res, vzemimoxαyp ∈I. Če jep≥m, potem je po konstrukciji idealaJ monomxαyp deljiv z vsaj enim od zgornjih generatorjev idealaJ. Če je p < m, je po konstrukciji ideala Jp monom xαyp deljiv z vsaj enim od zgornjih generatorjev ideala Jp.
Za konec moramo najti podmnožico množiceA, da pripadajoči monomi prav tako generirajo ideal I. Spremenljivke bodo spet označene običajno zx1, . . . , xn, zgornje generatorje pa preštevilčimo v I = (xβ(1), . . . , xβ(t)), kjer β(i) ni nujno element množice A za i= 1, . . . , t. Za vsak i = 1, . . . , t je xβ(i) ∈I = (xα; α ∈ A), zato po lemi 3.20 obstajajoα(1), . . . , α(t), da xα(i) deli xβ(i) za vsak i= 1, . . . , t. Potem pa seveda velja I = (xα(1), . . . , xα(t)).
Opomba 3.22. Rezultat, da so monomski ideali v kolobarjih komutativnih polino- mov končno generirani seveda ni presenetljiv, saj je po Hilbertovem izreku o bazi1 kolobark[x1, . . . , xn]noetherski za vsakn ∈N, torej so vsi ideali končno generirani, ne le monomski.
Definicija 3.23. Naj bokS polgrupni kolobar inInjegov levi, desni ali dvostranski ideal. Baza G ideala I je Gröbnerjeva baza za I, če množica LM(G) generira ideal vodilnih monomovLM(I)kot zaporedoma levi, desni ali dvostranski polgrupni ideal.
Opomba 3.24. Gröbnerjeva baza obstaja za vsak levi, desni in dvostranski ideal.
Na primer, za vsak ideal I je I \ {0} Gröbnerjeva baza ideala I. V posebnem je prazna množica ∅Gröbnerjeva baza ničelnega ideala.
1Glej npr. [1, Izrek 7.5].
Trditev 3.25. Naj bo I levi, desni ali dvostranski ideal polgrupnega kolobarja kS in naj bo G ⊆ I taka množica, da LM(G) generira LM(I). Potem je G Gröbnerjeva baza ideala I.
Dokaz. Dovolj je dokazati, da množicaGgenerira levi, desni ali dvostranski ideal I. Če jeI dvostranski ideal, za dokaz s protislovjem privzemimo, da velja(G)⊂I. Ker je ≤ dobra ureditev, lahko izberemo polinom f ∈ I \(G) z najmanjšim vodilnim monomom LM(f). Ker je LM(f) ∈ LM(I) in množica LM(G) generira LM(I), obstajajo c∈k, λ, ρ∈ S in g ∈G, da je LT(f) = LT(cλgρ) in f−cλgρ∈I \(G). Ampak velja LM(f − cλgρ) < LM(f), saj smo vodilni člen odšteli, kar pa je v protislovju z izbiro polinoma f.
Dokaz za enostranski ideal poteka povsem enako. Brez škode za splošnost privze- mimo, da je I levi ideal in označimo R=kS. Za dokaz s protislovjem privzemimo, da velja RG⊂I in vzemimof ∈I\RG z najmanjšim vodilnim monomom LM(f). Potem obstajajoc∈k,λ∈S ing ∈G, da je LT(f) = LT(cλg)inf−cλg ∈I\RG. Ker velja LM(f−cλg)<LM(F), smo prišli do protislovja z izbiro polinomaf.
Ena izmed ključnih lastnosti Gröbnerjevih baz je, da deljenje polinoma z Gröb- nerjevo bazo ideala po postopku algoritma 1 vrne enoličen ostanek. Situacija iz primera 3.17 se nam torej ne more zgoditi. Naslednjo trditev formuliramo za leve ideale, saj sta tako implicitno zastavljena tudi izrek 3.12 in algoritem 1, seveda pa deluje s primernimi spremembami tudi za desne ideale in po posledici 3.15 za dvostranske ideale.
Trditev 3.26. Naj bo kolobar R = k⟨X⟩ opremljen z monomsko ureditvijo ≤, naj bo I levi ideal kolobarja R in G Gröbnerjeva baza levega ideala I. Potem velja naslednje:
1. Polinom f ∈ R je v I natanko tedaj, ko obstaja končna podmnožica G′ = {g1, . . . , gs} ⊆G, da je ostanek polinoma f pri deljenju s polinomi iz G′ enak 0 (neodvisno od vrstnega reda).
2. Za vsak polinom f ∈ R in vsako končno podmnožico G′ = {g1, . . . , gs} ⊆ G obstaja natanko en polinom r∈R, da ni nobeden od členov polinoma r deljiv z nobenim LT(gi), kjer i= 1, . . . , s, in f−r ∈I.
Dokaz. Za prvi del trditve vzemimo f ∈ I in poljubno končno podmnožico G′ = {g1, . . . , gs} ⊆G, da obstajajo polinomia1, . . . , as ∈k⟨X⟩, da lahko f zapišemo kot
f =a1g1 +· · ·asgs.
Taka množica G′ ⊆Gmora obstajati po definiciji vsebovanosti v levem idealu. Naj bo r polinom, ki ga dobimo pri deljenju polinoma f s polinomi iz G′ v kateremkoli vrstnem redu po postopku algoritma 1. Ker f ∈I, po izreku 3.12 velja tudi r ∈I. Čer̸= 0, potem po izreku 3.12LT(r)ni deljiv z nobenim odLT(gi), kjeri= 1, . . . , s. Potem pa je
LT(r)∈LT(I) = SLT(G).
kar je v protislovju z definicijo Gröbnerjeve baze. Obratna trditev je očitna.
Za drugi del trditve vzemimo poljuben f ∈ R in končno podmnožico G′ = {g1, . . . , gs} ⊆G. Naj borpolinom, ki ga dobimo pri deljenju polinomaf s polinomi iz G′ v nekem vrstnem redu po postopku algoritma 1. Po izreku 3.12 je f−r ∈ I. Recimo, da pri deljenju v nekem drugem vrstnem redu dobimo drugačen ostanek r′, za katerega prav tako velja f−r′ ∈ I. Po izreku 3.12 sledi r−r′ ∈I in bodisi r−r′ = 0 bodisi nobeden od členov polinoma r −r′ ni deljiv z nobenim LT(gi), kjer i = 1, . . . , s. Če r−r′ ̸= 0, naš razmislek iz dokaza prvega dela trditve vodi v protislovje, zato mora bitir−r′ = 0, torej r=r′.
Opomba 3.27. Za dokaz zgornje trditve, kjer jeI dvostranski ideal, le zamenjamo vse sklice na izrek 3.12 s sklicem na posledico 3.15 in vse pojavitve algoritma 1 z algoritmom 2.
3.4 Reducirana Gröbnerjeva baza ideala
Podobno kot običajna baza ideala, tudi Gröbnerjeva baza ideala ni enolično do- ločena. Vsaka množica polinomov v idealu, ki vsebuje neko Gröbnerjevo bazo, je namreč Gröbnerjeva baza istega ideala. S tem namenom bomo definiralireducirano Gröbnerjevo bazo, ki bo za vsak ideal enolična, in podali algoritem, ki jo izračuna.
Ker je Gröbnerjeva baza G ideala I točno taka baza ideala I, da tudi množica monomovLM(G)generira polgrupni idealLM(I), najprej poskusimo zmanjšati bazo ideala vodilnih monomovLM(I).
Trditev 3.28. Naj boI polgrupni ideal polgrupe Sin naj boB množica vseh besed, ki ne vsebujejo nobenega elementa iz I kot pravo podbesedo. Tedaj množica B generira polgrupni ideal I in strogo vsebuje vse druge množice generatorjev ideala I.
Dokaz. Najprej dokažimo, da množica B generira polgrupni ideal I. Naj bo w∈I poljubna beseda in naj bo w′ neka podbeseda besedew z najmanjšo dolžino, da še vedno veljaw′ ∈I. Tedaj po definiciji množice B veljaw′ ∈B, torej množicaB res generira polgrupni ideal I.
Za dokaz s protislovjem, da je množica B res minimalna (glede na inkluzijo), privzemimo, da obstaja B′ ⊂ B, ki prav tako generira polgrupni ideal I. Potem obstaja beseda w ∈ B \B′ in posledično besede w′ ter α, β ∈ S, da je w = αw′β. Po definiciji množice B pa mora veljatiw=w′, kar je protislovje.
Nazadnje dokažimo še enoličnost. Denimo, da obstajata dve minimalni množici generatorjev ideala I, B in B′. Sedaj ponovimo argument iz dokaza minimalnosti za množici B′\B in B\B′.
Za konstrukcijo enolične Gröbnerjeve baze ideala potrebujemo tudi naslednji izrek in njegovo posledico.
Izrek 3.29 (Macaulayev izrek o bazi). Naj bo kS polgrupni kolobar inI njegov levi, desni ali dvostranski ideal. Kolobar kS je kot vektorski prostor enak direktni vsoti
kS=I⊕Link(I\LM(I)).
Dokaz. Če je neničelen element f ∈ I ∩Link(I \LM(I)), potem je LM(f) hkrati element LM(I) inI\LM(I), kar je protislovje, zato velja
I∩Link(I\LM(I)) = {0}.
Za dokaz, da je kS =I+ Link(I\LM(I)), vzemimof ∈kS in si oglejmo naslednji postopek, ki posplošuje algoritem za deljenje (algoritem 1). Začnemo z f0 = f, ϕ0 = 0 in h0 = 0. Dokler fi ̸= 0 ponavljamo naslednje. Če LM(fi)∈/ LM(I), potem nastavimo
ϕi+1 =ϕi, hi+1 =hi+ LT(fi), fi+1 =fi−LT(fi),
če pa je LM(fi)∈LM(I), obstaja tak eničen polinom g ∈I, da je LM(g) = LM(f), zato nastavimo
ϕi+1 =ϕi + LC(fi)g, hi+1 =hi, fi+1 =fi−LC(fi)g.
Zgornji postopek se ustavi, saj dokler fi ̸= 0, v vsakem koraku velja LM(fi) <
LM(fi−1), ≤ pa je dobra ureditev. Opazimo, da na vsakem koraku postopka velja, da je ϕi ∈I, hi ∈Link(I\LM(I)) in ključno
f =fi+ϕi+hi. Ko končamo s postopkom, je
f =ϕi+hi ∈I+ Link(I\LM(I)).
Naslednja posledica je sedaj očitna.
Posledica 3.30. Naj bo kS polgrupni kolobar inI njegov levi, desni ali dvostranski ideal. Za vsak polinomf ∈kSobstaja natanko en element NF(f)∈Link(I\LM(I)), da velja f−g ∈I.
V pomoč pri iskanju reducirane Gröbnerjeve baze nam bo, da si bolj podrobno ogledamo postopek deljenja polinomov.
Definicija 3.31. Naj bostaf, g∈k⟨X⟩nekomutativna polinoma. Polinomf lahko levo repno delimo s polinomom g, če obstajata koeficienta c, c′ ∈ k in monoma α, λ ∈ S, da je cα člen v zapisu polinoma f, ki ni vodilni, in cα = c′λLM(g). Rezultat repnega deljenja je enak h=f−c′λg.
Deljenju polinoma f s polinomom g, kjer odštejemo vodilni člen polinoma f, pravimo levo vodilno deljenje polinoma f s polinomom g.
Opomba 3.32. Na analogen način definiramo tudi desno in dvostransko repno in vodilno deljenje. Postopek deljenja polinoma f z množico F, kjer dopuščamo samo vodilno deljenje, označimo s f lead-modF.
Primer 3.33. Repno deljenje potrebujemo, da lahko na primer polinomy2−xyde- limo s polinomomxy. Množici{y2−xy, xy}in{y2, xy}namreč generirata isti ideal, njuni vodilni monomi pa isti ideal vodilnih monomov. Druga množica je manjša na način, da nobeden od polinomov v svoji vsoti členov ne vsebuje večkratnikov vodil- nih členov drugih polinomov.
Opomba 3.34. Seveda pa repno deljenje polinomov ne spremeni njihovega bistva s stališča iskanja Gröbnerjevih baz – vodilnih monomov. Za to je odgovorno vodilno deljenje. Repno deljenje je zato pomembno samo pri iskanju reducirane Gröbnerjeve baze.
Ključni postopek pri iskanju reducirane Gröbnerjeve baze je algoritem za med- sebojno redukcijo množice polinomov. Množico medsebojno zreduciramo tako, da vsak polinom v njej delimo z vsemi ostalimi in ga nato nadomestimo z dobljenim ostankom. Če smo pri tem našli polinom z ničelnim ostankom, ga preprosto odstra- nimo.
Algoritem 3: Algoritem za medsebojno redukcijo množice polinomov Input: končna množica polinomov G={g1, . . . , gs}
Output: končna množica polinomov i:= 1
while i̸=|G|+ 1 do
hi :=gi lead-mod G\ {gi} if hi = 0 then
G:=G\ {gi} i:=i+ 1
else if hi ̸=gi then G:= (G\ {gi})∪ {hi} i:= 1
else
i:=i+ 1 for g ∈G do
g :=g modG\ {g}
return G
Opazimo, da se v zgornjem algoritmu v primeru, ko hi ̸= 0 in hi ̸=gi, indeks i nastavi nazaj na 1. Dokazati moramo torej, da se algoritem 3 sploh ustavi.
Trditev 3.35. Algoritem 3 se ustavi v končnem številu korakov.
Dokaz. Pokažimo, da bo indeks enak |G|+ 1 v končnem številu korakov. V tem primeru se zanka while prekine in algoritem se ustavi. Če smo v koraku, kohi ̸= 0 in hi ̸= gi, to pomeni, da smo polinom gi vodilno delili z množico G\ {gi}, zato po algoritmu 1 velja LM(hi) < LM(gi). Ker je ≤ dobra ureditev, lahko indeks i nastavimo nazaj na 1le končno mnogokrat za vsak i= 1, . . . ,|G|. Ker jeG končna množica, se zanka while v algoritmu 3 res ustavi v končnem številu korakov.
Zanka for se ustavi v končnem številu korakov, saj v njej nastopa samo repno deljenje. Res, vzamemo polinom g ∈ G in njegove člene uredimo padajoče glede na ureditev ≤ ter jih preverjamo po vrsti. Če najdemo člen, ki je večkratnik vo- dilnega monoma katerega drugega polinoma iz množice G, polinom g zamenjamo z
rezultatom repnega deljenja polinoma g s tem polinomom. Po definiciji 3.31 smo najdeni člen zamenjali z vsoto členov, ki so vsi manjši glede na ureditev ≤. Ker je
≤ dobra ureditev, se vsak korak zanke for ustavi v končnem številu korakov. Ker je G končna množica, se algoritem 3 res ustavi.
Definicija 3.36. Naj bokSpolgrupni kolobar inI njegov levi, desni ali dvostranski ideal, kjerI ̸={0}. Baza idealaG⊂I jereducirana Gröbnerjeva baza zaI, če velja:
• množicaG je Gröbnerjeva baza ideala I,
• množica G je medsebojno zreducirana, tj. noben element g ∈ G v svojem zapisu ne vsebuje vodilnih monomov ostalih elementov množice G,
• za vse elementeg ∈G veljaLC(g) = 1.
Opomba 3.37. Gröbnerjevi bazi ideala I, ki ustreza prvima dvema, ne pa nujno tudi tretji zahtevi definicije 3.36, pravimo minimalna Gröbnerjeva baza.
Izrek 3.38. Za vsak levi, desni in dvostranski ideal I polgrupnega kolobarja kS obstaja enolično določena reducirana Gröbnerjeva baza.
Dokaz. Najprej dokažimo obstoj reducirane Gröbnerjeve baze. Spomnimo se, da je po opombi 3.19 ideal vodilnih monomov LM(I) polgrupni ideal polgrupe S. Po trditvi 3.28 obstaja enolična minimalna množica generatorjev B za polgrupni ideal LM(I). Brez škode za splošnost privzemimo, da jeB = LM(G)za neko Gröbnerjevo bazo G ideala I. Definiramo množico
G′ ={LM(g)−NF(LM(g)); g ∈G},
kjer za vsak polinomf ∈kSelementNF(f)tisti polinom, ki ga posledica 3.30 priredi polinomu f. Potem je LM(g)−NF(LM(g))∈I za vse g ∈ G, zato je G′ ⊆ I. Ker LM(G′) = LM(G) = B generira LM(I), je G′ po trditvi 3.25 prav tako Gröbnerjeva baza ideala I. Polinomi v G′ so po konstrukciji enični, po izreku 3.29 pa je množica G′ medsebojno zreducirana, zato je G′ reducirana Gröbnerjeva baza ideala I.
Za dokaz enoličnosti privzemimo, da obstajata dve reducirani Gröbnerjevi bazi G, H ideala I. Po zgornjem sta LM(G) in LM(H) minimalni generatorski množici polgrupnega ideala LM(I), zato sta po trditvi 3.28 enaki. Vzemimo elementag ∈G in h∈H, za katera velja LM(g) = LM(h). Seveda je g −h∈I, ker pa sta množici G in H medsebojno zreducirani, po izreku 3.29 velja tudi g−h∈Link(I \LM(I)). Po izreku 3.29 je potem g−h= 0, torej G=H.
V nadaljevanju bodo vsi algoritmi za računanje Gröbnerjevih baz izračunali le običajno Gröbnerjevo bazo (pod pogojem, da se ustavijo), zato samo omenimo, kako iz že dobljene končne Gröbnerjeve baze dobimo reducirano Gröbnerjevo bazo. To nam pove direktna posledica izreka 3.38.
Posledica 3.39. Naj bo I ⊆ k⟨X⟩ levi, desni ali dvostranski ideal kolobarja neko- mutativnih polinomov in naj bo Gneka končna Gröbnerjeva baza idealaI. Naj boG′ rezultat delovanja algoritma 3 na množici G. Potem je G′ reducirana Gröbnerjeva baza ideala I.
4 Buchbergerjev algoritem
V tem razdelku si bomo ogledali prvi algoritem za izračun Gröbnerjeve baze ideala, ki ga je Bruno Buchberger predstavil v svoji doktorski disertaciji [4] že leta 1965. V istem delu je tudi predstavil in poimenoval pojem Gröbnerjeve baze po svojem doktorskem mentorju Wolfgangu Gröbnerju. Potem bomo sledili korakom za po- splošitev algoritma na primer nekomutativnih polinomov, ki jih je Teo Mora povzel leta 1994 v [27].
4.1 Komutativen Buchbergerjev algoritem
4.1.1 Osnovna različica algoritma
Preden začnemo s prvotno različico Buchbergerjevega algoritma, definirajmo še ne- kaj pomožnih pojmov.
Definicija 4.1. Naj bostaf, g∈k[x1, . . . , xn]komutativna polinoma v spremenljiv- kah x1, . . . , xn. Najmanjši skupni monom polinomov f in g označimo z LCM(f, g) in definiramo kot najmanjši skupni večkratnik njunih vodilnih monomov z
LCM(f, g) = LCM(LM(f),LM(g)) =xγ11· · ·xγnn,
kjer je LM(f) = xα11· · ·xαnn, LM(g) = xβ11· · ·xβnn in γi = max{αi, βi} za vse i= 1, . . . , n. Tukaj eksponentomα1, . . . , αn, β1, . . . , βn dopuščamo tudi ničelno vre- dnost, če katera izmed spremenljivk v vodilnem monomu ni prisotna.
Opomba 4.2. Oznaka LCM za najmanjši skupni monom ali večkratnik sicer pride iz angleščine in pomeni least common multiple ali monomial, a je v računalništvu standardna, zato jo vseeno uporabimo.
Ključen pojem pri izračunu Gröbnerjevih baz so tako imenovani S-polinomi, ka- sneje tudiS-elementi,S-pari ali kritični pari, ki jih sedaj definiramo za komutativne polinome.
Definicija 4.3. Naj bosta f, g ∈ k[x1, . . . , xn] komutativna polinoma. Pripadajoči S-polinom definiramo kot
S(f, g) = LC(g)LCM(f, g)
LM(f) f−LC(f)LCM(f, g) LM(g) g.
Opomba 4.4. Ključni lastnosti S-polinoma komutativnih polinomov f in g sta naslednji:
1. Če je f =g, potem je S(f, g) = 0.
2. Vodilna člena polinomov, ki ju odštejemo v definiciji S-polinoma, sta enaka in se zato pokrajšata.
Ko bomo kasneje pojem posplošili za nekomutativne polinome, ga bomo definirali tako, da se bo druga lastnost ohranila, na prvo pa, kot bomo videli, v splošnem ne moremo računati.
Zakaj so S-polinomi tako pomembni nam pove naslednji izrek.
Izrek 4.5 (Buchbergerjev kriterij). Naj bo I ◁ k[x1, . . . , xn] ideal v kolobarju ko- mutativnih polinomov in naj bo G ={g1, . . . , gk} ⊂ I neka baza ideala I. Množica G je Gröbnerjeva baza za ideal I natanko tedaj, ko lahko vsak S-polinom S(gi, gj) za i, j ∈ {1, . . . , k} zapišemo kot vsoto
S(gi, gj) =
k
∑︂
l=1
hlgl (4.1)
za neke polinome h1, . . . , hk ∈k[x1, . . . , xn].
Dokaz. Dokazali bomo raje nekomutativno različico Buchbergerjevega kriterija (iz- rek 4.24), dokaz tega izreka je povsem analogen.
Opomba 4.6. Pogoj iz enačbe (4.1) pove, da je ostanek vseh S-polinomov iz po- linomov množice G pri deljenju z vsemi polinomi iz množice G enak ničelnemu polinomu.
Posledica 4.7. Naj bo I = (g) glavni ideal kolobarja k[x1, . . . , xn]. Potem je G= {g} Gröbnerjeva baza za I.
Dokaz. Ker je edini S-polinomS(g, g) ničelen, ta izjava takoj sledi iz izreka 4.5.
Oglejmo si osnovno različico Buchbergerjevega algoritma, ki za ideal s podano končno množico generatorjev ideala kolobarja k[x1, . . . , xn] izračuna Gröbnerjevo bazo.
Algoritem 4: Buchbergerjev algoritem – osnovna različica Input: končna množica polinomov F ⊂k[x1, . . . , xn] Output: Gröbnerjeva baza G za ideal(F)
G:=F repeat
G′ :=G
for p, q ∈G′ do
S := S(p, q)mod G′ if S ̸= 0 then
G:=G∪ {S}
untilG′ =G;
Izrek 4.8. Algoritem 4 se ustavi v končno mnogo korakih. Ob ustavitvi je množica G Gröbnerjeva baza ideala (F).
Dokaz. Algoritem se ustavi po izreku 3.21, v nasprotnem primeru bi bil (LM(G)) neskončno generiran monomski ideal v k[x1, . . . , xn]. Pravilnost nam potem očitno zagotavlja izrek 4.5.
4.1.2 Izboljšana različica algoritma
Že iz kode algoritma 4 je razvidno, da je algoritem v tej obliki sila potraten, tako časovno kot prostorsko. Nenavadno se zdi, da bi morali preveriti S-polinome prav vseh parov polinomov. Res, če je nek S-polinom skalarni ali celo polinomski več- kratnik nekega drugega, ga očitno ni treba (znova) preveriti. V nadaljevanju tega razdelka bomo zmanjšali množico polinomov, ki jih moramo preveriti, tako da bomo vnaprej izločili očitno nepotrebne polinome. Tistim polinomom, za katere še ne vemo, ali jih lahko izločimo, pravimo ovire. Poleg pospešitve osnovne različice al- goritma je to tudi prvi korak pri posplošitvi algoritma na nekomutativen primer. V naslednji definiciji podamo opis algoritma, ki bo to naredil za nas, naslednji izrek pa bo Buchbergerjev kriterij zožil le na preverjanje ovir.
Definicija 4.9. Naj bo {g1, . . . , gs} neka baza ideala I ◁ k[x1, . . . , xn] in naj bo brez škode za splošnost LC(gi) = 1 za vsak i = 1, . . . , s. Definiramo minimalno množico ovir OBS(j) za polinom gj z j ≥2 po naslednjem predpisu:
1. Začnemo z množico {︂
LCM(gi,gj)
LM(gj) ; 1≤i < j }︂.
2. Iz nje odstranimo vse elemente, ki so večkratniki drugih elementov iz te mno- žice.
3. Nato odstranimo še vse elemente oblike LCM(gLM(gij,g)j), za katere je LCM(gi, gj) = LM(gi) LM(gj).
4. Preostale elemente zberemo, vsakemu določimo indeks i, da je element enak
LCM(gi,gj)
LM(gj) in indekse zberemo v množico OBS(j).
S pomočjo zgornje definicije sedaj lahko formuliramo Buchbergerjev kriterij, ki deluje na manjši množici S-polinomov.
Izrek 4.10. Naj bo G = {g1, . . . , gs} baza ideala I ◁ k[x1, . . . , xn], za katero je LC(gi) = 1 za vsak i = 1, . . . , s. Množica G je Gröbnerjeva baza ideala I natanko tedaj, ko lahko za vsakj = 2, . . . , sin vsaki∈OBS(j)pripadajočiS-polinomS(gi, gj) zapišemo kot vsoto
S(gi, gj) =
s
∑︂
l=1
hlgl
za neke polinome h1, . . . , hs∈k[x1, . . . , xn].
Dokaz. Po izreku 4.5 drži implikacija iz leve v desno. Za obratno implikacijo vze- mimo i, j ∈ {1, . . . , s} in pokažimo, da lahko pripadajoči S-polinom zapišemo kot vsoto zgornjega tipa. Brez škode za splošnost lahko predpostavimo, da je i < j. Preveriti moramo le vse indekse, ki smo jih izvzeli pri postopku v definiciji 4.9. Če je LCM(gi, gj) = LM(gi) LM(gj), je
S(gi, gj) = LCM(gi, gj)
LM(gi) gi−LCM(gi, gj)
LM(gj) gj = LM(gj)gi−LM(gi)gj
