Discrete Wiskunde 2, 2WF15, Lente 2011 [version 14 Dec 2010 ed.] [PDF]

Zitiervorschau

Discrete Wiskunde 2 2WF15, Lente 2011 Jan Draisma

Voorwoord Dit zijn aantekeningen voor het vak Discrete Wiskunde (2WF15), gegeven in het lentesemester van 2011. Dit vak bestaat uit twee delen: algoritmische getaltheorie van Benne de Weger en rekenen in polynoomringen van mijzelf; deze delen worden alternerend gegeven. Deze aantekeningen betreffen het tweede deel. Ze zijn grotendeels gebaseerd op de tweede editie van het prachtige boek Ideals, Varieties, and Algorithms van Cox, Little, and O’Shea. Sterker nog, ze vormen slechts een beknopte samenvatting van de hoofdstukken uit dat boek die in het college aan bod komen. Voor dit deel van het college is het essentieel dat iedereen (toegang tot) een exemplaar van voornoemd boek heeft, en dat iedereen een computeralgebrasysteem zoals Mathematica of Singular op zijn laptop heeft. Eindhoven, Lente 2011 Jan Draisma

3

HOOFDSTUK 1

Polynoomringen, vari¨ eteiten en idealen 1. Polynoomringen Definitie 1.1. Een monoom in de variabelen x = (x1 , . . . , xn ) is een uitdrukking αn n α 1 van de vorm xα 1 · · · xn met α := (α1 , . . . , αn ) ∈ N . We schrijven ook wel x . (In dit college begint N met 0.) Twee monomen kun je met elkaar vermenigvuldigen volgens xα · xβ = xα+β . Deze operatie is associatief en heeft een neutraal element x0 , ook wel met 1 aangeduid. De verzameling M = M (x) van alle monomen in x is zodoende een mono¨ıde, die bovendien commutatief is. Zij K een lichaam. Hierbij mag je voor een groot deel van het college denken aan C of R, maar ook bijvoorbeeld eindige lichamen zullen weer aan bod komen. Definitie 1.2. Een polynoom in x over K is een uitdrukking X cα x α α∈Nm m

waarbij we eisen dat het aantal α ∈ N Twee polynomen f =

waarvoor cα ongelijk aan nul is eindig is.

α

P en g = α dα xα kun je optellen volgens X f +g = (cα + dα )xα

P

α cα x

α

en vermenigvuldigen volgens  f ·g =

X

 X

 γ

cα dβ  xγ .

α,β:α+β=γ

Polynomen in x over K vormen met deze operaties een ring, die commutatief is en een neutraal element heeft (namelijk 1 · x0 , afgekort tot x0 of 1), net zoals alle ringen in deze aantekeningen. Deze ring heet K[x]. Behalve een ring is het ook een K-algebra, want je kunt een polynoom met een getal uit K vermenigvuldigen en deze operatie is compatibel met de ringoperaties in R. P Definitie 1.3. Voor f = α cα xα ∈ K[x] heet cα de co¨effici¨ent van xα in f , en als cα 6= 0 dan heet cα xα een term van f . De (totale) graad deg f van f is de maximale waarde van |α| := α1 + . . . + αn over alle termen cα xα van f . Als f geen termen heeft (dus f = 0), dan definieren we deg f := −∞. 5

6

¨ 1. POLYNOOMRINGEN, VARIETEITEN EN IDEALEN

2. Vari¨ eteiten We zien polynomen graag als functies op een ruimte. Definitie 2.1. Het n-voudig Cartesisch product K n heet de n-dimensionale affiene ruimte over K. Een polynoom f ∈ K[x] geeft een functie K n → K als volgt: het punt p = (c1 , . . . , cn ) ∈ K n wordt afgebeeld op het element f (p) van K dat je krijgt door in f de variabele xi te vervangen door ci en vervolgens alle operaties in f (optellen, vermenigvuldigen, vermenigvuldigen met getallen uit K) uit te voeren in K. Omgekeerd legt de functie K n → K die door f gedefinieerd wordt, het polynoom f vaak eenduidig vast. Maar niet altijd. Voorbeeld 2.2. Zij K = GF(p), n = 1 en f = xp1 − x1 . Dan is de door f gedefinieerde functie K → K overal nul, maar f is niet het nul-polynoom. Opgave 2.3. Neem aan dat deg f kleiner is dan het aantal elementen van K. Toon aan dat er dan een p ∈ K n is met f (p) 6= 0. Hint: gebruik inductie naar n. In het bijzonder geldt dus: als K oneindig is, dan legt de door een polynoom f gedefinieerde functie f eenduidig vast. Definitie 2.4. Het lichaam K heet algebra¨ısch gesloten als elk polynoom f over K in ´e´en variabele x1 met deg f > 0 een nulpunt in K heeft. In dit geval is elk polynoom in K[x1 ] te schrijven is als een getal maal een product van lineaire polynomen van de vorm x1 −c. Uit een eerder college zul je je herinneren dat C algebra¨ısch gesloten is, maar R niet. Opgave 2.5. Laat zien dat een algebra¨ısch gesloten lichaam oneindig is. We komen nu aan de centrale definitie van dit college. Definitie 2.6. Zij S een deelverzameling van K[x]. Dan heet V (S) := {p ∈ K n | ∀f ∈ S : f (p) = 0} ⊆ K n de (affiene) vari¨eteit gedefinieerd door S. Een willekeurige deelverzameling V van K n heet een affiene vari¨eteit als er een S ⊆ K[x] bestaat waarvoor V = V (S) geldt. Voorbeelden zijn kegelsnedes in R2 of C2 , kegels in R3 , matrices van rang 2 in de ruimte van alle complexe 5 × 5-matrices, enzovoorts. 3. Idealen Merk op dat verschillende verzamelingen S dezelfde vari¨eteit kunnen definieren. Zo kun je S = {f1 , . . . , fk } vervangen door S 0 = {f1 , . . . , fk−1 , fk + h1 f1 + . . . + hk−1 fk−1 }, waarbij h1 , . . . , hk−1 willekeurige polynomen zijn—immers, S 0 heeft precies dezelfde nulpunten in K n als S. Deze ambigu¨ıteit wordt als volgt gedeeltelijk weggenomen. Definitie 3.1. Het ideaal hSi voortgebracht door S is de verzameling van alle polynomen van de vorm h1 f1 + . . . + hk fk waarbij f1 , . . . , fk in S en h1 , . . . , hk in K[x] zitten (en k willekeurig mag zijn).

4. IMPLICIET MAKEN

7

