Jan Slovák

Geometrické algoritmy II.

Polynomiální objekty

zápisky z přednášek zpracoval Aleš Křenek

Obsah

1 Afinní variety 1 1.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Parametrizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Ideály . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Dimenze 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Gröbnerovy báze 9 2.1 Dělení se zbytkem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Monomiální ideály . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Dicksonovo lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Hilbertova věta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Buchbergerův algoritmus 17 3.1 Kritéria pro Gröbnerovy báze . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 Redukované báze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Zefektivnění algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Teorie eliminací proměnných 28 4.1 Eliminace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 Věta o rozšíření . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 Existence společných kořenů . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4 Důkaz věty o rozšíření . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 Hilbertova věta o nulách . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 Věta o uzávěru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.7 Korespondence ideálů a variet . . . . . . . . . . . . . . . . . . . . . . . 36

5 Aplikace 38 5.1 Řešitelnost systémů rovnic . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Polynomiální a racionální implicitizace . . . . . . . . . . . . . . . . . . 40 5.3 Algebraické křivky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.4 Obálky systému křivek . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6 Algebraické důkazy geometrických tvrzení 48 6.1 Metoda Gröbnerových bazí . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.2 Příklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Poznámka úvodem

Druhá část přednášky geometrické algoritmy je daleko bližší ţčisté� matematické teorii než část předchozí. S tím jistě souvisí pozorovaná nechuť podstatné části studentů informatiky tuto část studovat. Věřím však, že právě uvažování nad matematickým formalismem účinně tříbí analytické schopnosti, proto jsem po úvahách o vesměs lineárně zadaných objektech v první části přednášky zvolil právě matematicky podstatně náročnější teorii popisující algoritmický přístup k problémům spojeným s vzájemnou polohou objektů zadaných algebraickými rovnicemi.

Ústředním pojmem a nástrojem jsou zde tzv. Gröbnerovy báze a algoritmus pro jejich sestrojení. Tím zároveň podávám úvod do algoritmického přístupu ke komutativní algebře a elementární algebraické geometrii a představuje se tak jeden ze základních pilířů každé současné implementace tzv. počítačové algebry. Pro jednoduchost nevychází text z rámce okruhů polynomů více proměnných nad reálnými nebo komplexními skaláry. Užitečnost odvozených výsledků se snažím předvést na (algoritmickém) řešení praktických aplikací (řešení a řešitelnost systémů algebraických rovnic, implicitizace parametrických popisů variet, singularity a obálky algebraických křivek, algebraické (počítačové) důkazy geometrických tvrzení). Věřím, že studium těchto textů přispěje k vzdělání studentů, kteří si k této problematice najdou cestu.

Těžkého úkolu sepsání těchto učebních textů se ujal pan Aleš Křenek, touto cestou mu moc děkuji. Tak jako v předchozí části, texty vznikly na základě mých přednášek prakticky bez mojí další účasti a podle mého názoru se Aleš svého úkolu zhostil výborně. Samozřejmě, za obsahovou stránku musím ručit sám. Jakékoli komentáře, dotazy, výhrady apod. posílejte prosím na adresu slovakmath.muni.cz.

Brno 1995, Jan Slovák

1 Afinní variety

V této a několika následujících kapitolách se budeme zabývat formálním aparátem, který může mít mnoho aplikací všude, kde se pracuje s objekty nebo ději popsatelnými polynomy, resp. systémy polynomiálních rovnic.

Jedná se například o

• Hledání příslušnosti bodu k nějakému tělesu

• Hledání extrémů na ploše

• Analýza pohybů součástí nějakého stroje atd.

1.1 Základní pojmy

Přistupme nejprve k formálnímu aparátu, konkrétních aplikací se snad dočkáme později. 1.1 Definice. Monomem v proměnných x_{1}, …, x_{n} nad polem k nazveme výraz x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}, kde α_{i} ∈ ℕ. Za stupeň tohoto monomu (značíme degx_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}) považujeme číslo α_{1} + ⋯ + α_{n}. Zavádíme pojem multiindexu pro α = (α_{1}, …, α_{n}) a pro zjednoduššení píšeme x^{α} = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} a |α| = α_{1} + ⋯ + α_{n}. Polynomem v proměnných x_{1}, …, x_{n} nad polem k rozumíme

∑_{α} a_{α}x^{α} kde a_{α} ∈ k a suma je konečná

Množinu všech polynomů v proměnných x_{1}, …, x_{n} nad polem k označíme k[x_{1}, …, x_{n}]. Sčítání na ní je vcelku zřejmé (u stejných monomů se sečtou koeficienty v k), násobení definujeme takto

(ax^{α}) · (bx^{β}) := (ab)x^{α+β}

Tím jsme definovali strukturu okruhu^{1}. Za stupeň polynomu považujeme maximum stupňů jeho monomů v daném uspořádání multiindexů. To bylo jistě pouhé opakování z algebry, přistupme dále. 1.2 Definice. Afinním n-rozměrným prostorem rozumíme k^{n} = \underbrace{k × ⋯ × k}_{n} se stan-

dardní afinní strukturou. Polynom f = ∑_{α} a_{α}x^{α} ∈ k[x_{1} …, x_{n}] lze pochopitelně přirozeným způsobem chápat jako zobrazení f: k^{n} → k definované

f(u_{1}, …, u_{n}) := ∑_{α} a_{α}u^{α} kde u^{α} = u_{1}^{α_{1}} ⋯ u_{n}^{α_{n}}

Platí implikace, že pokud f ∈ k[x_{1}, …, x_{n}] je identicky roven 0 (tj. z definice a_{α} = 0 pro každé α), pak je f: k^{n} → k nulové zobrazení. Obrácení ale nemusí obecně platit,

1Nepřítel nechť si samostatně dokáže, že je tomu skutečně tak.

Obr. 1: 𝔙((x^{2} + y^{2})^{3} − 4x^{2}y^{2})

uvažme třeba k = ℤ_{2}, f = x^{2} − x. Zřejmě f(x) = x(x − 1) = 0 na ℤ_{2} pro každé x, ale f není nulový polynom.

Ve dvou proměnných stačí vzít g(x, y) = x^{2}y + y^{2}x. Obecně pro každé prvočíslo p a a ≠ 0 platí a^{p−1} = 1 v ℤ_{p}, a tedy x^{p} − x je vždy nulové zobrazení. 1.3 Věta. Nechť k je nekonečné pole, f ∈ k[x_{1} …, x_{n}]. Pak f = 0 v k[x_{1} …, x_{n}] právě tehdy, když f: k^{n} → k je nulové zobrazení. Důkaz: Indukcí podle n. Je-li n = 1, pak má každý polynom stupně r > 0 nejvýše r kořenů. Pokud je f nulové zobrazení, musel by polynom mít nekonečně mnoho kořenů, a tedy je stupně 0 nebo nulový. Konstantní polynom, který je nulovým zobrazením, ovšem musí být nutně nulový.

Indukční krok. Můžeme psát f = ∑_{i} g_{i}(x_{1}, …, x_{n−1})x_{n}^{i}. Pro pevně zvolené hodnoty x_{1}, …, x_{n−1} je f polynom jedné proměnné, a tedy g_{i}(x_{1}, …, x_{n−1}) = 0. To platí pro libovolnou volbu x_{1}, …, x_{n−1}, tedy g_{i} jsou nulová zobrazení a podle indukčního předpokladu i nulové polynomy. □ 1.4 Důsledek. Pro nekonečná pole a polynomy f, g ∈ k[x_{1}, …, x_{n}] platí

f = g právě tehdy, když f, g: k^{n} → k jsou stejná zobrazení

1.5 Definice. Nechť f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}]. Afinní varietou v k^{n} určenou polynomy f_{1}, …, f_{n} nazveme množinu

𝔙(f_{1}, …, f_{s}) = {(a_{1}, …, a_{n}) ∈ k^{n} | f_{i}(a_{1}, …, a_{n}) = 0; i = 1, …, s}

Afinní variety jsou například všechny kuželosečky, kvadriky a nadkvadriky singulární i regulární. Ze zajímavějších dvourozměrných uveďme čtyřlístek (obr. 1) – varietu 𝔙((x^{2}+y^{2})^{3}−4x^{2}y^{2}), z trojrozměrných pak obrázek z titulní strany – 𝔙(x^{2}−y^{2}z^{2}+z^{3}), Whitneyho deštník (obr. 2) – 𝔙(x^{2}z −y^{2}), který obsahuje celou přímku {x = 0, y = 0}, a konečně Enneperovu plochu (obr. 3).

Varieta určená více polynomy je pak průnik variet jednotlivých polynomů. Tedy například 𝔙(x^{2} + y^{2} − 1, z) je kružnice se středem (0, 0, 0), poloměrem 1 ležící v rovině xy. Dále 𝔙(xz, yz) je sjednocení přímky x = 0, y = 0 a roviny z = 0, protože pro body těchto dvou útvarů jsou oba polynomy xz, yz nulové.

Obr. 2: Whitneyho deštník

1.6 Věta. Nechť V = 𝔙(f_{1}, …, f_{s}), W = 𝔙(g_{1}, …, g_{t}) ⊆ k^{n} jsou afinní variety. Potom i V ∪ W, V ∩ W jsou afinní variety a platí

\begin{aligned}V ∩ W & = & 𝔙(f_{1}, …, f_{s}, g_{1}, …, g_{t}) \\ V ∪ W & = & 𝔙(f_{i}g_{j}) pro 1 ≤ i ≤ s, 1 ≤ j ≤ t \end{aligned}

□

Na posledním příkladě se objevuje první problém – jak chápat dimenzi. Stačí zmíněná přímka, aby varieta byla třírozměrná, nebo ji ještě budeme považovat za dvojrozměrnou s jistou anomálií?

V následující části se mimo jiné pokusíme zodpovědět otázky, které se v souvislosti s varietami bezprostředně nabízejí.

1. Platí 𝔙(f_{1}, …, f_{s}) = ∅?

2. Je 𝔙(f_{1}, …, f_{s}) konečná množina?

3. Jak lze chápat pojem dimenze v případě variet? Jak se ukáže, 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é pro obecná pole, tj. například racionální čísla^{2}.

1.2 Parametrizace

Pro některé ryze praktické operace s varietami je vhodné používat implicitní reprezentaci (tedy až dosud používané vyjádření), např. pro zjištění, zda daný bod do variety patří či nikoli, jindy je naopak daleko užitečnější vyjádření parametrické. O co se přesně jedná, ukážeme na příkladech.

𝔙(x+y +z −1, x+2y −z −3) udává přímku (průnik dvou rovin). Řešíme-li systém

x + y + z − 1 = 0
x + 2y − z − 3 = 0

2Takové rozhodnutí, zda 𝔙(x^{n} + y^{n} − z^{n}) = ∅ vede na velkou Fermatovu větu.

Obr. 3: Enneperova plocha

dostaneme přímo parametrické vyjádření této přímky

x = −1 − 3t
y = 2 − 2t
z = t

V následujícím se pokusíme o precizní a obecné vyjádření parametrizace. 1.7 Definice. Nechť k je pole a f, g ∈ k[t_{1}, …, t_{n}] polynomy. Pak f/g nazveme racionální funkcí nad polem k. Množina racionálních funkcí rozložená na třídy ekvivalence podle

f/g = h/l ⟺ f · l = g · h v k[t_{1}, …, t_{n}]

tvoří podílové těleso okruhu polynomů k[t_{1}, …, t_{n}]; značíme k(t_{1}, …, t_{n}). 1.8 Definice. Racionální parametrickou reprezentací variety 𝔙(f_{1}, …, f_{r}) ⊆ k^{n} rozumíme racionální funkce r_{1}, …, r_{n} ∈ k(t_{1}, …, t_{s}) splňující následující podmínky

• Je-li x_{i} = r_{i}(t_{1}, …, t_{s}) pro i = 1, 2, …, n pak (x_{1}, …, x_{n}) ∈ 𝔙(f_{1}, …, f_{r}) pro libovolná t_{1}, …, t_{s}.

• 𝔙(f_{1}, …, f_{r}) je minimální afinní varieta obsahující takto dané body (x_{1}, …, x_{n}). V této souvislosti se nabízí další otázky.

4. Existuje parametrizace dané variety, resp. lze ji nalézt?

5. Naopak, existuje (lze nalézt) k parametricky zadané varietě implicitní popis? Obecná odpověď na první z těchto otázek je záporná. V podstatě lze tvrdit, že většinu afinních variet parametrizovat nelze, respektive neexistuje algoritmus parametrizace implicitního popisu. Ty, u kterých se to podaří, nazýváme neiracionální^{3}. Opět obecně není jednoduché rozhodnout, zda daná varieta je neiracionální. Cesta opačným směrem je v nekonečných polích zvládnutelná, algoritmus předvedeme v kapitole 5.2.

Na první pohled je zřejmé, že pro jednu a tutéž varietu existuje více implicitních, případně i parametrických popisů. Opomeneme-li parametrický popis, nejednoznačnosti implicitního jsou způsobeny pro tento účel nevhodnou reprezentací pomocí několika ţgenerujících� polynomů.

3Přímý překlad anglického unirational.

1.3 Ideály

Připomeňme si trochu algebry. 1.9 Definice. Množinu I ⊆ A, kde A je okruh, nazveme ideálem, platí-li 0 ∈ I a zároveň

\begin{matrix}f, g ∈ I ⟹ f + g ∈ I \\ f ∈ I, h ∈ A ⟹ f · h ∈ I \end{matrix}

Pojem generátorů ideálu je snad zřejmý, připomeňme jen značení I = ⟨a_{1}, …, a_{n}⟩. Je-li generátorů konečný počet, říkame, že ideál je konečně generovaný. Pro varietu V = 𝔙(f_{1}, …, f_{s}) klademe

ℑ(V) := {f ∈ k[x_{1}, …, x_{n}] | f(a_{1}, …, a_{n}) = 0 pro všechna (a_{1}, …, a_{n}) ∈ V }

1.10 Věta. Nechť f_{1}, …, f_{s}, g_{1}, …, g_{t} ∈ k[x_{1}, …, x_{n}] jsou polynomy. Pak platí 1. Jestliže ⟨f_{1}, …, f_{s}⟩ = ⟨g_{1}, …, g_{t}⟩, pak 𝔙(f_{1}, …, f_{s}) = 𝔙(g_{1}, …, g_{t}).

2. ℑ(V) je ideál a platí ⟨f_{1}, …, f_{s}⟩ ⊆ ℑ(V), kde V = 𝔙(f_{1}, …, f_{s}). Důkaz:

1. Uvažujme libovolný (a_{1}, …, a_{n}) ∈ 𝔙(f_{1}, …, f_{s}). Pro něj platí

f_{i}(a_{1}, …, a_{n}) = 0 pro i = 1, 2, …, s

Protože g_{1}, …, g_{t} ∈ ⟨f_{1}, …, f_{s}⟩, existují nějaké polynomy h_{1,1}, …, h_{t,s} v n proměnných tak, že

g_{j} = ∑_{i=1}^{s}h_{j,i} · f_{i} pro j = 1, 2, …, t

Odtud g_{j}(a_{1}, …, a_{n}) = 0 pro j = 1, 2, …, t. Máme tedy

𝔙(f_{1}, …, f_{s}) ⊆ 𝔙(g_{1}, …, g_{t}).

Opačná inkluze se dokáže zcela analogicky.

2. Nechť g, g′ ∈ ℑ(V), h ∈ k[x_{1}, …, x_{n}]. Potom pro zvolený bod (a_{1}, …, a_{n}) ∈ V platí g(a_{1}, …, a_{n}) = 0, a tedy

\begin{matrix}(g · h)(a_{1}, …, a_{n}) = 0 ⟹ g · h ∈ ℑ(V) \\ (g + g′)(a_{1}, …, a_{n}) = 0 ⟹ g + g′ ∈ ℑ(V) \end{matrix}

Proto ℑ(V) je ideál. Uvažujme libovolný f ∈ ⟨f_{1}, …, f_{s}⟩. Ten lze psát jako

f = ∑_{i=1}^{s}h_{i} · f_{i} pro nějaká h_{1}, …, h_{s} ∈ k[x_{1}, …, x_{n}]

Pro (a_{1}, …, a_{n}) ∈ V je tedy f(a_{1}, …, a_{n}) = 0. Proto platí ⟨f_{1}, …, f_{s}⟩ ⊆ ℑ(V).

□

Jednoduché příklady:

ℑ({(0, 0, …, 0)}) = ⟨x_{1}, …, x_{n}⟩

ℑ(k^{n}) = { 0} pro libovolné nekonečné pole k

Inkluze opačná k druhé části věty obecně neplatí. Například varieta 𝔙(x^{2}, y^{2}) má jediný bod – (0, 0). ℑ(V) je potom ⟨x, y⟩ ⊃ ⟨x^{2}, y^{2}⟩. Jsou-li V, W ⊆ k^{n} variety, pak platí

V ⊆ W ⟹ ℑ(V) ⊇ ℑ(W)

Neboli polynomy, které se nulovaly na nějaké varietě se nutně musí nulovat i na její podmnožině.

Objevují se další problémy 6. Je každý ideál I ∈ k[x_{1}, …, x_{n}] konečně generovaný?

7. Lze algoritmicky zjistit, zda f ∈ ⟨f_{1}, …, f_{s}⟩?

8. Jaký je přesný vztah mezi ⟨f_{1}, …, f_{s}⟩ a ℑ(𝔙(f_{1}, …, f_{s}))?

1.4 Dimenze 1

Na všechny výše zmíněné otázky se pokusíme odpovědět nejprve ve zjednodušeném, ale názorném případě polynomů v jedné proměnné. Konvenčně používáme proměnnou x a koeficienty v polynomu značíme

f = a_{0}x^{n} + a_{1}x^{n−1} + ⋯ + a_{n} kde a_{0} ≠ 0.

Vedoucí člen polynomu (leading term) definujeme jako LT (f) := a_{0}x^{n}. Zřejmě platí

degf ≤ degg ⟺ LT (f)|LT (g)

1.11 Věta Algoritmus dělení se zbytkem. Nechť k je pole a g nenulový polynom. Pak každé f ∈ k[x] lze jednoznačně psát jako

f = q · g + r kde r = 0 nebo degr < degg

Důkaz: je pochopitelně konstruktivní, podíl q a zbytek r počítá následující algoritmus. Algoritmus 1.1

1. q := 0, r := f

2. while r ≠ 0 ∧ LT (g)|LT (r)

2.1. q := q + LT (r)/LT (g) 2.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í. 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′) < degg (protože r ≠ r′, má smysl uvažovat deg(r − r′)). Zároveň ale platí

deg(r − r′) = deg(q − q′) + degg ≥ degg

což je spor. Dvojice q, r je tedy určena jednoznačně. □

1.12 Důsledek. Je-li k pole, má každý f ∈ k[x] nejvýše degf kořenů.

Důkaz: Je-li degf = 0 (konstantní polynom), neexistuje žádný kořen. Nechť degf = n > 0 a f má kořen a. Potom podle věty 1.11 existují q, r tak, že

f = q(x − a) + r a zároveň degr = 0 nebo r = 0.

Protože a je kořen, r nemůže být konstantní a tudíž f = q(x − a). Stupeň q je n − 1, podle indukčního předpokladu má nanajvýš n − 1 kořenů, a tedy f jich má nejvýše n.

