Bevezetés a Gröbner-bázisok elméletébe

Bevezetés a Gröbner-bázisok elméletébe Oktatási segédlet a Komputer algebra c. tárgyhoz

Felszeghy Bálint

Tartalomjegyzék 1. Bevezetés

3

2. Alapfogalmak és a Gröbner-bázisok elemi tulajdonságai 2.1. Jelölések . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Tagsorrendek . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Standard monomok és főtagok . . . . . . . . . . . . . . . . 2.4. A Gröbner-bázis . . . . . . . . . . . . . . . . . . . . . . . . Gröbner-bázis létezése . . . . . . . . . . . . . . . . . . . . Redukció . . . . . . . . . . . . . . . . . . . . . . . . . . . . A redukált Gröbner-bázis . . . . . . . . . . . . . . . . . . . 2.5. Eltűnő ideálok . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

5 5 5 8 9 10 11 14 15

3. Algoritmusok 17 3.1. Buchberger algoritmusa . . . . . . . . . . . . . . . . . . . . . . 17 3.2. A Buchberger–Möller-algoritmus . . . . . . . . . . . . . . . . . 20 4. Alkalmazások 4.1. Elemi kommutatív algebrai kérdések . . . . . Ideál egy elemének megadása generátorokkal . Ideálok egyenlősége . . . . . . . . . . . . . . . Számítások F [x] /I-ben . . . . . . . . . . . . . Ideálok metszetének generátorrendszere . . . . 4.2. Polinom-egyenletrendszerek megoldása . . . . Kommutatív algebrai alapok . . . . . . . . . . A megoldások száma, nulla dimenziós ideálok Polinom-egyenletrendszerek normálformája . . 4.3. Kombinatorikai alkalmazások . . . . . . . . . A Hilbert-függvény . . . . . . . . . . . . . . . Egy extremális halmazelméleti eredmény . . .

2

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

27 27 27 28 28 29 30 30 31 35 37 38 40

1. Bevezetés Ebben a jegyzetben a Gröbner-bázisok elméletével foglalkozunk. Az alapok bemutatásán kívül a téma néhány újabb eredményét is tárgyaljuk. Később természetesen a pontos definíciók is szerepelnek, egyelőre annyit mondunk, hogy egy polinomideál Gröbner-bázisa az ideál egy jó fajta generátorrendszere. A Gröbner-bázis fogalma Bruno Buchberger osztrák matematikustól származik, aki mintegy 40 éve [5] Ph. D. tézisében (az angol fordítást nemrég adták ki [6]) és valamivel később megjelent [7] (angol nyelven [8] kiadványban) cikkében dolgozta ki az elmélet alapjait. Buchbergert elsősorban kommutatív algebrai és algebrai geometriai kérdések motiválták, de a témavezetője tiszteletére elnevezett Gröbner-bázis – miközben a hetvenes években egyre ismertebbé vált – a matematika legkülönbözőbb területein lelt alkalmazásokra. A 33 Years of Gröbner Bases címmel tartott konferencia kiadványa [8] ezeknek egy jó összefoglalóját adja: ismertet alkalmazásokat a kódelméletben, az egész programozásban, az automatikus tételbizonyításokban, a szimbolikus számítások elméletében, a statisztikában, a parciális differenciálegyenletek elméletében és a numerikus módszerekben. A technika ereje abban rejlik, hogy eszközöket szolgáltat többismeretlenes polinomiális egyenletrendszerek megoldásainak vizsgálatára. A Gröbner-bázisokkal egyszerűen végezhető, redukciónak nevezett művelet közös általánosítása a lineáris egyenletrendszerek megoldásából ismert Gauss-eliminációnak és az egyismeretlenes polinomiális egyenletrendszerek megoldhatóságának eldöntéséhez szükséges euklideszi algoritmusnak.1 A Gröbner-bázisok elmélete nagyon is élő kutatási terület, minden évben temérdek új cikk jelenik meg a témakörben. Jelen jegyzetben igyekeztünk a már klasszikusnak számító eredmények bemutatása után a modern alkalmazásokból is ízelítőt adni. A 2. fejezetben ismertetjük az elmélet alapjait. A felépítésben a szokásos szemléletet ötvözzük egy, a legtöbb bevezető jellegű könyvben kevéssé hangsúlyos, modernebb hozzáállással: az ideálok standard monomjainak fontos szerepet szánunk. A 3. fejezet algoritmusokról szól. Buchberger eredeti módszere, amellyel 1

2006 tavaszán a linzi Kepler Egyetemen került megrendezésre egy Gröbner-bázisokról szóló speciális félév (Buchbergerrel a szervezők között), amelyen én is eltöltöttem egy hónapot. A rengeteg szakmai jellegű információ mellett azt is megtudtam, hogy Linzben a mérnök hallgatók matematika tananyagának részét képezik a Gröbner-bázisokról, mint polinom-egyenletrendszereket megoldó módszerről szóló ismeretek. Meggyőződésem, hogy nem csupán a hely szelleme miatt van ennek létjogosultsága, a Gröbner-bázisok széleskörű alkalmazhatósága és az alapok egyszerű elsajátíthatósága okán érdemes lenne más egyetemeknek is követniük ezt a példát.

3