Ga voor jezelf na dat dit inderdaad een ideaal in K[x] is. Later zullen we effectief leren rekenen in K[x]/hSi, zoals we dat met behulp van delen met rest al kunnen in het geval dat n = 1. Lemma 3.2. De vari¨eteit V (hSi) is identiek aan V (S). Dit betekent dat we ons zonder verlies van algemeenheid kunnen beperken tot affiene vari¨eteiten gedefinieerd door een ideaal. Overigens neemt dit de ambigu¨ıteit niet helemaal weg. Zo defini¨eren hx1 i en hx21 i dezelfde vari¨eteit in K 1 , maar zijn het verschillende idealen. Daarover later meer. Opgave 3.3. Laat zien dat (1) ∅ en K n affiene vari¨eteiten zijn; (2) de doorsnede van (willekeurig veel) affiene vari¨eteiten in K n er weer een is; (3) de vereniging van twee affiene vari¨eteiten er weer een is; Hint voor het laatste onderdeel: bekijk, voor n = 3, de vari¨eteit V gedefinieerd door S = {x1 , x2 } en de vari¨eteit W gedefinieerd door T = {x3 }. Door welke polynomen wordt V ∪ W gedefinieerd? 4. Impliciet maken Een belangrijke manier om idealen (en dus vari¨eteiten) te defini¨eren is impliciet, als volgt. Stel we hebben een tweede collectie variabelen y1 , . . . , ym , alsmede m polynomen f1 , . . . , fm ∈ K[x]. Dan is I = (f1 − y1 , . . . , fm − ym ) een ideaal in de ring K[x1 , . . . , xn , y1 , . . . , ym ] = K[x, y]. De doorsnede I ∩ K[y] is een ideaal in K[y], en definieert dus een vari¨eteit in K m . Opgave 4.1. Laat zien dat I ∩ K[y] de kern is van het ring-homomorfisme K[y] → K[x] dat wordt vastgelegd door y1 7→ f1 en y2 7→ f2 . Opgave 4.2. Neem K = R, n = 1, m = 2, f1 := 1 − x21 , f2 := x1 (1 − x21 ). Teken de kromme in R2 geparametriseerd door (f1 , f2 ) en laat zien dat het ideaal hf1 − y1 , f2 − y2 i ∩ K[y1 , y2 ] door ´e´en enkel polynoom wordt voortgebracht, en vindt dit polynoom.

HOOFDSTUK 2

Gr¨ obnerbases 1. Vragen We hebben gezien dat de studie van stelsels polynoomvergelijkingen in meerdere variabelen op natuurlijke manier leidt tot de begrippen ideaal en affiene vari¨eteit. Daarover is een aantal voor de hand liggende vragen te stellen: (1) Is elk ideaal I in K[x] = K[x1 , . . . , xn ] eindig voortgebracht? Dat wil zeggen, is er een eindige deelverzameling S van K[x] zodanig dat I = hSi? Dit is vanuit praktisch oogpunt wenselijk—hoe moeten we immers rekenen met een oneindig stelsel vergelijkingen? (2) Hoe gaan we na of de door I gedefinieerde vari¨eteit niet leeg is, en wat de dimensie daarvan is? Wat is dimensie u ¨berhaupt? (3) Hoe vinden we het (impliciete) ideaal van relaties tussen m polynomen f1 , . . . , fm ∈ K[x]? Als m = 2 en n = 1 gaat het hier bijvoorbeeld om het vinden van de vergelijking voor een geparametriseerde kromme. (4) Hoe bepalen we of een gegeven polynoom f in een ideaal I zit? Hoe bepalen we de doorsnede van twee idealen? Enzovoorts. Op veel van deze vragen zullen we in dit college een antwoord geven, al zullen we het onszelf bij vraag (2) makkelijk maken door aan te nemen dat het lichaam K algebraisch gesloten is. We beginnen met het volgende cruciale lemma. Lemma 1.1 (Dixons lemma). Zij u1 , u2 , . . . ∈ M (x) een oneindige rij monomen in x = (x1 , . . . , xn ). Dan bestaan er indices i en j met i < j waarvoor ui een deler is van uj . 2. Deling met rest We weten hoe deling met rest gaat voor polynomen in ´e´en variabele: bij deling van f = axd + lagere orde door g = bxe + lagere orde met a, b 6= 0 wordt d met e vergeleken. Als d < e, dan zijn we klaar. Anders wordt (a/b)xd−e g van f afgetrokken, zodat de graad van f omlaag gaat, enz. Maar hoe zou dat moeten in polynomen met meer variabelen? Net zo, maar we hebben meer keuze in wat we de grootste term van f en g noemen. Definitie 2.1. Een monomiale ordening op de verzameling M = M (x) van monomen in x = (x1 , . . . , xn ) is een relatie ≤ die voor alle u, v, w ∈ M voldoet aan: (1) u ≤ u; (2) als u ≤ v en v ≤ w dan u ≤ w; (3) als u ≤ v en v ≤ u dan u = v; 9

¨ 2. GROBNERBASES

10

(4) van de uitspraken u ≤ v en v ≤ u is er minstens ´e´en waar; (5) als u ≤ v dan uw ≤ uv; en (6) 1 ≤ u. De eerste twee axioma’s zeggen dat ≤ een parti¨ele quasi-ordening is, het derde dat ≤ zelfs een parti¨ele ordening is, het vierde dat ≤ zelfs een totale ordening is en het vijfde dat de ordening compatibel is met vermenigvuldiging. Als u ≤ v, dan zeggen we dat u ten hoogste v is, en dat v tenminste u is. We gebruiken ook de symbolen met de voor de hand liggende betekenis. Voorbeeld 2.2. De lexicografische ordening op M (x) is de binaire relatie ≤lex gegeven door xα ≤lex xβ als en alleen als ofwel α = β, ofwel de kleinste i ∈ {1, . . . , n} met αi 6= βi voldoet aan αi < βi . Dit is een monomiale ordening. Opgave 2.3. Laat zien dat uit de zes axioma’s samen volgt dat ≤ een welordening is, dat wil zeggen, dat elke niet-lege deelverzameling een kleinste element heeft. (Hint: gebruik Dixon’s lemma.) Opgave 2.4. Laat zien dat de relatie ≤ op M (x) gedefinieerd door xα ≤ xβ :⇔ |α| < |β| of |α| = |β| en α ≤lex β een monomiale ordening is. Deze ordening heet deglex. Opgave 2.5. (1) Laat w := (w1 , . . . , wn ) een vector van positieve re¨ele getallen zijn waartussen geen geheeltallige lineaire relatie bestaat, dat wil zeggen dat uit P i ai wi = 0 voor zekere a1 , . . . , an ∈ Z volgt dat alle ai nul zijn. Bewijs dat de relatie ≤=≤w op M (x) gedefinieerd door X X xα ≤ xβ :⇔ wi αi ≤ w i βi i

i