□

1.13 Důsledek. Nechť k je pole. Pak každý ideál v k[x] je tvaru ⟨f⟩.

Důkaz: Nechť I ⊆ k[x]. Pokud I = {0}, pak I = ⟨0⟩. Předpokládejme I ⊃ {0} a nechť f ∈ I je minimálního stupně. Pak zřejmě ⟨f⟩ ⊆ I.

Naopak uvažujme nějaké g ∈ I. Podle věty 1.11 existují q, r takové, že g = q · f + r a zároveň degr < degf nebo r = 0. Protože g, f ∈ I, platí q · f ∈ I, a tedy r ∈ I. Polynom f byl vybrán s nejmenším stupněm z I, a proto r = 0. Odtud už plyne g ∈ ⟨f⟩, a tedy i I ⊆ ⟨f⟩. □

1.14 Definice. 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 Algoritmus 1.2

1. h := f, s := g

2. while s ≠ 0

2.1. r := zbytek po dělěníh/s 2.2. h := s 2.3. s := r

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í.

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ě.

Pro korektnost následující věty ještě definujme největšího společného dělitele více než dvou polynomů. Je-li s > 2, potom

GCD(f_{1}, …, f_{s}) := GCD(f_{1}, GCD(f_{2}, …, f_{s}))

1.15 Věta. Pro polynomy f_{1}, …, f_{s} platí ⟨GCD(f_{1}, …, f_{s})⟩ = ⟨f_{1}, …, f_{s}⟩. Důkaz: Protože GCD(f_{1}, …, f_{s})|f_{1}, …, f_{s}, platí ⟨f_{1}, …, f_{s}⟩ ⊆ ⟨GCD(f_{1}, …, f_{s})⟩. Naopak přímo z algoritmu výpočtu GCD plyne Bezoutova rovnost, tj.

GCD(f_{1}, …, f_{s}) = h_{1}f_{1} + ⋯ + h_{s}f_{s} pro vhodná h_{1}, …, h_{s}

Odtud již vyplývá opačná inkluze. □

Během kapitoly jsme položili několik otázek. Nyní máme již vše potřebné k jejich zodpovězení pro případ polynomů jedné proměnné.

1. Protože 𝔙(f_{1}, …, f_{s}) = 𝔙(GCD(f_{1}, …, f_{s})) (důsledek věty 1.10), 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(f_{1}, …, f_{s}) s jedinou vyjímkou GCD(f_{1}, …, f_{s}) = 0; to nastane pouze v případě, že f_{1} = f_{2} = ⋯ = f_{s} = 0. Pak je varietou celá množina k.

3. Pojem dimenze v tomto případě postrádá smysl.

4. Stejně tak není nijak účelné parametrizovat konečnou množinu.

6. Každý ideál je generovatelný jediným polynomem – důsledek věty 1.15.

7. f ∈ ⟨f_{1}, …, f_{s}⟩ ⟺ GCD(f_{1}, …, f_{s})|f (důsledek věty 1.13).

8. Označíme-li ⟨f⟩ := ℑ(𝔙(f_{1}, …, f_{s})), pak f a GCD(f_{1}, …, f_{s}) se mohou lišit pouze násobností kořenů.

Obr. 4: Stejná varieta?

2 Gröbnerovy báze

Jak už bylo řečeno, implicitní reprezentace variety není vždy nejvhodnější. Jen pro k^{3} = ℝ^{3} je při komplikovanějším zadání obtížné vůbec interpretovat, jak daná varieta vypadá. Znamenalo by to určit průnik obecně i dost komplikovaných útvarů. Demonstrujme na ještě poměrně jednoduchém příkladě. Varieta na obr. 4 vlevo je 𝔙(x^{2}+y^{2}+z^{2}−1, x^{2}+y^{2}+z). V tomto případě lze ještě poměrně snadno určit, že průnikem koule a paraboloidu je kružnice ležící v rovině z = \frac{1}{2}−\frac{1}{2} \sqrt{5}, tedy varietu lze stejně dobře vyjádřit jako 𝔙(x^{2}+ y^{2}+ z^{2}− 1, z^{2}− z − 1), případně 𝔙(x^{2}+ y^{2}+ z, z − \frac{1}{2} + \frac{1}{2} \sqrt{5}) a podobně.

Obrázek 4 a předchozí odstavec nabízí další problém. Jak rozhodnout, zda dvě implicitně zadané variety jsou stejné? Zrovna tak prázdnou varietu (opět v ℝ^{3}) lze popsat 𝔙(x^{2} + 1) i 𝔙(1) nebo dokonce 𝔙(x^{2} + y^{2} + z^{2} − 1, x^{2} + y^{2} + z^{2} − 2). Podobným problémem je i určení průniku, odvoláme-li se opět na obr. 4, průnik koule 𝔙(x^{2}+ y^{2}+ z^{2} − 1) a paraboloidu 𝔙(x^{2} + y^{2} + z) lze vyjádřit jednodušeji jako průnik některého z těchto objektů a roviny.

Většinu těchto problémů poměrně uspokojivě řeší aparát prezentovaný v [1]. Jak se pokusíme ukázat, varietu je vhodnější reprezentovat generujícím ideálem a pro ten se podaří nalézt vyjádření nezávislé na volbě generátorů, resp. předvedeme algoritmus převádějící každou množinu generátorů na jistý jednoznačný kanonický tvar.

2.1 Dělení se zbytkem

U polynomů více proměnných je situace daleko komplikovanější než byla ve větě 1.11. Kupříkladu zde neexistuje přímý ekvivalent pojmu stupně, je nutné definovat ho podstatně opatrněji. Ani pojem vedoucího členu polynomu není zcela přímočarý, je zde nutné volit nějaké uspořádání na proměnných a monomech; celá teorie pak přestává být vůči proměnným symetrická.

Dělení se zbytkem zde znamená vyjádřit f ∈ k[x_{1}, …, x_{n}] jako

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r

Například mějme f = x^{2}y + xy^{2} + y^{2}, f_{1} = xy − 1 a f_{2} = y^{2} − 1. Prvním dělením získáme

f = (x + y) · f_{1} + (x + y^{2} + y)

LT (y^{2}−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) · f_{1} + f_{2} + (x + y + 1)

Zde již žádný člen zbytku není dělitelný žádným z LT (f_{1}), LT (f_{2}). To je také požadovaná vlastnost na výsledek dělení se zbytkem. 2.1 Definice. Úplné (lineární) dobré (tj. každá neprázdná podmnožina má nejmenší prvek) uspořádání < na ℕ_{0}^{n} splňující

∀α, β, γ ∈ ℤ^{n}: α < β ⟹ α + γ < β + γ

nazveme monomiálním uspořádáním na k[x_{1}, …, x_{n}]. Takto položená definice není úplná. Uspořádání na ℕ_{0}^{n} indukuje pouze 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šíří ţ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ě x_{1} > x_{2} > · · ·. 2.2 Definice. Lexikografické uspořádání je takové <_{lex}, že pro každé α, β ∈ ℕ_{0}^{n} platí

α >_{lex} β ⟺ Nejlevější nenulový člen v α − β je kladný

2.3 Definice. Gradované lexikografické uspořádání je takové <_{grlex}, že pro každé α, β ∈ ℕ_{0}^{n} platí:

α >_{grlex} β ⟺ |α| > |β| nebo
|α| = |β| a zároveň α >_{lex} β

2.4 Definice. Gradované opačné lexikografické uspořádání je takové <_{grevlex}, že pro každé α, β ∈ ℕ_{0}^{n} platí:

α >_{grevlex} β ⟺ |α| > |β| nebo

|α| = |β| a zároveň nejpravější nenulový člen (α − β) je záporný

Tedy x_{1} >_{grevlex} x_{2} >_{grevlex} ⋯ >_{grevlex} x_{n}, ale pokud x > y > z, pak x^{2}yz^{2} >_{grlex} xy^{3}z, ale x^{2}yz^{2} <_{grevlex} xy^{3}z. 2.5 Lemma. >_{lex}, >_{grlex}, >_{grevlex} jsou monomiální uspořádání.

2.6 Definice. Nechť f = ∑_{α∈ℕ_{0}^{n}} a_{α}x^{α} ∈ k[x_{1}, …, x_{n}] je nenulový a < monomiální. Pak definujeme:

• Stupeň multidegf := max{α ∈ ℕ_{0}^{n} | a_{α} ≠ 0} • Vedoucí koeficient LC f := a_{multideg f}

