Jan Slov k. Polynomi ln objekty. z pisky z p edn ek zpracoval Ale K enek

Jan Slov
k

Geometrick
algoritmy II. Polynomi
ln objekty

z
pisky z pedn
ek zpracoval Ale Kenek

OBSAH

i

Obsah

1 Ann variety 1.1 1.2 1.3 1.4

Z
kladn pojmy Parametrizace : Ide
ly : : : : : Dimenze 1 : : :

2 Grobnerovy bze 2.1 2.2 2.3 2.4

: : : :

: : : :

D len se zbytkem : Monomi
ln ide
ly Dicksonovo lemma Hilbertova v ta : :

: : : : : : : :

: : : : : : : :

: : : : : : : :

: : : : : : : :

: : : : : : : :

: : : : : : : :

3 Buchberger v algoritmus 3.1 3.2 3.3 3.4

Kritria pro Grobnerovy b
ze Algoritmus : : : : : : : : : : : Redukovan b
ze : : : : : : : Zefektivn n algoritmu : : : :

4 Teorie eliminac prom nn ch 4.1 4.2 4.3 4.4 4.5 4.6 4.7

Eliminace : : : : : : : : : : : V ta o rozen : : : : : : : : Existence spolench koen : Dkaz v ty o rozen : : : : Hilbertova v ta o nul
ch : : : V ta o uz
v ru : : : : : : : : Korespondence ide
l a variet

: : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : : : : : : : : : :

: : : :

: 9 : 12 : 12 : 14 : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

eitelnost systm rovnic : : : : : : : Polynomi
ln a racion
ln implicitizace Algebraick kivky : : : : : : : : : : : Ob
lky systmu kivek : : : : : : : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

6 Algebraick d kazy geometrick ch tvrzen

1 3 5 6

9

: : : : : : :

5 Aplikace 5.1 5.2 5.3 5.4

: : : :

1

17 17 20 21 23

28 28 29 29 32 33 35 36

38 38 40 42 44

48

6.1 Metoda Grobnerovch baz : : : : : : : : : : : : : : : : : : : : : : : : : 48 6.2 Pklady : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 50

ii

OBSAH

Poznmka vodem Druh

st pedn
ky geometrick algoritmy je daleko bli ist matematick teorii ne 
st pedchoz. S tm jist souvis pozorovan
nechu podstatn 
sti student informatiky tuto 
st studovat. V m vak, e pr
v uvaov
n nad matematickm formalismem inn tb analytick schopnosti, proto jsem po vah
ch o vesm s line
rn zadanch objektech v prvn 
sti pedn
ky zvolil pr
v matematicky podstatn n
ron j teorii popisujc algoritmick pstup k problmm spojenm s vz
jemnou polohou objekt zadanch algebraickmi rovnicemi. stednm pojmem a n
strojem jsou zde tzv. Grobnerovy b
ze a algoritmus pro jejich sestrojen. Tm z
rove pod
v
m vod do algoritmickho pstupu ke komutativn algebe a element
rn algebraick geometrii a pedstavuje se tak jeden ze z
kladnch pil kad souasn implementace tzv. potaov algebry. Pro jednoduchost nevych
z text z r
mce okruh polynom vce prom nnch nad re
lnmi nebo komplexnmi skal
ry. Uitenost odvozench vsledk se snam pedvst na (algoritmickm) een praktickch aplikac (een a eitelnost systm algebraickch rovnic, implicitizace parametrickch popis variet, singularity a ob
lky algebraickch kivek, algebraick (potaov) dkazy geometrickch tvrzen). V m, e studium t chto text pisp je k vzd l
n student, kte si k tto problematice najdou cestu. T kho kolu seps
n t chto uebnch text se ujal pan Ale Kenek, touto cestou mu moc d kuji. Tak jako v pedchoz 
sti, texty vznikly na z
klad mch pedn
ek prakticky bez moj dal asti a podle mho n
zoru se Ale svho kolu zhostil vborn . Samozejm , za obsahovou str
nku musm ruit s
m. Jakkoli koment
e, dotazy, vhrady apod. poslejte prosm na adresu slovakmath.muni.cz. Brno 1995,

Jan Slov
k

1

1 Ann variety V tto a n kolika n
sledujcch kapitol
ch se budeme zabvat form
lnm apar
tem, kter me mt mnoho aplikac vude, kde se pracuje s objekty nebo d ji popsatelnmi polynomy, resp. systmy polynomi
lnch rovnic. Jedn
se napklad o
Hled
n pslunosti bodu k n jakmu t lesu
Hled
n extrm na ploe
Analza pohyb sou
st n jakho stroje atd.

1.1 Zkladn pojmy

Pistupme nejprve k form
lnmu apar
tu, konkrtnch aplikac se snad dok
me pozd ji. 1.1 Denice. Monomem v prom nnch x1 : : :  xn nad polem k nazveme vraz x
1 1    x
nn , kde i 2 N. Za stupe tohoto monomu (zname deg x
1 1    x
nn ) povaujeme slo 1 +    + n. Zav
dme pojem multiindexu pro  = (1 : : : n) a pro zjednoduen peme x
= x
1 1    x
nn a jj = 1 +    + n . Polynomem v prom nnch x1 : : : xn nad polem k rozumme X
a
x kde a
2 k a suma je konen



Mnoinu vech polynom v prom nnch x1 : : :  xn nad polem k ozname k$x1 : : : xn]. St
n na n je vcelku zejm (u stejnch monom se setou koe&cienty v k), n
soben de&nujeme takto (ax
)  (bx ) := (ab)x
+ Tm jsme de&novali strukturu okruhu1. Za stupe polynomu povaujeme maximum stup jeho monom v danm uspo
d
n multiindex. To bylo jist pouh opakov
n z algebry, pistupme d
le. 1.2 Denice. A
nnm n-rozmrnm prostorem rozumme kn = k|  {z   k} se stann dardn a&nn strukturou. Polynom f = P
a
x
2 k$x1 : : : xn] lze pochopiteln pirozenm zpsobem ch
pat jako zobrazen f : kn ! k de&novan X f (u1 : : :  un) := a
u
kde u
= u
1 1    u
nn


Plat implikace, e pokud f 2 k$x1 : : : xn] je identicky roven 0 (tj. z de&nice a
= 0 pro kad ), pak je f : kn ! k nulov zobrazen. Obr
cen ale nemus obecn platit, 1

Nep
tel nech si samostatn doke, e je tomu skuten tak.

2

1 AFINN VARIETY 0.8

0.6

0.4

0.2

-0.8

-0.6

-0.4

-0.2

00

0.2

0.4

0.6

0.8

-0.2

-0.4

-0.6

-0.8

Obr. 1: V((x2 + y2)3 ; 4x2y2) uvame teba k = Z2, f = x2 ; x. Zejm f (x) = x(x ; 1) = 0 na Z2 pro kad x, ale f nen nulov polynom. Ve dvou prom nnch sta vzt g(x y) = x2y + y2x. Obecn pro kad prvoslo p a a 6= 0 plat ap;1 = 1 v Zp, a tedy xp ; x je vdy nulov zobrazen. 1.3 V ta. Nech k je nekonen pole, f 2 k$x1 : : :  xn]. Pak f = 0 v k$x1 : : :  xn] prv tehdy, kdy f : kn ! k je nulov zobrazen. Dkaz: Indukc podle n. Je-li n = 1, pak m
kad polynom stupn r > 0 nejve r koen. Pokud je f nulov zobrazen, musel by polynom mt nekonen mnoho koen, a tedy je stupn 0 nebo nulov. Konstantn polynom, kter je nulovm zobrazenm, ovem mus bt nutn nulov. Indukn krok. Meme ps
t f = Pi gi (x1 : : : xn;1 )xin. Pro pevn zvolen hodnoty x1 : : :  xn;1 je f polynom jedn prom nn, a tedy gi(x1 : : : xn;1) = 0. To plat pro libovolnou volbu x1 : : : xn;1, tedy gi jsou nulov
zobrazen a podle induknho pedpokladu i nulov polynomy.
1.4 D sledek. Pro nekonen pole a polynomy f g 2 k$x1 : : : xn] plat f = g prv tehdy, kdy f g : kn ! k jsou stejn zobrazen 1.5 Denice. Nech f1 : : : fs 2 k$x1 : : :  xn]. A
nn varietou v kn urenou polynomy f1 : : :  fn nazveme mnoinu n o V(f1  : : :  fs ) = (a1  : : : an ) 2 k n j fi (a1 : : :  an) = 0( i = 1 : : : s A&nn variety jsou napklad vechny kueloseky, kvadriky a nadkvadriky singul
rn i regul
rn. Ze zajmav jch dvourozm rnch uve)me tylstek (obr. 1) { varietu V((x2 + y 2)3 ; 4x2y 2 ), z trojrozm rnch pak obr
zek z tituln strany { V(x2 ; y 2z 2 + z 3), Whitneyho detnk (obr. 2) { V(x2z ; y2), kter obsahuje celou pmku fx = 0 y = 0g, a konen Enneperovu plochu (obr. 3). Varieta uren
vce polynomy je pak prnik variet jednotlivch polynom. Tedy napklad V(x2 + y2 ; 1 z) je krunice se stedem (0 0 0), polom rem 1 lec v rovin xy. D
le V(xz yz) je sjednocen pmky x = 0, y = 0 a roviny z = 0, protoe pro body t chto dvou tvar jsou oba polynomy xz yz nulov.

1.2 Parametrizace

3

Obr. 2: Whitneyho detnk

1.6 V ta. Nech V = V(f1 : : : fs ) W = V(g1 : : :  gt)  kn jsou a nn variety. Potom i V W V \ W jsou a nn variety a plat V \ W = V(f1 : : :  fs g1 : : : gt) V W = V(fi gj ) pro 1  i  s, 1  j  t




Na poslednm pklad se objevuje prvn problm { jak ch
pat dimenzi. Sta zmn n
pmka, aby varieta byla trozm rn
, nebo ji jet budeme povaovat za dvojrozm rnou s jistou anom
li? V n
sledujc 
sti se mimo jin pokusme zodpov d t ot
zky, kter se v souvislosti s varietami bezprostedn nabzej. 1. Plat V(f1 : : : fs) = ? 2. Je V(f1 : : : fs) konen
mnoina? 3. Jak lze ch
pat pojem dimenze v ppad variet? Jak se uk
e, tyto problmy lze rozumn  eit pro variety v oboru komplexnch sel (resp. pro vechna algebraicky uzaven
pole), pro sla re
ln
je to komplikovan j a velmi zl pro obecn
pole, tj. napklad racion
ln sla2.

1.2 Parametrizace

Pro n kter ryze praktick operace s varietami je vhodn pouvat implicitn reprezentaci (tedy a dosud pouvan vyj
den), nap. pro zjit n, zda dan bod do variety pat i nikoli, jindy je naopak daleko uiten j vyj
den parametrick. O co se pesn jedn
, uk
eme na pkladech. V(x + y + z ; 1 x +2y ; z ; 3) ud
v
pmku (prnik dvou rovin). eme-li systm

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

Takov rozhodnut, zda V( n + n ; n) =  vede na velkou Fermatovu vtu. x

y

z

4

1 AFINN VARIETY

Obr. 3: Enneperova plocha dostaneme pmo parametrick vyj
den tto pmky x = ;1 ; 3t y = 2 ; 2t z=t V n
sledujcm se pokusme o precizn a obecn vyj
den parametrizace. 1.7 Denice. Nech k je pole a f g 2 k$t1 : : : tn] polynomy. Pak f=g nazveme racion ln funkc nad polem k . Mnoina racion
lnch funkc rozloen
na tdy ekvivalence podle f=g = h=l () f  l = g  h v k$t1 : : : tn] tvo podlov t leso okruhu polynom k$t1 : : :  tn]( zname k(t1 : : :  tn). 1.8 Denice. Racion ln parametrickou reprezentac variety V(f1 : : :  fr )  kn rozumme racion
ln funkce r1 : : :  rn 2 k(t1 : : :  ts) splujc n
sledujc podmnky
Je-li xi = ri (t1  : : : ts ) pro i = 1 2 : : :  n pak (x1 : : : xn ) 2 V(f1  : : : fr ) pro libovoln
t1 : : : ts.
V(f1  : : : fr ) je minim
ln a&nn varieta obsahujc takto dan body (x1 : : :  xn ). V tto souvislosti se nabz dal ot
zky. 4. Existuje parametrizace dan variety, resp. lze ji nalzt? 5. Naopak, existuje (lze nalzt) k parametricky zadan variet implicitn popis? Obecn
odpov ) na prvn z t chto ot
zek je z
porn
. V podstat lze tvrdit, e v tinu a&nnch variet parametrizovat nelze, respektive neexistuje algoritmus parametrizace implicitnho popisu. Ty, u kterch se to poda, nazv
me neiracion ln 3 . Op t obecn nen jednoduch rozhodnout, zda dan
varieta je neiracion
ln. Cesta opanm sm rem je v nekonench polch zvl
dnuteln
, algoritmus pedvedeme v kapitole 5.2. Na prvn pohled je zejm, e pro jednu a tut varietu existuje vce implicitnch, ppadn i parametrickch popis. Opomeneme-li parametrick popis, nejednoznanosti implicitnho jsou zpsobeny pro tento el nevhodnou reprezentac pomoc n kolika generujcch polynom. 3

P
m p
eklad anglick ho unirational.

1.3 Idely

5

1.3 Idely

Pipomeme si trochu algebry. 1.9 Denice. Mnoinu I  A, kde A je okruh, nazveme ide lem, plat-li 0 z
rove f g 2 I =) f + g 2 I f 2 I h 2 A =) f  h 2 I

2

Ia

Pojem gener tor ide
lu je snad zejm, pipomeme jen znaen I = ha1 : : :  ani. Je-li gener
tor konen poet, kame, e ide
l je kone n generovan. Pro varietu V = V(f1 : : : fs) klademe n o I(V ) := f 2 k $x1 : : : xn ] j f (a1  : : : an ) = 0 pro vechna (a1 : : :  an ) 2 V

1.10 V ta. Nech f1 : : : fs g1 : : :  gt 2 k$x1 : : : xn] jsou polynomy. Pak plat 1. Jestli e hf1 : : :  fsi = hg1  : : : gti, pak V(f1 : : : fs) = V(g1 : : :  gt). 2. I(V ) je idel a plat hf1 : : : fsi  I(V ), kde V = V(f1  : : : fs). Dkaz: 1. Uvaujme libovoln (a1 : : :  an) 2 V(f1 : : :  fs). Pro n j plat

fi(a1 : : :  an) = 0 pro i = 1 2 : : :  s Protoe g1 : : :  gt 2 hf1 : : : fsi, existuj n jak polynomy h11 : : : hts v n prom nnch tak, e s X gj = hji  fi pro j = 1 2 : : :  t i=1

Odtud gj (a1 : : : an) = 0 pro j = 1 2 : : :  t. M
me tedy V(f1  : : : fs )  V(g1  : : :  gt ):

Opan
inkluze se dok
e zcela analogicky. 2. Nech g g0 2 I(V ), h 2 k$x1 : : : xn]. Potom pro zvolen bod (a1 : : :  an) 2 V plat g(a1 : : : an) = 0, a tedy (g  h)(a1 : : : an) = 0 =) g  h 2 I(V ) (g + g0)(a1 : : : an) = 0 =) g + g0 2 I(V ) Proto I(V ) je ide
l. Uvaujme libovoln f 2 hf1 : : :  fsi. Ten lze ps
t jako s X f = hi  fi pro n jak
h1 : : : hs 2 k$x1 : : :  xn] i=1

Pro (a1 : : : an) 2 V je tedy f (a1 : : : an) = 0. Proto plat hf1 : : : fs i  I(V ).

6

1 AFINN VARIETY

Jednoduch pklady:   I f(0 0 : : : 0)g = hx1  : : : xn i I(k n ) = f 0g pro libovoln nekonen pole k




Inkluze opan
k druh 
sti v ty obecn neplat. Napklad varieta V(x2 y2) m
jedin bod { (0 0). I(V ) je potom hx yi  hx2 y2i. Jsou-li V W  kn variety, pak plat

V

W

=) I(V )  I(W )

Neboli polynomy, kter se nulovaly na n jak variet se nutn mus nulovat i na jej podmnoin . Objevuj se dal problmy 6. Je kad ide
l I 2 k$x1 : : : xn] konen generovan? 7. Lze algoritmicky zjistit, zda f 2 hf1  : : : fsi?   8. Jak je pesn vztah mezi hf1 : : :  fsi a I V(f1 : : : fs ) ?

1.4 Dimenze 1