een monomiale ordening is. (2) Neem aan dat w0 = (w10 , . . . , wn0 ) 6= w net zo’n vector is en dat de ordening ≤w0 gelijk is aan de ordening ≤w . Bewijs dat w0 een positief scalair veelvoud is van w. (3) Concludeer dat er voor n ≥ 2 overaftelbaar veel verschillende monomiale ordeningen zijn. Hoe zit dat voor n = 1? (4) Is elke monomiale ordening van de vorm ≤w voor geschikte w? (Hint: bekijk lexicografische ordening.) P De vector w in de vorige opgave heet een gewichtsvector, en i wi αi heet het wgewicht van het monoom xα . Als er wel geheeltallige lineaire relaties tussen de componenten van w bestaan, kun je w nog steeds gebruiken om een monomiale ordening te defini¨eren, maar dan moet je monomen met hetzelfde w-gewicht nog weer verder ordenen, bijvoorbeeld lexicografisch. De ordening deglex is hier een voorbeeld van, met w = (1, 1, . . . , 1). Opgave 2.6. Laat A een n × m-matrix zijn met positieve re¨ele entries en neem aan dat er geen vector v = (v1 , . . . , vn ) ∈ Zn \ {0} bestaat met vA = 0 ∈ Rm . (1) Bewijs dat de relatie ≤ op M (x) gedefinieerd door xα ≤ xβ :⇔ αA ≤lex βA

3. HILBERTS BASISSTELLING

11

een monomiale ordening is. (2) (*) Laat zien dat elke monomiale ordening van deze vorm is. Definitie 2.7. Zij ≤ een monomiale ordening op M (x). Het leidende monoom lm(f ) = lm≤ (f ) van een polynoom f ∈ K[x] \ {0} is het grootste monoom waarvan de co¨effici¨ent in f niet gelijk is aan 0. De leidende co¨effici¨ent lc(f ) van f is de co¨effici¨ent van lm(f ). De leidende term van f is lc(f )lm(f ). Opgave 2.8. Laat zien dat lm(f g) = lm(f )lm(g) en dat, als f + g 6= 0, lm(f + g) ≤ max{lm(f ), lm(g)}. Lemma 2.9 (Deling met rest). Zij S een deelverzameling van K[x] \ {0} en zij f ∈ K[x]. Laat verder ≤ een monomiale ordening zijn. Dan is f te schrijven als P s∈S qs s + r waarbij • slechts eindig veel van de qs ∈ K[x] ongelijk aan nul zijn, • voor die s geldt dat lm(qs s) ≤ lm(f ), en • waarbij geen enkele term van r deelbaar is door een leidend monoom lm(s) met s ∈ S. Definitie 2.10. In dit geval heet r een rest van van f bij deling door S. Zo’n rest kan uitgerekend worden door eerst r := f te nemen, en zo lang r een term cxα heeft die door een leidend monoom lm(s), s ∈ S deelbaar is, r te vervangen door r − (cxα /lt(s))s (en bij qs het polynoom cxα /lt(s) op te tellen); dit heet een reductiestap. Opgave 2.11. Bewijs dat dit niet-deterministische algoritme om een rest van f bij deling door S te vinden altijd eindigt. De output van dit niet-deterministische algoritme hangt van de monomiale ordening af, maar in het algemeen ook van de gekozen volgorde van de reductiestappen.

3. Hilberts Basisstelling Stelling 3.1 (Hilberts Basisstelling). Elk ideaal I in K[x] = K[x1 , . . . , xn ] is eindig voortgebracht, d.w.z. van de vorm hSi met S een eindige deelverzameling van K[x]. In het bewijs gebruiken we een monomiale ordening; bijvoorbeeld ≤lex , en defini¨eren we lm(I) := {lm(f ) | f ∈ I \ {0}}. Dit is een ideaal in M (x), wat wil zeggen dat het gesloten is onder vermenigvuldiging met elementen uit M (x); zie Figuur 1. De exponenten van monomen in lm(I) vormen een deelverzameling van Nn die “naar boven toe gesloten is”. Uit Dixons lemma volgt dat er f1 , . . . , fk ∈ I zijn waarvoor geldt lm(I) = {m ∈ M (x) | ∃i ∈ {1, . . . , k} : lm(fi )|m}; we zeggen dat lm(f1 ), . . . , lm(fk ) het ideaal lm(I) in M (x) voortbrengen. Vervolgens volgt eenvoudig dat hf1 , . . . , fk i = I.

¨ 2. GROBNERBASES

12

x21x22 x41x2

x51

Figuur 1. Het ideaal in M (x) voortgebracht door x51 , x41 x2 , x21 x22 . 4. Gr¨ obnerbases Verzamelingen {f1 , . . . , fk } als in het bewijs van Hilberts basisstelling zijn zo belangrijk dat ze een naam verdienen. Definitie 4.1. Een Gr¨ obnerbasis van een ideaal I in K[x] ten opzichte van een monomiale ordening ≤ is een deelverzameling B van I \ {0} met de eigenschap dat lm(B) het ideaal lm(I) in M (x) voortbrengt. Een deelverzameling B van K[x] heet een Gr¨ obnerbasis (zonder meer) als B een Gr¨obnerbasis van hBi is. (In veel boeken wordt bovendien ge¨eist dat B eindig is; uit het bewijs van Hilberts Basisstelling weten we immers dat elk ideaal I een eindige Gr¨obnerbasis heeft.) Zo’n basis heeft allerlei belangrijke eigenschappen; we noemen er nu twee. Stelling 4.1. Zij B een Gr¨ obnerbasis van een ideaal I en zij f ∈ K[x]. Dan bestaan er unieke h ∈ I en r ∈ K[x] zo dat f = h + r en zo dat geen van de termen van r deelbaar is door een leidend monoom van een element uit B. Hieruit volgt dat als B een Gr¨obnerbasis is, de rest bij deling van f door B wel uniek is, en dat f ∈ I geldt als en alleen als die rest nul is. Dit beantwoordt dus de laatste vraag van ons rijtje vragen aan het begin van dit hoofdstuk—mits we een Gr¨ obnerbasis van een ideaal uit kunnen rekenen. 5. Buchbergers algoritme Het algoritme van Buchberger heeft als input een eindig stel polynomen in K[x] en als output een Gr¨ obnerbasis van het door die polynomen voortgebrachte ideaal. Definitie 5.1. Zij ≤ een monomiale ordening op M (x) en laat f, g ∈ K[x] polynomen ongelijk aan nul zijn. Zij u = lm(f ), v = lm(g) en w = lcm(u, v). Dan heet S(f, g) = S≤ (f, g) = lc(g)(w/u)f − lc(f )(w/v)g het S-polynoom van f en g. De volgende stelling is van fundamenteel belang in Buchbergers algoritme.

5. BUCHBERGERS ALGORITME

13