• Vedoucí monom LM f := x^{multideg 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í. 2.7 Lemma. Nechť f, g ∈ k[x_{1}, …, x_{n}] a < je monomiální. Pak

1. multideg(f · g) = multidegf + multidegg

2. f + g ≠ 0 ⟹ multideg(f + g) ≤ max{multidegf, multidegg} 2.8 Věta Dělení se zbytkem. Nechť < je monomiální a F = (f_{1}, …, f_{s}) s-tice polynomů v k[x_{1}, …, x_{n}]. Pak každý f ∈ k[x_{1}, …, x_{n}] lze vyjádřit jako

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r kde a_{i}, r ∈ k[x_{1}, …, x_{n}] 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 f_{1}, …, LT f_{s} a pokud a_{i}f_{i} ≠ 0 pak multidegf ≥ multidega_{i}f_{i} pro každé i. Polynom r nazýváme zbytkem po dělení f/F.

Je zřejmé, že narozdíl od jedné proměnné výsledek dělení se zbytkem není dán jednoznačně ani vzhledem k pevně zvolenému uspořádání monomů. Věta také nic o jednoznačnosti netvrdí, následující algoritmus dává jedno možné řešení. Nadále budeme výsledkem dělení se zbytkem chápat právě jeho výstup. Algoritmus 2.1

1. a_{1} := 0, …, a_{s} := 0, r := 0, p := f

2. while p ≠ 0

2.1. i := 1 2.2. d := false 2.3. while i ≤ s ∧ notd 2.3.1. if LT f_{i}|LT p

2.3.1.1. a_{i} := a_{i} + LT p/LT f_{i} 2.3.1.2. p := p − (LT p/LT f_{i}) · f_{i} 2.3.1.3. d := true 2.3.2. else i := i + 1

2.4. if notd 2.4.1. r := r + LT p 2.4.2. p := p − LT p

Důkaz: Při každém průchodu vnějším cyklem se právě jednou provede právě jeden z příkazů 2.3.1.2, 2.4.2, a tedy stupeň p klesne. Proto algoritmus skončí.

Platí invariant f = a_{1}f_{1} + ⋯ + p + r a přitom každý člen každého a_{i} je podílem LT p/LT f_{i} 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_{i}f_{i} je menší nebo roven stupni f. □

V k[x] byl každý ideál tvaru I = ⟨f⟩ a algoritmus dělení se zbytkem plně řešil příslušnost k ideálu. Oproti tomu v k[x_{1}, …, x_{n}] platí pouze implikace

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + 0 ⟹ f ∈ ⟨f_{1}, …, f_{s}⟩

Obrácení obecně neplatí, uvažujme f = xy^{2} − x, f_{1} = xy + 1, f_{2} = y^{2} − 1. Potom algoritmus dělení dá

f = y(xy + 1) + 0(y^{2} − 1) + (−x − y)

ale přitom evidentně f = x(y^{2} − 1), a tedy f ∈ ⟨f_{1}, f_{2}⟩.

2.2 Monomiální ideály

2.9 Definice. Ideál I ⊆ k[x_{1}, …, x_{n}] nazýváme monomiální, existuje-li množina A ⊆ ℕ_{0}^{n} tak, že I se sestává právě ze všech polynomů tvaru ∑_{α∈A} h_{α}x^{α}, kde h_{α} ∈ k[x_{1}, …, x_{n}]. Potom píšeme I = ⟨x^{α} | α ∈ A⟩. Zřejmě pro monomiální ideál I platí

x^{β} ∈ I ⟺ ∃α ∈ A: x^{α}|x^{β}

2.10 Lemma. Nechť I ⊆ k[x_{1}, …, x_{n}] je monomiální ideál, f ∈ k[x_{1}, …, x_{n}] 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[x_{1}, …, x_{n}]. Každý člen a_{α}x^{α} se musí rovnat některému členu z druhé rovnosti, tedy existují taková d ∈ k, δ ∈ ℕ_{0}^{n} tak, že a_{α}x^{α} = dx^{β+δ} . Proto x^{α} ∈ I, a tedy platí (3). □ 2.11 Důsledek. Dva monomiální ideály splývají právě tehdy, když obsahují stejné monomy.

2.3 Dicksonovo lemma

2.12 Věta Dicksonovo lemma. Každý monomiální ideál I = ⟨x^{α} | α ∈ A⟩ ⊆ k[x_{1}, …, x_{n}] lze psát ve tvaru I = ⟨x^{α_{1}}, …, x^{α_{s}}⟩, kde α_{1}, …, α_{s} ∈ A. Důkaz: Důkaz vedeme indukcí podle počtu proměnných. Nechť n = 1. Pak I ⊆ k[x], I = ⟨x^{α} | α ∈ A ⊆ ℕ_{0}⟩. Položme β := minA. Potom zřejmě I = ⟨x^{β}⟩.

Uvažujme tedy n > 1. Pro přehlednost označíme proměnné jako x_{1}, …, x_{n−1}, y, monomy potom budou tvaru x^{α}y^{m}, kde α ∈ ℕ_{0}^{n−1}, m ∈ ℕ_{0}, a množinu monomů x^{β} s β ∈ A budeme značit I_{A}. Předpokládejme, že I ⊆ k[x_{1}, …, x_{n−1}, y] je monomiální. Definujme J ⊆ k[x_{1}, …, x_{n−1}] následovně

J := ⟨x^{α} | ∃m ∈ ℕ_{0}: x^{α}y^{m} ∈ I_{A}⟩

Obr. 5: Monomy v ideálu I = ⟨x^{3}y, xy^{3}⟩ ⊂ ℝ[x, y]

Zřejmě J je monomiální ideál v n−1 proměnných, a tedy podle indukčního předpokladu lze psát J = ⟨x^{α_{1}}, …, x^{α_{s}}⟩. Dále z definice J vyplývá, že existují taková minimální m_{i} ∈ ℕ_{0} tak, že x^{α_{i}}y^{m_{i}} ∈ I_{A}. Označme tedy m := max{m_{i}} a definujme analogicky systém ideálů J_{k} ⊆ k[x_{1}, …, x_{n−1}] pro 0 ≤ k ≤ m − 1

J_{k} := ⟨x^{β} | x^{β}y^{k} ∈ I_{A}⟩

Opět všechny J_{k} splňují indukční předpoklad, a tedy je lze vyjádřit

J_{k} = ⟨x^{α_{k,1}}, …, x^{α_{k,s_{k}}} ⟩.

Zbývá ukázat, že I je generovaný touto množinou monomů

x^{α_{1}}y^{m} … x^{α_{s}}y^{m}
x^{α_{0,1}}y^{0} … x^{α_{0,s_{0}}} y^{0}
⋮
x^{α_{m−1,1}}y^{m−1} … x^{α_{m−1,s_{m−1}}} y^{m−1}

Uvažujme libovolný monom x^{α}y^{p} ∈ I_{A}. Nastane jeden ze dvou případů • p ≥ m. Potom jistě x^{α} ∈ J, a tedy některý z x^{α_{1}}y^{m}, …, x^{α_{s}}y^{m} dělí x^{α}y^{p}.

• p < m. Potom analogicky x^{α} ∈ J_{k} a některý z x^{α_{k,1}}y^{k}, …, x^{α_{k,s_{k}}} y^{k} dělí x^{α}y^{p}. Podle lemmatu 2.10 lze každé f ∈ I vyjádřit jako lineární kombinaci monomů z I_{A}, ty jsou již dělitelné některým ze zmíněných generátorů, a tedy f patří do ideálu jimi generovaného. Proto I je jeho podmnožinou.

Opačná inkluze je zcela triviální. □

2.13 Důsledek. Nechť < je relace na ℕ_{0}^{n} splňující podmínky 1. Relace < je úplné uspořádání.

2. α < β, γ ∈ ℕ_{0}^{n} ⟹ α + γ < β + γ Pak < je dobré uspořádání právě tehdy, když ∀α ∈ ℕ_{0}^{n}: α ≥ 0

Důkaz:

“⟹” Protože < je dobré, existuje α_{0} ∈ ℕ_{0}^{n} nejmenší. Předpokládejme α_{0} < 0. Podle podmínky (2) zkonstruujeme nekonečnou posloupnost 0 > α_{0} > 2α_{0} > ⋯, což je spor s tím, že < je dobré.

“⟸” Nechť ∀α ∈ ℕ_{0}^{n}: α ≥ 0. Uvažme libovolnou množinu ∅ ≠ A ⊆ ℕ_{0}^{n}. Potom I = ⟨x^{α} | α ∈ A⟩ je konečně generovaný nějakými monomy x^{α_{1}}, …, x^{α_{s}} ∈ A. Bez újmy na obecnosti předpokládejme α_{1} < ⋯ < α_{s}.

Uvažujme libovolné α ∈ A. Potom nutně x^{α_{i}}|x^{α} pro vhodné i = 1, …, s, tj. α = α_{i} + γ, kde γ ≥ 0 (předpoklad této implikace). Potom ale platí

α ≥ α_{i} + 0 ≥ α_{1}

a tedy α_{1} je nejmenší v A. Protože A byla zvolena libovolně, je uspořádání < dobré.

□

2.4 Hilbertova věta

Je-li I ⊆ k[x_{1}, …, x_{n}] 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 g_{1}, …, LT g_{s}⟩ pro nějaká vhodná g_{1}, …, g_{s} ∈ I.

2.14 Věta Hilbertova. Každý ideál I ∈ k[x_{1}, …, x_{n}] je konečně generovaný. 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á g_{1}, …, g_{s} ∈ I, že ⟨LT I⟩ = ⟨LT g_{1}, …, LT g_{s}⟩ Zřejmě ⟨g_{1}, …, g_{s}⟩ ⊆ I. Vezměme libovolné f ∈ I a proveďme dělení se zbytkem s-ticí g_{1}, …, g_{s}. Dostáváme

f = a_{1}g_{1} + ⋯ + a_{s}g_{s} + r kde žádný člen r není dělitelný LT g_{1}, …, LT g_{s}.

Protože r = f − a_{1}g_{1} − ⋯ − a_{s}g_{s}, 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 g_{1}, …, LT g_{s}. To je ovšem spor s výsledkem algoritmu dělení. Proto r = 0 a I je tedy generovaný g_{1}, …, g_{s}. □

2.15 Definice. Konečná báze g_{1}, …, g_{s} ideálu I ⊆ k[x_{1}, …, x_{n}] se nazývá Gröbnerova, jestliže platí ⟨LT I⟩ = ⟨LT g_{1}, …, LT g_{s}⟩.

Báze použitá v důkazu Hilbertovy věty byla Gröbnerova.

Jak už to na světě bývá, Gröbnerovy báze nevymyslel pan Gröbner, ale jeho aspirant B. Buchberger, který je tak údajně nazval na počest svého učitele. Ještě navíc nebyl první. V polovině šedesátých let popsal H. Hironaka ţstandardní báze�, v podstatě se jednalo o totéž. Ke cti pana Buchbergera nutno podotknout, že o práci svého současníka patrně neměl ani ponětí a dovedl ji dále.

Ani pan Hilbert to neměl ve své době jednoduché. Větu, která byla ostatně jako hypotéza už zformulována dříve, dokázal podstatně komplikovanějším způsobem, než jsme uvedli. Navíc nekonstruktivní důkazy nebyly tenkrát příliš oblíbeny, a tak se od svých kolegů uznání nedočkal.

Inkluze ⟨LT I⟩ ⊇ ⟨LT g_{1}, …, LT g_{s}⟩ platí pro libovolnou bázi g_{1}, …, g_{s}, a tedy se stačí omezit na dokazování opačné. Ta obecně platit nemusí. Uvažujme například <_{grlex} a polynomy x^{3} − 2xy a x^{2}y − 2y^{2} + x. Potom x^{2} = x(x^{2}y − 2y^{2} + x) − y(x^{3} − 2xy), a tedy x^{2} ∈ I, ale zřejmě x^{2} ∉ ⟨x^{3}, x^{2}y⟩.

2.16 Důsledek. Každý ideál I ⊆ k[x_{1}, …, x_{n}] má Gröbnerovu bázi. Naopak každá množina polynomů g_{1}, …, g_{s} ∈ I splňující ⟨LT I⟩ = ⟨LT g_{1}, …, LT g_{s}⟩ je Gröbnerovou bází ideálu I.

Na ilustraci uveďme jednoduchý případ, kdy generátory ideálu I budou polynomy stupně 1 a uspořádání bereme <_{lex}. Označme generátory f_{i} = ∑_{j} a_{i,j}x_{j} + a_{i,0}. Uvažujme matici A = (a_{i,j}), kde i = 1, …, s a j = 0, …, n a aplikujme na ni Gausovu eliminaci. Získláme B = (b_{i,j}) ve schodovitém tvaru, z ní navíc vypustíme nulové řádky. Máme novou bázi g_{1}, …, g_{t}, kde t ≤ s. Vzhledem k provedeným úpravám je každé f_{i} vyjádřitelné jako lineární kombinace g_{1}, …, g_{t}, a tedy ⟨f_{1}, …, f_{s}⟩ = ⟨g_{1}, …, g_{t}⟩ Tvrdíme, že g_{1}, …, g_{t} je Gröbnerova báze.

Bez újmy na obecnosti předpokládejme, že proměnné jsou značeny tak, že LM g_{i} = x_{i} pro i = 1, …, t. Uvažujme libovolný f ∈ I. Ten lze psát

f = h_{1}f_{1} + ⋯ + h_{s}f_{s} = h′_{1}g_{1} + ⋯ + h′_{t}g_{t}

Chceme, aby LT f ∈ ⟨LT g_{1}, …, LT g_{t}⟩, tj. LT f má být dělitelný některým z x_{1}, …, x_{t}. Předpokládejme, že f je pouze v proměnných x_{t+1} , …, x_{n}. Pak ale h′_{1} = 0, protože x_{1} je vzhedem ke schodovitosti B pouze v g_{1}. Analogickým postupem získáme h′_{2} = ⋯ = h′_{t} = 0, a tedy f = 0. Báze g_{1}, …, g_{t} je tedy Gröbnerova.

Použití Gausovy eliminace zde není náhodné, v následující části ukážeme algoritmus počítající Gröbnerovy báze, který je v podstatě zobecněním Gausovy eliminace pro polynomy vyšších stupňů.

2.17 Věta Ascending Chain Condition. Nechť I_{1} ⊆ I_{2} ⊆ ⋯ je neklesající nekonečná posloupnost ideálů v k[x_{1}, …, x_{n}]. Pak existuje N ≥ 1 tak, že I_{N} = I_{N+1} = · · ·.

Důkaz: Označme I := ⋃_{i=1}^{∞} I_{i}. Zřejmě I je ideál. Podle Hilbertovy věty existují f_{1}, …, f_{s} tak, že I = ⟨f_{1}, …, f_{s}⟩. Jistě existuje takové N, že f_{1}, …, f_{s} ∈ I_{N}. Potom už I = I_{N} = I_{N+1} = · · ·. □

2.18 Definice. Nechť I ⊆ k[x_{1}, …, x_{n}]. Označme

V (I) := {(a_{1}, …, a_{n}) ∈ k^{n} | ∀f ∈ I: f(a_{1}, …, a_{n}) = 0}

Podle Hilbertovy věty je I = ⟨f_{1}, …, f_{s}⟩ a V (I) je rovno varietě 𝔙(f_{1}, …, f_{s}).

V obecné teorii se okruhy, kde je každý ideál konečně generovaný, nazývají noetherovské. Ukazuje se, že okruh je noetherovský, právě tehdy, když v něm platí tvrzení věty 2.17. V tomto kontextu má Hilbertova věta hlubší smysl. Dokazuje totiž, že okruh polynomů nad noetherovským okruhem je opět noetherovský.

3 Buchbergerův algoritmus

Pouhé tvrzení, že každý ideál má Gröbnerovu bázi (důsledek Hilberovy věty) by asi nebylo příliš prakticky použitelné. Proto se budeme dále zaměřovat na algoritmické nalezení takové báze, a protože pro daný ideál může Gröbnerových bází existovat více, pokusíme se identifikovat i jakousi jednoznačnou kanonickou formu.

3.1 Kritéria pro Gröbnerovy báze

3.1 Věta. Nechť G = {g_{1}, …, g_{t}} je Gröbnerova báze ideálu I ⊆ k[x_{1}, …, x_{n}] a f je polynom v k[x_{1}, …, x_{n}]. Pak existuje právě jedno r = ∑_{α} a_{α}x^{α} ∈ k[x_{1}, …, x_{n}] s těmito vlastnostmi

1. Žádný člen r není dělitelný žádným z LT g_{1}, …, LT g_{t}, tj. ∀α∀i: LT g_{i} |̸ a_{α}x^{α}.

2. ∃g ∈ I: f = g + r

Důkaz: Algoritmus pro dělení se zbytkem dá

f = a_{1}g_{1} + ⋯ + a_{t}g_{t} + r kde r splňuje podmínku 1.

Za g už vezmeme a_{1}g_{1} + ⋯ + a_{t}g_{t}, které triviálně padne do I.

Zbývá dokázat jednoznačnost. Předpokládejme f = g + r = g′ + r′, kde r ≠ r′. Zřejmě platí r − r′ = g′ − g ∈ I. Protože G je Gröebnerova, je LT (r − r′) dělitelný některým z LT g_{1}, …, LT g_{t}. Diskutujme následující možnosti

• LM r ≠ LM r′. Pak ten s vyšším stupněm musí být dělitelný některým z vedoucích členů LT g_{1}, …, LT g_{t}, což je spor s prvním bodem.

• LM r = LM r′ ∧ LC r ≠ LC r′. Potom ale oba LM r, LM r′ musí být dělitelné

některým z LT g_{1}, …, LT g_{t}. Proto tedy LT r = LT r′ a induktivní úvahou odtud plyne r = r′. □ Předchozí věta je vlastně zobecněním dělení se zbytkem, kde na místě dělitele vystupuje ideál. V případě jedné proměnné nebylo co zobecňovat, protože každý ideál byl generovaný jedním polynomem. Zajímá-li nás pouze zbytek, věta navíc říká, že nezáleží na pořadí polynomů v bázi. Proto má smysl zavést značení \overline{f}^{F} pro zbytek po dělení f/F, pokud F je Gröbnerova báze. 3.2 Důsledek. Nechť G = {g_{1}, …, g_{t}} je Gröbnerova báze ideálu I ⊆ k[x_{1}, …, x_{n}] a f je polynom v k[x_{1}, …, x_{n}]. Pak platí

f ∈ I ⟺ zbytek po dělení f/G je nulový

Důkaz: “⟸” Nechť f = g + r je rozklad z předchozí věty a r = 0. Potom triviálně f ∈ I.

“⟹” f ∈ I ⟹ f = f +0. Protože f vyhovuje podmínkám předchozí věty, a takový polynom podle jejího tvrzení existuje právě jeden, musí být zbytek po dělení f/G nutně nulový.

□

3.3 Definice. Pokud α = multidegf a β = multidegg, buď

γ := (γ_{1}, …, γ_{n}) kde γ_{i} = max{α_{i}, β_{i}}

Monom x^{γ} nazýváme nejmenším společným násobkem (least common multiple) monomů LM f a LM g a zavádíme poněkud matoucí označení LCM(LM f, LM g) := x^{γ}. Výraz

S(f, g) := \frac{x^{γ}}{LT f} · f − \frac{x^{γ}}{LT g} · g

nazýváme S-polynomem^{4} polynomů f, g.

Jedná se o nástroj k jakési 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í.

Vezměme například f = x^{3}y^{2} − x^{2}y^{3} + x, g = 3x^{4}y + y^{2}, tedy polynomy stupně 5 v ℝ[x, y] a uspořádání <_{grlex}. Pak γ = (4, 2) a

S(f, g) = \frac{x^{4}y^{2}}{x^{3}y^{2}}f − \frac{x^{4}y^{2}}{3x^{4}y}g = xf − \frac{1}{3}yg = −x^{3}y^{3} + x^{2} − \frac{1}{3}y^{3}

což je polynom stupně 6.

Následuje lemma technického rázu, které je nutné pro důkaz stěžejní věty. 3.4 Lemma. Uvažme polynom f = ∑_{i=1}^{t} c_{i}x^{α_{i}}g_{i}, kde c_{1}, …, c_{t} ∈ k a α_{i}+multidegg_{i} = δ pro nějaké pevné δ kdykoli c_{i} ≠ 0. Pokud multidegf < δ, pak existují taková c_{i,j}, že

∑_{i=1}^{t}c_{i}x^{α_{i}}g_{i} = ∑_{j,k=1}^{t} c_{j,k}x^{δ−γ_{j,k}}S(g_{j}, g_{k}) kde x^{γ_{j,k}} = LCM(LM g_{j}, LM g_{k})

a dále každý x^{δ−γ_{j,k}}S(g_{j}, g_{k}) má stupeň menší než δ. Důkaz: Označme d_{i} := LC g_{i} a p_{i} = x^{α_{i}}g_{i}/d_{i}. Určitě c_{i}d_{i} = LC(c_{i}x^{α_{i}}g_{i}) a LC p_{i} = 1. Protože multideg(c_{i}x^{α_{i}}g_{i}) = δ a zároveň multidegf < δ, musí nutně platit ∑_{i=1}^{t} c_{i}d_{i} = 0. Pokusme se teď f vyjádřit jako kombinaci S-polynomů.

f = ∑_{i=1}^{t}c_{i}d_{i}p_{i} = c_{1}d_{1}(p_{1} − p_{2}) + (c_{1}d_{1} + c_{2}d_{2})(p_{2} − p_{3}) + ⋯

+ (c_{1}d_{1} + ⋯ + c_{t−1}d_{t−1})(p_{t−1} − p_{t}) + (\underbrace{c_{1}d_{1} + ⋯ + c_{t}d_{t}}_{0})p_{t}

Každý rozdíl p_{j} − p_{k} lze vyjádřit v S-polynomech

\frac{x^{δ}}{d_{j}x^{δ−α_{j}}} g_{j} − \frac{x^{δ}}{d_{k}x^{δ−α_{k}}} g_{k} = x^{δ−γ_{j,k}} (\frac{x^{γ_{j,k}}}{LT g_{j}} g_{j} − \frac{x^{γ_{j,k}}}{LT g_{k}} g_{k}) = x^{δ−γ_{j,k}}S(g_{j}, g_{k})

Z obou rovností se už snadno odvodí jednotlivé koeficienty c_{j,k}. □

4Ze syzygy neboli spřežení, více kapitola 3.4.

3.5 Věta. Nechť I ⊆ k[x_{1}, …, x_{n}] je ideál. Pak jeho báze G = {g_{j}, …, g_{t}} je Gröbnerova právě tehdy, když pro každé i ≠ j je zbytek po dělení S(g_{i}, g_{j})/G nulový. Důkaz: “⟹” Plyne bezprostředně z důsledku 3.2.

“⟸” Uvažujme 0 ≠ f ∈ I. Potřebujeme LT f ∈ ⟨LT g_{1}, … LT g_{t}⟩. Podaří-li se zaručit, aby pro f = ∑_{i=1}^{t} h_{i}g_{i} platilo

multidegf = max{multideg(h_{i}g_{i})}

bude LT f nutně dělitelný některým LT g_{i}, a tedy G bude Gröbnerova.

Označme m_{i} := multideg(h_{i}g_{i}), δ := max{m_{1}, …, m_{t}}. Zřejmě multidegf ≤ δ. Nechť h_{1}, …, h_{t} jsou zvolena tak, že δ je minimální. Protože pracujeme s monomiálním uspořádáním, které je dobré, takové δ existuje.

Dokažme tedy, že multidegf = δ. Lze psát

f = ∑_{m_{i}=δ} h_{i}g_{i} + ∑_{m_{i}<δ} h_{i}g_{i} = ∑_{m_{i}=δ} (LT h_{i})g_{i} + ∑_{m_{i}=δ} (h_{i} − LT h_{i})g_{i} + ∑_{m_{i}<δ} h_{i}g_{i} (1)

Všechny sčítance druhé a třetí sumy mají jistě stupeň menší než δ. Připustíme-li, že multidegf < δ, potom nutně

multideg( ∑_{m_{i}=δ} (LT h_{i})g_{i}) < δ

Označme nyní c_{i}x^{α_{i}} := LT h_{i} a aplikujme lemma 3.4.

∑_{m_{i}=δ} (LT h_{i})g_{i} = ∑_{m_{i}=δ} c_{i}x^{α_{i}}g_{i} = ∑_{j,k} c_{j,k}x^{δ−γ_{j,k}}S(g_{j}, g_{k})

Z předpokladu věty a algoritmu o dělení se zbytkem získáváme

S(g_{j}, g_{k}) = ∑_{i=1}^{t}a_{i,j,k}g_{i}

a navíc multideg(a_{i,j,k}g_{i}) ≤ multidegS(g_{j}, g_{k}). Označíme-li b_{i,j,k} := x^{δ−γ_{j,k}}a_{i,j,k}, dostáváme

x^{δ−γ_{j,k}}S(g_{j}, g_{k}) = ∑_{i=1}^{t}b_{i,j,k}g_{i}

Podle druhé části lemmatu 3.4 platí

multideg(b_{i,j,k}g_{i}) ≤ multideg(x^{δ−γ_{j,k}}S(g_{j}, g_{k})) < δ

a dosazením

∑_{m_{i}=δ} (LT h_{i})g_{i} = ∑_{j,k} c_{j,k} (∑_{i=1}^{t}b_{i,j,k}g_{i}) = ∑_{i=1}^{t} (∑_{j,k} c_{j,k}b_{i,j,k}) g_{i}

přičemž platí

multideg(∑_{j,k} c_{j,k}b_{i,j,k}g_{i}) < δ pro i = 1, …, t

Dosazením do rovnosti (1) získáváme vyjádření f jako kombinace g_{1}, …, g_{t}, kde všechny sčítance jsou stupně menšího než δ. To je spor s minimální volbou δ, a tedy multidegf = δ, odkud LT f ∈ ⟨LT g_{1}, …, LT g_{t}⟩ a báze G je Gröbnerova.

□

3.2 Algoritmus

Věta 3.5 poskytuje už účinný prostředek pro zjištění, zda nějaká báze je Gröbnerova. Uvažujme například I = ⟨x + y, y − z⟩. Jediný S-polynom, který připadá v úvahu je

S(x + y, y − z) = \frac{xy}{x} (x + y) − \frac{xy}{y} (y − z) = xz + y^{2}

Dělením získáme xz + y^{2} = z(x + y) + y(y − z), a tedy daná báze je Gröbnerova.

Spolu s větou 2.17 získáváme také návod k naivnímu algoritmu pro výpočet Gröbnerovy báze. V každém jeho kroku k již zkonstruované bázi G = {f_{1}, …, f_{s}} přidáme všechny nenulové \overline{S(f_{i}, f_{j})}^{G}. Získáme tak bázi G′. Zřejme jsme nic nového nepřidali, a tak ⟨G′⟩ = ⟨G⟩. Navíc ⟨LT G⟩ ⊆ ⟨LT G′⟩.

Pokud ovšem G ⊂ G′, pak také ⟨LT G⟩ ⊂ ⟨LT G′⟩, protože přidáváme zbytky po dělení G a ty nemohou být dělitelné žádným z LT f_{1}, …, LT f_{s}, a tedy ⟨LT G⟩ obohatí. Máme tedy neklesající posloupnost ideálů

⟨LT G_{1}⟩ ⊆ ⟨LT G_{2}⟩ ⊆ ⋯

A ta má podle věty 2.17 jistý index, od kterého je stabilní. Připustíme-li, že přidávání zbytků k bázím nikdy neskončí, dostáváme se tak do sporu. Následující algoritmus počítající Gröbnerovu bázi G ideálu ⟨F ⟩ je tedy korektní Algoritmus 3.1

1. G := F, G′ := ∅

2. while G ≠ G′ 2.1. G′ := G 2.2. ∀p, g ∈ G′: p ≠ g do

2.2.1. s := \overline{S(p, q)}^{G′} 2.2.2. if s ≠ 0

2.2.2.1. G := G ∪ {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. Z hlediska čistě rutinního algoritmus také není optimální, mnoho výpočtů zbytků zbytečně opakuje, i když je zřejmé, že jakmile byly zbytky jednou vynulovány, budou nulové i v následujících krocích.

3.3 Redukované báze

Jak již bylo řečeno, Gröbnerových bází daného ideálu existuje více. Zaměříme se tedy na nalezení jednoznačné kanonické podoby, která daný ideál bude identifikovat. 3.6 Lemma. Nechť G je Gröbnerova báze ideálu I a p ∈ 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í ⟨LT I⟩ = ⟨LT G⟩. Protože LT p ∈ ⟨LT (G − {p})⟩, platí ⟨LT (G − {p})⟩ = ⟨LT G⟩. Odsud již, podle důsledku 2.16, plyne tvrzení.

□

Následující definice je tedy smysluplná. 3.7 Definice. Minimální Gröbnerovou bází ideálu I je taková Gröbnerova báze G, že pro všechna p ∈ G platí LC p = 1 a zároveň LT p ∉ ⟨LT (G − {p})⟩ Například mějme k[x, y] a <_{grlex}, I = ⟨f_{1}, f_{2}⟩ = ⟨x^{3} − 2xy, x^{2}y − 2y^{2} + x⟩. Zmíněný algoritmus dá

(f_{1}, …, f_{5}) = (x^{3} − 2xy, x^{2}y − 2y^{2} + x, −x^{2}, −2xy, −2y^{2} + x)

Přitom platí LT f_{1} = x^{3} = −x LT f_{3} a LT f_{2} = −\frac{1}{2}x LT f_{4} a tedy f_{1} a f_{2} jsou podle lematu 3.6 zbytečné.

Minimální Gröbnerova báze ještě stále není to, co hledáme, protože ideál může mít více minimálních bází. Například pro každé a je {x^{2} + axy, xy, y^{2} − 1/2x} minimální Gröbnerovou bází uvedeného ideálu. Proto následující definice 3.8 Definice. Polynom g ∈ G nazveme redukovaný pro bázi G pokud žádný z jeho monomů neleží v ⟨LT (G − {g})⟩. Redukovanou Gröbnerovou bází ideálu I potom nazveme takovou Gröbnerovu bázi G, že pro všechna p ∈ G platí LC p = 1 a zároveň p je redukovaný pro G. Zejména každá redukovaná Gröbnerova báze je minimální.

3.9 Lemma. Je-li polynom g redukovaný pro nějakou minimální Gröbnerovu bázi G ideálu I, pak je také redukovaný pro každou minimální Gröbnerovu bázi G′ téhož ideálu, která jej obsahuje.

Důkaz: Tvrzení dokážeme sporem. Uvažme G = {g_{1}, …, g_{s}}, G′ = {g′_{1}, …, g′_{t}} a g = ⋯ + m + ⋯ kde m ∈ ⟨LT (G′ − {g})⟩ (tj. g není redukovaný pro G′). Potom m = a_{1} LT g′_{1} + ⋯ + a_{t} LT g′_{t} pro nějaké vhodné polynomy a_{1}, …, a_{t}. Protože G i G′ jsou Gröbnerovy báze téhož ideálu, platí ⟨LT G⟩ = ⟨LT G′⟩, a tedy každé LT g′_{i} lze vyjádřit jako kombinaci LT g_{1}, …, LT g_{s}. Odtud už plyne m ∈ ⟨LT G⟩ a protože je G′ minimální, je m ∈ ⟨LT (G\{g})⟩, což je spor s předpokládanou redukovaností g pro G.

□

3.10 Věta. Nechť I ⊆ k[x_{1}, …, x_{n}] 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.

Důkaz: Předpokládejme, že ⟨G⟩ = I, G je Gröbnerova. S ohledem na lemma 3.6 lze předpokládat, že G je i minimální. (Algoritmus minimalizace je zřejmý, stačí testovat pouze dělitelnost vedoucích monomů.)

Nechť g ∈ G není redukovaný. Při dělení g/(G−{g}) se tedy LT g nutně dostane do zbytku, protože nemá čím být dělitelný (báze je minimální). Tedy LT (\overline{g}^{G−\{g\}}) = LT g, protože nic jiného už nemůže být vedoucím členem zbytku. Označme

g′ := \overline{g}^{G−\{g\}} a G′ := (G − \{g\}) ∪ \{g′\}

G′ je opět minimální Gröbnerovou bází ideálu I, protože ⟨LT G′⟩ = ⟨LT G⟩, tjṫaké platí ⟨LT G′⟩ = ⟨LT I⟩. Polynom g′ je zřejmě redukovaný pro G′ díky vlastnostem algoritmu pro dělení. Byl-li nějaký h ≠ g redukovaný pro G, zůstává podle předchozího lemmatu redukovaný i pro G′. Tím je dán algoritmus pro redukci Gröbnerovy báze.

Zbývá dokázat jednoznačnost. Předpokládejme dvě redukované Gröbnerovy báze G, G̃ nenulového ideálu I. Platí tedy ⟨LT G⟩ = ⟨LT I⟩ = ⟨LT G̃⟩. Protože tento ideál je monomiální, lze pro něj aplikovat Dicksonovo lemma. S odvoláním na konstrukci báze v jeho důkazu lze tvrdit, že existuje právě jedna monomiální báze monomiálního ideálu tak, že koeficienty jejích členů jsou rovny jedné a žádný z členů této báze nedělí jiný.

Podle definice minimality musí být LT G i LT G̃ právě takovou bází. Tedy LT G = LT G̃. Ke každému g ∈ G tedy exisuje právě jedno g̃ ∈ G̃ takové, že LT g = LT g̃.

Platí g − g̃ ∈ I. Protože G je Gröbnerova, platí \overline{g − g̃}^{G} = 0. Členy LT g, LT g̃ se odečtou už v g −g̃. Protože obě báze jsou redukované, nemůže být žádný ze zbývajících členů g − g̃ dělitelný kterýmkoli z LT G = LT G̃. Musí se tedy dostat do zbytku. Platí tedy

g − g̃ = \overline{g − g̃}^{G} = 0

Tím je jednoznačnost dokázána. □

Algoritmus konstrukce redukované Gröbnerovy báze vyplývající z předchozí věty sice vede k cíli, ale zdaleka není optimální. Jeho první část, algoritmus uvedený za větou 3.5 totiž může dát výsledek z mnoha polynomů, resp. polynomů vysokých stupňů či koeficientů. Optimalizace^{5} spočívá v půběžném aplikování minimalizace, normování a redukce na mezivýsledky. Sice jsme neukázali, že si to můžeme dovolit, v důkaze předchozí věty se silně využívalo toho, že báze, která je redukována, byla minimální Gröbnerova, v jistých případech ale tento postup aplikovat lze. Bohužel není jednoduché rozhodnout, kdy a který ze tří zmíněných kroků použít. Všechny dostupné algoritmy se tedy opírají o nějakou heuristiku, nicméně ke každému lze zkonstruovat ţrozumně vypadající� vstup, pro který na soudobé technice zhavaruje pro nedostatek paměti. Nepříliš povzbudivé, ale pro většinu běžných aplikací naštěstí algoritmy příliš neselhávají.

V tuto chvíli máme odpovědi na dvě z dříve položených otázek.

• f ∈ I ⟺ \overline{f}^{G} = 0 pro Gröbnerovu bázi G ideálu I (důsledek 3.2).

• Dva ideály jsou stejné právě tehdy, když mají stejné redukované Gröbnerovy

báze. V obou případech nezáleží na zvoleném monomiálním uspořádání.

5Tento termín chápeme ve smyslu informatickém, matematici by snad raději viděli vylepšení – meliorace.

3.4 Zefektivnění algoritmu

Podstatným kritériem použitým v naivní verzi algoritmu je tvrzení věty 3.5. Výpočet S-polynomu a následné dělení se zbytkem je nejbolestivější místo algoritmu z hlediska časové náročnosti. Pokusíme se nalézt ekvivalentní kritérium, které bude snadněji implementovatelné. 3.11 Definice. Zvolme pevné monomiální uspořádání. Nechť G = {g_{1}, …, g_{t}} ⊆ k[x_{1}, …, x_{n}]. Řekneme, že f ∈ k[x_{1}, …, x_{n}] se redukuje na g modulo G (píšeme f →_{G} g), pokud existují nějaká a_{1}, …, a_{t} ∈ k[x_{1}, …, x_{n}] tak, že

f = a_{1}g_{1} + ⋯ + a_{t}g_{t} + g

a zároveň multidegf ≥ multidega_{i}g_{i} pro každé i = 1, …, t. Polynomy a_{1}, …, a_{t} v definici jsou veskrze libovolné, nemusí se jednat o výsledek dělení se zbytkem. 3.12 Lemma. Nechť G = (g_{1}, …, g_{s}) ∈ (k[x_{1}, …, x_{n}])^{s}, f ∈ k[x_{1}, …, x_{n}]. Platí implikace

\overline{f}^{G} = 0 ⟹ f →_{G} 0

Opak obecně neplatí. □ Například f = xy^{2} − x, G = (xy + 1, y^{2} − 1). Potom \overline{f}^{G} = −x − y, ale přitom f = x(y^{2} − 1).

V důkazu stěžejního kritéria (věta 3.5) se ale využívá pouze vlastnosti f →_{G} 0. Odtud plyne následující 3.13 Důsledek. Báze G = {g_{1}, …, g_{t}} je Gröbnerova právě tehdy, když S(g_{i}, g_{j}) →_{G} 0 pro všechna i, j. 3.14 Věta. Nechť G ⊂ k[x_{1}, …, x_{n}] je konečná, f, g ∈ G. Nechť navíc LCM(LM f, LM g) = LM f · LM g. Potom S(f, g) →_{G} 0. Důkaz: Bez újmy na obecnosti můžeme předpokládat LC f = LC g = 1. Potom lze vyjádřit

f = LM f + p
g = LM g + q

Počítejme

S(f, g) = LM g · f − LM f · g = (g − q)f − (f − p)g = gp − fq

Přitom stupně gp i fq jsou jistě menší než stupeň S(f, g). □ 3.15 Definice. Nechť F = (f_{1}, …, f_{s}) ∈ (k[x_{1}, …, x_{n}])^{s}. Syzygy^{6} vedoucích členů nazýváme s-tici polynomů S = (h_{1}, …, h_{s}) takovou, že

∑_{i=1}^{s}h_{i} LT f_{i} = 0

Symbolem S(F) značíme množinu všech s-tic, které danou podmínku splňují.

6Česky ţspřažení�, zachycuje algebraické relace mezi vedoucími členy.

Označíme-li e_{i} jednotkové vektory ve volném modulu^{7} (k[x_{1}, …, x_{n}])^{s}, každou syzygy lze vyjádřit

S = ∑_{i=1}^{s}h_{i}e_{i}

Každý S-polynom nad {f_{i}, f_{j}} ⊆ F odpovídá prvku volého modulu

S_{i,j} := \frac{x^{γ}}{LT f_{i}} e_{i} − \frac{x^{γ}}{LT f_{j}} e_{j} kde x^{γ} = LCM(LM f_{i}, LM f_{j})

který vždy patří do S(F). Termín S-polynom pochází právě z této korespondence. Na druhé straně každou syzygy S ∈ S(F) lze vyjádřit jako lineární kombinaci výrazů S_{i,j}. 3.16 Věta. Nechť F = (f_{1}, …, f_{s}) ∈ (k[x_{1}, …, x_{n}])^{s} a S ∈ S(F). Potom lze vyjádřit

S = ∑_{i<j} u_{i,j}S_{i,j} kde u_{i,j} jsou vhodné polynomy

Důkaz je analogický důkazu lemmatu 3.4 a pro velkou ošklivost ho raději vypustíme.□ 3.17 Definice. Homogenní syzygy S ∈ S(F) stupně α ∈ ℕ_{0}^{n} je tvaru

c_{1}x^{α_{1}}e_{1} + ⋯ + c_{s}x^{α_{s}}e_{s}

kde c_{i} ∈ k a α_{i} + multidegf_{i} = α pro všechna taková i, kde c_{i} ≠ 0.

3.18 Lemma. Nechť F = (f_{1}, …, f_{s}) ∈ (k[x_{1}, …, x_{n}])^{s}. Platí

1. Každou syzygy S ∈ S(F) lze vyjádřit jednoznačně jako součet homogenních syzygy z S(F).

2. S(F) je podmodul ve volném modulu (k[x_{1}, …, x_{n}])^{s} s bází vybranou z homo-

genních syzygy S_{i,j}. □

Podmodul S(F) pro netriviální F není volný. Pro bázi S(F) nejsou nutně třeba všechny S_{i,j}. Například v lexikografickém uspořádání x < y < z pro F = {x^{2}y^{2}+z, xy^{2}−y, x^{2}y+ yz} dostáváme S_{1,2} = (1, −x, 0), S_{1,3} = (1, 0, −y), S_{2,3} = (0, x, −y), tj. S_{2,3} = S_{1,3}−S_{1,2}. 3.19 Věta. Báze G = {g_{1}, …, g_{t}} ideálu I ⊆ k[x_{1}, …, x_{n}] je Gröbnerova právě tehdy, když pro každou syzygy S = h_{1}e_{1} + ⋯ + h_{t}e_{t} v homogenní bázi S(G) platí

S · G →_{G} 0 kde S · G = ∑_{i=1}^{t} h_{i}g_{i}

Důkaz je opět analogický větě 3.5. □

Jako kritérium pro zjištění, zda daná báze je Gröbnerova tedy stačí testovat redukovatelnost jistých velmi speciálních syzygy (pouze prvků homogenní báze podmodulu S(G)) na 0.

7Zobecnění vektorového prostoru. Definice modulu je zcela stejná, jen pole skalárů zaměníme libovolným okruhem. Volné moduly jsou právě kartézské mocniny okruhu skalárů s operacemi definovanými po komponentách. Všechny vektorové prostory jsou volné díky invertibilitě nenulových skalárů.

3.20 Věta. Nechť G = (g_{1}, …, g_{t}) a 𝔖 ⊆ {S_{i,j} | 1 ≤ i < j ≤ t} je báze S(G). Předpokládejme, že pro nějaké různé g_{i}, g_{j}, g_{k} platí LT g_{k}| LCM(LM g_{i}, LM g_{j}). Jestliže S_{i,k}, S_{j,k} ∈ 𝔖, pak 𝔖 − {S_{i,j}} je také báze S(G). Důkaz: Označme x^{γ_{i,j}} := LCM(LM g_{i}, LM g_{j}). Předpokládáme, že x^{γ_{i,k}}, x^{γ_{j,k}}|x^{γ_{i,j}}. Odtud zřejmě

S_{i,j} = \frac{x^{γ_{i,j}}}{x^{γ_{i,k}}} S_{i,k} − \frac{x^{γ_{i,j}}}{x^{γ_{j,k}}} S_{j,k}

Tedy S_{i,j} je v bázi 𝔖 zbytečný. □ Důsledek 3.13 poskytuje náhradní kritérium pro výpočet Gröbnerovy báze, navíc věty 3.14 a 3.20 dává zefektivnění. V tuto chvíli již můžeme formulovat algoritmus, který je vylepšenou podobou naivního Buchbergerova. Vstupem je nějaká báze F = (f_{1}, …, f_{s}), výstupem Gröbnerova báze G. Algoritmus 3.2

1. B := {(i, j) | 1 ≤ i < j ≤ s}, G := F, t := s

2. while B ≠ ∅

2.1. vezmi libovolné (i, j) ∈ B

2.2. if LCM(LT f_{i}, LT f_{j}) ≠ LT f_{i} · LT f_{j} and notTest(f_{i}, f_{j}, B)

2.2.1. S := \overline{S(f_{i}, f_{j})}^{G} 2.2.2. if S ≠ 0

2.2.2.1. t := t + 1 2.2.2.2. f_{t} := S 2.2.2.3. G := G ∪ {f_{t}} 2.2.2.4. B := B ∪ {(i, t) | 1 ≤ i < t}

2.3. B := B − {(i, j)} Funkce Test ověřuje podmínku věty 3.20, tj. vrací true, pokud existuje nějaké k ∉ {i, j} takové, že (i, k), (j, k) ∈ B (při vhodném pořadí dvojic) a přitom zároveň platí LT f_{k}| LCM(LT f_{i}, LT f_{j}). Invarientem algoritmu je tvrzení, že B neobsahuje ty dvojice, o nichž víme, že se S-polynom redukuje na nulu (buď je to patrné z testu 2.2, nebo si to zaručíme krokem 2.2.2.3). Algoritmus zastaví v důsledku věty 2.17 (Ascending Chain Condition) a výstupem je skutečně Gröbnerova báze.

Testy jsou v souhrnu podstatně méně pracné, než výpočty S-polynomů v původním algoritmu a následné opakované dělení. Problémy okolo vhodnosti minimalizace a redukce Gröbnerovy báze v daném okamžiku výpočtu ovšem zůstávají.

Jako vedlejší produkt algoritmu získáme informace o algebraických relacích mezi polynomy vzniklé Gröbnerovy báze. Zaměřme se o něco podrobněji na manipulaci algoritmu se syzygy. Označíme-li I množinu všech dvojic (i, j) takových, že Test(f_{i}, f_{j}, B) = false v okamžiku zastavení, je množina

𝔖 := {S_{i,j} | (i, j) ∈ I}

taková báze S(G), že pro všechny její prvky S_{i,j} platí

S_{i,j} · G = S(f_{i}, f_{j}) →_{G} 0

Toto tvrzení plyne ze zpětné rekonstrukce výpočtu algoritmu, dvojice (i, j) byla totiž odstraněna z B buď tehdy, bylo-li možné S_{i,j} vyjádřit z ostatních, nebo při platnosti výše uvedené podmínky. Tedy algoritmus navíc produkuje bázi S(G).

Nějaká verze Buchbergerova algoritmu je naimplementována ve všech programových systémech zahrnujících počítačovou algebru, většinou je na něm podstatná část algebraických manipulací založena. Jako příklad uveďme systém MAPLE, který je patrně v naší síti nejdostupnější, a MATHEMATICA (ten je bohužel dostupný pouze na stroji princ.math.muni.cz).

Velice stručnou ukázku můžete vidět na obr. 6. První příkaz slouží k načtení knihovny grobner, druhý vyvolá nápovědu týkající se této knihovny, třetí počítá redukovanou Gröbnerovu bázi pro ideál uvedený za definicí 3.7 v gradovaném lexikografickém uspořádání (tdeg je zkratka pro total degree), další totéž v lexikografickém uspořádání (plex=pure lexicographic). Následující příkazy ilustrují různé chování použitých uspořádání (leadmon dává vedoucí koeficient a monom, spoly je S-polynom v zadaném uspořádání, normalf je v podstatě zbytek po dělení).

Snadná modifikace předchozí teorie (od začátku kapitoly 2) vede k rozšíření na podmoduly ve volných modulech. Pak lze aplikovat předchozí algoritmus na vlastní výsledek, dostaneme příslušnou Gröbnerovu bázi podmodulu S(G) atd. Lze ukázat, že tento postup také zastaví. Počty generátorů v získaných Gröbnerových bázích mají mimo jiné topologickou interpretaci, lze z nich odvodit např. počty k-rozměrných ţděr� ve varietě apod.

Případný zájemce může najít více podrobností v diplomové práci Zorky Velenové, která je k dispozici ve stejném adresáři, jako tyto texty.^{8} 3.4 Zefektivnění algoritmu 27

8Zorka uvádí obecné vlastnosti modulů nad komutativními okruhy, Buchbergerův algoritmus v této obecné situaci včetně zmíněné iterace a ukazuje, že tato se musí zastavit nejpozději po tolika krocích, kolik je volných proměnných. Navíc představuje specializovaný software – Macaulay.

Obr. 6: Ukázka zápisníku systému MAPLE

4 Teorie eliminací proměnných

Pro úvahy o polynomech v různých počtech proměnných budeme považovat okruh k[x_{p+1} , …, x_{n}] za podokruh k[x_{1}, …, x_{n}]. Jedná se o polynomy, v nichž se nevyskytují proměnné x_{1}, …, x_{p}. Je to skutečně podokruh, ale už ne ideál.

4.1 Eliminace

4.1 Definice. Nechť I = ⟨f_{1}, …, f_{s}⟩ ⊆ k[x_{1}, …, x_{n}]. Pro p = 1, …, n definujeme

I_{p} := I ∩ k[x_{p+1} , …, x_{n}]

Tuto množinu nazveme p-tým eliminačním ideálem. Samozřejmě I_{p} je ideálem pouze v k[x_{p+1} , …, x_{n}]. Na úrovni polynomiálních rovnic I_{p} obsahuje všechny rovnice, které jsou důsledky systému f_{1} = 0, …, f_{s} = 0 a v kterých vystupují pouze proměnné x_{p+1} , …, x_{n}. 4.2 Věta Eliminační. Nechť I ⊆ k[x_{1}, …, x_{n}] je ideál, G = {g_{1}, …, g_{m}} jeho Gröbnerova báze vzhledem k <_{lex}. Proměnné nechť jsou uspořádány x_{1} >_{lex} x_{2} >_{lex} · · ·. Potom pro každé p = 0, …, n je G_{p} := G ∩ k[x_{p+1} , …, x_{n}] Gröbnerovou bází ideálu I_{p}. Důkaz: Bez újmy na obecnosti můžeme uvažovat G_{p} = {g_{1}, …, g_{r}}. Protože G ⊆ I, je i G_{p} ⊆ I_{p}. Inkluze ⟨G_{p}⟩ ⊆ I_{p} platí triviálně. Dokážeme opačnou. Nechť f ∈ I_{p}, chceme

f = h_{1}g_{1} + ⋯ + h_{r}g_{r}

Provedeme dělení původní Gröbnerovou bází G. Protože f ∈ I, platí \overline{f}^{G} = 0, a tedy

f = h_{1}g_{1} + ⋯ + h_{r}g_{r} + h_{r+1} g_{r+1} ⋯ + h_{m}g_{m}

Každý z polynomů g_{r+1} , …, g_{m} musí obsahovat nějakou z proměnných x_{1}, …, x_{p}, jinak by byl prvkem G_{p}. Vzhledem k vlastnostem lexikografického uspořádání takovou proměnnou obsahují i LT g_{r+1} , …, LT g_{m}. Uvědomíme-li si postup algoritmu pro dělení se zbytkem a skutečnost, že v f není žádný monom obsahující některou z x_{1}, …, x_{p}, musí být h_{r+1} = ⋯ = h_{m} = 0. Tedy f ∈ ⟨G_{p}⟩.

Dokázali jsme nejen požadovanou inkluzi, ale i fakt, že dělení f/G dopadne na I_{p} stejně jako f/G_{p}. Pro 1 ≤ i < j ≤ r uvažujme S-polynomy S(g_{i}, g_{j}). Platí

\overline{S(g_{i}, g_{j})}^{G_{p}} = \overline{S(g_{i}, g_{j})}^{G} = 0

a tedy G_{p} je Gröbnerova báze ideálu I_{p}. □ Zřejmě aplikací eliminační věty na minimální resp. redukovanou Gröbnerovu bázi získáme opět bázi minimální resp. redukovanou.

Jediná v důkazu využitá vlastnost lexikografického uspořádání je tvrzení, že z některých proměnných objevujících se v polynomu se ta, která je v daném uspořádání největší, objeví i ve vedoucím členu. To je ovšem podstatně slabší požadavek, než definice lexikografického uspořádání. Proto lze při skutečných implementacích používat uspořádání v podstatě gradované s touto vlastností zajištěnou. Dosáhne se tak většinou efektivnějších výpočtů, protože čisté lexikografické uspořádání zpravidla vede k nepříjemnému nárůstu exponentů.

4.2 Věta o rozšíření

Společnou myšlenkou následujících úvah je chápání k[x_{1}, …, x_{n}] jako k[x_{2}, …, x_{n}][x_{1}], tedy polynom v proměnných x_{1}, …, x_{n} považujeme za polynom v jedné proměnné x_{1} a koeficientech z k[x_{2}, …, x_{n}]. To ovšem není pole, ale pouze okruh. Proto místo něj pro účely důkazů použijeme odpovídající podílové těleso k(x_{2}, …, x_{n}) a na závěr vždy ukážeme, že se vše podstatné stejně odehrálo v k[x_{2}, …, x_{n}].

4.3 Věta O rozšíření. Nechť I = ⟨f_{1}, …, f_{s}⟩ ⊆ ℂ[x_{1}, …, x_{n}]. Pro každé i = 1, …, s položme

f_{i} := g_{i}(x_{2}, …, x_{n})x_{1}^{N_{i}} + členy nižšího stupně v x_{1}

kde g_{i} ∈ ℂ[x_{2}, …, x_{n}] je nenulový. Nechť (a_{2}, …, a_{n}) je prvek variety V (I_{1}) dané prvním eliminačním ideálem. Pak platí

(a_{2}, …, a_{n}) ∉ 𝔙(g_{1}, …, g_{s}) ⟹ ∃a_{1} ∈ ℂ: (a_{1}, a_{2}, …, a_{n}) ∈ V (I)

Ke korektnímu důkazu se časem propracujeme (kapitola 4.4), zatím jen ilustrativní příklad. Nechť f = xy − 1, g = xz − 1, I = ⟨f, g⟩. Gröbnerova báze je y − z, xz − 1, proto podle eliminační věty I_{1} = ⟨y − z⟩. Pro každé a ∈ ℂ platí (a, a) ∈ V (I_{1}). Vyjádříme polynomy y − z, xz − 1 podle stupně v x

y − z = (y − z)x^{0}
xz − 1 = zx^{1} − 1

Zřejmě pro a ≠ 0 existuje rozšíření (1/a, a, a) ∈ V (I).

Rozšíření znamená postup do značné míry opačný k eliminaci. K varietě prvního eliminačního ideálu (předpokládáme, že tu už určíme snáz) hledáme hodnoty pro x_{1}, aby výsledný bod padl do původní variety. Celý problém lze chápat jako hledání společného kořene polynomů po dosazení už známých n − 1 složek.

4.3 Existence společných kořenů

4.4 Definice. Nechť k je pole. Polynom f ∈ k[x_{1}, …, x_{n}] nazveme ireducibilní nad k, platí-li f ∉ k a f není součinem nekonstantních polynomů.

4.5 Lemma. Nechť f ∈ k[x_{1}, …, x_{n}] a platí f|gh. Pokud je f ireducibilní, pak f|h nebo f|g.

Důkaz je jednoduchý ale technicky zdlouhavý a opírá se o zmíněnou myšlenku rozšíření na podílové těleso. Vede se indukcí k počtu proměnných. □ 4.6 Lemma. Nechť f, g mají kladný stupeň v x_{1}. Potom mají společný faktor v k[x_{2}, …, x_{n}][x_{1}] s kladným stupněm v x_{1} právě tehdy, když mají takový faktor v k(x_{2}, …, x_{n})[x_{1}]. Důkaz: Implikace od případu v k[x_{2}, …, x_{n}][x_{1}] k k(x_{2}, …, x_{n})[x_{1}] je zcela zřejmá. Zaměřme se tedy na opačnou. Pišme f = h̃f̃_{1}, g = h̃g̃_{1} kde h̃, f̃_{1}, g̃_{1} ∈ k(x_{2}, …, x_{n})[x_{1}]. Dále za d označme společný jmenovatel ţzlomků� h̃, f̃_{1}, g̃_{1} a položme

h := dh̃, f_{1} := df̃_{1}, g_{1} := dg̃_{1}

Ty už nutně padnou do k[x_{2}, …, x_{n}][x_{1}]. Platí d^{2}f = hf_{1}, d^{2}g = hg_{1} a opět se pohybujeme v k[x_{2}, …, x_{n}][x_{1}]. Protože h̃ = h/d a d ∈ k[x_{2}, …, x_{n}], musí nutně existovat ireducibilní faktor h_{1} v h s kladným stupněm v x_{1}.

Víme, že h_{1}|d^{2}f. Protože je ireducibilní, musí dělit d nebo f. Ale d nemá s x_{1} nic společného, a tak nutně h_{1}|f. Dělitelnost h_{1}|g se ukáže analogicky. □ 4.7 Věta. Každý nekonstantní polynom f ∈ k[x_{1}, …, x_{n}] lze psát jako f = f_{1} ⋯ f_{r} součin ireducibilních polynomů. Toto vyjádření je jednoznačné až na permutaci faktorů a násobky skalárem. Důkaz: Tvrzení v případě polynomů jedné proměnné je všeobecně známé. Na základě předchozího lemmatu lze zobecnit i do okruhu polynomů více proměnných. □ 4.8 Lemma. Nechť f, g ∈ k[x], degf = l > 0, degg = m > 0. Polynomy f, g mají společný faktor právě tehdy, když ∃A, B ∈ k[x] tak, že

• A, B nejsou oba nulové

• degA < m, degB < l

• Af + Bg = 0 Důkaz: “⟹” Pišme f = hf_{1}, g = hg_{1}. Pak degf_{1} < l, degg_{1} < m. Platí

0 = g_{1}f_{1} − f_{1}g_{1} = g_{1}hf_{1} − f_{1}hg_{1} = g_{1}f − f_{1}g

což bylo třeba dokázat.

“⟸” Sporem. Předpokládejme, že f, g nemají společný faktor. Nechť například B ≠ 0. Platí GCD(f, g) = 1. Z Bezoutovy rovnosti dostáváme

Ãf + B̃g = 1 ⟹ B = (Ãf + B̃g)B = ÃBf − B̃Af = (ÃB − B̃A)f

a tedy degB ≥ l, což je spor.

□

Označme členy polynomů A, B z předchozího lemmatu

A = c_{0}x^{m−1} + ⋯ + c_{m−1}
B = d_{0}x^{l−1} + ⋯ + d_{l−1}

Porovnáme-li koeficienty u jednotlivých mocnin x při tomto vyjádření třetí podmínky lemmatu, dostáváme homogenní systém rovnic

a_{0}c_{0} + b_{0}d_{0} = 0
a_{1}c_{0} + a_{0}c_{1} + b_{1}d_{0} + b_{0}d_{1} = 0
⋮
a_{l}c_{m−1} + b_{m}d_{l−1} = 0

Ten má nenulové řešení (v proměnných c_{0}, … c_{m−1}, d_{0}, …, d_{l−1}) právě tehdy, když je jeho matice singulární. Pro ni zavádíme zvláštní označení.

4.9 Definice. Nechť f, g ∈ k[x] jsou kladného stupně. Označme

f = a_{0}x^{l} + ⋯ + a_{l}
g = b_{0}x^{m} + ⋯ + b_{m}

Sylvesterovou maticí polynomů f, g rozumíme matici Syl(f, g, x) řádu m + l tvaru

( \begin{matrix}a_{0} & 0 & ⋯ & 0 & b_{0} & 0 & ⋯ & 0 \\ a_{1} & a_{0} & & ⋮ & b_{1} & b_{0} & & ⋮ \\ a_{2} & a_{1} & ... & 0 & b_{2} & b_{1} & ... & 0 \\ ⋮ & & & a_{0} & ⋮ & & & b_{0} \\ a_{l} & & & & b_{m} \\ 0 & a_{l} & & ⋮ & 0 & b_{m} & & ⋮ \\ ⋮ & & ... & & ⋮ & & ... \\ 0 & ⋯ & 0 & a_{l} & 0 & ⋯ & 0 & b_{m} \end{matrix} )

Rezultantem polynomů f, g vzhledem k proměnné x nazveme její determinant. Značíme Res(f, g, x). Pro f, g ∈ k[x] kladných stupňů je Res(f, g, x) zřejmě prvkem pole k. Lze jej chápat jako polynom v proměnných a_{0}, …, a_{l}, b_{0}, …, b_{m} s celočíselnými koeficienty. 4.10 Důsledek. Polynomy f, g ∈ k[x] mají společný faktor (tedy i kořen pro algebraicky uzavřené k) právě tehdy, když Res(f, g, x) = 0. Důkaz: Plyne bezprostředně z lemmatu 4.8 a definice rezultantu. □

4.11 Lemma. Nechť f, g ∈ k[x] jsou polynomy kladného stupně. Pak existují taková A, B ∈ k[x] tak, že platí

Af + Bg = Res(f, g, x)

Důkaz: Pro Res(f, g, x) = 0 je tvrzení přímým důsledkem lemmatu 4.8. Uvažujme tedy případ Res(f, g, x) ≠ 0. Z Bezoutovy rovnosti plyne existence Ã, B̃, takových, že Ãf + B̃g = 1. Označme jednotlivé členy těchto polynomů

Ã = c_{0}x^{m−1} + ⋯ + c_{m−1}
B̃ = d_{0}x^{l−1} + ⋯ + d_{l−1}

Porovnáme-li koeficienty u jednotlivých mocnin proměnné x v Bezoutově rovnosti, získáme systém

a_{0}c_{0} + b_{0}d_{0} = 0
a_{1}c_{0} + a_{0}c_{1} + b_{1}d_{0} + b_{0}d_{1} = 0
⋮
a_{l}c_{m−1} + b_{m}d_{l−1} = 1

Chápeme-li tento systém v proměnných c_{0}, …, c_{m−1}, d_{0}, …, d_{l−1}, je jeho matice právě Syl(f, g, x). Protože předpokládáme nenulovost rezultantu, lze aplikovat Cramerovo pravidlo a získáváme

Ã = \frac{A}{Res(f, g, x)}  B̃ = \frac{B}{Res(f, g, x)}

pro nějaká vhodná A, B. Odtud již plyne požadovaná rovnost. □

Rezultant lze poměrně efektivně vypočítat modifikací Euklidova algoritmu. Zřejmě platí

Res(f, g, x) = (−1)^{lm} Res(g, f, x)

Dá se ukázat, že pokud f = qg + r, kde degr < degg (krok algoritmu), pak

Res(f, g, x) = Res(r, g, x) · b_{0}^{l−deg r} kde b_{0} = LC g

Návod k důkazu je uveden v rámci cvičení ke kapitole týkající se rezultantů v [2].

S ohledem na myšlenku předloženou na začátku kapitoly můžeme zobecnit definici rezultantu na polynomy ve více proměnných. Res(f, g, x_{1}) definujeme zcela analogicky, jen polynomy f, g chápeme jako polynomy v proměnné x_{1} a koeficientech z k[x_{2}, …, x_{n}]. 4.12 Věta. Nechť f, g ∈ k[x_{1}, …, x_{n}] jsou kladného stupně v x_{1}. Pak

1. Res(f, g, x_{1}) ∈ I_{1}, kde I_{1} je první eliminační ideál ⟨f, g⟩.

2. Res(f, g, x_{1}) = 0 právě tehdy, když f, g mají společný faktor kladného stupně

v x_{1}. Důkaz: Uvažujme opět f, g ∈ k[x_{2}, …, x_{n}][x_{1}] ⊆ k(x_{2}, …, x_{n})[x_{1}]. To už je pole, a tak lze aplikovat důsledek 4.10 a lemma 4.11.

1. Pokud Res(f, g, x_{1}) = 0, je tvrzení zřejmé. Přímo z definice rezultantu plyne Res(f, g, x_{1}) ∈ k[x_{2}, …, x_{n}]. Podle lemmatu 4.11 existují nějaká A, B ∈ k(x_{2}, …, x_{n})[x_{1}] tak, že Res(f, g, x_{1}) = Af + Bg, což už je i prvek ⟨f, g⟩. Zbývá ukázat, že A, B ∈ k[x_{2}, …, x_{n}][x_{1}]. Ale tyto polynomy jsou konstruovány v důkazu lemmatu 4.11 tak, že tuto podmínku splňují.

2. Lemma 4.6 umožňuje pohybovat se bez problémů mezi okruhem k[x_{2}, …, x_{n}] a

polem k(x_{2}, …, x_{n}). V poli je ale druhá část tvrzení zřejmá.

□

4.4 Důkaz věty o rozšíření

Nyní máme k dispozici nástroje dostatečně silné pro důkaz věty o rozšíření (4.3). Pro jednoduchost ho detailně provedeme pouze pro ideály generované jen dvěma polynomy. Důkaz 4.3: Uvažujme f, g ∈ ℂ[x_{1}, …, x_{n}] ⊆ ℂ(x_{2}, …, x_{n})[x_{1}] s vedoucími koeficienty a_{0}, b_{0}. Tradičně označíme I_{1} := ⟨f, g⟩ ∩ ℂ[x_{2}, …, x_{n}]. Chceme ukázat, že pro každé (c_{2}, …, c_{n}) ∈ V (I_{1}) − 𝔙(a_{0}, b_{0}) existuje c_{1} ∈ ℂ tak, že (c_{1}, …, c_{n}) ∈ V (⟨f, g⟩).

Označme c := (c_{2}, …, c_{n}) a konvenčně pišme f(x_{1}, c) = f(x_{1}, c_{2}, …, c_{n}). Stačí ukázat

Res(f(x_{1}, c), g(x_{1}, c)) = 0

Potom už podle předchozího bude existovat společný kořen c_{1} ∈ ℂ a (c_{1}, …, c_{n}) padne do 𝔙(f, g).

Předpokládejme nejprve, že a_{0}(c) ≠ 0 a zároveň b_{0}(c) ≠ 0. Označme h := Res(f, g, x_{1}). Podle věty 4.12 platí h ∈ I_{1}, a tedy zejména h(c) = 0. Dosazením c za (x_{2}, …, x_{n}) získáváme

Res(f(x_{1}, c), g(x_{1}, c)) = h(c) = 0

Uvažujme nyní např. b_{0}(c) = 0, a_{0}(c) ≠ 0. Potom stupeň g(x_{1}, c) v x_{1} je menší než m a h(c) nelze použít jako v předchozím případě. Můžeme ovšem uvážit jinou bázi ideálu ⟨f, g⟩, např. ⟨f, g +x_{1}^{N}f⟩ a volit N tak velké, aby stupeň x_{1}^{N}f v x_{1} byl větší, než stupeň g. Potom bude vedoucí koeficient g + x_{1}^{N}f roven a_{0} a je možno aplikovat první část důkazu. □

Uvažme například ideál I = ⟨x^{2}y−1, x^{2}z−1⟩. První eliminační ideál je potom ⟨y−z⟩. Varieta V (I) je ţjakási hyperbola� o dvou větvích položená v rovině y = z. Tato rovina je vlastně V (I_{1}). Věta o rozšíření tvrdí, že ke každé dvojici (y, z) ∈ V (I_{1}) s vyjímkou jistých bodů nalezneme hodnotu pro x, abychom získali bod původní variety. Jinými slovy na téměř každé přímce dané dvojicí y, z (tedy volné v x) lze najít bod patřící do původní variety. Problematickým bodem v tomto příkladě je právě y = z = 0, k němuž rozšíření neexistuje. Obecně se jedná právě o ty body, které neleží v projekci původní variety podle proměnné x_{1}, ale padnou do nejmenší afinní variety, která tuto projekci obsahuje (viz. kapitola 4.6).

Obecný důkaz věty o rozšíření je v podstatě analogický předchozímu, je však technicky náročný. Pro ideál I = ⟨f_{1}, …, f_{s}⟩ se vytvoří polynom g = u_{2}f_{2} + ⋯ + u_{s}f_{s} ∈ ℂ[u_{2}, …, u_{s}, x_{1}, …, x_{m}]. Uvažuje se rezultant

Res(f_{1}, g, x_{1}) = ∑_{α} h_{α}(x_{2}, …, x_{n}) · u^{α} kde u = (u_{2}, …, u_{s})

a porovnávají se koeficienty u^{α}. Věřme a detaily přenechejme jen vážným zájemcům.

4.5 Hilbertova věta o nulách

4.13 Věta Hilbertova o nulách. Nechť pole k je algebraicky uzavřené, f, f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}]. Platí