Na vechny ve zmn n ot
zky se pokusme odpov d t nejprve ve zjednoduenm, ale n
zornm ppad polynom v jedn prom nn. Konvenn pouv
me prom nnou x a koe&cienty v polynomu zname

f = a0xn + a1xn;1 +    + an kde a0 6= 0. Vedouc len polynomu (leading term ) de&nujeme jako LT (f ) := a0xn. Zejm plat deg f  deg g

()

LT (f )jLT (g)

1.11 V ta Algoritmus d
len se zbytkem. Nech k je pole a g nenulov polynom. Pak ka d f 2 k$x] lze jednoznan pst jako

f = q  g + r kde r = 0 nebo deg r < deg g Dkaz: je pochopiteln konstruktivn, podl q a zbytek r pot
n
sledujc algoritmus.

Algoritmus 1.1

1. q := 0, r := f 2. while r 6= 0 ^ LT (g)jLT (r) 2.1. q := q + LT (r)=LT (g) 2.2. r := r ; LT (r)=LT (g)  g

1.4 Dimenze 1

7

Pro prchod cyklem plat invariant f = q  g + r, algoritmus tedy d
v
spr
vn vsledek. Stupe r se kadm prchodem zmenuje, algoritmus tedy zastav. Pipusme, e existuj jet jin
q0 r0 tak, e f = q0  g + r0. Protoe stupn r a r0 jsou oste men ne stupe g, mus platit i deg(r ; r0) < deg g (protoe r 6= r0, m
smysl uvaovat deg(r ; r0)). Z
rove ale plat deg(r ; r0) = deg(q ; q0) + deg g  deg g co je spor. Dvojice q r je tedy urena jednoznan .
1.12 D sledek. Je-li k pole, m ka d f 2 k$x] nejve deg f koen. Dkaz: Je-li deg f = 0 (konstantn polynom), neexistuje 
dn koen. Nech deg f = n > 0 a f m
koen a. Potom podle v ty 1.11 existuj q r tak, e

f = q(x ; a) + r a z
rove deg r = 0 nebo r = 0. Protoe a je koen, r neme bt konstantn a tud f = q(x ; a). Stupe q je n ; 1, podle induknho pedpokladu m
nanajv n ; 1 koen, a tedy f jich m
nejve n.

1.13 D sledek. Nech k je pole. Pak ka d idel v k$x] je tvaru hf i.




Dkaz: Nech I  k$x]. Pokud I = f0g, pak I = h0i. Pedpokl
dejme I  f0g a nech f 2 I je minim
lnho stupn . Pak zejm hf i  I . Naopak uvaujme n jak g 2 I . Podle v ty 1.11 existuj q r takov, e g = q  f + r a z
rove deg r < deg f nebo r = 0. Protoe g f 2 I , plat q  f 2 I , a tedy r 2 I . Polynom f byl vybr
n s nejmenm stupn m z I , a proto r = 0. Odtud u plyne g 2 hf i, a tedy i I  hf i.
1.14 Denice. Nech f g 2 k$x]. Nejvtm spole nm dlitelem polynom f g, zname GCD (f g), nazveme takov polynom h, e hjf , hjg a plat 8p 2 k $x]: pjf ^ pjg

=) pjh

Nejv tho spolenho d litele lze pochopiteln spotat

Algoritmus 1.2

1. h := f , s := g 2. while s 6= 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 hjr g a z
rove 8p 2 k $x]: pjr g

tedy pjf a pjh

Odtud h je GCD (r g). Trivi
ln GCD (h 0) = h, proto algoritmus pot
spr
vn GCD (f g). Protoe stupn r postupn klesaj, algoritmus zastav.

8

1 AFINN VARIETY

Nejv t spolen d litel dvou polynom tedy existuje. Je uren jednoznan a na n
sobek skal
rem. Dva rzn GCD se toti mus d lit navz
jem a to je u polynom mon pr
v v tomto ppad . Pro korektnost n
sledujc v ty jet de&nujme nejv tho spolenho d litele vce ne dvou polynom. Je-li s > 2, potom   GCD (f1  : : :  fs ) := GCD f1 GCD (f2 : : :  fs )

1.15 V ta. Pro polynomy f1 : : : fs plat hGCD (f1 : : : fs )i =D hf1 : : : fsi.

E

Dkaz: Protoe GCD (f1  : : : fs)jf1 : : : fs , plat hf1  : : : fs i  GCD (f1  : : :  fs ) . Naopak pmo z algoritmu vpotu GCD plyne Bezoutova rovnost, tj. GCD (f1  : : : fs) = h1 f1 +    + hs fs pro vhodn
h1 : : :  hs

Odtud ji vyplv
opan
inkluze.
B hem kapitoly jsme poloili n kolik ot
zek. Nyn m
me ji ve potebn k jejich zodpov zen pro ppad polynom jedn prom nn. 1. Protoe V(f1 : : : fs) = V(GCD (f1 : : : fs )) (dsledek v ty 1.10), problm pr
zdnosti variety se redukuje na problm existence koene polynomu. 2. Ze stejnho dvodu je vdy konenou mnoinou izolovanch bod { koen GCD (f1 : : :  fs) s jedinou vyjmkou GCD (f1  : : :  fs ) = 0( to nastane pouze v ppad , e f1 = f2 =    = fs = 0. Pak je varietou cel
mnoina k. 3. Pojem dimenze v tomto ppad postr
d
smysl. 4. Stejn tak nen nijak eln parametrizovat konenou mnoinu. 6. Kad ide
l je generovateln jedinm polynomem { dsledek v ty 1.15. 7. f 2 hf1 : : : fs i () GCD (f1 : : : fs)jf (dsledek v ty 1.13). 8. Ozname-li hf i := I(V(f1 : : :  fs)), pak f a GCD (f1 : : : fs) se mohou liit pouze n
sobnost koen.

9

Obr. 4: Stejn
varieta?

2 Grobnerovy b
ze Jak u bylo eeno, implicitn reprezentace variety nen vdy nejvhodn j. Jen pro k3 = R3 je pi komplikovan jm zad
n obtn vbec interpretovat, jak dan
varieta vypad
. Znamenalo by to urit prnik obecn i dost komplikovanch tvar. Demonstrujme na jet pom rn jednoduchm pklad . Varieta na obr. 4 vlevo je V(x2 + y 2 + z 2 ; 1 x2 + y 2 + z ). V tomto ppad lze jet pom rn p snadno urit, e prnikem koule a paraboloidu je krunice lec v rovin z = 21 ; 12 5, tedy varietu lze stejn p dobe vyj
dit jako V(x2 + y2 + z2 ; 1 z2 ; z ; 1), ppadn V(x2 + y2 + z z ; 21 + 12 5) a podobn . Obr
zek 4 a pedchoz odstavec nabz dal problm. Jak rozhodnout, zda dv implicitn zadan variety jsou stejn? Zrovna tak pr
zdnou varietu (op t v R3) lze popsat V(x2 + 1) i V(1) nebo dokonce V(x2 + y2 + z2 ; 1 x2 + y2 + z2 ; 2). Podobnm problmem je i uren prniku, odvol
me-li se op t na obr. 4, prnik koule V(x2 + y2 + z2 ; 1) a paraboloidu V(x2 + y2 + z) lze vyj
dit jednodueji jako prnik n kterho z t chto objekt a roviny. V tinu t chto problm pom rn uspokojiv e apar
t prezentovan v $1]. Jak se pokusme uk
zat, varietu je vhodn j reprezentovat generujcm ide
lem a pro ten se poda nalzt vyj
den nez
visl na volb gener
tor, resp. pedvedeme algoritmus pev
d jc kadou mnoinu gener
tor na jist jednoznan kanonick tvar.

2.1 Dlen se zbytkem

U polynom vce prom nnch je situace daleko komplikovan j ne byla ve v t 1.11. Kupkladu zde neexistuje pm ekvivalent pojmu stupn , je nutn de&novat ho podstatn opatrn ji. Ani pojem vedoucho lenu polynomu nen zcela pmoar, je zde nutn volit n jak uspo
d
n na prom nnch a monomech( cel
teorie pak pest
v
bt vi prom nnm symetrick
. D len se zbytkem zde znamen
vyj
dit f 2 k$x1 : : : xn] jako

f = a1f1 +    + asfs + r Napklad m jme f = x2y + xy2 + y2, f1 = xy ; 1 a f2 = y2 ; 1. Prvnm d lenm

10 zsk
me

 2 GROBNEROVY BZE

f = (x + y)  f1 + (x + y2 + y) LT (y2 ; 1) ned l x (vedouc len zbytku), a tak bychom teoreticky nemohli pokraovat d
l. Pesuneme-li vak toto x do zbytku, dost
v
me teprve vsledek f = (x + y)  f1 + f2 + (x + y + 1) Zde ji 
dn len zbytku nen d liteln 
dnm z LT (f1), LT (f2). To je tak poadovan
vlastnost na vsledek d len se zbytkem. 2.1 Denice. pln (line
rn) dobr (tj. kad
nepr
zdn
podmnoina m
nejmen n prvek) uspo
d
n < na N0 splujc n 8   2 Z :  <  =)  +  <  +  nazveme monomi lnm uspo d nm na k$x1 : : :  xn]. Takto poloen
de&nice nen pln
. Uspo
d
n na Nn0 indukuje pouze uspo
d
n na monomech. Kad polynom lze vak peskl
dat jako klesajc posloupnost monom (na koe&cienty te) nehledme). Uspo
d
n se na polynomy roz lexikogra&cky, tedy v t je ten polynom, kter m
v t prvn monom, pokud tak nelze rozhodnou, bere se v potaz druh monom atd. N
sledujc ti de&nice zav
d j nejb n ji uvan
monomi
ln uspo
d
n. Vechna se opraj o pedem dan uspo
d
n jednotlivch prom nnch, standardn x1 > x2 > . 2.2 Denice. Lexikogra
ck uspo d n je takov lex  () Nejlev j nenulov len v  ;  je kladn 2.3 Denice. Gradovan lexikogra
ck uspo d n je takov grlex  () jj > j j nebo jj = j j a z
rove  >lex  2.4 Denice. n Gradovan opa n lexikogra
ck uspo d n je takov grevlex  () jj > j j nebo jj = j j a z
rove nejprav j nenulov len ( ;  ) je z
porn Tedy x1 >grevlex x2 >grevlex    >grevlex xn , ale pokud x > y > z, pak x2yz2 >grlex xy3z, ale x2yz2 lex >grlex >grevlex jsou monomiln uspodn. 2.6 Denice. Nech f = P
2Nn0 a
x
2 k$x1 : : : xn] je nenulov a < monomi
ln. Pak de&nujeme:
Stupe multideg f := maxf 2 Nn0 j a
6= 0g

2.1 D len se zbytkem

11

Vedouc koe&cient LC f := amultideg f
Vedouc monom LM f := xmultideg f
Vedouc len LT f := LC f  LM f Tyto pojmy jsou tedy pro polynomy vce prom nnch vesm s siln z
visl na volb konkrtnho uspo
d
n. 2.7 Lemma. Nech f g 2 k$x1 : : :  xn] a < je monomiln. Pak 1. multideg(f  g) = multideg f + multideg g 2. f + g 6= 0 =) multideg(f + g)  maxfmultideg f multideg gg 2.8 V ta D
len se zbytkem. Nech < je monomiln a F = (f1 : : :  fs) s-tice polynom v k$x1 : : : xn]. Pak ka d f 2 k$x1 : : : xn] lze vyjdit jako f = a1f1 +    + asfs + r kde ai r 2 k$x1 : : :  xn] pro i = 1 2 : : :  s a navc r = 0 nebo r je linern kombinac monom, z nich dn nen d liteln ktermkoli z LT f1 : : : LT fs a pokud aifi 6= 0 pak multideg f  multideg aifi pro ka d i. Polynom r nazvme zbytkem po d len f=F . Je zejm, e narozdl od jedn prom nn vsledek d len se zbytkem nen d
n jednoznan ani vzhledem k pevn zvolenmu uspo
d
n monom. V ta tak nic o jednoznanosti netvrd, n
sledujc algoritmus d
v
jedno mon een. Nad
le budeme vsledkem d len se zbytkem ch
pat pr
v jeho vstup.


Algoritmus 2.1

1. a1 := 0 : : :  as := 0 r := 0 p := f 2. while p 6= 0 2.1. i := 1 2.2. d := false 2.3. while i  s ^ not d 2.3.1. if LT fijLT p 2.3.1.1. ai := ai + LT p=LT fi 2.3.1.2. p := p ; (LT p=LT fi)  fi 2.3.1.3. d := true 2.3.2. else i := i + 1 2.4. if not d 2.4.1. r := r + LT p 2.4.2. p := p ; LT p Dkaz: Pi kadm prchodu vn jm cyklem se pr
v jednou provede pr
v jeden z pkaz 2.3.1.2, 2.4.2, a tedy stupe p klesne. Proto algoritmus skon. Plat invariant f = a1f1 +    + p + r a pitom kad len kadho ai je podlem LT p=LT fi z n jakho okamiku. Proto stupe t chto len je men ne stupe p v danm okamiku a ten je nejve roven stupni f . Dohromady stupe kadho aifi je men nebo roven stupni f .


 2 GROBNEROVY BZE

12

V k$x] byl kad ide
l tvaru I = hf i a algoritmus d len se zbytkem pln eil pslunost k ide
lu. Oproti tomu v k$x1 : : : xn] plat pouze implikace f = a1f1 +    + asfs + 0 =) f 2 hf1 : : :  fsi Obr
cen obecn neplat, uvaujme f = xy2 ; x, f1 = xy + 1, f2 = y2 ; 1. Potom algoritmus d len d
f = y(xy + 1) + 0(y2 ; 1) + (;x ; y) ale pitom evidentn f = x(y2 ; 1), a tedy f 2 hf1 f2i.

2.2 Monomiln idely

2.9 Denice. Ide
l I n

k$x1 : : : xn] nazv
me monomi ln, existuje-li mnoina P A  N0 tak, e I se sest
v
pr
v ze vech polynom tvaru
2A h
x
, kde h
2 k$x1 : : : xn]. Potom peme I = hx
j  2 Ai. Zejm pro monomi
ln ide
l I plat x 2 I () 9 2 A : x
jx 2.10 Lemma. Nech I  k$x1 : : :  xn] je monomiln idel, f 2 k$x1 : : : xn] polynom. Pak nsledujc tvrzen jsou ekvivalentn 1. f 2 I 2. Ka d len polynomu f je prvkem I . 3. Polynom f je linern kombinac monom z I s koe cienty z k. Dkaz: Implikace (3) =) (2) =) (1) je trivi
ln. Zbv
uk
zat (1) =) (3). P Plat f =
a
x
2 I , kde a
2 k. Z pedpokladu vyplv
, e lze vyj
dit P f = 2A h x , kde h 2 k$x1 : : : xn]. Kad len a
nx
se mus rovnat n ktermu lenu z druh rovnosti, tedy existuj takov
d 2 k 2 N0 tak, e a
x
= dx+ . Proto x
2 I , a tedy plat (3).
2.11 D sledek. Dva monomiln idely splvaj prv tehdy, kdy obsahuj stejn monomy. 

2.3 Dicksonovo lemma

2.12 V ta

Dicksonovo lemma. Ka d monomiln idel I = hx
j  2 Ai 

k$x1 : : : xn] lze pst ve tvaru I = hx
1  : : : x
s i, kde 1 : : : s 2 A. Dkaz: Dkaz vedeme indukc podle potu prom nnch. Nech n = 1. Pak I  k$x], I = hx
j  2 A  N0 i. Polome  := min A. Potom zejm I = hx i. Uvaujme tedy n > 1. Pro pehlednost ozname prom nn jako x1 : : : xn;1 y, monomy potom budou tvaru x
ym, kde  2 Nn0 ;1 , m 2 N0, a mnoinu monom x s  2 A budeme znait IA. Pedpokl
dejme, e I  k$x1 : : : xn;1 y] je monomi
ln. De&nujme J  k$x1 : : : xn;1 ] n
sledovn J := hx
j 9m 2 N0 : x
ym 2 IAi

2.3 Dicksonovo lemma

13

x

y

Obr. 5: Monomy v ide
lu I = hx3y xy3i  R$xy] Zejm J je monomi
ln ide
l v n;1 prom nnch, a tedy podle induknho pedpokladu lze ps
t J = hx
1  : : : x
s i. D
le z de&nice J vyplv
, e existuj takov
minim
ln mi 2 N0 tak, e x
i ymi 2 IA. Ozname tedy m := maxfmig a de&nujme analogicky systm ide
l Jk  k$x1 : : : xn;1] pro 0  k  m ; 1