Figuur 2. Is deze graaf 3-kleurbaar? Stelling 5.1. Zij B een deelverzameling van K[x] \ {0}. Neem aan dat voor elk paar f, g ∈ B nul een rest is van het S-polynoom S(f, g) bij deling door B. Dan is B een Gr¨ obnerbasis van het ideaal hBi. Dit leidt tot het volgende algoritme. Algoritme 5.2. Input: een eindige deelverzameling T van K[x] \ {0}. Output: een eindige Gr¨obnerbasis van het door T voortgebrachte ideaal. Procedure: (1) Stel B := T en P := {{f, g} | f, g ∈ B}. (2) Zolang P 6= ∅ doe het volgende. (a) Kies een paar {f, g} ∈ P en verwijder dit uit P . (b) Bereken een rest r van S(f, g) bij deling door B. (c) Als r 6= 0, voeg dan r aan B toe en voeg bovendien, voor alle f ∈ B, het paar {r, f } aan P toe. (3) Return B. Stelling 5.2. Het bovenstaande algoritme geeft na eindig veel stappen als output een Gr¨ obnerbasis van het ideaal dat door T wordt voortgebracht. Buchbergers algoritme is in Singular aan te roepen met het commando groebner. Een Gr¨ obnerbasis van een ideaal I is bepaald niet uniek—als B een Gr¨obnerbasis van I is, dan is bijvoorbeeld ook B ∪ {f } een Gr¨obnerbasis van I, voor alle f ∈ I. Definitie 5.3. Een G¨ obnerbasis B heet gereduceerd als elk element van B leidende co¨effici¨ent 1 heeft en als voor elk polynoom f ∈ B geldt dat geen enkele term van f deelbaar is door een lm(h) met h ∈ B \ {f }. Stelling 5.3. Zij I een ideaal in K[x] en zij ≤ een monomiale ordening. Dan heeft I een unieke gereduceerde Gr¨ obnerbasis ten opzichte van ≤. Opgave 5.4. Laat zij , i ∈ {1, . . . , m}, j ∈ {1, . . . , m} variabelen zijn en neem de lexicografische monomiale ordening op M (z) waarbij zk,l > zk0 ,l0 als (k, l) lexicografisch groter is dan (k 0 , l0 ). Leet zien dat de verzameling 2 × 2-determinanten zij zkl − zil zkj , i, k = 1, . . . , m; j, l = 1, . . . , n een Gr¨obnerbasis is. Opgave 5.5. Bewijs met een Gr¨obnerbasisberekening in Singular dat de knopen van de graaf in Figuur 2 niet te kleuren zijn met drie kleuren zonder twee naburige knopen dezelfde kleur te geven. Wat gebeurt er met de berekening als je een kant weglaat?

14

¨ 2. GROBNERBASES

Opgave 5.6. Beschrijf een algoritme dat als invoer twee eindige deelverzamelingen S en T van K[x] neemt, en als uitvoer een eindig stel voortbrengers van de doorsnede hSi ∩ hT i geeft.

HOOFDSTUK 3

De Nullstellensatz 1. De zwakke Nullstellensatz Stelling 1.1. Zij K een algebra¨ısch gesloten lichaam en zij I een ideaal in K[x] = K[x1 , . . . , xn ] dat niet heel K[x] is. Dan hebben de polynomen in I een gemeenschappelijk nulpunt in K n . We zullen dit bewijzen voor het geval dat K = C, waar we gebruik maken van het feit dat C overaftelbaar is. Het algemene bewijs is niet veel moeilijker, maar vergt meer technische snufjes. Definitie 1.1. Zij T een enkele variabele. Met C(T ) bedoelen we het lichaam van rationale functies in T , d.w.z. het lichaam bestaande uit uitdrukkingen van de vorm f /h met f, h ∈ C[T ] en h 6= 0, met de gebruikelijke rekenregels. We zullen f /h ∈ C(T ) met ggd(f, h) = 1 ook opvatten als functie C → C die buiten de polen van h gedefinieerd is. Definitie 1.2. Zij L een lichaam. Met V (L) bedoelen we de L-deelruimte van LN×1 bestaande uit alle oneindige kolomvectoren (c1 , c2 , . . .)T waarvoor slechts eindig veel van de ci ongelijk aan nul zijn. Een lineaire afbeelding van V (L) naar zichzelf kan dan worden voorgesteld door middel van een N × N-matrix waarvan elke kolom een element van V (L) is. Een L-lineaire functie van V (L) naar L kan worden voorgesteld door een rijvector met componenten uit L, waarvan er nu wel oneindig veel niet nul mogen zijn. Lemma 1.3. Zij A(T ) een C(T )-lineaire afbeelding van V (C(T )) naar V (C(T )), voorgesteld door een N × N-marix als hierboven, en zij v(T ) ∈ V (C(T )). Neem aan dat er voor elke t ∈ C waar zowel alle componenten van A(T ) als die van v(T ) gedefinieerd zijn een u ∈ V (C) bestaat met A(t)u = v(t) ∈ V (C). Dan bestaat er een u(T ) ∈ V (C(T )) met A(T )u(T ) = v(T ). Bewijs. Laat R ⊆ V (C(T )) de kolomruimte zijn van A(T ). We willen laten zien dat R de vector v(T ) bevat. Zo niet, dan kun je v(T ) van R scheiden met behulp van een C(T )-lineaire functie f (T ); concreet, er is een rijvector f (T ) ∈ C(T )1×N met de eigenschap dat enerzijds f (T )A(T )u(T ) = 0 voor alle u(T ) ∈ V (C(T )) en anderzijds f (T )v(T ) = 1. Kies nu echter een t ∈ C waar alle componenten van zowel f (T ) als A(T ) als v(T ) gedefinieerd zijn. Dit kan omdat dat in totaal maar aftelbaar veel componenten zijn, die dus in totaal maar aftelbaar veel polen hebben, en anderzijds C overaftelbaar is. Nu is f (t) een rij-vector in C1×N die voldoet aan f (t)A(t)u = 0 voor alle u ∈ V (C) en aan f (t)v(t) = 1. Dit betekent dat het beeld 15

16

3. DE NULLSTELLENSATZ

van A(t) bevat is in de kern van f (t), terwijl v(t) dat niet is. Het stelsel A(t)u = v(t) heeft dus geen oplossing, in tegenspraak tot de aanname.  Bewijs van de zwakke Nullstellensatz voor K = C. We redeneren met inductie naar het aantal variabelen n. We mogen dus aannemen dat als J een ideaal is in C[x1 , . . . , xn−1 ] dat 1 niet bevat, J een nulpunt in Cn−1 heeft. Zij nu I een ideaal in C[x1 , . . . , xn ] dat 1 niet bevat, en zij f1 , . . . , fk een eindig stel voortbrengers van I (die bestaan vanwege Hilberts Basisstelling). Voor elke waarde t ∈ C is de verzameling Jt := {f (x1 , . . . , xn−1 , t) | f ∈ I} een ideaal in C[x1 , . . . , xn−1 ] voortgebracht door de k polynomen fi,t := fi (x1 , . . . , xn−1 , t). Als er een t ∈ C is waarvoor Jt het polynoom 1 niet bevat, dan zijn we klaar. Dan heeft Jt immers een nulpunt (t1 , . . . , tn−1 ), en is (t1 , . . . , tn−1 , t) een nulpunt van I. Dus we mogen aannemen dat voor alle t ∈ C polynomen u1 , . . . , uk ∈ C[x1 , . . . , xn−1 ] bestaan met u1 f1,t + . . . + uk fk,t = 1. Merk op dat dit betekent dat u1 f1 + . . . + uk fk = 1 + h · (xn − t) voor zekere h ∈ C[x1 , . . . , xn ]. Hieruit herleiden we dat −h · (xn − t) ≡ 1