f ∈ ℑ(𝔙(f_{1}, …, f_{s})) ⟺ f^{m} ∈ ⟨f_{1}, …, f_{s}⟩ pro vhodné m ∈ ℕ_{0}

Důkaz: Nejprve dokážeme, že každý ideál I ⊆ k[x_{1}, …, x_{n}] splňuje

V (I) = ∅ ⟺ I = k[x_{1}, …, x_{n}] (2)

To je bezprostřední důsledek věty pro f = 1. V závěru ukážeme, že se jedná o ekvivalentní tvrzení.

Každé algebraicky uzavřené pole je nekonečné. Jinak by stačilo uvažovat polynom (x − a_{1}) ⋯ (x − a_{n}) + 1, který nemá kořen – spor. Proto implikace zprava doleva platí triviálně. Důkaz zleva doprava vedeme indukcí. Předpokládejme V (I) = ∅.

1. Nechť n = 1. Pak I = ⟨f_{1}⟩ podle důsledku 1.13. Protože f_{1} nemá kořeny a k je algebraicky uzavřené, musí být f_{1} konstanta. Tedy ⟨f_{1}⟩ = k[x_{1}].

2. Nechť I = ⟨f_{1}, …, f_{s}⟩. Je-li některý z f_{1}, …, f_{s} konstanta, je tvrzení zřejmé. Předpokládejme tedy nekonstantní polynomy. Předpokládejme navíc, že f_{1} je velmi speciálního tvaru