Jk := hx j x yk 2 IAi Op t vechny Jk spluj indukn pedpoklad, a tedy je lze vyj
dit

Jk = hx
k
1  : : :  x
k
sk i: Zbv
uk
zat, e I je generovan touto mnoinou monom

x
1 ym : : : x
s ym x
0
1 y0 : : : x
0
s0 y0 ... x
m;1
1 ym;1 : : : x
m;1
sm;1 ym;1 Uvaujme libovoln monom x
yp 2 IA. Nastane jeden ze dvou ppad
p  m. Potom jist x
2 J , a tedy n kter z x
1 y m  : : : x
s y m d l x
y p.
p < m. Potom analogicky x
2 Jk a n kter z x
k
1 y k  : : :  x
k
sk y k d l x
y p. Podle lemmatu 2.10 lze kad f 2 I vyj
dit jako line
rn kombinaci monom z IA, ty jsou ji d liteln n kterm ze zmn nch gener
tor, a tedy f pat do ide
lu jimi generovanho. Proto I je jeho podmnoinou. Opan
inkluze je zcela trivi
ln.


 2 GROBNEROVY BZE

14

2.13 D sledek. Nech < je relace na Nn0 splujc podmnky

1. Relace < je pln uspodn. 2.  <  ,  2 Nn0 =)  +  <  +  Pak < je dobr uspodn prv tehdy, kdy 8 2 Nn0 :   0 Dkaz: \=)" Protoe < je dobr, existuje 0 2 Nn0 nejmen. Pedpokl
dejme 0 < 0. Podle podmnky (2) zkonstruujeme nekonenou posloupnost 0 > 0 > 20 >    , co je spor s tm, e < je dobr. \(=" Nech 8 2 Nn0 :   0. Uvame libovolnou mnoinu 6= A  Nn0 . Potom I = hx
j  2 Ai je konen generovan n jakmi monomy x
1  : : : x
s 2 A. Bez jmy na obecnosti pedpokl
dejme 1 <    < s. Uvaujme libovoln  2 A. Potom nutn x
i jx
pro vhodn i = 1 : : :  s, tj.  = i +  , kde   0 (pedpoklad tto implikace). Potom ale plat

  i + 0  1 a tedy 1 je nejmen v A. Protoe A byla zvolena libovoln , je uspo
d
n < dobr.




2.4 Hilbertova vta

Je-li I  k$x1 : : : xn] nenulov, ozname

LT I := fax
j 9f 2 I : LT f = ax
g Zejm hLT I i je monomi
ln, a tedy podle Dicksonova lemmatu lze ps
t hLT I i = hLT g1  : : : LT gs i pro n jak
vhodn
g1  : : : gs 2 I . 2.14 V ta Hilbertova. Ka d idel I 2 k$x1 : : :  xn] je konen generovan. Dkaz: Pokud by I = f0g, je tvrzen trivi
ln. Uvaujme tedy I  f0g. Podle Dicksonova lematu a pedchoz pozn
mky existuj takov
g1 : : :  gs 2 I , e hLT I i = hLT g1  : : : LT gs i Zejm hg1  : : :  gs i  I . Vezm me libovoln f 2 I a prove)me d len se zbytkem s-tic g1 : : :  gs. Dost
v
me

f = a1g1 +    + asgs + r kde 
dn len r nen d liteln LT g1 : : : LT gs. Protoe r = f ; a1g1 ;    ; asgs, plat r 2 I , a tedy LT r 2 LT I . Zejm tedy LT r 2 hLT I i. Pipusme, e r 6= 0. Protoe hLT I i je monomi
ln, mus bt LT r d liteln n kterm z jeho gener
tor, tj. LT g1 : : :  LT gs . To je ovem spor s vsledkem algoritmu d len. Proto r = 0 a I je tedy generovan g1 : : : gs .


2.4 Hilbertova v ta

15

2.15 Denice. Konen
b
ze g1  : : : gs ide
lu I  k$x1 : : :  xn] se nazv
Grobnerova, jestlie plat hLT I i = hLT g1 : : : LT gs i. B
ze pouit
v dkazu Hilbertovy v ty byla Grobnerova.

Jak u
to na svt bv, Grobnerovy bze nevymyslel pan Grobner, ale jeho aspirant B. Buchberger, kter je tak dajn nazval na po est sv ho u itele. Jet nav c nebyl prvn . V polovin edestch let popsal H. Hironaka standardn bze, v podstat se jednalo o tot
. Ke cti pana Buchbergera nutno podotknout,
e o prci sv ho sou asn ka patrn neml ani pont a dovedl ji dle. Ani pan Hilbert to neml ve sv dob jednoduch . Vtu, kter byla ostatn jako hypot za u
zformulovna d ve, dokzal podstatn komplikovanj m zpsobem, ne
jsme uvedli. Nav c nekonstruktivn dkazy nebyly tenkrt p li obl beny, a tak se od svch koleg uznn nedo kal.

Inkluze hLT I i  hLT g1 : : :  LT gs i plat pro libovolnou b
zi g1 : : : gs , a tedy se sta omezit na dokazov
n opan. Ta obecn platit nemus. Uvaujme napklad
f = h1f1 +    + hs fs = h01g1 +    + h0tgt Chceme, aby LT f 2 hLT g1 : : :  LT gti, tj. LT f m
bt d liteln n kterm z x1 : : :  xt. Pedpokl
dejme, e f je pouze v prom nnch xt+1 : : : xn. Pak ale h01 = 0, protoe x1 je vzhedem ke schodovitosti B pouze v g1. Analogickm postupem zsk
me h02 =    = h0t = 0, a tedy f = 0. B
ze g1 : : : gt je tedy Grobnerova. Pouit Gausovy eliminace zde nen n
hodn, v n
sledujc 
sti uk
eme algoritmus potajc Grobnerovy b
ze, kter je v podstat zobecn nm Gausovy eliminace pro polynomy vych stup. 2.17 V ta Ascending Chain Condition. Nech I1  I2     je neklesajc nekonen posloupnost idel v k$x1 : : :  xn]. Pak existuje N  1 tak, e IN = IN +1 =    . Dkaz: Ozname I := S1 i=1 Ii . Zejm I je ide
l. Podle Hilbertovy v ty existuj f1  : : : fs tak, e I = hf1 : : : fs i. Jist existuje takov N , e f1 : : : fs 2 IN . Potom u I = IN = IN +1 =    .


 2 GROBNEROVY BZE

16

2.18 Denice. Nech I  k$x1 : : :  xn]. Ozname V (I ) := f(a1 : : : an) 2 kn j 8f 2 I : f (a1 : : : an) = 0g Podle Hilbertovy v ty je I = hf1 : : : fs i a V (I ) je rovno variet V(f1 : : :  fs). V obecn teorii se okruhy, kde je kad ide
l konen generovan, nazvaj 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 noetherovskm okruhem je op t noetherovsk.

17

3 Buchbergerv algoritmus Pouh tvrzen, e kad ide
l m
Grobnerovu b
zi (dsledek Hilberovy v ty) by asi nebylo pli prakticky pouiteln. Proto se budeme d
le zam ovat na algoritmick nalezen takov b
ze, a protoe pro dan ide
l me Grobnerovch b
z existovat vce, pokusme se identi&kovat i jakousi jednoznanou kanonickou formu.

3.1 Krit ria pro Gr obnerovy bze

3.1 V ta. Nech G = fg1 : : : gtg je Grobnerova bzeP idelu I  k$x1 : : : xn] a f je

polynom v k$x1 : : : xn]. Pak existuje prv jedno r =
a
x
2 k$x1 : : : xn] s t mito vlastnostmi 1. dn len r nen d liteln dnm z LT g1 : : :  LT gt, tj. 88i : LT gi 6 j a
x
. 2. 9g 2 I : f = g + r Dkaz: Algoritmus pro d len se zbytkem d


f = a1g1 +    + atgt + r kde r spluje podmnku 1. Za g u vezmeme a1g1 +    + atgt, kter trivi
ln padne do I . Zbv
dok
zat jednoznanost. Pedpokl
dejme f = g + r = g0 + r0, kde r 6= r0. Zejm plat r ; r0 = g0 ; g 2 I . Protoe G je Groebnerova, je LT (r ; r0) d liteln n kterm z LT g1 : : :  LT gt . Diskutujme n
sledujc monosti
LM r 6= LM r0 . Pak ten s vym stupn m mus bt d liteln n kterm z vedoucch len LT g1 : : :  LT gt, co je spor s prvnm bodem.
LM r = LM r0 ^ LC r 6= LC r0 . Potom ale oba LM r LM r0 mus bt d liteln n kterm z LT g1 : : :  LT gt . Proto tedy LT r = LT r0 a induktivn vahou odtud plyne r = r0.
Pedchoz v ta je vlastn zobecn nm d len se zbytkem, kde na mst d litele vystupuje ide
l. V ppad jedn prom nn nebylo co zobecovat, protoe kad ide
l byl generovan jednm polynomem. Zajm
-li n
s pouze zbytek, v ta navc k
, e nez
le na poad polynom v b
zi. Proto m
smysl zavst znaen f F pro zbytek po d len f=F , pokud F je Grobnerova b
ze. 3.2 D sledek. Nech G = fg1 : : : gtg je Grobnerova bze idelu I  k$x1 : : : xn] a f je polynom v k$x1 : : : xn]. Pak plat

f 2I

()

zbytek po d len f=G je nulov

Dkaz: \(=" Nech f = g + r je rozklad z pedchoz v ty a r = 0. Potom trivi
ln f 2 I . \=)" f 2 I =) f = f +0. Protoe f vyhovuje podmnk
m pedchoz v ty, a takov polynom podle jejho tvrzen existuje pr
v jeden, mus bt zbytek po d len f=G nutn nulov.




18

3 BUCHBERGERV ALGORITMUS

3.3 Denice. Pokud  = multideg f a  = multideg g, bu)  := (1 : : :  n) kde i = maxfi ig Monom x nazv
me nejmenm spole nm n sobkem (least common multiple) monom LM f a LM g a zav
dme pon kud matouc oznaen LCM (LM f LM g) := x . Vraz   S (f g) := LTx f  f ; LTx g  g

nazv
me S -polynomem4 polynom f g. Jedn
se o n
stroj k jaksi eliminaci vedoucch len, Gaussova eliminace je speci
lnm ppadem tohoto postupu pro stupe 1. Narozdl od n ale me dojt ke zven stupn , i kdy pvodn vedouc leny odstran. Vezm me napklad f = x3y2 ; x2y3 + x, g = 3x4y + y2, tedy polynomy stupn 5 v R$xy] a uspo
d
n
jk=1

a dle ka d x;j
k S (gj  gk ) m stupe men ne . Dkaz: Ozname di := LC gi a pi = x
i gi=di . Urit ci di = LC (cix
i gi ) a PLC pi = 1. Protoe multideg(cix
i gi ) = a z
rove multideg f < , mus nutn platit ti=1 cidi = 0. Pokusme se te) f vyj
dit jako kombinaci S -polynom. t X f = ci dipi = c1d1(p1 ; p2) + (c1d1 + c2d2)(p2 ; p3) +    i=1

+ (c1d1 +    + ct;1dt;1)(pt;1 ; pt ) + (c|1d1 + {z  + ctd}t )pt 0

Kad rozdl pj ; pk lze vyj
dit v S -polynomech  ! x g ; x g = x;j
k xj
k g ; xj
k g = x;j
k S (g  g ) j k d x;
j j d x;
k k LT g j LT g k j

k

j

k

Z obou rovnost se u snadno odvod jednotliv koe&cienty cjk . 4

Ze syzygy neboli sp
een, vce kapitola 3.4.




3.1 Kritria pro Grobnerovy bze

19

3.5 V ta. Nech I  k$x1 : : : xn ] je idel. Pak jeho bze G = fgj  : : : gtg je Grobnerova prv tehdy, kdy pro ka d i 6= j je zbytek po d len S (gi  gj )=G nulov. Dkaz: \=)" Plyne bezprostedn z dsledku 3.2. \(=" Uvaujme 0 6= fP2 I . Potebujeme LT f 2 hLT g1 : : :LT gt i. Poda-li se zaruit, aby pro f = ti=1 higi platilo n o multideg f = max multideg(higi) bude LT f nutn d liteln n kterm LT gi, a tedy G bude Grobnerova. Ozname mi := multideg(higi), := maxfm1 : : : mtg. Zejm multideg f  . Nech h1 : : : ht jsou zvolena tak, e je minim
ln. Protoe pracujeme s monomi
lnm uspo
d
nm, kter je dobr, takov existuje. Dokame tedy, e multideg f = . Lze ps
t X X X X X (1) f = higi + higi = (LT hi )gi + (hi ; LT hi)gi + higi mi =

mi <

mi =

mi =

mi <

Vechny stance druh a tet sumy maj jist stupe men ne . Pipustme-li, e multideg f < , potom nutn 0 1 X multideg @ (LT hi)giA < mi =

Ozname nyn cix
i := LT hi a aplikujme lemma 3.4. X X
i X ;j
k (LT hi)gi = ci x gi = cjk x S (gj  gk ) m i =

mi =

jk

Z pedpokladu v ty a algoritmu o d len se zbytkem zsk
v
me Xt S (gj  gk ) = aijk gi i=1

a navc multideg(aijkgi )  multideg S (gj  gk ). Ozname-li bijk := x;j
k aijk , dost
v
me Xt x;j
k S (gj  gk ) = bijk gi i=1

Podle druh 
sti lemmatu 3.4 plat   multideg(bijk gi)  multideg x;j
k S (gj  gk ) < a dosazenm 0 1 ! X t t X X X X bijk gi = @ cjk bijk A gi (LT hi)gi = cjk mi =

jk

i=1

i=1

jk

20

3 BUCHBERGERV ALGORITMUS piem plat

0 1 X multideg @ cjk bijk giA < pro i = 1 : : :  t jk

Dosazenm do rovnosti (1) zsk
v
me vyj
den f jako kombinace g1 : : : gt, kde vechny stance jsou stupn menho ne . To je spor s minim
ln volbou , a tedy multideg f = , odkud LT f 2 hLT g1 : : : LT gti a b
ze G je Grobnerova.




3.2 Algoritmus

V ta 3.5 poskytuje u inn prostedek pro zjit n, zda n jak
b
ze je Grobnerova. Uvaujme napklad I = hx + y y ; zi. Jedin S -polynom, kter pipad
v vahu je xy ( x + y ) ; (y ; z ) = xz + y 2 S (x + y y ; z) = xy x y

D lenm zsk
me xz + y2 = z(x + y) + y(y ; z), a tedy dan
b
ze je Grobnerova. Spolu s v tou 2.17 zsk
v
me tak n
vod k naivnmu algoritmu pro vpoet Grobnerovy b
ze. V kadm jeho kroku k ji zkonstruovan b
zi G = ff1 : : : fsg pid
me vechny nenulov S (fi fj ) G. Zsk
me tak b
zi G0 . Zejme jsme nic novho nepidali, a tak hG0 i = hGi. Navc hLT Gi  hLT G0i. Pokud ovem G  G0, pak tak hLT Gi  hLT G0i, protoe pid
v
me zbytky po d len G a ty nemohou bt d liteln 
dnm z LT f1 : : : LT fs, a tedy hLT Gi obohat. M
me tedy neklesajc posloupnost ide
l hLT G1 i  hLT G2 i     A ta m
podle v ty 2.17 jist index, od kterho je stabiln. Pipustme-li, e pid
v
n zbytk k b
zm nikdy neskon, dost
v
me se tak do sporu. N
sledujc algoritmus potajc Grobnerovu b
zi G ide
lu hF i je tedy korektn

Algoritmus 3.1

1. G := F , G0 := 2. while G 6= G0 2.1. G0 := G 2.2. 8p g 2 G0 : p 6= g do 0 2.2.1. s := S (p q) G 2.2.2. if s 6= 0 2.2.2.1. G := G fsg Tento algoritmus ovem nen zdaleka ide
ln. Lze vymyslet velmi jednodue vypadajc vstupy, pro n  vrac divok vsledky. D
le vstupn b
ze se pmo odvj od vstupn, a tedy pro tent ide
l zadan rznmi b
zemi d
tak rzn vsledky. Z hlediska ist rutinnho algoritmus tak nen optim
ln, mnoho vpot zbytk zbyten opakuje, i kdy je zejm, e jakmile byly zbytky jednou vynulov
ny, budou nulov i v n
sledujcch krocch.

3.3 Redukovan bze

21

3.3 Redukovan bze