mod I.

Elk lineaire polynoom xn −t in C[xn ] heeft dus een multiplicatieve inverse modulo I. Omdat elk polynoom in C[xn ] een product is van lineaire polynomen—C is immers algebra¨ısch gesloten—volgt dat elk polynoom in C[xn ] \ {0} een multiplicatieve inverse modulo I heeft. Omdat I het polynoom 1 niet bevat, geldt dus I ∩ C[xn ] = {0}. Bekijk aan de andere kant de C(T )-lineaire afbeelding A(T ) : (C(T )[x1 , . . . , xn−1 ])k → C(T )[x1 , . . . , xn−1 ], (u1 , . . . , uk ) 7→ u1 f1 (x1 , . . . , xn−1 , T ) + . . . + uk fk (x1 , . . . , xn−1 , T ). Gegeven is dat voor elke t ∈ C het stelsel A(t)u = 1 een oplossing (u1 , . . . , uk ) ∈ C[x1 , . . . , xn−1 ] heeft. Zowel C(T )[x1 , . . . , xn−1 ] als (C(T )[x1 , . . . , xn−1 ])k hebben aftelbare dimensie over C(T ), dus we kunnen het bovenstaande lemma toepassen, en concluderen dat er een u(T ) = (u1 (T ), . . . , uk (T )) ∈ (C(T )[x1 , . . . , xn−1 ])k bestaat waarvoor A(T )u(T ) = 1. Uitschrijven geeft u1 (T )f1 (x1 , . . . , xn−1 , T ) + . . . + uk (T )fk (x1 , . . . , xn−1 , T ) = 1, waarbij de linkerkant rationaal van T afhangt. Kies een polynoom h ∈ C[T ] \ {0} zodanig dat u0i (T ) := h(T )ui (T ) ∈ C[T ][x1 , . . . , xn−1 ] voor alle i. Dan volgt u01 (T )f1 (x1 , . . . , xn−1 , T ) + . . . + u0k (T )fk (x1 , . . . , xn−1 , T ) = h(T ) en door de variabele T te vervangen door xn vinden we u01 (xn )f1 + . . . + u0k (xn )fk = h(xn ). Met andere woorden, h(xn ) zit in I. Maar dit weerspreekt onze eerdere opmerking dat I ∩ C[xn ] = {0}. 

3. NULLSTELLENSATZ-CERTIFICATEN VOOR COMBINATORISCHE PROBLEMEN

17

2. De sterke Nullstellensatz Bij een ideaal I ⊆ K[x] hoort de nulpuntverzameling V (I) ⊆ K n , een affiene vari¨eteit. Omgekeerd hoort bij elke deelverzameling X van K n een natuurlijk ideaal, namelijk: I(X) := {f ∈ K[x] | f (p) = 0 voor alle p ∈ X}. Lemma 2.1. Er geldt: (1) (2) (3) (4)

als I ⊆ J dan V (I) ⊇ V (J); als X ⊆ Y dan I(X) ⊇ I(Y ); I(V (I(X))) = I(X); V (I(V (I))) = V (I).

Hieruit volgt dat er een bi-jectie is tussen affiene vari¨eteiten (verzamelingen van de vorm V (I) voor zekere I) en bepaalde idealen, namelijk die van de vorm I(X) voor zekere X. De sterke Nulstellensatz geeft een alternatieve beschrijving van die laatste idealen. Definition 2.2. Een ideaal I in K[x] heet radicaal als elke f ∈ K[x] waarvan een positieve gehele macht f n in I zit, zelf al in I zit. Opgave 2.3. Laat zien dat I radicaal is als en alleen als f ∈ K[x] geldt: als f 2 ∈ I dan f ∈ I. Lemma 2.4. Zij I een ideaal in K[x]. Dan is √ I := {f ∈ K[x] | ∃n ∈ Z 0 : f n ∈ I} een radicaal ideaal in K[x] dat I bevat. Dit ideaal heet het radicaal ideaal van I; het is het kleinste radicale ideaal dat I bevat. Stelling 2.1. Neem aan√dat K algebra¨ısch gesloten is. Dan geldt voor elk ideaal I ⊆ K[x] dat I(V (I)) = I. 3. Nullstellensatz-certificaten voor combinatorische problemen Deze paragraaf is deels gebaseerd op werk van De Loera, Lee, Margulies en Onn. We weten dat f1 = 0, . . . , fk = 0 een oplossing heeft (over C, of een ander algebra¨ısch gesloten lichaam) als en alleen als 1 niet in het door f1 , . . . , fk voortgebrachte ideaal zit. Een uitdrukking 1 = a1 f1 + . . . + ak fk heet een certificaat voor het niet oplosbaar zijn van het stelsel. Als dat stelsel equivalent is met het oplosbaar zijn van een combinatorisch probleem, dan heet deze uitdrukking een Nullstellensatz-certificaat voor het niet oplosbaar zijn van dat combinatorische probleem. Aan de andere kant weten we dat zo’n uitdrukking altijd gevonden kan worden door een eindige Gr¨obnerbasisberekening. Opgave 3.1. Een eindige, ongerichte graaf heet Hamiltoniaans als er een cykel is die alle knopen precies 1 keer aandoet. Modelleer de vraag of een graaf zo’n Hamiltoniaanse cykel heeft met behulp van een stelsel polynoomvergelijkingen, en

18

3. DE NULLSTELLENSATZ

los zo’n stelsel op met behulp van Singular in twee gevallen: een waarbij de graaf Hamiltoniaans is, en een waarbij de graaf niet Hamiltoniaans is. Opgave 3.2. Een kliek in een graaf is een verzameling knopen die onderling paarsgewijs verbonden zijn. Modelleer de vraag of een graaf een kliek ter grootte k heeft als een stelsel polynoomvergelijkingen, en los zo’n stelsel op met Singular, weer voor twee gevallen.

HOOFDSTUK 4