f_{1}(x_{1}, …, x_{n}) = cx_{1}^{N} + členy s nižším stupněm v x_{1}

kde c ∈ k, c ≠ 0 je konstanta. Posléze ukážeme, že si tento předpoklad můžeme dovolit. Z věty o rozšíření (4.3) díky speciálnímu tvaru f_{1} plyne π_{1}(V (I)) = V (I_{1}). Předpokládáme V (I) = ∅, a tedy i π_{1}(V (I)) = ∅. I_{1} už je pouze v n−1 proměnné, a tedy podle indukčního předpokladu 1 ∈ I_{1}. Odtud zřejmě i 1 ∈ I.

Zbývá ukázat, že v obecném případě umíme problém redukovat tak, abychom mohli předpokládat speciální tvar f_{1}. K tomu užijeme homomorfismus k[x_{1}, …, x_{n}] → k[x̃_{1}, …, x̃_{n}]

x_{1} := x̃_{1}
x_{2} := x̃_{2} + a_{2}x̃_{1}
⋮
x_{n} := x̃_{n} + a_{n}x̃_{1}

Pokud neexistuje řešení systému rovnic po této transformaci, neexistovalo ani před ní, pokud patří 1 do obrazu nějaké množiny, patří i do vzoru (vše jsou vlastnosti homomorfismu).