Jak ji bylo eeno, Grobnerovch b
z danho ide
lu existuje vce. Zam me se tedy na nalezen jednoznan kanonick podoby, kter
dan ide
l bude identi&kovat. 3.6 Lemma. Nech G je Grobnerova bze idelu I a p 2 G takov, e LT p 2 hLT (G ; fpg)i. Pak G ; fpg je tak Grobnerova bze I . Dkaz: Z de&nice Grobnerovy b
ze plat hLT I i = hLT Gi. Protoe LT p 2 hLT (G ; fpg)i, plat hLT (G ; fpg)i = hLT Gi. Odsud ji, podle dsledku 2.16, plyne tvrzen.




N
sledujc de&nice je tedy smyslupln
. 3.7 Denice. Minim ln Grobnerovou b z ide
lu I je takov
Grobnerova b
ze G, e pro vechna p 2 G plat LC p = 1 a z
rove LT p 2= hLT (G ; fpg)i Napklad m jme k$x y] a
idelu, kter jej obsahuje. Dkaz: Tvrzen dok
eme sporem. Uvame G = fg1  : : : gs g, G0 = fg10  : : : gt0 g a g =    + m +    kde m 2 hLT (G0 ; fgg)i (tj. g nen redukovan pro G0). Potom m = a1 LT g10 +    + at LT gt0 pro n jak vhodn polynomy a1 : : : at. Protoe G i G0 jsou Grobnerovy b
ze tho ide
lu, plat hLT Gi = hLT G0i, a tedy kad LT gi0 lze vyj
dit jako kombinaci LT g1 : : :  LT gs. Odtud u plyne m 2 hLT Gi a protoe je G0 minim
ln, je m 2 hLT (G nfgg)i, co je spor s pedpokl
danou redukovanost g pro G.




3.10 V ta. Nech I  k$x1 : : : xn] je nenulov. Pak pro ka d monomiln uspodn

existuje prv jedna redukovan Grobnerova bze idelu I . Navc ka dou Grobnerovu bzi lze algoritmicky redukovat. Dkaz: Pedpokl
dejme, e hGi = I , G je Grobnerova. S ohledem na lemma 3.6 lze pedpokl
dat, e G je i minim
ln. (Algoritmus minimalizace je zejm, sta testovat pouze d litelnost vedoucch monom.)

22

3 BUCHBERGERV ALGORITMUS

Nech g 2 G nen redukovan. Pi d len g=(G ;fgg) se tedy LT g nutn dostane do zbytku, protoe nem
m bt d liteln (b
ze je minim
ln). Tedy LT (g G;fgg) = LT g, protoe nic jinho u neme bt vedoucm lenem zbytku. Ozname   g0 := g G;fgg a G0 := G ; fgg fg0g G0 je op t minim
ln Grobnerovou b
z ide
lu I , protoe hLT G0i = hLT Gi, tjt_ak plat hLT G0 i = hLT I i. Polynom g 0 je zejm redukovan pro G0 dky vlastnostem algoritmu pro d len. Byl-li n jak h 6= g redukovan pro G, zst
v
podle pedchozho lemmatu redukovan i pro G0. Tm je d
n algoritmus pro redukci Grobnerovy b
ze. Zbv
dok
zat jednoznanost. Pedpokl
dejme dv redukovan Grobnerovy b
ze G Ge nenulovho ide
lu I . Plat tedy hLT Gi = hLT I i = hLT Ge i. Protoe tento ide
l je monomi
ln, lze pro n j aplikovat Dicksonovo lemma. S odvol
nm na konstrukci b
ze v jeho dkazu lze tvrdit, e existuje pr
v jedna monomi
ln b
ze monomi
lnho ide
lu tak, e koe&cienty jejch len jsou rovny jedn a 
dn z len tto b
ze ned l jin. Podle de&nice minimality mus bt LT G i LT Ge pr
v takovou b
z. Tedy LT G = LT Ge . Ke kadmu g 2 G tedy exisuje pr
v jedno g~ 2 Ge takov, e LT g = LT g~. Plat g ; g~ 2 I . Protoe G je Grobnerova, plat g ; g~ G = 0. 0leny LT g LT g~ se odetou u v g ; g~. Protoe ob b
ze jsou redukovan, neme bt 
dn ze zbvajcch len g ; g~ d liteln ktermkoli z LT G = LT Ge . Mus se tedy dostat do zbytku. Plat tedy g ; g~ = g ; g~ G = 0 Tm je jednoznanost dok
z
na.
Algoritmus konstrukce redukovan Grobnerovy b
ze vyplvajc z pedchoz v ty sice vede k cli, ale zdaleka nen optim
ln. Jeho prvn 
st, algoritmus uveden za v tou 3.5 toti me d
t vsledek z mnoha polynom, resp. polynom vysokch stup i koe&cient. Optimalizace5 spov
v pb nm aplikov
n minimalizace, normov
n a redukce na mezivsledky. Sice jsme neuk
zali, e si to meme dovolit, v dkaze pedchoz v ty se siln vyuvalo toho, e b
ze, kter
je redukov
na, byla minim
ln Grobnerova, v jistch ppadech ale tento postup aplikovat lze. Bohuel nen jednoduch rozhodnout, kdy a kter ze t zmn nch krok pout. Vechny dostupn algoritmy se tedy opraj o n jakou heuristiku, nicmn ke kadmu lze zkonstruovat rozumn vypadajc vstup, pro kter na soudob technice zhavaruje pro nedostatek pam ti. Nepli povzbudiv, ale pro v tinu b nch aplikac nat st algoritmy pli neselh
vaj. V tuto chvli m
me odpov di na dv z dve poloench ot
zek. G
f 2 I () f = 0 pro Grobnerovu b
zi G ide
lu I (dsledek 3.2).
Dva ide
ly jsou stejn pr
v tehdy, kdy maj stejn redukovan Grobnerovy b
ze. V obou ppadech nez
le na zvolenm monomi
lnm uspo
d
n. Tento termn chpeme ve smyslu informatick m, matematici by snad radji vidli vylepen { meliorace. 5

3.4 Zefektivn n algoritmu

23

3.4 Zefektivnn algoritmu

Podstatnm kritriem pouitm v naivn verzi algoritmu je tvrzen v ty 3.5. Vpoet S -polynomu a n
sledn d len se zbytkem je nejbolestiv j msto algoritmu z hlediska asov n
ronosti. Pokusme se nalzt ekvivalentn kritrium, kter bude snadn ji implementovateln. 3.11 Denice. Zvolme pevn monomi
ln uspo
d
n. Nech G = fg1 : : : gtg  k$x1 : : : xn]. ekneme, e f 2 k$x1 : : : xn] se redukuje na g modulo G (peme f !G g), pokud existuj n jak
a1 : : : at 2 k$x1 : : : xn] tak, e f = a1g1 +    + atgt + g a z
rove multideg f  multideg aigi pro kad i = 1 : : : t. Polynomy a1 : : : at v de&nici jsou veskrze libovoln, nemus se jednat o vsledek d len se zbytkem. 3.12 Lemma. Nech G = (g1 : : : gs ) 2 (k$x1 : : :  xn])s, f 2 k$x1 : : :  xn]. Plat implikace f G = 0 =) f !G 0 Opak obecn neplat.
G 2 2 Napklad f = xy ; x, G = (xy + 1 y ; 1). Potom f = ;x ; y, ale pitom f = x(y2 ; 1). V dkazu st ejnho kritria (v ta 3.5) se ale vyuv
pouze vlastnosti f !G 0. Odtud plyne n
sledujc 3.13 D sledek. Bze G = fg1 : : :  gtg je Grobnerova prv tehdy, kdy S (gi  gj ) !G 0 pro vechna i j . 3.14 V ta. Nech G  k$x1 : : :  xn] je konen, f g 2 G. Nech navc LCM (LM f LM g) = LM f  LM g. Potom S (f g) !G 0. Dkaz: Bez jmy na obecnosti meme pedpokl
dat LC f = LC g = 1. Potom lze vyj
dit f = LM f + p g = LM g + q Potejme S (f g) = LM g  f ; LM f  g = (g ; q)f ; (f ; p)g = gp ; fq Pitom stupn gp i fq jsou jist men ne stupe S (f g).
3.15 Denice. Nech F = (f1 : : :  fs) 2 (k$x1 : : : xn])s. Syzygy6 vedoucch len nazv
me s-tici polynom S = (h1 : : : hs) takovou, e s X hi LT fi = 0 i=1

Symbolem S (F ) zname mnoinu vech s-tic, kter danou podmnku spluj. 6

esky sp
aen, zachycuje algebraick relace mezi vedoucmi leny.

24

3 BUCHBERGERV ALGORITMUS

Ozname-li ei jednotkov vektory ve volnm modulu7 (k$x1 : : : xn ])s, kadou syzygy lze vyj
dit s X S = hiei i=1

Kad S -polynom nad ffi fj g  F odpovd
prvku volho modulu   Sij := LTx f ei ; LTx f ej kde x = LCM (LM fi LM fj ) i j kter vdy pat do S (F ). Termn S -polynom poch
z pr
v z tto korespondence. Na druh stran kadou syzygy S 2 S (F ) lze vyj
dit jako line
rn kombinaci vraz Sij . 3.16 V ta. Nech F = (f1 : : : fs) 2 (k$x1 : : :  xn])s a S 2 S (F ). Potom lze vyjdit X S = uij Sij kde uij jsou vhodn polynomy i<j

Dkaz je analogick dkazu lemmatu 3.4 a pro velkou oklivost ho rad ji vypustme.
3.17 Denice. Homogenn syzygy S 2 S (F ) stupn  2 N0 n je tvaru

c1x
1 e1 +    + csx
s es kde ci 2 k a i + multideg fi =  pro vechna takov
i, kde ci 6= 0. 3.18 Lemma. Nech F = (f1 : : :  fs) 2 (k$x1 : : : xn])s. Plat 1. Ka dou syzygy S 2 S (F ) lze vyjdit jednoznan jako souet homogennch syzygy z S (F ). 2. S (F ) je podmodul ve volnm modulu (k$x1 : : : xn])s s bz vybranou z homogennch syzygy Sij .




Podmodul S (F ) pro netrivi
ln F nen voln. Pro b
zi S (F ) nejsou nutn teba vechny Sij . Napklad v lexikogra&ckm uspo
d
n x < y < z pro F = fx2y2 +z xy2 ;y x2y + yzg dost
v
me S12 = (1 ;x 0), S13 = (1 0 ;y), S23 = (0 x ;y), tj. S23 = S13 ;S12. 3.19 V ta. Bze G = fg1 : : :  gtg idelu I  k$x1 : : : xn] je Grobnerova prv tehdy, kdy pro ka dou syzygy S = h1e1 +    + htet v homogenn bzi S (G) plat S  G ! 0 kde S  G = Pt h g G

i=1 i i

Dkaz je op t analogick v t 3.5.
Jako kritrium pro zjit n, zda dan
b
ze je Grobnerova tedy sta testovat redukovatelnost jistch velmi speci
lnch syzygy (pouze prvk homogenn b
ze podmodulu S (G)) na 0. Zobecnn vektorov ho prostoru. Denice modulu je zcela stejn, jen pole skalr zamnme libovolnm okruhem. Voln moduly jsou prv kart zsk mocniny okruhu skalr s operacemi denovanmi po komponentch. Vechny vektorov prostory jsou voln dky invertibilit nenulovch skalr. 7

3.4 Zefektivn n algoritmu

25

3.20 V ta. Nech G = (g1 : : : gt) a S

 fSij j 1  i < j  tg je bze S (G). Pedpokldejme, e pro n jak rzn gi gj  gk plat LT gk j LCM (LM gi  LM gj ). Jestli e Sik  Sjk 2 S, pak S ; fSij g je tak bze S (G). Dkaz: Ozname xi
j := LCM (LM gi  LM gj ). Pedpokl
d
me, e xi
k  xj
k jxi
j . Od-

tud zejm

i
j i
j Sij = xxi
k Sik ; xxj
k Sjk Tedy Sij je v b
zi S zbyten.
Dsledek 3.13 poskytuje n
hradn kritrium pro vpoet Grobnerovy b
ze, navc v ty 3.14 a 3.20 d
v
zefektivn n. V tuto chvli ji meme formulovat algoritmus, kter je vylepenou podobou naivnho Buchbergerova. Vstupem je n jak
b
ze F = (f1 : : :  fs), vstupem Grobnerova b
ze G.

Algoritmus 3.2

1. B := f(i j ) j 1  i < j  sg, G := F , t := s 2. while B 6= 2.1. vezmi libovoln (i j ) 2 B 2.2. if LCM (LT fi LT fj ) 6= LT fi  LT fj and not Test (fi fj  B ) 2.2.1. S := S (fi fj ) G 2.2.2. if S 6= 0 2.2.2.1. t := t + 1 2.2.2.2. ft := S 2.2.2.3. G := G fftg 2.2.2.4. B := B f(i t) j 1  i < tg 2.3. B := B ; f(i j )g Funkce Test ov uje podmnku v ty 3.20, tj. vrac true, pokud existuje n jak k 2= fi j g takov, e (i k ) (j k ) 2 B (pi vhodnm poad dvojic) a pitom z
rove plat LT fk j LCM (LT fi LT fj ). Invarientem algoritmu je tvrzen, e B neobsahuje ty dvojice, o nich vme, e se S -polynom redukuje na nulu (bu) je to patrn z testu 2.2, nebo si to zarume krokem 2.2.2.3). Algoritmus zastav v dsledku v ty 2.17 (Ascending Chain Condition) a vstupem je skuten Grobnerova b
ze. Testy jsou v souhrnu podstatn mn pracn, ne vpoty S -polynom v pvodnm algoritmu a n
sledn opakovan d len. Problmy okolo vhodnosti minimalizace a redukce Grobnerovy b
ze v danm okamiku vpotu ovem zst
vaj. Jako vedlej produkt algoritmu zsk
me informace o algebraickch relacch mezi polynomy vznikl Grobnerovy b
ze. Zam me se o n co podrobn ji na manipulaci algoritmu se syzygy. Ozname-li I mnoinu vech dvojic (i j ) takovch, e Test(fi fj  B ) = false v okamiku zastaven, je mnoina n o S := Sij j (i j ) 2 I takov
b
ze S (G), e pro vechny jej prvky Sij plat Sij  G = S (fi fj ) !G 0

26

3 BUCHBERGERV ALGORITMUS

Toto tvrzen plyne ze zp tn rekonstrukce vpotu algoritmu, dvojice (i j ) byla toti odstran na z B bu) tehdy, bylo-li mon Sij vyj
dit z ostatnch, nebo pi platnosti ve uveden podmnky. Tedy algoritmus navc produkuje b
zi S (G). N jak
verze Buchbergerova algoritmu je naimplementov
na ve vech programovch systmech zahrnujcch potaovou algebru, v tinou je na n m podstatn

st algebraickch manipulac zaloena. Jako pklad uve)me systm MAPLE, kter je patrn v na sti nejdostupn j, a MATHEMATICA (ten je bohuel dostupn pouze na stroji princ.math.muni.cz). Velice strunou uk
zku mete vid t na obr. 6. Prvn pkaz slou k naten knihovny grobner, druh vyvol
n
pov du tkajc se tto knihovny, tet pot
redukovanou Grobnerovu b
zi pro ide
l uveden za de&nic 3.7 v gradovanm lexikogra&ckm uspo
d
n (tdeg je zkratka pro total degree), dal tot v lexikogra&ckm uspo
d
n (plex=pure lexicographic). N
sledujc pkazy ilustruj rzn chov
n pouitch uspo
d
n (leadmon d
v
vedouc koe&cient a monom, spoly je S-polynom v zadanm uspo
d
n, normalf je v podstat zbytek po d len). Snadn
modi&kace pedchoz teorie (od za
tku kapitoly 2) vede k rozen na podmoduly ve volnch modulech. Pak lze aplikovat pedchoz algoritmus na vlastn vsledek, dostaneme pslunou Grobnerovu b
zi podmodulu S (G) atd. Lze uk
zat, e tento postup tak zastav. Poty gener
tor v zskanch Grobnerovch b
zch maj mimo jin topologickou interpretaci, lze z nich odvodit nap. poty k-rozm rnch d r ve variet apod. Ppadn z
jemce me najt vce podrobnost v diplomov pr
ci Zorky Velenov, kter
je k dispozici ve stejnm adres
i, jako tyto texty.8