Eliminatie 1. Projecteren en elimineren Eliminatie gaat, meetkundig gezien, over het projecteren van vari¨eteiten. Propositie 1.1. Laat x = (x1 , . . . , xn ) en y = (y1 , . . . , ym ) variabelen zijn. Zij V ⊆ K n+m een vari¨eteit en zij I(V ) ⊆ K[x, y] het ideaal van alle polynomen die op V verdwijnen. Definieer W := {q ∈ K m | ∃p ∈ K n : (p, q) ∈ V } Dan is I(W ) ⊆ K[y] gelijk aan I(V ) ∩ K[y]. Merk op dat W in het algemeen geen deelvari¨eteit van K m is. Zo is de projectie van de vari¨eteit in K 1+1 gegeven door x1 y1 = 1 op de tweede co¨ordinaat gelijk aan K ∗ . In dit geval is I(W ) dus gelijk aan {0}. Bewijs. Als f ∈ I(W ) en (p, q) ∈ V , dan geldt q ∈ W en dus f (q) = 0, dus f ∈ I(V ) ∩ K[y]. Omgekeerd, als f ∈ I(V ) ∩ K[y] en q ∈ W , dan is er een p ∈ K n met (p, q) ∈ V en dus f (p, q) = f (q) = 0, dus f ∈ I(W ).  Gevolg 1.2. Laat f1 , . . . , fm ∈ K[x1 , . . . , xn ], en neem aan dat K oneindig is. Zij I ⊆ K[x, y] het ideaal voortgebracht door yj − fj voor j = 1, . . . , m. Dan is I ∩ K[y] het ideaal van alle polynomen die overal op het beeld van de afbeelding K n → K m , x 7→ (f1 (x), . . . , fm (x)) verdwijnen. Bewijs. Dit volgt direct uit de propositie met V = {(x, f (x)) | x ∈ K n }, als we tenminste kunnen inzien dat I gelijk is aan I(V ). Alleen de inclusie I ⊇ I(V ) is niet meteen duidelijk. Maar als h ∈ I(V ), dan geldt h = h0 (yi − fi ) + h00 voor zekere h00 ∈ I(V ) waar yi niet meer in voorkomt. Doe dit met alle yi en je vindt dat h = r + s met r ∈ I en s ∈ I ∩ K[x]. Maar dan verdwijnt s op alle punten in  K n en is dus het nulpolynoom omdat K oneindig is. Opmerking 1.3. Merk op dat in de situatie in het voorgaande bewijs het ideaal K[y] ∩ I gelijk is aan de kern van het unieke K-algebrahomomorfisme K[y] → K[x] dat elke yi naar fi (x) stuurt. Definition 1.4. Laat x en y als boven zijn en zij I een ideaal in K[x, y]. Dan heet I ∩ K[y] het eliminatie-ideaal van I met betrekking tot de variabelen in x. De volgende stelling laat zien dat je eliminatie-idealen ook echt kunt uitrekenen. 19

20

4. ELIMINATIE

Stelling 1.1. Zij I een ideaal in K[x, y] en zij ≤ een monomiale ordening op de monomen in M (x, y) met de eigenschap dat elk monoom uit M (x, y) \ M (y) groter is dan elk monoom in M (y). Zij B een Gr¨ obnerbasis van I met betrekking tot ≤. Dan is B ∩ K[y] een Gr¨ obnerbasis van I ∩ K[y] met betrekking tot de beperking van ≤ tot M (x). In het bijzonder betekent dit, dat B ∩ K[y] het ideaal I ∩ K[y] voortbrengt. Opgave 1.5. Bereken met Singular voortbrengers voor het ideaal van het beeld van de afbeelding Q2 → Q3 , (m, n) 7→ (m2 − n2 , 2mn, m2 + n2 ). Opgave 1.6. De paraplu van Whitney is het oppervlak in C3 gegeven door x = uv, y = v, z = u2 . Teken een plaatje in R3 van de door re¨ele u, v geparametriseerde punten van die paraplu. Vind het ideaal I ⊆ C[x, y, z] van de paraplu en laat zien dat elk punt in V (I) ⊆ C3 ook door geschikte (u, v) ∈ C2 geparametriseerd wordt. Geldt dit ook voor C vervangen door R? 2. Markovbases Een concept dat op het eerste gezicht niets met Gr¨obnerbases te maken heeft is het volgende. Definitie 2.1. Zij A een n×m-matrix met entries uit N = {0, 1, 2, . . .}. In wat volgt schrijven we ker A voor de verzameling van alle kolomvectoren u ∈ Zm zo dat Au = 0. Een Markov basis voor A is deelverzameling M ⊆ ker A met de eigenschap dat er voor elk paar u, v ∈ Nm dat voldoet aan Au = Av een rij u0 := u, u1 , u2 , . . . , uk := v van vectoren in Nn bestaat met de eigenschap dat ui+1 − ui ∈ ±M voor alle i. Voorbeeld 2.2. Neem

 3 A= 0

2 1

1 2

 0 . 3

De vectoren m1 = (−1, 2, −1, 0)T en m2 = (0, −1, 2, −1)T spannen ker A op, maar vormen geen Markovbasis—immers, er geldt A(1, 0, 0, 1)T = A(0, 1, 1, 0)T , maar er is geen pad van (1, 0, 0, 1)T naar (0, 1, 1, 0)T met stappen uit ±{m1 , m2 } dat geheel binnen N4 blijft. De verzameling M = {m1 , m2 , m3 := (−1, 1, 1, −1)T } daarentegen is wel een Markovbasis. Zij namelijk u ∈ N4 . Dan kun je u met stappen uit ±M verbinden met een u0 die hooguit twee positieve entries heeft, die dan bovendien nog opeenvolgend moeten zijn. Zij nu v ∈ N4 met Au = Av, en verbind v met stappen uit ±M met een v 0 met dezelfde eigenschappen. Uit Au0 = Av 0 en het feit dat u0 , v 0 ∈ N4 allebei hooguit twee positieve entries hebben die dan bovendien naast elkaar moeten zitten volgt eenvoudig dat u0 = v 0 . Opgave 2.3. Veralgemeen dit voorbeeld naar het geval waar   n n − 1 ... 0 A= . 0 1 ... n De link met Gr¨ obnerbases en affiene vari¨eteiten komt als volgt tot stand. De matrix A definieert een monomiale afbeelding Cn → Cm gedefinieerd door x = (x1 , . . . , xn ) 7→ (y1 , . . . , ym )

2. MARKOVBASES

met yj =

n Y

21

a

xi ij .

i=1

Het ideaal van het beeld wordt vanwege Gevolg 1.2 gegeven door de doorsnede met C[y] van het ideaal I in C[x, y] voortgebracht door de polynomen n Y a yj − xi ij , j = 1, . . . , m. i=1 Qn voor i=1

Met de verkorte notatie x xbi i voor kolomvectoren b = (b1 , . . . , bn )T ∈ n N , kunnen we bovenstaand polynoom ook schrijven als yj − xaj , waar aj de j-de kolom van A is. Voor u ∈ Nm geldt nu Y Y u (xaj )uj = xAu mod I, yu = yj j = b

j

j

m