Tyto transformační rovnice s neznámými parametry dosadíme do f_{1}. Chtěli bychom, aby koeficient členu nejvyššího stupně v x_{1} byl konstantní. Přitom monom s nejvyšším stupněm v x̃_{1} může vzniknout z monomu s nejvyšším součtem stupňů ve všech proměnných x_{i}. Požadavek, aby jeho koeficient nezávisel na ostatních proměnný je polynomiálních podmínka na parametry a_{2}, …, a_{n}.

Tím je dokázáno tvrzení (2). Zbývá ukázat, že implikuje dokazovanou větu. Nejprve směr tvrzení zprava doleva. Pokud f^{m} ∈ ⟨f_{1}, …, f_{s}⟩, také f^{m} ∈ ℑ(𝔙(f_{1}, …, f_{s})), to znamená (f(a))^{m} = 0 pro všechna a ∈ 𝔙(f_{1}, …, f_{s}). Protože k je obor integrity, musí nutně i f(a) = 0, a tedy f ∈ ℑ(𝔙(f_{1}, …, f_{s})).

Obráceně chceme f^{m} = ∑_{i=1}^{s} h_{i}f_{i}. Uvažme ideál

Ĩ = ⟨f_{1}, …, f_{s}, 1 − yf⟩ ⊂ k[x_{1}, …, x_{n}, y].

Zvolme a = (a_{1}, …, a_{n+1} ) libovolné. Pokud (a_{1}, …, a_{n}) ∉ V (I), pak zřejmě a ∉ V (Ĩ). Pokud naopak (a_{1}, …, a_{n}) ∈ V (I), platí i f(a_{1}, …, a_{n}) = 0, a tedy 1 − yf se určitě nenuluje na a. Dohromady V (Ĩ) = ∅, tedy 1 ∈ Ĩ a lze psát

1 = ∑_{i=1}^{s}p_{i}(x_{1}, …, x_{n}, y)f_{i} + q(x_{1}, …, x_{n}, y)(1 − yf)

Za y dosadíme 1/f(x_{1}, …, x_{n}). Potom v k(x_{1}, …, x_{n}) dostáváme rovnost

1 = ∑_{i=1}^{s}p_{i}(x_{1}, …, x_{n}, \frac{1}{f(x_{1},...,x_{n})})f_{i}

Vynásobením f^{m} s m dostatečně velkým získáme požadovanou rovnost. □

4.6 Věta o uzávěru

Připomeňme, že projekci ţodřezávající� prvních k souřadnic značíme π_{k}. 4.14 Lemma. Nechť I_{k} = ⟨f_{1}, …, f_{s}⟩ ∩ C[x_{k+1} , …, x_{n}]. Potom

π_{k}(𝔙(⟨f_{1}, …, f_{s}⟩)) ⊆ V (I_{k})

Důkaz: Nechť f ∈ I_{k} je libovolný. Je to polynom pouze v proměnných x_{k+1} , …, x_{n}. Uvažme libovolné (a_{1}, …, a_{n}) ∈ 𝔙(⟨f_{1}, …, f_{s}⟩). Protože f ∈ ⟨f_{1}, …, f_{s}⟩, jistě platí f(a_{k+1} , …, a_{n}) = 0, a tedy f(π_{k}(a_{1}, …, a_{n})) = 0. Tím je inkluze dokázána. □ Obecně π_{k}(V) nemusí být varieta, tj. inkluze je ostrá. Viz příklad u věty o rozšíření. 4.15 Lemma. Nechť V = 𝔙(f_{1}, …, f_{s}) ⊆ ℂ^{n}, I_{1} je první eliminační ideál a g_{i} jako ve větě o rozšíření. Pak v ℂ^{n−1} platí

V (I_{1}) = π_{1}(V) ∪ (𝔙(g_{1}, …, g_{n}) ∩ V (I_{1}))
□

Tedy varieta daná prvním eliminačním ideálem se skládá právě z projekce původní variety a oné ţméně rozměrné� množiny vymykajících se bodů, které dotvoří projekci na afinní varietu.

S právě diskutovanými vlastnostmi souvisí pojem Zariského topologie. To je taková topologie na k^{n}, kde k je pole, že uzavřené množiny jsou právě nulové množiny systémů racionálních lomených funkcí. 4.16 Věta O uzávěru. Nechť V = 𝔙(f_{1}, …, f_{s}) ⊆ ℂ^{n} a I_{k} je k-tý eliminační ideál. Potom platí

1. V (I_{k}) je nejmenší afinní varieta obsahující π_{k}(V), tedy uzávěr v Zariského topologii.

2. Pokud V ≠ ∅, pak existuje afinní varieta W ⊂ V (I_{k}) tak, že V (I_{k}) − W ⊆ π_{k}(V). Důkaz: Potřebujeme dokázat V (I_{k}) = V (ℑ(π_{k}(V))). Uvažme libovolný f ∈ ℑ(π_{k}(V)) ⊆ ℂ[x_{k+1} , …, x_{n}]. Zřejmě f(a_{k+1} , …, a_{n}) = 0 pro všechna (a_{k+1} , …, a_{n}) ∈ π_{k}(V), a tedy také f(a_{1}, …, a_{n}) = 0 v ℂ[x_{1}, …, x_{n}] pro všechna (a_{1}, …, a_{n}) ∈ V. Podle Hilbertovy věty o nulách tedy existuje m tak, že f^{m} ∈ ⟨f_{1}, …, f_{s}⟩. Protože f nezávisí na x_{1}, …, x_{k}, nezávisí na nich ani f^{m}.

Uvažujme nyní libovolné a ∈ V (I_{k}). Víme, že ke každému polynomu f ∈ ℑ(π_{k}(V)) existuje m tak, že f^{m} ∈ I_{k}. Pokud f^{m}(a) = 0 musí i f(a) = 0, a tedy i a ∈ V (ℑ(π_{k}(V))). Opačná inkluze je zřejmá, protože I_{k} ⊆ ℑ(π_{k}(V)).

Důkaz druhé části věty patří k netriviálním a opět formálně komplikovaným. Provedeme ho jen pro případ k = 1. Podle lemmatu 4.15 můžeme vyjádřit

V (I_{1}) = π_{1}(V) ∪ \underbrace{(𝔙(g_{1}, …, g_{s}) ∩ V (I_{1}))}_{W}

Toto W je zřejmě afinní varieta. Pokud W ⊂ V (I_{1}), je vše v pořádku. Pro případ W = V (I_{1}) lze, podobně jako v důkazu věty 4.3, ţzlepšit� generátory, aby použitá báze indukovala požadovanou vlastnost. K tomu budeme potřebovat následující lemma.

4.17 Lemma. Pokud W = V (I_{1}), pak V = 𝔙(f_{1}, …, f_{s}, g_{1}, …, g_{s}). Důkaz: Protože se jedná o variety, je zřejmě 𝔙(f_{1}, …, f_{s}, g_{1}, …, g_{s}) ⊆ V. Zvolme libovolně (a_{1}, …, a_{n}). Protože π_{1}(V) ⊆ V (I_{1}), je (a_{2}, …, a_{n}) ∈ V (I_{1}) = W. Tedy nutně z definice W platí g_{i}(a_{2}, …, a_{n}) = 0 pro všechna i. Odtud opačná inkluze.

□

Vraťme se k vlastnímu důkazu věty. Definujme nový ideál Ĩ := ⟨f_{1}, …, f_{s}, g_{1}, …, g_{s}⟩. Ten podle lemmatu určuje stejnou varietu. Polynomy g_{i} už mají nulový stupeň v x_{1}, f_{i} můžeme nahradit f̃_{i} := f_{i} − g_{i}x_{1}^{N_{i}}, které mají ostře menší stupeň v x_{1}.

Podle lemmatu 4.15 získáme nový rozklad a nové W̃. Pokud bude opět W = V (I_{1}), celý postup zopakujeme. Po konečném počtu kroků buď dojdeme k žádané vlastnosti anebo vynulujeme stupeň v x_{1}. To ale znamená π_{1}(V) = V (I_{1}) a můžeme volit W = ∅, což je také afinní varieta. □ V příkladu na straně 33 je varieta W právě bod y = z = 0. Věta byla sice pro jednoduchost dokázána pro okruhy polynomů nad ℂ, ale zřejmě platí pro libovolné algebraicky uzavřené pole.

4.7 Korespondence ideálů a variet

Sumarizujme na závěr výsledky celé teorie s ohledem na korespondenci algebraických struktur (ideály) a geometrických objektů (variety) a na odpovídající si operace na nich. 4.18 Definice. Radikálovým ideálem ideálu I ⊆ k[x_{1}, …, x_{n}] nazveme

\sqrt{I} := ⟨f ∈ k[x_{1}, …, x_{n}] | ∃m ∈ ℕ: f^{m} ∈ I⟩

Jako důsledek Hilbertovy věty o nulách dostáváme 4.19 Důsledek. Je-li k algebraicky uzavřenmé, pak pro každou varietu 𝔙(f_{1}, …, f_{s}) platí

ℑ(𝔙(f_{1}, …, f_{s})) = \sqrt{⟨f_{1}, …, f_{s}⟩}

4.20 Definice. Ideál I ⊆ k[x_{1}, …, x_{n}] nazýváme prvoideálem, jestliže pro každé f ·g ∈ I je už f ∈ I nebo g ∈ I. Ideál je vlastní, pokud {0} ≠ I ⊂ k[x_{1}, …, x_{n}], maximální, není-li obsažen v žádném ostře větším vlastním ideálu.

4.21 Definice. Afinní varieta V ⊆ k^{n} se nazývá ireducibilní, jestliže kdykoli V = V_{1} ∪ V_{2}, kde V_{1}, V_{2} jsou afinní variety, platí už V = V_{1} nebo V = V_{2}.

To je vcelku přirozený pojem. Například varieta 𝔙(xy) ⊆ ℝ^{2} není ireducibilní, tvoří ji dvě přímky, které jsou pochopitelně afinní variety. V tuto chvíli se nabízí hypotéza, dokázaná v následující větě. 4.22 Věta. Afinní varieta V ⊆ k^{n} je ireducibilní právě tehdy, když ℑ(V) je prvoideál. Důkaz: “⟹” Nechť f · g ∈ ℑ(V) a označme

V_{1} := V ∩ 𝔙(f)
V_{2} := V ∩ 𝔙(g)

To jsou zřejmě afinní variety. Platí V = V_{1} ∪ V_{2}, protože na každém bodě V se musí nulovat alespoň jeden z f, g. Předpokládáme, že V je ireducibilní, nechť tedy například V = V_{1}. Určitě f ∈ ℑ(V_{1}), a tedy i f ∈ ℑ(V). To znamená, že ℑ(V) je prvoideál.

“⟸” Předpokládejme naopak, že ℑ(V) je prvoideál, V = V_{1} ∪ V a například V_{1} ≠ V. Odtud ostrá inkluze ℑ(V) ⊂ ℑ(V_{1}). Určitě také ℑ(V) ⊆ ℑ(V_{2}). Zvolme f ∈ ℑ(V_{1}) − ℑ(V), g ∈ ℑ(V_{2}). Protože V = V_{1} ∪ V_{2}, platí f · g ∈ ℑ(V). To je prvoideál, a tedy f ∈ ℑ(V), což jsme vyloučili volbou f, anebo g ∈ ℑ(V). Ukázali jsme ℑ(V_{2}) ⊆ ℑ(V). Tedy tyto ideály se rovnají a musí se rovnat i variety V a V_{2}.

□

Všechny závěry jsou shrnuty v tabulce 1. K ní je nutné jen poznamenat, že při projekci musíme uvažovat uzávěr, protože, jak již víme, projekce samotná nemusí ještě být varieta.

Algebraické objekty  Geometrické objekty
radikálový ideál  varieta
I  ⟶  V (I)
ℑ(V)  ⟵  V
součet ideálů  průnik variet
I + J  ⟶  V (I) ∩ V (J)
\sqrt{ℑ(V) + ℑ(W)}  ⟵  V ∩ W
součin ideálů  sjednocení variet
I · J  ⟶  V (I) ∪ V (J)
\sqrt{ℑ(V) · ℑ(W)}  ⟵  V ∪ W
eliminace proměnných  projekce variety
\sqrt{I ∩ k[x_{k+1} , …, x_{n}]} ⟷ \overline{π_{k}(V (I))}
prvoideál  ireducibilní varieta
maximální ideál  jednobodová varieta
Ascending Chain Condition  Descending Chain Condition

Tabulka 1: Korespondence ideálů a variet

5 Aplikace

5.1 Řešitelnost systémů rovnic

5.1 Věta. Systém f_{1} = 0, …, f_{s} = 0, kde f_{1}, …, f_{s} ∈ k[x_{1}, …, x_{n}] a k je algebraicky uzavřené pole, nemá řešení právě tehdy, když 1 ∈ ⟨f_{1}, …, f_{s}⟩, tj. redukovaná Gröbnerova báze tohoto ideálu je {1}. Důkaz: Pokud je varieta prázdná, lze tvrdit, že libovolný polynom se nuluje na všech jejích bodech^{9}, tedy i polynom 1. Potom ale, podle Hilbertovy věty o nulách (4.13), platí 1^{m} ∈ ⟨f_{1}, …, f_{s}⟩ pro nějaké m.

Naopak je-li 1 ∈ ⟨f_{1}, …, f_{s}⟩, musí to být nutně celý okruh. Protože pole k předpokládáme algebraicky uzavřené a tedy nekonečné, varieta, kde se nulují všechny polynomy, je už triviálně prázdná. □ Tedy o daném systému algebraických rovnic lze algoritmicky rozhodnout, zda má nebo nemá řešení. Alternativní metodou pro tohoto rozhodnutí je přímé použití aparátu rezultantů, patrně se tak dosáhne i lepší časové složitosti. Tato problematika ale není naším cílem, a tak případné zájemce odkazujeme na literaturu. 5.2 Věta. Nechť V = V (I) ⊆ ℂ^{n} je afinní varieta a < libovolné monomiální uspořádání. Pak následující tvrzení jsou ekvivalentní.

1. V je konečná

2. ∀i = 1, …, n ∃m_{i} ∈ ℕ_{0}: x_{i}^{m_{i}} ∈ ⟨LT I⟩

3. Nechť G je redukovaná Gröbnerova báze I. Pak

∀i = 1, …, n ∃m_{i} ∈ ℕ_{0}: x_{i}^{m_{i}} = LM g pro některé g ∈ G

4. Faktorokruh^{10} ℂ[x_{1}, …, x_{n}]/I nad ℂ je konečně rozměrný vektorový prostor. Důkaz: “1 ⟹ 2” Pokud je V = ∅, potom 1 ∈ I a můžeme brát m_{i} = 0 pro každé i.

Předpokládejme tedy V ≠ ∅ a zvolme i. Nechť a_{j} ∈ ℂ pro j = 1, …, k jsou různé i-té souřadnice bodů V. Polynom

f(x_{i}) := ∏_{j=1}^{k}(x_{i} − a_{j})

je nulový ve všech bodech V. Podle Hilberovy věty o nulách existuje m tak, že f^{m} ∈ I. Odtud už x_{i}^{km} ∈ ⟨LT I⟩ a stačí položit m_{i} = km.

“2 ⟹ 3” Předpokládáme, že x_{i}^{m_{i}} ∈ ⟨LT I⟩. Protože G je Gröbnerova, platí ⟨LT I⟩ = ⟨LT G⟩. Ovšem jedná se o monomiální ideály, a tak musí existovat g ∈ G takové, že LT g|x_{i}^{m_{i}} (přímo z definice 2.9). Tedy pro nějaké vhodné m′_{i} musí být LT g = x_{i}^{m′_{i}}.

9Poněkud krkolomné, ale podrobným rozebráním důkazu Hilbertovy věty o nulách pro tento případ tvrzení skutečně dostaneme

10Připomeňme, že faktorokruh ℂ[x_{1}, …, x_{n}]/I nad ℂ je množina tříd ekvivalence f ∼ g ⟺ f − g ∈ I.

“3 ⟹ 2” je zcela triviální.

“2 ⟹ 4” Nechť x_{i}^{m_{i}} ∈ ⟨LT I⟩. Definujme vektorový prostor nad ℂ

S := ⟨x^{α} | x^{α} ∉ ⟨LT I⟩⟩

Zde je na místě podotknout, že se nejedná o tytéž ţzobáky�. Vnější znamenají generování vektorového prostoru, tedy máme k použití sčítání uvnitř a násobení skalárem (tj. komplexním číslem), vnitřní generují ideál, tedy se sčítá uvnitř a násobí zvenku polynomem.

Například pro I = ⟨x^{2}, y^{2}⟩ je S = ⟨1, x, y, xy⟩. Vzhledem k předpokladu je S konečněrozměrný nanejvýš dimenze m_{1} ⋯ m_{n}. Ukážeme, že zobrazení

S → ℂ[x_{1}, …, x_{n}]/I
x^{α} ↦ [x^{α}]