Zorka uvd obecn vlastnosti modul nad komutativnmi okruhy, Buchbergerv algoritmus v t to obecn situaci vetn zmnn iterace a ukazuje, e tato se mus zastavit nejpozdji po tolika krocch, kolik je volnch promnnch. Navc p
edstavuje specializovan software { Macaulay. 8

3.4 Zefektivn n algoritmu

27

> with(grobner); [

finduni, finite, gbasis, gsolve, leadmon, normalf, solvable, spoly ]

> ?grobner > gbasis([x^3-2*x*y,x^2*y-2*y^2+x],[x,y],tdeg);

x y, x

x+2y

, -

> gbasis([x^3-2*x*y,x^2*y-2*y^2+x],[x,y],plex);

x - 2 y , y! > leadmon(x-2*y^2, [x,y],plex); [ 1,

x]

> leadmon(x-2*y^2, [x,y],tdeg); -2,

y

> spoly(x-2*y^2,y^3, [x,y],plex); > normalf(spoly(x-2*y^2,y^3, [x,y],plex),[x-2*y^2,y^3], > [x,y],plex); -2

y#

0

> spoly(x-2*y^2,y^3, [x,y],tdeg); > normalf(spoly(x-2*y^2,y^3, [x,y],tdeg),[x-2*y^2,y^3], > [x,y],tdeg);

xy xy >

Obr. 6: Uk
zka z
pisnku systmu MAPLE

28

4 TEORIE ELIMINAC PROMNNCH

4 Teorie eliminac prom nnch Pro vahy o polynomech v rznch potech prom nnch budeme povaovat okruh k$xp+1 : : : xn] za podokruh k$x1 : : : xn]. Jedn
se o polynomy, v nich se nevyskytuj prom nn x1 : : : xp. Je to skuten podokruh, ale u ne ide
l.

4.1 Eliminace

4.1 Denice. Nech I = hf1 : : : fsi  k$x1 : : :  xn]. Pro p = 1 : : :  n de&nujeme Ip := I \ k$xp+1 : : :  xn]

Tuto mnoinu nazveme p-tm elimina nm ide lem. Samozejm Ip je ide
lem pouze v k$xp+1 : : : xn]. Na rovni polynomi
lnch rovnic Ip obsahuje vechny rovnice, kter jsou dsledky systmu f1 = 0 : : :  fs = 0 a v kterch vystupuj pouze prom nn xp+1 : : :  xn. 4.2 V ta Eliminan. Nech I  k$x1 : : : xn] je idel, G = fg1 : : : gm g jeho Grobnerova bze vzhledem k lex x2 >lex    . Potom pro ka d p = 0 : : :  n je Gp := G \ k$xp+1 : : :  xn] Grobnerovou bz idelu Ip. Dkaz: Bez jmy na obecnosti meme uvaovat Gp = fg1  : : :  gr g. Protoe G  I , je i Gp  Ip. Inkluze hGp i  Ip plat trivi
ln . Dok
eme opanou. Nech f 2 Ip, chceme f = h1g1 +    + hr gr Provedeme d len pvodn Grobnerovou b
z G. Protoe f 2 I , plat f G = 0, a tedy f = h1g1 +    + hr gr + hr+1gr+1    + hmgm Kad z polynom gr+1 : : :  gm mus obsahovat n jakou z prom nnch x1 : : :  xp, jinak by byl prvkem Gp. Vzhledem k vlastnostem lexikogra&ckho uspo
d
n takovou prom nnou obsahuj i LT gr+1 : : : LT gm . Uv domme-li si postup algoritmu pro d len se zbytkem a skutenost, e v f nen 
dn monom obsahujc n kterou z x1 : : : xp, mus bt hr+1 =    = hm = 0. Tedy f 2 hGpi. Dok
zali jsme nejen poadovanou inkluzi, ale i fakt, e d len f=G dopadne na Ip stejn jako f=Gp . Pro 1  i < j  r uvaujme S -polynomy S (gi gj ). Plat S (gi gj ) Gp = S (gi gj ) G = 0 a tedy Gp je Grobnerova b
ze ide
lu Ip.
Zejm aplikac eliminan v ty na minim
ln resp. redukovanou Grobnerovu b
zi zsk
me op t b
zi minim
ln resp. redukovanou. Jedin
v dkazu vyuit
vlastnost lexikogra&ckho uspo
d
n je tvrzen, e z n kterch prom nnch objevujcch se v polynomu se ta, kter
je v danm uspo
d
n nejv t, objev i ve vedoucm lenu. To je ovem podstatn slab poadavek, ne de&nice lexikogra&ckho uspo
d
n. Proto lze pi skutench implementacch pouvat uspo
d
n v podstat gradovan s touto vlastnost zajit nou. Dos
hne se tak v tinou efektivn jch vpot, protoe ist lexikogra&ck uspo
d
n zpravidla vede k nepjemnmu n
rstu exponent.

4.2 V ta o rozen

29

4.2 Vta o roz en

Spolenou mylenkou n
sledujcch vah je ch
p
n k$x1 : : : xn] jako k$x2 : : :  xn]$x1], tedy polynom v prom nnch x1 : : : xn povaujeme za polynom v jedn prom nn x1 a koe&cientech z k$x2 : : :  xn]. To ovem nen pole, ale pouze okruh. Proto msto n j pro ely dkaz pouijeme odpovdajc podlov t leso k(x2 : : :  xn) a na z
v r vdy uk
eme, e se ve podstatn stejn odehr
lo v k$x2 : : : xn]. 4.3 V ta O rozen. Nech I = hf1 : : : fsi  C $x1  : : :  xn]. Pro ka d i = 1 : : :  s polo me fi := gi (x2 : : : xn )xN1 i + leny ni ho stupn v x1 kde gi 2 C $x2  : : : xn] je nenulov. Nech (a2 : : :  an) je prvek variety V (I1) dan prvnm eliminanm idelem. Pak plat (a2 : : : an) 2= V(g1  : : : gs ) =) 9a1 2 C : (a1 a2 : : :  an) 2 V (I ) Ke korektnmu dkazu se asem propracujeme (kapitola 4.4), zatm jen ilustrativn pklad. Nech f = xy ; 1, g = xz ; 1, I = hf gi. Grobnerova b
ze je y ; z xz ; 1, proto podle eliminan v ty I1 = hy ; zi. Pro kad a 2 C plat (a a) 2 V (I1). Vyj
dme polynomy y ; z xz ; 1 podle stupn v x

y ; z = (y ; z)x0 xz ; 1 = zx1 ; 1 Zejm pro a 6= 0 existuje rozen (1=a a a) 2 V (I ). Rozen znamen
postup do znan mry opan k eliminaci. K variet prvnho eliminanho ide
lu (pedpokl
d
me, e tu u urme sn
z) hled
me hodnoty pro x1, aby vsledn bod padl do pvodn variety. Cel problm lze ch
pat jako hled
n spolenho koene polynom po dosazen u zn
mch n ; 1 sloek.

4.3 Existence spole nch ko en

4.4 Denice. Nech k je pole. Polynom f 2 k$x1 : : : xn] nazveme ireducibiln nad k,

plat-li f 2= k a f nen souinem nekonstantnch polynom. 4.5 Lemma. Nech f 2 k$x1 : : : xn] a plat f jgh. Pokud je f ireducibiln, pak f jh nebo f jg. Dkaz je jednoduch ale technicky zdlouhav a opr
se o zmn nou mylenku rozen na podlov t leso. Vede se indukc k potu prom nnch.
4.6 Lemma. Nech f g maj kladn stupe v x1. Potom maj spolen faktor v k$x2 : : :  xn]$x1] s kladnm stupn m v x1 prv tehdy, kdy maj takov faktor v k(x2 : : :  xn)$x1]. Dkaz: Implikace od ppadu v k $x2 : : : xn]$x1] k k (x2 : : :  xn )$x1] je zcela zejm
. Zam me se tedy na opanou. Pime f = ~hf~1 g = ~hg~1 kde ~h f~1 g~1 2 k(x2 : : : xn)$x1]. D
le za d ozname spolen jmenovatel zlomk ~h f~1 g~1 a polome h := d~h f1 := df~1 g1 := dg~1

30

4 TEORIE ELIMINAC PROMNNCH

Ty u nutn padnou do k$x2 : : :  xn]$x1]. Plat d2f = hf1 d2g = hg1 a op t se pohybujeme v k$x2 : : :  xn]$x1]. Protoe h~ = h=d a d 2 k$x2 : : : xn], mus nutn existovat ireducibiln faktor h1 v h s kladnm stupn m v x1. Vme, e h1jd2f . Protoe je ireducibiln, mus d lit d nebo f . Ale d nem
s x1 nic spolenho, a tak nutn h1jf . D litelnost h1jg se uk
e analogicky.
4.7 V ta. Ka d nekonstantn polynom f 2 k$x1 : : : xn] lze pst jako f = f1    fr souin ireducibilnch polynom. Toto vyjden je jednoznan a na permutaci faktor a nsobky skalrem. Dkaz: Tvrzen v ppad polynom jedn prom nn je veobecn zn
m. Na z
klad pedchozho lemmatu lze zobecnit i do okruhu polynom vce prom nnch.
4.8 Lemma. Nech f g 2 k$x], deg f = l > 0, deg g = m > 0. Polynomy f g maj spolen faktor prv tehdy, kdy 9A B 2 k$x] tak, e
A B nejsou oba nulov
deg A < m, deg B < l
Af + Bg = 0 Dkaz: \=)" Pime f = hf1, g = hg1. Pak deg f1 < l, deg g1 < m. Plat 0 = g1f1 ; f1g1 = g1hf1 ; f1hg1 = g1f ; f1g co bylo teba dok
zat. \(=" Sporem. Pedpokl
dejme, e f g nemaj spolen faktor. Nech napklad B 6= 0. Plat GCD (f g) = 1. Z Bezoutovy rovnosti dost
v
me ~ + Bg ~ = 1 =) B = (Af ~ + Bg ~ )B = ABf ~ ; BAf ~ = (AB ~ ; BA ~ )f Af a tedy deg B  l, co je spor.




Ozname leny polynom A B z pedchozho lemmatu A = c0xm;1 +    + cm;1 B = d0xl;1 +    + dl;1 Porovn
me-li koe&cienty u jednotlivch mocnin x pi tomto vyj
den tet podmnky lemmatu, dost
v
me homogenn systm rovnic a0c0 + b0d0 = 0 a1c0 + a0c1 + b1d0 + b0d1 = 0 ... alcm;1 + bmdl;1 = 0 Ten m
nenulov een (v prom nnch c0 : : :cm;1  d0 : : : dl;1) pr
v tehdy, kdy je jeho matice singul
rn. Pro ni zav
dme zvl
tn oznaen.

4.3 Existence spolench koen

31

4.9 Denice. Nech f g 2 k$x] jsou kladnho stupn . Ozname f = a0xl +    + al g = b0xm +    + bm Sylvesterovou matic polynom f g rozumme matici Syl (f g x) 
du m + l tvaru

0 BB BB BB BB BB BB BB BB B@

a0 a1 a2 ... al 0 ... 0

0  a0 a1 . . .

0 ... 0 a0

al

...



... 0 al

b0 b1 b2 ... bm 0 ... 0

1 CC CC CC CC CC CC ... C CC CC ... A 0 bm

0  b0 b1 . . .

bm 

0 ... 0 b0

Rezultantem polynom f g vzhledem k prom nn x nazveme jej determinant. Zname Res (f g x). Pro f g 2 k$x] kladnch stup je Res (f g x) zejm prvkem pole k. Lze jej ch
pat jako polynom v prom nnch a0 : : : al b0 : : : bm s celoselnmi koe&cienty. 4.10 D sledek. Polynomy f g 2 k$x] maj spolen faktor (tedy i koen pro algebraicky uzaven k) prv tehdy, kdy Res (f g x) = 0. Dkaz: Plyne bezprostedn z lemmatu 4.8 a de&nice rezultantu.
4.11 Lemma. Nech f g 2 k$x] jsou polynomy kladnho stupn . Pak existuj takov A B 2 k$x] tak, e plat Af + Bg = Res (f g x) Dkaz: Pro Res (f g x) = 0 je tvrzen pmm dsledkem lemmatu 4.8. Uvaujme ~ B~ , takovch, e tedy ppad Res (f g x) 6= 0. Z Bezoutovy rovnosti plyne existence A ~ + Bg ~ = 1. Ozname jednotliv leny t chto polynom Af

A~ = c0xm;1 +    + cm;1 B~ = d0xl;1 +    + dl;1 Porovn
me-li koe&cienty u jednotlivch mocnin prom nn x v Bezoutov rovnosti, zsk
me systm a0c0 + b0d0 = 0 a1c0 + a0c1 + b1d0 + b0d1 = 0 ... alcm;1 + bmdl;1 = 1

32

4 TEORIE ELIMINAC PROMNNCH

Ch
peme-li tento systm v prom nnch c0 : : :  cm;1 d0 : : : dl;1 , je jeho matice pr
v Syl (f g x). Protoe pedpokl
d
me nenulovost rezultantu, lze aplikovat Cramerovo pravidlo a zsk
v
me B A ~= B A~ = Res (f g x) Res (f g x) pro n jak
vhodn
A B . Odtud ji plyne poadovan
rovnost.
Rezultant lze pom rn efektivn vypotat modi&kac Euklidova algoritmu. Zejm plat Res (f g x) = (;1)lm Res (g f x) D
se uk
zat, e pokud f = qg + r, kde deg r < deg g (krok algoritmu), pak Res (f g x) = Res (r g x)  bl0;deg r kde b0 = LC g N
vod k dkazu je uveden v r
mci cvien ke kapitole tkajc se rezultant v $2]. S ohledem na mylenku pedloenou na za
tku kapitoly meme zobecnit de&nici rezultantu na polynomy ve vce prom nnch. Res (f g x1) de&nujeme zcela analogicky, jen polynomy f g ch
peme jako polynomy v prom nn x1 a koe&cientech z k$x2 : : : xn]. 4.12 V ta. Nech f g 2 k$x1 : : : xn] jsou kladnho stupn v x1. Pak 1. Res (f g x1) 2 I1, kde I1 je prvn eliminan idel hf gi. 2. Res (f g x1) = 0 prv tehdy, kdy f g maj spolen faktor kladnho stupn v x1. Dkaz: Uvaujme op t f g 2 k$x2 : : : xn]$x1]  k (x2 : : :  xn)$x1]. To u je pole, a tak lze aplikovat dsledek 4.10 a lemma 4.11. 1. Pokud Res (f g x1) = 0, je tvrzen zejm. Pmo z de&nice rezultantu plyne Res (f g x1) 2 k$x2 : : :  xn]. Podle lemmatu 4.11 existuj n jak
A B 2 k(x2 : : : xn )$x1] tak, e Res (f g x1) = Af + Bg, co u je i prvek hf gi. Zbv
uk
zat, e A B 2 k$x2 : : : xn]$x1]. Ale tyto polynomy jsou konstruov
ny v dkazu lemmatu 4.11 tak, e tuto podmnku spluj. 2. Lemma 4.6 umouje pohybovat se bez problm mezi okruhem k$x2 : : : xn] a polem k(x2 : : : xn). V poli je ale druh

st tvrzen zejm
.




4.4 Dkaz vty o roz en

Nyn m
me k dispozici n
stroje dostaten siln pro dkaz v ty o rozen (4.3). Pro jednoduchost ho detailn provedeme pouze pro ide
ly generovan jen dv ma polynomy. Dkaz 4.3: Uvaujme f g 2 C $x1  : : : xn]  C (x2  : : : xn )$x1] s vedoucmi koe&cienty a0 b0. Tradin ozname I1 := hf gi \ C $x2  : : :  xn]. Chceme uk
zat, e pro kad (c2 : : :  cn) 2 V (I1) ; V(a0 b0) existuje c1 2 C tak, e (c1 : : : cn) 2 V (hf gi). Ozname c := (c2 : : : cn) a konvenn pime f (x1 c) = f (x1 c2 : : :  cn). Sta uk
zat   Res f (x1  c) g (x1 c) = 0

4.5 Hilbertova v ta o nulch

33

