Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Grobnerovy báze ooo oooooooooooo ooooooooooo oooo OOOOOOOOOOOO Diskrétní matematika B - 10. (zkrácený) týden Systémy polynomiálních rovnic Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo oooooooooooo Ql Polynomy více proměnných • Těleso racionálních funkcí Q Variety a ideály • Dimenze 1 Dělení se zbytkem Ql Monomiální ideály a Hilbertova věta • Hilbertova věta (Hilbert basis theorem) Q Gróbnerovy báze a eliminace proměnných Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo oooooooooooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). Naší snahou nyní bude zobecnit způsob konstrukce racionálních čísel jakožto zlomků čísel celých. Nechť R je obor integrity. Jeho podílové těleso (Field of fractions) definujeme jako třídy ekvivalence dvojic (a, b) £ R x R, b ^ 0, které zapisujeme |, a ekvivalence je dána vztahem 3- = Í- & ab' = a'b. b b' Sčítání a násobení definujeme prostřednictvím reprezentantů tříd a c ad + bc ~b + ~ď~ bd a c ac ~bd~~bď Snadno se ověří korektnost této definice a všechny axiomy tělesa. Zejména je j neutrální prvek vzhledem ke sčítání, j je neutrální prvek vzhledem k násobení a pro a ^ 0, b ^ 0 je = \. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze o«o oooooooooooo ooooooooooo oooo oooooooooooo Touto konstrukcí „přidáme" k okruhu R minimální množství prvků tak, abychom již mohli dělit libovolnými nenulovými prvky. Příklad Podílové těleso okruhu R[xi,... ,xr] nazýváme těleso racionálních funkcí a značíme je R(xi,... ,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 racionálních funkcí, zpravidla s použitím R = Q. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze oo» oooooooooooo ooooooooooo oooo oooooooooooo Připomeňme tzv. multiidexovou symboliku. Multiindexy Multiindex a délky r je r-tice nezáporných celých čísel («1,..., ar). Celé číslo \a\ = a\ + • • • + ar nazýváme velikost multiindexu a. Stručně zapisujeme monomy xa místo x^x^2 .. .xfr. 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 = ^2 3axa, g = ^2 aPx^ G KtXl' • • • 'Xrl- M<" \P\• f + gel f e l,heK =^ f- h e I Ideály můžeme generovat podmnožinami, budeme používat značení / = (ai,..., an). Tím máme na mysli / = {^a;/)/, b; G /?}. i Množina generátorů může být také nekonečná, je-li generátorů jen konečný počet, říkáme, že ideál je konečně generovaný. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo ooooooo«oooo ooooooooooo oooo oooooooooooo Pro varietu V = 23(/"i,..., fs) klademe 3{V) := {f gK[xi,...,x„], f{ai,...,an) = 0, V(ai,...,a„) g V} Věta Nechť fi,..., fs, gi,..., gt g K[xi,..., x„] jsou polynomy. Pak platí O Jestliže (fi,..., fs) = (gi,..., gř), pa/c 23(f1,...,fs) = 23(g1,...,gř)-O 3(23(fi, • • •, 4)) 7'e «fea7 a p/at/' (/"i,..., fs) C J(Q3(fi,..., £)). Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooo»ooo ooooooooooo oooo oooooooooooo Příklad Jednoduché příklady: J({(0,0,...,0)}) = z - 2 + 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! Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo o»ooooooooo oooo oooooooooooo 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. Definice Dělením se zbytkem polynomu f £ K[xi,... ,x„] polynomy Sii ■ ■ ■ > Ss Pak budeme rozumět vyjádření f = 3iSi H-----h asgs + r, kde žádný člen zbytku r nebude dělitelný některým z vedoucích členů LTg,. Literatura Racioná ní funkce Variety a ideály Dělení se zbytkem Hilbertova věta Grobnerovy báze ooo oooooooooooo oo»oooooooo oooo OOOOOOOOOOOO Příklad Například f = x2 y + xy2 + y2, gi = xy — 1 a g2 = y2 — 1 (předpokládejme na chvíli, že členy polynomů máme uspořádány). Prvním dělením získáme f = {x + y)- gi + {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) • gi + g2 + {x + y +1) Zde již žádný člen zbytku není dělitelný žádným z LT(gi), LT(g2). Jak jsme ale vlastně určovali vedoucí členy? Literatura Racioná ní funkce Variety a ideály Dělení se zbytkem Hilbertova věta Grobnerovy báze ooo oooooooooooo ooo»ooooooo oooo OOOOOOOOOOOO Definice Úplné (lineární) dobré (tj. každá neprázdná podmnožina má nej menší prvek) uspořádání < na N" splňující Va, /3,7 G Z": a < /3 =>- a + 7 < /3 + 7 nazveme monomiálním uspořádáním na K[xi,... ,xn]. Uspořádání na N" 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í na polynomy rozšíříme „lexikograficky", tedy větší je ten polynom, který má větší první monom, pokud tak nelze rozhodnout, 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ě xi > x? > • • •. Literatura Racioná ní funkce Variety a ideály Dělení se zbytkem Hilbertova věta Grobnerovy báze ooo OOOOOOOOOOOO oooo»oooooo oooo OOOOOOOOOOOO Definice Lexikografické uspořádání <\ex je takové, že pro každé a,/3 G N" platí a >iex P Nejlevější nenulový člen v a — (3 je kladný Gradované lexikografické uspořádání griex /3 <í=>- \a\ > \/3\ nebo \a\ = \(3\ a zároveň a >|ex /3 Gradované opačné lexikografické uspořádání greviex /3 -^=>- H > |/3| nebo \a\ = \(3\ a zároveň nejpravější nenulový člen (a — (3) je záporný Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooo»ooooo oooo oooooooooooo Tedy X1 >grevlex *2 >grevlex • • • >grevlex xn, ale pokud X > y > Z, pak x2yz2 >gr|ex xy3z, ale x2yz2 /ex) >griex, >grevlex Jsou monomiální uspořádání. Definice Nechť f = Y,aen"0 a^a £ • • • ,x„] je nenulový a < monomiální. Pak definujeme: • Stupeň multidegf := max{a G N", aa 7^0} • Vedoucí koeficient Z. C ŕ := Smuitidegf » Vedoucí monom LM f := xmultidesf • Vedoucí člen LT f := /.C 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í. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze OOO OOOOOOOOOOOO 000000*0000 oooo oooooooooooo Lemma "* Nechť f,ge K[xi,. .., xn\ a < je monomiální. Pak Q multideg(/r-g) = multideg f + multidegg & f+g £ o =^ multideg(f+g) < maxjmultideg f, multideg g} Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooo»ooo oooo oooooooooooo Věta (Dělení se zbytkem) Necht < je monomiálnía F = (fi,... ,fs) s-tice polynomů v K[xi,..., xn\. Pak každý f G K[xi,..., xn\ lze vyjádřit jako f = a\f\A-----\-asfs+r kde a,-, r G K[xi,...,x„] pro / = 1, 2,...,« a navíc r = 0 nebo r je lineární kombinací monomů, z nichž žádný není dělitelný kterýmkoli z LT fi,..., LT fs a pokud a;f; ^ 0 pak multidegf > multideg a;f, 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. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo oooooooo^oo oooo oooooooooooo O ai := 0,..., as : = 0, r := 0, p := f O while p/0 O / := 1 © g/ := fa/se 0 while i < s A not c/ O if LT f,\LTp a; := ai + LTp/LTfi P:=p-(LTP/LTfi)-f, (1) c/ := true © else / := / + 1 O if notcř O r := r + LTp 0 p:=p-LTp (2) Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze OOO OOOOOOOOOOOO OOOOOOOOO0O oooo oooooooooooo 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 stupeň p tedy klesne. Proto algoritmus skončí. Platí invariant f = a\f\ + • • • + p + r a přitom každý člen každého a,-je podílem LTp/LTf, 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 a,/)- je menší nebo roven stupni f. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Grobnerovy báze OOO OOOOOOOOOOOO 0000000000» oooo oooooooooooo V K[xi,... ,x„] obecně platí pouze implikace f = 3ifi + • • • + asfs + O =>• f G (ŕi,..., fs). Příklad Obrácení obecně neplatí, uvažujme f = xy2 — x, f\ = xy + 1, Í2 = 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 G (fi, /š)- Naší snahou bude tento deficit napravit - zavedeme tzv. Grobnerovy báze. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo »ooo oooooooooooo Definice Ideál / c K[xi,... , x„] nazýváme monomiální, existuje-li množina A c N" taková, že / se sestává právě ze všech polynomů tvaru J2aeA ha*01, kde ha g K[xi,..., x„]. Potom píšeme / = (xa, a g A). Zřejmě pro monomiální ideál / platí x? g / Ba g A: xa\x? Příklad monomiálního ideálu / = (x3y,x2y4): cbo • • • • • cbo • • • • • cbo • • • • • 9 o o • • • • cbo o • • • • gt} je Gróbnerova báze ideálu 1 C K[xi,. ■,xn] a f je polynom v K[xi,..., xn\. Pak platí f G / <í=^> zbytek po dělení f / G je nulový Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze OOO OOOOOOOOOOOO OOOOOOOOOOO OOOO 00*000000000 Pro a = multideg f a (3 multidegg uvažme 7 := (7i) • • • ,7n) kde 7/ = max{a/,/3/} Monom x7 nazýváme nejmenším společným násobkem (least common multiple) monomů LM f a LM g a zavádíme označení LCM(LMf, LMg) :=x7. Výraz nazýváme S-polynomem (nebo také syzygy, neboli spřežení) polynomů f, g. Jedná se o nástroj k eliminaci vedoucích členů, Gaussova eliminace je speciálním případem tohoto postupu pro stupeň 1. Narozdíl od ní ale může dojít ke zvýšení stupně, i když původní vedoucí členy odstraní. S(f,g): LTf f LTg ■g Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo ooo»oooooooo Věta Nechi I C K[xi,..., xn] je ideál. Pak jeho báze G = {gj,..., gt} je Gróbnerova právě tehdy, když pro každé i ^ j je zbytek po dělení S(gi,gj)/G nulový. Věta poskytuje účinný prostředek pro zjištění, zda nějaká báze je Gróbnerova. Příklad Uvažujme například / = (x + y,y — z). Jediný S-polynom, který připadá v úvahu je xy xy 2 5{x + y,y - z) = —(x + y)--(y - z) =xz+y x y Dělením získáme xz + y2 = z(x + y) + y(y — z), a tedy daná báze je Gróbnerova. Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo oooooooooooo Naivní algoritmus pro Gróbnerovy báze Gróbnerovy báze zavedl v roce 1965 Bruno Buchberger ve své Ph.D. disertaci, po němž je rovněž pojmenován algoritmus na jejich výpočet. Dnes existují další algoritmy, mezi nejznámější patří Faugěreho algoritmy známé pod názvem F4 a F5. O G:=F, G' := 0 & while G/G' O G' :— G Q Vp, q G G1: p ^ q do Q s : = S(p,q)G @ if s / 0 G := G U {s} Tento algoritmus ovšem není zdaleka ideální. Lze vymyslet velmi jednoduše vypadající vstupy, pro něž vrací divoké výsledky. Dále výstupní báze se přímo odvíjí od vstupní, a tedy pro tentýž ideál zadaný různými bázemi dá také různé výsledky. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo ooooo»oooooo Lemma Nechť G je Gróbnerova báze ideálu I a p G G takový, že LT p^ (LT(G - {p})). Pak G - {p} je také Gróbnerova báze I. Důkaz. Z definice Gróbnerovy báze platí (LTI) = (LTG). Protože LTp G (LT(G - {p})), platí (LT(G - {p})) = (LT G). Odsud již plyne tvrzení. □ Definice Minimální Gróbnerovou bází ideálu / je taková Gróbnerova báze G, že pro všechna p G G platí LCp = 1 a zároveň LTp i (LT(G - {p})> Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo oooooo»ooooo Příklad Například mějme C[x,y] a - {g})) (tj. g není redukovaný pro G'). Potom m = a\ LTg[ + • • • + atLTg[ pro nějaké vhodné polynomy 3i,..., at. Protože G i G' jsou Gróbnerovy báze téhož ideálu, platí (LTG) = (LT G'), a tedy každé LTg\ lze vyjádřit jako kombinaci LTgi,..., LTgs. Odtud už plyne m G (LT G) a protože je G' minimální, je m G (LT(G \ {g})}, což je spor s předpokládanou red u kován ostí g pro G. □ Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo OOOO 000000000*00 Věta Necht I c /c[xi,... ,x„] je nenulový. Pak pro každé monomiální uspořádání existuje právě jedna redukovaná Gróbnerova báze ideálu I. Navíc každou Gróbnerovu bázi lze algoritmicky redukovat. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo oooo oooooooooo^o Na závěr si uveďme alespoň jednu aplikaci. Budeme považovat okruh K[xp+i,... , x„] za podokruh K[xi,... , x„]. Jedná se o polynomy, v nichž se nevyskytují proměnné xi,... ,xp. Je to skutečně podokruh, ale už ne ideál. Definice Nechť / = (fi,..., fs) c K[xi,... , x„]. Pro p = 0,..., n definujeme lp := I nK[xp+i,... ,x„] Tuto množinu nazveme p-tým eliminačním ideálem. Sa mozřejmě lp je ideálem pouze v K[xp+i,... ,x„]. Literatura Racionální funkce Variety a ideály Dělení se zbytkem Hilbertova věta Gróbnerovy báze ooo oooooooooooo ooooooooooo OOOO 00000000000» Na úrovni polynomiálních rovnic lp obsahuje všechny rovnice, které jsou důsledky systému f\ = O,..., fs = O a v kterých vystupují pouze proměnné xp+i,... ,xn. Věta (Eliminační věta) Nechi I c K[xi,..., xn] je ideál, G = {gi,..., gm} jeho Gróbnerova báze vzhledem k \ex xi >/ex • • • ■ Potom pro každé p = O,..., n je Gp := G n K[xp_|_i,... ,x„] Gróbnerovou bází ideálu lp.