zodat als u, v ∈ N voldoen aan Au = Av, dan y u − y v ∈ I. Dit gaan we als volgt gebruiken. Als w ∈ ker A, dan kunnen we w schrijven als w+ − w− met w+ , w− ∈ Nm gedefinieerd door (w+ )i = max{wi , 0} en (w− )i = − min{wi , 0}. Nu geldt Aw+ = Aw− en dus is het polynoom pw := y w+ − y w− ∈ K[y] een element van I. Lemma 2.4. Het ideaal I ∩ C[y] wordt voortgebracht (zelfs opgespannen over C) door binomen van de vorm y u − y v met u, v ∈ Nm zo dat Au = Av. P Bewijs. Stel f = u cu y u ∈ I. Dit betekent dat het polynoom 0 wordt als je elke yj vervangt door het monoom xaj . In dat proces kunnen alleen termen cu y u , cv y v tegen elkaar wegvallen die hetzelfde monoom in x geven, dus waarvoor geldt Au = Av. Van alle termen cu y u met Au gelijk aan een vaste vector w moeten de co¨effici¨enten dus tot nul optellen. Maar dat betekent dat de som van die termen een lineaire combinatie is van binomen y u − y v met Au = Av = w. Omdat dit voor alle w geldt, is f ook zo’n lineaire combinatie.  Theorem 2.5 (Diaconis-Sturmfels). Zij M ⊆ ker A een deelverzameling. Dan is M een Markovbasis voor A als en alleen als de polynomen pw := y w+ − y w− , w ∈ M het ideaal I ∩ K[y] voortbrengen. Een belangrijk gevolg van deze stelling is dat elke matrix A met natuurlijke getallen als entries een eindige Markovbasis heeft. Bovendien kun je dankzij Stelling 1.1 met het Buchbergeralgoritme (ten opzichte van een geschikte monomiale ordening) een eindige Markovbasis van A uitrekenen. Bewijs. Van beide uitspraken verandert de waarheid niet als we M door M ∪ −M vervangen. Dus we mogen wel aannemen dat M = −M . Neem eerst aan dat M een Markovbasis is. Om te bewijzen dat de pw het ideaal I ∩ K[y] voortbrengen is het op grond van voorgaand lemma voldoende te bewijzen dat als u, v ∈ Nm met Au = Av, dan y u − y v ∈ J := h{pw | w ∈ M }i. Omdat M een Markov basis is, bestaan er u0 := u, u1 , . . . , uk := uv , alle in Nm , zo dat ui − ui+1 ∈ ±M . We laten zien dat dit betekent dat y ui modulo J gelijk is aan y ui+1 . Immers, schrijf ui − ui+1 = w = w+ − w− ∈ M . Dan volgt y ui − y ui+1 = y ui+1 +w+ −w− − y ui+1 = y ui+1 −w− (y w+ − y w− ) ∈ J.

22

4. ELIMINATIE

Hier hebben we gebruikt dat ui+1 − w− enkel niet-negatieve componenten heeft. Omgekeerd, neem aan dat de pw , w ∈ M het ideaal I ∩ K[y] voortbrengen. Voor een paar u, v ∈ Nm met Au = Av geldt yu − yv =

k X

y mi (y wi+ − y wi− )

i=1

voor geschikte mi ∈ N en w1 , . . . , wk ∈ M . Hieruit vinden we als volgt een M -pad van u naar v dat helemaal in Nm blijft: aan de linkerkant komt het monoom y v met een minteken voor, dus dat moet ook aan de rechterkant met een minteken voorkomen. Kies een j waarvoor y mj y wj− = y v , en zij v 0 := mj + wj+ . Dan geldt 0 dus v 0 − v = wj+ − wj− = wj ∈ M en y v = y v + y mj (y wj+ − y wj− ), zodat X 0 yu − yv = y mi (y wi+ − y wi− ). i6=j

Aan de linkerkant staan minder termen, dus zo kunnen we doorgaan tot we een M -pad v, v 0 , . . . , u hebben.  3. Rang-1 matrices We willen het ideaal bepalen van alle relaties tussen de entries van rang-1 matrices. Laat hiertoe zij , xi , yj , i ∈ {1, . . . , p}, j ∈ {1, . . . , q} variabelen zijn en bekijk het ideaal I ⊆ K[x, y, z] voortgebracht door de polynomen zij −xi yj met i = 1, . . . , p en j = 1, . . . , q. Het gaat ons om de relaties tussen de zij , dus we zijn ge¨ınteresseerd in de doorsnede van I met K[z]. Zij A de (p+q)×pq-matrix waarvan de kolommen gelabeld zijn door de variabelen zij en de rijen door de variabelen x1 , . . . , xp , y1 , . . . , yq en de kolom behorende bij zij precies twee enen heeft, in de rijen behorende bij xi en bij yj , en verder nullen. We zoeken een Markovbasis van A. Het is handig om A te interpreteren als de Z-lineaire afbeelding Zp×q → Zp × Zq die aan een p × qmatrix zijn p-tupel van rijsommen en zijn q-tupel van kolomsommen toevoegt. Zo bekeken is het eenvoudig elementen in de kern van A te vinden, zoals   0 1 0 −1 0 −1 0 1  = Eij + Ekl − Eil − Ekj 0 0 0 0 (voor p = 3, q = 4). We bewijzen nu dat de verzameling M = {Eij + Ekl − Eil − Ekj | i, k = 1, . . . , p; j, l = 1, . . . , q} een Markovbasis voor A is. Dit betekent dat als twee p × q matrices U en V met niet-negatieve geheeltallige entries dezelfde rij- en kolomsommen hebben, ze met elkaar kunnen worden verbonden door middel van een rij zetten uit M . Zolang U − V niet nul is, kies de lexicografisch kleinste entry (i, j) waar ze verschillen. Neem aan dat uij − vij > 0. Dan bestaan er k 6= i en l 6= j zo dat uil − vil < 0 en ukj − vkj < 0 en ukl − vkl > 0—waarom? Bewijs dit! Door nu bij V de matrix Eij + Ekl − Eil − Ekj ∈ M op te tellen blijf je binnen de matrices met niet-negatieve entries en lijkt het resultaat meer op U —hetzij de lexicografisch kleinste positie waar ze verschillen gaat omhoog, ofwel het verschil op die positie wordt kleiner. Na eindig veel zulke stappen is het resultaat U . Dit bewijst de volgende stelling. Stelling 3.1. Het ideaal I∩K[z] wordt voortgebracht door de 2×2-subdeterminanten van de matrix z.

3. RANG-1 MATRICES

23

Opgave 3.1. Reken met Singular een Markovbasis uit voor de Z-lineaire afbeelding die b =P (bijk ) van P aan eenP2 × 2 × 2-blok P PgetallenPeen rijtje van 6 getallen, te weten ( jk b1jk , jk b2jk , ik bi1k , ik bi2k , ij bij1 , ij bij2 ) toevoegt.

HOOFDSTUK 5