Potom u podle pedchozho bude existovat spolen koen c1 2 C a (c1 : : : cn) padne do V(f g). Pedpokl
dejme nejprve, e a0(c) 6= 0 a z
rove b0(c) 6= 0. Ozname h := Res (f g x1). Podle v ty 4.12 plat h 2 I1, a tedy zejmna h(c) = 0. Dosazenm c za (x2 : : : xn) zsk
v
me   Res f (x1  c) g (x1 c) = h(c) = 0 Uvaujme nyn nap. b0(c) = 0, a0(c) 6= 0. Potom stupe g(x1 c) v x1 je men ne m a h(c) nelze pout jako v pedchozm ppad . Meme ovem uv
it jinou b
zi ide
lu N hf g i, nap. hf g + xN 1 f i a volit N tak velk, aby stupe x1 f v x1 byl v t, ne stupe N g. Potom bude vedouc koe&cient g + x1 f roven a0 a je mono aplikovat prvn 
st dkazu.
2 2 Uvame napklad ide
l I = hx y;1 x z;1i. Prvn eliminan ide
l je potom hy;zi. Varieta V (I ) je jak
si hyperbola o dvou v tvch poloen
v rovin y = z. Tato rovina je vlastn V (I1). V ta o rozen tvrd, e ke kad dvojici (y z) 2 V (I1) s vyjmkou jistch bod nalezneme hodnotu pro x, abychom zskali bod pvodn variety. Jinmi slovy na tm  kad pmce dan dvojic y z (tedy voln v x) lze najt bod patc do pvodn variety. Problematickm bodem v tomto pklad je pr
v y = z = 0, k n mu rozen neexistuje. Obecn se jedn
pr
v o ty body, kter nele v projekci pvodn variety podle prom nn x1, ale padnou do nejmen a&nn variety, kter
tuto projekci obsahuje (viz. kapitola 4.6). Obecn dkaz v ty o rozen je v podstat analogick pedchozmu, je vak technicky n
ron. Pro ide
l I = hf1 : : :  fsi se vytvo polynom g = u2f2 +    + usfs 2 C $u2  : : : us  x1 : : :  xm ]. Uvauje se rezultant X Res (f1 g x1) = h
(x2 : : :  xn )  u
kde u = (u2  : : : us ) a porovn
vaj se


koe&cienty u
.

V me a detaily penechejme jen v
nm z
jemcm.

4.5 Hilbertova vta o nulch

4.13 V ta Hilbertova o nulch. Nech pole k je algebraicky uzaven, f f1 : : :  fs 2 k$x1 : : : xn]. Plat   f 2 I V(f1 : : : fs)

()

f m 2 hf1  : : : fsi pro vhodn m 2 N0

Dkaz: Nejprve dok
eme, e kad ide
l I  k$x1 : : : xn] spluje

(2)

V (I ) =

()

I = k$x1 : : :  xn]

To je bezprostedn dsledek v ty pro f = 1. V z
v ru uk
eme, e se jedn
o ekvivalentn tvrzen. Kad algebraicky uzaven pole je nekonen. Jinak by stailo uvaovat polynom (x ; a1)    (x ; an) + 1, kter nem
koen { spor. Proto implikace zprava doleva plat trivi
ln . Dkaz zleva doprava vedeme indukc. Pedpokl
dejme V (I ) = .

34

4 TEORIE ELIMINAC PROMNNCH

1. Nech n = 1. Pak I = hf1i podle dsledku 1.13. Protoe f1 nem
koeny a k je algebraicky uzaven, mus bt f1 konstanta. Tedy hf1i = k$x1]. 2. Nech I = hf1 : : : fs i. Je-li n kter z f1 : : : fs konstanta, je tvrzen zejm. Pedpokl
dejme tedy nekonstantn polynomy. Pedpokl
dejme navc, e f1 je velmi speci
lnho tvaru f1(x1 : : : xn) = cxN1 + leny s nim stupn m v x1 kde c 2 k, c 6= 0 je konstanta. Poslze uk
eme, e si tento pedpoklad meme dovolit. Z v ty o rozen (4.3) dky speci
lnmu tvaru f1 plyne 1(V (I )) = V (I1). Pedpokl
d
me V (I ) = , a tedy i 1(V (I )) = . I1 u je pouze v n ; 1 prom nn, a tedy podle induknho pedpokladu 1 2 I1. Odtud zejm i 1 2 I . Zbv
uk
zat, e v obecnm ppad umme problm redukovat tak, abychom mohli pedpokl
dat speci
ln tvar f1. K tomu uijeme homomor&smus k$x1 : : : xn] ! k$~x1 : : : x~n] x1 := x~1 x2 := x~2 + a2x~1 ... xn := x~n + anx~1 Pokud neexistuje een systmu rovnic po tto transformaci, neexistovalo ani ped n, pokud pat 1 do obrazu n jak mnoiny, pat i do vzoru (ve jsou vlastnosti homomor&smu). Tyto transforman rovnice s nezn
mmi parametry dosadme do f1. Cht li bychom, aby koe&cient lenu nejvyho stupn v x1 byl konstantn. Pitom monom s nejvym stupn m v x~1 me vzniknout z monomu s nejvym soutem stup ve vech prom nnch xi. Poadavek, aby jeho koe&cient nez
visel na ostatnch prom nn je polynomi
lnch podmnka na parametry a2 : : :  an. Tm je dok
z
no tvrzen (2). Zbv
uk
zat, e implikuje dokazovanou v tu. Nejprve sm r tvrzen zprava doleva. Pokud f m 2 hf1 : : : fsi, tak f m 2 I(V(f1 : : :  fs)), to znamen
(f (a))m = 0 pro vechna a 2 V(f1 : : :  fs). Protoe k je obor integrity, mus nutn i f (a) = 0, a tedy f 2PI(V(f1 : : : fs )). Obr
cen chceme f m = si=1 hifi. Uvame ide
l I~ = hf1 : : : fs  1 ; yf i  k$x1 : : :  xn y]: Zvolme a = (a1 : : :  an+1) libovoln. Pokud (a1 : : : an) 2= V (I ), pak zejm a 2= V (I~). Pokud naopak (a1 : : : an) 2 V (I ), plat i f (a1 : : :  an) = 0, a tedy 1 ; yf se urit nenuluje na a. Dohromady V (I~) = , tedy 1 2 I~ a lze ps
t s X 1 = pi(x1 : : : xn y)fi + q(x1 : : : xn y)(1 ; yf ) Za y

i=1 dosadme 1=f (x1  : : : xn).

Potom v k(x1 : : : xn) dost
v
me rovnost   1 1 = pi x1 : : :  xn f (x1:::x n ) fi s X i=1

Vyn
sobenm f m s m dostaten velkm zsk
me poadovanou rovnost.




4.6 V ta o uzv ru

35

4.6 Vta o uzvru

Pipomeme, e projekci odez
vajc prvnch k souadnic zname k . 4.14 Lemma. Nech Ik = hf1 : : :  fsi \ C$xk+1 : : : xn]. Potom  

k V(hf1 : : : fs i)  V (Ik) Dkaz: Nech f 2 Ik je libovoln. Je to polynom pouze v prom nnch xk+1  : : :  xn . Uvame libovoln (a1 : : :  an) 2 V(hf1 : : :  fsi). Protoe f 2 hf1 : : :  fsi, jist plat f (ak+1 : : : an) = 0, a tedy f ( k (a1 : : :  an)) = 0. Tm je inkluze dok
z
na.
Obecn k (V ) nemus bt varieta, tj. inkluze je ostr
. Viz pklad u v ty o rozen. 4.15 Lemma. Nech V = V(f1 : : : fs )  C n , I1 je prvn eliminan idel a gi jako ve v t o rozen. Pak v C n;1 plat   V (I1) = 1(V ) V(g1 : : :  gn) \ V (I1)




Tedy varieta dan
prvnm eliminanm ide
lem se skl
d
pr
v z projekce pvodn variety a on mn rozm rn mnoiny vymykajcch se bod, kter dotvo projekci na a&nn varietu. S pr
v diskutovanmi vlastnostmi souvis pojem Zariskho topologie. To je takov
topologie na kn , kde k je pole, e uzaven mnoiny jsou pr
v nulov mnoiny systm racion
lnch lomench funkc. 4.16 V ta O uzv
ru. Nech V = V(f1 : : :  fs)  C n a Ik je k-t eliminan idel. Potom plat 1. V (Ik ) je nejmen a nn varieta obsahujc k (V ), tedy uzv r v Zariskho topologii. 2. Pokud V 6= , pak existuje a nn varieta W  V (Ik ) tak, e V (Ik ) ; W  k (V ). Dkaz: Potebujeme dok
zat V (Ik ) = V (I( k (V ))). Uvame libovoln f 2 I( k (V ))  C $xk+1  : : :  xn ]. Zejm f (ak+1  : : : an ) = 0 pro vechna (ak+1  : : : an ) 2 k (V ), a tedy tak f (a1 : : : an) = 0 v C $x1  : : :  xn] pro vechna (a1 : : : an) 2 V . Podle Hilbertovy v ty o nul
ch tedy existuje m tak, e f m 2 hf1 : : : fsi. Protoe f nez
vis na x1 : : : xk , nez
vis na nich ani f m . Uvaujme nyn libovoln a 2 V (Ik). Vme, e ke kadmu polynomu f 2 I( k(V )) existuje m tak, e f m 2 Ik. Pokud f m(a) = 0 mus i f (a) = 0, a tedy i a 2 V (I( k (V ))). Opan
inkluze je zejm
, protoe Ik  I( k(V )). Dkaz druh 
sti v ty pat k netrivi
lnm a op t form
ln komplikovanm. Provedeme ho jen pro ppad k = 1. Podle lemmatu 4.15 meme vyj
dit   V (I1) = 1(V ) V(g1  : : : gs ) \ V (I1) | {z } W

Toto W je zejm a&nn varieta. Pokud W  V (I1), je ve v po
dku. Pro ppad W = V (I1) lze, podobn jako v dkazu v ty 4.3, zlepit gener
tory, aby pouit
b
ze indukovala poadovanou vlastnost. K tomu budeme potebovat n
sledujc lemma.

36

4 TEORIE ELIMINAC PROMNNCH

4.17 Lemma. Pokud W = V (I1), pak V = V(f1 : : : fs g1 : : :  gs).

Dkaz: Protoe se jedn
o variety, je zejm V(f1  : : : fs  g1 : : :  gs )  V . Zvolme libovoln (a1 : : : an). Protoe 1(V )  V (I1), je (a2 : : :  an) 2 V (I1) = W . Tedy nutn z de&nice W plat gi(a2 : : : an) = 0 pro vechna i. Odtud opan
inkluze.




Vrame se k vlastnmu dkazu v ty. De&nujme nov ide
l I~ := hf1 : : : fs  g1 : : :  gsi. Ten podle lemmatu uruje stejnou varietu. Polynomy gi u maj nulov stupe v x1, fi meme nahradit f~i := fi ; gixN1 i , kter maj oste men stupe v x1. f . Pokud bude op t W = V (I1), Podle lemmatu 4.15 zsk
me nov rozklad a nov W cel postup zopakujeme. Po konenm potu krok bu) dojdeme k 
dan vlastnosti anebo vynulujeme stupe v x1. To ale znamen
1(V ) = V (I1) a meme volit W = , co je tak a&nn varieta.
V pkladu 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 C , ale zejm plat pro libovoln algebraicky uzaven pole.

4.7 Korespondence idel a variet

Sumarizujme na z
v r vsledky cel teorie s ohledem na korespondenci algebraickch struktur (ide
ly) a geometrickch objekt (variety) a na odpovdajc si operace na nich. 4.18 Denice. Radik
lovm ide
lem ide
lu I  k$x1 : : : xn ] nazveme p

I := hf 2 k$x1 : : : xn] j 9m 2 N : f m 2 I i Jako dsledek Hilbertovy v ty o nul
ch dost
v
me 4.19 D sledek. Je-li k algebraicky uzavenm, pak pro ka dou varietu V(f1 : : : fs) plat q I(V(f1  : : : fs )) = hf1  : : : fs i 4.20 Denice. Ide
l I  k$x1 : : :  xn] nazv
me prvoide lem, jestlie pro kad f g 2 I je u f 2 I nebo g 2 I . Ide
l je vlastn, pokud f0g 6= I  k$x1 : : : xn], maxim ln, nen-li obsaen v 
dnm oste v tm vlastnm ide
lu. 4.21 Denice. A&nn varieta V  kn se nazv
ireducibiln, jestlie kdykoli V = V1 V2, kde V1 V2 jsou a&nn variety, plat u V = V1 nebo V = V2. To je vcelku pirozen pojem. Napklad varieta V(xy)  R2 nen ireducibiln, tvo ji dv pmky, kter jsou pochopiteln a&nn variety. V tuto chvli se nabz hypotza, dok
zan
v n
sledujc v t . 4.22 V ta. A nn varieta V  kn je ireducibiln prv tehdy, kdy I(V ) je prvoidel. Dkaz: \=)" Nech f  g 2 I(V ) a ozname

V1 := V V2 := V

\ V(f ) \ V(g )

4.7 Korespondence idel a variet

37

To jsou zejm a&nn variety. Plat V = V1 V2, protoe na kadm bod V se mus nulovat alespo jeden z f g. Pedpokl
d
me, e V je ireducibiln, nech tedy napklad V = V1. Urit f 2 I(V1), a tedy i f 2 I(V ). To znamen
, e I(V ) je prvoide
l. \(=" Pedpokl
dejme naopak, e I(V ) je prvoide
l, V = V1 V a napklad V1 6= V . Odtud ostr
inkluze I(V )  I(V1). Urit tak I(V )  I(V2). Zvolme f 2 I(V1) ; I(V ), g 2 I(V2). Protoe V = V1 V2 , plat f  g 2 I(V ). To je prvoide
l, a tedy f 2 I(V ), co jsme vylouili volbou f , anebo g 2 I(V ). Uk
zali jsme I(V2)  I(V ). Tedy tyto ide
ly se rovnaj a mus se rovnat i variety V a V2 .




Vechny z
v ry jsou shrnuty v tabulce 1. K n je nutn jen poznamenat, e pi projekci musme uvaovat uz
v r, protoe, jak ji vme, projekce samotn
nemus jet bt varieta. Algebraick objekty radik
lov ide
l I I(V ) souet ide
l q I +J I(V ) + I(W ) souin ide
l q I J I(V )  I(W ) eliminace prom nnch q I \ k$xk+1 : : : xn ] prvoide
l maxim
ln ide
l Ascending Chain Condition

;! ; ;! ; ;! ; !

Geometrick objekty varieta V (I ) V prnik variet V (I ) \ V (J ) V \W sjednocen variet V (I ) V (J ) V W projekce variety

k (V (I )) ireducibiln varieta jednobodov
varieta Descending Chain Condition

Tabulka 1: Korespondence ide
l a variet

38

5 APLIKACE

5 Aplikace

5.1 eitelnost syst m rovnic

5.1 V ta. Systm f1 = 0 : : :  fs = 0, kde f1 : : : fs

2 k $x1 : : : xn ] a 2 hf1  : : :  fs i, tj.

k je algebredukovan

raicky uzaven pole, nem een prv tehdy, kdy 1 Grobnerova bze tohoto idelu je f1g. Dkaz: Pokud je varieta pr
zdn
, lze tvrdit, e libovoln polynom se nuluje na vech jejch bodech9, tedy i polynom 1. Potom ale, podle Hilbertovy v ty o nul
ch (4.13), plat 1m 2 hf1 : : :  fsi pro n jak m. Naopak je-li 1 2 hf1 : : : fs i, mus to bt nutn cel okruh. Protoe pole k pedpokl
d
me algebraicky uzaven a tedy nekonen, varieta, kde se nuluj vechny polynomy, je u trivi
ln pr
zdn
.
Tedy o danm systmu algebraickch rovnic lze algoritmicky rozhodnout, zda m
nebo nem
een. Alternativn metodou pro tohoto rozhodnut je pm pouit apar
tu rezultant, patrn se tak dos
hne i lep asov sloitosti. Tato problematika ale nen nam clem, a tak ppadn z
jemce odkazujeme na literaturu. 5.2 V ta. Nech V = V (I )  C n je a nn varieta a < libovoln monomiln uspodn. Pak nsledujc tvrzen jsou ekvivalentn. 1. V je konen 2. 8i = 1 : : : n 9mi 2 N0 : xmi i 2 hLT I i 3. Nech G je redukovan Grobnerova bze I . Pak i 8i = 1 : : : n 9mi 2 N0 : xm i = LM g pro n kter g 2 G 4. Faktorokruh10 C $x1  : : : xn]=I nad C je konen rozm rn vektorov prostor. Dkaz: \1 =) 2" Pokud je V = , potom 1 2 I a meme br
t mi = 0 pro kad i. Pedpokl
dejme tedy V 6= a zvolme i. Nech aj 2 C pro j = 1 : : :  k jsou rzn i-t souadnice bod V . Polynom k Y f (xi) := (xi ; aj ) j =1