přirozeně rozšířené na polynomy je izomorfismus vektorových prostorů.

• Nechť x^{β} je také vzorem [x^{α}]. Potom x^{β} ∈ [x^{α}], tedy x^{α} − x^{β} ∈ I. Protože oba jsou prvky S, není ani jeden z nich prvkem LT I. Kdyby rozdíl byl nenulový, jeho vedoucí monom, tj. jeden z x^{α}, x^{β} by patřil do LT I. Proto jejich rozdíl musí být nulový. To znamená x^{α} = x^{β}, tj. zobrazení je prosté.

• Nechť f = ∑_{α} a_{α}x^{α} je libovolný. Jsou-li všechny monomy x^{α} ∈ S, pak třída [f] je jeho obrazem. Pokud nejsou, vezmeme z jeho monomů x^{α} ∉ S největšího stupně. Pak určitě existuje g ∈ I takové, že LT g = a_{α}x^{α}. Zřejmě [f] = [f − g] a problematický monom v f − g je ostře nižšího stupně. Po konečném počtu kroků získáme reprezentanta [f] tvořeného pouze monomy S. Zobrazení je tedy surjektivní.

• Sčítání i násobení skalárem je zřejmě zachováno.

“4 ⟹ 1” Stačí ukázat, že pro dané i existuje pouze konečně mnoho možných i-tých souřadnic bodů z V.

Uvažme proto třídy [x_{i}^{j}] ∈ ℂ[x_{1}, …, x_{n}]/I. Dimenze je konečná, a tedy, pro dostatečně velké m, existuje nenulová lineární kombinace

∑_{j=0}^{m}c_{j}[x_{i}^{j}] = [0]

což lze psát

[∑_{j=0}^{m}c_{j}x_{i}^{j}] = [0]

Odtud ∑_{j=0}^{m} c_{j}x_{i}^{j} ∈ I, což je nenulový polynom v x_{i} a ten má nejvýše konečně mnoho kořenů.

□

V obou větách nezáleželo na volbě monomiálního uspořádání. V praxi to znamená, že pokud výpočet zhavaruje pro nějaké, je možné jej provést s jiným uspořádáním a pravděpodobnost úspěchu se tak zvyšuje.

5.2 Polynomiální a racionální implicitizace

Připomeňme, že parametrická reprezentace variety v k^{n} je dána systémem n racionálních funkcí (viz. 1.8). Uvažme množinu definovanou parametricky systémem polynomů F = (f_{1}, …, f_{n}), kde f_{1}, …, f_{n} ∈ k[t_{1}, …, t_{m}]. F je možno chápat jako zobrazení

k^{m} → k^{n} takto x_{1} = f_{1}(t_{1}, …, t_{m})

⋮
x_{n} = f_{n}(t_{1}, …, t_{m})

Cílem implicitizace je nalézt varietu 𝔙(g_{1}, …, g_{s}) parametricky zadanou systémem F, tj. nejmenší afinní varietu V ⊆ k^{n} obsahující F (k^{m}). Podobně pro racionální parametrizace.

Například kružnice (obrázek 7) 𝔙(x^{2} + y^{2} = 1) je implicitizací parametrického vyjádření

y = \frac{1 − t^{2}}{1 + t^{2}} x = \frac{2t}{1 + t^{2}}

Bodu (0, 1) ovšem parametrickým vyjádřením nikdy nedosáhneme, bez něj by ale F (ℝ^{2}) nebyla varieta.

(0, 1) (0, 0)  (x, y) (t, 0)

Obr. 7: Implicitizace kružnice

5.3 Věta O polynomiální implicitizaci. Nechť k je nekonečné pole, F: k^{m} → k^{n} polynomiální zobrazení F = (f_{1}, …, f_{n}) a I = ⟨x_{1}−f_{1}, …, x_{n}−f_{n}⟩ ⊆ k[t_{1}, …, t_{m}, x_{1}, …, x_{n}]. Pak V (I_{m}) m-tého eliminačního ideálu je nejmenší afinní varieta v k^{n} obsahující F (k^{m}). Tedy sestrojíme-li varietu V = 𝔙(x_{1}−f_{1}, …, x_{n} −f_{n}), a ţvyeliminujeme� z přslušných polynomů hodnoty parametrů t_{1}, …, t_{m}, dostaneme právě implicitní popis hledané variety – uzávěru F (k^{m}). Důkaz: Označme p_{m}: k^{m+n} → k^{n} projekci zapomínající prvních m komponent. Přímo z definice I je F (k^{m}) = p_{m}(𝔙(I)). Proto pro algebraicky uzavřené pole k plyne tvrzení přímo z věty o uzávěru (4.16).

Uvažujme tedy algebraicky uzavřené rozšíření K ⊃ k, označme Ī = ⟨x_{1}−f_{1}, …, x_{n}− f_{n}⟩ ⊆ K[t_{1}, …, t_{m}, x_{1}, …, x_{n}]. Přímo z definice I a Ī je

F (k^{m}) = p_{m}(𝔙(I)) ⊆ V (I_{m})

Obr. 8: Enneperova plocha a Whitneyho deštník

Uvažme tedy nějakou jinou varietu Z = 𝔙(g_{1}, …, g_{s}) ⊆ k^{n} tak, že F (k^{m}) ⊆ Z_{k}. Odsud g_{i} ∘ F = 0 na každém (t_{1}, …, t_{m}) ∈ k^{m}. Stejná vlastnost platí i v K^{m}, a tedy i varieta Z_{K} generovaná stejnými polynomy g_{1}, …, g_{s} v K^{n} obsahuje F (K^{m}). Lze tedy aplikovat větu o uzávěru a dostáváme V (Ī_{m}) ⊆ Z_{K}. Zpětným zúžením na k získáme žádané V (I_{m}) ⊆ Z. □

Z předchozí věty už vyplývá podoba algoritmu pro implicitizaci. Spočteme redukovanou Gröbnerovu bázi ideálu ⟨x_{1} − f_{1}, …, x_{n} − f_{n}⟩ v lexikografickém uspořádání, kde t_{i} > x_{j} pro každé i, j. Dále snadno stanovíme I_{m} a to je přesně hledaný ideál.

Respektive stačí takové uspořádání, které zaručí převahu všech t_{i} nad x_{j}, aby se algoritmem pro výpočet Gröbnerovy báze eliminovala t_{i}, jinak může být uspořádání libovolné. Máme tak naději dosáhnout efektivnějšího výpočtu, než s čistým lexikografickým uspořádáním.

Jako příklady můžeme uvést už dříve zobrazené variety v ℝ^{3} nazývané Enneperova plocha a Whitneyho deštník, viz. obr. 8. Jejich parametrický popis je x = 3u+3uv^{2}−u^{3}, y = 3v + 3u^{2}v − v^{3}, z = 3u^{2} − 3v^{2}, resp. x = uv, y = v, z = u^{2}. Aplikace eliminační procedury (např. v systému MAPLE za použití gbasis s uspořádáním plex) dá odpovídající implicitní popisy. V případě Enneperovy plochy je to odpudivý polynom:

−59049z − 104976z^{2} − 6561y^{2} − 72900z^{3} − 18954y^{2}z − 23328z^{4} + 32805z^{2}x^{2} + 14580z^{3}x^{2} + 3645z^{4}x^{2}−1296y^{4}z−16767y^{2}z^{2}−6156y^{2}z^{3}−783y^{2}z^{4}+39366zx^{2}+19683x^{2}−1296y^{4}−2430z^{5}+ 432z^{6} + 108z^{7} + 486z^{5}x^{2} − 432y^{4}z^{2} + 54y^{2}z^{5} + 27z^{6}x^{2} − 48y^{4}z^{3} + 15y^{2}z^{6} − 64y^{6} − z^{9}

Výsledný implicitní popis Whitneyho deštníku je jednodušší: x^{2} − y^{2}z

Racionální implicitizací rozumíme analogický postup pro racionální lomené funkce

x_{i} = \frac{f_{i}(t_{1}, …, t_{m})}{g_{i}(t_{1}, …, t_{m})}

nefunguje. Například uvažujme

x = \frac{u^{2}}{v} y = \frac{v^{2}}{u} z = u

Přímočaře se nabízející řešení dosadit do předchozí věty ideál ⟨x_{1}g_{1} − f_{1}, …, x_{n}g_{n} − f_{n}⟩ Dostáváme I = ⟨vx − u^{2}, uy − v^{2}, z − u⟩ a po eliminaci I_{2} = ⟨z(x^{2}y − z^{3})⟩. Správný výsledek je ale jenom 𝔙(x^{2}y − z^{3}), tedy postup přidal navíc celou rovinu.

42 5 APLIKACE

Řešení vypadá tak, že zavedeme varietu nulových bodů jmenovatelů W = 𝔙(g_{1}, …, g_{n}) a zobrazení F chápeme jako (k^{m} − W) → k^{n}. Pro implicitizaci použijeme ideál

I = ⟨g_{1}x_{1} − f_{j}, …, g_{n}x_{n} − f_{n}, 1 − g_{1} ⋯ g_{n}y⟩ ⊆ k[y, t_{1}, …, t_{m}, x_{1}, …, x_{n}]

Potom V (I_{m+1} ) je minimální afinní varieta obsahující F (k^{m}−W). Důkaz už se vede v podstatě analogicky předchozí větě. Stěžejním bodem je ověření, že pokud se polynom nuluje na k^{m} − W, nuluje se už na celém k^{m}. Viz. [2], str. 132.

5.3 Algebraické křivky

5.4 Definice. Nechť f ∈ k[x, y]. Varietu 𝔙(f) nazveme algebraickou křivkou v k^{2} (v rovině).

V následující části půjde především o postižení pojmu tečny a singulárního bodu, tj. takového bodu na křivce, kde je pojem tečny těžko definovatelný.

5.5 Definice. Nechť m ∈ ℕ, (a, b) ∈ 𝔙(f) a L je přímka taková, že (a, b) ∈ L. Řekneme, že L protíná 𝔙(f) v (a, b) s násobností m, jestliže L lze parametrizovat

x = a + ct
y = b + dt

tak, že t = 0 je m-násobný kořen polynomu f(a + ct, b + dt) ∈ k[t]. Označme

∇f(p, q) := (\frac{∂f}{∂x}(p, q), \frac{∂f}{∂y} (p, q))

5.6 Lemma. Nechť f ∈ k[x, y] a (a, b) ∈ 𝔙(f). Pak platí

1. Je-li ∇f(a, b) ≠ (0, 0), pak existuje právě jedna přímka L procházející bodem (a, b), která v něm protíná 𝔙(f) s násobností alespoň 2.

2. Je-li ∇f(a, b) = (0, 0), pak každá přímka procházející (a, b) v něm protíná 𝔙(f) s násobností alespoň 2.

Důkaz: Označme g(t) := f(a + ct, b + dt). Protože (a, b) ∈ 𝔙(f), je t = 0 kořen g. Derivujme podle proměnné t

g′(t) = \frac{∂f}{∂x}(a + ct, b + dt) · c + \frac{∂f}{∂y} (a + ct, b + dt) · d

V bodě t = 0 potom

g′(0) = \frac{∂f}{∂x}(a, b) · c + \frac{∂f}{∂y} (a, b) · d

Tedy pokud ∇f(a, b) = (0, 0), je g′(0) = 0, a tedy t = 0 je alespoň dvojnásobný – druhá část tvrzení.

Pokud ∇f(a, b) ≠ (0, 0), dostaneme z podmínky g′(0) = 0 jednorozměrný prostor řešení pro dvojici (c, d). To spolu s požadavkem (a, b) ∈ L udává přímku jednoznačně. □

Obr. 9: Křivky 𝔙(f) s f(x, y) = (x^{2} + y^{2} − 2x)^{2} − a^{2}(x^{2} + y^{2}), a = 0, 1, 2, 3

44 5 APLIKACE

5.7 Definice. Nechť f ∈ k[x, y]. Body (a, b) ∈ 𝔙(f) s vlastností ∇f(a, b) = (0, 0) se nazývají singulární body křivky 𝔙(k), ostatní regulární. Přímka protínající 𝔙(f) v regulárním bodě s násobností alespoň 2 se nazývá tečna.

Singulární body mohou velmi zajímat inženýry. Pokud křivka popisuje pohyb nějaké součásti, singulární bod je vždy podezřelé místo – jedná se o bod zvratu, křížení apod. Jejich určení má tedy bezprostřední praktický význam.

Množina singulárních bodů dané křivky je zřejmě právě varieta

𝔙 (f, \frac{∂f}{∂x}, \frac{∂f}{∂y} )

Existence singulárních bodů je tedy na základě předchozí teorie problém algoritmicky řešitelný (nad ℂ), mnohdy se podaří je přímo nalézt.

Například pro křivky z obr. 9 dostaneme (třeba aplikací procedury gsolve v MAPLE), že pro každou hodnotu parametru a existuje vždy právě jeden singulární bod (0, 0). Pro a > 1 je to izolovaný bod, pro a = 1 je to ţbod vratu�, pro menší dochází k samoprotnutí křivky.

5.4 Obálky systému křivek

Polynom F ∈ k[x, y, t] budeme chápat jako proměnnou t parametrizovaný systém křivek 𝔙(F_{t}) v k[x, y] daných rovnicemi F (x, y, t) = 0. Například

(x − t)^{2} + (y − 2t^{2})^{2} − 1 = 0

definuje systém kružnic o poloměru 1, jejichž střed se pohybuje po parabole y = 2x^{2}, viz. obr. 10.

5.8 Definice. Říkáme, že dvě křivky mají dotyk řádu m, jestliže je lze lokálně parametrizovat^{11} hladkým zobrazením tak, aby parametrizace v bodě dotyku měly stejné derivace až do řádu m včetně. Maximální křivka, kterou lze lokálně parametrizovat tak, aby každý bod v této parametrizaci byl prvkem právě jedné z křivek daného systému a měl s ní v něm dotyk alespoň řádu 1, se nazývá obálka daného systému.

5.9 Věta. Obálka systému křivek F ∈ k[x, y, t] je obsažena ve varietě

𝔙 (F, \frac{∂F}{∂t} )

Důkaz: Nechť je obálka parametrizována x = f(t), y = g(t). Pro každé t ∈ k požadujeme příslušnost ke křivce, tj.

(f(t), g(t)) ∈ 𝔙(F_{t})

Navíc, aby křivka byla obálka, musí být ∇F_{t} v bodě (f(t), g(t)) kolmý na (f′(t), g′(t)). Kdo nevěří, ať si zopakuje analýzu. Kolmost znamená nulovou hodnotu skalárního součinu, tj.

\frac{∂F}{∂x} (f(t), g(t), t) · f′(t) + \frac{∂F}{∂y} (f(t), g(t), t) · g′(t) = 0 (3)

11Křivku nemusí nutně jít parametrizovat, ale pro nějaké dostatečně malé okolí daného bodu se to podaří.

5.4 Obálky systému křivek 45

Obr. 10: Systém křivek (x − t)^{2} + (y − 2t^{2})^{2} − 1 = 0 a jejich obálka

Pouhým derivováním složené funkce t ↦ F (f(t), g(t), t) a následným dosazením za t dostaneme

\frac{∂}{∂t}|_{t=s} F (f(t), g(t), t) = \frac{∂F}{∂x} (f(s), g(s), s) · f′(s) + \frac{∂F}{∂y} (f(s), g(s), s) · g′(s) + \frac{∂F}{∂t} (f(s), g(s), s)

Funkce F je na všech bodech tvaru (f(s), g(s), s) nulová (vlastnost obálky), a tedy musí být nulová i její derivace podle t. O prvních dvou členech pravé strany víme, že jsou dohromady nulové, pokud uvažovaná křivka je obálka. Dohromady tedy dostáváme

\frac{∂F}{∂t} (f(s), g(s), s) = 0

□

Pro všechny singulární body křivek systému je rovnost 3 splněna triviálně, a tedy i singulární body budou zahrnuty do výsledné variety.

Obálku systému kružnic se středy na parabole vidíme na obr. 10. K jejímu zadání jako afinní variety lze dospět v MAPLE např. posloupností příkazů h := proc (x, y, t) (x − t)^{2} + (y − 2 ∗ t^{2})^{2} − 1 end; gbasis ([h(x, y, t), diff (h(x, y, t), t)], [t, x, y], plex ), přičemž polynom definující hledanou obálku je generátor prvního eliminačního ideálu (poslední z výsledného seznamu). Vyjde 256x^{6} + 256x^{4}y^{2} − 320x^{4}y − 764x^{4} − 256x^{2}y^{3} − 384x^{2}y^{2} + 60x^{2}y + 688x^{2} + 64y^{4} − 272y^{3} + 225y^{2} + 272y − 289.

5.10 Tečny v singulárních bodech. Právě studium chování křivky v okolí singulárních bodů nám podá dobrou informaci o celé křivce. Všechny přímky procházející takovým bodem sice mají dotyk vyššího řádu, jistě je ale všechny nechceme považovat

Obr. 11: Tečný kužel křivek 𝔙(x^{3} + x^{2} − y^{2}) a 𝔙(X^{3} − y^{2}) v singulárním bodě

za tečny. Podle Taylorovy věty (snad dobře známé z matematické analýzy) má polynom f rozvoj v singulárním bodě (a, b)

f(x, y) = \underbrace{f(a, b)}_{=0 protože (a,b∈K)} + \underbrace{\frac{∂f}{∂x}(a, b)(x − a) + \frac{∂f}{∂y} (y − b)}_{=0 protože je (a,b) singulární}+

+ \frac{∂^{2}f}{∂x^{2}}(a, b)(x − a)^{2} + \frac{∂^{2}f}{∂x∂y} (a, b)(x − a)(y − b) + \frac{∂^{2}f}{∂y^{2}} (a, b)(y − a)^{2} + …

Předpokládejme, že f_{r}(x − a, y − b) = ∑_{i=1}^{r} \frac{∂^{r}f}{∂x^{i}∂y^{r−i}} (a, b)(x − a)^{i}(y − a)^{r−i} je první nenulová homogenní část. Pak množina všech řešení (u : v) rovnice f_{r}(u, v) = 0 dává směrové vektory tečen v singulárním bodě (a, b). Množinu všech těchto tečen nazýváme tečný kužel křivky K v singulárním bodě (a, b). 5.11 Příklad. Pro kubickou křivku K = V(x^{3} + x^{2} − y^{2}) snadno spočteme, že její jediný singulární bod je (0, 0), první nenulová homogenní část polynomu je x^{2} − y^{2}, tečný kužel je tedy tvořen dvěma přímkami x ± y = 0, viz. obrázek 11. 5.12 Deformace singularit. Jednoduchý postup jak zjistit chování křivky v okolí regulárního bodu je spočíst její tečnu v tomto bodě. Pro singulární body je to sice s tečnami složitější, často však stačí libovolně málo pozměnit vhodný parametr (tj. koeficient) definujícího polynomu a singularita vymizí. Z chování tečen pro blízké hodnoty parametru můžeme usuzovat na typ původní singularity. Již jsme se potkali se singularitou v počátku u křivek V(x^{3} − y^{2}) (násobná tečna – osa x) a V(x^{3} + x^{2} − y^{2}). Uvažme polynomy