egy általános polinomideál Gröbner-bázisa számítható ki, szerepel minden a témába bevezető könyvben. Itt Adams és Loustaunau [2] munkáját választottuk a leírás alapjául. Tárgyalunk egy további algoritmust, amely egy véges pontrendszerhez tartozó Gröbner-bázist számol; az általánosság megszorításáért kárpótlásul algoritmuselmélészi szemmel nézve is igen hatékonyan. A Buchberger–Möller-algoritmus néven ismert módszer bemutatásában főként Teo Mora és Lorenzo Robbiano [23] összefoglaló cikkére hagyatkozunk. Végül az utolsó fejezetben alkalmazásokról írunk. Két nagy területet választottunk erre: kommutatív algebrai számolgatásokról – beleértve polinomiális egyenletrendszerek megoldását is –, és kombinatorikai alkalmazásokról szólunk. Utóbbiak között sort kerítünk egy általánosabb módszerre, amely segítségével sok kombinatorikai probléma lefordítható algebrai kérdéssé. Erre mutatunk példát a nemrégiben született [15] cikk (néhány számolósabb részletet mellőző) bemutatásával. A legtöbb matematikai program – így a Maple és a Mathematica is – tartalmaz Gröbner-bázist számoló algoritmust, és használ Gröbner-bázisokat más jellegű kérdések eldöntésére. Kifejezetten polinom-számítások végzésére fejlesztették ki a Singular és a C++ alapú CoCoA programcsomagokat; az Olvasónak a jegyzetben tanultak gyakorlásához mindenképpen ez utóbbiakat javasoljuk. A legújabb algoritmusok a publikásukkal szinte egyidőben megjelennek ezekben (ami az előbbi két programra nem igaz), ráadásul mindkét program szabadon letölthető (http://www.singular.uni-kl.de és http://cocoa.dima.unige.it). A témában komolyabban elmélyedni szándékozóknak elsősorban a komputer algebrai számítások szemszögéből, de egyúttal kellő elméleti mélységgel megírt [19] könyvet ajánljuk. Alapos és az általunk leírtnál általánosabb tárgyalást találhatunk például [2] és [3] könyvekben is.

4

2. Alapfogalmak és a Gröbner-bázisok elemi tulajdonságai Mielőtt rátérnénk a legfontosabb fogalmak definiálására, bevezetünk néhány jelölést, amelyeket végig használni fogunk.

2.1. Jelölések A nemnegatív egészek, az egészek és a racionális számok halmazát rendre N, Z és Q rövidíti, Fp pedig a p elemű véges testet jelöli. A jegyzetben F mindvégig egy tetszőleges test lesz, n pedig egy pozitív egész. Az {1, 2, . . . , n} halmazra röviden [n] halmazként hivatkozunk, az F feletti n változós polinomgyűrűre pedig a szokásos F [x1 , . . . , xn ] jelölést használjuk. wn 1 w2 Monomok alatt xw 1 x2 . . . xn ∈ F [x1 , . . . , xn ] alakú polinomokat értünk. Az F [x1 , . . . , xn ] polinomgyűrű tekinthető F feletti vektortérnek (sőt akár algebrának), ennek a monomok egy lineáris bázisát alkotják. Azt mondjuk, wn 2 hogy egy x1w1 xw 2 . . . xn monom szerepel f -ben, ha f -et monomok lineáris wn 1 w2 kombinációjaként előállítva xw 1 x2 . . . xn együtthatója nem nulla. Ha f1 , . . . , fm ∈ F [x1 , . . . , xn ], akkor az általuk F [x1 , . . . , xn ] gyűrűben generált ideált hf1 , . . . , fm i jelöli. Vektorok megkülönböztetésére félkövér betűket használunk, koordinátáikra pedig ugyanazon betű megfelelően számozott nem vastag változatával hivatkozunk, például w = (w1 , . . . , wn ). Hasonlóan, f (x) ∈ F [x] rövidíti wn 1 w2 f (x1 , . . . , xn ) ∈ F [x1 , . . . , xn ]-et, xw pedig az xw 1 x2 . . . xn monomot.

2.2. Tagsorrendek 2.1. Definíció. Egy, az F [x] monomjain értelmezett ≺ teljes rendezést tagsorrend nek nevezzük, amennyiben minden xw ∈ F [x] monomra 1 ¹ xw , és minden xw , xu , xv ∈ F [x] monomra, amelyre xu ≺ xv , teljesül xu · xw ≺ xv · xw is. Gröbner-bázisról mindig egy rögzített tagsorrendet feltételezve beszélünk, más rendezéshez általában más polinomhalmaz lesz Gröbner-bázis. Bizonyos alkalmazásokban elegendő egy tetszőleges Gröbner-bázis meghatározása, míg egyes esetekben egyéb tulajdonságoknak is eleget tevő tagsorrendek szükségesek. A következőkben mutatunk néhány példát, és egyben definiáljuk a leggyakrabban használt három tagsorrendet. 2.2. Definíció. Azt mondjuk, hogy xw a lexikografikus rendezés szerint kisebb vagy egyenlő, mint xu , ha a legkisebb i-re, amelyre wi 6= ui , arra 5

wi < ui tejesül. Nyilvánvaló, hogy a lexikografikus rendezés tagsorrend. Ezt a rendezést ezentúl röviden lex nek fogjuk nevezni. 2.3. Definíció. A másik gyakran használt tagsorrend a fok-kompatibilis lexikografikus rendezés, az angol degree compatible lexicographic rövidítéseként deglex. Egy xw deglex-kisebb mint xu , amennyiben xw foka kisebb, mint xu n n P P ui ) vagy pedig azonos fokúak, és xw megelőzi xu -t a wi < foka (azaz i=1

i=1

lexikografikus rendezés szerint. A tagsorrendtől megkívánt tulajdonságok a deglex rendezésre is triviálisan teljesülnek. Végül egy, az első pillantásra különös tagsorrend a degrevlex:

2.4. Definíció. Monomok fok-kompatibilis fordított lexikografikus – gyakoribb nevén degrevlex – sorrendje a következő. A kisebb fokú monom kisebb, azonos fokok esetén pedig xw kisebb, mint xu pontosan akkor, ha a legnagyobb i indexnél, amelynél wi 6= ui , ott wi > ui teljesül. Általában is fok-kompatibilisnek hívunk egy tagsorrendet, ha teljesül, hogy kisebb fokú monomok a rendezésben kisebbek. 2.1. Feladat. Igazoljuk, hogy n = 1-re minden tagsorrend megegyezik, n = 2-re pedig pontosan két különböző fok-kompatibilis rendezés létezik. Például n = 3 esetén az első néhány monom lex rendezése: 1 ≺ x3 ≺ x23 ≺ x33 ≺ · · · ≺ x2 ≺ x2 x3 ≺ x2 x23 ≺ · · · ≺ x22 ≺ x22 x3 ≺ x22 x23 ≺ · · · ≺ x1 ≺ x1 x3 ≺ x1 x23 ≺ . . . , deglex rendezése: 1 ≺ x3 ≺ x2 ≺ x1 ≺ x23 ≺ x2 x3 ≺ x22 ≺ x1 x3 ≺ x1 x2 ≺ x21 ≺ x33 ≺ . . . és degrevlex rendezése: 1 ≺ x3 ≺ x2 ≺ x1 ≺ x23 ≺ x2 x3 ≺ x1 x3 ≺ x22 ≺ x1 x2 ≺ x21 ≺ x33 ≺ . . . 2.2. Feladat. Mutassuk meg, hogy a lex, deglex, és degrevlex rendezések valóban tagsorrendek. Definiáljuk a revlex rendezést értelemszerűen, és lássuk be, hogy ez nem tagsorrend. (A revlex lokális rendezés. Bizonyos gyűrűkben ilyenek segítségével definiálható Gröbner-bázis, amely az általunk tárgyalt általánosítása.)

6

A változók sorrendjének variálásával nyilván további tagsorrendeket kaphatunk. Ez természetesen még nem az összes. Mielőtt rátérünk a tagsorrendek számunkra fontos tulajdonságainak tárgyalására, bizonyítás nélkül közöljük ezen rendezések egy szép jellemzését. Legyen a egy nemnegatív valós számokból álló n hosszú vektor. Egy w x monom a-val súlyozott fokszáma a és w skaláris szorzata, azaz a1 w1 + a2 w2 + · · · + an wn . Legyen A egy n × n-es nemnegatív valós elemekből álló invertálható mátrix, és definiáljunk a segítségével tagsorrendet a következő módon. Egy xw monom legyen kisebb, mint xu , ha A első sora, mint súlyvektor szerinti súlyozott fokszáma xw -nek kisebb. Amennyiben ezek egyenlőek, hasonlítsuk össze az A második sora szerinti súlyozott fokszámokat. Az eljárást folytatva teljes rendezést kapunk, hiszen amennyiben xw és xu összes A szerinti súlyozott fokszáma egyenlő, akkor w-t és u-t oszlopvektorként tekintve Aw = Au, így w = u, hiszen A reguláris. Teljesül 1 ¹ xw , mivel xw tetszőleges súlyozott fokszáma nemnegatív. Végül a tagsorrendtől megkívánt harmadik tulajdonság abból következik egyszerűen, hogy xu · xw súlyozott fokszáma éppen xu és xw súlyozott fokszámainak összege. Robbiano [24] (vagy vázlatosan [25]) igazolta, hogy tetszőleges tagsorrend előáll ilyen alakban valamilyen alkalmasan választott A mátrixszal. A lex rendezést például megadja az n × n-es identitás, a deglexet pedig az   1 1 1 ... 1  1 0 0 ... 0     0 1  0 . . . 0     . .   . 0 ... 0 1 0

mátrix.

2.3. Feladat. Írjuk fel a degrevlex egy mátrix-reprezentációját! A következő tételben bebizonyítjuk a tagsorrendek két alapvető tulajdonságát. A jólrendezésről szóló állítás Dickson-lemma néven ismert. Vegyük észre, hogy – bár eddig is monomokról beszéltünk – még sehol sem használtuk fel, hogy polinomokkal dolgozunk: nyilván definiálhattuk volna mindent természetes számokból álló n hosszú vektorok rendezésére is. Dickson lemmája eredetileg ilyenekről szólt (és egyébként Leonard Dickson 1913-as [11] cikke előtt is ismert volt). Érdemes megpróbálkozni az elemi bizonyítással – utána bizonyára jobban fogjuk tudni értékelni az alább leírtat, amely Hilbert bázis tételét használja, tehát most kihasználjuk, hogy monomok rendezéséről beszélünk. 7

2.5. Tétel. Tetszőleges ≺ tagsorrend a monomok közötti oszthatóság finomítása (azaz ha xw | xu , akkor xw ¹ xu ) és jólrendezés. Bizonyítás: Az első állítás igazolásához tegyük fel, hogy xw | xu . Ekkor u xu is monom, tehát teljesül 1 ¹ xxw . Ha beszorzunk xw -vel, éppen a kívánt xw egyenlőtlenséget kapjuk. Tegyük fel indirekt, hogy ≺ nem jólrendezés, azaz létezik végtelen hosszú leszálló lánc xw1 ≻ xw2 ≻ xw3 ≻ · · · ≻ xwi ≻ xwi+1 ≻ . . . Tekintsük az hxw1 i ⊆ hxw1 , xw2 i ⊆ hxw1 , xw2 , xw3 i ⊆ . . . felszálló ideálláncot. Mivel F [x] Noether-gyűrű, ez nem lehet végtelen, tehát speciálisan van olyan i, amelyre xwi+1 ∈ hxw1 , . . . , xwi i. Ha h ∈ F [x] tetszőleges polinom, akkor minden xw h(x)-ben szereplő monom nagyobb vagy egyenlő, mint xw . Emiatt igaz az is, hogy tetszőleges h1 , . . . , hi ∈ i P hj (x)xwj polinomban szereplő monom nagyobb vagy F [x]-re minden a j=1

egyenlő, mint az xw1 , . . . , xwi monomok közül a legkisebb. Más szóval, az hxw1 , . . . , xwi i ideál tetszőleges elemének legkisebb monomja is nagyobb vagy egyenlő, mint xwi . Arra jutottunk tehát, hogy xwi ¹ xwi+1 , ami ellentmond indirekt feltevésünknek.

2.3. Standard monomok és főtagok Rögzítsünk egy ≺ tagsorrendet. 2.6. Definíció. Egy f (x) ∈ F [x], f 6= 0 polinom főtagja avagy vezető tagja (a ≺ tagsorrendre nézve) a benne szereplő monomok közül a legnagyobb. Az angol leading monomial elnevezés rövidítéseként f főtagját lm (f )-fel jelöljük, főegyütthatónak pedig lm (f ) együtthatóját hívjuk. 2.7. Definíció. Legyen I E F [x] egy ideál. Ekkor I főtagjainak Lm (I) halmaza az I-ben szereplő nemnulla polinomok főtagjaiból áll, azaz Lm (I) = {lm (f ) : f ∈ I, f 6= 0} . Látható, hogy Lm (I) az oszthatóságra nézve felszálló halmaz, azaz xw ∈ Lm (I) és xw | xu esetén xu ∈ Lm (I), hiszen amennyiben xw = lm (f (x)) és ¡ ¢ u u f (x) ∈ I, úgy xu = lm xxw f (x) és xxw f (x) ∈ I 8

Az I ideál standard monomjai azon monomok, amelyek semelyik f ∈ I polinomnak sem vezető tagjai, azaz Sm (I) = {xw ∈ F [x]} \ Lm (I) = {xw : 6 ∃f ∈ I, amelyre lm (f ) = xw } . Miután felszálló halmaz komplementere, ezért Sm (I) leszálló az oszthatóságra nézve. Néha fogjuk használni ideálok helyett tetszőleges F ⊆ F [x] polinomhalmazra is az Sm (F ) és Lm (F ) jelöléseket. 2.8. Definíció. Lm (F ) = {xw : ∃ f ∈ F lm (f ) | xw } , Sm (F ) = {xw ∈ F [x]} \ Lm (F ) Amennyiben F ideál, akkor az újonnan definiált Lm (F ) (és Sm (F )) megegyezik az ideálokra definiált korábbi fogalommal. Pusztán azért nem az általánosabban működő utóbbi definíciót mondtuk ki ideálokra, mert az elsőt valamivel szemléletesebbnek tartjuk. Ezek után pedig gondolhatunk Lm (F )-re úgy is, mint az F -ben szereplő polinomok főtagjainak halmazának (az oszthatóságra nézve) felszállóvá tétele. Fontos megjegyezni, hogy általában Lm (F ) 6= Lm (hF i). Hamarosan látni fogjuk, hogy ez épp a Gröbner-bázisokat karakterizáló egyik tulajdonság. 2.4. Feladat. Mutassuk meg, hogy lm (g · h) = lm (g) · lm (h). 2.5. Feladat. Igazoljuk, hogy I ⊆ J ideálokra Sm (I) ⊇ Sm (J).

2.4. A Gröbner-bázis 2.9. Definíció. Az I ideál Gröbner-bázisának olyan véges G ⊆ I halmazt nevezünk, amelyre teljesül, hogy minden f ∈ I, f 6= 0 polinomhoz létezik g ∈ G, amelyre lm (g) osztója lm (f )-nek. Másképpen megfogalmazva, G ⊆ I véges halmaz I Gröbner-bázisa, ha Lm (I) = Lm (G). Fontos megjegyezni, hogy miután egy polinom vezető tagja függ a választott tagsorrendtől, ezért általában a Gröbner-bázis sem független tőle. 2.10. Példa. Tegyük fel, hogy az F alaptest nem 2 karakterisztikájú. Az I = hx1 − x2 , x1 + x2 i ideálnak egy Gröbner-bázisa G = {x1 , x2 } (tetszőleges tagsorrendre nézve). Egyrészt könnyű látni, hogy G ⊆ I (itt kell, hogy nem 2 a karakterisztika). Másrészt ha egy f polinom vezető tagját nem osztja G semelyik elemének vezető tagja (azaz sem x1 , sem x2 ), akkor lm (f ) = 1, 9

tehát f konstans c 6= 0. Azt kell csak látni, hogy c 6∈ I. Ez például azért igaz, mert az x1 = 0, x2 = 0 behelyettesítéskor a fenti két generátorelem 0-t ad, tehát I minden elemére igaz kell legyen ugyanez. Viszont a G′ = {x1 − x2 , x1 + x2 } halmaz nem Gröbner-bázis, hiszen x2 ∈ I, de x2 -t nem osztja semelyik G′ -beli polinom főtagja. 2.6. Feladat. Lássuk be, hogy ha I főideál, akkor {g} pontosan akkor Gröbner-bázisa, ha hgi = I. Gröbner-bázis létezése A definícióban megköveteltük, hogy G véges halmaz legyen, ezért nem teljesen világos, hogy létezik-e tetszőleges ideálnak Gröbner-bázisa. Belátjuk, hogy a válasz szerencsére igen. 2.11. Definíció. Egy ideált monomiális ideál nak nevezünk, ha van monomokból álló generátorrendszere. 2.12. Lemma. Ha I monomiális ideál, és H ennek monomokból álló generátorrendszere, valamint f ∈ I, akkor f minden monomja osztható valamely H-beli monommal, tehát f minden monomja is I-ben van. Minden monomiális ideálnak van monomokból álló véges generátorrendszere. Bizonyítás: Legyen I monomiális és f ∈ I. Ekkor a feltétel szerint léteznek xw1 , . . . , xwm ∈ H monomok és h1 , . . . hm ∈ F [x] polinomok, amelyekre f (x) =

m X

hi (x)xwi .

i=1

A jobb oldal minden monomja osztható valamely xwi -vel, azaz f minden monomjára ugyanez igaz. Tekintsük I-nek egy véges f1 , . . . , fm generátorrendszerét. A lemma első része szerint az ezekben szereplő véges sok monom mind I-ben van. Nyilvánvalóan ezek generálják is I-t, tehát a második állítás is igaz. 2.13. Állítás. Tetszőleges I ideál esetén Lm (I)-nek van olyan véges H részhalmaza, amelyre igaz, hogy tetszőleges xw ∈ Lm (I)-t osztja valamely H-beli monom. (Utóbbi tulajdonságot Lm (H) = Lm (I)-nek rövidíthetjük.) Bizonyítás: Tekintsük az In (I) := hLm (I)i monomiális ideál egy monomokból álló véges H generátorrendszerét, amely a 2.12 lemma szerint létezik. Minden In (I)-ben levő monom szerepel Lm (I)-ben is, ugyanis ha 10

xw ∈ In (I), akkor a 2.12 lemma alapján valamely Lm (I)-beli monom osztja xw -t, így – kihasználva, hogy Lm (I) az oszthatóságra nézve felszálló – xw ∈ Lm (I) is teljesül. Speciálisan tehát H ⊆ Lm (I). Másrészt, ha xw ∈ Lm (I), akkor xw ∈ In (I), így megint csak a 2.12 lemma alapján valamely H-beli monom osztja őt. Ezek szerint H megfelel a követelményeknek. Az előbb definiált In (I) ideált kezdő vagy kezdeti ideál nak szokás hívni, jelölése az angol initial ideal elnevezésből ered. Vegyük észre, hogy a 2.13 állítás éppen azt mondja ki, hogy minden ideálnak létezik Gröbner-bázisa, hiszen az ott szereplő H halmaz minden xw eleméhez van g ∈ I, amelyre lm (g) = xw , és ezen g polinomok G halmaza I egy Gröbner-bázisa, miután Lm (G) = Lm (H) = Lm (I). Redukció A definícióból nem látszik közvetlenül a Gröbner-bázisok legfontosabb tulajdonsága, amelyet az alábbiakban fogunk vizsgálni, és amely szerint a Gröbner-bázis egy nagyon jó adottságokkal rendelkező generátorrendszere az ideálnak. Legyen f, g ∈ F [x], tegyük fel, hogy f egy xw monomja osztható lm (g)vel, xw együtthatója f -ben cf , g főegyütthatója pedig cg . Legyen c f · xw fˆ(x) = f (x) − g(x). cg · lm (g)

(1)

Vegyük észre, hogy fˆ-ban xw helyébe nála szigorúan kisebb monomok kerülxw tek, hiszen lm(g) g(x) főtagja xw éppen kiesik. Ezt a műveletet redukciónak hívjuk. 2.14. Definíció. Ha G polinomok egy véges halmaza és f (x) ∈ F [x], akkor azt mondjuk, hogy f redukált G-re nézve, amennyiben f semelyik monomját sem osztja semelyik g ∈ G vezető tagja.

Legyen most f tetszőleges, és redukáljuk (1) szerint G elemeivel, amíg G-re nézve redukált polinomot nem kapunk, úgy hogy mindig a szereplő legnagyobb monomot helyettesítjük kisebbekkel. Ez az eljárás véges sok lépésben véget ér, hiszen minden egyes redukcióval kisebb lesz a legnagyobb G-vel redukálható monom. Az is világos, hogy az eljárás során megkapjuk f -nek egy m X f (x) = gi (x)hi (x) + fˆ(x) (2) i=1

előállítását, ahol G = {g1 , . . . , gm }, h1 , . . . , hm ∈ F [x], fˆ redukált polinom G-re nézve, és teljesül lm (gi hi ) ¹ lm (f ). 11

2.15. Definíció. Azt mondjuk, hogy fˆ az f (egy) redukáltja G-re nézve, (vagy f (egy) G szerinti redukáltja,) amennyiben létezik (2) előállítás a fenti tulajdonságú h1 , . . . , hm polinomokkal. Hangsúlyozzuk, hogy a definícióban nem követeljük meg, hogy fˆ redukciós lépésekkel legyen megkapható f -ből. 2.16. Példa. Legyen g1 (x1 , x2 ) = x1 x2 + x1 , g2 (x1 , x2 ) = x1 x2 + x2 , G = {g1 , g2 } és f (x1 , x2 ) = 2x1 x2 + x1 + x2 . Ha f -et először g1 -gyel redukáljuk, akkor x2 − x1 -et kapunk, ha g2 -vel, akkor x1 − x2 -t. Világos, hogy mindkettő f redukáltja G-re nézve. Ráadásul f = g1 + g2 , ezért a redukált definíciója alapján a 0 polinom is f redukáltja, annak ellenére, hogy (1) szerinti redukciós lépésekkel nem kapható meg. Látni fogjuk azonban, hogy ennek az az oka, hogy G nem Gröbner-bázisa a hGi ideálnak. Hamarosan igazoljuk, hogy Gröbner-bázis szerint minden polinom redukáltja egyértelmű, és így meg is kapható a fenti redukciós lépésekkel. Az alábbi tétel az első fontos állításunk, amit a Gröbner-bázis fogalma segítségével tudunk bizonyítani. 2.17. Tétel. Ha I egy ideál F [x]-ben, akkor az F feletti F [x] /I vektortérnek lineáris bázisát adják Sm (I) elemeinek I szerinti ekvivalenciaosztályai. Bizonyítás: Sm (I) ekvivalenciaosztályai lineárisan függetlenek az F [x] /I faktorban, ugyanis amennyiben m X

ai (xwi + I) = 0

i=1

egy nemtriviális lineáris összefüggés, akkor f (x) :=

m X i=1

ai xwi ∈ I,

amiből lm (f ) ∈ Lm (I) következik, ellentmondva annak, hogy csupa standard monomot tekintettünk. Legyen G az I tetszőleges Gröbner-bázisa, f ∈ F [x] és fˆ az f egy G szerinti redukáltja. Ekkor fˆ és f azonos I szerinti mellékosztályban van, hiszen m P gi (x)hi (x) ∈ I. Másrészt fˆ redukált G-re nézve, ezért monomjai nem lei=1

hetnek Lm (I)-ben, tehát fˆ standard monomok lineáris kombinációja. Ezek szerint f is előáll modulo I, mint Sm (I) elemeinek lineáris kombinációja.

12

2.18. Következmény. Ha G az I ideál Gröbner-bázisa, akkor tetszőleges f ∈ F [x] polinom G szerinti redukáltja egyértelmű, és f ∈ I pontosan akkor, ha a redukált 0. Speciálisan hGi = I teljesül. Bizonyítás: Ha fˆ1 és fˆ2 is f redukáltja G-vel, akkor fˆ1 − fˆ2 ∈ I, ugyanakkor fˆ1 −fˆ2 standard monomok lineáris kombinációja, tehát fˆ1 −fˆ2 = 0. A második állítás következik, hiszen f ∈ I esetén f és 0 modulo I azonos, redukáltjuk ezért megegyezik. Ugyanakkor a 0 polinom már redukált, tehát f redukáltja 0. A most igazolt következmény adja a Gröbner-bázisok erejét. A redukált számolásához ezek szerint használhatunk (1) szerinti redukciós lépéseket, tetszőleges sorrendben véve G elemeit: ugyanazt fogjuk kapni. Egyszerű lépésekkel eldönthető például, hogy egy polinom redukáltja nulla-e, tehát hogy benne van-e az ideálban. A 2.18 következmény alábbi megfordításai is igazak (bár a gyakorlatban nem igazán használhatóak annak tesztelésére, hogy G Gröbner-bázis). 2.19. Állítás. Ha G ⊆ I véges, és minden f ∈ I polinom G-vel redukálható 0-ra, akkor G Gröbner-bázis. Ha G ⊆ I véges, hGi = I és minden f ∈ F [x] polinom G szerinti redukáltja egyértelmű, akkor G Gröbner-bázis. Bizonyítás: Az első állítás világos, hiszen ha 0-ra redukálható egy f ∈ m P gi hi , ahol G = {g1 , . . . , gm }, hi ∈ F [x] és minden iI, akkor f = i=1

re lm (gi hi ) ¹ lm (f ). Ráadásul valamely i-re biztosan teljesül lm (f ) = lm (gi hi ) = lm (gi ) lm (hi ), így ez az lm (gi ) osztja lm (f )-et. A második állítás bizonyításához először azt látjuk be, hogy tetszőleges f, h ∈ F [x] és g ∈ G polinomok esetén f és f − gh redukáltja (ami a feltétel szerint egyértelmű) megegyezik. Ha lm (f − gh) ¹ lm (f ), akkor legyen f −gh redukáltja fˆ és a redukciót leíró egyenlet f − gh =

m X

gi hi + fˆ,

i=1

ahol természetesen lm (gi hi ) ¹ lm (f − gh). Ekkor f is redukálható fˆ-re, ugyanis m X f= gi hi + gh + fˆ i=1

redukció megfelelő: annyit kell csak észrevennünk, hogy lm (gi hi ) ¹ lm (f ) és lm (gh) ¹ lm (f ). Ha pedig lm (f ) ¹ lm (f − gh) a helyzet, akkor legyen 13

f ′ = f − gh, h′ = −h, és így f = f ′ − gh′ , tehát lm (f ′ − gh′ ) ¹ lm (f ′ ), ezért az előbbiek szerint f ′ = f − gh és f ′ − gh′ = f redukáltja ugyanaz. Most már egyszerűen következik, hogy G Gröbner-bázis, ugyanis elegendő annyitPbelátni, hogy f ∈ I esetén f redukáható G-vel 0-ra. De hGi = I miatt ghg , tehát a fenti lépést többször alkalmazva arra jutunk, hogy f f = g∈G

redukáltja azonos 0 redukáltjával, azaz 0-val. Ideje, hogy összefoglaljuk a Gröbner-bázis eddig tanult ekvivalens definícióit.

2.20. Tétel. Egy I E F [x] ideál véges G részhalmazára az alábbiak ekvivalensek. 1. Minden f ∈ I \ {0}-ra létezik g ∈ G, hogy lm (g) | lm (f ). 2. Lm (G) = Lm (I) 3. Minden f ∈ I redukálható 0-ra G-vel. 4. hGi = I és minden f redukáltja G-vel egyértelmű. Ilyenkor G az I egy Gröbner-bázisa. A redukált Gröbner-bázis Egy I ideál Gröbner-bázisa természetesen nem egyértelmű, például egy G Gröbner-bázishoz hozzávéve I véges sok elemét, a kapott halmaz is Gröbnerbázisa I-nek. Bizonyos kézenfekvő további tulajdonságot is megkövetelve viszont már egyértelmű lesz. 2.21. Definíció. Ha az I ideál G Gröbner-bázisára teljesül, hogy minden g ∈ G redukált G \ {g}-re nézve és főegyütthatója 1, akkor G az I redukált Gröbner-bázisa. Más szóval G Gröbner-bázis pontosan akkor redukált, ha minden g ∈ G-ben lm (g)-től eltekintve csupa Sm (G)-beli monom szerepel és g főegyütthatója 1. 2.22. Tétel. Tetszőleges I ideálhoz egy rögzített tagsorrend mellett létezik redukált Gröbner-bázis és az egyértelmű. Bizonyítás: A létezés igazolásához legyen G tetszőleges Gröbner-bázisa Inek, amelyben minden főegyüttható 1, és módosítsuk az alábbiak szerint. Dobjuk el (valamilyen sorrendben haladva) azokat a g ∈ G polinomokat, amelyek vezető tagjait osztja valamely másik, még el nem dobott G-beli polinom főtagja. Az így kapott G1 polinomhalmaz nyilván továbbra is Gröbnerbázis, hiszen Lm (I) minden – az oszthatóságra nézve – minimális xw eleméhez pontosan egy g ∈ G-t tartottunk meg, aminek főtagja xw . 14

Ha g ∈ G1 , akkor legyen gˆ a g − lm (g) polinom G1 szerinti redukáltja és G2 := {lm (g) + gˆ : g ∈ G1 } . Ekkor G2 szintén Gröbner-bázis, hiszen pontosan ugyanazok G1 és G2 elemeinek főtagjai, továbbá lm (g) + gˆ és g modulo I azonos, azaz lm (g) + gˆ ∈ I. Az is világos, hogy G2 redukált. Az egyértelműség bizonyításához tegyük fel, hogy G és H is redukált Gröbner-bázis. Mivel a főtagok speciálisan egymást sem oszthatják redukált Gröbner-bázisban, ezért G és H vezető tagjai is éppen Lm (I) minimális elemei, így |G| = |H|. Legyen g ∈ G és h ∈ H, amelyre lm (g) = lm (h). Ekkor g − h standard monomokból áll, ugyanakkor g − h ∈ I, ezért csak g − h = 0, lehet. Ezek szerint G = H.

A redukált Gröbner-bázis elemeinek főtagjait Lm (I) minimális generátorainak hívjuk, hiszen – amint az előbbi bizonyításban is láttuk – ezek éppen az oszthatóságra nézve minimális I-beli vezető tagok.

2.5. Eltűnő ideálok Ebben az alfejezetben olyan ideálokkal fogunk foglalkozni, amelyek egyrészt központi szerepet játszanak az alkalmazásokban, másrészt egyszerűbb meghatározni Gröbner-bázisaikat. Ha f (x1 , . . . , xn ) ∈ F [x] egy polinom, és y ∈ Fn az F feletti n dimenziós affin tér egy pontja, akkor behelyettesíthetjük f változói helyére y-t, azaz f tekinthető egy Fn → F függvénynek. 2.23. Definíció. Legyen V ⊆ Fn és jelölje I(V ) a V -n eltűnő polinomok halmazát, azaz I(V ) := {f (x) ∈ F [x] : f (y) = 0 minden y ∈ V -re} . Azt mondjuk, hogy I(V ) a V halmaz eltűnő ideálja. Világos, hogy I(V ) ideál F [x]-ben. Az F feletti F [x] /I(V ) vektortér a V -n értelmezett polinomfüggvények tere. Az elnevezés jogos, hiszen f1 és f2 polinomok pontosan akkor egyeznek meg függvényként a V halmazon, ha f1 − f2 a teljes V -n eltűnik, azaz ha f1 és f2 modulo I(V ) azonos. Tegyük fel, hogy V véges. Ekkor F [x] /I(V ) izomorf a V → F függvények vektorterével, ugyanis tetszőleges V → F függvény reprezentálható polinommal. Ez a Lagrange-interpolációval egyszerűen látható: elég annyit megmutatni, hogy minden y ∈ V pontra y karakterisztikus függvénye χy 15

(amely y-ban 1, mindenütt másutt V -n pedig 0) reprezentálható polinommal, hiszen tetszőleges függvény előáll χy alakú függvények lineáris kombinációjaként. Jelölje F ⊆ F azon testelemek halmazát, amelyek előfordulnak V valamely pontjának valamely koordinátájában. Ha y ∈ F , akkor legyen χy (x) =

Y

z∈F \{y}

és y ∈ V esetén pedig χy (x) :=

n Q

x−z , y−z

χyi (xi ).

i=1

2.24. Következmény. Ha valamelyik oldal véges, akkor |Sm (I(V ))| = |V | . Bizonyítás: A V → F függvények vektortere |V | dimenziós, F [x] /I(V ) faktortér pedig a 2.17 tétel szerint éppen |Sm (I(V ))| dimenziós. Fent láttuk, hogy ha V véges, akkor ez a két vektortér izomorf. Annyit kell tehát még látnunk, hogy ha V végtelen, akkor Sm (I(V )) is az. Ez azért igaz, mert ha V végtelen, akkor az előbb látott interpolációs módszerrel készítsünk fi polinomot minden i pozitív egészre, amely V első i − 1 pontján eltűnik, az i. pontján pedig 1-et vesz fel. Világos, hogy ez végtelen sok lineárisan független polinomfüggvény, tehát F [x] /I(V ) dimenziója végtelen. Végül bebizonyítunk egy lemmát, amely jól használható annak bizonyítására, hogy egy G = {g1 , . . . , gm } polinomhalmaz Gröbner-bázis. 2.25. Lemma. Legyen I ideál, G ⊆ I és tegyük fel, hogy Sm (I) véges. Ekkor teljesül, hogy G pontosan akkor Gröbner-bázisa I-nek, ha |Sm (I)| = |Sm (G)|. Bizonyítás: A definícióból nyilvánvaló, hogy Sm (I) ⊆ Sm (G) mindig teljesül. A végességi feltétel miatt az elemszámok egyenlősége tehát ekvivalens a halmazok egyenlőségével. Az Sm (I) = Sm (G) egyenlőség mindkét oldalának komplementerét véve, kapjuk, hogy Lm (I) = Lm (G), tehát G Gröbner-bázis. Ezt a lemmát leginkább véges V halmazon eltűnő polinomok I(V ) ideáljára kényelmes alkalmazni. Vegyük észre ugyanis, hogy ilyenkor |Sm (I(V ))| = |V |, ezért a 2.25 lemma feltétele könnyen ellenőrizhető. 2.26. Következmény. Ha V véges, G ⊆ I(V ), akkor G pontosan akkor I(V ) Gröbner-bázisa, ha |V | = |Sm (G)|. 16

3. Algoritmusok Két Gröbner-bázist számoló algoritmust mutatunk be ebben a fejezetben. Az első Buchberger 1965-ös [5] dolgozatában már szerepelt, amely azon kívül, hogy általános módszert ad egy ideál egy Gröbner-bázisának meghatározására, a redukcióról is sok mindent elárul. A második, a Buchberger–Möller-algoritmus csak speciális ideálokra működik: véges V pontrendszerekhez tartozó I(V ) ideálok redukált Gröbnerbázisainak meghatározására szolgál. Sok alkalmazáshoz viszont ez éppen elég. Az irodalomban számtalan egyéb algoritmust – amelyek közül sok az itt tárgyalt általánosítása, vagy valamilyen javítása – lehet találni, közöttük olyanokat, amelyek általánosabban nulla dimenziós ideálokra (a definíciót lásd a 4.2 alfejezetben) működnek. A Buchberger–Möller-algoritmust egyszerűsége és ugyanakkor gyors futásideje miatt választottuk ki bemutatásra. Az általános algoritmussal szemben ez is a fő előnye: a Buchberger-algoritmus futásidejéről nehéz bármi pontosat állítani, azon túl, hogy véges sok lépésben véget ér.

3.1. Buchberger algoritmusa Az algoritmus ismertetéséhez szükségünk lesz néhány új fogalomra, a helyesség bizonyításához pedig a Gröbner-bázisok egy ekvivalens definíciójára. 3.1. Definíció. Legyenek f és g nemnulla polinomok, és legyen f és g főtagjának legkisebb közös többszöröse xw , azaz wi = max{(lm (f )-ben xi kitevője), (lm (g)-ben xi kitevője)}. Legyen f főegyütthatója cf , g polinomé pedig cg . Ekkor f és g S-polinomja xw xw f (x) − g(x). cf lm (f ) cg lm (g) ³ w ´ ³ w ´ Könnyű látni, hogy lm cf xlm(f ) f (x) = xw = lm cg xlm(g) g(x) , ugyanakkor xw kiesik S(f, g)-ből, így lm (S(f, g)) ≺ xw . Előfordulhat emiatt, hogy S(f, g) nem redukálható f -fel vagy g-vel. Az alfejezet fő tételében belátjuk, hogy egy véges G polinomhalmaz pontosan akkor Gröbner-bázis (az általa generált ideálban), ha tetszőleges két eleme S-polinomjának G szerinti redukáltja 0. Szükségünk lesz a következő lemmára. S(f, g) =

17

3.2. Lemma. Legyenek f1 , . . . , fs közös xw főtagú és 1 főegyütthatójú polinos P ci fi valamilyen ci ∈ F együtthatókkal. mok. Tegyük fel továbbá, hogy f = i=1

Ha lm (f ) ≺ xw , akkor f előáll,

s−1 P i=1

c∗i S(fi , fi+1 ) alakban, ahol c∗i ∈ F.

Bizonyítás: Miután xw együtthatója f (x)-ben 0, ezért

s P

ci = 0. Felhasz-

i=1

nálva S(fi , fi+1 ) = fi − fi+1 egyenlőséget is, látható, hogy ! ! s−1 ÃÃ i s s−1 X X X X f= cj (fi − fi+1 ) = ci fi = c∗i S(fi , fi+1 ). i=1

j=1

i=1

i=1

3.3. Tétel. Legyen G = {g1 , . . . , gm } nemnulla polinomok halmaza. G pontosan akkor Gröbner-bázisa a hGi ideálnak, ha minden gi , gj ∈ G esetén S(gi , gj )-nek G-vel vett redukáltja 0. Bizonyítás: Ha G Gröbner-bázis, akkor a 2.18 következmény szerint minden f ∈ hGi redukáltja 0. Nyilván S(gi , gj ) ∈ hGi, tehát a feltétel szükséges. Tegyük most fel, hogy minden gi , gj ∈ G-re az S(gi , gj ) polinom 0-ra redukálható G-vel. Az általánosság megszorítása nélkül feltehető, hogy minden gi főegyütthatója 1. A 2.19 állítás első része szerint elegendő megmutatni, hogy minden f ∈ hGi redukálható 0-ra. Indirekt tegyük fel, hogy f ellenpélda. Tekintsünk egy olyan m X f= gi hi (3) i=1

előállítást, amelyben xw := max lm (gi hi ) minimális. Ilyen létezik, hiszen i=1...m

f ∈ hGi miatt van megfelelő előállítás, továbbá minden tagsorrend jólrendezés (így a minimum létezik). Nyilván lm (f ) ¹ xw , ráadásul egyenlőség sem állhat fenn, különben a 2.15. definíció értelmében (3) azt mutatná, hogy f redukálható 0-ra. Megkonstruáljuk f -nek egy (3)-hoz hasonló előállítását, amelyben azonban a szereplő monomok mind xw -nél kisebbek lesznek, ellentmondva xw minimalitásának. Jelölje L azon i indexek nemüres halmazát, amelyre xw = lm (gi hi ). Leválasztva azokat a tagokat, ahol xw szerepel, kapjuk, hogy f (x) =

m X

gi (x)h∗i (x) +

i=1

X i∈L

18

ci gi (x)xwi ,

P ci = 0 teljesül, hiahol lm (gi h∗i ) ≺ xw és lm (gi (x)xwi ) = xw . Ekkor i∈L P ci gi (x)xwi . Ha g előállítható szen ez xw együtthatója. Legyen g(x) = i∈L

a gi polinomok F [x]-lineáris kombinációjával úgy, hogy minden előforduló monom kisebb xw -nél, akkor megkapjuk f -nek is egy hasonló tulajdonságú előállítását, ami ellentmondás. Ez lesz P tehát mostantól a célunk. ci gi (x)xwi -re, így kapjuk, hogy A 3.2 lemma alkalmazható g(x) = i∈L

g(x) =

X

c∗i,j S (gi (x)xwi , gj (x)xwj ) .

i,j∈L

Számoljuk most ki a szereplő S-polinomokat. Legyen lm (gi ) és lm (gj ) legkisebb közös többszöröse xuij . Világos, hogy xuij | xw . Ekkor S(gi (x)xwi , gj (x)xwj ) = xwi gi −xwj gj =

xw xw xw gi − gj = uij S(gi , gj ). lm (gi ) lm (gj ) x

Miután a feltétel szerint S(gi , gj ) 0-ra redukálódik, ezért létezik S(gi , gj ) =

m X

hijℓ gℓ

ℓ=1

előállítás, ahol minden ℓ-re lm (hijℓ gℓ ) ¹ lm (S(gi , gj )). Az előzőekkel összevetve kapjuk, hogy à ! m m w w X X X X x x gℓ (x) c∗i,j hijℓ uij . hijℓ gℓ (x) = g(x) = c∗i,j uij x x i,j∈L i,j∈L ℓ=1 ℓ=1 Itt lm (hijℓ gℓ ) ¹ lm (S(gi , gj )) ≺ xuij , ezért à ! w X x lm gℓ (x) c∗i,j hijℓ uij ≺ xw , x i,j∈L és éppen ilyen tulajdonságú előállítást kerestünk. Buchberger algoritmusa ezek után igen egyszerű. 3.4. Algoritmus (Buchberger). Legyen I ideál F [x]-ben és F ⊆ I egy tetszőleges véges generátorrendszere. A következő eljárás véges lépésben véget ér, a végén F az I ideál egy Gröbner-bázisa lesz. While ∃f1 , f2 ∈ F , amelyeket együtt még nem vizsgáltunk do r := (S(f1 , f2 ) redukáltja F -fel); If r 6= 0 then F := F ∪ {r}; endif; endwhile; 19

Bizonyítás: A helyesség bizonyítása a 3.3 tétel alapján egyszerű. Tudjuk, hogy hF i = I az elején, a továbbiakban hozzávett polinomok pedig I-beli polinomok S-polinomjainak néhány I-beli polinommal vett redukáltjai, ezért maguk is I-ben vannak. Tehát a végén kapott F -re is hF i = I. A konstrukció alapján világos, hogy F bármely két polinomjának S-polinomja F -fel 0-ra redukálható (hiszen ahol ez nem volt igaz, ott hozzávettük a redukáltat, amit felhasználva viszont már nyilván 0-ra redukálódik). A 3.3 tétel szerint tehát I egy Gröbner-bázisát kapjuk így. Végül megmutatjuk, hogy az eljárás véges sok lépésben véget ér. Tegyük fel indirekt az ellenkezőjét. Legyen F1 = F és Fi+1 = Fi ∪ {ri } az F halmaz (i + 1)-edik állapota, speciálisan ri redukált Fi -re. Megkaptuk tehát I generátorrendszereinek egy F1 ( F2 ( . . . végtelen sorozatát. Teljesül Lm (Fi ) ( Lm (Fi+1 ) is, hiszen lm (ri ) ∈ Lm (Fi+1 ) \ Lm (Fi ). Legyen In (Fi ) = hLm (Fi )i. Ekkor lm (ri ) ∈ In (Fi+1 ) \ In (Fi ) szintén igaz, ugyanis In (Fi ) monomiális ideál, tehát a 2.12 lemma miatt ha lm (ri ) ∈ In (Fi ) lenne, akkor lm (ri ) ∈ Lm (Fi ) is fennállna. Így viszont In (F1 ) ( In (F2 ) ( . . . ideálok végtelen növő lánca, ami F [x]-ben nem létezik. Látjuk tehát, hogy a Buchberger-algoritmus F [x] tetszőleges véges generátorrendszerrel megadott ideáljához véges sok lépésben előállít egy Gröbnerbázist. Természetesen ez általában nem lesz redukált, sőt tipikusan a szükségesnél sokkal több elemet tartalmaz. Emiatt az algoritmus lépésszámára nem igazán mondható használható felső becslés. Ugyanakkor a módszeren lehet gyorsítani néhány egyszerű és néhány bonyolultabb trükkel. Sok múlik például azon, hogy F elemeit milyen sorrendben tekintjük. Az érdeklődő Olvasó találhat javításokat [2] 3.3. alfejezetében, Giovini, Mora, Niesi, Robbiano és Traverso [18] munkájában. Érdemes megnézni Faugère [12] és [13] cikkeit is. A két leggyorsabban futó algoritmus a kutatások mai állása szerint az utóbbi és Brickenstein [4] eljárása, amely számos trükköt – köztük a „sovány polinomokkal” való számolást – sorakoztat fel. A következő alfejezetben egy véges pontrendszerre működő algoritmust tárgyalunk. Emiatt, míg a Buchberger-algoritmus bemeneteként az ideált egy véges generátorrendszerével adtuk meg, a következő algoritmusnál egy véges V pontrendszerből indulunk ki.

3.2. A Buchberger–Möller-algoritmus Az algoritmus változatai több cikkben megtalálhatóak, az eredeti Buchberger és Möller 1982-ben megjelent [9] munkája. Részletes költségelemzést tartal20

maz és elég általános Marinari, Möller és Mora [22] dolgozata, jó összefoglalót ad Mora és Robbiano [23] és végül a nulla dimenziós esetre általánosítja Abott, Kreuzer és Robbiano [1]. Ugyanezen az alapötleten múlik Faugère, Gianni, Lazard és Mora [14] algoritmusa, amely a számításhoz felteszi, hogy valamely más tagsorrendre már ismert a redukált Gröbner-bázis. A Buchberger–Möller-algoritmus egy V véges pontrendszerhez tartozó ideál redukált Gröbner-bázisát számolja ki. Mielőtt nekikezdenénk az algoritmus ismertetésének, vizsgáljuk meg, hogy hogyan járhatnánk el, ha azt a – látszólag – egyszerűbb feladatot tűznénk ki, hogy V segítségével adjuk meg I(V ) egy tetszőleges generátorrendszerét. Tekintsük a következő, végtelenszer |V |-es A „mátrixot”. Az A sorait monomokkal, oszlopait V elemeivel indexeljük. Az xw és v-hez tartozó elem legyen xw (v) = vw , azaz xw helyettesítési értéke a v helyen. Sorműveletek segítségével az A mátrixot „felső háromszög” alakra lehet hozni, azaz kaphatunk egy   1 * ... *  0 1 ... *      . .   .    0 0 ... 1     0 0 ... 0  ...

alakú A′ mátrixot. A sorműveletek során megőrizhetjük A azon tulajdonságát, hogy minden sor egy-egy polinom V -n felvett helyettesítési értékeiből áll: például ha az f (x)-hez tartozó sorhoz hozzáadjuk a g(x)-hez tartozó sor α skalárszorosát, akkor mostantól az előbbi sor az f (x) + αg(x) polinom helyettesítési értékeiből áll. Ezek szerint a csupa 0 sorok V -n eltűnő polinomokhoz tartoznak. Miután az összes monom lineáris bázisa F [x] vektortérnek, ezért az A′ soraihoz tartozó polinomok halmaza szintén lineáris bázisa F [x]-nek. Ebből viszont következik, hogy a csupa nulla sorokhoz tartozó polinomok lineáris kombinációjával előállítható tetszőleges f ∈ I(V ). Ezek szerint a csupa nulla sorok polinomjai közül kiválasztható I(V ) egy véges generátorrendszere. Ennek az eljárásnak a hatékony megvalósítása a Buchberger–Möller-algoritmus. Végtelen sok sor kinullázása helyett pontosan annyival fogunk foglalkozni, amennyire feltétlenül szükség van. Egyetlen sorral – az 1 monomhoz tartozóval – kezdünk és az algoritmus futása közben határozzuk meg azon monomokat, amelyekhez tartozó sorokat érdemes lesz vizsgálni. (Ezek szerepelnek majd az M halmazban.) Egy új sor (azaz egy xw ∈ M monom) vizsgálatakor megpróbáljuk kinullázni azt a korábbi sorok segítségével. Jelölje p(x) az ezen sorhoz tartozó polinomot 21

(tehát először p(x) = xw , majd a sorműveletek során p(x) változik). Nagyon lényeges, hogy egy új sorhoz a kizárólag a korábbiak skalárszorosát adhatjuk hozzá. Miután az adott tagsorrendre nézve egyre nagyobb monomokkal fogunk foglalkozni, ezzel garantáljuk, hogy a sorműveletek során változatlan xw marad p(x) főtagja. Ha az új sort sikerült kinullázni, akkor a kapott p(x) épp a redukált Gröbner-bázis xw főtagú eleme. Ha nem sikerült, akkor viszont p(x) egy alkalmas skalárszorosa az A′ mátrix egyik nem csupa 0 sorának felel majd meg. Ha eddig i ilyen sorunk volt, akkor a megfelelő polinomot qi+1 (x) jelöli. A V pontrendszer elemeinek a sorrendjének esetleges megváltoztatása árán feltehető, hogy a nemnulla elem a főáltóban van. Képletben tehát: qi+1 (vj ) = 0 (ha j ≤ i) és qi+1 (vi+1 ) = 1 (az előbb említett skalár tehát 1 lesz). Belátjuk majd, hogy ilyenkor teljesül xw ∈ Sm (I(V )) . p(vi+1 ) Lássuk tehát az algoritmus pontos működését. 3.5. Algoritmus (Buchberger–Möller). Legyen V ⊆ Fn véges pontrendszer. A következő eljárás előállítja az I(V ) E F [x] ideál G redukált Gröbner-bázisát (az inputként megadandó) ≺ tagsorrendre. Melléktermékként megkapjuk az I(V ) standard monomjait (az S halmazban), továbbá a fent részletezett tulajdonságú qi polinomokat is. G := ∅; S := ∅; M := {1}; i := 0; While M 6= ∅ do xw := min M ; M := M \ {xw }; If xw 6∈ Lm (G) then p(x) := xw ; For j = 1 to i do p(x) := p(x) − p(uj )qj (x); endfor; If p(x) ∈ I(V ) then G := G ∪ {p(x)}; else legyen vi+1 ∈ V , amire p(vi+1 ) 6= 0; p(x) qi+1 (x) := p(v ; i+1 ) w S := S ∪ {x }; M := M ∪ {xj · xw : j = 1 . . . n}; i := i + 1; endif; endif; endwhile; Bizonyítás: Könnyű látni (i-re vonatkozó indukció), hogy qi+1 eleget tesz a kívánalmaknak, azaz j ≤ i esetén qi+1 (vj ) = 0 és qi+1 (vi+1 ) = 1. Vegyük észre, hogy a For ciklus pontosan a Gauss-elimináció azon lépését valósítja 22

meg, amelyben a p(x) = xw polinomhoz tartozó sort a korábbiakkal megpróbáljuk kinullázni: q1 , . . . , qi segítségével tehát elérjük, hogy p helyettesítési értéke 0 legyen a v1 , . . . , vi pontokon. Ha p(x) 6∈ I(V ), akkor van olyan V -beli vi+1 pont, amire p(vi+1 ) 6= 0. Ekkor qi+1 (x) definíciójára tekintve az állítás világos. Az algoritmus véges sok lépésben leáll, ugyanis ha már i = |V |, akkor minden újabb p(x) polinom eltűnik V -n (a megfelelő sor kinullázható), ezért M -be több elem már nem kerül, tehát előbb-utóbb kiürül. Rátérünk annak igazolására, hogy G redukált Gröbner-bázis, és S = Sm (I(V )). Először is bebizonyítjuk, hogy lm (p) = xw . Vegyük észre, hogy a vizsgált xw monomok egyre nagyobbak. Valóban, amikor xw -t választjuk M -ből, akkor ő a minimális elem, és M -be később már csak olyan monomok kerülhetnek be (tekintsünk az első endif előtti sorra), amelyeknek valamelyik már bent levő monom osztója, tehát olyan, ami xw -nél nagyobb. Nyilvánvaló emiatt az is, hogy amikor xw -t vizsgáljuk, akkor a már készen levő q1 , . . . , qi polinomok csupa kisebb monomból állnak, hiszen csakis vizsgált (ráadásul S-ben levő) monomokat tartalmaznak. Tehát lm (p) = xw . Ezek után igazoljuk, hogy az algoritmus végére minden monom vagy Lm (G)-ben vagy S-ben van. Tegyük fel, hogy xw egy minimális ellenpélda. Az 1 monom az első lépésben bekerül S-be, tehát xw -nek van eggyel kisebb fokú osztója. A minimalitás miatt ez szerepel Lm (G)-ben vagy Sben. Lm (G) felszálló, ezért csak S-ben lehet. Akkor viszont abban a lépésben, amikor bekerült, xw monomot felvettük az M listára. Valamikor tehát vizsgáltuk xw -t, így viszont vagy p polinom főtagjaként bekerül Lm (G)-be, vagy S-hez vesszük hozzá. Az algoritmusra tekintve az is világos, hogy S és Lm (G) diszjunkt, tehát S = Sm (G). Látható, hogy G ⊆ I(V ), ezért az algoritmus végén |S| = |Sm (G)| ≥ |Sm (I(V ))| = |V |. De az algoritmus során mindvégig |S| = i ≤ |V |, tehát az előbbi összefüggésben valójában egyenlőség áll fenn, speciálisan |Sm (G)| = |V |. A 2.26 következmény szerint G tehát Gröbner-bázis és így persze S = Sm (G) = Sm (I(V )) is igaz. Végül következik, hogy G redukált Gröbner-bázis. Mivel a qi polinomok mind S-beli, tehát standard monomok lineáris kombinációi, ezért ugyanez igaz főtagjától eltekintve az összes szereplő p polinomra is. Így speciálisan G elemei vezető tagjuktól eltekintve standard monomokból állnak. Már csak azt kell igazolni, hogy G különböző elemeinek főtagjai nem oszthatják egymást. Ez viszont abból világos, hogy két vezető tag közül a kisebbet előbb vizsgáltuk, ezért amikor a nagyobb xw monomra került a sor, már xw ∈ Lm (G) lett volna, amennyiben a kisebb xw -nek osztója lenne. 23

3.1. Feladat. Igazoljuk, hogy Sm (I({v1 , . . . , vi })) = S az algoritmus során végig igaz. 3.6. Példa. Legyen V = {(1, 2, 3), (2, 2, 3), (0, 3, 2)} ∈ Q3 és tekintsük a deglex rendezést. Végig fogjuk nézni az algoritmus futását. Gyakorlás végett érdemes párhuzamosan az A′ mátrix alakulását is számolni. min M = 1, tehát p(x) := 1. p(x) 6∈ I(V ), mert p(1, 2, 3) = 1 6= 0, így q1 (x) := 1, v1 := (1, 2, 3), S = {1} és M = {x1 , x2 , x3 }. min M = x3 , tehát p(x) := x3 , p(x) := x3 − q1 (x)(x3 (1, 2, 3)) = x3 − 3. p(x) 6∈ I(V ), mert p(0, 3, 2) = −1 6= 0, így 3 −3 q2 (x) := x−1 = −x3 + 3, v2 := (0, 3, 2), S = {1, x3 } és M = {x1 , x2 , x1 x3 , x2 x3 , x23 }. min M = x2 , tehát p(x) := x2 , p(x) := x2 − q1 (x)(x2 (1, 2, 3)) = x2 − 2, p(x) := x2 − 2 − q2 (x)((x2 − 2)(0, 3, 2)) = x2 + x3 − 5. p(x) ∈ I(V ), így g1 (x) := x2 + x3 − 5 és M = {x1 , x1 x3 , x2 x3 , x23 }. min M = x1 , tehát p(x) := x1 , p(x) := x1 − q1 (x)(x1 (1, 2, 3)) = x1 − 1, p(x) := x1 − 1 − q2 (x)((x1 − 1)(0, 3, 2)) = x1 − x3 + 2. p(x) 6∈ I(V ), mert p(2, 2, 3) = 1 6= 0, így q3 (x) := x1 −x1 3 +2 = x1 − x3 + 2, v3 := (2, 2, 3), S = {1, x3 , x1 }, M = {x1 x3 , x2 x3 , x23 , x21 , x1 x2 }. min M = x23 , tehát p(x) := x23 , p(x) := x23 − q1 (x)(x23 (1, 2, 3)) = x23 − 9, p(x) := x23 − 9 − q2 (x)((x23 − 9)(0, 3, 2)) = x23 − 5x3 + 6, p(x) := x23 − 5x3 + 6 − q3 (x)((x23 − 5x3 + 6)(2, 2, 3)) = x23 − 5x3 + 6. p(x) ∈ I(V ), így g2 (x) := x23 − 5x3 + 6 és M = {x1 x3 , x2 x3 , x21 , x1 x2 }. min M = x2 x3 , de lm (g1 ) = x2 | x2 x3 , ezért nem foglalkozunk vele és M = {x1 x3 , x21 , x1 x2 }. min M = x1 x3 , tehát p(x) := x1 x3 , p(x) := x1 x23 − q1 (x)((x1 x3 )(1, 2, 3)) = x1 x3 − 3, p(x) := x1 x3 − 3 − q2 (x)((x1 x3 − 3)(0, 3, 2)) = x1 x3 − 3x3 + 6, p(x) := x1 x3 − 3x3 + 6 − q3 (x)((x1 x3 − 3x3 + 6)(2, 2, 3)) = x1 x3 − 3x1 . p(x) ∈ I(V ), így 24

g3 (x) := x1 x3 − 3x1 és M = {x21 , x1 x2 }. min M = x21 , tehát p(x) := x21 , p(x) := x21 − q1 (x)(x21 (1, 2, 3)) = x21 − 1, p(x) := x21 − 1 − q2 (x)((x21 − 1)(0, 3, 2)) = x21 − x3 + 2, p(x) := xx21 − x3 + 2 − q3 (x)((x21 − x3 + 2)(2, 2, 3)) = x21 + 3x1 − 4x3 + 8. p(x) ∈ I(V ), így g3 (x) := x21 + 3x1 − 4x3 + 8 és M = {x1 x2 }. min M = x1 x2 , de lm (g1 ) = x2 | x1 x2 , ezért nem foglalkozunk vele és M = ∅, azaz végeztünk.

Tehát Sm (I(V )) = {1, x3 , x1 } és G = {x2 + x3 − 5, x23 − 5x3 + 6, x1 x3 − 3x1 , x21 + 3x1 − 4x3 + 8} a redukált Gröbner-bázis. 3.7. Tétel. Tegyük fel, hogy az aritmetikai műveletek F testben a, két n változós monom ≺ szerinti összehasonlítása pedig nb költségűek. Legyen továbbá m = |V |. Ekkor a Buchberger–Möller-algoritmus O (am3 n + bmn2 log(mn)) időben megvalósítható. Például egy kis elemszámú véges testben a lex vagy deglex rendezéssel dolgozva, és valamely ε > 0 számra m1−ε > n-et feltéve a futásidő O(m3 n). Bizonyítás: Először teszünk néhány észrevételt, amelyekre a futásidő csökkentése miatt lesz szükségünk. Először is, M elemeit érdemes valamilyen bináris keresőfában tárolni. Itt ebből annyit használunk, hogy O(log |M |) összehasonlítással tudunk M -ben keresni, ennyi idő alatt megkapjuk M minimális elemét, illetve ugyanekkora költséggel tudunk M -ből törölni és M -be beszúrni elemeket. Ahelyett, hogy valamiféle kereséssel direkt módon próbálnánk eldönteni, hogy xw ∈ Lm (G) fennáll-e, a következőt tesszük. Feljegyezzük M elemei mellé, hogy hány alkalommal szúrtuk be őket. (Ehhez kell, hogy keresni is tudjunk gyorsan M -ben.) Bebizonyítjuk, hogy ha xw az M minimális eleme egy lépésben, akkor pontosan akkor teljesül xw 6∈ Lm (G), ha az xw mellé feljegyzett szám megegyezik az xw -ben nemnulla kitevővel szereplő változók számával. Egy xw pontosan akkor standard monom, vagy Lm (I) minimális generátora, ha minden eggyel kisebb fokú osztója standard monom. Amikor xw -vel foglalkozunk, addigra már az összes osztójával végeztünk (tehát vagy vizsgáltuk már, vagy többé nem is fogjuk). Ha minden eggyel kisebb fokú osztója standard monom, akkor xw -t mindnél beszúrtuk M -be. Tehát a fent javasolt

25

számláló xw -re pontosan akkor egyenlő az xw -ben szereplő változók számával, ha xw ∈ Sm (I(V )) vagy xw monom Lm (I) minimális generátora. Ez viszont ekvivalens azzal, hogy xw 6∈ Lm (G) amikor ezt tesztelnünk kell. Szükségünk van vi w kiszámolására is. Ehhez M elemei mellé még további ′ értékeket is érdemes felírni. Ha xℓ xw = xw és xw -t most első ízben szúrjuk ′ be M -be, akkor írjuk fel mellé a már úgyis kiszámolt vi w értékeket (és persze ℓ-et se feledjük). Így minden egyes vi w kiszámolható egyetlen szorzással, ez összesen tehát i ≤ m aritmetikai művelet. Amikor p polinommal dolgozunk, p ∈ I(V ) eldöntéséhez szükségünk lesz rá, hogy minden pontban kiszámoljuk p helyettesítési értékét. Érdemes emiatt a sokat emlegetett A′ mátrixot ténylegesen tárolni, így a For ciklus után kapott p polinom V -n felvett értékeit néhány sorművelettel megkaphatjuk. Pontosan tehát azt mondhatjuk, hogy p számolásakor az alábbi   1 q1 (v2 ) . . . q1 (vi−1 ) q1 (vi ) . . . q1 (vm ) q1 (x)  0 1 . . . q2 (vi−1 ) q2 (vi ) . . . q2 (vm ) q2 (x)      . . . . . .    0 0 ... 1 qi−1 (vi ) . . . qi−1 (vm ) qi−1 (x)  v1 w v2 w ... vi−1 w vi w ... vm w xw

mátrixot ismerjük. Kihasználva, hogy a qj (x) polinomok csupa standard monomból állnak, így legfeljebb m nemnulla monomot tartalmaznak (sőt qj legfeljebb j-t), látható, hogy p(vj ) (j = 1 . . . m) és p(x) polinom számításához O(m2 ) aritmetikai operáció elegendő. Minden standard monomra összesen n elemet szúrunk be M -be, azaz összesen nm-et. Egy beszúrás költsége log |M | ≤ log(mn)-nel arányos, tehát ebből a részből a költség O(bmn2 log(mn)). Az is következik, hogy összesen legfeljebb mn monomra kellett kiszámolni a megfelelő p polinomot, ennek ára O(m3 n) aritmetikai művelet. A további műveletek nagyságrendje láthatóan kisebb, a teljes futásidő ezért valóban O (am3 n + bmn2 log(mn)). A tipikus használat esetét mutató példában az O(m3 n) költség könnyen ellenőrizhető, hiszen ilyenkor a és b konstans, és O(log(mn)) = O(log(m)) < O(mε ).

26

4. Alkalmazások 4.1. Elemi kommutatív algebrai kérdések Ideál egy elemének megadása generátorokkal Komputer algebra rendszerekben természetesnek vesszük, hogy találunk beépített függvényt annak tesztelésére, hogy egy elem benne van-e egy adott (véges) halmazban. A hasonló kérdés, hogy egy polinomot tartalmaz-e egy ideál, nem ilyen egyszerű, hiszen egy ideál tipikusan végtelen elemszámú. Erre az elemi kérdésre a választ az ideál egy Gröbner-bázisának segítségével lehet megadni. Tegyük fel, hogy I = hf1 , . . . , fs i és f ∈ F [x]. Legyen egy Gröbner bázisa I-nek G = {g1 , . . . , gm }. Számítsuk ki f -nek fˆ redukáltját G-re. Erre, mint láttuk, jó a „mohó” algoritmus: f -ből kiindulva az aktuális polinom legnagyobb monomját redukáljuk, amely még redukálható G valamely elemével. A 2.18 következmény szerint f ∈ I pontosan akkor, ha fˆ = 0.

Jogos igény, hogy f ∈ I esetén adjuk is meg f előállítását a generátorokkal. Először is, a redukció során megkapjuk f egy f=

m X

gi hi .

i=1

alakú előállítását. Elegendő ezért G elemeit kifeljezni az eredeti fj generátorokkal. Egy lehetséges megoldás – amennyiben G-t a Buchberger-algoritmussal számoljuk –, hogy F = {f1 , . . . , fs }-ből kiindulva, amikor F két elemének S-polinomjának redukáltját számoljuk, rögtön {f1 , . . . , fs } polinom-lineáris kombinációjával kifejezzük. Pontosabban, ha az aktuális F = {f1 , . . . , fs′ } halmaz elemeinek a kezdeti generátorokkal való előállítása például fi =

s X

fj hi,j

j=1

(1 ≤ i ≤ s′ ),

akkor az újonnan hozzáveendő fs′ +1 polinomot a következő módon tudjuk kifejezni. Tegyük fel, hogy ebben a lépésben épp fk , fℓ polinomokkal dolgozunk. Ekkor s′ X S(fk , fℓ ) = fi hi + fs′ +1 , i=1

27

összefüggésből kapjuk, hogy s′

fs′ +1

X xw xw = fk − fℓ − fi hi = cfk lm (fk ) cfℓ lm (fj ) i=1

′

s s s X s X X X xw xw fj hk,j − fj hℓ,j − fj hi,j hi = cfk lm (fk ) j=1 cfℓ lm (fℓ ) j=1 i=1 j=1 Ã ! s s′ X X xw xw fj hk,j − hℓ,j − hi,j hi , cfk lm (fk ) cfℓ lm (fℓ ) j=1 i=1

azaz hs′ +1,j =

xw h cfk lm(fk ) k,j

−

xw h cfℓ lm(fℓ ) ℓ,j

−

s′ P

hi,j hi .

i=1

Ideálok egyenlősége ?

Ha I = hF i és J = hHi ideálok, akkor I = J eldöntésére használhatjuk az előző alfejezetben tanultakat: I ⊆ J akkor és csak akkor, ha F minden eleme J-ben van. Egy másik – talán kevesebb számolást igénylő – eljárás, ha meghatározzuk I és J redukált Gröbner-bázisát. Ez, a redukált Gröbner-bázis egyértelműségéről szóló, 2.22 tétel bizonyításában leírtak alapján gyorsan megtehető, tetszőleges Gröbner-bázisból kiindulva. A két ideál pontosan akkor egyenlő, ha a redukált Gröbner-bázisok megegyeznek. ? Fontos speciális eset az I = F [x] kérdés, amit természetesen 1 ∈ I tesztelésével dönthetünk el, ami ekvivalens kérdés azzal, hogy G-ben van-e nem nulla konstans polinom (bármilyen G Gröbner-bázis esetén). Számítások F [x] /I-ben A 2.17 tételben láttuk, hogy Sm (I) elemeinek I szerinti mellékosztályai a faktor lineáris bázisát adják. Másrészt azt is igazoltuk, hogy egy Gröbnerbázis segítségével tetszőleges f ∈ F [x] polinom redukálható fˆ polinommá, amely standard monomok lineáris kombinációja. Másképpen mondva, tetszőleges polinom mellékosztályának egy kanonikus reprezentációja a polinom redukáltja. Redukált polinomok összege nyilván redukált. A szorzásra ugyanez nem mondható el: itt a Gröbner-bázisunkkal még redukálnunk kell az eredményt. Az inverz számítása már érdekesebb feladat. 4.1. Állítás. Egy f polinommal reprezentált F [x] /I-beli elem pontosan akkor invertálható, ha hf, Ii = F [x]. 28

Bizonyítás: Világos, hogy hf, Ii = F [x] akkor és csak akkor teljesül, ha valamely g ∈ I és h ∈ F [x] polinomokra 1 = hf + g. Utóbbi egyenlőséget az F [x] /I faktorban tekintve kapjuk, hogy h épp f inverze modulo I. Ha g1 , . . . , gm egy generátorrendszere I-nek, akkor f, g1 , . . . , gm generátorrendszere az hf, Ii ideálnak. Számoljuk ki az utóbbi egy Gröbner-bázisát úgy, hogy az f, g1 , . . . , gm polinomokból indulunk ki és a számítás közben megjegyezzük az új elemek előállítását f, g1 , . . . , gm polinomokkal. Ha a kapott Gröbner-bázisban nem szerepel 1, akkor az előbbi állítás szerint f mellékosztálya nem invertálható. Ha szerepel, akkor viszont a számítás mentén m P gi hi előállítást, amiből látszik, hogy f modulo megkaptunk egy 1 = f h + i=1

I inverze éppen h.

Ideálok metszetének generátorrendszere 4.2. Állítás. Legyen I, J EF [x] és tekintsük a hzI, (1 − z)JiEF[z, x1 , . . . , xn ] ideált, ahol z egy új változó. Ekkor I ∩ J = hzI, (1 − z)Ji ∩ F [x] . Bizonyítás: Ha f ∈ I ∩ J, akkor f = zf + (1 − z)f miatt f a jobb oldalon is szerepel. Megfordítva, tegyük fel, hogy f (x) a jobb oldali metszet egy eleme. Ha I = hf1 , . . . , fs i és J = hg1 , . . . , gm i, akkor hzI, (1 − z)Ji = hzf1 , . . . , zfs , (1 − z)g1 , . . . , (1 − z)gm i, ezért f (x) =

s X

zfi (x)hi (z, x) +

i=1

m X i=1

(1 − z)gi (x)h′i (z, x).

Innen z = 1 helyettesítéssel adódik f ∈ I és z = 0-val f ∈ J. Legyen F [x] monomjain egy rögzített tagsorrend ≺. Definiáljunk egy ≺′ rendezést F[z, x] monomjain a következő módon. Akkor és csak akkor teljesül z w xw ≺′ z u xu , ha w < u, vagy w = u és xw ≺ xu . Könnyű látni, hogy ≺′ tagsorrend. 4.3. Állítás. Legyen I ′ E F[z, x] ideál egy Gröbner-bázisa G′ a ≺′ tagsorrendre. Ekkor I = I ′ ∩ F [x] ideálnak G := G′ ∩ F [x] Gröbner-bázisa a ≺ rendezésre. Bizonyítás: Legyen f ∈ I. Ekkor f ∈ I ′ is, ezért van olyan g ∈ G′ , amelyre lm (g) | lm (f ). Megmutatjuk, hogy g ∈ G is teljesül, ami bizonyítja, hogy G valóban Gröbner-bázis. Miután f ∈ F [x], ezért speciálisan lm (f )-ben nem szerepel a z változó. Így viszont ugyanez igaz osztójára, lm (g)-re is. Ha z szerepelne g egy másik monomjában, akkor ez a monom ≺′ definíciója szerint 29

nagyobb lenne lm (g)-nél, ami lehetetlen. Tehát z nem szerepel g semelyik monomjában, azaz g ∈ G. A két fenti állítás segítségével meghatározható I, J ideálok metszetének egy generátorrendszere, amely ráadásul a metszet Gröbner-bázisa is egyben. Valóban, ha G′ az hzI, (1 − z)Ji ideál Gröbner-bázisa akkor G′ ∩ F [x] a 4.3 állítás szerint Gröbner bázisa hzI, (1 − z)Ji ∩ F [x] ideálnak, amely a 4.2 állítás alapján pontosan I ∩ J.

4.2. Polinom-egyenletrendszerek megoldása Az előző fejezetben ízelítőt kaptunk a Gröbner-bázisok alkalmazására különböző szimbolikus számítási feladatok elvégzésében. Bár ezek kétségtelenül igen hasznosak, mégis valószínűleg senki sem vitatkozik azzal a kijelentéssel, hogy a Gröbner-bázisok legfontosabb alkalmazási területe a többváltozós polinomiális egyenletek megoldása. Az ilyen jellegű szimbolikus számításoknak jól ismert korlátja, hogy nem létezik képlet, amely megadná például tetszőleges ötödfokú polinom gyökeit. Ez nyilván a többváltozós esetnek is határokat szab, a szimbolikus számítások egy bizonyos pontján elő kell vegyünk numerikus megoldási módszereket. Az alapprobléma tehát a következő. Adott f1 , . . . , fs ∈ F [x] polinom. n Létezik-e olyan y ∈ Fn , esetleg y ∈ F elem (F az F algebrai lezártja), amely kielégíti az f1 (x) = 0 ... fs (x) = 0

(4)

egyenletrendszert? Ha igen, szeretnénk tudni legalább egy, de inkább az összes megoldást. Esetleg megelégszünk a megoldások számának meghatározásával. Ebben az alfejezetben I végig az f1 , . . . , fs polinomok által generált ideált jelöli. Kommutatív algebrai alapok A 2.5 alfejezetben megismerkedtünk az I(V ) jelöléssel. Az I(.) operátor Fn részhalmazaihoz ideálokat rendelt. Most definiáljuk a duális fogalmat, amely polinomiális egyenletrendszerek vizsgálatakor kulcsszerepet játszik. 4.4. Definíció. Jelölje V (I) az I ideál elemeinek közös gyökeinek a halmazát, azaz V (I) := {y ∈ Fn : f (y) = 0 minden f ∈ I-re}. 30

4.5. Lemma. A (I(.), V (.)) pár Galois-kapcsolat, azaz teljesül I ⊆ I(V (I)), V ⊆ V (I(V )), I ⊆ J ⇒ V (I) ⊇ V (J) és V ⊆ U ⇒ I(V ) ⊇ I(U ). Ebből következik, hogy I(V (I(V ))) = I(V ) és V (I(V (I))) = V (I). Bizonyítás: Legyen f ∈ I. Ahhoz, hogy f ∈ I(V (I)) legyen, meg kell mutatni, hogy f eltűnik V (I) tetszőleges y elemén. Csakhogy V (I) definíciója miatt y ∈ V (I)-ből következik f (y) = 0. Teljesen analóg módon megy V ⊆ V (I(V )) bizonyítása is. A második állításpár triviális. Végül egyrészt alkalmazzuk a V ⊆ V (I(V )) összefüggésre az I(.) operátort, így I(V ) ⊇ I(V (I(V ))). Másrészt az I := I(V ) ideálra írjuk fel az I ⊆ I(V (I)) egyenlőtlenséget, amiből kapjuk, hogy I(V ) ⊆ I(V (I(V ))). A másik állítás ugyanígy igazolható. 4.1. Feladat. Bizonyítsuk be, hogy ha V véges halmaz, akkor V (I(V )) = V . Ahhoz, hogy polinomok közös gyökei közül ne csak az alaptestben levőket tudjuk vizsgálni, szükségünk lesz a következő definícióra. 4.6. Definíció. Legyen az F′ test az F egy bővítése, és VF′ (I) := {y ∈ F′n : f (y) = 0 minden f ∈ I-re} az F′n -ben levő közös gyökök halmaza. Az I(V ) ideált szó szerint ugyanúgy értelmezzük V ⊆ F′n esetén, tehát I(V ) E F [x] továbbra is. Speciálisan, ha F az F algebrai lezártja, akkor VF (I) az algebrai lezárt feletti összes gyökök halmaza. √ √ I az I ideál radikál√ja, azaz Könnyű látni, hogy I ⊆ I(V (I)), ahol √ f ∈ I ⇐⇒ valamely e pozitív egészre f e ∈ I. Valóban, ha f ∈ I, azaz f e ∈ I, akkor tetszőleges y ∈ V (I)-n f eltűnik, hiszen f e is eltűnik V (I) definíciója szerint. Ez azt jelenti, hogy f ∈ I(V (I)). A megfordítás általában nem igaz, algebrailag zárt test felett azonban igen. Erről szól a kommutatív algebra egyik legfontosabb állítása, Hilbert nullhelytétele, amelyet itt nem bizonyítunk. √ 4.7. Tétel (Hilbert Nullstellensatz). I = I(VF (I)). A megoldások száma, nulla dimenziós ideálok 4.2. Feladat. Bizonyítsuk be, hogy V (I) egyenlő I tetszőleges generátorrendszerében szereplő polinomok közös gyökeinek a halmazával.

31

A (4) egyenletrendszer megoldásainak halmaza az előbbi feladat szerint éppen V (I). Természetesen az is igaz, hogy az algebrai lezárt feletti megoldások éppen VF (I) elemei. ? ? A fő kérdések tehát: VF (I) = ∅, V (I) = ∅, illetve |VF (I)| =?, |V (I)| =?, végül pedig, hogy pontosan mik VF (I) és V (I) elemei. Nem túl meglepő módon az algebrai lezártban levő megoldásokkal kapcsolatos kérdésekre tudunk egyszerűbben választ adni. Az első probléma eldöntése Gröbner-bázisok segítségével egészen könnyű. 4.8. Állítás. Legyen az I ideál egy Gröbner-bázisa G. Pontosan akkor teljesül VF (I) = ∅, ha G-ben szerepel egy nem nulla konstans polinom. Bizonyítás: Hilbert nullhelytételéből következik, hogy VF (I) = ∅ akkor és csak akkor, ha 1 ∈ I (tehát I = F [x]). Ha ugyanis √ VF (I) = ∅, akkor I(VF (I)) √ = I(∅) = F [x], tehát a Nullstellensatz szerint I = F [x], ezért 1 ∈ I, tehát 1 ∈ I is igaz. A megfordítás nyilvánvaló: az 1 polinomnak nincs gyöke. Ha G-ben van nemnulla konstans polinom, akkor ez I-ben is benne van, tehát 1 ∈ I. Fordítva: ha 1 ∈ I, akkor G-ben kell legyen g polinom, amely főtagja osztja az 1 monomot, tehát amely főtagja 1. Miután 1 a legkisebb monom, ezért g ebből az egyetlen monomból áll, tehát konstans. Ez persze speciális esete az algebrai lezárt feletti megoldások számára vonatkozó kérdésnek. A következő tétel két módon jellemzi azon polinomegyenletrendszereket, amelyeknek véges sok megoldása van az algebrai lezárt felett. Vegyük észre, hogy tetszőleges Gröbner-bázis kiszámításával el lehet tehát dönteni, hogy VF véges-e. 4.9. Tétel. Legyen I egy Gröbner-bázisa G. Ekkor az alábbiak ekvivalensek. i 1. Minden i ∈ [n]-hez létezik gi ∈ G és wi ∈ N, hogy lm (gi ) = xw i .

2. |Sm (I)| < ∞ 3. |VF (I)| < ∞ Az ilyen ideálokat 0 dimenziós ideáloknak nevezzük. Bizonyítás: 1 ⇒ 2: Egy xu monom legfeljebb akkor lehet Sm (I)-ben, ha i minden i-re ui < wi (hiszen xw i ∈ Lm (I)), ilyenből viszont csak véges sok (w1 · w2 . . . wn ) van. 2 ⇒ 3: Az 1, xi , x2i , . . . monomok modulo I lineárisan összefüggőek, hiszen dim (F [x] /I) = |Sm (I)| véges. Ezek szerint van olyan fi (xi ) ∈ F[xi ], amely 32

I-ben van. Ennek csak véges sok gyöke van, azaz VF (I) elemeinek i-edik koordinátája csak véges sok féle lehet. 3 ⇒ 1: Miután VF (I) véges, az i-edik koordinátában csak véges sok elem fordulhat elő, legyenek ezek αi,1 , . . . , αi,si ∈ F. Ha fi,j (xi ) az αi,j minimálpolisi Q fi,j (xi ). Világos, hogy fi (xi ) ∈ F [x] nomja F felett, akkor legyen fi (xi ) = j=1 √ eltűnik VF (I) minden elemén, azaz fi (xi ) ∈ I(VF (I)) = I a Hilbert Nullstellensatz szerint. Tehát valamilyen ei -re fiei (xi ) ∈ I. Ha gi ∈ G egy polinom, amelyre lm (gi ) | lm (fiei ), akkor miután fiei főtagja xi hatványa (pontosan lm (fiei ) = xiei ·deg fi ), ezért lm (gi ) is xi -hatvány. Ebben a jegyzetben nem foglalkozunk ideálok dimenziójával, kizárólag a nulla dimenziós esetet különböztetjük meg, ezért magasabb dimenziókra pontos definíciót sem adunk. Szemléletesen azonban egyszerű magyarázni az elnevezést. Legyen például I = hx21 − x2 − x3 i és n = 3. Ekkor I két dimenziós, miután V (I) a három dimenziós tér egy felületének pontjaiból áll. A tér véges sok pontja természetesen 0 dimenziós halmaz, tehát ilyenkor jogos 0 dimenziós ideálnak nevezni I-t. 4.10. Példa. Legyen F = R, n = 2 és I = hx21 + x22 i. Ekkor V (I) = {(0, 0)},√ de VC (I) végtelen√sok pontot tartalmaz, egész pontosan VC (I) az x1 + x2 −1 = 0 és x1 − x2 −1 = 0 komplex egyenesek uniója. Tehát I nem 0 dimenziós (hanem 1). Utóbbi egyben arra is példa, hogy előfordulhat, hogy az algebrai lezárt felett végtelen sok megoldás van, míg az alaptestben véges sok. A következő cél, hogy pontosabbat mondjunk a megoldások számáról a 0 dimenziós esetben, tehát amikor véges sok megoldás van. Ha F′ test az F bővítése, akkor jelölje IF′ az I által F′ [x]-ben generált ideált, azaz IF′ = I · F′ [x]. 4.11. Lemma. VF′ (IF′ ) = VF′ (I) Bizonyítás: Nyilvánvaló, hogy y pontosan akkor közös gyöke egy ideál összes polinomjának, ha az ideál egy generátorrendszerének gyöke. Válasszunk I-ben egy f1 , . . . , fs generátorrendszert. Ezek a polinomok F′ [x]-ben természetesen IF′ ideált generálják. Tehát az állításban szereplő két ideálnak ugyanaz a polinomhalmaz generátorrendszere, így az ideálok F′n -beli gyökei is megegyeznek. 4.12. Lemma. Sm (IF′ ) = Sm (I), sőt G ⊆ F [x] pontosan akkor Gröbnerbázisa I-nek, ha Gröbner-bázisa az IF′ ideálnak. 33

Bizonyítás: Miután tetszőleges Gröbner-bázis meghatározza a standard monomokat, ezért elegendő a második állítást igazolni. Ehhez a Buchberger-algoritmus kapcsán tanult, a Gröbner-bázist S-polinomok segítségével jellemző 3.3 tételt használjuk. Jelölje hGiF , illetve hGiF′ a G által F [x], illetve F′ [x] gyűrűben generált ideált. Az idézett tétel szerint G pontosan akkor Gröbner bázis hGiF ideálban, ha G bármely két elemének S-polinomja 0-ra redukálható G-vel. Ez a feltétel viszont független a testtől, ezért újra alkalmazva a tételt, utóbbi azzal ekvivalens, hogy G Gröbner bázisa hGiF′ -nek. Annyit kell még látni, hogy G pontosan akkor generálja az egyik gyűrűben I-t, ha a másikban IF′ -t. Ha G az IF′ ideál generátorrendszere, akkor IF′ ∩ F [x] = I miatt (és mert G ⊆ F [x]) teljesül hGiF = I. Fordítva: miután IF′ az I által F [x]-ben generált ideál, ezért I bármely generátorrendszere F′ [x]-ben IF′ ideált generálja. Az állítást ezzel beláttuk. Készen állunk a megoldások számáról szóló második tételünk bizonyítására. 4.13. Tétel. Ha valamelyik oldal véges, akkor ¯ ³√ ´¯ ¯ ¯ |VF (I)| = ¯Sm I ¯.

Bizonyítás: Tegyük fel először, hogy F = F, azaz az alaptestünk algebrailag zárt. Ekkor a 2.24 következmény és a Hilbert Nullstellensatz miatt ¯ ³√ ´¯ ¯ ¯ |V (I)| = |Sm (I(V (I)))| = ¯Sm I ¯,

amint állítottuk. Az általános esetben az előbbi összefüggést IF ideálra alkalmazva azt kapjuk, hogy ¯ ³p ´¯ ¯ ¯ IF ¯ |VF (IF )| = ¯Sm

A 4.11 lemma miatt egyenlő |VF (I)|-vel. A jobb oldal pedig q a bal oldal ³√ ´ √ p I , másrészt a 4.12 lemma egyrészt IF = I · F[x] = I · F[x] = F ³√ ´ I elemszámával egyezik meg. miatt éppen Sm

4.3. Feladat. Lássuk be az állítást direkt módon, ha n = 1. (Segítség: Ilyenkor I főideál, mondjuk I = hf i. Az f polinom irreducibilis √ felbontása segítségével I generátorát könnyű megadni.) Jogos ezek után a kérdés, hogy nyertünk-e valamit, azaz I ismeretében meg tudjuk-e határozni I radikáljának standard monomjait. A válasz igen, 34

ráadásul a módszer Gröbner-technikákkal működik, de ezen jegyzetben nem tárgyaljuk. A nulla karakterisztikájú alaptest esete egyébként nem különösebben nehéz, pozitív karakterisztika esetén a megoldás viszont egyáltalán nem magától értetődő, az ismert algoritmusok mindössze néhány évesek. Egy jó kiindulópont ezek felkutatására ³√ ´ [20], és az ott hivatkozott cikkek. Min√ I ⊆ Sm (I), tehát felső becslést egyszerűen denesetre I ⊇ I miatt Sm tudunk mondani a megoldások számára pusztán I egy Gröbner-bázisának kiszámításával. ′ Mielőtt továbblépnénk, √ érdemes megjegyezni, hogy F tetszőleges F bővítése esetén VF′ (I) = VF′ ( I), hiszen egy polinomnak és hatványainak ugyanazok a gyökei. Polinom-egyenletrendszerek normálformája Az alfejezet tételeiben eddig nem tettünk fel semmit a Gröbner-bázishoz tartozó tagsorrendről. A továbbiakban viszont a lexikografikus rendezést fogjuk használni. 4.14. Definíció. A (4) egyenletrendszer normálformája a g1 (x) = 0 ... gm (x) = 0 egyenletrendszer, ahol G = {g1 , . . . , gm } az f1 , . . . , fs polinomok által generált I ideál redukált Gröbner-bázisa a lexikografikus tagsorrendre nézve. 4.15. Állítás. Ha I nulla dimenziós (tehát az algebrai lezárt felett is csak véges sok közös gyöke van I elemeinek) és G egy lexikografikus Gröbner-bázisa, akkor minden i ∈ [n] számra van olyan gi ∈ G polinom, amely csak xi , xi+1 , . . . xn változóktól függ, és gi vezető tagja xi -hatvány. Bizonyítás: A 4.9 tétel szerint minden 0 dimenziós ideál és bármely i ∈ [n] számra tetszőleges Gröbner-bázis tartalmaz olyan gi polinomot, amelyre lm (gi ) épp xi -hatvány. A lexikografikus rendezés tulajdonságai miatt gi semelyik monomjában nem szerepelhet olyan xj , amelyre j < i, hiszen ez a monom nagyobb volna xi bármely hatványánál. Ez az egyszerű megfigyelés lehetőséget ad nulla dimenziós ideálok elemei közös gyökeinek meghatározására. Jelölje tehát az I ideál lexikografikus Gröbner-bázisának a tételben szereplő n elemét gn (xn ), . . . , gi (xi , . . . , xn ), . . . , g1 (x1 , . . . , xn ). Ekkor a közös gyökök utolsó koordinátája biztosan gn (xn ) 35

egyváltozós polinom gyökei közül kerül ki. Ha yn a gn egy gyöke, akkor ezt gn−1 -be helyettesítve egy egyváltozós gˆ(xn−1 ) = gn−1 (xn−1 , yn ) polinomot kapunk, amelynek egy gyöke legyen yn−1 . Az eljárást yn−1 és yn elemek gn−2 -be helyettesítésével folytathatjuk. A g1 , . . . , gn polinomok ilyen vizsgálata után meg kell nézni még, hogy a kapott gyökök kielégítik-e a további gn+1 , . . . gm polinomokat is. 4.16. Példa. Tekintsük az x1 x2 + x3 − 11 = 0 x1 x3 + x2 − 13 = 0 x2 x3 + x1 − 17 = 0. egyenletrendszert Q felett. A megfelelő I ideál egy lex Gröbner-bázisa g3 (x3 ) = x53 − 11x43 − 2x33 + 243x23 − 457x3 + 210 ¢ 1 ¡ g2 (x2 , x3 ) = 120x2 − 13x43 + 126x33 + 200x23 − 2999x3 + 2010 120 g1 (x1 , x2 , x3 ) = x1 + x2 x3 − 17. A g3 polinom racionális gyökeit 210 egész osztói között kell keresnünk. Ellenőrizhető, hogy az egyetlen racionális gyök az 5. Ekkor g2 (x2 , 5) = x2 − 3, tehát x2 csakis 3 lehet. Végül g2 (x1 , 3, 5) = x1 − 2, azaz V (I) = {(2, 3, 5)}. 3) Ha kíváncsiak vagyunk VQ (I)-re is, kénytelenek vagyunk megoldani a g(x = x3 −5 4 3 2 x3 − 6x3 − 32x3 + 83x3 − 42 = 0 egyenletet, akár a megoldóképlettel, akár valamilyen numerikus módszerrel (a négy gyök mindegyike valós). Annyit mindenesetre bonyolultabb számolások nélkül is látunk, hogy g3 -nak öt különböző gyöke van, amelyek mindegyikéhez pontosan egy¯ VQ (I)-beli pont tar¯ ¯ ¯ tozik (hiszen g2 az x2 -ben, g3 az x3 -ban lineáris) azaz VQ (I) = 5. Vegyük észre, hogy |Sm (I)| = 5 szintén teljesül. 4.4. Feladat. Mutassuk meg, hogy amennyiben f1 , . . . , fs lineáris polinomok, úgy az egyenletrendszer normálalakja az egyenletrendszerhez tartozó mátrix felső háromszög alakjának felel meg (minden sor első nullától különböző eleme 1, és ennek oszlopindexe nagyobb, mint a felette levő sorban található első nemnulla elem oszlopindexe). A fenti gyökkereső eljárás tehát a Gauss-elimináció általánosítása.

A módszer többé-kevésbé használható nem nulla dimenziós ideál esetén is: ha xn egy hatványa főtag, akkor ugyanúgy találunk egy megfelelő tulajdonságokkal rendelkező gn (xn ) polinomot, mint a 4.15 állítás bizonyításában. Ha xn semelyik hatványa sem főtag, akkor viszont véges sok kivételtől eltekintve 36

n

F minden eleme előfordul, mint egy F -beli megoldás i-edik koordinátája, tehát a behelyettesítgetést ilyenkor szinte bármerre folytathatjuk. A részletek kidolgozását az Olvasóra bízzuk. A tisztesség kedvéért meg kell említeni, hogy a fenti eljárás a numerikus számítások tekintetében korántsem olyan jó, mint gondolnánk. Egyrészt a lexikografikus Gröbner-bázis együtthatói nem mindig „szépek”, elég csak megnézni a 4.16 példát: az aránylag kis egész számokból nagyobb egészek, néhol pedig törtek lettek a normálformára hozás során. Másrészről, ha például valós együtthatós polinomokkal kell számolnunk, akkor a Gröbner-számításhoz feltehetően kerekíteni kell ezeket, ami a Gröbner-bázisban már komoly eltéréseket okozhat. (Nagyon nem mindegy, hogy egy polinom egyik monomjának 10−100 az együtthatója, vagy 0, ezen múlhat például, hogy mi a főtag.) A módszer tehát ebben a formájában numerikusan instabil. Végül – ha a normálformát pontosan ki is tudtuk számolni –, az egyváltozós polinomok közelítéssel meghatározott gyökeit más polinomokba helyettesítve a közelítés hibája esetleg túlságosan megnőhet. Ezen kérdések egyik legnagyobb szakértője Hans J. Stetter, akinek a honlapján2 találhat útbaigazítást a numerikus számítások iránt érdeklődő Olvasó. Egy polinom-egyenletrendszer megoldásának más értelmezését is szokás vizsgálni. A közös gyökök halmazán túl azt is célként tűzhetjük ki, hogy a gyökök multiplicitását határozzuk meg. Például az x1 x2 − x1 − x2 + 1 = 0 egyenletnek az (1, 1) gyöke és az (y, 1), illetve (1, y) gyökei (ahol y 6= 1) között lényeges különbség van. A legáltalánosabb megoldásfogalom az egyenletrendszernek megfelelő ideál primér felbontásának meghatározása. A témának nagy irodalma van (lásd például [17], vagy az újabb [10] és [21]), a módszerek legtöbbször Gröbner-számításokat használnak.

4.3. Kombinatorikai alkalmazások Bemelegítésként mutatunk egy példát, hogyan lehet kombinatorikai problémákat polinomokra vonatkozó kérdéssé átfogalmazni, és ezután Gröbnerbázisok segítségével megoldani. Gráfok 3-színezhetősége Legyen adott n ponton egy G gráf. A kérdés, hogy kiszínezhetőek-e a pontjai három színnel, úgy, hogy szomszédos csúcsok különböző színűek. 2

http://www.math.tuwien.ac.at/˜stetter/

37

Legyen F = C és ebben ε egy primitív harmadik egységgyök. A három „szín” 1, ε és ε2 lesz. A G gráf i-edik csúcsához rendeljünk egy xi változót, xi értéke mutatja majd az i csúcs színét. Fogalmazzuk meg a színezés szabályait polinomok eltűnési feltételeként! • Csak 1, ε és ε2 lehet szín: x3i − 1 = 0. • Szomszédos i és j csúcsok különböző színűek kell legyenek: x2i + xi xj + x2j = 0. Ez az egyenlet – az előző feltétellel együtt – a kért tulajdonságot garantálja. Valóban: x3i = 1 = x3j , ezért 0 = x3i − x3j = (xi − xj )(x2i + xi xj + x2j ), tehát xi és xj pontosan akkor különböző, ha a szorzat második tényezője tűnik el. Legyen I az ezen polinomok által generált ideál. Az eddigiekből világos, hogy G pontosan akkor színezhető 3 színnel, ha az I-beli polinomoknak van közös gyöke, azaz V (I) 6= ∅. A polinomiális egyenletek megoldhatóságáról szóló 4.8 állítás szerint V (I) 6= ∅ ⇐⇒ G-ben nincs konstans polinom, ahol G az ideál tetszőleges Gröbner-bázisa. Ez az alkalmazás szépen mutatja a polinom-módszernek nevezett eljárás erejét kombinatorikában. Ugyanakkor a Gröbner-bázis számítás szempontjából negatív eredmény, hiszen egy NP-teljes problémát oldottunk meg Gröbner-bázis számolás segítségével. A Hilbert-függvény Bevezetünk egy igen fontos fogalmat, amely gyakran használható kombinatorikai tulajdonságok algebrai átfogalmazására. 4.17. Definíció. Ha m nemnegatív egész, jelölje F [x]≤m az F feletti legfeljebb m-edfokú polinomok vektorterét. Hasonlóan, egy I E F [x] ideál esetén I≤m = I ∩ F [x]≤m az előbbi vektortér azon altere, amely az I-beli legfeljebb m-edfokú polinomokból áll. Az F [x] /I algebra Hilbert-függvénye ± ¢ ¡ H(m) = dimF F [x]≤m I≤m .

Most megadjuk a 2.17 tétel egy általánosítását fok-kompatibilis rendezésekre.

4.18. Állítás. Legyen ≺ tetszőleges fok-kompatibilis rendezés (például deglex, vagy degrevlex). Ekkor a legfeljebb m-edfokú standard ± monomok I≤m szerinti mellékosztályai lineáris bázisát alkotják az F [x]≤m I≤m vektortérnek 38

Bizonyítás: Miután a standard monomok modulo I lineárisan függetlenek és I≤m ⊆ I, ezért modulo I≤m is azok. Azt kell még megmutatnunk, hogy generálják is a legfeljebb m fokú polinomokat modulo I≤m . Legyen f ∈ F [x] legfeljebb m fokú és legyen fˆ az f egy ≺-hez tartozó Gröbner-bázis szerinti redukáltja. Vegyük észre, hogy a redukálás során csak legfeljebb m fokú polinomokat használhatunk, hiszen a fok-kompatibilitás miatt a nagyobb fokú polinomok főtagjai nagyobbak volnának, mint lm (f ). Így fˆ és f − fˆ szintén legfeljebb m fokú, utóbbiból adódik f − fˆ ∈ I≤m . Elegendő ezért fˆ polinomot előállítani legfeljebb m fokú standard monomok lineáris kombinációjaként. De miután fˆ monomjai redukáltak egy Gröbner-bázisra nézve, ezért fˆ standard monomok lineáris kombinációja, a fokszámkorlát miatt pedig ezek legfeljebb m fokúak. 4.19. Következmény. Ha ≺ egy fok-kompatibilis rendezés, I egy ideál, akkor H(m) éppen a legfeljebb m-edfokú, ≺-re nézve standard monomok száma. Ha I nulla dimenziós, akkor van olyan m0 , hogy m ≥ m0 -ra H(m) = |Sm (I)|, tehát nem függ m-től. Bizonyítás: Az első állítás világos a 4.18 állításból. A másodikhoz emlékezzünk vissza, hogy I nulla dimenziós voltának egy ekvivalens megfogalmazása az volt, hogy Sm (I) véges, így m0 választható a legmagasabb fokú standard monom fokának. Láttuk, hogy egy konkrét ideál Hilbert-függvények kiszámításához nem kell mást tennünk, mint meghatározni valamely fok-kompatibilis rendezésre vonatkozó Gröbner-bázist. Most megnézzük, hogy ennek mi köze van a kombinatorikához. 4.20. Definíció. Legyen F ⊆ 2[n] egy halmazrendszer (avagy halmazcsalád ), azaz az [n] halmaz bizonyos részhalmazaiból álló halmaz. Az F család ideálja I(VF ), ahol VF = {vF : F ∈ F} és vF pedig F karakterisztikus vektora, tehát az i-edik koordinátája 1, ha i ∈ F és 0 különben. Miután e jegyzetben nincs szükségünk algebrák Hilbert-függvényére teljes általánosságban, ezért nem okoz keveredést, hogy F [x] /I(VF ) Hilbert-függvényét ezentúl röviden F Hilbert-függvényének fogjuk nevezni. Megjegyezzük, hogy a definíció elég általános, például gráfok is kezel¡s¢ hetőek vele. Egy s pontú gráfot kódolhatunk egy 2 dimenziós 0-1 vektorral: minden pontpárhoz egy koordinátát rendelünk, amelynek értéke 0 vagy 1, attól függően, hogy az adott gráfban van-e él a két pont között. A VF halmazrendszer ilyen alkalmazásokban valamilyen közös tulajdonsággal (k-színezhető, k-összefüggő) rendelkező összes s pontú gráfok vektorainak halmaza. 39

4.21. Definíció. Ha G ⊆ [n], akkor legyen xG =

Q

xi . Világos, hogy

i∈G

tetszőleges négyzetmentes monom valamely G ⊆ [n] halmazra xG alakú, továbbá hogy deg xG = |G|. 4.22. Definíció. Két F, G ⊆ 2[n] halmazrendszer I(F, G) tartalmazási mátrix a egy |F|×|G| mértetű mátrix, amely sorai F, oszlopai G elemeivel vannak indexelve. Az (F, G)-hez tartozó érték a mátrixban 1, ha G ⊆ F , 0 különben. 4.23. Tétel.¡Jelölje ¢ az [n] összes legfeljebb m elemű részhalmazából álló hal[n] mazcsaládot ≤m . Ekkor F halmazrendszer Hilbert-függvénye µ

µ

[n] H(m) = rangF I F, ≤m

¶¶

.

Bizonyítás: Miután minden i ∈ [n] esetén x2i − xi ∈ IF , ezért IF standard monomjai négyzetmentesek. Tekintsük az összes legfeljebb m fokú négyzetmentes monomot. A 4.18 állítás miatt ezek közül a modulo I(VF ) lineárisan függetlenek maximális száma épp egyenlő a legfeljebb m-edfokú standard monomok számával, ami a 4.19 következmény szerint éppen H(m). Tehát © ª H(m) = rangF xw + I(VF ) : deg xw ≤ m és xw négyzetmentes © ª = rangF xG + I(VF ) : |G| ≤ m , (5)

ahol a halmaz rangján a lineárisan függetlenek maximális számát értjük. Láttuk, hogy F [x] /I(VF ) izomorf a VF -en értelmezett fügvények vektorterével. Másképpen, izomorf az F|F | oszlopvektorok terével, ahol f (x)

függvénynek az az f vektor felel meg, amely F ∈ F-fel indexelt koordinátája f (vF ). Ezen izomorfizmus mentén átírva (5) egyenlőséget, kapjuk, hogy ¶¾ ½ µ [n] . H(m) = rangF (xG (vF ))F ∈F : G ∈ ≤m

Végül vegyük észre, hogy xG (vF ) pontosan akkor 1, ha G ⊆ ¡F és¢ 0 különben. [n] -hez tartozó Ezek szerint (xG (vF ))F ∈F éppen a tartalmazási mátrix G ∈ ≤m oszlopa. Egy extremális halmazelméleti eredmény A kombinatorikai alkalmazások lezárásaként bemutajuk Hegedűs Gábor, Rónyai Lajos és e sorok írójának egy 2006-os eredményét. A bizonyítás egy részét kihagyjuk, a részletek megtalálhatóak [15] cikkben. 40

4.24. Definíció. Legyen L ⊆ {0, . . . , q−1} halmaz és F egy halmazrendszer. Azt mondjuk, hogy F modulo q L-kerülő, ha F ∈ F és f ∈ L-ből következik, hogy |F | 6≡ f (mod q). Ha pedig az teljesül, hogy bármely két különböző F1 , F2 ∈ F esetén |F1 ∩ F2 | ≡ f (mod q) fennáll valamely f ∈ L-re, akkor F-et modulo q Lmetszőnek nevezzük. 4.25. Definíció. Egy L ⊆ {0, . . . , q − 1} halmaz modulo q intervallum, ha L vagy egész számok intervalluma, vagy olyan L1 , L2 ⊆ {0, . . . , q − 1} intervallumok uniója, amelyekre teljesül, hogy 0 ∈ L1 és q − 1 ∈ L2 . 4.26. Tétel (Hegedűs, Rónyai, Felszeghy; 2006). Legyen q egy prímhatvány, L modulo q intervallum és F ⊆ 2[n] egy modulo q L-kerülő, L-metsző halmazcsalád. Ha |L| ≤ n − q + 2, akkor q−1 µ ¶ X n . |F| ≤ k k=|L|

A tétel bizonyításához előbb be kell vezetni egy újabb halmazrendszert. 4.27. Definíció. Legyenek q, d és ℓ egész számok, amelyekre teljesül 1 ≤ ℓ < q. Ekkor a modulo q teljes ℓ-széles család : G = {G ⊆ [n] : ∃ g ∈ Z hogy d ≤ g < d + ℓ és |G| ≡ g

(mod q)} .

Más szóval G az [n] minden olyan részhalmazát tartalmazza, amely elemszáma modulo q beleesik a [d, d + ℓ − 1] (ℓ hosszú) intervallumba. Az ℓ és q paraméterekre vonatkozó fenti feltételek éppen annyit mondanak, hogy ha |G| ≡ d + ℓ (mod q), akkor G 6∈ G (azaz G valóban ℓ-széles). A következő tétel a 4.26 tétel bizonyításának az alapja. Csak vázoljuk, hogy hogyan juthatunk el ehhez az eredményhez, a részletes igazolás hosszadalmas volna. 4.28. Tétel. Legyen p prímszám, Fp a p elemű test, q pedig p-hatvány. Jelölje H(m) a modulo q teljes ℓ-széles G család Hilbert-függvényét. Ha 0 ≤ m ≤ n+ℓ , akkor 2 H(m) ≤

∞ X ℓ−1 µ X i=0 k=0

41

¶ n . m − iq − k

A bizonyítás vázlata a következő. A „lex játék módszerrel” (lásd [16]) meg lehet határozni az I(VG ) ideál lexikografikus standard monomjait. Ezek után maga a lexikografikus Gröbnerbázis is megkonstruálható: minden minimális főtaggal mutatunk egy-egy polinomot az ideálban. Kiderül, hogy ezen polinomok főtagjai a lex és a deglex rendezésre nézve is ugyanazok. Ebből viszont következik, hogy ők egyben egy deglex Gröbner-bázist is alkotnak, és a lex és deglex standard monomok ugyanazok. Ez azért jó hír, mert a legfeljebb m fokú deglex standard monomok összeszámolásával megkapjuk H(m) pontos értékét. A 4.28 tételben szereplő felső korlát a pontos formula triviális becslésével adódik. A 4.26 tétel bizonyításához fel fogjuk használni az alábbi lemmát. 4.29. Lemma. Ha f egész és q a p prím egy hatványa, akkor ¶ ½ µ f −1 0 (mod p), ha f 6≡ 0 (mod q) ≡ 1 (mod p), ha f ≡ 0 (mod q). q−1 Bizonyítás: Egy erősebb állítást fogunk belátni,¡ azt ¢ hogy ¡f ′ ¢ amennyiben f ≡ f ′ f (mod q) és 0 ≤ s < q tetszőleges egész, akkor s ≡ s (mod p). ¡ ¢ ¡f ¢ ≡ s (mod p). Ez pedig fennáll, Utóbbihoz elég megmutatni, hogy q+f s miután µ ¶ X ¶ µ ¶ s µ ¶ µ q+f q f f = · ≡ (mod p), s j s−j s j=0 ¡¢ ahol kihasználtuk, hogy qj ≡ 0 (mod p), ha 0 < j < q. Az eredeti állítás igazolásához tehát feltehetjük, hogy 0 ≤ f ≤ q − 1, így nyilvánvaló az egyenlőség. A 4.26 tétel bizonyítása: Legyen ℓ = q − |L|. Ha L egészekből álló intervallum, akkor legyen d = max L + 1, máskülönben – amikor L az L1 , L2 intervallumok uniója, de maga nem intervallum – akkor legyen d = max L1 + 1, feltéve, hogy 0 ∈ L1 . Jelölje G az ezen d paraméterrel definiált modulo q teljes ℓ-széles halmazrendszert. A definíciókból jól látszik, hogy F ⊆ G. Minden F ∈ F halmazra definiáljuk az fˆF (x) ∈ Q[x] polinomot a következő módon:   ¶ q−1 µ X x · vF − k − 1   redukáltja x2j − xj polinomokkal, fˆF (x) =    q−1 k=0 k6∈L

ahol x · v =

n P

xj vj a vektorok szokásos skaláris szorzata.

j=1

42

Azt állítjuk, hogy fˆF ∈ Z[x]. Miután redukáltunk az x2j − xj polinoP mokkal, így fˆF (x) négyzetmentes, ezért írható fˆF = αG xG valamilyen G⊆[n]

αG ∈ Q együtthatókkal. Ha fˆF 6∈ Z[x], akkor legyen G a tartalmazásra nézve minimális olyan halmaz, amelyre αG 6∈ Z. Világos, hogy a redukció x2j − xj polinomokkal nem változtatja meg az eredeti polinom 0-1 vektorokon vett helyettesítési értékét, ezért fˆF (vG ) egész szám. De másrésztPxG′ (vG ) pontosan akkor 1, ha G′ ⊆ G és 0 különben. Ezért fˆF (vG ) = αG′ + αG . A G′ (G

′

G minimalitása miatt αG′ egész, ha G ( G, így az előbbi egyenlőségből az következik, hogy αG -nek is egésznek kellene lennie. Tehát valóban fˆF ∈ Z[x]. Vegyünk egy F ′ ∈ F halmazt. Ekkor fˆF (vF ′ ) =

¶ q−1 µ X |F ′ ∩ F | − k − 1 q−1

k=0 k6∈L

.

(6)

Ha F ′ 6= F , akkor, miután F modulo q L-metsző, ezért |F ′ ∩ F | − k 6≡ 0 (mod q), ha k 6∈ L. Legyen p prím, amelynek q hatványa. A 4.29 lemmát alkalmazva kapjuk, hogy ha F ′ 6= F , akkor a (6) egyenlet jobb oldalán minden tag 0 modulo p. Ha viszont F ′ = F , akkor miután F modulo q L-kerülő, ezért pontosan egy modulo p nemnulla tag szepepel a jobb oldalon, ez a tag pedig modulo p éppen 1. Jelölje Fp a p elemű testet és fF azt az Fp [x]-beli polinomot, amelyet ˆ fF (egész) együtthatóinak modulo p redukciójával kapunk. A fenti érvelés szerint tehát ½ 0 ha F 6= F ′ fF (vF ′ ) = 1 ha F = F ′ .

Miután fˆF foka legfeljebb q −1, ezért ugyanezt elmondhatjuk fF polinomról is. Ezt a korábbi jelöléseinkkel úgy írhatjuk, hogy fF ∈ Fp [x]≤q−1 . Azt ± állítjuk, hogy fF polinomok f F képei az Fp [x]≤q−1 I(G)≤q−1 -re képező természetes faktorleképezésnél lineárisan függetlenek Fp felett. Tegyük ugyanis fel, hogy X αF f F = 0 (7) F ∈F valamely αF ∈ Fp együtthatókra. Többször használtuk, hogy Fp [x] /I(G) elemei tekinthetőek VG halmazon értelmezett függvényeknek. Speciálisan a (7) egyenlőség akkor is fennáll, ha behelyettesítjük vF pontot valamely F ∈ F ⊆ G halmazra. Innen azonnal következik αF = 0. 43

Végül annyit kell észrevennünk, hogy az f F ±polinomok számának a lineáris függetlenség miatt felső korlátja Fp [x]≤q−1 I(G)≤q−1 dimenziója, tehát ³ ´ ± |F| ≤ dim Fp [x]≤q−1 I(G)≤q−1 = H(q − 1) ≤ ∞ X ℓ−1 µ X i=0 k=0

n q − 1 − iq − k

¶

q−1 µ ¶ X n . = k k=|L|

a modulo q ℓ-széles család Hilbert-függvényéről szóló 4.28 tétel miatt. (Jegyezzük még meg, hogy |L| ≤ n − q + 2 egyenlőtlenségből következik a tétel q − 1 ≤ n+ℓ feltétele.) 2

44

Köszönetnyilvánítás Köszönettel tartozom Horváth Erzsébetnek, amiért lektorálta és számtalan hasznos megjegyzéssel javította jelen jegyzetet.

Hivatkozások [1] J. Abott, M. Kreuzer, L. Robbiano, Computing zero-dimensional schemes, J. Symbolic Computation 39 (2005) 31–49. [2] W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, American Mathematical Society, 1994. [3] T. Becker, V. Weispfenning, Gröbner bases – a computational approach to commutative algebra, Springer-Verlag, Berlin, Heidelberg, 1993. [4] M. Brickenstein, Slimgb: Gröbner bases with slim polynomials, Reports on Computer Algebra 35, ZCA, University of Kaiserslautern, (2005). [5] B. Buchberger Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph. D. Thesis, Univ. of Innsbruck, Austria, 1965. [6] B. Buchberger Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal J. Symbolic Computation 41 (2006) no. 3–4, 475–511. [7] B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleischungssystem, Aequationes Mathematicae, 4 (1970), 374–383. [8] B. Buchberger, F. Winkler (editors), Gröbner Bases and Applications, London Mathematical Society Series, Volume 251 (1998), Proc of the international conference ”33 Years of Gröbner Bases” [9] B. Buchberger, H. M. Möller, The construction of multivariate polynomials with preassigned zeros, Proc EUROCAM ’82, Lecture Notes In Computer Science 144 (1982), 24–31. [10] W. Decker, G.-M. Greuel, G. Pfister, Primary decomposition: algorithms and comparisons, in Algorithmic Algebra and Number Theory (G.-M. Greuel, B. H. Matzat, G. Hiss editors), Springer 1998, 187–220.

45

[11] L. E. Dickson, Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors, Amer. Journal Math 35 (1913), 413–422. [12] J.-C. Faugère, A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F4), Journal of Pure and Applied Algebra 139 (1999) 61–88. [13] J.-C. Faugère, A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F5), Proc ISSAC ’02, ACM Press (2002). [14] J. C. Faugère, P. Gianni, D. Lazard, T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Computation 16 (1993) 329–344. [15] B. Felszeghy, G. Hegedűs, L. Rónyai, Algebraic properties of modulo q ℓ-wide families, preprint (2006) [16] B. Felszeghy, B. Ráth, L. Rónyai, The lex game and some applications, J. Symbolic Computation 41 (2006), 663-681. [17] P. Gianni, B. Trager, G. Zacharias, Gröbner bases and Primary Decomposition of Polynomial Ideals, J. Symbolic Computation 6 (1988), 149–167. [18] A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. Traverso, ”One sugar cube, please” or selection strategies in Buchberger algorithm, Proc ISSAC ’91, ACM Press (1991), 49–54. [19] G.-M. Greuel, G. Pfister, A Singular Introduction to Commutative Algebra (with contributions by O. Bachmann, C. Lossen, and H. Schönemann), Springer-Verlag 2002. [20] S. Laplagne, An algorithm for the computation of the radical of an ideal, Proc ISSAC ’06, ACM Press (2006) 191–195. [21] S. Laplagne, Computation of the Minimal Associated Primes, in Challenges in Symbolic Computation Software (W. Decker, M. Dewar, E. Kaltofen, S. Watt editors) Dagstuhl Seminar Proceedings 2006, http://drops.dagstuhl.de/opus/volltexte/2006/774 [22] M. G. Marinari, H. M. Möller, T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 103–145. 46

[23] T. Mora, L. Robbiano, Points in affine and projective spaces, in Computational Algebraic Geometry and Commutative Algebra (D. Eisenbud, L. Robbiano editors), Cambridge Univ. Press (1993), 106–150. [24] L. Robbiano, Term orderings on the polynomial ring, Proc EUROCAL ’85, Lecture Notes In Computer Science 204 (1985), 513–517. [25] L. Robbiano, On the theory of graded structures, J. Symbolic Comput. 2 (1986), no. 2, 139–170.

47