je nulov ve vech bodech V . Podle Hilberovy v ty o nul
ch existuje m tak, e f m 2 I . Odtud u xkm i 2 hLT I i a sta poloit mi = km. \2 =) 3" Pedpokl
d
me, e xmi i 2 hLT I i. Protoe G je Grobnerova, plat hLT I i = hLT Gi. Ovem jedn
se o monomi
ln ide
ly, a tak mus existovat g 2 G takov, e LT gjxmi i (pmo z de&nice 2.9). Tedy pro n jak vhodn m0i mus bt LT g = 0 xmi i .

Ponkud krkolomn , ale podrobnm rozebrnm dkazu Hilbertovy vty o nulch pro tento p
pad tvrzen skuten dostaneme 10P
ipomeme, e faktorokruh C  () 1 n] nad C je mnoina t
d ekvivalence  ; 2 . 9

x
: : :
x

f

g

I

=I

f

g

5.1 "eitelnost systm rovnic

39

\3 =) 2" je zcela trivi
ln. \2 =) 4" Nech xmi i 2 hLT I i. De&nujme vektorov prostor nad C D E S := x
j x
2= hLT I i Zde je na m st podotknout,
e se nejedn o tyt
zobky. Vnj znamenaj generovn vektorov ho prostoru, tedy mme k pou
it s tn uvnit a nsoben skalrem (tj. komplexn m slem), vnitn generuj idel, tedy se s t uvnit a nsob zvenku polynomem.

Napklad pro I = hx2 y2i je S = h1 x y xyi. Vzhledem k pedpokladu je S konen rozm rn nanejv dimenze m1    mn. Uk
eme, e zobrazen S ! C $x1  : : : xn]=I x
7! $x
] pirozen rozen na polynomy je izomor&smus vektorovch prostor.
Nech x je tak vzorem $x
]. Potom x 2 $x
], tedy x
; x 2 I . Protoe oba jsou prvky S , nen ani jeden z nich prvkem LT I . Kdyby rozdl byl nenulov, jeho vedouc monom, tj. jeden z x
 x by patil do LT I . Proto jejich rozdl mus bt nulov. To znamen
x
= x , tj. zobrazen je prost. P
Nech f =
a
x
je libovoln. Jsou-li vechny monomy x
2 S , pak tda $f ] je jeho obrazem. Pokud nejsou, vezmeme z jeho monom x
2= S nejv tho stupn . Pak urit existuje g 2 I takov, e LT g = a
x
. Zejm $f ] = $f ; g] a problematick monom v f ; g je oste niho stupn . Po konenm potu krok zsk
me reprezentanta $f ] tvoenho pouze monomy S . Zobrazen je tedy surjektivn.
St
n i n
soben skal
rem je zejm zachov
no. \4 =) 1" Sta uk
zat, e pro dan i existuje pouze konen mnoho monch i-tch souadnic bod z V . Uvame proto tdy $xji ] 2 C $x1  : : : xn]=I . Dimenze je konen
, a tedy, pro dostaten velk m, existuje nenulov
line
rn kombinace m X cj $xji ] = $0] j =0

co lze ps
t Odtud Pmj=0 cj xji mnoho koen.

2m 3 X 4 cj xji 5 = $0] j =0

2

I , co je nenulov polynom v xi a ten m
nejve konen




V obou v t
ch nez
leelo na volb monomi
lnho uspo
d
n. V praxi to znamen
, e pokud vpoet zhavaruje pro n jak, je mon jej provst s jinm uspo
d
nm a pravd podobnost sp chu se tak zvyuje.

40

5 APLIKACE

5.2 Polynomiln a racionln implicitizace

Pipomeme, e parametrick
reprezentace variety v kn je d
na systmem n racion
lnch funkc (viz. 1.8). Uvame mnoinu de&novanou parametricky systmem polynom F = (f1 : : : fn ), kde f1 : : : fn 2 k$t1 : : :  tm]. F je mono ch
pat jako zobrazen km ! kn takto x1 = f1(t1 : : : tm) ... xn = fn(t1 : : : tm) Clem implicitizace je nalzt varietu V(g1  : : : gs ) parametricky zadanou systmem F , tj. nejmen a&nn varietu V  kn obsahujc F (km). Podobn pro racion
ln parametrizace. Napklad krunice (obr
zek 7) V(x2 + y2 = 1) je implicitizac parametrickho vyj
den 2t ; t2 x = y = 11 + t2 1 + t2 Bodu (0 1) ovem parametrickm vyj
denm nikdy nedos
hneme, bez n j by ale F (R2) nebyla varieta. (0 1)

(0 0)

(x y) (t 0)

Obr. 7: Implicitizace krunice

5.3 V ta O polynomiln implicitizaci. Nech k je nekonen pole, F : km ! kn

polynomiln zobrazen F = (f1 : : : fn ) a I = hx1;f1 : : :  xn;fni  k$t1 : : : tm x1 : : : xn]. Pak V (Im) m-tho eliminanho idelu je nejmen a nn varieta v kn obsahujc F (km). Tedy sestrojme-li varietu V = V(x1 ; f1 : : :  xn ; fn), a vyeliminujeme z pslunch polynom hodnoty parametr t1 : : : tm, dostaneme pr
v implicitn popis hledan variety { uz
v ru F (km). Dkaz: Ozname pm : km+n ! kn projekci zapomnajc prvnch m komponent. Pmo z de&nice I je F (km) = pm V(I ) . Proto pro algebraicky uzaven pole k plyne tvrzen pmo z v ty o uz
v ru (4.16). Uvaujme tedy algebraicky uzaven rozen K  k, ozname I1 = hx1;f1 : : :  xn; fni  K $t1 : : : tm x1 : : :  xn]. Pmo z de&nice I a I1 je   F (km) = pm V(I )  V (Im)

5.2 Polynomiln a racionln implicitizace

41

Obr. 8: Enneperova plocha a Whitneyho detnk Uvame tedy n jakou jinou varietu Z = V(g1  : : : gs )  kn tak, e F (kmm)  Zk . Odsud gi  F = 0 na kadm (t1 : : : tm) 2 km. Stejn
vlastnost plat i v Km , a tedy i varieta ZK generovan
stejnmi polynomy g1 : : : gs v K n obsahuje F (K ). Lze tedy aplikovat v tu o uz
v ru a dost
v
me V (I1m)  ZK . Zp tnm zenm na k zsk
me 
dan V (Im)  Z .
Z pedchoz v ty u vyplv
podoba algoritmu pro implicitizaci. Spoteme redukovanou Grobnerovu b
zi ide
lu hx1 ; f1 : : : xn ; fni v lexikogra&ckm uspo
d
n, kde ti > xj pro kad i j . D
le snadno stanovme Im a to je pesn hledan ide
l. Respektive sta takov uspodn , kter zaru pevahu vech ti nad xj , aby se algoritmem pro vpo et Grobnerovy bze eliminovala ti , jinak m
e bt uspodn libovoln . Mme tak nadji doshnout efektivnj ho vpo tu, ne
s istm lexikograckm uspodn m.

Jako pklady meme uvst u dve zobrazen variety v R3 nazvan Enneperova plocha a Whitneyho detnk, viz. obr. 8. Jejich parametrick popis je x = 3u+3uv2 ;u3, y = 3v + 3u2v ; v3, z = 3u2 ; 3v2, resp. x = uv, y = v, z = u2. Aplikace eliminan procedury (nap. v systmu MAPLE za pouit gbasis s uspo
d
nm plex) d
odpovdajc implicitn popisy. V ppad Enneperovy plochy je to odpudiv polynom: ;59049z ; 104976z2 ; 6561y2 ; 72900z3 ; 18954y2z ; 23328z4 + 32805z2x2 + 14580z3x2 + 3645z 4x2 ; 1296y 4z ; 16767y 2z 2 ; 6156y 2z 3 ; 783y 2z 4 +39366zx2 +19683x2 ; 1296y 4 ; 2430z 5 + 432z 6 + 108z 7 + 486z 5x2 ; 432y 4z 2 + 54y 2z 5 + 27z 6x2 ; 48y 4z 3 + 15y 2z 6 ; 64y 6 ; z 9 Vsledn implicitn popis Whitneyho detn ku je jednodu : x2 ; y 2z Racion
ln implicitizac rozum me analogick postup pro racionln lomen funkce

xi = fgi((tt1

:: :: :
:
ttm )) i

m

1

P mo ae se nab zej c een dosadit do pedchoz vty idel hx1g1 ; f1
: : :
xngn ; fn i nefunguje. Nap klad uva
ujme

x = uv y = vu z = u 2

2

Dostvme I = hvx ; u2
uy ; v 2
z ; ui a po eliminaci I2 = hz (x2y ; z 3 )i. Sprvn vsledek je ale jenom V(x2y ; z 3 ), tedy postup pidal nav c celou rovinu.

42

5 APLIKACE

"een vypad tak,
e zavedeme varietu nulovch bod jmenovatel W = V(g1
: : :
gn) a zobrazen F chpeme jako (km ; W ) ! kn . Pro implicitizaci pou
ijeme idel

I = hg1x1 ; fj
: : :
gnxn ; fn
1 ; g1    gny i  k#y
t1
: : :
tm
x1
: : :
xn] Potom V (Im+1 ) je minimln ann varieta obsahuj c F (km ;W ). Dkaz u
se vede v podstat analogicky pedchoz vt. St
ejn m bodem je oven ,
e pokud se polynom nuluje na km ; W , nuluje se u
na cel m km . Viz. #2], str. 132.

5.3 Algebraick k ivky

5.4 Denice. Nech% f 2 k#x
y]. Varietu V(f ) nazveme algebraickou kivkou v k2 (v rovin). V nsleduj c sti pjde pedev m o posti
en pojmu te ny a singulrn ho bodu, tj. takov ho bodu na kivce, kde je pojem te ny t
ko denovateln. 5.5 Denice. Nech% m 2 N, (a
b) 2 V(f ) a L je p mka takov,
e (a
b) 2 L. "ekneme,
e L prot n V(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-nsobn koen polynomu f (a + ct
b + dt) 2 k#t]. Ozna me   @f @f rf (p
q) := @x (p
q)
@y (p
q)

5.6 Lemma. Nech
f 2 k#x
y] a (a
b) 2 V(f ). Pak plat 1. Je-li rf (a
b) 6= (0
0), pak existuje prv jedna p mka L prochzejc bodem (a
b), kter v nm protn V(f ) s nsobnost alespo 2. 2. Je-li rf (a
b) = (0
0), pak ka d p mka prochzejc (a
b) v nm protn V(f ) s nsobnost alespo 2.

Dkaz: Ozna me g (t) := f (a + ct
b + dt). Proto
e (a
b) 2 V(f ), je t = 0 koen g . Derivujme

podle promnn t

@f g (t) = @f @x (a + ct
b + dt)  c + @y (a + ct
b + dt)  d 0

V bod t = 0 potom

@f g (0) = @f @x (a
b)  c + @y (a
b)  d 0

Tedy pokud rf (a
b) = (0
0), je g (0) = 0, a tedy t = 0 je alespo& dvojnsobn { druh st tvrzen . Pokud rf (a
b) 6= (0
0), dostaneme z podm nky g (0) = 0 jednorozmrn prostor een pro dvojici (c
d). To spolu s po
adavkem (a
b) 2 L udv p mku jednozna n.
0

0

5.3 Algebraick kivky

43

1

1.5

1 0.5 0.5

00

0.5

1

1.5

2

00

0.5

1

1.5

2

2.5

3

2

3

4

5

-0.5 -0.5 -1

-1.5

-1

3 2

2

1 1

00

1

2

3

4

-1

00

1

-1 -1

-2

-2 -3

Obr. 9: Kivky V(f ) s f (x y) = (x2 + y2 ; 2x)2 ; a2(x2 + y2), a = 0 1 2 3

44

5 APLIKACE

5.7 Denice. Nech% f 2 k#x
y]. Body (a
b) 2 V(f ) s vlastnost rf (a
b) = (0
0) se nazvaj singul
rn body kivky V(k), ostatn regul
rn. P mka prot naj c V(f ) v regulrn m bod s nsobnost alespo& 2 se nazv tena. Singulrn body mohou velmi zaj mat in
enry. Pokud kivka popisuje pohyb njak sou sti, singulrn bod je v
dy podezel m sto { jedn se o bod zvratu, k
en apod. Jejich ur en m tedy bezprostedn praktick vznam. Mno
ina singulrn ch bod dan kivky je zejm prv varieta  @f @f  V f
@x
@y Existence singulrn ch bod je tedy na zklad pedchoz teorie probl m algoritmicky eiteln (nad C ), mnohdy se poda je p mo nal zt. Nap klad pro kivky z obr. 9 dostaneme (teba aplikac procedury gsolve v MAPLE),
e pro ka
dou hodnotu parametru a existuje v
dy prv jeden singulrn bod (0
0). Pro a > 1 je to izolovan bod, pro a = 1 je to bod vratu, pro men dochz k samoprotnut kivky.

5.4 Oblky syst mu k ivek

Polynom F 2 k#x
y
t] budeme chpat jako promnnou t parametrizovan syst m kivek V(Ft) v k#x
y] danch rovnicemi F (x
y
t) = 0. Nap klad (x ; t)2 + (y ; 2t2)2 ; 1 = 0 denuje syst m kru
nic o polomru 1, jejich
sted se pohybuje po parabole y = 2x2 , viz. obr. 10. 5.8 Denice. " kme,
e dv kivky maj dotyk 
du m, jestli
e je lze lokln parametrizovat11 hladkm zobrazen m tak, aby parametrizace v bod dotyku mly stejn derivace a
do du m v etn. Maximln kivka, kterou lze lokln parametrizovat tak, aby ka
d bod v t to parametrizaci byl prvkem prv jedn z kivek dan ho syst mu a ml s n v nm dotyk alespo& du 1, se nazv ob
lka dan ho syst mu. 5.9 V ta. Oblka syst mu k ivek F 2 k#x
y
t] je obsa ena ve variet   V F
@F @t Dkaz: Nech% je oblka parametrizovna x = f (t), y = g (t). Pro ka
d t 2 k po
adujeme p slunost ke kivce, tj. ;f (t)
g(t) 2 V(F ) t Nav c, aby kivka byla oblka, mus bt rFt v bod (f (t)
g (t)) kolm na (f (t)
g (t)). Kdo nev , a% si zopakuje analzu. Kolmost znamen nulovou hodnotu skalrn ho sou inu, tj. @F ;f (t)
g (t)
t  f (t) + @F ;f (t)
g(t)
t  g (t) = 0 (3) @x @y 0

0

0

0

K
ivku nemus nutn jt parametrizovat, ale pro njak dostaten mal okol dan ho bodu se to poda
. 11

5.4 Oblky systmu kivek

45

Obr. 10: Systm kivek (x ; t)2 + (y ; 2t2)2 ; 1 = 0 a jejich ob
lka Pouhm derivovn m slo
en funkce t 7! F (f (t)
g (t)
t) a nslednm dosazen m za t dostaneme @  F (f (t)
g (t)
t) = @F ;f (s)
g (s)
s  f (s) + @F ;f (s)
g (s)
s  g (s) + @F ;f (s)
g (s)
s @t t=s @x @y @t Funkce F je na vech bodech tvaru (f (s)
g (s)
s) nulov (vlastnost oblky), a tedy mus bt nulov i jej derivace podle t. O prvn ch dvou lenech prav strany v me,
e jsou dohromady nulov , pokud uva
ovan kivka je oblka. Dohromady tedy dostvme @F ;f (s)
g (s)
s = 0 @t 0

0




Pro vechny singulrn body kivek syst mu je rovnost 3 splnna triviln, a tedy i singulrn body budou zahrnuty do vsledn variety. Oblku syst mu kru
nic se stedy na parabole vid me na obr. 10. K jej mu zadn jako ann variety lze dospt v MAPLE nap. posloupnost p kaz h := proc(x
y
t) (x ; t)2 + (y ; 2  t2 )2 ; 1 end( gbasis(#h(x
y
t)
diff(h(x
y
t)
t)]
#t
x
y ]
plex), pi em
polynom denuj c hledanou oblku je genertor prvn ho elimina n ho idelu (posledn z vsledn ho seznamu). Vyjde 256x6 + 256x4y 2 ; 320x4y ; 764x4 ; 256x2y 3 ; 384x2y 2 + 60x2y + 688x2 + 64y 4 ; 272y 3 + 225y 2 + 272y ; 289.

5.10 Teny v singulrnch bodech. Pr
v studium chov
n kivky v okol singu-

l
rnch bod n
m pod
dobrou informaci o cel kivce. Vechny pmky proch
zejc takovm bodem sice maj dotyk vyho 
du, jist je ale vechny nechceme povaovat

46

5 APLIKACE

-1

-0.5

1

2

