Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Matematika IV – 8. týden Systémy polynomiálních rovnic Jan Slovák Masarykova univerzita Fakulta informatiky 8. 4. – 12. 4. 2013 Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Obsah přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Plán přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Připomeňme induktivní definici polynomů r proměnných. Budeme v dalším pracovat nad tělesem K. K[x1, . . . , xr ] := K[x1, . . . , xr−1][xr ]. Např. K[x, y] = K[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem K[x]. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Připomeňme induktivní definici polynomů r proměnných. Budeme v dalším pracovat nad tělesem K. K[x1, . . . , xr ] := K[x1, . . . , xr−1][xr ]. Např. K[x, y] = K[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem K[x]. Zavedli jsem také tzv. podílová tělesa okruhů polynomů K[x1, . . . , xr ], kterým říkáme těleso racionálních funkcí a značíme je K(x1, . . . , xr ). Všechny algebraické operace s polynomy v softwarových systémech jako je Maple nebo Mathematica jsou prováděny ve skutečnosti nad podílovými tělesy, tj. v tělesech raciolnálních funkcí, zpravidla s použitím K = Q. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Polynomy v proměnných x1, . . . , xr lze i při této definici chápat jako výrazy vzniklé z písmen x1, . . . , xn a prvků okruhu K konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v K[x, y] jsou tvaru f = an(x)yn + an−1(x)yn−1 + · · · + a0(x) = (amnxm + · · · + a0n)yn + · · · + (bp0xp + · · · + b00) = c00 + c10x + c01y + c20x2 + c11xy + c02y2 + . . . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pro zjednodušení zápisu si zavedeme tzv. multiidexovou symboliku. Multiindexy Multiindex α délky r je r-tice nezáporných celých čísel (α1, . . . , αr ). Celé číslo |α| = α1 + · · · + αr nazýváme velikost multiindexu α. Stručně zapisujeme monomy xα místo xα1 1 xα2 2 . . . xαr r . Pro polynomy v r proměnných pak máme symbolické vyjádření velice podobné obvyklému značení pro polynomy v jedné proměnné: f = |α|≤n aαxα , g = |β|≤m aβxβ ∈ K[x1, . . . , xr ]. Říkáme, že f má celkový stupeň n, je-li alespoň jeden z koeficientů s multiindexem α velikosti n nenulový. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Okamžitě se také nabízejí analogické vzorce pro sčítání a násobení polynomů f + g = |α|≤max(m,n) (aα + bα)xα fg = m+n |γ|=0   α+β=γ (aαbβ)xγ   kde multiindexy se sčítají po složkách a formálně neexistující koeficienty považujeme za nulové. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Okamžitě se také nabízejí analogické vzorce pro sčítání a násobení polynomů f + g = |α|≤max(m,n) (aα + bα)xα fg = m+n |γ|=0   α+β=γ (aαbβ)xγ   kde multiindexy se sčítají po složkách a formálně neexistující koeficienty považujeme za nulové. Lemma Tyto vzorce opravdu popisují sčítání a násobení v induktivně definovaném okruhu polynomů v r proměnných. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Důkaz. Tvrzení lze snadno dokázat indukcí přes počet proměnných. Předpokládejme, že vztahy platí v K[x1, . . . , xr−1] a počítejme součet f = ak(x1, . . . , xr−1)xk r + · · · + a0(x1, . . . , xr−1) = α ak,αxα xk r + . . . g = bl (x1, . . . , xr−1)xl r + · · · + b0(x1, . . . , xr−1) =   β bl,βxβ   xk r + . . . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pokračování. f + g = a0(x1, . . . , xr−1) + b0(x1, . . . , xr−1) + + a1(x1, . . . , xr−1) + b1(x1, . . . , xr−1) xr + . . . = γ (ak,γ + bk,γ)(x1, . . . , xr−1)γ xk r + . . . + γ (a0,γ + b0,γ)(x1, . . . , xr−1)γ = (γ,j) (aj,γ + bj,γ)(x1, . . . , xr−1)γ xj r . Podobně lze vést důkaz pro součin (proveďte si samostatně!). Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pro jednoduchost (existence kořenů), budeme pracovat zejména nad polem komplexních čísel, nicméně úvahy některé uvedeme pro obecné pole K. Afinním n-rozměrným prostorem nad polem K rozumíme Kn = K × · · · × K n se standardní afinní strukturou, viz ??. Jak jsme již viděli, polynom f = α aαxα ∈ K[x1 . . . , xn] lze přirozeným způsobem chápat jako zobrazení f : Kn → Kn definované f (u1, . . . , un) := α aαuα kde uα = uα1 1 · · · uαn n Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pro jednoduchost (existence kořenů), budeme pracovat zejména nad polem komplexních čísel, nicméně úvahy některé uvedeme pro obecné pole K. Afinním n-rozměrným prostorem nad polem K rozumíme Kn = K × · · · × K n se standardní afinní strukturou, viz ??. Jak jsme již viděli, polynom f = α aαxα ∈ K[x1 . . . , xn] lze přirozeným způsobem chápat jako zobrazení f : Kn → Kn definované f (u1, . . . , un) := α aαuα kde uα = uα1 1 · · · uαn n V dimenzi n = 1 popisuje rovnost f (x) = 0 jen nejvýše konečně mnoho bodů v K. Ve vyšší dimenzi bude rovnost f (x1, . . . , xn) popisovat podmnožiny podobné, jako jsou křivky v rovině nebo plochy v trojrozměrném prostoru, mohou ale mít docela složité a samoprotínající se tvary. Např. množina zadaná rovnicí (x2 + y2)3 − 4x2y2 = 0 vypadá jako čtyřlístek. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pěkný obrázek dává také tzv. Whitneyho detník x2z − y2 = 0, který kromě znázorněné části na obrázku obsahuje také celou přímku {x = 0, y = 0}. Definition Nechť f1, . . . , fs ∈ K[x1, . . . , xn]. Afinní varietou v Kn určenou polynomy f1, . . . , fn nazveme množinu V(f1, . . . , fs) = (a1, . . . , an) ∈ Kn , fi (a1, . . . , an) = 0; i = 1, . . . , s Afinní variety jsou například všechny kuželosečky, kvadriky a nadkvadriky singulární i regulární. Mnoho pěkných křivek či ploch můžeme snadno popsat jako afinní variety. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Theorem Nechť V = V(f1, . . . , fs), W = V(g1, . . . , gt) ⊆ Kn jsou afinní variety. Potom i V ∪ W , V ∩ W jsou afinní variety a platí V ∩ W = V(f1, . . . , fs, g1, . . . , gt) V ∪ W = V(fi gj , pro všechny 1 ≤ i ≤ s, 1 ≤ j ≤ t) Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Plán přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pokusíme zodpovědět otázky, které se v souvislosti s varietami bezprostředně nabízejí. 1 Platí V(f1, . . . , fs) = ∅? 2 Je V(f1, . . . , fs) konečná množina? 3 Jak lze chápat pojem dimenze v případě variet? Tyto problémy lze „rozumně“ řešit pro variety v oboru komplexních čísel (resp. pro všechna algebraicky uzavřená pole), pro čísla reálná je to komplikovanější a velmi zlé to je pro obecná pole, tj. například racionální čísla. Takové rozhodnutí, zda V(xn + yn − zn) = ∅ nad racionálními čísly vede na velkou Fermatovu větu. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Různé systémy polynomiálních rovnic mohou snadno zadávat stejnou varietu. Budeme proto spolu s daným systémem rovnic chtít uvažovat i všechny důsledky rovnic. To vede na pojem ideálu: Definition Množinu I ⊆ K, kde K je komutativní okruh, nazveme ideálem, platí-li 0 ∈ I a zároveň f , g ∈ I =⇒ f + g ∈ I f ∈ I, h ∈ K =⇒ f · h ∈ I Ideály můžeme generovat podmnožinami, budeme používat značení I = a1, . . . , an . Tím máme na mysli I = i ai bi , bi ∈ K . Množina generátorů může být také nekonečná, je-li generátorů jen konečný počet, říkame, že ideál je konečně generovaný. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Pro varietu V = V(f1, . . . , fs) klademe I(V ) := f ∈ K[x1, . . . , xn], f (a1, . . . , an) = 0, ∀ (a1, . . . , an) ∈ V Theorem Nechť f1, . . . , fs, g1, . . . , gt ∈ k[x1, . . . , xn] jsou polynomy. Pak platí 1 Jestliže f1, . . . , fs = g1, . . . , gt , pak V(f1, . . . , fs) = V(g1, . . . , gt). 2 I(V ) je ideál a platí f1, . . . , fs ⊆ I(V ), kde V = V(f1, . . . , fs). Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Jednoduché příklady: I {(0, 0, . . . , 0)} = x1, . . . , xn I(Kn ) = { 0} pro libovolné nekonečné pole K Inkluze opačná k druhé části věty obecně neplatí. Například varieta V(x2, y2) má jediný bod – (0, 0). I(V ) je potom x, y ⊃ x2, y2 . Jsou-li V , W ⊆ kn variety, pak platí V ⊆ W =⇒ I(V ) ⊇ I(W ) Neboli polynomy, které se nulovaly na nějaké varietě se nutně musí nulovat i na její podmnožině. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Můžeme formulovat další přirozené problémy 1 Je každý ideál I ∈ K[x1, . . . , xn] konečně generovaný? 2 Lze algoritmicky zjistit, zda f ∈ f1, . . . , fs ? 3 Jaký je přesný vztah mezi f1, . . . , fs a I V(f1, . . . , fs) ? Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Plán přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Podívejme se na polynomy v jedné proměnné x f = a0xn + a1xn−1 + · · · + an kde a0 = 0. Vedoucí člen polynomu (leading term) definujeme jako LT(f ) := a0xn. Zřejmě platí deg f ≤ deg g ⇐⇒ LT(f )|LT(g) Nechť K je pole a g nenulový polynom. Již jsme viděli, že každé f ∈ K[x] lze jednoznačně psát jako f = q · g + r kde r = 0 nebo deg r < deg g Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Jde ve skutečnosti o algoritmický postup, podíl q a zbytek r počítá následující algoritmus. 1 q := 0, r := f 2 while r = 0 ∧ LT(g)|LT(r) 1 q := q + LT(r)/LT(g) 2 r := r − LT(r)/LT(g) · g Pro průchod cyklem platí invariant f = q · g + r, algoritmus tedy dává správný výsledek. Stupeň r se každým průchodem zmenšuje, algoritmus tedy zastaví. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Připusťme, že existují ještě jiná q , r tak, že f = q · g + r . Protože stupně r a r jsou ostře menší než stupeň g, musí platit i deg(r − r ) < deg g (protože r = r , má smysl uvažovat deg(r − r )). Zároveň ale platí deg(r − r ) = deg(q − q ) + deg g ≥ deg g což je spor. Dvojice q, r je tedy určena jednoznačně. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Corollary Nechť K je pole. Pak každý ideál v K[x] je tvaru f . Definition Nechť f , g ∈ k[x]. Největším společným dělitelem polynomů f , g, značíme GCD(f , g), nazveme takový polynom h, že h|f , h|g a platí ∀p ∈ k[x]: p|f ∧ p|g =⇒ p|h Největšího společného dělitele lze pochopitelně spočítat 1 h := f , s := g 2 while s = 0 1 r := zbytek po dělění h/s 2 h := s 3 s := r Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Nechť f = q · g + r a h = GCD(f , g). Potom h|r, g a zároveň ∀p ∈ k[x]: p|r, g tedy p|f a p|h Odtud h je GCD(r, g). Triviálně GCD(h, 0) = h, proto algoritmus počítá správně GCD(f , g). Protože stupně r postupně klesají, algoritmus zastaví. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Největší společný dělitel dvou polynomů tedy existuje. Je určen jednoznačně až na násobek skalárem. Dva různé GCD se totiž musí dělit navzájem a to je u polynomů možné právě v tomto případě. Definujme největšího společného dělitele více než dvou polynomů. Je-li s > 2, potom GCD(f1, . . . , fs) := GCD f1, GCD(f2, . . . , fs) Theorem Pro polynomy f1, . . . , fs platí GCD(f1, . . . , fs) = f1, . . . , fs . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Položili jsme několik otázek. Tady jsou odpovědi pro dimenzi 1: 1 Protože V(f1, . . . , fs) = V(GCD(f1, . . . , fs)), problém prázdnosti variety se redukuje na problém existence kořene polynomu. 2 Ze stejného důvodu je vždy konečnou množinou izolovaných bodů – kořenů GCD(f1, . . . , fs) s jedinou vyjímkou GCD(f1, . . . , fs) = 0; to nastane pouze v případě, že f1 = f2 = · · · = fs = 0. Pak je varietou celá množina k. 3 Pojem dimenze v tomto případě postrádá smysl. 4 Každý ideál je generovatelný jediným polynomem. 5 f ∈ f1, . . . , fs ⇐⇒ GCD(f1, . . . , fs)|f . 6 Označíme-li f := I(V(f1, . . . , fs)), pak f a GCD(f1, . . . , fs) se mohou lišit pouze násobností kořenů. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Plán přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Zadat varietu v prostoru pomocí dvou polynomů znamená zadat průnik obecně i dost komplikovaných útvarů. Např. V(x2 + y2 + z2 − 1, x2 + y2 + z) je kružnice ležící v rovině z = 1 2 − 1 2 √ 5. Jistě proto tutéž varietu zadáme jako V(x2 + y2 + z2 − 1, z2 − z − 1), případně V(x2 + y2 + z, z − 1 2 + 1 2 √ 5) a podobně. Bude proto lepší varietu reprezentovat generujícím ideálem a pro ten nalézt vyjádření nezávislé na volbě generátorů. To skutečně budeme umět a navíc algoritmicky! Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Nejprve najdeme pořádný ekvivalent pojmu stupeň polynomu pro případ více proměnných, tak abychom vůbec mohli mluvit o vedoucím členu polynomu. Dělením se zbytkem polynomu f ∈ K[x1, . . . , xn] polynomy g1, . . . , gs budeme rozumět vyjádření f = a1g1 + · · · + asgs + r, kde vžádný člen zbytku r nebude dělitelný některým z vedoucích členů LT gi . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Například f = x2y + xy2 + y2, g1 = xy − 1 a g2 = y2 − 1. Prvním dělením získáme f = (x + y) · g1 + (x + y2 + y) LT(y2 − 1) nedělí x (vedoucí člen zbytku), a tak bychom teoreticky nemohli pokračovat dál. Přesuneme-li však toto x do zbytku, dostáváme teprve výsledek f = (x + y) · g1 + g2 + (x + y + 1) Zde již žádný člen zbytku není dělitelný žádným z LT(g1), LT(g2). Jak jsme ale vlastně určovali vedoucí členy? Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Úplné (lineární) dobré (tj. každá neprázdná podmnožina má nejmenší prvek) uspořádání < na Nn splňující ∀α, β, γ ∈ Zn : α < β =⇒ α + γ < β + γ nazveme monomiálním uspořádáním na K[x1, . . . , xn]. Uspořádání na Nn indukuje uspořádání na monomech. Každý polynom lze však přeskládat jako klesající posloupnost monomů (na koeficienty teď nehledíme). Uspořádání se na polynomy rozšíříme „lexikograficky“, tedy větší je ten polynom, který má větší první monom, pokud tak nelze rozhodnou, bere se v potaz druhý monom atd. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Úplné (lineární) dobré (tj. každá neprázdná podmnožina má nejmenší prvek) uspořádání < na Nn splňující ∀α, β, γ ∈ Zn : α < β =⇒ α + γ < β + γ nazveme monomiálním uspořádáním na K[x1, . . . , xn]. Uspořádání na Nn indukuje uspořádání na monomech. Každý polynom lze však přeskládat jako klesající posloupnost monomů (na koeficienty teď nehledíme). Uspořádání se na polynomy rozšíříme „lexikograficky“, tedy větší je ten polynom, který má větší první monom, pokud tak nelze rozhodnou, bere se v potaz druhý monom atd. Následující tři definice zavádějí nejběžněji užívaná monomiální uspořádání. Všechna se opírají o předem dané uspořádání jednotlivých proměnných, standardně x1 > x2 > · · · . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Lexikografické uspořádání je takové lex β ⇐⇒ Nejlevější nenulový člen v α − β je kladný Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Lexikografické uspořádání je takové lex β ⇐⇒ Nejlevější nenulový člen v α − β je kladný Gradované lexikografické uspořádání je takové grlex β ⇐⇒ |α| > |β| nebo |α| = |β| a zároveň α >lex β Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Lexikografické uspořádání je takové lex β ⇐⇒ Nejlevější nenulový člen v α − β je kladný Gradované lexikografické uspořádání je takové grlex β ⇐⇒ |α| > |β| nebo |α| = |β| a zároveň α >lex β Gradované opačné lexikografické uspořádání je takové grevlex β ⇐⇒ |α| > |β| nebo |α| = |β| a zároveň nejpravější nenulový člen (α − β) je záporný Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Tedy x1 >grevlex x2 >grevlex · · · >grevlex xn, ale pokud x > y > z, pak x2yz2 >grlex xy3z, ale x2yz2 lex, >grlex, >grevlex jsou monomiální uspořádání. Definition Nechť f = α∈N n 0 aαxα ∈ k[x1, . . . , xn] je nenulový a < monomiální. Pak definujeme: Stupeň multideg f := max{α ∈ Nn, aα = 0} Vedoucí koeficient LC f := amultideg f Vedoucí monom LM f := xmultideg f Vedoucí člen LT f := LC f · LM f Tyto pojmy jsou tedy pro polynomy více proměnných vesměs silně závislé na volbě konkrétního uspořádání. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Lemma Nechť f , g ∈ k[x1, . . . , xn] a < je monomiální. Pak 1 multideg(f · g) = multideg f + multideg g 2 f +g = 0 =⇒ multideg(f +g) ≤ max{multideg f , multideg g} Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Theorem (Dělení se zbytkem) Nechť < je monomiální a F = (f1, . . . , fs) s-tice polynomů v K[x1, . . . , xn]. Pak každý f ∈ K[x1, . . . , xn] lze vyjádřit jako f = a1f1+· · ·+asfs+r kde ai , r ∈ K[x1, . . . , xn] pro i = 1, 2, . . . , s a navíc r = 0 nebo r je lineární kombinací monomů, z nichž žádný není dělitelný kterýmkoli z LT f1, . . . , LT fs a pokud ai fi = 0 pak multideg f ≥ multideg ai fi pro každé i. Polynom r nazýváme zbytkem po dělení f /F. Věta neříká nic o jednoznačnosti výsledku. Následující algoritmus dává jedno možné řešení. Nadále budeme výsledkem dělení se zbytkem chápat právě tento výstup pevně zvoleného algoritmu. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta 1 a1 := 0, . . . , as := 0, r := 0, p := f 2 while p = 0 1 i := 1 2 d := false 3 while i ≤ s ∧ not d 1 if LT fi |LT p ai := ai + LT p/LT fi p := p − (LT p/LT fi ) · fi d := true 2 else i := i + 1 4 if not d 1 r := r + LT p 2 p := p − LT p Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Diskuse správnosti algoritmu Při každém průchodu vnějším cyklem se právě jednou provede právě jeden z příkazů 1, 2, a tedy stupeň p klesne. Proto algoritmus skončí. Platí invariant f = a1f1 + · · · + p + r a přitom každý člen každého ai je podílem LT p/LT fi z nějakého okamžiku. Proto stupeň těchto členů je menší než stupeň p v daném okamžiku a ten je nejvýše roven stupni f . Dohromady stupeň každého ai fi je menší nebo roven stupni f . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta V K[x1, . . . , xn] platí pouze implikace f = a1f1 + · · · + asfs + 0 =⇒ f ∈ f1, . . . , fs Obrácení obecně neplatí, uvažujme f = xy2 − x, f1 = xy + 1, f2 = y2 − 1. Potom algoritmus dělení dá f = y(xy + 1) + 0(y2 − 1) + (−x − y) ale přitom evidentně f = x(y2 − 1), a tedy f ∈ f1, f2 . Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Plán přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Ideál I ⊆ k[x1, . . . , xn] nazýváme monomiální, existuje-li množina A ⊆ Nn taková, že I se sestává právě ze všech polynomů tvaru α∈A hαxα, kde hα ∈ k[x1, . . . , xn]. Potom píšeme I = xα, α ∈ A . Zřejmě pro monomiální ideál I platí xβ ∈ I ⇐⇒ ∃α ∈ A: xα |xβ Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Lemma Nechť I ⊆ k[x1, . . . , xn] je monomiální ideál, f ∈ k[x1, . . . , xn] polynom. Pak následující tvrzení jsou ekvivalentní 1 f ∈ I 2 Každý člen polynomu f je prvkem I. 3 Polynom f je lineární kombinací monomů z I s koeficienty z k. Důkaz. Implikace (3) =⇒ (2) =⇒ (1) je triviální. Zbývá ukázat (1) =⇒ (3). Platí f = α aαxα ∈ I, kde aα ∈ k. Z předpokladu vyplývá, že lze vyjádřit f = β∈A hβxβ, kde hβ ∈ k[x1, . . . , xn]. Každý člen aαxα se musí rovnat některému členu z druhé rovnosti, tedy existují taková d ∈ k, δ ∈ Nn tak, že aαxα = dxβ+δ. Proto xα ∈ I, a tedy platí (3). Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Corollary Dva monomiální ideály splývají právě tehdy, když obsahují stejné monomy. Theorem (Dicksonovo lemma) Každý monomiální ideál I = xα, α ∈ A ⊆ k[x1, . . . , xn] lze psát ve tvaru I = xα1 , . . . , xαs , kde α1, . . . , αs ∈ A. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Plán přednášky 1 Polynomy více proměnných 2 Variety a ideály 3 Dimenze 1 4 Dělení se zbytkem 5 Monomiální ideály 6 Hilbertova věta Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Je-li I ⊆ K[x1, . . . , xn] nenulový, označme LT I := {axα , ∃f ∈ I : LT f = axα } Zřejmě LT I je monomiální, a tedy podle Dicksonova lemmatu lze psát LT I = LT g1, . . . , LT gs pro nějaká vhodná g1, . . . , gs ∈ I. Theorem (Hilbertova věta) Každý ideál I ∈ K[x1, . . . , xn] je konečně generovaný. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Důkaz. Pokud by I = {0}, je tvrzení triviální. Uvažujme tedy I ⊃ {0}. Podle Dicksonova lematu a předchozí poznámky existují taková g1, . . . , gs ∈ I, že LT I = LT g1, . . . , LT gs Zřejmě g1, . . . , gs ⊆ I. Vezměme libovolné f ∈ I a proveďme dělení se zbytkem s-ticí g1, . . . , gs. Dostáváme f = a1g1 + · · · + asgs + r kde žádný člen r není dělitelný LT g1, . . . , LT gs. Protože r = f − a1g1 − · · · − asgs, platí r ∈ I, a tedy LT r ∈ LT I. Zřejmě tedy LT r ∈ LT I . Připusťme, že r = 0. Protože LT I je monomiální, musí být LT r dělitelný některým z jeho generátorů, tj. LT g1, . . . , LT gs. To je ovšem spor s výsledkem algoritmu dělení. Proto r = 0 a I je tedy generovaný g1, . . . , gs. Polynomy více proměnných Variety a ideály Dimenze 1 Dělení se zbytkem Monomiální ideály Hilbertova věta Definition Konečná báze g1, . . . , gs ideálu I ⊆ k[x1, . . . , xn] se nazývá Gröbnerova, jestliže platí LT I = LT g1, . . . , LT gs . Báze použitá v důkazu Hilbertovy věty byla Gröbnerova.