GRÖBNERJEVE BAZE IN REŠEVANJE SISTEMOV NELINEARNIH POLINOMSKIH ENAČB BRIGITA FERČEC1,2, MATEJ MENCINGER3,4 1Center za uporabno matematiko in teoretično fiziko, Univerza v Mariboru 2Fakulteta za energetiko, Univerza v Mariboru 3Fakulteta za gradbeništvo, prometno inženirstvo in arhitekturo Univerza v Mariboru 4Inštitut za matematiko, fiziko in mehaniko, Ljubljana Math. Subj. Class. (2010): 13A15, 13B25, 68N30 Obravnavamo Gröbnerjeve baze, ki so pomemben teoretični gradnik moderne teorije polinomskih kolobarjev. Razložimo pomen multideljenja, S-polinoma in Buchbergerjevega algoritma. Opišemo reševanje nekaterih problemov, ki se nanašajo na ideale v polinomskih kolobarjih in se osredotočimo na uporabo pri reševanju sistemov polinomskih enačb ter problemu implicitizacije. GRÖBNER BASES AND SOLVING NONLINAR POLYNOMIAL SYSTEMS Gröbner bases, which are an important building block of modern theory of polyno- mial ring theory, are considered. The meaning of the multidivision, S-polynomial and Buchberger’s algorithm is explained. The use of Gröbner bases in some theoretical aspects concerning the ideals in polynomial rings is considered. We are interested in the use of solving polynomial systems and implicitization problem. Uvod V grobem lahko rečemo, da uporabo Gröbnerjevih baz najdemo povsod, kjer nastopijo polinomski ideali oz. polinomske enačbe. Torej ne le v matematiki, temveč tudi v številnih drugih vedah – nekaterih inženirskih problemih, kot je na primer robotika [3, pogl. 6]. V matematiki Gröbnerjeve baze nasto- pijo pri odgovoru na vprašanje, ali je neki polinom element danega ideala, pri problemu enakosti idealov, izračunu preseka dveh ali več idealov in po- dobno (glej npr. [3, 9]). Teorijo Gröbnerjevih baz je leta 1965 vpeljal Bruno Buchberger [2]. Na teorijo lahko gledamo s stališča posplošitve Evklido- vega algoritma, pa tudi kot na posplošitev Gaussove eliminacije linearnega sistema, katere rezultat je (zgornje-) trikotna oblika linearnega sistema. Te- orija Gröbnerjevih baz omogoča računanje (deljenje) v kolobarju polinomov več spremenljivk, ki je analogno računanju (deljenju) v polinomskih kolo- barjih ene spremenljivke. Pogosto moramo v praksi rešiti sistem polinomskih enačb (več spremen- ljivk) f1 (x, y, z) = 0, f2 (x, y, z) = 0, f3 (x, y, z) = 0 (1) Obzornik mat. fiz. 62 (2015) 4 121 Brigita Ferčec, Matej Mencinger ali pa imamo podano ploskev ali krivuljo v parametrični obliki x = f1 (u, v) , y = f2 (u, v) , z = f3 (u, v) ; u, v ∈ R (2) ali x = f1 (t) , y = f2 (t) , z = f3 (t) ; t ∈ R (3) ali x = f1 (t) , y = f2 (t) ; t ∈ R (4) in želimo zapisati pripadajočo enačbo (enačbi) v implicitni obliki. Poglejmo si dva konkretna motivacijska primera: Primer 1. a) x = t5, y = t2 + 1, z = t3 − 1. b) x = u+v u−v , y = 2 v 2+u2 (u−v)2 , z = 2v v 2+3u2 (u−v)3 . c) x = u + v, y = 2uv + v2, z = 3uv2 + v3. Začnimo s primerom c). Če želimo iz enačb eliminirati parametra u in v, hitro opazimo, da zaradi nelinearnosti naloga ni tako preprosta, kot npr. pri linearnem primeru x = 1 + 2u − v, y = u + v, z = 2 − u + 3v. Čeprav lahko poskusimo s podobno »strategijo« in iz prvih dveh enačb nekako izrazimo parametra u in v (z x in y) in rezultata vstavimo v tretjo enačbo ter jo preoblikujemo tako, da le-ta ne vsebuje več nobenih korenov – nam po dolgem računanju celo uspe dobiti implicitno enačbo ploskve c): 4x3z + 4y3 − 3x2y2 − 6xyz + z2 = 0. V nadaljevanju tega članka želimo ugotoviti, ali lahko zgornjo enačbo do- bimo z metodo, podobno Gaussovi eliminaciji, oz. z neke vrste metodo na- sprotnih koeficientov. Nadaljujmo s krivuljo a), kjer nastopajo t5, t2 in t3. Spodnja računa ne potrebujeta dodatnih pojasnil, saj sta precej očitna: t5·2 = x2 in t2·5 = (y − 1)5, zato je (y − 1)5 − x2 = 0 in t5·3 = x3, (z + 1)5 = t3·5, zato je (z + 1)5 − x3 = 0. Tako dobljeni enačbi zagotovo pomenita implicitno enačbo krivulje a), ki pa verjetno ni »najboljša možna« v smislu najve- čje potence spremenljivk, ki v implicitnih enačbah nastopajo. Hitro lahko preverimo, da je ena od možnosti tudi y3 − 3y2 + 3y − z2 − 2z − 2 = 0 in yz + y − z − x − 1 = 0 (z najvišjo potenco 3). Nazadnje poglejmo še točko b): x = u + v u − v , y = 2 v2 + u2 (u − v)2 , z = 2v v2 + 3u2 (u − v)3 . 122 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb Hitro lahko preverimo, da z uvedbo nove spremenljivke t = u+v u−v enačbe b) postanejo »enoparametrične«: x = t, y = t2 + 1, z = t3 − 1, kar pomeni, da imamo za neskončno različnih vrednosti u in v isto vrednost t; torej se pri implicitizaciji lahko pojavi »problem inverza«, ki algebrsko pomeni problem neodvisnosti parametrov u in v (podrobnosti najdete v [6]). Zgoraj naštete probleme uspešno reši teorija Gröbnerjevih baz, ki npr. polinomom x− t5, y − t2 −1, z − t3 +1 priredi polinome −2+3y −3y2 +y3 − 2z − z2, 1 + x − y + z − yz, −1 + t + 2y − y2 + tz, −1 − t + ty − z, 1 + t2 − y, ki predstavljajo njihovo Gröbnerjevo bazo. Če bi bili eliminacijski problemi iz primera 1 linearni, bi bil rang razširjene matrike pripadajočega sistema manjši od števila neznank v sistemu. Če za linearni sistem velja, da sta ranga (pripadajoče) matrike sistema in razširjene matrike sistema enaka številu neznank, je rešitev enolična. V nadaljevanju bomo videli, da je edina ustrezna posplošitev Gaussove eliminacije za nelinearne polinomske sisteme iskanje Gröbnerjeve baze sis- temu pripadajočega ideala (polinomov sistema). Iz »novega« eliminacij- skega postopka mora biti na koncu tudi razvidno, ali je rešitev v obliki izoliranih točk, ali pa so rešitve krivulje, ploskve (tj. kakšna raznoterost pripada sistemu enačb). Osnovna ideja pri reševanju sistema (1) temelji na tako imenovanih S-polinomih in spominja na (srednješolsko) metodo nasprotnih koeficientov, zato ni presenetljivo, da pri tej teoriji postane po- membno tako imenovano »multideljenje« (posplošitev deljenja polinomov ene spremenljivke), kjer želimo polinom f (x1, . . . , xn) deliti z več polinomi p1 (x1, . . . , xn) , . . . , pk (x1, . . . , xn). Kot bomo videli, dobimo pri takem de- ljenju ustrezne koeficiente q1 (x1, . . . , xn) , . . . , qk (x1, . . . , xn) ter (enoličen) ostanek r (x1, . . . , xn) f = q1p1 + · · · + qkpk + r, kar bo podrobneje opisano v naslednjem poglavju. Primer 2. Motivacijo končajmo z dvema sistemoma oblike (1): (A) f1 = −xy3 − y2z + yz2 + 2xz3, f2 = z2 + xy + z, f3 = y2 + xz + y; (B) g1 = −xy3 − y2z + yz2 + 1xz3, f2 = z2 + xy + z, f3 = y2 + xz + y. Po eni strani (npr. po videzu) sta si sistema (A) in (B) zelo podobna, saj se razlikujeta le v enem koeficientu (prikazan z debelejšo pisavo). Po drugi strani pa sta sistema (A) in (B) bistveno različna, saj ima sistem (A) končno mnogo rešitev (rešitve so izolirane) za z, medtem ko ima sistem (B) za z neizolirane rešitve (jih je neskončno mnogo). Za zdaj povejmo, da razlog za to tiči v tem, da je g1 = −y2f2 + z2f3, čemur v nadaljevanju pravimo, da 121–137 123 Brigita Ferčec, Matej Mencinger je g1 v idealu, ki ga tvorita f2 in f3, oziroma da se deljenje polinoma g1 z množico {f2, f3} »izide«, medtem ko za f1 velja f1 = −y2f2 + z2f3 + xz3, čemur v nadaljevanju pravimo, da f1 ni element ideala, ki ga tvorita f2 in f3, oziroma da se deljenje polinoma f1 z množico {f2, f3} »ne izide« (ostanek r = xz3 je neničeln). Oboje lahko enostavno preverimo. Na koncu »iz- dajmo«, da je Gröbnerjeva baza množice polinomov {f1, f2, f3} (kar bomo definirali kasneje), če damo spremenljivki x »večji pomen« kot spremen- ljivki y in obema »večji pomen« kot spremenljivki z, enaka GA = {z4 + z5, z3 +yz3 +z4 +yz4, yz2 +y2z2, y2 +y3 −z2 −z3, y+y2 +xz, xy+z+z2}, med- tem ko je Gröebnerjeva baza množice polinomov {g1, f2, f3} enaka GB ={ y2 + y3 − z2 − z3, y + y2 + xz, xy + z + z2 } . Če za zdaj na Gröbnerjevo bazo pogledamo kot na preoblikovanje sistema f1 = 0, f2 = 0, f3 = 0 tako, da vedno ohranimo množico rešitev sistema, je očitno, da ima sistem (A) glede na neznanko z izolirane (realne) rešitve z1,2,3,4 = 0 in z5 = −1 (kot sledi iz prve enačbe z4+z5 = 0), medtem ko ima sistem (B) rešitve na krivu- lji ỹ2+ỹ3−z̃2−z̃3 = 0 (glej sliko 1b), torej so rešitve oblike ( − ỹ+ỹ2 z̃ , ỹ, z̃ ) , če je z̃ 6= 0, ter (x̃, 0, 0) oziroma (0, −1, 0) sicer. Na sliki 1a so v (y, z)-ravnini prikazane rešitve sistema (A); hitro lahko preverimo, da rešitev sestavljajo izolirane točke (0, −1, 0), (0, −1, −1), (0, 0, −1) ter premica (x, 0, 0). Osnovna ideja Gröbnerjevih baz je posplošiti korak v klasičnem algo- ritmu Gaussove eliminacije, kjer npr. par polinomov f = 5x + 2y − z − 1 in g = 3x + 4y − 2z − 2 zamenjamo z ekvivalentnim parom polinomov f = 5x + 2y − z − 1 in Sf,g = 7z − 14y + 7. Če koeficiente monomov (a) Rešitev sistema (A). (b) Rešitev sistema (B). Slika 1. Primer 2: rešitve projicirane na ravnino x = 0. 124 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb polinomov f in g zapišemo v prvo vrstico matrike, dobimo matriko ( 5 2 −1 −1 3 4 −2 −2 ) , kjer sta v prvem stolpcu matrike koeficienta pred spremenljivko x, v drugem stolpcu sta koeficienta pred spremenljivko y, v tretjem stolpcu sta koefici- enta pred spremenljivko z, v četrtem stolpcu pa stojita prosta člena obeh polinomov. Sedaj s pomočjo Gaussove metode (nasprotni koeficienti) eli- miniramo spremenljivko x v drugem polinomu, in sicer pomnožimo prvo vrstico matrike s 3 in drugo z −5 ter obe vrstici seštejemo, da dobimo ( 5 2 −1 −1 0 −14 7 7 ) . Poudarimo, da smo zadnjo vrstico dobili z metodo nasprotnih koeficientov: Sf,g = 15 5 (5x + 2y − z − 1) − 15 3 (3x + 4y − 2z − 2) = −14y + 7y + 7. V nadaljevanju tega poglavja bomo podali nekaj definicij, ki poma- gajo razumeti pomen Gröbnerjevih baz. Več podrobnosti in splošnejši pri- stop najdete na primer v [3, 9]. Obravnavajmo polinome f spremenljivk x1, . . . , xn s koeficienti iz polja k: f = ∑ α∈S aαx α1 1 · · · xαnn , kjer je S končna podmnožica množice Nn0 in α = (α1, . . . , αn). Pravimo, da je xα = xα11 · · · xαnn monom, aα ∈ k \ {0} koeficient in aαxα11 · · · xαnn člen polinoma. Množico vseh polinomov spremenljivk x1, . . . , xn s koeficienti iz k označimo s k[x1, . . . , xn]. Z operacijama seštevanje in množenje polinomov je k[x1, . . . , xn] komutativen kolobar. Nadalje rečemo, da je |α| = α1 + · · ·+ αn stopnja monoma ter st(f) = max{|α| : α ∈ S} stopnja polinoma. Za vsako naravno število n je kn = {(a1, . . . , an) : a1, . . . , an ∈ k} afin prostor dimenzije n. Množica polinomov f1, . . . , fs je naravno povezana s sistemom enačb f1(x1, . . . , xn) = 0, f2(x1, . . . , xn) = 0, . . . , fs(x1, . . . , xn) = 0, kar zapišemo krajše: ~f(~x) = ~0. (5) Množica vseh rešitev sistema (5) je definirana kot afina raznoterost, določena s polinomi f1, . . . , fs: V(f1, . . . , fs) = {(a1, . . . , an) ∈ kn : fj(a1, . . . , an) = 0 za 1 ≤ j ≤ s}. Ideal v k[x1, . . . , xn] je podmnožica I kolobarja k[x1, . . . , xn], ki zadošča naslednjima pogojema: 121–137 125 Brigita Ferčec, Matej Mencinger (i) če sta f, g ∈ I, potem je f + g ∈ I in (ii) če je f ∈ I in h ∈ k[x1, . . . , xn], je hf ∈ I. Kot najpreprostejši primer ideala v k[x1, . . . , xn] vzemimo množico vseh možnih linearnih kombinacij, ki lahko nastanejo iz polinomov f1, . . . , fs: 〈f1, . . . , fs〉 = { s∑ j=1 hjfj : h1, . . . , hs ∈ k[x1, . . . , xn] } . Ta množica je ideal, ki mu pravimo ideal, generiran s polinomi f1, . . . , fs. Če je ideal I ⊂ k[x1, . . . , xn] generiran s končno mnogo elementi f1, . . . , fs, pravimo, da je I končno generiran ideal. Potem je I = 〈f1, . . . , fs〉 in mno- žica {f1, . . . , fs} se imenuje baza ideala I. Na primer, baza ideala 〈f1, f2, f3〉 iz primera 2 (A) je {f2, f3}, baza ideala 〈g1, f2, f3〉 iz primera 2 (B) pa je {g1, f2, f3}. Po izreku o Hilbertovi bazi (glej npr. [3, str. 74: Theorem 4]) je vsak polinomski ideal v kolobarju k[x1, . . . , xn] končno generiran. Ekviva- lentno, vsaka naraščajoča veriga idealov I1 ⊂ I2 ⊂ I3 ⊂ · · · v k[x1, . . . , xn] se ustali [9, str. 4: Corollary 1.1.7], kar pomeni, da obstaja takšen m ≥ 1, da je Ij = Im za vsak j > m. Algebraična geometrija, ki obravnava zveze med algebro (ideali) in geo- metrijo (afine raznoterosti), je zelo obširna (glej npr. [3, 9]). Glavno vlogo pri tem imata »naravni« preslikavi, V (I), med množicama vseh afinih ra- znoterosti V in vseh idealov I ter radikal ideala. Preslikava I : V → I je definirana z I (V ) = {f ∈ k [x1, . . . , xn] : f (a1, . . . , an) = 0 za vse (a1, . . . , an) ∈ V } . (6) Preslikava V : I → V je definirana z 〈f1, . . . , fk〉 7−→ V (f1, . . . , fk) , (7) kjer je V (f1, . . . , fk) tako imenovana ničelna množica polinomov f1, . . . , fk (torej rešitev sistema f1 = 0, . . . , fk = 0). Radikal ideala I, ki ga označimo s √ I, je definiran takole: √ I = {f ∈ k[x1, . . . , xn] : obstaja tak p ∈ N, da je fp ∈ I}. Ideal I ⊂ k[x1, . . . , xn] je radikalni ideal, če je enak svojemu radikalu: I = √ I. Zvezo med algebro in geometrijo si bomo ogledali na primeru vsote in produkta idealov, ki imata tu zanimivo in pomembno vlogo, ki sledi iz formul za raznoterost vsote in produkta idealov: V (I + J) = V (I) ∩ V (J) , (8) 126 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb Slika 2. Ploskvi V(I) in V(J) iz primera 3. V (I · J) = V (I) ∪ V (J) . (9) Vsota, I + J, idealov I in J je ideal, definiran z vsemi možnimi vsotami elementov iz obeh idealov: I + J := {f + g : f ∈ I, g ∈ J} , produkt, I ·J, idealov I in J je ideal, definiran z (vsemi) vsotami produktov, kjer nastopajo faktorji iz obeh idealov: I · J := {f1g1 + · · · + frgr : f1, . . . , fr ∈ I, g1, . . . , gr ∈ J, r ∈ N} . Če sta I = 〈f1, . . . , fk〉 in J = 〈g1, . . . , gs〉, sta vsota I + J in produkt I · J generirana tako (glej npr. [3, str. 181–183]) I + J = 〈f1, . . . , fk, g1, . . . , gs〉 in I · J = 〈figj : 1 ≤ i ≤ k, 1 ≤ j ≤ s〉 , torej je 〈f1〉 + · · · + 〈fk〉 = 〈f1, . . . , fk〉. Geometrijska pomena enačb (8) in (9) si oglejmo na enostavnih primerih. Primer 3. Naj bosta I = 〈x + 2y + 6 − 2z〉 in J = 〈 x2 + y2 − z 〉 ideala v R [x, y, z] . Tedaj je I + J = 〈 x + 2y + 6 − 2z, x2 + y2 − z 〉 in V (I + J) = V (I) ∩ V (J), kot je prikazano na slikah 2 in 3. Primer 4. Naj bosta I = 〈 (x + y)2 , 2x2 − y − 1 〉 in J = 〈 x + y, x3 + 2y 〉 ideala v R [x, y] . Tedaj je I · J = 〈 (x + y)3,(x + y)2 ( x3 + 2y ) , ( 2x2 − y − 1 ) (x + y) , ( 2x2 − y − 1 )( x3 + 2y )〉 121–137 127 Brigita Ferčec, Matej Mencinger Slika 3. Presek ploskev V(I) in V(J) iz primera 3. Slika 4. Raznoterost V(I) iz primera 4 (dve točki). Slika 5. Raznoterost V(J) iz primera 4 (tri točke). Slika 6. Raznoterost V(I · J) iz primera 4 (pet točk). in V (I · J) = V (I) ∪ V (J) , kar je prikazano na slikah 4, 5 in 6. Opomba: Raznoterost V (I · J) je določena z x + y = 0 in ( 2x2 − y − 1 ) ( x3 + 2y ) = 0, kar nam da pet točk na sliki 6. V nadaljevanju opozorimo na pomen preslikav (6) in (7). Vemo, da vsaka raznoterost V določa neki ideal I (V ) in vsak ideal I določa neko raznoterost V (I). Če velja I (V1) = I (V2), je nujno V1 = V2, toda če je V (I1) = V (I2), ni nujno, da je I1 = I2. Najpreprostejši tak par je I1 = 〈x〉 in I2 = 〈 x2 〉 . Tudi za f1 = x2 − y2 in f2 = (x − y)2 (x + y) velja I1 = 〈f1〉, I2 = 〈f2〉 in I1 6= I2, toda V (I1) = V (I2). Iz enakosti raznoterosti pa sledi, da sta pripadajoča radikala enaka, √ I1 = √ I2. O tem govori tako imenovani Hilbertov Nullstellensatz [3, str. 170–171]. Izrek 1 (Krepki Hilbertov Nullstellensatz). Naj bo An afin prostor nad algebraično zaprtim poljem k in naj bo I ideal v k [x1, . . . , xn]. Tedaj za vsak ideal I ∈ k [x1, . . . , xn] velja I (V (I)) = √ I. 128 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb V nadaljevanju želimo natančno definirati Gröbnerjevo bazo in s tem povezano (že omenjeno) »multideljenje«. Zato najprej definirajmo monom- sko ureditev, <, v k[x1, . . . , xn] kot relacijo dobre ureditve < v množici Nn0 z naslednjima dvema lastnostma: (i) vsaka neprazna podmnožica monomov ima najmanjši element in (ii) če velja xα < xβ , potem velja xαxγ < xβxγ za vsak monom xγ . Najbolj običajna in splošno znana monomska ureditev je leksikografska ure- ditev: obravnavajmo monome x21x 8 2x 50 3 , x 3 1x 2 2x 5 3, x 2 1x 9 2x 4 3 ∈ R[x1, x2, x3] in recimo, da je x1 »pomembnejši« od x2 (in x3) in da je x2 »pomembnejši« kot x3. Potem je x31x 2 2x 5 3 > x 2 1x 9 2x 4 3 > x 2 1x 8 2x 50 3 . Splošno je xα < xβ natanko tedaj, ko prvi koordinati αi in βi od leve proti desni v α in β, ki sta različni, zadoščata αi < βi. Obstaja še veliko drugih monomskih ureditev: inverzna leksikografska, stopenjsko inverzna leksiko- grafska itd. (glej npr. [3, 9]). Če imamo opravka z več različnimi ureditvami, lahko poudarimo ime monomske ureditve. Na primer, leksikografsko uredi- tev označimo z Y . Če f delimo z urejeno množico (f1, f2), pričakujemo rezultat oblike f = q1f1 + q2f2 + r. Zapis sheme multideljenja je skladen s shemo multideljenja v [9, str. 14]. Oznaka √ f pomeni, da je f polinom, ki ga delimo z množico polinomov (f1 in f2). Oba vodilna člena LT (f1) = XY in LT (f2) = X2 delita vodilni člen LT (f) = X2Y . Toda ker je v urejeni množici (f1, f2), s katero delimo, najprej naveden f1, delimo X2Y z XY in dobimo X, ki ga zapišemo h kvocientu q1. Nato pomnožimo X s f1 in rezultat podpišemo pod polinom f , od katerega slednjega tudi odštejemo. Dobimo polinom XY 2 − XY , katerega vodilni člen delimo z LT (f1) in dobimo Y , ki ga pripišemo h q1. Postopek ponovimo in nov polinom, ki ga delimo z LT (f1) ali LT (f2), je −XY − Y 2. Njegov vodilni člen je prav tako deljiv z LT (f1): faktor −1 pripišemo h q1. Na koncu dobimo polinom −Y 2 + Y , katerega vodilni člen ni več deljiv niti z LT (f1) niti z LT (f2), zato vodilni člen −Y 2 pripišemo v 130 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb desni stolpec kot ostanek in ostane polinom Y , ki ga pa prav tako pripišemo k ostanku. Nazadnje h q2 pripišemo 0 in polinom −Y 2 + Y je (končni) ostanek, r, pri tem multideljenju. Celotna shema multideljenja je taka: q1 : X + Y − 1 q2 : 0 r f1 : XY + Y √ X2Y + XY 2 f2 : X2 + Y X2Y + XY XY 2 − XY XY 2 − XY XY 2 + Y 2 −XY − Y 2 −XY − Y −Y 2 + Y Y → −Y 2 0 → −Y 2 + Y, kar pomeni f = (X + Y − 1)f1 + 0f2 − Y 2 + Y. Po drugi strani, če zamenjamo »vrstni red« polinomov f1 in f2, torej če delimo z urejeno množico (f2, f1), s podobnim izračunom kot zgoraj dobimo f = Y f1 + Y f2 − 2Y 2. Očitno je rezultat tovrstnega deljenja zelo odvisen od vrstnega reda polino- mov, s katerimi delimo, saj lahko sprememba vrstnega reda spremeni tako vrednosti kvocientov q1, q2 kot tudi vrednost ostanka r. Ko delimo poli- nom f z množico polinomov F = (f1, f2), lahko pišemo f = { {q1, q2}, r } namesto f = q1f1 + q2f2 + r. Z uporabo teh simbolov lahko prvi pri- mer zapišemo kot f = { {X + Y − 1, 0}, −Y 2 + Y } , drugi primer pa po- meni f = { {Y, Y }, −2Y 2 } . Omenimo še, da je rezultat v osnovi odvi- sen tudi od izbire ureditve monomov. Če izberemo leksikografsko ureditev Y > X, je rezultat deljenja spet drugačen, kar je razvidno iz naslednjega primera, ki ga izvedemo s pomočjo sistema računske algebre Mathematica. V programu Mathematica se procedura deljenja polinoma f (x1, . . . , xk) z množico polinomov {f1, . . . , fn} (upoštevajoč ureditev x1 > . . . > xk) iz- vede z ukazom PolynomialReduce[f, {f1, . . . , fn}, {x1, . . . , xk}]. Rezultat je oblike {{q1, . . . , qn}, r} in pomeni f = q1f1 + q2f2 + · · · + qsfs + r. Na primer: PolynomialReduce[X2Y + XY 2, {XY + Y, X2 + Y }, {Y, X}] nam vrne {{−2 + 2X + Y, 2 − Y }, −2X2}, kar pomeni X2Y + XY 2 = (2X + Y − 2) · (XY + Y ) + (−Y + 2) · ( X2 + Y ) − 2X2. Iz primera 5 je razvidno, da lahko smiseln rezultat v zvezi z deljenjem polinoma z množico polinomov podamo samo pri vnaprej izbrani ureditvi in 121–137 131 Brigita Ferčec, Matej Mencinger pri vnaprej izbranem vrstnem redu polinomov v množici, s katero delimo. Multideljenje je smiselno definirati, kot kaže spodnji algoritem, ki je povzet po [9, str. 12]. Preden zapišemo algoritem, zapišimo definicijo reduciranosti ostanka r pri deljenju polinoma z množico polinomov. Definicija 1. Naj bodo f, f1, . . . , fs ∈ k[x1, . . . , xn], fj 6= 0 (za 1 ≤ j ≤ s) in naj bo F = {f1, . . . , fs}. Ostanek r ∈ k[x1, . . . , xn] je reduciran glede na F , če je bodisi r = 0 bodisi noben monom, ki nastopi v polinomu r, ni deljiv z nobenim elementom množice {LM(f1), . . . , LM(fs)}, tj. r ima manjšo stopnjo kot katerikoli polinom f1, . . . , fs. Sedaj si poglejmo algoritem multideljenja. V algoritem vstavimo f ∈ k [x1, . . . , xn] in urejeno množico F = (f1, . . . , fs) ∈ k [x1, . . . , xn] {0} . Rezultat algoritma so takšni polinomi q1, . . . , qs, r ∈ k [x1, . . . , xn], da velja: (i) f = q1f1 + · · · + qsfs + r, (ii) r je reduciran glede na (f1, . . . , fs), (iii) max (LM (q1) LM (f1) , . . . , LM (qs) LM (fs)) = LM (f) . Algoritem 1 (Multideljenje). Koraki algoritma v psevdokodu: POSTAVI q1 := 0, . . . , qs := 0, h := f DOKLER h 6= 0 DELAJ: ČE obstaja j tak, da LM (fj) deli LM (h) POTEM Za najmanjši j, za katerega LM (fj) deli LM (h): qj := qj + LT (h) LT (fj) , h := h − LT (h) LT (fj) fj SICER r := r + LT (h), h := h − LT (h). Zgornji algoritem je osnova za naslednji izrek, ki je povezan z deljenjem polinoma z množico polinomov. Izrek 2. Naj bo podana (urejena) množica polinomov F = (f1, . . . , fs). Naj bo v kolobarju k[x1, . . . , xn] izbrana monomska ureditev <. Tedaj lahko vsak polinom f ∈ k[x1, . . . , xn] zapišemo v obliki f = q1f1 + · · · + qsfs + r, kjer je r reduciran glede na F = {f1, . . . , fs}. 132 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb Dokaz lahko najdete na primer v [3, str. 62–63]. Če dobimo pri deljenju polinoma f z urejeno množico polinomov F ostanek r, to običajno krajše zapišemo takole: f F−→ r. V nadaljevanju želimo uporabiti algoritem multideljenja za rešitev nekaterih (dobro znanih) teoretičnih problemov teorije polinomskih kolobarjev (kot je na primer problem članstva v idealu in njegovem radikalu). Vemo, da ničeln ostanek pri deljenju polinoma f s polinomi f1, . . . , fs pomeni f ∈ I. Obrat tedaj ne velja (vedno). Četudi ima f pri deljenju s f1, . . . , fs neničeln ostanek, lahko obstaja deljenje polinoma f s polinomi f1, . . . , fs (v drugem vrstnem redu), ki da ostanek 0, saj smo videli, da ostanki (dokler ni izbrana monomska ureditev) niso enolično določeni. Poglejmo primer: Primer 6. Naj bo f = x2y + xy + 2x + 2, f1 = x2 − 1 in f2 = xy + 2. Izberimo leksikografsko ureditev x > y. Potem z algoritmom multideljenja dobimo f = yf1 + f2 + (2x + y). Ostanek r = 2x+y je neničeln in tako bi lahko zaključili, da f /∈ 〈f1, f2〉. Če pa spremenimo vrstni red deliteljev f1 in f2, imamo f F−→ 0 za F = (f2, f1), saj je f = 0f1 + (x + 1)f2 + 0, kar pomeni f ∈ 〈f1, f2〉. Kot bomo videli kasneje, lahko težave, ki so nakazane v primeru 6, odpravimo z definicijo Gröbnerjevih baz. Gröbnerjeve baze in njihova uporaba Gröbnerjeva baza ideala 〈f1, . . . , fs〉 je posebna množica {g1, . . . , gt}, za ka- tero algoritem 1 (multideljenje) iz prejšnjega poglavja za poljuben polinom f vrne ostanek r = 0 natanko tedaj, ko je f ∈ 〈f1, . . . , fs〉. Natančneje: Gröb- nerjeva baza ideala I ⊂ k[x1, . . . , xn] je končna podmnožica G = {g1, . . . , gt} ideala I z lastnostjo 〈LT (I)〉 = 〈LT (g1), . . . , LT (gt)〉. Spodnji izrek je splošno znan (glej npr. [3, str. 75]). Poudarimo, da je funkcija LT (in LM) smiselna samo pri izbrani (znani) monomski ureditvi <. Izrek 3. Vsak neničelni ideal I ⊂ k[x1, . . . , xn] ima Gröbnerjevo bazo. 121–137 133 Brigita Ferčec, Matej Mencinger Če je G = {g1, . . . , gt} Gröbnerjeva baza ideala I, je očitno ostanek vsakega polinoma f ∈ I pri multideljenju enoličen. Če je f = q1g1 + · · · + qtgt + r in f = q′1g1 + · · · + q′tgt + r′, potem je r − r′ = (q1 − q′1)g1 + · · · + (gt − q′t)gt ∈ I. Če je r − r′ 6= 0, je LT (r − r′) ∈ 〈LT (I)〉, kar pomeni, da LT (gi) deli LT (r − r′) za neki i. To je protislovje, saj noben člen ostankov r in r′ ni deljiv z LT (gi) za noben i = 1, . . . , t. Zato je r = r′ in qi = q′i za vsak i = 1, . . . , t. Gröbnerjeva baza je tesno povezana s tako imenovanim S-polinomom za dan par polinomov f, g ∈ k[x1, . . . , xn]; gre za posplošitev S-polinoma, defi- niranega v uvodu. Naj bosta f, g ∈ k[x1, . . . , xn] neničelna polinoma. Naj- manjši skupni večkratnik njunih vodilnih monomov naj bo LCM(LM(f), LM(g)) = xγ . Potem je S-polinom polinomov f in g definiran kot Sf,g = xγ LT (f) · f − x γ LT (g) · g. Opazimo, da S-polinomi poskrbijo za eliminacijo vodilnih členov in so v bistvu edini način, da se ta eliminacija zgodi med seštevanjem členov iste stopnje. Buchbergerjeva osnovna ideja pri definiciji Gröbnerjevih baz je bil na- slednji kriterij. Naj bo I ideal. Potem je G = {g1, . . . , gt} Gröbnerjeva baza ideala I natanko tedaj, ko je za vsak i 6= j ostanek deljenja polinoma Sgi,gj z G enak nič: Sgi,gj G−→ 0. Buchbergerjev algoritem, ki je prikazan v nadaljevanju, je povzet po [9]; prvič je bil opisan v Buchbergerjevi doktorski disertaciji [3]. Algoritem zahteva vnos množice polinomov {f1, . . . , fs} ∈ k [x1, . . . , xn] \ {0} in vrne Gröbnerjevo bazo G ideala 〈f1, . . . , fs〉. Algoritem 2 (Buchberger). Procedura v psevdokodu je: POSTAVI G := {f1, . . . , fs} . Korak 1. Za vsak par gi, gj ∈ G, i 6= j, izračunaj Sgi,gj S pomočjo algoritma za multideljenje izračunaj ri,j : Sgi,gj G−→ ri,j ČE Vsi ri,j = 0, izpiši G SICER K množici G dodaj vse neničelne ri,j in se vrni na Korak 1. Opomnimo, da imajo vsi najučinkovitejši sistemi računske algebre ukaze (»rutine«) za izračun Gröbnerjevih baz. V sistemu Mathematica je ukaz 134 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb GroebnerBasis. Ker Buchbergerjev algoritem temelji na algoritmu 1, ta pa temelji na monomski ureditvi členov, je izračun Gröbnerjeve baze odvisen od monomske ureditve. (Toda pri izbrani monomski ureditvi je Gröbnerjeva baza enolična.) Poleg Mathematice imajo takšne rutine med drugimi še Singular in Maculay2. Opazimo, da lahko Buchbergerjev algoritem proizvede več baznih ele- mentov, kot je potrebno, in s tega stalšča ni optimalen. To pa lahko izbolj- šamo, če zahtevamo dodatni pogoj, da noben člen polinoma gi ni deljiv z LT (gj) za j 6= i. Enoličnost množice G končno zagotovimo, če zahtevamo še, da je vsak gi moničen (tj. LC(gi) = 1 za vsak i). Tako dobimo t. i. reducirano Gröbnerjevo bazo. Reducirana Gröbnerjeva baza vedno obstaja in je enolična (glej npr. [9, Theorem 1.2.24]). Preprost algoritem, ki pro- izvede reducirano Gröbnerjevo bazo in se začne s katerokoli Gröbnerjevo bazo, je naslednji: začnemo z G in naredimo vsak polinom gi ∈ G moničen, nato vsak g ∈ G zamenjamo z njegovim ostankom pri deljenju g z elementi G\{g} (pri fiksni monomski ureditvi). Seveda ukazi v vseh sistemih račun- ske algebre izračunajo Gröbnerjevo bazo, ki je že reducirana. Na primer: Gröbnerjeva baza ideala I = 〈−x3 + y, x2y − y2〉 glede na leksikografsko ureditev x > y je G = {−y2 + y3, −y2 + xy2, x2y − y2, x3 − y}. V nadaljevanju bomo obravnavali problem iskanja Gröbnerjeve baze v zvezi z nelinearnimi sistemi enačb. Med številnimi uporabami Gröbnerjevih baz bomo na koncu omenili tudi uporabo pri celoštevilskem programiranju, kjer uporabimo Gröbnerjevo bazo z uteženo ureditvijo (glej [5]). Recimo, da iščemo rešitev (a1, . . . , an) ∈ kn (nelinearnega) polinomskega sistema (5), kjer je k algebraično zaprtje polja k. Naslednji izrek (glej [3, str. 170]) poda kriterij za obstoj rešitve sistema (5). Izrek 4. Naj bo G = {g1, . . . , gt} reducirana Gröbnerjeva baza ideala 〈f1, . . . , fs〉. Sistem nima rešitve natanko tedaj, ko je G = {1}. Med glavnimi problemi v teoriji polinomskih kolobarjev je problem, ali je neki polinom f v danem idealu I = 〈f1, . . . , fn〉, in problem, ali je neki polinom v radikalu √ I [9, str. 30]. S tem problemom je povezanih več sorodnih problemov; od relacije (v smislu podmnožice) med dvema idealoma do enakosti idealov in preseka idealov [9, str. 36–37], ter nenazadnje problem tako imenovane primarne dekompozicije ideala [9, str. 40–42]. Če sistem (5) nima končno mnogo rešitev, je za njegovo razrešitev treba izračunati primarno dekompozicijo ideala I, kar je znatno zahtevnejše kot račun v spodnjem primeru (podrobnosti glej v [9, poglavje 1.4]), kjer je prikazan tudi postopek uporabe Buchbergerjevega algoritma. 121–137 135 Brigita Ferčec, Matej Mencinger Primer 7. Poiščimo rešitev sistema: f1 = x 2 + y = 0, f2 = 2x 2y + x4 = 0, f3 = xz + x 4 + xy + x2y2 = 0. Izračunajmo Gröbnerjevo bazo z uporabo Buchbergerjevega algoritma. Fiksiramo leksikografsko ureditev z > y > x in uredimo zapis polinomov f1, f2, f3 glede na to ureditev: f1 = y + x 2, f2 = 2yx 2 + x4, f3 = zx + y 2x2 + yx + x4. Sedaj izračunamo posamezne S-polinome, ki so Sf1,f2 = yx2 y (y + x2) − yx2 2yx2 (2yx2 + x4) = x 4 2 , Sf1,f3 = zyx y (y + x2) − zyx zx (zx + y2x2 + yx + x4) = zx3 − y3x2 − y2x − yx4, Sf2,f3 = zyx2 2yx2 (2yx2 + x4) − zyx2 zx (zx + y2x2 + yx + x4) = zx 4 2 − y3x3 − y2x2 − yx5. Sedaj Sf1,f2 = 1 2x 4 delimo z urejeno množico polinomov (f1, f2, f3) in do- bimo ostanek 12x 4. Ker je le-ta neničeln, ga pripišemo k začetni množici polinomov in dobimo urejeno množico G = (f1, f2, f3, f4), kjer je f4 = 12x 4. Če delimo polinoma Sf1,f3 in Sf2,f3 z množico polinomov G, obakrat do- bimo ostanek 0. Tako je Gröbnerjeva baza ideala 〈f1, f2, f3〉 enaka GB = {f1, f2, f3, f4}. Bazo reduciramo tako, da vse vodilne koeficiente polinomov f1, f2, f3 in f4 postavimo na 1. Opazimo tudi, da če polinom f2 delimo z množico (f1, f4), dobimo ostanek 0. Zato lahko f2 odstranimo iz Gröb- nerjeve baze. Če pa polinom f3 delimo z množico (f1, f4), dobimo ostanek zx − x3, ki ga v Gröbnerjevi bazi zapišemo namesto f3. Tako je reducirana Gröbnerjeva baza ideala 〈f1, f2, f3〉 enaka GR = {y + x2, x4, zx − x3}. Sedaj lahko sistem f1 = f2 = f3 = 0 rešimo zelo preprosto. Ker je drugi polinom v GR odvisen samo od spremenljivke x, je očitno x = 0. Prvi polinom v Gröbnerjevi bazi vsebuje samo x in y, od koder sledi y = 0. Zadnji polinom vsebuje spremenljivki x in z, x = 0 pa očitno reši enačbo zx − x3 = 0 za vsak z, torej je z poljuben in sistem ima neskončno rešitev, ki jih zapišemo kot {(0, 0, z) : z ∈ R}. 136 Obzornik mat. fiz. 62 (2015) 4 Gröbnerjeve baze in reševanje sistemov nelinearnih polinomskih enačb Nazadnje omenimo, da lahko s pomočjo Gröbnerjevih baz rešujemo splo- šni problem celoštevilskega programiranja (IP) (glej [5]), ki se glasi takole: minimiziraj ~c · ~x pri pogoju A~x = ~b, (10) kjer je A ∈ Zm×n in ~b = (b1, . . . , bm)T ∈ Zm, in da je zelo obsežna tudi uporaba Gröbnerjevih baz pri kvalitativni obravnavi sistemov navadnih di- ferencialnih enačb (glej npr. [4, 8, 9]). LITERATURA [1] M. Beaudin, G. Picard in G. Savard, Polynomial Systems Solving with Nspire CAS, V: Galán García, José Luis (ur.). ACA 2013, Málaga, July 2nd–6th, 2013, Hotel Málaga Palacio, Málaga, Spain. Proceedings of Applications of Computer Algebra, 2013, str. 41. [2] B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restlasse- nringes nach einem nulldimensionalen Polynomideal, PhD Thesis, Mathematical In- stitute, University of Innsbruck, Austria, 1965; An Algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, J. Symbolic Comput. 41 (2006), 475–511. [3] D. Cox, J. Little in D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd edition, Springer, New York, 2007. [4] V. F. Edneral, A. Mahdi, V. G. Romanovski in D. S. Shafer, The center problem on a center manifold in R3, Nonlinear Anal. 75 (2012), 2614–2622. [5] S. Flory in E. Michel, Integer Programming with Gröbner basis, http://www. iwr.uni-heidelberg.de/groups/amj/People/Eberhard.Michel/Documents/Else/ DiscreteOptimization.pdf, ogled 29. 9. 2015. [6] X. S. Gao in S. Chou, Implicitization of rational parametric equations, J. Symbolic Comput. 14 (1992), 459–470. [7] G.-M. Greuel, G. Pfister in H. A. Schönemann, SINGULAR 3.0 A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserlautern (2005), http://www.singular.uni-kl.de, ogled 29. 9. 2015. [8] V. Romanovski, M. Mencinger in B. Ferčec, Investigation of center manifolds of three- dimensional systems using computer algebra, Program. comput. softw. 39 (2013), 67–73. [9] V. G. Romanovski in D. S. Shafer, The Center and cyclicity Problems: A computa- tional Algebra Approach, Birkhäuser, Boston, 2009. http://www.dmfa-zaloznistvo.si/ 121–137 137