1. Polynomy více proměnných, Grobnerova báze 1.1. Monomiální uspořádání. Jaké je lexikografické a gradované lexikografické uspořádání monomů polynomu / — 4xy2 z+4z2—5x3+7x2 z2 s uspořádáním proměnných x > y > zl Určete LM(f), LC(f) a LT(f). Řešení. V lexikografickém uspořádání sledujeme prvně stupeň největší proměnné, tj. x. Potom stupeň y, pak z. Proto x3 >iex x2z2 >iex xy2z >iex z2. Vedoucí monom, koeficient a člen jsou po řadě LM(f) — x3, LC(f) — —5 a LT(f) — — 5x3. Při gradovaném uspořádání se díváme nejprve na součet stupňů všech proměnných. Je-li stejný, pak pokračujeme jako v lex, tj. x2z2 >griex xy2z >griex x3 >griex z2, a proto LM(f) = x2z2, LC(f) = 7 a LT(f) = 7x2z2. 1.2. Dělení se zbytkem. Vydělte polynom / — xy2 + 1 polynomem fi — xy + 1 a polynomem f2 — y + 1 (uvažujte obvyklé lexikografické uspořádání). Řešení. Narozdíl od číselných okruhů nám algoritmus dělení se zbytkem v okruhu polynomů nedává obecně jednoznačný výsledek. Budeme nejprve dělit f / fi. Stejně jako přidělení polynomů jedné proměnné dělíme vedoucí členy LT(f) / LT(f{) — y a přičteme zbytek, tj. f — yfi — y + 1. Protože vedoucí člen zbytku y není dělitelný LT(fi), je algoritmus u konce. Pokračujeme ale dělením polynomem /2 a dostaneme LT(í-y)/LT(f2) = -1, a proto celkem / = y(xy+í) + (-í)(y + í) + 2. Pokud budeme dělit napřed polynomem /2, pak dostaneme LT(f) / LT(f2) — xy, konkrétně / — xyf2 — xy + 1. Můžeme dělit dál LT(-xy)/LT(/2) — —x ~> / — {xy — 2ľ)/2 + x + 1. Dále už nemůžeme dělit ani jedním z polynomů /1; /2. 1.3. Ideál, algebraická varieta, Grobnerova báze. Najděte Grôbnerovu bázi ideálu generovaného polynomy /1 — x3 — 2xy, f2 — x2y + x — 2y2 a určete příslušnou algebraickou varietu v M2. Řešení. Ideál je toren všemi polynomiálními kombinacemi polynomů /1; /2, tj. I = {h,h) = {/ e : / = ai/i + a2/2 ;ai,a2 G K[a;,y]}- Není úplně jednoduché rozhodnout, zda jsou dva ideály totožné nebo také, zda daný polynom / leží v /. Víme sice, že pokud dá algoritmus dělení se zbytkem polynomu / polynomy /1, /2 zbytek nula, pak f E I. Pokud je ale nenulový, pak můžeme usoudit / e / jen pokud /1 a /2 splňují LM(I) — (LM(fi), LM(/2)) (je třeba si rozmyslet). Taková báze ideálu / se nazývá Grobnerova a vždy existuje. V našem případě je LM(fi) — x3 a LM(/2) — x2y. Zároveň ale vidíme, že tzv. S-polynom 3 2 3 2 2 2 yfi — XJ2 — yx — 2xy — x y — x + 2y x — —x G /, ale x2 ^ (x3,x2y). Báze /1, /2 tedy není Grobnerova - "chybí tam x2". Algoritmus nalezení Grôbnerovy báze spočívá právě v přidávání těchto "chybějících" S-polynomů ke stávající bázi a její následné redukování. V našem případě tedy máme (/1, /2, x2). Redukování není nic jiného než vzájemné dělení se zbytkem těchto bázových polynomů tak, aby vedoucí členy byly vzájemně nesoudělné. Můžeme dělit následovně: /1 — x3 — 2xy — x ■ x2 — 2xy, f2 — V'X2+x — 2y2. Máme tak novou bázi / — (xy, x — 2y2, x2). Můžeme ovšem dělit dál: xy = y(x - 2y2) + 2y3, x2 = x(x - 2y2) + 2xy2 = (x + 2y2)(x - 2y2) + 4y4. Dostáváme tak bázi I — (x — 2y2,y3,y4), kterou ovšem můžeme zredukovat na I — (x — 2y2,y3). Tato báze už je Grobnerova, protože jediný S-polynom, který můžeme vytvořit je y3(x — 2y2) —xy3 — —2y5 a ten je dělitelný bázovým polynomem y3. Tím se nám algoritmus nalezení báze zastavil. 1 2 Výhodou Grôbnerovy báze je, že pomůže nalézt algebraickou varietu V{I). tj. body v (x,y) G M2, pro které je fi — fy — 0 - jinými slovy řešení těchto dvou polynomiálních rovnic. Pro Grôbnerovu bázi totiž příslušné bázové polynomy mají separované proměnné. Místo původních polynomiálních rovnic fy — fy — 0 máme ekvivalentní soustavu rovnic x — 2y2 — 0 a y 3 — 0, kterou vyřešíme zpětnou eliminací. V našem případě je vidět, že vyhovuje jediný bod, V{I) — (0, 0). 1.4. Vyřešte soustavu polynomiálních rovnic x2 + y + z — 1, x + y2 + z — 1, x + y + z2 — 1. Řešení. Nalezneme Grôbnerovu bázi vzhledem k lexikografickému uspořádání s x > y > z. Vedoucí monomy polynomů nejsou nesoudělné, a proto můžeme dělit a tím redukovat bázi. Zafixujme například /1 :— x + y + z2 — 1 a dělme tímto polynomem zbylé dva. Dostáváme x + y2 + z -1 = fi+y2 - y - z2 + z a x2 + y + z- l = (x-y-z2 + l)/i + y2 + 2yz2 - y + z4 - 2z2 + z. První zbytek označme j\. Druhý zbytek můžeme dělit prvním a dostaneme y2 + 2yz2 - y + z4-2z2 + z = f2 + 2yz2 + z4 - z2. Tento zbytek označme fy. Nyní už máme redukovanou bázi (fi, h, h) = (x + y + z2 - 1, y2 - y - z2 + z, 2yz2 + z4 - z2}. Na řadu přichází vytvoření S-polynomu 2z2f2 - y h = -V^ - y z2 - 2z4 + 2z\ Tento polynom (nebo raději jeho dvojnásobek) vydělíme polynomem fy: -2yz4 - 2yz2 - 4z4 + 4z3 = -(z2 + l)/3 + z6 - 4z4 + 4z3 - z2 Do naší báze přidáme tento zbytek f4 :— z6 — 4z4 + 4z3 — z2 a tím už dostaneme bázi /2, fy, fy) s eliminovanými proměnnými. Daň, kterou platíme za vyloučení proměnných je, že polynom fy je sice o jedné neznámé (eliminační ideál), ale má vysoký stupeň. V tomto případě lze ale jednoduše přijít na to, že f4 — z2 (z — l)2(z2 + 2z — 1). Odtud plyne, že z — 0 nebo z — 1 nebo z — — 1 ± \/2. Zpětnou eliminací dopočítáme zbylé proměnné. Zjistíme, že řešením soustavy jsou body (1,0, 0), (0,1,0), (0, 0,1) a (-1+VŽ,-l+y/2,-l+y/2), (-l-y/2,-l-y/2,-l-y/2).