f_{ε} = x^{3} − y^{2} − ε, g_{δ} = x^{3} + δx^{2} − y^{2}, h_{ε,δ} = x^{3} + δx^{2} − y^{2} − ε.

Polynomy f_{0} a g_{0} dávají první z našich křivek, g_{1} dá druhou.

Podívejme se nejprve na chování křivek V(g_{δ}). Snadno spočteme, že vždy mají pouze jeden singulární bod (0, 0), jeho typ je ovšem zcela odlišný pro δ < 0 a δ > 0.

Obr. 12: Deformace singularit křivek

Je-li δ kladné, pak nám vyjdou dvě reálné tečny ve směrech (1 : ±\sqrt{δ}), zatímco pro δ < 0 vyjdou obě tečny imaginární, je proto počátek izolovaným bodem křivky, viz. levý obrázek na 12.

Při deformacích f_{ε} je situace ještě daleko jednodušší. Pro nenulové ε totiž budou všechny body křivky regulární, viz. pravý obrázek na 12.

V obou případech získáváme jasnou představu o typu singularity Neilovy paraboly V(x^{3} − y^{2}). Diskusí současných deformací h_{ε,δ} dospějeme ke křivce hodnot parametrů V(ε)∪V(ε− \frac{4δ^{3}}{27} ), pro které křivky obsahují nějaký singulární bod, pro všechny hodnoty vně této křivky jsou všechny body regulární. Tvar křivky se přitom podstatně mění pouze při přechodech mezi uvedenými čtyřmi oblastmi. Hodnoty odpovídající Neilově parabole jsou právě jediným bodem společným všem čtyřem oblastem.

6 Algebraické důkazy geometrických tvrzení

Některá geometrická tvrzení lze poměrně jednoduše převést na algebraická a použít algebraické metody k jejich důkazu. Takových postupů je k dispozici několik, my se soustředíme pouze na jednu metodu, která vužívá k důkazům již vybudovaného aparátu.

6.1 Metoda Gröbnerových bazí

Začněme příkladem. Budeme cvičně uvažovat tvrzení, že uhlopříčky rovnoběžníka se navzájem půlí. Uvažujme rovnoběžník se souřadnicemi vrcholů podle obrázku 13. Proměnné u_{1}, u_{2}, u_{3} jsou volné, zadávají rovnoběžník, x_{1}, …, x_{4} jsou na nich závislé.

Sformulujme nejprve předpoklad, že se jedná o rovnoběžník. Přímka \overline{CD} musí být rovnoběžná s \overline{AB}, tedy h_{1} := x_{2} − u_{3} = 0. Podobně se musí rovnat směrnice \overline{AC} a \overline{BD}

\frac{u_{3}}{u_{2}} = \frac{x_{2}}{x_{1} − u_{1}} tedy h_{2} := u_{3}(x_{1} − u_{1}) − u_{2}x_{2} = 0

Varieta 𝔙(h_{1}, h_{2}) dává podmínky na rovnoběžník. Požadujeme kolinearitu bodů A, N, D, tedy dostáváme h_{3} := x_{1}x_{4} − x_{2}x_{3} = 0. Analogicky z kolinearity B, N, C získáme polynom h_{4} := x_{4}(u_{2}−u_{1})−(x_{3}−u_{1})u_{3}. Tím jsme popsali, že N je průsečík uhlopříček. Samozřejmě, že jsme mohli zvolit i jiný (dokonce jednodušší) systém polynomů popisující stejný geometrický objekt. Ten náš je v jistém smyslu co nejprimitivnější, využívající jen popis rovnosti směrů a rovnosti vzdáleností bodů.

Chceme ukázat, že se uhlopříčky půlí, tedy x_{3}^{2}+x_{4}^{2} = (x_{3}−x_{1})^{2}+(x_{4}−x_{2})^{2}. Podobně pro druhou uhlopříčku (x_{3} − u_{1})^{2} + x_{4}^{2} = (x_{3} − u_{2})^{2} + (x_{4} − u_{3})^{2}. Dostaneme tak polynomy g_{1}, g_{2} jejichž vynulování máme odvodit za předpokladu vynulování předpokladů h_{1}, h_{2}, h_{3}, h_{4}.

C(u_{2}, u_{3}) A(0, 0)  B(u_{1}, 0) N(x_{3}, x_{4})D(x_{1}, x_{2})

Obr. 13: Označení bodů v rovnoběžníku

Zdá se tedy, že vše co potřebujeme je přesně zachyceno v následující definici. 6.1 Definice. Řekneme, že g ∈ ℝ[u_{1}, …, u_{m}, x_{1}, …, x_{n}] silně vyplývá z h_{1}, …, h_{r}, jestliže g ∈ ℑ(𝔙(h_{1}, …, h_{r})).

6.2 Věta. Je-li g ∈ \sqrt{⟨h_{1}, …, h_{r}⟩}, pak g silně vyplývá z h_{1}, …, h_{r}. Důkaz: Z definice radikálového ideálu plyne g^{s} ∈ ⟨h_{1}, …, h_{r}⟩ pro vhodné s. Tedy g^{s} se nuluje na všech bodech dané variety, a tedy nutně i g ∈ ℑ(𝔙(h_{1}, …, h_{r})).

□ Obrácení věty v případě algebraicky uzavřeného pole plyne z Hilbertovy věty o nulách.

Příslušnost polynomu g k radikálovému ideálu se určí snadno výpočtem redukované Gröbnerovy báze (dokonce pro libovolné nekonečné pole k): 6.3 Věta. Nechť k je libovolné nekonečné pole a g, h_{1}, …, h_{r} ∈ k[x_{1}, …, x_{n}]. Pak g ∈ \sqrt{⟨h_{1}, …, h_{r}⟩} právě když je \{1\} redukovaná Gröbnerova báze ideálu I = ⟨h_{1}, …, h_{r}, 1− yg⟩ ⊂ k[x_{1}, …, k_{n}, y]. Důkaz: Předpokládejme nejprve, že konstantní polynom 1 patří do I. Pak stejně jako v závěru důkazu Hilbertovy věty o nulách dostáváme 1 jako lineární kombinaci polynomů h_{i} a 1 − yg a v k(x_{1}, …, x_{n})[y] můžeme za y dosadit 1/g a ověříme tak příslušnost g^{m} do ⟨h_{1}, …, h_{r}⟩. K tomuto kroku jsme ale nepotřebovali algebraickou uzavřenost k.

Naopak, je-li g^{m} ∈ ⟨h_{1}, …, h_{r}⟩, pak

1 = y^{m}g^{m} + (1 − y^{m}g^{m}) = y^{m}g^{m} + (1 − yg)(1 + yg + ⋯ + (yg)^{m−1}) ∈ I.

□

Spočítáme-li Gröbnerovu bázi ideálu ⟨h_{1}, …, h_{4}, 1 − yg_{1}⟩ z předchozího případu, nezískáme {1}, tedy g_{1} z předpokladů h_{1}, …, h_{4} nevyplývá silně. Je-to díky případům, kdy u_{1} = 0 nebo u_{3} = 0 a rovnoběžník degeneruje na úsečku. Potom průsečíkem uhlopříček je dokonce nekonečně mnoho bodů a ty všechny nesplňují podmínku půlení.

Zkuste si spočíst Gröbnerovu bázi polynomů h_{1}, h_{2}, h_{3}, h_{4} (v lex. uspořádání). Z ní bude jasně vidět, že v našem příkladě získáme ve skutečnosti čtyři komponenty diskutované variety V ⊂ ℝ^{7}. Můžeme je zapsat například jako

V′ = 𝔙(x_{1} − u_{1} − u_{2}, x_{2} − u_{3}, x_{3} − \frac{u_{1} + u_{2}}{2} , x_{4} − \frac{u_{3}}{2})
U_{1} = 𝔙(x_{2}, x_{4}, u_{3})
U_{2} = 𝔙(x_{1}, x_{2}, u_{1} − u_{2}, u_{3})
U_{3} = 𝔙(x_{1} − u_{2}, u_{2} − u_{3}, x_{3}u_{3} − x_{4}u_{2}, u_{1})

Obecně jsou problémy tohoto rázu způsobeny právě neireducibilními varietami. Jediná možná cesta z těchto komplikací je revize pojmu důsledku. Budeme požadovat, aby dokazované tvrzení platilo pouze na těch komponentách, kde jsou námi zvolené volné parametry u_{i} skutečně nezávislé: 6.4 Definice. Nechť W ⊆ ℝ^{m+n} je ireducibilní varieta, souřadnice značíme u_{1}, …, u_{m}, x_{1}, …, x_{n}. Řekneme, že souřadné funkce u_{1}, …, u_{m} jsou algebraicky nezávislé na W, jestliže neexistuje polynom v ℝ[u_{1}, …, u_{n}] patřící do ℑ(W). 6.5 Definice. Řekneme, že hypotéza g vyplývá genericky z předpokladů h_{1}, …, h_{r}, jestliže

g ∈ ℑ(V′) ⊆ ℝ[u_{1}, …, u_{m}, x_{1}, …, x_{n}]

kde V′ ⊆ ℝ^{m+n} je sjednocení těch ireducibilních komponent variety V = 𝔙(h_{1}, …, h_{r}), na kterých jsou u_{1}, …, u_{m} algebraicky nezávislé.

Rozklad variety na ireducibilní komponenty lze provést algoritmicky. Jde však o komplikovanou proceduru, je naimplementovaná například v systému Axiom. Není však nezbytně nutný, jak ukážeme v následujícím.

6.6 Věta. Hypotéza g vyplývá genericky z h_{1}, …, h_{r}, jestliže existuje nenulový polynom c ∈ ℝ[u_{1}, …, u_{m}] tak, že

c · g ∈ \sqrt{⟨h_{1}, …, h_{r}⟩}.

Je-li pole k algebraicky uzavřené, pak platí i obrázená implikace Důkaz: Nechť V_{j} je nějaká z komponent V′ dle definice 6.5. Protože cg se nuluje na V, musí se nulovat i na V_{j}, tedy cg ∈ ℑ(V_{j}). To je prvoideál podle věty 4.22, ale c ∉ ℑ(V_{j}) (požadováno v definici 6.5), a tedy g ∈ ℑ(V_{j}).

Předpokládejme nyní, že g vyplývá genericky z h_{1}, …, h_{r} a k je algebraicky uzavřené. Nechť V_{1}, …, V_{k} jsou všechny ireducibilní komponenty na kterých jsou u_{1}, …, u_{m} algebraicky závislé, tj ėxistují polynomy c_{1}, …, c_{k} ∈ k[u_{1}, …, u_{m}], c_{i} ∈ ℑ(V_{j}). Nyní stačí zvolit c = c_{1}c_{2} … c_{k} a z definice plyne, že cg ∈ ℑ(V). Protože je k algebraicky uzavřené, plyne odtud příslušnost do radikálnového ideálu. □

Pro praktické použití předchozí věty je vhodné formulovat ekvivalentní kritéria. Jako obvykle, budeme uvažovat

ℝ[u_{1}, …, u_{m}, x_{1}, …, x_{n}] ⊂ ℝ(u_{1}, …, u_{m})[x_{1}, …, x_{n}].

6.7 Věta. Následující tvrzení jsou ekvivalentní 1. Existuje c ∈ ℝ[u_{1}, …, u_{m}] nenulový tak, že cg ∈ \sqrt{⟨h_{1}, …, h_{r}⟩}.

2. g ∈ \sqrt{H}, kde H = ⟨h_{1}, …, h_{r}⟩ ⊂ ℝ(u_{1}, …, u_{m})[x_{1}, …, x_{n}].

3. {1} je redukovaná Gröbnerova báze ⟨h_{1}, …, h_{r}, 1 − yg⟩ opět v okruhu polynomů

ℝ(u_{1}, …, u_{m})[x_{1}, …, x_{n}]. Důkaz: Ukážeme nejprve (1) ⇔ (2). Předpokládejme, že platí (1), tj. (cg)^{s} = ∑_{j=1}^{n} a_{j}h_{j} pro vhodné polynomy a_{j} ∈ ℝ[u_{1}, …, u_{m}, x_{1}, …, x_{n}] a s ≥ 1. Odtud

g^{s} = ∑_{j=1}^{n} \frac{a_{j}}{c^{s}} h_{j}

což značí právě g^{s} ∈ ⟨h_{1}, …, h_{r}⟩ ⊂ ℝ(u_{1}, …, u_{m})[x_{1}, …, x_{n}], neboli g patří do příslušného radikálu.

Naopak, patří-li g do \sqrt{⟨h_{1}, …, h_{r}⟩} ⊂ ℝ(u_{1}, …, u_{m})[x_{1}, …, x_{n}], pak g^{s} = ∑_{j=1}^{n} b_{j}h_{j}. Vynásobením mocninou společného násobku všech jmenovatelů racionálních funkcí lomených b_{j} dostaneme výraz tvaru (cg)^{s} = ∑_{j=n} b′_{j}h_{j}, kde koeficienty b′_{j} jsou již polynomy.

Ekvivalenci druhého a třetího tvrzení jsme již ukázali, viz. 6.3 □ Tedy opět vystačíme s počítámím Gröbnerových bází, rozklad na ireducibilní kom-

ponenty není pro tyto účely třeba.

6.2 Příklady

Závěrem ukážeme aplikaci předchozích úvah při důkazu jedné z Apolloniových vět. Vraťme se ale nejprve k úvodnímu příkladu.

Již jsme zmínili rozklad 𝔙(h_{1}, …, h_{4}) na variety

V′ = 𝔙(x_{1} − u_{1} − u_{2}, x_{2} − u_{3}, x_{3} − (u_{1} + u_{2})/2, x_{4} − u_{3}/2)
U_{1} = 𝔙(x_{2}, x_{4}, u_{3})
U_{2} = 𝔙(x_{1}, x_{2}, u_{1} − u_{2}, u_{3})
U_{3} = 𝔙(x_{1} − u_{2}, u_{2} − u_{3}, x_{3}u_{3} − x_{4}u_{2}, u_{1})

Jedině na komponentě V′ jsou u_{1}, u_{2}, u_{3} algebraicky nezávislé, zbývající komponenty popisují degenerované případy. V_{1} a V_{2} znamenají, že bod C leží na přímce \overline{AB}, V_{3} znamená splynutí bodů A a B.

Ověřme si výsledek nalezením příslušné Gröbnerovy báze. V systému MAPLE to vypadá takto:

with(grobner):

¿ g1:=x1ˆ 2 - 2*x1*x3 - 2*x4*x2 + x2ˆ 2:

¿ g2:=2*x3*u1 - 2*x3*u2 - 2*x4*u3 - u1ˆ 2 + u2ˆ 2 + u3ˆ 2:

¿ gbasis([x1-u1-u2, x2-u3,x3-(u1+u2)/2,x4-u3/2,1-y*g1], [u1,u2,u3,x1,x2,x3,x4,y]);

[ 1 ]

¿ gbasis([x1-u1-u2, x2-u3,x3-(u1+u2)/2,x4-u3/2,1-y*g2], [u1,u2,u3,x1,x2,x3,x4,y]);

[ 1 ]

Odtud je vidět, že na komponentě V′ opravdu g_{1} i g_{2} skutečně silně vyplývá z předpokladů. Pro původní polynomy h_{i} ovšem dostaneme něco jiného:

¿ gbasis([x2-u3, (x1-u1)*u3- x2*u2, x1*x4 - x2*x3, x4*(u2-u1) - (x3-u1)*u3, 1-y*g1],[u1,u2,u3,u4,x1,x2,x3,x4,y]);

[−x1x4 + x4u2, x4u1, −1 + y x1^{2} − 2 y x1x3 − 2 y x4x2 + y x2^{2},
−x2 + u3, −x1x4 + x2x3, x2u1, x2u2 − x2x1]

Pokud ovšem použijeme původní polynomy, ale test pro generické implikování, dostáváme opět potřebnou bázi:

¿ gbasis([x2-u3, (x1-u1)*u3- x2*u2, x1*x4 - x2*x3, x4*(u2-u1) - (x3-u1)*u3, 1-y*g1],[x1,x2,x3,x4,y]);

[ 1 ]

¿ gbasis([x2-u3, (x1-u1)*u3- x2*u2, x1*x4 - x2*x3, x4*(u2-u1) - (x3-u1)*u3, 1-y*g2],[x1,x2,x3,x4,y]);

[ 1 ]

Nyní slíbená Apolloniova úloha. Chceme dokázat, že pro pravoúhlý trojúhelník jsou středy všech tří stran a pata výšky nad přeponou na jediné kružnici. K formulaci zadání budeme potřebovat osm polynomů h_{1}, …, h_{8}, obsahující dva volné parametry (délky odvěsen) a osm volných proměnných x_{1}, …, x_{8} (poslední dvě jsou souřadnice středu kružnice procházející středy stran trojúhelníka). Dokazované tvrzení je pak vyjádřeno jediným polynomem g:

¿ h1:= 2*x1 - u1: h2 := 2*x2 - u2: h3 := 2*x3 - u1: h4 := 2*x4 - u2: ¿ h5:= x5*u1 - x6*u2 : h6:= x5*u2 + x6*u1 - u1*u2: ¿ h7 := (x1-x7)ˆ 2 + x8ˆ 2 - x7ˆ 2 - (x8 - x2)ˆ 2: ¿ h8:= (x1-x7)ˆ 2 + x8ˆ 2 - (x3-x7)ˆ 2 - (x4-x8)ˆ 2: ¿ g := (x5-x7)ˆ 2 + (x6-x8)ˆ 2 - (x1-x7)ˆ 2 - x8ˆ 2: ¿ x:= seq(x.i, i=1..8): u:= u1,u2: h:= seq(h.i, i=1..8): Nakreslete si sami obrázek! Potřebný test ověřující, že g genericky vyplývá z h_{1}, …, h_{8}

je positivní:

¿ gbasis([h,1-y*g],[x,y]); [ 1 ]

Silně ovšem tvrzení nevyplývá: ¿ gbasis([h,1-y*g],[u,x,y]); [ x1, x3, x4, x2, u2, −1 + y x5^{2} − 2 y x5x7 + y x6^{2} − 2 y x6x8, u1] Všimněme si ještě, že často vystačíme i s jednodušším testem. Může se totiž stát,

že g patří přímo do ideálu generovaného h_{i} (v okruhu polynomů v nezávislých proměnných nad podílovým tělesem ℝ(u_{1}, u_{2})). Stačí pak provést dělení se zbytkem podle Gröbnerovy baze:

¿ F:= gbasis([h], [x],plex);

F := [2 x1 − u1, 2 x2 − u2, 2 x3 − u1, 2 x4 − u2, −u2^{2} u1 + ( u2^{2} + u1^{2} ) x5,
−u1^{2} u2 + ( u2^{2} + u1^{2} ) x6, −u1 + 4 x7, −u2 + 4 x8]

¿ normalf(g, F, [x],plex); 0

Zájemcům doporučuji zkusit si další jednoduché (či složitější) úlohy samostatně.

Literatura

[1] B. Buchberger. Groebner bases: an algorithmic method in polynomial ideal theory. In N. K. Bose, editor, Multidimensional Systems Theory, pages 184–232. D. Reidel Publishing Company, Dordrecht, 1985.

[2] David Cox, John Little, and Donal O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, New York, Inc., 1992.