y0.5

y 1

00

0.5 x

1

0

0.2

0.4

0.6

1

0.8

1.2

1.4

1.6

x

-0.5

-1

-1

-2

Obr. 11: Ten kuel kivek V(x3 + x2 ; y2) a V(X 3 ; y2) v singul
rnm bod za teny. Podle Taylorovy v ty (snad dobe zn
m z matematick analzy) m
polynom f rozvoj v singul
rnm bod (a b) @f (a b)(x ; a) + @f (y ; b) + + f (x y) = f| (a b ) {z } @x {z @y } =0 protoe (ab2K ) | +

=0 protoe je (ab) singulrn @ 2f (a b)(x ; a)2 + @ 2f (a b)(x ; a)(y ; b) + @ 2f (a b)(y ; a)2 + : : : @x2 @x@y @y2

Pedpokl
dejme, e fr (x ; a y ; b) = Pri=1 @xi@@yr fr;i (a b)(x ; a)i(y ; a)r;i je prvn nenulov
homogenn 
st. Pak mnoina vech een (u : v) rovnice fr (u v) = 0 d
v
sm rov vektory te en v singul rnm bod (a b). Mnoinu vech t chto teen nazv
me te n kuel k ivky K v singul
rnm bod (a b). 5.11 Pklad. Pro kubickou kivku K = V (x3 + x2 ; y2) snadno spoteme, e jej jedin singul
rn bod je (0 0), prvn nenulov
homogenn 
st polynomu je x2 ; y2, ten kuel je tedy tvoen dv ma pmkami x  y = 0, viz. obr
zek 11. 5.12 Deformace singularit. Jednoduch postup jak zjistit chov
n kivky v okol regul
rnho bodu je spost jej tenu v tomto bod . Pro singul
rn body je to sice s tenami sloit j, asto vak sta libovoln m
lo pozm nit vhodn parametr (tj. koe&cient) de&nujcho polynomu a singularita vymiz. Z chov
n teen pro blzk hodnoty parametru meme usuzovat na typ pvodn singularity. Ji jsme se potkali se singularitou v po
tku u kivek V (x3 ; y2) (n
sobn
tena { osa x) a V (x3 + x2 ; y2). Uvame polynomy f" = x3 ; y2 ; " g = x3 + x2 ; y2 h" = x3 + x2 ; y2 ; ": Polynomy f0 a g0 d
vaj prvn z naich kivek, g1 d
druhou. Podvejme se nejprve na chov
n kivek V (g ). Snadno spoteme, e vdy maj pouze jeden singul
rn bod (0 0), jeho typ je ovem zcela odlin pro < 0 a > 0.

5.4 Oblky systmu kivek

47

1

1

y0.5

-1

-0.5

00

0.5y

0.5

1

1.5

-1

-0.8

-0.6

-0.4

-0.2

00

0.2

x

-0.5

0.4 x

0.6

0.8

-0.5

-1

-1

Obr. 12: Deformace singularit kivek p

Je-li kladn, pak n
m vyjdou dv re
ln teny ve sm rech (1 :  ), zatmco pro < 0 vyjdou ob teny imagin
rn, je proto po
tek izolovanm bodem kivky, viz. lev obr
zek na 12. Pi deformacch f" je situace jet daleko jednodu. Pro nenulov " toti budou vechny body kivky regul
rn, viz. prav obr
zek na 12. V obou ppadech zsk
v
me jasnou pedstavu o typu singularity Neilovy paraboly V (x3 ; y 2). Diskus souasnch deformac h" dosp jeme ke kivce hodnot parametr 3 ), pro kter kivky obsahuj n jak singul
rn bod, pro vechny hodnoty V (") V (" ; 427 vn tto kivky jsou vechny body regul
rn. Tvar kivky se pitom podstatn m n pouze pi pechodech mezi uvedenmi tymi oblastmi. Hodnoty odpovdajc Neilov parabole jsou pr
v jedinm bodem spolenm vem tyem oblastem.

48

6 ALGEBRAICK# DKAZY GEOMETRICKCH TVRZEN

6 Algebraick dkazy geometrickch tvrzen N kter
geometrick
tvrzen lze pom rn jednodue pevst na algebraick
a pout algebraick metody k jejich dkazu. Takovch postup je k dispozici n kolik, my se soustedme pouze na jednu metodu, kter
vuv
k dkazm ji vybudovanho apar
tu.

6.1 Metoda Gr obnerovch baz

Zan me pkladem. Budeme cvin uvaovat tvrzen, e uhlopky rovnob nka se navz
jem pl. Uvaujme rovnob nk se souadnicemi vrchol podle obr
zku 13. Prom nn u1 u2 u3 jsou voln, zad
vaj rovnob nk, x1 : : :  x4 jsou na nich z
visl. Sformulujme nejprve pedpoklad, e se jedn
o rovnob nk. Pmka CD mus bt rovnob n
s AB, tedy h1 := x2 ; u3 = 0. Podobn se mus rovnat sm rnice AC a BD u 3 = x2 u x ; u tedy h2 := u3(x1 ; u1) ; u2x2 = 0 2

1

1

Varieta V(h1 h2) d
v
podmnky na rovnob nk. Poadujeme kolinearitu bod A N D, tedy dost
v
me h3 := x1x4 ; x2x3 = 0. Analogicky z kolinearity B N C zsk
me polynom h4 := x4(u2 ; u1) ; (x3 ; u1)u3. Tm jsme popsali, e N je prsek uhlopek. Samozejm , e jsme mohli zvolit i jin (dokonce jednodu) systm polynom popisujc stejn geometrick objekt. Ten n
 je v jistm smyslu co nejprimitivn j, vyuvajc jen popis rovnosti sm r a rovnosti vzd
lenost bod. Chceme uk
zat, e se uhlopky pl, tedy x23 + x24 = (x3 ; x1)2 +(x4 ; x2)2. Podobn pro druhou uhlopku (x3 ; u1)2 + x24 = (x3 ; u2)2 + (x4 ; u3)2. Dostaneme tak polynomy g1 g2 jejich vynulov
n m
me odvodit za pedpokladu vynulov
n pedpoklad h1 h2 h3 h4.

C (u2 u3)

D(x1 x2) N (x3 x4)

A(0 0)

B (u1 0)

Obr. 13: Oznaen bod v rovnob nku Zd
se tedy, e ve co potebujeme je pesn zachyceno v n
sledujc de&nici. 6.1 Denice. ekneme, e g 2 R$u1 : : :  um x1 : : : xn ] siln vyplv z h1 : : : hr , jestlie g 2 I(V(h1 : q : : hr )). 6.2 V ta. Je-li g 2 hh1  : : : hr i, pak g siln vyplv z h1 : : : hr . Dkaz: Z de&nice radik
lovho ide
lu plyne g s 2 hh1  : : : hr i pro vhodn s. Tedy gs se nuluje na vech bodech dan variety, a tedy nutn i g 2 I(V(h1 : : :  hr )).




6.1 Metoda Grobnerovch baz

49

Obr
cen v ty v ppad algebraicky uzavenho pole plyne z Hilbertovy v ty o nul
ch. Pslunost polynomu g k radik
lovmu ide
lu se ur snadno vpotem redukovan Grobnerovy b
ze (dokonce pro libovoln nekonen pole k): 6.3 q V ta. Nech k je libovoln nekonen pole a g h1 : : : hr 2 k$x1 : : : xn]. Pak g 2 hh1  : : :  hr i prv kdy je f1g redukovan Grobnerova bze idelu I = hh1  : : :  hr  1 ; ygi  k$x1 : : :  kn y]. Dkaz: Pedpokl
dejme nejprve, e konstantn polynom 1 pat do I . Pak stejn jako v z
v ru dkazu Hilbertovy v ty o nul
ch dost
v
me 1 jako line
rn kombinaci polynom hi a 1 ; yg a v k(x1 : : :  xn)$y] meme za y dosadit 1=g a ov me tak pslunost gm do hh1  : : : hr i. K tomuto kroku jsme ale nepotebovali algebraickou uzavenost k. Naopak, je-li gm 2 hh1 : : : hr i, pak 1 = ymgm + (1 ; ymgm) = ymgm + (1 ; yg)(1 + yg +    + (yg)m;1) 2 I:




Spot
me-li Grobnerovu b
zi ide
lu hh1 : : :  h4 1 ; yg1i z pedchozho ppadu, nezsk
me f1g, tedy g1 z pedpoklad h1 : : :  h4 nevyplv
siln . Je-to dky ppadm, kdy u1 = 0 nebo u3 = 0 a rovnob nk degeneruje na seku. Potom prsekem uhlopek je dokonce nekonen mnoho bod a ty vechny nespluj podmnku plen. Zkuste si spost Grobnerovu b
zi polynom h1 h2 h3 h4 (v lex. uspo
d
n). Z n bude jasn vid t, e v naem pklad zsk
me ve skutenosti tyi komponenty diskutovan variety V  R7. Meme je zapsat napklad jako V 0 = V(x1 ; u1 ; u2 x2 ; u3 x3 ; u1 +2 u2  x4 ; u23 ) U1 = V(x2 x4 u3) U2 = V(x1 x2 u1 ; u2 u3) U3 = V(x1 ; u2 u2 ; u3 x3u3 ; x4u2 u1) Obecn jsou problmy tohoto r
zu zpsobeny pr
v neireducibilnmi varietami. Jedin
mon
cesta z t chto komplikac je revize pojmu dsledku. Budeme poadovat, aby dokazovan tvrzen platilo pouze na t ch komponent
ch, kde jsou n
mi zvolen voln parametry ui skuten nez
visl: 6.4 Denice. Nech W  Rm+n je ireducibiln varieta, souadnice zname u1 : : :  um x1 : : : xn. ekneme, e souadn funkce u1 : : : um jsou algebraicky nez visl na W , jestlie neexistuje polynom v R$u1 : : : un] patc do I(W ). 6.5 Denice. ekneme, e hypotza g vyplv
genericky z pedpoklad h1 : : : hr , jestlie g 2 I(V 0)  R$u1 : : :  um x1 : : : xn] kde V 0  Rm+n je sjednocen t ch ireducibilnch komponent variety V = V(h1  : : : hr ), na kterch jsou u1 : : : um algebraicky nez
visl. Rozklad variety na ireducibiln komponenty lze provst algoritmicky. Jde vak o komplikovanou proceduru, je naimplementovan
napklad v systmu Axiom. Nen vak nezbytn nutn, jak uk
eme v n
sledujcm.

50

6 ALGEBRAICK# DKAZY GEOMETRICKCH TVRZEN

6.6 V ta. Hypotza g vyplv genericky z h1 : : :  hr , jestli e existuje nenulov polynom c 2 R$u1 : : : um] tak, e

q c  g 2 hh1 : : :  hr i: Je-li pole k algebraicky uzaven, pak plat i obrzen implikace Dkaz: Nech Vj je n jak
z komponent V 0 dle de&nice 6.5. Protoe cg se nuluje na V , mus se nulovat i na Vj , tedy cg 2 I(Vj ). To je prvoide
l podle v ty 4.22, ale c 2= I(Vj ) (poadov
no v de&nici 6.5), a tedy g 2 I(Vj ). Pedpokl
dejme nyn, e g vyplv
genericky z h1 : : : hr a k je algebraicky uzaven. Nech V1 : : :  Vk jsou vechny ireducibiln komponenty na kterch jsou u1 : : : um algebraicky z
visl, tj_existuj polynomy c1 : : : ck 2 k$u1 : : : um], ci 2 I(Vj ). Nyn sta zvolit c = c1c2 : : : ck a z de&nice plyne, e cg 2 I(V ). Protoe je k algebraicky uzaven, plyne odtud pslunost do radik
lnovho ide
lu.
Pro praktick pouit pedchoz v ty je vhodn formulovat ekvivalentn kritria. Jako obvykle, budeme uvaovat R$u1 : : :  um  x1 : : : xn ]  R(u1 : : : um )$x1 : : : xn ]:

6.7 V ta. Nsledujc tvrzen jsou ekvivalentn

q 1. Existuje c 2 R$u1 : : :  um] nenulov tak, e cg 2 hh1 : : :  hr i. p 2. g 2 H , kde H = hh1 : : : hr i  R(u1 : : : um)$x1 : : : xn]. 3. f1g je redukovan Grobnerova bze hh1  : : : hr  1 ; ygi op t v okruhu polynom R(u1 : : : um )$x1 : : :  xn ]. Dkaz: Uk
eme nejprve (1) , (2). Pedpokl
dejme, e plat (1), tj. (cg )s = Pnj=1 aj hj pro vhodn polynomy aj 2 R$u1 : : : um x1 : : :  xn] a s  1. Odtud n X gs = acsj hj j =1

co zna pr
v gs 2 hh1 : : :  hr i  R(u1 : : : um)$x1 : : :  xn], neboli g pat do pslunho radik
lu. q Naopak, pat-li g do hh1 : : : hr i  R(u1 : : : um)$x1 : : : xn], pak gs = Pnj=1 bj hj . Vyn
sobenm mocninou spolenho n
sobkuPvech jmenovatel racion
lnch funkc lomench bj dostaneme vraz tvaru (cg)s = j=n b0j hj , kde koe&cienty b0j jsou ji polynomy. Ekvivalenci druhho a tetho tvrzen jsme ji uk
zali, viz. 6.3
Tedy op t vystame s pot
mm Grobnerovch b
z, rozklad na ireducibiln komponenty nen pro tyto ely teba.

6.2 P klady

Z
v rem uk
eme aplikaci pedchozch vah pi dkazu jedn z Apolloniovch v t. Vrame se ale nejprve k vodnmu pkladu.

6.2 Pklady

51

Ji jsme zmnili rozklad V(h1 : : :  h4) na variety

V 0 = V(x1 ; u1 ; u2 x2 ; u3 x3 ; (u1 + u2)=2 x4 ; u3=2) U1 = V(x2 x4 u3) U2 = V(x1 x2 u1 ; u2 u3) U3 = V(x1 ; u2 u2 ; u3 x3u3 ; x4u2 u1) Jedin na komponent V 0 jsou u1 u2 u3 algebraicky nez
visl, zbvajc komponenty popisuj degenerovan ppady. V1 a V2 znamenaj, e bod C le na pmce AB, V3 znamen
splynut bod A a B . Ov me si vsledek nalezenm pslun Grobnerovy b
ze. V systmu 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 0 opravdu g1 i g2 skuten siln vyplv
z pedpoklad. Pro pvodn polynomy hi ovem dostaneme n co jinho: > 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])

$;x1 x4 + x4 u2 x4 u1 ;1 + y x12 ; 2 y x1 x3 ; 2 y x4 x2 + y x22 ;x2 + u3 ;x1 x4 + x2 x3 x2 u1 x2 u2 ; x2 x1] Pokud ovem pouijeme pvodn polynomy, ale test pro generick implikov
n, dost
v
me op t potebnou 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 slben
Apolloniova loha. Chceme dok
zat, e pro pravohl trojhelnk jsou stedy vech t stran a pata vky nad peponou na jedin krunici. K formulaci zad
n budeme potebovat osm polynom h1 : : : h8, obsahujc dva voln parametry (dlky

52

6 ALGEBRAICK# DKAZY GEOMETRICKCH TVRZEN

odv sen) a osm volnch prom nnch x1 : : :  x8 (posledn dv jsou souadnice stedu krunice proch
zejc stedy stran trojhelnka). Dokazovan tvrzen je pak vyj
deno jedinm 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! Potebn test ov ujc, e g genericky vyplv
z h1 : : : h8 je positivn: > gbasis(h,1-y*g],x,y])

Siln ovem tvrzen nevyplv
:

$1]

> gbasis(h,1-y*g],u,x,y])

$ x1 x3 x4 x2 u2 ;1 + y x52 ; 2 y x5 x7 + y x62 ; 2 y x6 x8 u1 ] Vimn me si jet , e asto vystame i s jednodum testem. Me se toti st
t, e g pat pmo do ide
lu generovanho hi (v okruhu polynom v nez
vislch prom nnch nad podlovm t lesem R(u1 u2)). Sta pak provst d len se zbytkem podle Grobnerovy baze: > F:= gbasis(h], x],plex)

F := $2 x1 ; u1 2 x2 ; u2 2 x3 ; u1 2 x4 ; u2 ;u22 u1 + ( u22 + u12 ) x5 ;u12 u2 + ( u22 + u12 ) x6 ;u1 + 4 x7 ;u2 + 4 x8] > normalf(g, F, x],plex)

0 Z
jemcm doporuuji zkusit si dal jednoduch (i sloit j) lohy samostatn .

LITERATURA

53

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.