Dimensie Dit hoofdstuk is bijna uitsluitend gebaseerd op Hoofdstuk 9 van Ideals, Varieties, and Algorithms. 1. Monomiale idealen Laat I ⊆ K[x] = K[x1 , . . . , xn ] een monomiaal ideaal zijn, d.w.z. dat het voortgebracht wordt door (eindig veel) monomen xα met α ∈ Nn . Voor S ⊆ {1, . . . , n} defini¨eren we HS := {p ∈ K n | pi = 0 voor alle i ∈ S}; dit is een lineaire deelruimte van K n . Lemma 1.1. De vari¨eteit V (I) is de vereniging HS1 ∪ . . . ∪ HSk voor geschikte deelverzamelingen S1 , . . . , Sk ⊆ {1, . . . , n}. We mogen zelfs eisen dat Sa 6⊆ Sb voor alle a 6= b, en dan zijn de Sa op volgorde na uniek. We defini¨eren alvast dim V (I) als het maximum van de dimensies der HSa , dus als n − mina |Sa |. We zullen zien dat dit strookt met een algemenere definitie van dimensie verderop. Zij CI := {α ∈ Nn | xα 6∈ I}, en voor S ⊆ {1, . . . , n} schrijf NS voor de verzameling van alle α ∈ Nn met αi = 0 voor alle i 6∈ S. Lemma 1.2. De dimensie dim V (I), zoals hierboven gedefinieerd, is gelijk aan max{|S| | NS ⊆ CI }. Bewijs. Er geldt NS ⊆ CI als en alleen als HS c ⊆ V (I).



Lemma 1.3. De verzameling CI is een eindige disjuncte vereniging van verzamelingen van de vorm β + NS met β ∈ Nn en S ⊆ {1, . . . , n}. Bewijs. Schrijf I0 := I. We gaan een rij I0 ⊆ I1 ⊆ . . . ⊆ Ik = h1i van monomiale idealen construeren met de eigenschap dat CIa \ CIa+1 van de vorm β + NS is voor geschikte β ∈ Nn en S ⊆ {1, . . . , n}. Zolang Ia 6= h1i is, bekijk alle paren (β, S) met de eigenschap dat enerzijds β + NS ⊆ CIa en anderzijds 0 β + NS 6⊆ CIa voor alle S 0 ) S. Onder zulke paren kies een paar (β0 , S) met S minimaal. Dit impliceert dat voor alle γ ∈ Nn waarvoor β + γ in CI zit, de hele verzameling β +γ +NS in CI bevat is. Neem voor het gemak aan dat S = {1, . . . , l}. Als l 6= n, dan zij d ∈ N maximaal met de eigenschap dat β0 + del+1 ∈ CIa —zo’n d bestaat, want anders gold β0 + NS∪{l+1} ⊆ CI . Schrijf β1 := β0 + del+1 ; er geldt β1 + NS ⊆ CI maar β1 + el+1 6∈ CI . Ga zo door met de co¨ordinaten l + 2, . . . , n tot je een βn−l gevonden hebt waarvoor geldt dat βn−l + NS ⊆ CI maar βn−l + ei 6∈ CI voor alle i 6∈ S. Definieer Ia+1 als het ideaal dat door Ia en xβn−l voortgebracht 25

26

5. DIMENSIE

wordt. Er geldt CIa \ CIa+1 = βn−l + NS . Tenslotte volgt uit Hilberts Basisstelling dat de rij strict stijgende idealen I0 ( I1 ( . . . ergens moet ophouden, dus met Ik = h1i.  Stelling 1.1. Er bestaat een polynoom hI (T ) ∈ Q[T ] met de eigenschap dat X CI≤e := {α ∈ CI | αi ≤ e} i

voor e groot genoeg kardinaliteit hI (e) heeft. Dit polynoom is uniek (want het ligt voor oneindig veel waarden vast) en heet het (affiene) Hilbertpolynoom van I. Bewijs. Vanwege het voorgaande lemma hoef je alleen te bewijzen dat (β + NS )≤e P voor grote e polynomiaal in e is. En dat is zo, want als e ≥ i βi =: d is, dan is
het aantal punten in voorgaande verzameling gelijk aan |S|+(e−d) , een polynoom |S| van graad |S| in e.  Lemma 1.4. De dimensie van V (I), zoals hierboven gedefinieerd, is gelijk aan de graad van hI (T ). 2. Algemene idealen Zij nu I een ideaal in K[x1 , . . . , xn ] dat niet noodzakelijkerwijs monomiaal is. Stelling 2.1. Er bestaat een polynoom hI (T ) ∈ Q[T ] met de eigenschap dat voor alle groot genoege e ∈ N geldt: dim K[x]≤e − dim(K[x]≤e ∩ I) = hI (e), waarbij K[x]≤e de ruimte van alle polynomen van totale graad hooguit e is. Merk op dat als I monomiaal is, het in de vorige paragraaf gedefinieerde Hilbertpolynoom van I voldoet. Het bewijs van deze stelling geeft een algoritme om hI te vinden. Bewijsschets. Kies een mononomiale ordening die de graad respecteert, d.w.z. P P met de eigenschap dat xα < xβ als i αi < i βi . De ordening deglex voldoet daar bijvoorbeeld aan (maar de lexicografische ordening niet). Zij J het ideaal in K[x] dat door alle leidende monomen lm(f ), f ∈ I opgespannen wordt. We bewijzen dat voor alle e geldt dim(K[x]≤e ∩ I) = dim(K[x]≤e ∩ J). Laat namelijk m1 < . . . < mk de monomen van de vorm lm(f ) met f ∈ K[x]≤e ∩ I zijn. Kies f1 , . . . , fk ∈ K[x]≤e ∩ I met lm(fi ) = mi . Dan volgt eenvoudig dat f1 , . . . , fk een basis vormen van de ruimte K[x]≤e ∩ I. Anderzijds zijn m1 , . . . , mk een basis van de ruimte K[x]≤e ∩ J. Om dat in te zien, merk op dat deze laatste ruimte door monomen opgespannen wordt; zij m zo’n monoom. Per definitie van J is er een g ∈ I met lm(g) = m. In het bijzonder is de graad van lm(g) hooguit e, en omdat de monomiale ordening de graad respecteert hebben alle termen van g graad hooguit e. Dus g ∈ K[x]≤e ∩ I en lm(g) = m is gelijk aan zekere mi .

2. ALGEMENE IDEALEN

27

We concluderen dat het Hilbertpolynoom van J de gewenste eigenschap voor I heeft.  Definitie 2.1. De dimensie van een affiene vari¨eteit V ⊆ K n is per definitie de graad van het Hilbertpolynoom van I(V ). Opgave 2.2. Zij I voortgebracht door een enkel polynoom van graad d. Bepaal de leidende term (dus graad en co¨effici¨ent) van hI (T ). Opmerking 2.3. Als K algebraisch gesloten is en I ⊆ K[x] een ideaal is, dan is de graad van HI gelijk aan de graad van H√I , en dus gelijk aan dim V (I).