Obsah Kapitola 1. Rozcvička 4 1. Čísla a funkce 4 2. Kombinatorické veličiny 9 3. Diferenční rovnice 13 4. Pravděpodobnost 17 5. Geometrie v rovině 26 6. Relace a zobrazení 40 Kapitola 2. Elementární lineární algebra 46 1. Vektory a matice 46 2. Determinanty 58 3. Vektorové prostory a lineární zobrazení 67 4. Vlastnosti lineárních zobrazení 86 Kapitola 3. Linární modely a maticový počet 95 1. Lineární procesy 95 2. Diferenční rovnice 102 3. Iterované lineární procesy 110 4. Více maticového počtu 119 5. Rozklady matic a pseudoinverze 139 Kapitola 4. Analytická geometrie 148 1. Afinní a euklideovská geometrie 148 2. Geometrie kvadratických forem 170 3. Projektivní geometrie 177 Kapitola 5. Zřízení ZOO 187 1. Interpolace polynomy 187 2. Reálná čísla a limitní procesy 197 3. Derivace 218 4. Mocninné řady 231 Kapitola 6. Diferenciální a integrální počet 246 1. Derivování 246 2. Integrování 263 3. Nekonečné řady 283 Kapitola 7. Spojité modely 298 1. Fourierovy řady 298 2. Metrické prostory 312 3. Integrální operátory 329 4. Diskrétní transformace 337 Kapitola 8. Spojité modely s více proměnnými 338 1. Funkce a zobrazení na Rn 338 2. Integrování podruhé 371 3. Diferenciální rovnice 395 i 4. Numerické metody 420 5. Komplexní analýza 421 6. Variační počet 421 Kapitola 9. Statistické a pravděpodobnostní metody 422 1. Popisná statistika 422 2. Pravděpodobnost 431 3. Matematická statistika 459 4. Bayesovská a neparametrická statistika 460 Kapitola 10. Elementární teorie čísel 461 Kapitola 11. Algebraické struktury 462 1. Grupy 462 2. Okruhy polynomů 479 3. Systémy polynomiálních rovnic 492 4. Uspořádané množiny a Booleovská algebra 512 5. Kódování 525 Kapitola 12. Kombinatorické metody 533 1. Grafy a algoritmy 533 2. Aplikace kombinatorických postupů 556 ii KAPITOLA 11 Algebraické struktury čím větší abstrakce, tím větší zmatek? – ne, často to bývá naopak ... V této kapitole se budeme věnovat zdánlivě velice formálnímu studiu pojmů, které ale ve skutečnosti odráží spoustu skutečných vlastností věcí kolem nás. Abstrahujeme z nich přitom jen ty nejjednodušší operace a „algebru“ tak lze vnímat jako algoritmické manipulace s písmeny, které zpravidla mají nějaké souvislosti s výpočty nebo popisem procesů. Zároveň si budeme trochu všímat, kde všude jsme takové objekty potkávali v předchozích kapitolách (aniž by ale bylo nutné mít tyto kapitoly předem pročtené). Přímo navážeme víceméně jen na první a šestou část první kapitoly, kde jsme podobně abstraktně pohlíželi na čísla, se kterými počítáme, a obecněji na vztahy mezi objekty, když jsme je abstrahovali do tzv. relací. V první části této kapitoly se zastavíme u té nejjednodušší situace – budeme se zamýšlet nad případem, kdy máme jen jednu jedinou operaci, která se chová podobně jako násobení čísel. Pak si přídáme druhou operaci, podobně jako jsou u čísel k dispozici společně sčítání a násobení. To nám umožní vysvětlit elementární základy tzv. počítačové algebry, tj. algoritmických postupů, díky kterým počítače umí manipulovat s formálními výrazy a počítat s nimi, včetně řešení systémů polynomiálních rovnic. V další části se vrátíme k jiné abstrakci situací s jedinou operací a budeme přitom vycházet z uspořádní čísel podle velikosti nebo množinové inkluze. V poslední části kapitoly se pak zastavíme u několika poznámek ohledně využití algebraických nástrojů pro návrhy (samoopravných) kódů využívahých hojně při přenosech dat. 1. Grupy Naše první úvahy se budou týkat objektů a situací, ve kterých je možné rovnice tvaru a · x = b vždy jednoznačně řešit (tak jako u lineárních rovnic jsou objekty a a b dány, zatímco x hledáme). Půjde o tzv. teorii grup. Všimněme si, že zatím nic nevíme o povaze objektů, ani co znamená ta tečka. Jen předpokládáme, že dvěma objektům a a x umíme přiřadit objekt a · x. Nejprve si oprášíme a rozšíříme náš slovník pojmů ohledně operací, jak jsme jej zavedli již v kapitole první a projdeme přitom příklady čísel a transformací roviny a prostoru, ve kterých se s takovými „grupovými“ objekty potkáváme. Teprve pak se budeme chvíli věnovat základům obecné teorie. 462 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY 10.1 11.1. Příklady a pojmy. Pro libovolnou množinu A jsme již dříve definovali binární operace na A jako libovolné zobrazení A × A → A. Výsledek takové operace budeme často značit (a, b) → a · b. Množina s binární operací se nazývá grupoid. Abychom mohli něco podstatného říci, potřebujeme nějaké další vlastnosti operací. Binární operace je asociativní, jestliže pro všechny prvky v A platí a · (b · c) = (a · b) · c. Binární operace a pologrupy Grupoid s asociativní binární operací, se nazývá pologrupa. Binární operace je komutativní, jestliže pro všechny prvky v A platí a · b = b · a. Přirozená čísla N = {0, 1, 2, . . . }, spolu s kteroukoliv z operací sčítání a násobení jsou asociativní a komutativní pologrupa. Celá čísla Z = {. . . , −2, −1, 0, 1, 2, . . . } jsou grupoid vůči kterékoliv z operací sčítání, odčítání, násobení. Operace odčítání ale není asociativní. Např. (5 − 3) − 2 = 0 = 5 − (3 − 2) = 4, ani komutativní, protože a − b = −(b − a). Jednotky, inverze a grupy Levá jednotka v grupoidu (A, ·) je takový prvek e ∈ A, že pro všechny prvky v A platí e · a = a; obdobně pro pravou jednotku musí platit pro všechny prvky a · e = a. Jednotka binární operace je prvek e, který je pravou i levou jednotkou zároveň. Prvek a−1 je levou inverzí k prvku a v pologrupě (A, ·) s jednotkou e, jestliže platí a−1 · a = e; obdobně je pravou inverzí a−1 takový prvek, pro který je a · a−1 = e. Prvek a−1 je inverzní k a v pologrupě s jednotkou, jestliže je levou i pravou inverzí zároveň. Monoid (M, ·) je pologrupa s jednotkou. Grupa (G, ·) je pologrupa s jednotkou, ve které má každý prvek inverzi. Komutativní grupa, resp. komutativní pologrupa, je taková, kde je operace · komutativní. Komutativní grupy se také často nazývají abelovské.1 Podívejme se na přímé jednoduché důsledky definic. V monoidu nemohou být pravé a levé inverze různé. Je-li totiž a · x = x · b = e, pak také a = a · (x · b) = (a · x) · b = b. Podstatná je zde pouze asociativita operace. Všimněme si, že pro odečítání na celých číslech (tady operace není asociativní) je nula pravou jednotkou, tj. a − 0 = a pro všechna 1Je to na počest mladého matematika Abela ... V angličtině se používá přídavné jméno „abelian“ a bývá to uváděno jako příklad absolutní pocty, protože se píše s malým písmenem, tzn. je to tak obecně používáno, že se již zapomnělo, že jde o jméno člověka. 463 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY celá čísla a, není však levou jednotkou. Dokonce v tomto případě levý neutrální prvek neexistuje. Celá čísla jsou zjevně pologrupou vúči sčítání i násobní. Grupou jsou přitom jen vůči sčítání, protože pro násobení neexistují inverzní prvky, kromě čísel ±1. Je-li (A, ·) grupa, pak její podmnožinu B ⊂ A, která je uzavřená vůči zúžení operace · a zároveň je spolu s touto operací grupou, nazýváme podgrupa. Racionální čísla Q jsou komutativní grupou vzhledem ke sčítání a nenulová racionální čísla jsou také komutativní grupou vůči násobení. Celá čísla spolu se sčítáním jsou jejich podgrupou. Pro každé kladné přirozené číslo k je množina všech k-tých odmocnin z jedničky, tj. množina {z ∈ C; zk = 1} konečnou grupou vůči násobení komplexních čísel. Např. pro k = 2 dostaneme grupu {−1, 1} se dvěma prvky, které jsou oba samy sobě inverzí, zatímco pro k = 4 dostáváme grupu G = {1, i, −1, −i}. Množina Matn, n > 1, všech čtvercových matic je (nekomutativní) pologrupa vzhledem k násobení matic a komutativní grupa vzhledem ke sčítání matic (viz odstavce 2.2–2.5). Množina všech lineárních zobrazení Hom(V, V ) na vektorovém prostoru je pologrupa vzhledem ke skládání zobrazení a komutativní grupa vzhledem ke sčítání zobrazení (viz odstavec 2.34). V obou předchozích příkladech, podmnožina invertibilních objektů uvažované pologrupy tvoří grupu. V prvním případě jde o tzv. grupu invertibilních matic, ve druhém o grupu lineárních transformací vektorového prostoru. V dřívějších kapitolách jsme již potkali mnoho (polo)grupových struktur, občas asi i docela nečekaně. Vzpomeňme např. různé podgrupy grupy matic nebo grupovou strukturu na eliptických křivkách. 10.3 11.2. Grupy permutací. Velmi často grupy a pologrupy potkáváme jako množiny zobrazení na pevně dané množině M, které jsou uzavřeny vůči skládání zobrazení. Ne vždy si ale tuto skutečnost přímo uvědomujeme, protože vidíme jen některá zobrazení a na všechna ostatní vznikající složeními nemyslíme. Nejsnáze je tato souvislost vidět na konečných množinách M, kde nám každá podmnožina invertibilních zobrazení vygeneruje pomocí skládání jistou grupu. Na každé takové množině o m = |M| ∈ N prvcích (prázdná množina má 0 prvků) totiž máme k dispozici mm možných definic zobrazení (každý z m prvků můžeme zobrazit na kterýkoliv v M) a všechna taková zobrazení umíme skládat. Protože skládání zobrazení je samozřejmě asociativní operace, dostáváme grupoid. Pokud chceme, aby existovala k zobrazení α : M → M jeho inverze α−1 , musí být α bijekcí. Složením dvou bijekcí vznikne opět bijekce a proto podmnožina m všech bijekcí na 464 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY množině M o m prvcích je grupa. Říkáme jí grupa permutací (na m prvcích). Je příkladem konečné grupy.2 Sám název grupy m přitom uvádí jinou souvislost, kdy místo bijekcí na konečné množině vnímáme permutace jako přerovnání rozlišitelných prvků. Potkávali jsme se s permutacemi v tomto smyslu např. při studiu determinantů, viz odstavec 2.14 na straně 58. Promysleme si podrobněji, jak vlastně násobení v takové grupě vypadá. U (malé) konečné grupy si můžeme snadno sestavit úplnou tabulku všech operací. Jestliže v grupě permutací 3 na číslech {1, 2, 3} označíme jednotlivá pořadí a = (1, 2, 3), b = (2, 3, 1), c = (3, 1, 2), d = (1, 3, 2), e = (3, 2, 1), f = (2, 1, 3), pak skládání našich permutací je zadáno tabulkou · a b c d e f a a b c d e f b b c a f d e c c a b e f d d d e f a b c e e f d c a b f f d e b c a Všimněme si podstatného rozdílu mezi permutacemi a, b a c a dalšími třemi. Ty první tři tvoří tzv. cyklus generovaný prvkem b nebo prvkem c: b2 = c, b3 = a, c2 = b, c3 = a. Samy o sobě jsou tyto tři prvky komutativní podgrupou. V této podgrupě je a jednotka a prvky b s c jsou vzájemně inverzní. Je tedy tato podgrupa stejná jako je grupa Z3 zbytkových tříd celých čísel modulo 3, resp. jako grupa třetích odmocnin z jedničky. Další tři prvky jsou samy sobě inverzí a každý z nich je tedy společně s jednotkou a podgrupou stejnou jako je Z2. Říkáme, že b a c jsou prvky řádu 3, zatímco prvky d, e a f jsou řádu 2. Tabulka ale není symetrická podle diagonály, naše operace · tedy není komutativní. Obdobně se chovají všechny grupy permutací m konečných množin o m prvcích. Každá permutace σ rozkládá množinu M na disjunktní sjednocení maximálních invariantních podmnožin, které dostaneme tak, že postupně vybíráme dosud nezpracované prvky x ∈ M a do třídy rozkladu Mx přidáváme všechny akce iterací σk (x), k = 1, 2, . . . , dokud není σk (x) = x. Každou permutaci tak dostáváme jako složení jednodušších permutací, tzv. cyklů, které se chovají jako identická permutace vně Mx a tak jako σ na Mx. Pokud přitom očíslujeme prvky v Mx jako pořadí (1, 2, . . . , |Mx|) tak aby i odpovídalo σi (x), pak je naše permutace prostým posunutím o jednu pozici v cyklu (tj. poslední prvek je 2A lze dokázat, že každá konečná grupa je podgrupou ve vhodné konečné grupě permutací. To si můžeme interpretovat tak, že grupy m jsou tak nekomutativní a složité, jak to jen jde. 465 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY zobrazen zpátky na první). Odtud název cyklus. Zjevně přitom tyto cykly komutují, takže je jedno, v jakém pořadí z nich permutaci σ složíme. Nejjednodušší cykly jsou jednoprvkové pevné body permutace σ a dvouprvkové (x, σ(x)), kde σ(σ(x)) = x. Těm se říká transpozice. Protože každý cyklus zjevně můžeme poskládat z permutací sousedních prvků (necháme „probublat“ první prvek nakonec), lze každou permutaci napsat jako složení transpozic sousedních prvků. Vraťme se k případu 3. Tam máme jednak možnost cyklu, který zahrne všechny tři prvky a v něm dostaneme permutace a, b, c. Kromě toho ještě můžeme mít jeden cyklus o délce 2 a zbývající prvek bude pevným bodem – tak dostaneme zbývající 3 permutace. Více možností není. Z postupu je zřejmé, že u větších počtů prvků bude možností velmi mnoho. Jednotlivé permutce můžeme obecně vyjádřit pomocí transpozic mnoha způsoby. Přitom ale skutečnost, jestli potřebujeme sudý nebo lichý počet transpozic, je na volbách nezávislá (můžeme tuto skutečnost vyjádřit pomocí počtu tzv. inverzí a poslední tvrzení pak plyne z toho, že každá transpozice mění počet inverzí o lichý počet, viz úvahy v odstavci 2.15 na straně 60). Máme tedy definováno dobře zobrazení sgn : m → Z2 = {±1}, tzv. paritu. Dokázali jsme si znovu tvrzení, která jsme již využívali při studiu determinantů (viz 2.14 a dále): Věta. Každá permutace konečné množiny je složením cyklů. Cyklus délky lze vyjádřit jako složení −1 transpozic. Parita cyklu délky je (−1) −1 . Parita složení permutací σ ◦ τ je součinem parit σ a τ. Poslední tvrzení věty říká, že zobrazení sgn převádí složení permutací σ ◦ τ na součin sgn σ · sgn τ v komutativní grupě Z2. Homomorfismy (polo)grup Obecně říkáme, že zobrazení f : G1 → G2 je homomorfismus (polo)grup, jestliže respektuje grupové operace, tzn. f (a · b) = f (a) · f (b). Zejména tedy vidíme, že je naše právě zavedená signatura permutací homomorfismem sgn : m → Z2. 10.4 11.3. Symetrie rovinných útvarů. V páté části první kapitoly jsme podrobně a elementárně rozebrali souvislosti invertibilních matic se dvěma řádky a dvěma sloupci a lineárními transformacemi v rovině. Viděli jsme přitom, že matice v Mat2(R) zadávají lineární zobrazení R2 → R2 , které zachovávají standardní vzdálenosti právě, když jsou jejich sloupce ortonormální bazí R2 (což je jednoduchá podmínka na souřadnice matice, viz odstavec 1.29 na straně 32). 466 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Ve skutečnosti je snadné dokázat, že každé zobrazení roviny do sebe, které zachovává velikosti, je afinní euklidovské, tj. je složením lineárního a vhodné translace.3 Jak jsme již připomněli, lineární část takového zobrazení přitom musí navíc být ortogonální. Všechna taková zobrazení tedy tvoří grupu všech ortogonálních transformací (nebo také euklidovských transformací) v rovině. Navíc jsme ukazovali, že kromě translací Ta o vektor a jde pouze o rotace Rϕ o jakýkoliv úhel ϕ kolem počátku a zrcadlení Z vůči jakékoliv přímce procházející počátkem (povšimněme si, že středová souměrnost je totéž jako rotace o π). Zastavíme se teď u ilustrace obecných grupových pojmů na problému symetrií rovinných obrazců. Budeme přitom uvažovat objekty typu dlaždiček. Nejprve jednotlivě, tj. ve formě ohraničeného obrázku v rovině, později ještě s požadavkem dláždění v rovinném pásu nebo v celé rovině. Pro začátek uvažme třeba úsečku a rovnostranný trojúhelník. Ptáme se, jak moc jsou symetrické, tzn. vůči kterým trasformacím (zachovávajícím velikost) jsou invariantní. Jinak řečeno, chceme aby obraz našeho obrazce byl od původního k nerozeznání, dokud si nepopíšeme nějaké význačné body, třeba vrcholy trojúhelníka A, B a C a konce úseček. Zároveň je předem jasné, že všechny symetrie pevně zvoleného útvaru budou vždy tvořit grupu (většinou pouze s jediným prvkem, identickým zobrazením). 3A B p Zp 1 2 U úsečky je situace obzvlášť jednoduchá – na první pohled je zřejmé, že jedinými jejími netriviálními symetriemi jsou rotace o π kolem středu úsečky, zrcadlení vůči ose této úsečky a zrcadlení vůči úsečce samotné. Všechny tyto symetrie jsou samy sobě inverzí. Celá grupa symetrií úsečky má tedy čtyři prvky. Její tabulka násobení vypadá takto: 3Jestliže totiž má zobrazení F : R2 → R2 zachovávat velikosti, totéž musí být pravda pro přenášené vektory rychlostí, tj. Jacobiho matice DF(x, y) musí být v každém bodě ortogonální. Rozepsání této podmínky pro dané zobrazení F = (f (x, y), g(x, y)) : R2 → R2 vede na systém diferenciálních rovnic, který má pouze afinní řešení, protože snadno uvidíme, že všechny druhé derivace F musí být nulové (a pak už je naše tvrzení okamžitým důsledkem Taylorovy věty se zbytkem). Zkuste si promyslet detaily! Ve skutečnosti vede stejný postup k výsledku pro euklidovské prostory libovolné dimenze. Všimněte si přitom, že dokazovaná podmínka je nazávislá na volbě afinních souřadnic, proto složením F s lineárním zobrazením výsledek nemění. Můžeme proto pro pevný bod (x, y) složit (DF)−1 ◦F a bez újmy na obecnosti rovnou předpokládat, že DF(x, y) je matice identického zobrazení. Derivováním rovnic pak dostáváme důsledky, které přímo říkají požadované tvrzení. 467 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY · R0 Rπ ZH ZV R0 R0 Rπ ZH ZV Rπ Rπ R0 ZV ZH ZH ZH ZV R0 Rπ ZV ZV ZH Rπ R0 a je tedy celá tato grupa komutativní. Pro rovnostranný trojúhelník už symetrií nacházíme víc: můžeme rotovat o π/3 nebo můžeme zrcadlit vůči osám stran. Abychom dostali grupu celou, musíme přidat všechna složení takovýchto transformací. Už v 1.29 jsme viděli, že složení dvou zrcadlení je vždy otočením. Zároveň je zřejmé, že složení takových zrcadlení v opačném pořadí dá otočení o stejný úhel, ale s opačnou orientací. V našem případě tedy zrcadlení kolem dvou různých os vygenerují postupnou opakovanou aplikací všechny symetrie, který bude dohromady šest. Jestliže si umístíme trojúhelník v souřadnicích jako na obrázku, bude našich šest transformací zadáno maticemi a = 1 0 0 1 , b = −1 2 √ 3 2 − √ 3 2 −1 2 , c = −1 2 − √ 3 2√ 3 2 −1 2 d = −1 0 0 1 , e = 1 2 − √ 3 2 − √ 3 2 −1 2 , f = 1 2 √ 3 2√ 3 2 −1 2 . Sestavením tabulky pro násobení, tak jak jsme ji udělali pro grupu permutací 3 obdržíme právě stejný výsledek. Pro větší názornost jsou vrcholy označeny čísly, takže jsou příslušné permutace přímo čitelné. Obdobně umíme nacházet grupy symetrií s k různými rotacemi a k zrcadleními. Stačí si k tomu vzít pravidelný k-úhelník. Takové grupy symetrií se často označují jako grupy Dk a říká se jim dihedrální grupy řádu k. Tyto grupy jsou nekomutativní pro všechna k ≥ 3, zatímco D2 je komutativní. Název patrně je odvozen od skutečnosti, že D2 je grupa symetrií molekuly vodíku H2, ve které jsou dva atomy vodíku a geometricky si ji lze představit jako úsečku. Stejně tak lze snadno najít obrazce, které mají pouze rotační symetrie a jde tedy o komutativní grupy, které se v chemii značí jako Ck. Říkáme jim cyklické grupy řádu k. K tomu postačí např. uvažovat pravidelný mnohoúhelník, u kterého nesymetricky, ale pořád stejně, pozměníme chování hran, viz. čerchované rozšíření trojúhelníku na obrázku. Všimněme si, že grupu C2 lze realizovat dvěma způsoby – buď jedinou netriviální rotací o π nebo jediným zrcadlením. Jako první ukázku síly našich abstraktních úvah dokážeme následující větu. Řekneme, že obrazec má diskrétní grupu symetrií, jestliže množina obrazů libovolného bodu při působení všemi prvky grupy je diskrétní podmnožinou v rovině (tj. všechny její body mají okolí, ve kterém už žádný další bod množiny není). Všimněme si, že každá diskrétní grupa symetrií ohraničeného obrazce je nutně konečná. 468 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Věta. Nechť je M ohraničená množina v rovině R2 s diskrétní grupou grupou symetrií G. Pak je grupa G buď triviální nebo jedna z grup Ck, Dk, s k > 1. Důkaz. Kdyby nějaká množina M připouštěla jako svoji symetrii translaci, nemůže být ohraničená. Pokud by M připouštěla rotaci o úhel, jehož žádný celočíselný násobek není 2π (tj. rotaci o iracionální násobek 2π), pak bychom iteracemi této rotace obdželi hustou podmnožinu obrazů na příslušné kružnici. Grupa symetrií by tedy nemohla být diskrétní. Pokud by M připouštěla netriviální rotace s různými středy, opět nemůže být ohraničená. Napíšeme-li totiž příslušné rotace v komplexní rovině jako R : z → (z − a)ζ + a, Q : z → ηz pro komplexní jednotky ζ = e2πi/k , η = e2πi/ a libovolné a = 0 ∈ C, pak okamžitě vidíme Q ◦ R ◦ Q−1 : z → z + aη(1 − ζ), což je translace o netriviální vektor, pokud není úhel rotace Q nulový. Množina M by tedy nemohla být ohraničená. Totéž platí pro případ, že by existovala rotační symetrie a zrcadlení podél přímky, která neprochází středem rotace. Máme tedy k dispozici pouze rotace se společným středem a zrcadlení podél přímek tímto středem procháze- jících. Zbývá tedy dokázat, že je celá grupa složena vždy buď pouze z rotací nebo vždy ze stejného počtu rotací a zrcadlení. Připomeňme, že vždy složením dvou různých zrcadlení dostáváme rotaci o úhel rovný polovině úhlu svíraného osami zrcadlení (viz 1.29). Proto je i naopak složením zrcadlení podle přímky p s rotací o úhel ϕ/2 zase zrcadlení podél přímky svírající úhel ϕ s p. Odtud již vcelku snadno plyne požadované tvrzení. 10.5 11.4. Symetrie rovinných dláždění. Složitější chování lze vypozorovat u rovinných obrazců v pásech nebo v celé rovině (řekněme, že abstraktně zkoumáme možnosti symetrií pro různé dlažby). Nejprve uvažme množinu tvořenou pásem v rovině uzavřeném mezi dvěma rovnoběžkami a předpokládejme, že je celý tento pás pokryt disjuktními obrazy ohraničené podmnožiny M pomocí nějaké translace. Tato translace bude samozřejmě symetrií zvoleného dláždění rovinného pásu. Grupa symetrií tedy bude vždy nekonečná. Pro symetrie takové množiny nepřicházejí v úvahu žádné netriviální rotace, kromě Rπ , a jediná možná zrcadlení jsou buď horizontální podle osy pásu nebo vertikální podle kterékoliv přímky kolmé na hranice pásu. Zůstavají ještě případné translace zadané vektorem rovnoběžným s osou pásu. Nepříliš složitá diskuse vede k popisu všech diskrétních grup symetrií pro rovinné pásy. Každá takové grupa je generována některými z následujících možných symetrií: translace T , posunuté zrcadlení G (tj. složení horizontálního zrcadlení 469 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY s translací), vertikální zrcadlení V , horizontální zrcadlení H a rotace R o π. Věta. Každá diskrétní grupa symetrií dláždění pásu v rovině je jednoho z následujících sedmi typů, tj. je izmorfní s jednou z grup generovaných následujícími symetriemi: (1) jedinou translací T (2) jediným posunutým zrcadlením G (3) jednou translací T a jedním vertikálním zrcadlením V (4) jednou translací T a jednou rotací R (5) jednou posunutou translací G a jednou rotací R (6) jednou translací T a horizontálním zrcadlením H (7) jednou translací T , horizontálním zrcadlením H a jedním vertikálním zrcadlením V . Důkaz zde nyní nebudeme uvádět. Příklady vzorů časem by se mohlo dát ověření do série příkladů za kapitolou, případně i sems příslušnými symetriemi jsou aspoň na obrázku. Složitější je to se symetriemi dláždění, které vyplní celou rovinu. Nemáme zde prostor pro podrobnější zkoumání, nicméně alespoň poznamenejme, že všech takových grup symetrií v rovině je pouze sedmnáct. Říká se jim dvourozměrné krystalografické grupy. Obdobná úplná diskuse je známa i pro trojrozměrné diskrétní grupy symetrií. Bohatá teorie byla vypracována zejména v 19. století v souvislosti se studiem symetrií krystalů a molekul chemických prvků. 10.6 11.5. Homomorfismy grup. Připomeňme, že zobrazení f : G → H mezi dvěmi grupami G a H se nazývá homomorfismus grup, jestliže respektuje násobení, tj. pro všechny prvky a, b ∈ G platí f (a · b) = f (a) · f (b). Povšimněme si, že násobení vlevo je uvnitř grupy G předtím, než zobrazujeme, zatímco vpravo jde o násobení v H poté, co zobrazujeme. Přímo z definice se snadno ověří následující vlastnosti homomorfismů: Tvrzení. Pro každý homomorfismus f : G → H grup platí (1) obraz jednotky e ∈ G je jednotka v H (2) obraz inverze k prvku je inverzí obrazu. tj. f (a−1 ) = f (a)−1 . (3) obraz podgrupy K ⊂ G je podgrupa f (K) ⊂ H. (4) vzorem f −1 (K) ⊂ G podgrupy K ⊂ H je podgrupa. (5) je-li f zároveň bijekcí, pak i inverzní zobrazení f −1 je homomorfismus. (6) f je injektivní zobrazení právě, když f −1 (e) = {e}. Důkaz. Je-li K ⊂ G podgrupa, pak pro každé dva prvky y = f (a), z = f (b) v H nutně také y · z = f (a · b) patří do obrazu. Je proto vždy obrazem podgrupy opět podpologrupa (tj. bude to podgrupa, pokud obraz nutně obsahuje i inverze a jednotku). 470 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Specielně, triviální podgrupa {e} má za obraz opět podpologrupu. Protože z rovnosti z · z = z v grupě H vynásobením prvkem z−1 dostáváme z = e, ověřili jsme, že jedinou jednoprvkovou podpologrupou v grupě je triviální podgrupa {e}. Zejména tedy f (e) = e. Přímo z definice homomorphismu nyní vidíme, že f (a−1 ) · f (a) = f (e) = e, tj. f (a)−1 = f (a−1 ). Dokázali jsme tedy první tři tvrzení. Stejně postupujeme u vzorů: jestliže a, b ∈ G splňují f (a), f (b) ∈ K ⊂ H, potom také f (a · b) ∈ K. Předpokládejme, že existuje inverzní zobrazení g = f −1 a zvolme libovolné y = f (a), z = f (b) ∈ H. Pak f (a ·b) = y · z = f (a) · f (b), což je ekvivalentní výrazu g(y) · g(z) = a · b = g(y · z). Je tedy inverze skutečně homomorfismem. Pokud platí f (a) = f (b), pak f (a · b−1 ) = e ∈ H. Pokud je tedy jediným vzorem jednotky v H jednotka v G, pak a · b−1 = e, tj. a = b. Opačná implikace je zřejmá. Podgrupa f −1 (e) jednotkového prvku e ∈ H se nazývá jádro homomorfismu f a značíme ji ker f . Bijektivní homomorfismus grup nazýváme izomorfismus. Z předchozích tvrzení okamžitě vyplývá, že homomorfismus f : G → H s triviálním jádrem je izomorfismem na obraz f (G). 10.7 11.6. Příklady. Grupy zbytkových tříd Zk jsou izomorfní grupám komplexních k–tých odmocnin z jedničky, což jsou zároveň izomorfní obrazy konečných grup otočení v rovině o celé násobky úhlu 2π/k. Nakreslete si obrázek, počítání s tzv. komplexními jednotkami e2πi/k je velmi efektivní. Zobrazení exp : R → R+ je izomorfismus aditivní grupy reálných čísel na multiplikativní grupu kladných reálných čísel. Tento izomorfismus se přirozeně rozšiřuje na morfismus exp : C → C \ 0 aditivní grupy komplexních čísel na multiplikativní grupu všech nenulových komplexních čísel. Pro komplexní čísla přitom ale dostáváme netriviální jádro. Viděli jsme totiž, že zúžení exp na ryze imaginární čísla (což je podgrupa izomorfní R) je homomorfismem it → eit = cos t + i sin t, tzn. že čísla 2kπi, k ∈ Z, jsou v jádru. Snadno se dopočítá, že je to celé jádro. Je-li totiž es+it = es · eit = 1 pro reálná s a t, musí být es = 1, tj. s = 0, a pak zbývá pouze t = 2kπ pro libovolné celé k. Determinant matice je zobrazením, které každé matici skalárů z K přiřazuje nějaký skalár v K (pracovali jsme s K = Z, Q, R, C). Cauchyova věta o determinantu součinu čtvercových matic det(A · B) = (det A) · (det B) je tedy tvrzením, že pro grupu G = GL(n, K) invertibilních matic je det : G → K \ 0 homomorfismem grup. 471 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY 10.7b 11.7. Součin grup. Jestliže máme k dispozici dvě grupy, můžeme snadno vytvořit složitější grupu následující kon- strukcí: Součin grup Pro každé dvě grupy G, H definujeme součin grup G×H takto: Jako množina je G × H skutečně součin a násobení definujeme po složkách. tj. (a, x) · (b, y) = (a · b, x · y) kde nalevo vystupuje součin, který definujeme, zatímco napravo používáme tečku k naznačení součinů v jednotlivých grupách G a H. Projekce na jednotlivé komponenty G a H v součinu, pG : G × H (a, b) → a ∈ G, pH : G × H (a, b) → b jsou surjektivní homomorfismy grup s jádry ker pG = {(eG, b); b ∈ H} H ker pH = {(a, eH ); a ∈ G} G. Grupa Z6 je izomorfní součinu Z2 × Z3. Docela snadno můžeme toto tvrzení vidět při multiplikativní realizaci grup zbytkových tříd Zk jakožto komplexních k-tých odmocnin z jedničky. Skutečně tak vidíme, že Z6 je tvořeno body na jednotkové kružnici v komplexní rovině ve vrcholech pravidleného šestiúhelníku, Z2 pak odpovídá ±1, Z3 pravidelnému trojúhelníku s jedním vrcholem v jedničce. Jestliže budeme ztotožňovat příslušné body s otočeními v rovině, které jedničku převede právě do nich, pak skládání dvou takových otočení bude vždy komutativní a kombinacemi jednoho otočení ze Z2 a jednoho ze Z3 dostaneme právě všechna otočení ze Z6. Nakreslete si obrázek! Takto tedy dostaneme (při obvyklejší aditivní notaci pro zbytkové třídy) izomorfis- mus: [0]6 → ([0]2, [0]3) [1]6 → ([1]2, [2]3) [2]6 → ([0]2, [1]3) [3]6 → ([1]2, [0]3) [4]6 → ([0]2, [2]3) [5]6 → ([1]2, [1]3) V zápětí uvidíme, že jsou podobné konstrukce k dispozici pro konečné komutativní grupy úplně obecně. 10.7a 11.8. Komutativní grupy. Libovolný prvek a v grupě G je obsažen v minimální podgrupě {a, a2 , a3 , . . . }, která jej obsahuje. Je zjevné, že je tato podgrupa komutativní, a pokud je celá grupa G konečná, nutně musí jednou nastat případ ak = e. Nejmenší k s touto vlastností nazýváme řád prvku a v G. Grupa G je cyklická grupa je-li celé G generované nějakým 472 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY svým prvkem a výše uvedeným způsobem. Pokud je řád k generátoru grupy konečný, jde právě o grupy Ck z naší diskuse symetrií obrazců v rovině. Z definice přímo vyplývá, že každá cyklická grupa je izomorfní buď grupě celých čísel Z (pokud je nekonečná) nebo některé grupě zbytkových tříd Zk (když je konečná). Ve skutečnosti z takových jednoduchých stavebních kamenů můžeme poskládat všechny konečné komutativní grupy. Věta. Každá konečná komutativní grupa G je izomorfní součinu cyklických grup Ck. Je-li n = pk1 1 · · · pkr r rozklad přirozeného čísla n na prvočísla, pak je grupa Cn izomorfní součinu Cn = Cp k1 1 × · · · × Cpkr r . Důkaz. Obecné první tvrzení věty zde vůbec nebudeme dokazovat. Kompletní důkaz lze najít např. v [?]. Několika poznámkami se ještě k problematice vrátíme v odstavci 11.12. Důkaz druhého tvrzení začneme jednodušším speciálním případem, kdy n = pq s nesoudělnými p a q. Zvolme generátory a grupy Cn, b grupy Cp a c grupy Cq. Nabízí se definovat zobrazení f : Cn → Cp × Cq vztahem f (ak ) = (bk , ck ). Protože platí ak · a = ak+ a podobně pro b a c, dostáváme f (ak · a ) = (bk+ , ck+ ) = (bk , ck ) · (b , c ) a jde tedy o homomorfismus. Jestliže je obrazem jednotka, pak k musí být zíroveň násobkem p i q. Protože jsou p a q nesoudělné, znamená to, že je k i násobkem n a je proto f injektivní. Přitom zřejmě mají grupy Cn i Cp × Cq stejně prvků, takže jde o izomorfismus. Odtud již vyplývá tvrzení věty o rozkladu cyklických grup řádu k na součiny menších cyklických grup. Všimněme si, že naopak Cp2 nikdy není izomorfní součinu Cp × Cp. Zatímco Cp2 je totiž generované prvkem řádu p2 , největší dostupný řád prvku v Cp × Cp je jenom p. Vzhledem k tomu, že všechny konečné komutativní grupy jsou izomorfní součinu cyklických grup, můžeme pro malé počty prvků najít všechny takové grupy až na izomorfismus. Např. máme jen dvě grupy s 12 prvky C12 = C4 × C3, C2 × C2 × C3 = C2 × C6. Podobně si můžeme povšimnout, že mají-li všechny prvky v grupě G kromě jednotky řád 2, pak jde o grupu (C2)n pro nějaké n, zejména tedy má 2n prvků. Skutečně, kdybychom totiž v rozkladu G na součin cyklických grup povolili Cp s p > 2, pak by tam nutně musely vzniknout prvky vyššího řádu. 10.8 473 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY 11.9. Rozklady podle podgrup. Volbou libovolné podgrupy H v grupě G dostáváme další informace o struktuře celé grupy. Na množině prvků grupy G nyní definujeme relaci a ∼H b jestliže b−1 · a ∈ H. Snadno ověříme, že je takto definována relace ekvivalence: Platí a−1 · a = e ∈ H, je tedy relace reflexivní. Je-li b−1 ·a = h ∈ H, potom a−1 ·b = (b−1 ·a)−1 = h−1 ∈ H, je proto relace symetrická. Konečně, je-li c−1 · b ∈ H a zároveň je b−1 · a ∈ H, potom c−1 · a = c−1 · b · b−1 · a ∈ H, ověřili jsme tedy i tranzivitu. Celá grupa G se proto jako množina rozpadá na tzv. levé třídy rozkladu podle podgrupy H vzájemně ekvivalentních prvků. Třídu příslušející prvku a značíme a · H a skutečně platí, že a · H = {a · h; h ∈ H}, neboť prvek b je ve stejné třídě s a, právě když jde takovýmto způsobem vyjádřit. Množinu všech levých tříd rozkladu podle podgrupy H označujeme G/H. Obdobně definujeme pravé třídy rozkladu H ·a. Příslušná ekvivalence je: a ∼ b, jestliže a · b−1 ∈ H. Proto H \ G = {H · a; a ∈ G}. Tvrzení. Pro třídy rozkladu grupy G podle podgrupy H platí: (1) Levé a pravé třídy rozkladu podle podgrupy H ⊂ G splývají právě, když pro každé a ∈ G, h ∈ H platí a · h · a−1 ∈ H. (2) Všechny třídy (levé i pravé) mají shodnou mohutnost s podgrupou H. Důkaz. Obě vlastnosti vyplývají bezprostředně z definičních vlastností. V prvém případě chceme, aby pro jakékoliv a ∈ G, h ∈ H platilo h · a = a · h pro vhodné h ∈ H. To ale nastane právě tehdy, když a−1 · h · a = h ∈ H. Ve druhém případě si stačí uvědomit, že pokud a · h = a · h , pak také vynásobením a−1 zleva obdržíme h = h . Jako okamžitý důsledek předchozího jednoduchého tvrzení dostáváme 10.9 11.10. Věta. Nechť G je konečná grupa s n prvky, H její podgrupa. Potom (1) Mohutnost n = |G| je součinem mohutnosti H a mohutnosti G/H, tj. |G| = |G/H| · |H| (2) Přirozené číslo |H| je dělitelem čísla n. (3) Je-li a ∈ G prvek řádu k, pak k dělí n. (4) Pro každé a ∈ G je an = e. (5) Je-li mohutnost grupy G prvočíslo, pak je G izomorfní cyklické grupě Zn. Druhému tvrzení se říkává Lagrangeova věta, předposlednímu malá Fermatova věta. 474 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Důkaz. Viděli jsme, že každá třída levého rozkladu má právě |H| prvků. Přitom dvě různé třídy rozkladu musí mít nutně prázdný průnik. Odtud vyplývá první tvrzení. Druhé tvrzení je okamžitým důsledkem prvního. Každý prvek a ∈ G generuje cyklickou podgrupu {a, a2 , . . . , ak = e} a právě počet prvků této podgrupy je řádem prvku a. Proto musí řád dělit počet prvků v G. Jelikož je řád k prvku a dělitelem čísla n a ak = e, je také an = (ak )s = e pro nějaké s. Jestliže je n > 1, pak existuje prvek a ∈ G různý od jednotky e. Jeho řád je přirozené číslo k různé od jedničky a nutně dělí n. Proto musí být k rovno n. Pak ovšem jsou všechny prvky G tvaru ak pro k = 1, . . . , n. Tady určitě přijdou nějaké reminiscence z elementární teorie čísel! 10.10 11.11. Normální podgrupy a faktorgrupy. Podgrupy H, pro které platí, že a · h · a−1 ∈ H pro všechny a ∈ G, h ∈ H, se nazývají normální podgrupy. Pro normální podgrupy je dobře definováno násobení na G/H vztahem (a · H) · (b · H) = (a · b) · H. Skutečně, volbou jiných reprezentantů a · h, b · h dostaneme opět stejný výsledek (a ·h·b ·h )·H = ((a ·b)·(b−1 ·h·b)·h )·H = (a ·b)·H. Totéž si můžeme odůvodnit tak, že nezáleží na tom jestli pracujeme s pravými nebo levými třídami. Můžeme proto rovnou naše třídy psát jako H · a · H a potom snadno definujeme (H · a) · (b · H) = H · (a · b) · H. Zřejmě jsou splněny pro nové násobení na G/H všechny vlastnosti grupy: jednotkou je sama grupa H jakožto třída e ·H jednotky, inverzí k a ·H je zřejmě a−1 ·H a asociativita násobení je zřejmá z definice. Hovoříme o faktorové grupě G/H grupy G podle normální podgrupy H. V komutativních grupách jsou samozřejmě všechny podgrupy normální. Podmnožina nZ = {na; a ∈ Z} ⊂ Z zadává v celých číslech podgrupu a její faktorgrupou je právě (aditivní) grupa zbytkových tříd Zn. Z definice je zřejmé, že všechna jádra homomorfismů jsou normální podgrupy. Naopak, jestliže je podgrupa H ⊂ G normální, pak zobrazení p : G → G/H, a → a · H je surjektivní homomorfismus grup s jádrem H. Skutečně, p je dobře definované, přímo z definice násobení na G/H je vidět, že p je homomorfismus, a p je zjevně surjektivní. Je tedy vidět, že normální podgrupy jsou právě všechna jádra homomorfismů. 475 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Dále, pro libovolný homomorfismus grup f : G → K s jádrem H = ker f je dobře definován také homomorfismus ˜f : G/ ker f → K, ˜f (a · H) = f (a), který je injektivní. Zdánlivě paradoxní je příklad homomorfismu grup C∗ → C∗ , který je definovaný na nenulových komplexních číslech vztahem z → zk s přirozeným k. Zjevně jde o surjektivní homomorfismus a jeho jádro je množina k–tých odmocnin z jedničky, tj. cyklická podgrupa Zk. Předchozí úvaha tedy dává pro všechna přirozená k izomorfismus ˜f : C∗ /Zk → C∗ . Tento příklad ukazuje, že u nekonečných grup nejsou počty s mohutnostmi tak přehledné jako tomu bylo u konečných grup ve Větě 11.10. 10.10a 11.12. Exaktní posloupnosti. Kdykoliv zvolíme normální podgrupu H v grupě G, dostáváme tzv. krátkou exaktní posloupnost grup e → H → G → G/H → e, kde šipky postupně znázorňují jediný homomorfismus triviální grupy {e} do grupy H, vložení ι podgrupy H ⊂ G, projekci ν na faktorgrupu G/H a, konečně, jediný morfismus grupy G/H na triviální grupu {e}. Ve všech případech je vidět, že obraz předcházející šipky je přesně jádrem následující. To je definice exaktnosti posloupnosti homomorfismů. Jesliže existuje homomorfismus σ : G/H → G, takový že ν ◦ σ = idG/H , říkáme, že se naše exaktní posloupnost štěpí. Lemma. Každá rozštěpená krátká exatkní posloupnost komutativních grup zadává izomorfismus G = H × G/H. Důkaz. Definujeme zobrazeni f : H × G/H → G vztahem f (a, b) = a · σ(b). Protože pracujeme s komutativními grupami, jde zjevně o homomorfismus: f (aa , bb ) = aa σ(b)σ(b ) = (aσ(b))(a σ(b )). Jestliže f (a, b) = e, pak σ(b) = a−1 ∈ H, tj. b = ν(σ(b)) je tedy jednotkový prvek v G/H. Pak ovšem jeho obraz musí být σ(b) = e a je proto i a = e. Protože jsou levé a pravé třídy rozkladu u komutativních grup totožné, je zobrazení f zjevně surjektivní. Dokázali jsme tedy, že je f izomorfismus. Můžeme nyní naznačit hlavní ideu důkazu Věty 11.8. Kdybychom totiž věděli, že se všechny krátké exaktní posloupnosti vzniklé volbou cyklických podgrup H v konečných komutativních grupách G štěpí, pak bychom snadno důkaz vedli indukcí. V grupě G o mohutnosti n, která není cycklická, bychom totiž zvolili prvek s řádem p < n a našli jím generovanou cyklickou podgrupu H a štěpení příslušné krátké exaktní posloupnosti. 476 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Tím bychom dostali grupu G vyjádřenou jako součin zvolené cyklické podgrupy H a grupy G/H s mohutností n/p. Hlavním technickým bodem důkazu tedy je ověření, že v každé konečné komutativní grupě najdeme prvky řádu pr s patřičnými mocninami prvočíselných p a že se skutečně výše uvedené krátké exaktní posloupnosti pro tyto grupy štěpí. 10.11 11.13. Akce grupy. Již jsme viděli, že často potkáváme grupy jako množiny transformací nějaké pevné množiny. Musí přitom být všechny invertibilní a zároveň musí být naše množina transformací uzavřená na skládání. Často ale také chceme pracovat s pevně zvolenou grupou, jejíž prvky reprezentujeme jako zobrazení na nějaké množině, přitom ale ne nutně jsou zobrazení příslušná různým prvkům grupy různá. Např. všechna otočení roviny kolem počátku o všechny možné úhly odpovídají grupě reálných čísel. Otočení o 2π je ale identické zobrazení. Formálně si můžeme takovou situaci popsat následovně. Akce grupy Levá akce grupy G na množině S je homomorfismus grupy G do podgrupy invertibilních prvků v pologrupě SS všech zobrazení S → S. Takový homomorfismus si také můžeme představit jako zobrazení ϕ : G × S → S, které splňuje ϕ(a · b, x) = ϕ(a, ϕ(b, x)), odtud název „levá akce“. Často budeme k vyjádření akce prvku grupy na prvku S používat pouze zápis a · x (byť jde o jinou tečku než u násobení uvnitř grup). Definiční vlastnost pak vypadá takto: (a · b) · x = a · (b · x). Obraz prvku x ∈ S v akci celé grupy G nazýváme orbita Sx prvku x, tj. Sx = {y = ϕ(a, x); a ∈ G}. Pro každý bod x ∈ S definujeme izotropní podgrupu Gx ⊂ G akce ϕ, Gx = {a ∈ G; ϕ(a, x) = x}. Jestliže pro každé dva prvky x, y ∈ S existuje a ∈ G tak, že ϕ(a, x) = y, pak říkáme, že akce ϕ je tranzitivní. Jestliže zvolíme dva body x, y ∈ S a prvek g ∈ G zobrazující x an y = g·x, pak je zjevně množina {ghg−1 ; h ∈ Gx} izotropní podgrupou Gy. Zobrazení h → ghg−1 je přitom homomorfismem grup Gx → Gy. Snadno se vidí, že u tranzitivních akcí je celý prostor jedinou orbitou a všechny izotropní podgrupy mají stejnou mohutnost. Jako příklad tranzitivní akce konečné grupy můžeme uvést např. zjevnou akci grupy permutací pevně zvolené množiny X na samotné množině X. Přirozená akce všech invertibilních lineárních transformací na nenulových prvcích 477 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY vektorového prostoru V je také tranzitívní. Pokud vezmeme ale prostor V celý, je nulový vektor zvláštní orbitou. Výše uváděný příklad akce aditivní grupy reálných čísel prostřednictvím rotací kolem pevného středu O v rovině není tranzitivní. Orbity jednotlivých bodů jsou právě kružnice se středem O procházející těmito body. Typický příklad tranzitivní akce grupy G je přirozená akce na množině levých tříd G/H pro jakoukoliv podgrupu H. Definujeme ji vztahem g · (aH) = (ga)H. Snadno ukážeme, že takto v podstatě vypadají všechny tranzitivní akce grup. Pro libolnou tranzitivní akci G × S → S a pevně zvolený bod x ∈ G můžeme totiž ztotožnit S s množinou levých tříd G/Gx pomocí vztahu gGx → g · x. Toto zobrazení je zjevně surjektivní a obrazy g · x = h · x splývají právě když h−1 g ∈ Gx a to je ekvivalentní s gGx = hGx. Konečně si všimněme, že toto ztotožnění převádí původní akci G na S právě na výše uvedenou akci G na G/Gx. 10.11a 11.14. Věta. Pro každou akci konečné grupy G na konečné množině S platí: (1) Pro každý prvek x ∈ S je |G| = |Gx| · |Sx|. (2) (Burnsidovo lemma) Je-li N počet orbit akce G na S pak |G| = 1 N g∈G |Sg|, kde Sg = {x ∈ S; g · x = x} označuje množinu pevných bodů akce prvku g. Důkaz. Uvažme libovolný bod x ∈ S a izotropní podgrupu Gx ⊂ G tohoto bodu. Stejný argument jako na konci minulého odstavce u tranzitivních grup můžeme uplatnit na každou akci grupy G. Dostáváme zobrazení G/Gx → Sx, g · Gx → g · x. Pokud (g · Sx) · x = (h · Sx) · x, pak zjevně g−1 h ∈ Sx, je tedy naše zobrazaní injektvní. Zároveň je zjevně surjektivní, proto pro mohutnosti našich konečných množin platí |G/Gx| = |Sx|. Odtud již vyplývá první vlastnost z věty, protože |G| = |G/Gx| · |Gx|. Druhé tvrzení dokážeme tak, že dvěma způsoby spočteme mohutnost množiny pevných bodů akce: F = {(x, g) ∈ S × G; g(x) = x} ⊂ S × G. Protože jde o konečné množiny, můžeme si představit prvky součinu S × G jako prvky v matici (sloupce označujeme prvky v S, řádky pak podle prvků v G). Sčítáním po řádcích i sloupcích obdržíme |F| = g∈G |Sg| = x∈S |Gx|. Nyní si pro přehlednost vyberme po jednom reprezentantu x1, . . . , xN z každé orbity v S a připomeňme, že mohutnosti 478 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY izotropních grup pro body ve stejné orbitě jsou stejné. Využitím již dokázaného tvrzení (1) nyní vcelku snadno dostáváme |F| = g∈G |Sg| = N i=1 x∈Sxi |Gx| = N i=1 |Sxi ||Gxi | = N · |G| a důkaz je ukončen. Doporučujeme si pečlivě promyslet, jak užitečná jsou tvrzení věty pro řešení kombinatorických úloh, viz ??. explicitně zmínit neco z vedlejších sloupců 2. Okruhy polynomů Grupové operace byly podstatné u skalárů i vektorů. Vystupovalo nám tam ovšem několik obdobných struktur zároveň. Zaměříme se teď právě na takové případy. Budeme přitom mít na mysli zejména obvyklé skaláry, tj. celá čísla Z, racionální čísla Q, komplexní čísla C, a množiny polynomů nad takovými skaláry K. Budeme přitom ale pečlivě budovat abstraktní algebraickou teorii. 10.12 11.15. Okruhy a tělesa. Celá čísla mají následující vlastnosti tzv. okruhu: Okruhy a obory integrity Definice. Komutativní grupa (M, +) s neutrálním prvkem 0 ∈ M, spolu s další operací · splňující • (a · b) · c = a · (b · c), pro všechny a, b, c ∈ M; • a · b = b · a, pro všechny a, b ∈ M; • existuje prvek 1 takový, že pro všechny a ∈ M platí 1 · a = a; • a · (b + c) = a · b + a · c, pro všechny a, b, c ∈ M; se nazývá komutativní okruh. Jestliže v okruhu K platí c · d = 0 právě, když alespoň jeden z prvků c a d je nulový, pak nazýváme okruh K oborem integrity. Poslední vlastnosti v našem výčtu axiomů okruhu se říká distributivita sčítání vůči násobení. Pokud neplatí vlastnost komutativity operace ·, hovoříme o nekomutativním okruhu. V dalším se ovšem omezíme zpravidla na okruhy komutativní. Operaci + budeme říkat sčítání a operaci · násobení, aniž by to znamenalo, že jde skutečně o tyto operace na některém z našich číselných oborů. Navíc budeme vždy předpokládat existenci jedničky 1 pro operaci násobení. Neutrálnímu prvku pro sčítání říkáme nula. Tělesa Netriviální (komutativní) okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá (komutativní) těleso. Komutativní těleso se také nazývá pole. 479 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Typickým příkladem komutativních těles, tj. polí, jsou číslené obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Dobrým příkladem nekomutativního okruhu s jedničkou je množina Matk(K) všech čtvercových matic nad okruhem K s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity. Jako příklad nekomutativního tělesa uveďme těleso kvaternionů H, viz příklad ?? ve druhém sloupci. Lemma. V každém komutativním okruhu K s jedničkou platí následující vztahy (které nám jistě připadají samozřejmé u skalárů) (1) 0 · c = c · 0 = 0 pro všechny c ∈ K, (2) −c = (−1) · c = c · (−1) pro všechny c ∈ K, (3) −(c · d) = (−c) · d = c · (−d) pro všechny c, d ∈ K, (4) a · (b − c) = a · b − a · c, (5) celý okruh K je triviální množinou {0} = {1} právě, když 0 = 1. Důkaz. Všechna tvrzení vyplývají z jednoduché úvahy a definičních axiomů. V prvém případě počítáme pro jakákoliv c, a: c · a = c · (a + 0) = c · a + c · 0 a protože jediným neutrálním prvkem vůči sčítání je nula, dostáváme a · 0 = 0. Stejně se dokáže i 0 · a = 0. Ve druhém případě teď stačí spočíst 0 = c · 0 = c · (1 + (−1)) = c + c · (−1), proto je c · (−1) opačný prvek k prvku c, což jsme chtěli dokázat. Další dvě tvrzení jsou už přímým důsledkem druhého vztahu a základních axiomů. Jestliže je celý okruh tvořen jediným prvkem, je pochopitelně 0 = 1. Naopak, jestliže platí 1 = 0, pak pro jakékoliv c ∈ K je c = 1 · c = 0 · c = 0. 10.13 11.16. Polynomy nad okruhy. Definice komutativního okruhu s jedničkou abstrahuje právě vlastnosti potřebné k násobení a sčítání. Můžeme je hned využít pro práci s tzv. polynomy. Rozumíme jimi jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků K a jedné neznámé proměnné pomocí operací sčítání a násobení. Formálně můžeme definovat polynomy takto:4 Polynomy Definice. Nechť K je jakýkoliv komutativní okruh skalárů s jedničkou. Polynomem nad K rozumíme konečný výraz f (x) = k i=0 aixi kde ai ∈ K, i = 0, 1, . . . , k, jsou tzv. koeficienty polynomu. Je-li ak = 0, říkáme, že f (x) má stupeň k, píšeme deg f = k. Nulový polynom nemá stupeň, polynomy stupně nula jsou 4Ne náhodou je pro okruh použit symbol K – nadále si pod ním představujte třeba kterýkoliv okruh naších číselných oborů. 480 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY právě nenulové prvky v K, kterým říkáme konstantní poly- nomy. Polynomy f (x) a g(x) jsou stejné, jestliže mají stejné nenulové koeficienty. Množinu všech polynomů nad okruhem K budeme značit K[x]. Každý polynom zadává zobrazení f : K → K, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj. f (c) = a0 + a1c + · · · + akck . Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením. Kořen polynomu f (x) je takový prvek c ∈ K, pro který je f (c) = 0 ∈ K. Obecně mohou různé polynomy definovat různá zobrazení. Např. polynom x2 + x ∈ Z2[x] zadává identicky nulové zobrazení. Obecněji, pro každý konečný okruh K = {a0, a1, . . . , ak} zadává polynom f (x) = (x − a0)(x − a1) . . . (x − ak) identicky nulové zobrazení. Dva polynomy f (x) = i aixi a g(x) = i bixi umíme přirozeně také sčítat i násobit: (f + g)(x) = (a0 + b0) + (a1 + b1)x + · · · + (ak + bk)xk (f · g)(x) = (a0b0) + (a0b1 + a1b0)x + . . . + (a0br + a1br−1 + arb0)xr + · · · + akb xk+ , kde k ≥ jsou stupně polynomů f a g a uvažujeme nulové koeficienty všude tam, kde v původním výrazu pro polynomy nenulové koeficienty nejsou.5 . Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f , g : K → K, díky vlastnostem „skalárů“ v původním okruhu K. Přímo z definice vyplývá, že množina polynomů K[x] nad komutativním okruhem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v K[x] je opět jednička 1 v okruhu K vnímaná jako polynom stupně nula, nulou pro sčítání je nulový polynom. Lemma. Okruh polynomů nad oborem integrity je opět obor integrity. Důkaz. Máme ukázat, že v K[x] mohou být netriviální dělitelé nuly pouze, jetliže jsou už v K. To je ale zřejmé z výrazu pro násobení polynomů. Jsou-li f (x) a g(x) polynomy stupně k a jako výše, pak koeficient u xk+ v součinu f (x) · g(x) je součin ak · b a ten musí být nenulový, pokud nejsou dělitelé nuly v K. 10.19 11.17. Polynomy více proměnných. Často se setkáváme s objekty popsanými pomocí polynomiálních výrazů ale s více proměnnými. Např. kružnici v rovině se středem S = (x0, y0) a poloměrem r zapíšeme pomocí rovnice 5Formálně bychom mohli naopak za polynom považovat nekonečný výraz pro i = 0, . . . , ∞ s podmínkou, že jen konečně mnoho koeficientů je nenulových. 481 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY (x − x0)2 + (y − y0)2 − 1 = 0. Okruhy polynomů v proměnných x1, . . . , xr můžeme zavést úplně podobně jako jsme postupovali s K[x]. Místo mocnin jediné proměnné xk budeme uvažovat tzv. monomy xk1 1 · · · xkr r a jejich formální lineární kombinace s koeficienty ak1···kr ∈ K. Formálně i technicky je ale jednodušší je definovat induktivně vztahem K[x1, . . . , xr] := K[x1, . . . , xr−1] [xr]. Např. K[x, y] = K[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem K[x]. Snadno si každý ověří (promyslete si to!), že polynomy v proměnných x1, . . . , xr lze i při této definici chápat jako výrazy vzniklé z písmen x1, . . . , xn a prvků okruhu K konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v K[x, y] jsou tvaru f = an(x)yn + an−1(x)yn−1 + · · · + a0(x) = (amnxm + · · · + a0n)yn + · · · + (bp0xp + · · · + b00) = c00 + c10x + c01y + c20x2 + c11xy + c02y2 + . . . Pro zjednodušení zápisu si zavedeme tzv. multiidexovou symboliku (kterou jsme používali při diskusi parciálních diferenciálních rovnic vyšších řádů). Multiindexy Multiindex α délky r je r-tice nezáporných celých čísel (α1, . . . , αr). Celé číslo |α| = α1+· · ·+αr nazýváme velikost multiindexu α. Stručně zapisujeme monomy xα místo xα1 1 xα2 2 . . . xαr r . Pro polynomy v r proměnných pak máme symbolické vyjádření velice podobné obvyklému značení pro polynomy v jedné proměnné: f = |α|≤n aαxα , g = |β|≤m aβxβ ∈ K[x1, . . . , xr]. Říkáme, že f má celkový stupeň n, je-li alespoň jeden z koeficientů s multiindexem α velikosti n nenulový. Okamžitě se také nabízejí analogické vzorce pro sčítání a násobení polynomů f + g = |α|≤max(m,n) (aα + bα)xα fg = m+n |γ |=0   α+β=γ (aαbβ)xγ   kde multiindexy se sčítají po složkách a formálně neexistující koeficienty považujeme za nulové. Lemma. Tyto vzorce opravdu popisují sčítání a násobení v induktivně definovaném okruhu polynomů v r proměnných. 482 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Důkaz. Tvrzení lze snadno dokázat indukcí přes počet proměnných. Předpokládejme, že vztahy platí v K[x1, . . . , xr−1] a počítejme součet f = ak(x1, . . . , xr−1)xk r + · · · + a0(x1, . . . , xr−1) = α ak,αxα xk r + . . . g = bl(x1, . . . , xr−1)xl r + · · · + b0(x1, . . . , xr−1) =   β bl,βxβ   xk r + . . . f + g = a0(x1, . . . , xr−1) + b0(x1, . . . , xr−1) + + a1(x1, . . . , xr−1) + b1(x1, . . . , xr−1) xr + . . . = γ (ak,γ + bk,γ )(x1, . . . , xr−1)γ xk r + . . . + γ (a0,γ + b0,γ )(x1, . . . , xr−1)γ = (γ,j) (aj,γ + bj,γ )(x1, . . . , xr−1)γ xj r . Podobně lze vést důkaz pro součin (udělejte samostatně!). Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostaneme: Dusledek. Jestliže v okruhu K nejsou dělitelé nuly, pak také v okruhu polynomů K[x1, . . . , xr] nejsou dělitelé nuly. Důkaz. Budeme postupovat indukcí přes počet proměnných r.6 Polynomy v jediné proměnné mají tvar f = anxn 1 + · · · + a1x1 + a0 a g = bmxm + · · · + b0, přičemľ bm = 0 a an = 0. Vedoucí člen součinu fg je anbmxn+m , protože anbm = 0, zejména tedy je součin nenulových polynomů opět nenulový. Pokud tvrzení platí pro r −1 proměnných, pak použijeme předchozí úvahu pro okruh polynomů v jedné proměnné xr s koeficienty v K[x1, . . . , xr−1]. 10.14 11.18. Dělitelnost a nerozložitelnost. Naším dalším cílem bude pochopit, jak je to v obecném případě polynomů nad oborem integrity s jejich rozkladem na součin polynomů jednodušších, tj. ve speciálním případě polynomů s jedinou proměnnou budeme diskutovat kořeny polynomů. U polynomů s více proměnnými půjde o rozklad na jednodušší faktory nižších stupňů. Protože již víme, že polynomy ve více proměnných můžeme definovat induktivně, stačí nám nyní uvažovat jen polynomy v jedné proměnné, ovšem nad obecným oborem 6Důkaz lze vést také přímo s použitím multiindexových formulí pro součin, když si zavedeme vhodné uspořádání monomů tak, jak to budeme za chvíli stejně dělat. 483 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY integrity, a směřujeme ke zobecnění úvah o dělitelnosti, které byly základem našeho počínání v elemntární teorii čísel. Uvažujme nějaký pevně zvolený obor integrity K. Příkladem nám stále mohou sloužit celá čísla Z nebo okruh Zp s prvočíselným p. Dělitelnost v okruzích Obecně říkáme, že a ∈ K dělí c ∈ K, jestliže existuje b tak, že a · b = c. Skutečnost že c ∈ K je dělitelné a ∈ K zapisujeme a|c. Dělitelé jedničky, tj. invertibilní prvky v K, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu. V oboru integrity jsou dělitelé určeny jednoznačně. Skutečně je-li b = a·c a b = 0, pak c je jednoznačně dáno volbou a, b, protože při b = ac = ac totiž platí 0 = a · (c − c ) a a = 0. Z neexistence dělitelů nuly proto vyplývá c = c . Přimo z definic vyplývají následující tvrzení: Lemma. Nechť a, b, c ∈ K. Potom (1) je-li a|b a zároveň b|c pak také a|c; (2) je-li a|b a zároveň a|c pak také a|(αb + βc) pro všechny α, β ∈ K; (3) a|0 pro všechny a ∈ K (je totiž a · 0 = 0); (4) každý prvek a ∈ K je dělitelný všemi jednotkami e ∈ K a jejich násobky a · e (jak přímo plyne z existence e−1 ). Jednoznačný roklad v oboru integrity Řekneme, že prvek a ∈ K je nerozložitelný, jestliže je dělitelný pouze jednotkami e ∈ K a jejich násobky a · e. Řekneme, že okruh K je obor integrity s jednoznačným rozkladem, jestliže platí: • pro každý nenulový prvek a ∈ K existují nerozložitelné a1, . . . , ar ∈ K takové, že a = a1 · a2 . . . ar • jsou-li prvky a1, . . . , ar a b1, . . . , bs nerozložitelné, nejsou mezi nimi žádné jednotky a a = a1a2 . . . ar = b1b2 . . . bs, pak je r = s a ve vhodném přeuspořádání platí aj = ej bj pro vhodné jednotky ej . Již jsme viděli, že Z je obor integrity s jednoznačným rozkladem a každé pole (komutativní těleso) je obor integrity s jednoznačným rozkladem (protože každý nenulový prvek v poli je jednotka). Pro ilustraci si uveďme příklad oboru integrity, který jednoznačný rozklad nemá. Konstrukce je podobná polynomům, jen místo mocnin uvážíme vhodně se skládající odmocniny: Naše K bude mít prvky tvaru a0 + k i=1 ai 2ni √ xmi 484 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY kde a0, . . . , ak ∈ Z, mi, n ∈ Z>0. Pak jednotky jsou v K pouze prvky ±1, všechny prvky s a0 = 0 jsou rozložitelné, ale např. výraz x nelze vyjádřit jako součin nerozložitelných. Nerozložitelných prvků je v K prostě příliš málo. 10.15 11.19. Dělení se zbytkem a kořeny polynomu. Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Z byla procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Lemma (Algoritmus pro dělení se zbytkem). Nechť K je komutativní okruh bez dělitelů nuly a f, g ∈ K[x] polynomy, g = 0. Pak existuje a ∈ K, a = 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo deg r < deg g. Je-li navíc K pole, nebo je aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně. Důkaz. Tvrzení dokážeme indukcí vzhledem ke stupni f . Je-li deg f < deg g nebo f = 0, pak volíme a = 1, q = 0, r = f , což vyhovuje všem našim podmínkám. Pro konstantní polynom g klademe a = g, q = f , r = 0. Předpokládejme tedy, že deg f ≥ deg g > 0 a pišme f = a0 + · · · + anxn , g = b0 + · · · + bmxm . Buď platí bmf − anxn−m g = 0 a nebo je deg(bmf − anxn−m g) < deg f . V prvém případě jsme hotovi, ve druhém pak, podle indukčního předpokladu, existují a , q , r splňující a (bmf − anxn−m g) = q g + r a buď r = 0 nebo deg r < deg g. Tzn. a bmf = (g + a anxn−m )g + r . Přitom je-li bm = 1 nebo K je pole, pak podle indukčního předpokladu lze volit a = 1 a q , r jsou tak určeny jednoznačně. V takovém případě ovšem získáme bmf = (g + anxn−m )g + r a je-li K pole, můžeme rovnost vynásobit b−1 . Předpokládejme, že f = q1g + r1 je jiné řešení. Pak 0 = f − f = (q − q1)g + (r − r1) a buď je r = r1, nebo deg(r − r1) < deg g. V prvém případě odtud ovšem plyne i q = q1, protože K[x] neobsahuje dělitele nuly. Nechť axs je člen nejvyššího stupně v q − q1 = 0 (určitě existuje). Potom jeho součin se členem nejvyššího stupňe v g musí být nulový (protože nejvyšší stupeň dostaneme tak, že vynásobíme nejvyšší stupně). To ovšem znamená, že a = 0. Protože axs byl největší nenulový stupeň, nutně dostáváme, že q − q1 žádné nenulové monomy neobsahuje, je tedy určitě nulové. Pak ovšem i r = r1. 485 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme tedy polynom f ∈ K[x], deg f > 0, a zkusme jej vydělit polynomem x − b, b ∈ K. Protože je vedoucí koeficient jednička, algoritmus pro dělení dává jednoznačný výsledek. Dostáváme tedy jednoznačně zadané polynomy q a r splňující f = q(x − b) + r, kde r = 0 nebo deg r = 0, tj. r ∈ K. Tzn., že hodnota polynomu f v b ∈ K je rovna právě f (b) = r. Z toho plyne, že prvek b ∈ K je kořen polynomu f právě, když (x − b)|f . Protože po vydělení polynomem stupně jedna vždy klesne stupeň výsledku alespoň o jedničku, dokázali jsme následující tvrzení: Dusledek. Každý polynom f ∈ K[x] má nejvýše deg f kořenů. Zejména tedy zadávají polynomy nad nekonečným oborem integrity stejná zobrazení K → K, právě když jde o stejné polynomy. Skutečně, dva polynomy nad nekonečným komutativním okruhem, které zadávají stejné zobrazení K → K, mají rozdíl, jehož kořenem je každý prvek v K. To však znamená, že pokud by jejich rozdíl nebyl nulový polynom, pak K má nejvýše tolik prvků, kolik je maximum ze stupňů uvažovaných polynomů. Zatímco reálné polynomy mohou být i úplně bez kořenů, každý komplexní polynom naopak takovýto rozklad připouští. To je obsahem tzv. základní věty algebry, kterou pro úplnost uvádíme s (v podstatě) kompletním důkazem. Díky tomuto výsledku víme, že každý polynom v C[x] má tolik kořenů, včetně násobnosti, jako je jeho stupeň deg f = k. Proto připouští vždy rozklad tvaru f (x) = (x − a1) · (x − a2) . . . (x − ak) s vhodnými komplexními kořeny ai. 10.18 11.20. Věta (Základní věta algebry). Pole C je algebraicky uzavřené, tj. každý polynom stupně alespoň 1 má kořen. Důkaz. Předpokládejme, že f ∈ C[z] je nenulový polynom, který nemá kořen, tj. f (z) = 0 pro všechny z ∈ C. Definujme zobrazení ϕ : C → C, z → f (z) |f (z)| tj. ϕ zobrazí celé C do jednotkové kružnice K1 = {eit , t ∈ R} ⊂ R2 = C. Díky našemu předpokladu o nenulovosti f (z) je to skutečně dobře definované zobrazení. Dále definujme zobrazení s hodnotami v kružnici Kr ⊂ C se středem v nule a poloměrem r ≥ 0 ψr : R → Kr, t → ψ(t) = reit . Pro každé r ∈ 0, ∞) máme definováno spojité zobrazení κr = ϕ ◦ψr : R → K1. Ze spojité závislosti κ na parametru r navíc vyplývá existence zobrazení αr : R → R jednoznačně zadaných podmínkami 0 ≤ αr(0) < 2π a κr(t) = eiαr (t) . 486 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Získané zobrazení αr opět spojitě závísí na r. Celkem tedy máme spojité zobrazení α : R × 0, ∞) → R, (t, r) → αr(t) a z jeho konstrukce plyne že pro všechna r je 1 2π (αr(2π) − αr(0)) = nr ∈ Z. Protože je α spojité, znamená to, že nr je celočíselná konstanta nezávislá na r. Podívejte se na obrázek, odkud kam jdou jednotlivá zobrazení v naší konstrukci! $0$ $2\pi$ $0$ $\psi_r$ $\alpha_r$ $psi_1$ $K_1$ $\phi$$e^{it}$ $K_r$ $2\pi$ Pro dokončení důkazu si stačí uvědomit, že pokud f = a0 + · · · + adzd a ad = 0, pak pro malá r se bude αr chovat podobně jako konstantní zobrazení, zatímco pro velká r to vyjde stejně, jako kdyby f = zd . Nejprve si spočtěme, jak tedy nr dopadne při f = zd , pak toto tvrzení upřesníme a důkaz tím bude ukončen. Funkce C → C, z → zd , z → zd |zd | se snadno vyjádří pomocí goniometrického tvaru komplexních čísel z = r(cos α + i sin α). zd = rd (cos dα + i sin dα) = rd eidα zd |zd| = 1(cos dα + i sin dα) = eidα zobrazení ϕ je tedy v tomto případě pouze „zatočení“ na jednotkové kružnici. Pak tedy κr(t) = eidt a proto αr(t) = dt, nezávisle na r. Odtud pro naši volbu f = zd vyplývá nr = d. Pokud zvolíme f = azd , a = 0, nebude to mít na předchozí výsledek žádný vliv (přesvědčte se!). Zvolme nyní obecný polynom f = a0 +· · ·+adzd , který nemá kořen. Víme tedy, že a0 = 0 (pokud by bylo a = 0, existoval by kořen). Pro z = 0 platí f (z) adzd = 1 + 1 ad (a0z−d + · · · + ad−1z−1 ) a proto lim|z|→∞ f (z) ad zd = 1. Když tohle víme, můžeme spočítat lim |z|→∞ f (z) |f (z)| − adzd |adzd| = = lim |z|→∞ f (z) adzd adzd |adzd| |adzd | |f (z)| − adzd |adzd| = 0. 487 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Proto nr = d pro velká r. Podobnou úvahu uděláme i pro malá r. Připomeňme si, že a0 = 0. f (z) a0 = 1 + 1 a0 (a1z + · · · + adzd ) proto lim|z|→0 f (z) a0 = 1. Přitom opět platí f (z) |f (z)| = f (z) a0 a0 |a0| |a0| |f (z)| . Odtud lim|z|→0 f (z) |f (z)| = lim|z|→0 a0 |a0| , tj. nr = 0 pro malá r. Celkem vidíme, že stupeň našeho polynomu je d = 0. 10.16 11.21. Největší společný dělitel polynomů. Uvažme okruh polynomů K[x] nad oborem integrity K. Řekneme, že h je největší společný dělitel dvou polynomů a f a g ∈ K[x] jestliže: • h|f a zároveň h|g • jestliže k|f a zároveň k|g pak také k|h. Jako přímý důsledek existence algoritmu pro jednoznačné dělení se zbytkem dostáváme následující důležitou Bezoutovu rovnost Věta. Nechť K je pole a nechť f, g ∈ K[x]. Pak existuje největší společný dělitel h polynomů f a g. Polynom h je určený jednoznačně, až na násobek nenulovým skalárem. Přitom existují polynomy A, B ∈ K[x] takové, že h = Af + Bg. Důkaz. Přímá konstrukce polynomů h, A a B se provede tzv. Euklidovým algoritmem. Provádíme postupně dělení se zbytkem (K je pole, takže to vždy umíme jednoznačně, viz. předchozí lemma): f = q1g + r1 g = q2r1 + r2 r1 = q3r2 + r3 ... rp−1 = qp+1rp + 0. V tomto postupu neustále klesají stupně ri, proto jistě nastane rovnost z posledního řádku (pro vhodné p) a ta říká, že rp|rp−1. Z předposledního řádku pak ale plyne rp|rp−2 a postupně dojdeme až nazpět k prvnímu a druhému řádku, které dají rp|g a rp|f . Pokud h|f a h|g, pak ze stejných rovností postupně plyne, že h dělí všechny ri, zejména tedy rp, tzn. získali jsme největšího společného dělitele h = rp polynomů f a g. 488 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Nyní můžeme postupně dosazovat z poslední do předchozích rovnic. h = rp = rp−2 − qprp−1 = rp−2 − qp(rp−3 − qp−1rp−2) = −qprp−3 + (1 + qp−1)rp−2 = −qprp−3 + (1 + qp−1qp)rp−2 = −qprp−3 + (1 + qpqp−1)(rp−4 − qp−2rp−3) ... = Af + Bg. 10.20 11.22. Podílová tělesa. Když se potýkáme s celočíselnými výpočty, je často technicky výhodnější pracovat v číslech racionálních a až na konci postupu ověřit, že výsledek musí ve skutečnosti být celočíselný. Takto jsme už postupovali mnohokrát. Při práci s polynomy nám bude podobný postup užitečný také. Nechť K je komutativní okruh (s jedničkou) bez dělitelů nuly. Jeho podílové těleso definujeme jako třídy ekvivalence dvojic (a, b) ∈ K × K, b = 0, které zapisujeme a b , a ekvivalence je dána a b = a b ⇔ ab = a b. Sčítání a násobení definujeme prostřednictvím reprezentantů tříd a b + c d = ad + bc bd a b c d = ac bd Snadno se ověří korektnost této definice a vąechny axiomy komutativního tělesa. Zejména je 0 1 neutrální prvek vzhledem ke sčítání, 1 1 je neutrální prvek vzhledem k násobení a pro a = 0, b = 0 je a b b a = 1 1 . Podílové těleso okruhu K[x1, . . . , xr] nazýváme těleso racionálních funkcí a značíme je K(x1, . . . , xr). Všechny algebraické operace s polynomy v softwarových systémech jako je Maple nebo Mathematica jsou prováděny ve skutečnosti nad podílovými tělesy, tj. v tělesech raciolnálních funkcí, zpravidla s použitím K = Q. Zformulujme si teď velice užitečné (i elegantní) tvrzení, jehož důkaz je docela přímočarý, ale vyžaduje poměrně technické dopracování detailů (a odvíjí se na úrovni podílového tělesa racionálních funkcí). Doporučujeme proto pečlivě pročíst následující odstavec a případně pak při prvním čtení přeskočit další tři lemmata důkazu (a pokračovat na straně ??). 10.17 11.23. Věta. Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x] je obor integrity s jednoznačným rozkladem. 489 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Důkaz. Myšlenka důkazu je velice jednoduchá. Uvažujme polynom f ∈ K[x]. Je-li f rozložitelný, pak je f = f1 · f2, kde žádný z polynomů f1, f2 ∈ K[x] není jednotka. Předpokládejme na chvíli navíc, že je-li f dělitelný nerozložitelným polynomem h, pak jistě h dělí f1 nebo f2. Pokud tomu tak vždy bude, docílíme postupnou aplikací předchozí úvahy jednoznačný rozklad. Pokud je totiž f1 dále rozložitelné, opět f1 = g1 · g2, kde g1, g2 nejsou jednotky, a přitom vždy buď oba polynomy g1 a g2 mají menší stupeň než f , nebo se sníží počet nerozložitelných faktorů ve vedoucích členech g1 a g2 (např. nad celými čísly Z je 2x2 + 2x + 2 = 2(x2 + x + 1)). Proto po konečném počtu kroků dojdeme k rozkladu f = f1 . . . fr na nerozložitelné polynomy f1, . . . , fr. Z našeho dodatečného předpokladu také plyne, že každý nerozložitelný polynom h dělící f , dělí některý z f1, . . . , fr. Proto pro každý další rozklad f = f1f2 . . . fs nutně každý z faktorů fi dělí některý z fj a v takovém případě musí být fj = efi pro vhodnou jednotku e. Postupným krácením takových dvojic odvodíme, že r = s a jednotlivé faktory se liší pouze o násobky jednotek. Zbývá tedy dokázat, že je-li f = f1f2 dělitelný nerozložitelným polynomem h, pak jistě h dělí f1 nebo f2. Toto tvrzení odvodíme v několika následujících odstavcích. Dusledek. Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x1, . . . , xr] je obor integrity s jednoznačným rozkladem. Vidíme tedy, že každý polynom nad oborem integrity s jednoznačným rozkladem můžeme rozložit tak, jak to známe s polynomy s reálnými nebo komplexními koeficienty. Zejména je tomu tedy tak pro polynomy nad jakýmkoliv polem skalárů. 10.17a 11.24. Lemma. Nechť K je obor integrity s jednoznačným rozkladem. Pak platí: (1) Jsou-li a, b, c ∈ K, a je nerozložitelné a a|bc, pak buď a|b nebo a|c. (2) Jestliže konstantní polynom a ∈ K[x] dělí f ∈ K[x] pak a dělí všechny koeficienty polynomu f . (3) Je-li a nerozložitelný konstantní polynom v K[x] a a|fg, f, g ∈ K[x], pak a|f nebo a|g. Důkaz. 1. Podle předpokladu bc = ad pro vhodné d ∈ K a nechť d = d1 . . . dr, b = b1 . . . bs, c = c1 . . . cq jsou rozklady na nerozložitelné faktory. To znamená ad1 . . . dr = b1 . . . bsc1 . . . cq. Z jednoznačnosti rozkladu ad plyne a = ebj nebo a = eci pro vhodnou jednotku e. 2. Nechť f = b0 + b1x + · · · + bnxn . Protože a|f , jistě existuje polynom g = c0 + c1x + . . . ckxk takový, že f = ag. Odtud okamžitě plyne k = n, ac0 = b0, . . . , acn = bn. 3. Uvažujme f, g ∈ K[x] jako výše a předpokládejme, že a nedělí ani f ani g. Pak podle předchozího bodu existuje 490 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY nějaké i tak, že a nedělí bi a nějaké j tak, že a nedělí cj . Zvolme taková i, j nejmenší možná. Koeficient u xi+j v polynomu fg je b0ci+j +b1ci+j−1 +· · ·+bi+j c0. Podle naší volby a dělí všechny b0ci+j , . . . , bi−1cj+1, bi+1cj−1, . . . , bi+j c0. Zároveň ale nedělí bicj . Proto nemůže dělit celý koefici- ent. 10.17b 11.25. Lemma. Uvažme podílové těleso L oboru integrity K s jednoznačným rozkladem. Je-li polynom f nerozložitelný v K[x] je nerozložitelný také v L[x]. Důkaz. Každý koeficient a ∈ K můžeme považovat za prvek a 1 ∈ L. Proto každý nenulový polynom f ∈ K[x] můžeme uvažovat jako polynom v L[x] . Předpokládejme, že f = g h pro vhodné g , h ∈ L[x], kde polynomy g , h nejsou jednotky v L[x] (tzn. nejsou to konstantní polynomy, neboť L je pole). Nechť a je společný násobek jmenovatelů koeficientů v g a b je společný násobek jmenovatelů koeficientů v h . Pak bh , ag ∈ K[x] a platí abf = (bh )(ag ). Nechť c je nerozložitelný faktor v rozkladu ab. Pak c dělí (bh )(ag ) a proto c dělí polynom bh nebo polynom ag (podle předchozího lemmatu). To ale znamená, že c můžeme vykrátit. Po konečném počtu takových krácení zjistíme, že f = gh pro polynomy g, h ∈ K[x]. Přitom stupeň polynomů se neměnil, proto i g a h nejsou konstantní. Tím jsme dokázali, že když je f rozložitelné v L[x], je rozložitelné i v K[x] a odtud negací vyplývá i požadovaná implikace. 10.17c 11.26. Lemma. Nechť K je obor integrity s jednoznačným rozkladem a f, g, h ∈ K[x]. Předpokládejme, že f je nerozložitelné a f |gh. Pak buď f |g nebo f |h. Důkaz. Je-li f konstantní polynom (tj. prvek v K), pak jsme tvrzení již dokázali, viz. jedno z předchozích lemmat. Předpokládejme, že deg f > 0. Již víme, že f je nerozložitelný také v L[x], kde L je podílové těleso okruhu K. Předpokladejme tedy nejdříve, že K je pole (a je tedy rovno svému podílovému tělesu). Předpokládejme dále, že f |gh a zároveň f nedělí g. Ukážeme, že pak jistě f |h. Největší společný dělitel polynomů g a f musí být konstantní polynom v L, proto existují A, B ∈ L[x] takové, že 1 = Af + Bg. Odtud h = Af h + Bgh a protože f |gh musí platit i f |h. Vraťme se nyní k obecnému případu. Podle předchozího vyplývá z našich předpokladů, že f |g nebo f |h v okruhu polynomů L[x] nad podílovým tělesem L okruhu K. Nechť např. h = kf v L[x] a zvolme a ∈ K tak, aby ak ∈ K[x]. Pak ah = akf a pro každý nerozložitelný faktor e ∈ a musí platit e|ak, protože f je nerozložitelný a nekonstantní. Můžeme proto e krátit. Po konečném počtu takových krácení je z a jednotka, tzn. h = k f pro vhodné k ∈ K[x]. Důkaz tohoto lemmatu ukončil celý důkaz věty 11.23. 491 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY 3. Systémy polynomiálních rovnic V praktických úlohách se často setkáváme s objekty nebo ději popsanými polynomy, resp. systémy polynomiálních rovnic. Může jít o hledání příslušnosti bodu k nějakému tělesu, hledání extrémů na algebraicky popsaných podmnožinách mnohorozměných prostorů, analýzu pohybů součástí nějakého stroje atd. 10.51 11.27. Afinní variety. Pro jednoduchost (existence kořenů polynomů) budeme pracovat zejména nad polem komplexních čísel, nicméně některé úvahy rozvineme pro obecné pole K. Afinním n-rozměrným prostorem nad polem K rozumíme Kn = K × · · · × K n se standardní afinní strukturou, viz začátek čtvrté kapitoly. Jak jsme již viděli, polynom f = α aαxα ∈ K[x1 . . . , xn] lze přirozeným způsobem chápat jako zobrazení f : Kn → Kn definované f (u1, . . . , un) := α aαuα kde uα = uα1 1 · · · uαn n V dimenzi n = 1 popisuje rovnost f (x) = 0 jen nejvýše konečně mnoho bodů v K. Ve vyšší dimenzi bude rovnost f (x1, . . . , xn) popisovat podmnožiny podobné, jako jsou křivky v rovině nebo plochy v trojrozměrném prostoru, mohou ale mít docela složité a samoprotínající se tvary. Např. množina zadaná rovnicí (x2 + y2 )3 − 4x2 y2 = 0 vypadá jako čtyřlístek. Pěkný obrázek dvourozměrné plochy dává tzv. Whitneyho deštník x2 − y2 z = 0, který kromě znázorněné části na obrázku obsahuje také celou přímku {x = 0, y = 0}. 492 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Obrázek byl vykreslen s pomocí parametrického popisu x = uv, y = v, z = u2 , ze kterého nejspíš snadno uhádneme i implicitní popis x2 − y2 z = 0. Další obrázek ukazuje tzv. Enneperovu plochu s parametrizací x = 3u+3uv2 −u3 , y = 3v+3u2 v−v3 , z = 3u2 −3v2 . Těžko si představit, jak z této parametrizace dopočítat ručně implicitní popis, přesto to budeme umět algoritmicky zvládnout eliminací proměnných u a v z těchto tří rovnic. Budeme k tomu ale muset vybudovat docela složitou teorii. Začneme jako obvykle formalizací objektů. Afinní variety Nechť f1, . . . , fs ∈ K[x1, . . . , xn]. Afinní varietou v Kn určenou polynomy f1, . . . , fn nazveme množinu V(f1, . . . , fs) = (a1, . . . , an) ∈ Kn , fi(a1, . . . , an) = 0; i = 1, . . . , s Afinní variety jsou například všechny kuželosečky, kvadriky a nadkvadriky singulární i regulární. Mnoho pěkných křivek či ploch můžeme snadno popsat jako afinní variety. Varieta určená více polynomy je pak průnik variet zadaných jednotlivými polynomy. Tedy například V(x2 +y2 −1, z) je kružnice se středem (0, 0, 0) a poloměrem jedna, ležící v rovině xy. Podobně V(xz, yz) je sjednocení přímky x = 0, y = 0 a roviny z = 0, protože pro právě pro body těchto dvou útvarů jsou oba polynomy xz, yz nulové. Vidíme na těchto příkladech, že není lehké s vypořádat s pojmem dimenze. Stačí zmíněná přímka navíc k rovině, aby naše varieta byla třírozměrná, nebo ji ještě budeme považovat za dvojrozměrnou s jistou anomálií? Následující přímočaré tvrzení si ověřte samostatně: 493 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Věta. Nechť V = V(f1, . . . , fs), W = V(g1, . . . , gt ) ⊆ Kn jsou afinní variety. Potom i V ∪W a V ∩W jsou afinní variety a platí V ∩ W = V(f1, . . . , fs, g1, . . . , gt ), V ∪ W = V(figj ) pro 1 ≤ i ≤ s, 1 ≤ j ≤ t. V následujících odstavcích se mimo jiné pokusíme zodpovědět otázky, které se v souvislosti s varietami bezprostředně nabízejí. A. Platí V(f1, . . . , fs) = ∅? B. Je V(f1, . . . , fs) konečná množina? C. Jak lze chápat pojem dimenze v případě variet? Všechny tyto problémy lze „rozumně“ řešit pro variety v oboru komplexních čísel (resp. pro všechna algebraicky uzavřená pole), pro čísla reálná je to komplikovanější a velmi zlé je to pro obecná pole. Například pro racionální čísla je ověření tvrzení V(xn + yn − zn ) = ∅ známo jako tzv. velká Fermatova věta. 10.52 11.28. Parametrizace. Pro některé ryze praktické operace s varietami je vhodné používat implicitní reprezentaci (tedy až dosud používané vyjádření). Např. zjištění, zda daný bod patří do variety, resp. do určité části prostoru jí vymezené, je při implicitním popisu docela snadné. Jindy je naopak daleko užitečnější vyjádření parametrické (např. jsme jej již použili při kreslení obrázků). Varieta V(x + y + z − 1, x + 2y − z − 3) je přímka (průnik dvou rovin). Řešíme-li systém x + y + z − 1 = 0 x + 2y − z − 3 = 0 dostaneme přímo parametrické vyjádření této přímky x = −1 − 3t y = 2 − 2t z = t Racionální parametrizace Definice. Racionální parametrickou reprezentací variety V(f1, . . . , fr) ⊆ Kn rozumíme racionální funkce r1, . . . , rn ∈ K(t1, . . . , ts) splňující následující podmínky • Je-li xi = ri(t1, . . . , ts) pro i = 1, 2, . . . , n pak (x1, . . . , xn) ∈ V(f1, . . . , fr) pro libovolná t1, . . . , ts. • V(f1, . . . , fr) je minimální afinní varieta obsahující takto dané body (x1, . . . , xn). Všimněme si, že při parametrizaci nepožadujeme popis všech bodů variety. To je podstatné, jak je vidět i na jednoduchém příkladu parametrizace kružnice v rovině, x = 2t 1 + t2 , y = −1 + t2 1 + t2 , kterou obdržíme tzv. stereografickou projekcí. (Ověřte si detailně!) Všimněme si, že skutečně dostaneme parametrizací 494 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY všechny body, kromě bodu (0, 1), ze kterého promítáme. Ten totiž není dosažitelný pro žádnou hodnotu parametru t. To není způsobeno naší nešikovností, z rozdílných topologických vlastností přímky a kružnice totiž vyplývá, že globální bijektivní racionální parametrizace existovat nemůže. V této souvislosti se nabízí další otázky. D. Existuje parametrizace dané variety, resp. lze ji nalézt? E. Naopak, umíme k parametricky zadané varietě najít její implicitní popis? Obecná odpověď na otázku D je záporná. V podstatě lze tvrdit, že většinu afinních variet parametrizovat nelze, respektive neexistuje algoritmus parametrizace implicitního popisu. Ty, u kterých se to podaří, se v angličtině nazývájí unirational, česky tedy patrně neiracionální. Na první pohled je zřejmé, že pro jednu a tutéž varietu existuje více implicitních, případně i parametrických popisů. Opomeneme-li parametrický popis, nejednoznačnosti implicitního jsou způsobeny reprezentací pomocí několika „generujících“ polynomů a zjevně máme velikou volnost v jejich volbě. 10.53 11.29. Ideály. Abychom se vyhnuli závislosti na jednotlivých zvolených rovnicích zadávajících varietu, budeme chtít uvažovat i všechny důsledky zadaných rovnic. To vede na následující algebraický pojem: Ideály Definice. Množinu I ⊆ K, kde K je komutativní okruh, nazveme ideálem, platí-li 0 ∈ I a zároveň f, g ∈ I ⇒ f + g ∈ I f ∈ I, h ∈ K ⇒ f · h ∈ I Ideály můžeme generovat podmnožinami, budeme používat značení I = a1, . . . , an . Tím máme na mysli I = i aibi, bi ∈ K . Množina generátorů může být také nekonečná, je-li generátorů jen konečný počet, říkame, že ideál je konečně genero- vaný. Ideál variety Pro varietu V = V(f1, . . . , fs) klademe I(V ) := f ∈ K[x1, . . . , xn], f (a1, . . . , an) = 0, ∀ (a1, . . . , an) ∈ V Lemma. Nechť f1, . . . , fs, g1, . . . , gt ∈ k[x1, . . . , xn] jsou polynomy. Pak platí (1) Jestliže f1, . . . , fs = g1, . . . , gt , pak V(f1, . . . , fs) = V(g1, . . . , gt ). 495 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY (2) I(V ) je ideál a platí f1, . . . , fs ⊆ I(V ), kde V = V(f1, . . . , fs). Důkaz. Jestliže nějaký bod (a1, . . . , an) patří varietě V(f1, . . . , fs), s v tomto bodě jistě nuluje i jakýkoliv po- lynom f = h1f1 + · · · + hsfs, tj. libovolný prvek ideálu I = f1, . . . , fs . Proto se v něm dle předpokladu nulují i všechny polynomy gi. Ověřili jsme tedy V(f1, . . . , fs) ⊆ V(g1, . . . , gt ). Opačná inkluze se dokáže stejně. Abychom ověřili druhé tvrzení, zvolme g, g ∈ I(V ), h ∈ K[x1, . . . , xn]. Pak pro každý bod a ∈ V platí (gh)(a) = 0 ⇔ gh ∈ I(V ) (g + g )(a) = 0 ↔ g + g ∈ I(V ) Je tedy I(V ) ideál v K[x1, . . . , xn]. Pro libovolný f = h1f1 + · · · + hsfs ∈ f1, . . . , fs a bod a ∈ V je samozřejmě také f (a) = 0, což ověřuje i dokazovanou inkluzi. Nejjednodušší příklady jsou triviální variety – jeden bod a celý afinní prostor: I {(0, 0, . . . , 0)} = x1, . . . , xn I(Kn ) = { 0} pro libovolné nekonečné pole K Inkluze opačná k druhé části věty obecně neplatí. Například varieta V(x2 , y2 ) má jediný bod – (0, 0). I(V ) je potom x, y ⊃ x2 , y2 . Jsou-li V, W ⊆ Kn variety, pak platí V ⊆ W ⇒ I(V ) ⊇ I(W) Neboli polynomy, které se nulovaly na nějaké varietě se nutně musí nulovat i na její podmnožině. Můžeme hned formulovat další přirozené problémy F. Je každý ideál I ∈ K[x1, . . . , xn] konečně generovaný? G. Lze algoritmicky zjistit, zda f ∈ f1, . . . , fs ? H. Jaký je přesný vztah mezi f1, . . . , fs a I V(f1, . . . , fs) ? 10.54 11.30. Dimenze 1. Podívejme se na polynomy v jedné proměnné x f = a0xn + a1xn−1 + · · · + an kde a0 = 0. Vedoucí člen polynomu definujeme jako LT(f ) := a0xn (označení pochází z anglického „leading term“). Zřejmě platí deg f ≤ deg g ⇐⇒ LT(f )|LT(g) Nechť K je pole a g nenulový polynomu. Víme, že každý polynom f ∈ K[x] lze jednoznačně psát jako f = q · g + r kde r = 0 nebo deg r < deg g. Jde ve skutečnosti o algoritmický postup, podíl q a zbytek r počítá následující algoritmus. 496 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY (1) q := 0, r := f (2) while r = 0 ∧ LT(g)|LT(r) (a) q := q + LT(r)/LT(g) (b) r := r − LT(r)/LT(g) · g Pro průchod cyklem platí invariant f = q · g + r, algoritmus tedy dává správný výsledek, pokud se zastaví. Stupeň r se každým průchodem zmenšuje, proto k zastavení nutně dojde. Dusledek. Nechť K je pole. Pak každý ideál v orkuhu polynomů K[x] je tvaru f . Důkaz. Uvažme jakýkoliv ideál I ⊆ K[x]. Je-li I = {0}, pak je generován nulovým polynomem. Jestliže I obsahuje nenulový polynom f , pak jistě obsahuje i polynom f minimálního stupně. Jistě je pak f ⊂ I. Pro jakýkoliv jiný polynom g ∈ I spočteme výsledek dělení se zbytkem, tj. g = qf + r. Zjevně je tedy qf ∈ I a proto i r ∈ I. Stupeň f byl ale minimální, takže nutně r = 0. Je tedy i g ∈ I a I = f . Ideály generované jediným prvkem se nazývají hlavní ideály. Okruhům, které mají vlastnost z posledního lematu říkáme okruh hlavních ideálů. Největší společný dělitel h = GCD(f, g) polynomů f a g lze opět spočítat algoritmicky: (1) h := f , s := g (2) while s = 0 (a) r := zbytek po dělění h/s (b) h := s (c) s := r Nechť f = q · g + r a h = GCD(f, g). Potom h|r, g a zároveň ∀p ∈ K[x]: p|r, g tedy p|f a p|h Odtud h je GCD(r, g). Triviálně GCD(h, 0) = h, proto algoritmus počítá správně GCD(f, g). Protože stupně r postupně klesají, algoritmus zastaví. Největší společný dělitel dvou polynomů tedy existuje. Je určen jednoznačně až na násobek skalárem. Dva různé GCD se totiž musí dělit navzájem a to je u polynomů možné právě v tomto případě. Největšího společného dělitele více než dvou polynomů definujeme takto: Je-li s > 2, potom GCD(f1, . . . , fs) := GCD f1, GCD(f2, . . . , fs) Lemma. Pro polynomy f1, . . . , fs platí GCD(f1, . . . , fs) = f1, . . . , fs . Důkaz. GCD(f1, . . . , fs) dělí všechny polynomy fi. Je tedy hlavní ideál GCD(f1, . . . , fs) obsažen v ideálu f1, . . . , fs . Naopak z Bezoutovy rovnosti okamžitě plyne inkluze opačná. Položili jsme několik otázek. Tady jsou odpovědi pro dimenzi 1: 497 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY • Protože V(f1, . . . , fs) = V(GCD(f1, . . . , fs)), problém prázdnosti variety se redukuje na problém existence kořene polynomu. • Ze stejného důvodu je varieta vždy konečnou množinou izolovaných bodů – kořenů GCD(f1, . . . , fs) s jedinou vyjímkou, kdy GCD(f1, . . . , fs) = 0; to nastane pouze v případě, že f1 = f2 = · · · = fs = 0. Pak je varietou celá množina K. • Pojem dimenze v tomto případě postrádá smysl, všechny variety mají coby diskrétní množiny bodů dimenzi nulo- vou. • Každý ideál je generovatelný jediným polynomem. • f ∈ f1, . . . , fs ⇐⇒ GCD(f1, . . . , fs)|f . • Označíme-li f := I(V(f1, . . . , fs)), pak f a GCD(f1, . . . , fs) se mohou lišit pouze násobností kořenů. 10.55 11.31. Monomiální uspořádání. Abychom mohli zobecnit dělení polynomů se zbytkem pro polynomy více proměnných, najdeme nejprve dobrý ekvivalent pojmů stupeň polynomu a vedoucí člen poly- nomu. Dělením se zbytkem polynomu f ∈ K[x1, . . . , xn] polynomy g1, . . . , gs chceme rozumět vyjádření f = a1g1 + · · · + asgs + r, kde vžádný člen zbytku r nebude dělitelný některým z vedoucích členů LT gi. Zkusme to s f = x2 y + xy2 + y2 , g1 = xy − 1 a g2 = y2 − 1. Prvním dělením získáme f = (x + y) · g1 + (x + y2 + y) LT(y2 − 1) nedělí x (vedoucí člen zbytku), a tak bychom teoreticky nemohli pokračovat dál. Přesuneme-li však toto x do zbytku, dostáváme teprve výsledek f = (x + y) · g1 + g2 + (x + y + 1) Zde již žádný člen zbytku není dělitelný žádným z LT(g1), LT(g2). Jak jsme ale vlastně určovali vedoucí členy? Uspořádání monomů Úplné (lineární) dobré (tj. každá neprázdná podmnožina má nejmenší prvek) uspořádání < na Nn splňující ∀α, β, γ ∈ Zn : α < β ⇒ α + γ < β + γ nazveme monomiálním uspořádáním na K[x1, . . . , xn]. Uspořádání na Nn indukuje uspořádání na monomech. Každý polynom lze však přeskládat jako klesající posloupnost monomů (na koeficienty teď nehledíme). Uspořádání se na polynomy rozšíříme „lexikograficky“, tedy větší je ten polynom, který má větší první monom, pokud tak nelze rozhodnou, bere se v potaz druhý monom atd. 498 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Následující tři definice zavádějí nejběžněji užívaná monomiální uspořádání. Všechna se opírají o předem dané uspořádání jednotlivých proměnných, standardně x1 > x2 > · · · > xn. Definice. Lexikografické uspořádání je takové lex β ⇐⇒ Nejlevější nenulový člen v α − β je kladný Gradované lexikografické uspořádání je takové grlex β ⇐⇒ |α| > |β| nebo |α| = |β| a zároveň α >lex β Gradované opačné lexikografické uspořádání je takové grevlex β ⇐⇒ |α| > |β| nebo |α| = |β| a zároveň nejpravější nenulový člen (α − β) < 0 Tedy x1 >grevlex x2 >grevlex · · · >grevlex xn, ale pokud x > y > z, pak x2 yz2 >grlex xy3 z, ale x2 yz2 lex, >grlex, >grevlex jsou skutečně monomiální uspořádání. 10.56 11.32. Dělení se zbytkem. Nechť f = α∈Nn aαxα je nenulový polynom v K[x1, . . . , xn] a < monomiální uspořádání. Pak definujeme: • Stupeň multideg f := max{α ∈ Nn , aα = 0} • Vedoucí koeficient LC f := amultideg f • Vedoucí monom LM f := xmultideg f • Vedoucí člen LT f := LC f · LM f Tyto pojmy jsou tedy pro polynomy více proměnných vesměs silně závislé na volbě konkrétního uspořádání. Lemma. Nechť f, g ∈ K[x1, . . . , xn] a uvažme monomiální uspořádání <. Pak (1) multideg(f · g) = multideg f + multideg g (2) f + g = 0 ⇒ multideg(f + g) ≤ max{multideg f, multideg g} Důkaz. Plyne okamžitě přímo z definic. Věta. Nechť < je monomiální a F = (f1, . . . , fs) s-tice polynomů v K[x1, . . . , xn]. Pak každý f ∈ K[x1, . . . , xn] lze vyjádřit jako f = a1f1 + · · · + asfs + r kde ai, r ∈ K[x1, . . . , xn] pro všechna i = 1, 2, . . . , s. Navíc r = 0 nebo r je lineární kombinací monomů, z nichž žádný není dělitelný kterýmkoli z LT f1, . . . , LT fs a pokud aifi = 0 pak multideg f ≥ multideg aifi pro každé i. Polynom r nazýváme zbytkem po dělení f/F. Důkaz. Věta neříká nic o jednoznačnosti výsledku. Následující algoritmus dává jedno možné řešení a je tedy důkazem platnosti věty. 499 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Nadále budeme výsledkem dělení se zbytkem chápat právě tento výstup pevně zvoleného algoritmu. (1) a1 := 0, . . . , as := 0, r := 0, p := f (2) while p = 0 (a) i := 1 (b) d := false (c) while i ≤ s ∧ not d (i) if LT fi|LT p ai := ai + LT p/LT fi p := p − (LT p/LT fi) · fidecdg1 d := true (ii) else i := i + 1 (d) if not d (i) r := r + LT p (ii) p := p − LT pdecdg2 Při každém průchodu vnějším cyklem se právě jednou provede právě jeden z příkazů 2(c)i, 2(d)ii, a tedy stupeň p klesne. Proto algoritmus skončí. Platí invariant f = a1f1 + · · · + p + r a přitom každý člen každého ai je podílem LT p/LT fi z nějakého okamžiku. Proto stupeň těchto členů je menší než stupeň p v daném okamžiku a ten je nejvýše roven stupni f . Dohromady stupeň každého aifi je menší nebo roven stupni f . V okruhu K[x1, . . . , xn] platí pouze implikace f = a1f1 + · · · + asfs + 0 ⇒ f ∈ f1, . . . , fs Obrácení obecně pro naše dělení se zbytkem neplatí. Uvažujme f = xy2 − x, f1 = xy + 1, f2 = y2 − 1. Potom algoritmus dělení dá f = y(xy + 1) + 0(y2 − 1) + (−x − y) ale přitom evidentně f = x(y2 − 1), a tedy f ∈ f1, f2 . 10.58 11.33. Monomiální ideály. Ideál I ⊆ K[x1, . . . , xn] nazýváme monomiální, jestliže existuje množina multiindexů α ⊆ Nn taková, že I je generován právě všemi monomy xα s α ∈ A. To znamená, že všechny polynomy v I jsou tvaru α∈A hαxα , kde hα ∈ k[x1, . . . , xn]. Zřejmě pro monomiální ideál I platí, že xβ ∈ I, právě když existuje α ∈ A takové, že xα dělí xβ . Lemma. Nechť I ⊆ K[x1, . . . , xn] je monomiální ideál, f ∈ K[x1, . . . , xn] polynom. Pak následující tvrzení jsou ekvivalentní (1) f ∈ I (2) Každý člen polynomu f je prvkem I. (3) Polynom f je lineární kombinací monomů z I s koeficienty z k. Důkaz. Implikace (3) ⇒ (2) ⇒ (1) jsou zřejmé. Zbývá ukázat (1) ⇒ (3). Zapišme si polynom f = α aαxα , kde aα ∈ K. Z předpokladu f ∈ I vyplývá, že lze také vyjádřit f = β∈A hβxβ , kde xβ ∈ I a hβ ∈ K[x1, . . . , xn]. 500 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Každý člen aαxα se musí rovnat některému členu z druhé rovnosti. Jistě tedy každý člen aαxα polynomu f můžeme vyjádřit jako součet výrazů d xβ+δ , kde d ∈ K, xβ ∈ I. Pak ale také xα ∈ I, a tedy platí (3). Dusledek. Dva monomiální ideály splývají právě tehdy, když obsahují stejné monomy. 10.59 11.34. Věta (Dicksonovo lemma). Každý monomiální ideál I = xα , α ∈ A ⊆ k[x1, . . . , xn] lze psát ve tvaru I = xα1 , . . . , xαs , kde α1, . . . , αs ∈ A. Důkaz. Důkaz provedeme indukcí podle počtu proměnných. V případě n = 1 je I ⊆ K[x], I = xα , α ∈ A ⊆ N . Množina všech exponentů v A má jistě minimum a definujeme β := min A. Potom zřejmě xβ dělí všechny monomy xα s α ∈ A a tedy také I = xβ . Uvažujme nyní n > 1 a předpokládejme, že pro menší počty proměnných tvrzení platí. Pro přehlednost si označíme proměnné jako x1, . . . , xn−1, y a monomy budeme psát ve tvaru xα ym , kde α ∈ Nn−1 , m ∈ N. Množinu monomů xβ s β ∈ A budeme značit IA. Předpokládejme, že I ⊆ K[x1, . . . , xn−1, y] je monomiální a definujme J ⊆ K[x1, . . . , xn−1] následovně J := xα , ∃m ∈ N, xα ym ∈ IA . Zřejmě je J monomiální ideál v n − 1 proměnných a tedy podle indukčního předpokladu lze psát J = xα1 , . . . , xαs . Dále z definice J vyplývá, že existují taková minimální mi ∈ N, že xαi ymi ∈ IA. Označme tedy m := max{mi} a definujme analogicky systém ideálů Jk ⊆ K[x1, . . . , xn−1] pro 0 ≤ k ≤ m − 1 Jk := xβ , xβ yk ∈ IA Opět všechny Jk splňují indukční předpoklad a tedy je lze vyjádřit Jk = xαk,1 , . . . , xαk,sk . Zbývá ukázat, že I je generovaný právě zkonstruovanou konečnou množinou 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 Uvažujme tedy libovolný monom xα yp ∈ IA. Nastane jeden ze dvou případů • p ≥ m. Potom jistě xα ∈ J, a tedy některý z xα1 ym , . . . , xαs ym dělí xα yp . • p < m. Potom analogicky xα ∈ Jk a některý z xαk,1 yk , . . . , xαk,sk yk dělí xα yp . Podle předchozího lemmatu lze každé f ∈ I vyjádřit jako lineární kombinaci monomů z IA, ty jsou již dělitelné některým 501 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY z našich generátorů, proto f patří do ideálu jimi generovaného. Proto I je jeho podmnožinou. Opačná inkluze je zcela triviální a důkaz Dicsonova lematu je hotov. 10.60 11.35. Hilbertova věta. Nyní již máme nachystáno vše potřebné pro diskusi pěkných bazí ideálů v okruzích polynomů. Hlavní myšlenkou je maximální využití informací o vedoucích členech prvků v bázi a v celém ideálu. Je-li I ⊆ K[x1, . . . , xn] nenulový, označíme LT I := {axα , ∃f ∈ I : LT f = axα } Zřejmě LT I je monomiální ideál, proto podle Dicksonova lemmatu lze psát LT I = LT g1, . . . , LT gs pro nějaká vhodná g1, . . . , gs ∈ I. Věta. Každý ideál I ∈ K[x1, . . . , xn] je konečně generovaný. Důkaz. Pokud je I = {0}, je tvrzení triviální. Uvažujme tedy I = {0}. Podle Dicksonova lematu a předchozí poznámky existují taková g1, . . . , gs ∈ I, že LT I = LT g1, . . . , LT gs . Zřejmě g1, . . . , gs ⊆ I. Vezměme libovolné f ∈ I a proveďme dělení se zbytkem s-ticí g1, . . . , gs. Dostáváme f = a1g1 + · · · + asgs + r, kde žádný člen r není dělitelný LT g1, . . . , LT gs. Protože r = f − a1g1 − · · · − asgs, platí r ∈ I, a tedy také LT r ∈ LT I. Zřejmě tedy LT r ∈ LT I . Připusťme, že r = 0. Protože LT I je monomiální, musí být LT r dělitelný některým z jeho generátorů, tj. LT g1, . . . , LT gs. To je ovšem spor s výsledkem algoritmu dělení. Proto r = 0 a I je generovaný g1, . . . , gs. Gröbnerovy báze ideálů 10.61 11.36. Definice. Konečná báze g1, . . . , gs ideálu I ⊆ k[x1, . . . , xn] se nazývá Gröbnerova, jestliže platí LT I = LT g1, . . . , LT gs . Báze použitá v důkazu Hilbertovy věty byla Gröbnerova. Dusledek. Každý ideál I ⊆ K[x1, . . . , xn] má Gröbnerovu bázi. Přitom každá množina polynomů g1, . . . , gs ∈ I splňující LT I = LT g1, . . . , LT gs je Gröbnerovou bází ideálu I. Ukažme smysl předchozích obecných výsledků na nejjednodušším případě polynomů stupně jedna s lexikografickým uspořádáním: Označme generátory fi = j ai,j xj + ai,0. Uvažujme matici A = (ai,j ), kde i = 1, . . . , s a j = 0, . . . , n a aplikujme na ni Gausovu eliminaci. Získláme B = (bi,j ) ve schodovitém tvaru, z ní navíc vypustíme nulové řádky. Máme novou bázi g1, . . . , gt , kde t ≤ s. 502 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Vzhledem k provedeným úpravám je každé fi vyjádřitelné jako lineární kombinace g1, . . . , gt , a tedy f1, . . . , fs = g1, . . . , gt Ověříme si, že takto získané polynomy g1, . . . , gt jsou Gröbnerovou bází: Bez újmy na obecnosti předpokládejme, že proměnné jsou značeny tak, že LM gi = xi pro i = 1, . . . , t. Libovolný f ∈ I lze psát f = h1f1 + · · · + hsfs = h1g1 + · · · + ht gt Chceme, aby LT f ∈ LT g1, . . . , LT gt , tj. LT f má být dělitelný některým z x1, . . . , xt . Předpokládejme, že f je pouze v proměnných xt+1, . . . , xn. Pak ale h1 = 0, protože x1 je vzhedem ke schodovitosti B pouze v g1. Analogickým postupem získáme h2 = · · · = ht = 0, a tedy f = 0. Dokázali jsme sice existenci nadějných zvláštních bází, zatím je ale neumíme algoritmicky konstruovat. K tomu se dostaneme v následujících odstavcích. 10.62 11.37. Věta. Nechť G = {g1, . . . , gt } je Gröbnerova báze ideálu I ⊆ K[x1, . . . , xn] a f je polynom v K[x1, . . . , xn]. Pak existuje právě jedno r = α aαxα ∈ K[x1, . . . , xn] s těmito vlastnostmi (1) Žádný člen r není dělitelný žádným z LT g1, . . . , LT gt , tj. ∀α∀i : LT gi | aαxα . (2) ∃g ∈ I : f = g + r Důkaz. Algoritmus pro dělení se zbytkem dá f = a1g1 + · · · + at gt + r, kde r splňuje podmínku (1). Za g si zvolme a1g1 +· · ·+at gt , které samozřejmě patří do I. Zbývá dokázat jednoznačnost. Předpokládejme f = g + r = g + r , kde r = r . Zřejmě platí r − r = g − g ∈ I. Protože G je Gröebnerova báze, je LT(r − r ) dělitelný některým z LT g1, . . . , LT gt . Máme přitom jen dvě možnosti • LM r = LM r . Pak ten s vyšším stupněm musí být dělitelný některým z vedoucích členů LT g1, . . . , LT gt , což je spor s podmínkou (1). • LM r = LM r a zároveň LC r = LC r . Potom ale oba mnomy LM r a LM r musí být dělitelné některým z LT g1, . . . , LT gt , což je opět spor. Proto tedy LT r = LT r a induktivní úvahou odtud plyne r = r . Předchozí věta zobecňuje dělení se zbytkem, kde na místě dělitele vystupuje ideál. V případě jedné proměnné nebylo co zobecňovat, protože každý ideál byl generovaný jedním polynomem. Zajímá-li nás pouze zbytek, věta navíc říká, že nezáleží na pořadí polynomů v Gröbnerově bázi. Proto má smysl zavést značení f G pro zbytek po dělení f/G, pokud G = (g1, . . . , gs) je Gröbnerova báze. 503 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Dusledek. Nechť G = {g1, . . . , gt } je Gröbnerova báze ideálu I ⊆ K[x1, . . . , xn] a f je polynom v K[x1, . . . , xn]. Pak je libovolný polynom f prvkem ideálu I, právě když je zbytek po dělení f/G nulový. 10.63 11.38. Syzygy. Dalším krokem bude nalezení dostatečné „testovací množiny“ polynomů z daného ideálu, které je třeba prověřit dělením se zbytkem, abychom mohli usoudit, že je uvažovaný systém generátorů již Gröbnerovou bazí. Pro α = multideg f a β = multideg g uvažme γ := (γ1, . . . , γn) kde γi = max{αi, βi} Monom xγ nazýváme nejmenším společným násobkem (least common multiple) monomů LM f a LM g a zavádíme označení LCM(LM f, LM g) := xγ . Výraz S(f, g) := xγ LT f · f − xγ LT g · g nazýváme S-polynomem (nebo také syzygy, neboli spřežení) polynomů f, g. Jedná se o nástroj k eliminaci vedoucích členů, Gaussova eliminace je speciálním případem tohoto postupu pro polynomy stupně jedna. Narozdíl od ní ale může dojít ke zvýšení stupně, i když původní vedoucí členy odstraní. Vezměme například f = x3 y2 −x2 y3 +x, g = 3x4 y+y2 , tedy polynomy stupně 5 v R[x, y] a uspořádání lex x2 >lex · · · . Potom pro každé p = 0, . . . , n je Gp := G ∩ K[xp+1, . . . , xn] Gröbnerovou bází ideálu Ip. Jestliže je G minimální, resp. redukovaná, Gröbnerova báze, pak Gp je opět báze minimální resp. redukovaná. Důkaz. Bez újmy na obecnosti můžeme uvažovat Gp = {g1, . . . , gr}. Protože G ⊆ I, je i Gp ⊆ Ip. Inkluze Gp ⊆ Ip platí triviálně. Dokážeme tedy ikluzi opačnou. Pro libovolný polynom f ∈ Ip bychom rádi ověřili, že f = h1g1 + · · · + hrgr. Provedeme za tím účelem dělení se zbytkem původní Gröbnerovou bází G. Protože je také f ∈ I, platí f G = 0, a tedy f = h1g1 + · · · + hrgr + hr+1gr+1 · · · + hmgm Každý z polynomů gr+1, . . . , gm musí obsahovat nějakou z proměnných x1, . . . , xp, jinak by byl prvkem Gp. Vzhledem k vlastnostem lexikografického uspořádání takovou proměnnou obsahují i LT gr+1, . . . , LT gm. Uvědomíme-li si postup algoritmu pro dělení se zbytkem a skutečnost, že v f není žádný monom obsahující některou z x1, . . . , xp, musí být hr+1 = · · · = hm = 0. Ověřili jsem proto f ∈ Gp . Dokázali jsme nejen požadovanou inkluzi, ale i fakt, že dělení f/G dopadne na Ip stejně jako f/Gp. Pro 1 ≤ i < j ≤ r uvažujme S-polynomy S(gi, gj ). Platí S(gi, gj ) Gp = S(gi, gj ) G = 0 a tedy Gp je Gröbnerova báze ideálu Ip. Tvrzení o minimalitě nebo redukovanosti báze je zřejmé z definic těchto pojmů. 510 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Jediná vlastnost lexikografického uspořádání, kterou jsme použili v důkazu, je tvrzení, že pokud se některé proměnné objevují v polynomu f , pak se objevují v jeho vedoucím členu. To je ovšem podstatně slabší požadavek, než definice lexikografického uspořádání. Proto lze při skutečných implementacích používat jakékoliv uspořádání, které bude zajišťovat tuto vlastnost. Dosáhne se tak většinou efektivnějších výpočtů, protože čisté lexikografické uspořádání zpravidla vede k nepříjemnému nárůstu stupňů polynomů. 10.68 11.44. Implicitní popis parametrizovaných variet. Z předchozí věty lze docela snadno odvodit algoritmus pro nalezení implicitního popisu variet zadaných pomocí polynomiální parametrizace. Nebudeme se věnovat detailní diskusi, protože nemáme k dispozici všechny nástroje pro práci s nejménšími varietami obsahujícími body zadané parametrizací. Zústaneme proto na úrovni poznámek. Jestliže je naše parametrizace variety dána polynomiálními vztahy x1 = f1(u1, . . . , uk), . . . , xn = fn(u1, . . . , uk), spočteme redukovanou Gröbnerovu bázi ideálu x1 − f1, . . . , xn − fn v lexikografickém uspořádání, kde ui > xj pro všechna i,j. Z této báze dostaneme redukovanou Gröbnerovu bázi eliminačního ideálu Ik a to je přesně hledaný ideál a jeho implicitní popis. Ve skutečnosti nám pro výpočet stačí takové uspořádání, které zaručí převahu všech ui nad xj , aby se algoritmem pro výpočet Gröbnerovy báze eliminovala ui, jinak může být uspořádání libovolné. Máme tak naději dosáhnout efektivnějšího výpočtu, než s čistým lexikografickým uspořádá- ním. Jako příklad si uveďme už dříve zobrazenou varietu v R3 nazývnou Enneperova plocha. Její parametrický popis byl x = 3u + 3uv2 − u3 , y = 3v + 3u2 v − v3 , z = 3u2 − 3v2 . Aplikace eliminační procedury (např. v systému MAPLE za použití gbasis s uspořádáním plex) dá odpovídající implicitní popis, tj. rovnici s jediným polynomem devátého stupně: −59049z − 104976z2 − 6561y2 − 72900z3 − 18954y2 z − 23328z4 +32805z2 x2 +14580z3 x2 +3645z4 x2 −1296y4 z− 16767y2 z2 − 6156y2 z3 − 783y2 z4 + 39366zx2 + 19683x2 − 1296y4 − 2430z5 + 432z6 + 108z7 + 486z5 x2 − 432y4 z2 + 54y2 z5 + 27z6 x2 − 48y4 z3 + 15y2 z6 − 64y6 − z9 . Když je naše parametrizace racionální, tj. xi = fi(t1, . . . , tm) gi(t1, . . . , tm) , asi nás hned napadne dosadit do předchozí věty ideál x1g1 − f1, . . . , xngn − fn . To ale většinou nefunguje dobře. Například uvažujme x = u2 v y = v2 u z = u. 511 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Dostali bychom I = vx − u2 , uy − v2 , z − u a po eliminaci I2 = z(x2 y − z3 ) . Správný výsledek je ale jenom V(x2 y − z3 ), tedy náš postup přidal navíc celou rovinu. Problém je v tom, že zahrnujeme i celou varietu nulových bodů jmenovatelů v parametrizacích jednotlivých proměnných, W = V(g1, . . . , gn). Raději tedy parametrizaci F chápejme jako zobrazení F : (Kk − W) → Kn . Pro implicitizaci pak použijeme ideál I = g1x1 − fj , . . . , gnxn − fn, 1 − g1 · · · gny ⊆ K[y, t1, . . . , tm, x1, . . . , xn], kde si navíc pomáháme dodatečnou proměnnou y. Potom lze ukázat, že V (Ik+1) je minimální afinní varieta obsahující F(Km − W). 4. Uspořádané množiny a Booleovská algebra Tak jako jsme z vlastností čísel nebo symetrií objektů abstrahovali podstatné axiomy a dostali jsme daleko šířeji použitelné nástroje pro úvahy v linerární algebře, při diskusi grup symetrií a jejich akcí, studium okruhů polynomů atd. Nyní budeme postupovat obdobně a okamžitě uvidíme, že jen docela drobnou změnou základních vlastností dostaneme na první pohled úplně jiné objekty. To co zůstane podobné je algebraická práce se symboly zastupujícími velice rozmanité objekty a tím pádem i docela univerzální použitelnost výsledků. Za východisko si vezmeme základní operace s množinami, tj. jejich sjednocení, průnik a vztahy inkluze a naším prvním cílem bude uvést tyto operace do souvislosti s výrokovou logikou (tj. formalizovanými postupy pro vyjadřování výroků a vyhodnocování jejich pravdivosti). 10.21 11.45. Množinová algebra. S každou množinou M máme k dispozici také množinu K = 2M všech jejích podmnožin a na ní operace ∨ : K × K → K sjednocení množin a ∧ : K × K → K průniku množin. To jsou dvě binární operace, které jsme dosud značili ∪ a ∩. Dále máme ke každé množině A ∈ K také její množinu doplňkovou A = K \ A, což je další unární operace. Konečně máme „největší objekt“, tj. celou množinu M, který je neutrální vůči operaci ∧ a který proto budeme v této souvislosti označovat jako 1, a obdobně se chová prázdná množina ∅ ∈ K vůči operaci ∨. Tu budeme v této souvislosti značit jako 0. Na množině K všech podmnožin v M můžeme velmi snadno ověřit pro všechny prvky A, B, C následující vlastnosti (již jsme definovali význačné prvky 0 = ∅ a 1 = M a 512 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY unární operaci vzetí doplňku A k podmnožině A): A ∧ (B ∧ C) = (A ∧ B) ∧ C,puvodnipuvodni (1) A ∨ (B ∨ C) = (A ∨ B) ∨ C,(2) A ∧ B = B ∧ A, A ∨ B = B ∨ A,(3) A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C),(4) A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C),(5) existuje 0 ∈ K tak, že A ∨ 0 = A,(6) existuje 1 ∈ K tak, že A ∧ 1 = A,(7) A ∧ A = 0, A ∨ A = 1.(8) Porovnejme si tyto vlastnosti s vlastnostmi okruhů: První dvě z nich, tj. (1) a (2) říkají, že obě operace ∧ a ∨ jsou asociativní. Vlastnost (3) konstatuje komutativitu obou operací. Až potud je tedy vše jako u číslených oborů a operací sčítání a násobení. Zásadní změnou jsou ale další dvě vlastnosti (4) a (5), protože ty vyžadují jak distributivitu operace ∨ vůči průniku ∧, tak naopak. To pochopitelně u sčítání a násobení čísel nejde — máme tam pouze distributivitu sčítání vůči násobení, ale ne naopak. Poslední tři vlastnosti (6) – (8) konstatují existenci neutrálních prvků vůči oběma operacím, ale také existenci obdoby k „inverzím“ ke všem prvkům (ale všimněme si, že průnikem s komplementem chceme dostat neutrální prvek ke sjednocení a naopak, tedy odlišně od vzetí inverzí v okruzích). Jistě nás nepřekvapí, když zachvíli uvidíme, že takto silně provázané vlastnosti dvou různých operací nemůže mít příliš mnoho objektů. Booleovské algebry Definice. Množině K spolu s dvěmi binárními operacemi ∧ a ∨ a jednou unární operací splňující vlastnosti (1)–(8) říkáme Booleovská algebra. Operaci ∧ budeme říkat infimum (případně sjednocení, anglicky často také meet), operaci ∨ budeme říkat supremum (případně průnik, anglicky také join). Prvku A se říká doplněk k prvku A. Všimněme si, že axiomy Booleovské algebry jsou zcela symetrické vůči záměně operací ∧ a ∨, společně se záměnou prvků 0 a 1. Důsledkem tohoto faktu je, že jakékoliv tvrzení, které odvodíme z axiomů, má také platné duální tvrzení, které vznikne z prvého právě záměnou všech výskytů ∧ za ∨ a naopak a stejně tak všech výskytů 0 a 1. Hovoříme o principu duality. 10.21a 11.46. Vlastnosti Booleovských algeber. Jako obvykle si hned odvodíme několik elementárních důsledků axiomů. Zejména si povšimněme, že tak dokážeme u speciálního případu Booleovské algebry všech podmnožin v dané množině M elementární vlastnosti známé z množinové algebry. Např. je doplněk k A ∈ K určen svými vlastnostmi jednoznačně. V obecném pohledy však toto pozorování říká, 513 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY že máme-li dáno (K, ∧, ∨), může existovat nejvýše jedna unární operace , se kterou dostaneme Booleovskou algebru (K, ∧, ∨, )). Skutečně, pokud B a C ∈ K splňují vlastnosti A (tj. poslední axiom (8) v definici výše), platí B = B ∨ 0 = B ∨ (A ∧ C) = (B ∨ A) ∧ (B ∨ C) = 1 ∧ (B ∨ C) = B ∨ C a stejně také spočteme C = C ∨ B. Je tedy nutně B = C. Všimněme si, že použitím tohoto výsledku na prvky 1 a 0, společně s jejich definicí, okamžitě dostáváme jednoznačnost pro tyto výjimečné prvky v libovolné Booleovské algebře (promyslete si podrobně!). Vlastnosti v následujícím tvrzení mají svá zavedená jména v množinové algebře: vlatnosti (2) se říká absorpční zákony, vlastnosti (3) popisují idempotentnost operací ∧ a ∨ a rovnosti (4) jsou známy jako De Morganova pravidla. Tvrzení. V každé Booleovské algebře (K, ∧, ∨, ) platí pro všechny prvky v K (1) A ∧ 0 = 0, A ∨ 1 = 1 (2) A ∧ (A ∨ B) = A, A ∨ (A ∧ B) = A (3) A ∧ A = A, A ∨ A = A (4) (A ∧ B) = A ∨ B , (A ∨ B) = A ∧ B (5) (A ) = A. Důkaz. Podle principu duality potřebujeme z každého z duálních tvrzení na jednotlivých řádcích dokázat pouze jedno. Počítejme s využitím axiomů: Začneme s vlastností (3) A = A ∧ 1 = A ∧ (A ∨ A ) = (A ∧ A) ∨ 0 = A ∧ A. Nyní už umíme snadno (1) A ∧ 0 = A ∧ (A ∧ A ) = (A ∧ A) ∧ A = A ∧ A = 0 a pak je snadné i (2) A ∧ (A ∨ B) = (A ∨ 0) ∧ (A ∨ B) = A ∨ (0 ∧ B) = A ∨ 0 = A. K důkazu De Morganových pravidel stačí ověřit, že A ∨ B má vlastnosti doplňku k A ∧ B, pak to totiž bude doplněk dle úvahy výše. S využitím (1) spočteme (A ∧ B) ∧ (A ∨ B ) = ((A ∧ B) ∧ A ) ∨ ((A ∧ B) ∧ B ) = (0 ∧ B) ∨ (A ∧ 0) = 0. Obdobně, s použitím (2) dostáváme (A ∧ B) ∨ (A ∧ B ) = (A ∨ (A ∨ B )) ∨ (B ∨ (A ∨ B )) = (1 ∨ B ) ∧ (1 ∨ A ) = 1. Konečně, přímo z definice je A ∧ A = 0 a A ∨ A = 1, má proto A požadované vlastnosti doplňku k A a je tedy A = (A ) . 514 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY 10.21b 11.47. Příklady Booleovských algeber. Nejmenší zajímavá algebra je množina všech podmnožin jednoprvkové množiny M. Ta má právě dva prvky 0 = ∅ a 1 = M. Operace ∧ a ∨ v tomto případě splývají s násobením a sčítáním v okruhu abytkových tříd Z2, proto budeme nadále hovořit o Booleovské algebře Z2. Podobně jako u vektorových prostorů a okruhů můžeme algebraickou strukturu Booleovské algebry přenášet na prostory funkcí, jejichž obor hodnot Booleovskou algebrou je. Skutečně, pro množinu všech funkcí S = {f : M → K} zmnožiny M do Booleovské algebry (K, ∧, ∨, ) definujeme potřebné operace a vybrané prvky 0 a 1 na S jako funkce v argumentu x ∈ M takto: (f1 ∧ f2)(x) = (f1(x)) ∧ (f2(x)) ∈ K (f1 ∨ f2)(x) = (f1(x)) ∨ (f2(x)) ∈ K (1)(x) = 1 ∈ K, (0)(x) = 0 ∈ K (f ) (x) = (f (x)) ∈ K. Ověření, že tyto nové operace skutečně zadávají Booleovskou algebru je zcela přímočaré a jednoduché. Připoměňme, že všechny podmnožiny dané množiny M lze interpretovat jako zobrazení M → Z2, když na jedničku zobrazíme právě body vybrané podmnožiny. Pak skutečně můžeme sjednocení a průnik definovat výše uvedeným způsobem — např. o každém bodu x ∈ M rozhodujeme u (A ∧ B)(x) zda patří do A a zda patří do B a vezmeme sjednocení výsledků v Z2, tj. výsledek bude 1, právě když x padne do sjednocení. 10.22 11.48. Výroková logika. V předchozích odstavcích jsme použili symboliku, kterou je často rozumné interpretovat tak, že z prvků A, B, . . . ∈ K tvoříme „slova“ pomocí operací ∨, ∧, a závorek vyjasňujících v jakém pořadí a na jaké argumenty jsou operace aplikovány. Samotné axiomy Booleovských algeber a jejich důsledky pak říkají, že velice často různá slova dávají stejnou hodnotu výsledku v K. V případě množiny všech podmnožin K = 2M je to zřejmé – prostě jde o rovnost podmnožin. Nyní uvedeme stručně jinou podobnou souvislost. Budeme pracovat opět se slovy jako výše, interpretujeme je ale jako tvrzení složené z elementárních výroků A, B, . . . a logických operací AND (binární operace ∧), OR (binární operace ∨) a negace NOT (unární operace ). Taková slova nazýváme výroky a přiřazujeme jim pravdivostní hodnotu v závislosti na pravdivostní hodnotě jednotlivých elementárních argumentů. Pravdivostní hodnotu přitom bereme jako prvek z triviální Booleovy algebry Z2, tedy buď 0 nebo 1. Pravdivostní hodnota výroku je plně určena přiřazením hodnot pro nejjednoduší výroky A ∧ B, A ∨ B a A , tj. A ∧ B je pravdivé pouze, když jsou oba výroky A a B pravdivé, A ∨ B 515 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY je nepravdivé pouze. když jsou oba výroky nepravdivé a A má opačnou hodnotu než A. Výrok obsahující n elementárních výroků tedy představuje funkci (Z2)n → Z2 a dva výroky nazýváme logicky ekvivalentní, jestliže zadávají stejnou funkci. V předchozím příkladu jsme již ověřili, že na množině tříd logicky ekvivalentních výroků je dána struktura Booleovy algebry. Nutně tedy pro výrokovou logiku bude v tomto smyslu platné vše, co dokážeme pro obecné Booleovy algebry. Stručně si proberme, jak vypadají obvyklé další jednoduché výroky ve výrokové logice jakožto prvky Booleovy algebry (tj. reprezentujeme vždy naším výrazem třídu výroků ekvivalentních): Implikaci A ⇒ B dostaneme jako A ∨ B, ekvivalenci A ⇔ B odpovídá (A ∧ B) ∨ (A ∧ B ). Dále vylučovací OR, neboli XOR, je dáno jako (A ∧ B ) ∨ (A ∧ B), negace NOR operace OR je vyjádřena jako A ∧B a negace NAND operace AND je dána jako A ∨ B . Konečně tautologie je dána pomocí libovolného elementárního výroku jako A ∨ A . Všimněme si také, že XOR odpovídá v množinové algebře symetrickému rozdílu množin. 10.23 11.49. Přepínače jako Booleova algebra. Přepínač je pro nás černá skříňka, která má jen dva stavy, buď je zapnut (a signál prochází) nebo naopak vypnut (a signál neprochází). B A B A Jeden nebo více přepínačů zapojujeme do sítě sériově nebo paralelně. Sériové zapojení je popsáno pomocí binární operace ∧, paralelní je naopak ∨. Unární operace A zadává přepínač, který je vždy v opačné poloze než A. Každé konečné slovo vytvořené pomocí přepínačů A, B, . . . a operací ∧, ∨ a umíme převést na obrázek, který bude představovat systém přepínačů propojených dráty a zcela obdobně jako v minulém odstavci nám každá volba poloh jednotlivých přepínačů zadá hodnotu „zapnuto/vypnuto“ pro celý systém. Opět se snadno krok po kroku ověří platnost základních axiomů Booleových algeber pro náš systém. Na následujícím obrázku je ilustrován jeden z axiomů distributivity. =A A A B C B C Propojení bez přepínače odpovídá prvku 1, koncové body bez propojení (nebo sériové zapojení A a A ) dává prvek 0. Nakreslete si obrázky pro všechny axiomy Booleovské algebry a ověřte si je! 10.24 11.50. Dělitelé. Dalším přirozeným příkladem Booleovské algebry může být systém dělitelů přirozeného čísla nebo polynomu. 516 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Začněme trochu obecněji a zvolme pevně takové přirozené číslo p ∈ N nebo polynom p ∈ K[x1, . . . , xs] nad oborem integrity K s jednoznačným rozkladem. Za nosnou množinu Dp bereme množinu všech dělitelů q našeho p. Pro dva takové dělitele definujeme q ∧ r jako největší společný dělitel prvků q a r, q ∨ r je nejmenší společný násobek. Dále definujeme význačný prvek 1 ∈ Dp jako naše číslo nebo polynom p a neutrálním prvkem 0 vůči supremu na Dp je jednička v N, resp. 1 ∈ K ⊂ K[x1, . . . , xs]. Unární operaci definujeme pomocí dělení: q = p/q. Lemma. Množina Dp spolu s výše uvedenými operacemi ∧, ∨ a je Booleovská algebra, právě když rozklad p na nerozložitelné faktory neobsahuje žádné kvadráty (tj. v jednoznačném rozkladu p = q1 . . . qn na nerozložitelné faktory jsou všechna qi po dvou různá). Důkaz. Ověření axiomů je vcelku snadné, projdeme jeden po druhém a budeme zkoumat, kdy je zapotřebí nešeho požadavku na nepřítomnost kvadrátů v rozkladu. Největší společný dělitel konečného počtu čísel nebo polynomů nezávisí na pořadí, ve kterém jej počítáme. Stejně tak pro nejmenší společný násobek. To odpovídá axiomům (1) a (2) v 11.45. Komutativita, tj. axiom (3) je zcela zřejmá. Pro tři libovolné prvky a, b, a c můžeme bez újmy na obecnosti psát jejich rozklad ve tvaru a = q p1 1 . . . q ps s , b = qm1 1 . . . qms s a c = qk1 1 . . . qks s , kde připouštíme i mocniny 0 a všechny prvky qj jsou po dvou nesoudělné. Prvek a ∧ b ∈ Dp je tedy prvek s rozkladem, ve kterém se objeví všechna společná qi v mocnině, která bude minimem z mocnin v a a b. Naopak a ∨ b bude mít rozklad, ve kterém se objeví všechny členy z rozkladů a a b a to s mocninou, která bude tou větší z mocnin příslušného faktoru v a a b. Z této úvahy nyní snadno plynou distributivní zákony (4) a (5) z 11.45. Problém nemáme ani s existencí prvků 0 a 1, které jsme přímo definovali a zjevně splňují axiomy (6) a (7). Případná existecne kvadrátů v rozkladech ale znemožní určení doplňku. Např. v D12 = {1, 2, 3, 4, 6, 12} nelze 6 ∧ 6 = 1 dosáhnout, protože má 6 netriviálního společného dělitele se všemi ostatními prvky v D12 mimo jedničku, ta ovšem nesplňuje 6 ∨ 1 = 12. Pokud ovšem nejsou v rozkladu čísla nebo polynomu p kvadráty, definujeme doplněk pomocí dělení jako q = p/q a snadno ověříme potřebné vlastnosti z axiomů (6)–(8). 10.25 11.51. Částečná uspořádání. K Booleovským algebrám teď půjdeme z jiné strany. Základní strukturou pro nás bude pojem uspořádání. Vzpomeňme na definici uspořádání jakožto reflexivní, antisymetrické a tranzitivní relace ≤ na množině K. Taková relace obecně neříká o každé dvojici a, b ∈ K jestli je a ≤ b nebo b ≤ a (takové uspořádání se nazývá úplné uspořádání nebo dobré uspořádání). Často v našem případě obecného uspořádání proto hovoříme také o částečném uspořádání a množina (K, ≤) vybavená 517 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY částečným uspořádáním se nazývá poset (z anglického „partially ordered set“). Takové uspořádání je zejména vždy na množině K = 2M všech podmnožin množiny M prostřednictvím inkluze podmnožin. Pomocí naší relace infima na K je můžeme definovat jako A ⊂ B právě, když A ∧ B = A. Ekvivalentně, A ⊂ B právě, když A ∨ B = B. Lemma. Je-li (K, ∧, ∨, ) Booleova algebra, pak relace ≤ definovaná vytahem A ≤ B právě, když A ∧ B = A, je částečné uspořádání. Navíc platí pro všechny prvky A, B, C ∈ K (1) A ∧ B ≤ A (2) A ≤ A ∨ B (3) jestliže A ≤ C a zároveň B ≤ C, pak také A ∨ B ≤ C (4) A ≤ B, právě když A ∧ B = 0 (5) 0 ≤ A a A ≤ 1. Důkaz. Všechny dokazované vlastnosti a vztahy jsou výsledkem jednoduchého výpočtu v Booleovské algebře K. Začněme s vlastnostmi uspořádání pro ≤. Reflexivita je přímým důsledkem idempotence: A ∧ A = A, tj. A ≤ A. Podobně komutativita pro ∧ zaručuje antisymetrii ≤, protože z A ∧ B = A a zároveň B ∧ A = B vyplývá A = A ∧ B = B ∧ A = B. Konečně z platnosti A ∧ B = A a B ∧ C = B vyvodíme A ∧ C = (A ∧ B) ∧ C = A ∧ (B ∧ C) = A ∧ B = A, což ověřuje tranzitivitu relace ≤. Dále počítáme (A ∧ B) ∧ A = (A ∧ A) ∧ B = A ∧ B, takže A ∧ B ≤ A. Ze vztahu A ∧ (A ∨ B) = A, viz 11.46(2), plyne A ≤ A ∨ B, což dokazuje tvrzení (2). Distributivita společně s předpokladem (3) dává (A ∨ B) ∧ C = (A ∧ C) ∨ (B ∧ C) = A ∨ B, takže skutečně platí (3). Tvrzení (5) plyne přímo z axiomů pro význačné prvky 1 a 0. Zbývá nám tvrzení (4). Jestliže A ≤ B, pak A ∧ B = A ∧ B ∧ B = 0. Naopak je-li A ∧ B = 0, pak A = A ∧ 1 = A∧(B ∨B ) = (A∧B)∨(A∧B ) = (A∧B)∨0 = A∧B. Odtud A ≤ B a důkaz je ukončen. Všimněme si, že stejně jako v případě algebry podmnožin je v Booleovských algebrách A ∧ B = A právě, když je A ∨ B = B. Skutečně, je-li A ∧ B = A, pak z absorpčních zákonů plyne A∨B = (A∧B)∨B = B, a naopak. Můžeme proto pro definici částečného uspořádání stejně dobře používat také operaci ∨. 10.26 518 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY 11.52. Svazy. Viděli jsme, že každá Booleova algebra zadává poset (K, ≤). Zdaleka ne každý poset ovšem vzniká takovýmto způsobem. Např. triviální částečné uspořádání, kdy A ≤ A pro všechny A a všechny dvojice různých prvků jsou nesrovnatelné, samozřejmě z Booleovy algebry vzniknout nemůže, pokud je v K více než jeden prvek (viděli jsme, že největší a nejmenší prvek v Booleově algebře je totiž srovnatelný s každým prvkem). Zkusme se zamyslet, do jaké míry lze z uspořádání budovat operace ∧ a ∨. Pracujme s pevně zvoleným posetem (K, ≤). O prvku C ∈ K řekneme, že je dolní závorou pro nějakou množinu prvků L ⊂ K, je-li C ≤ A pro všechny A ∈ L. Prvek C ∈ K je infimem množiny L ⊂ K, jestliže je dolní závorou a pro každou jinou dolní závoru D téže množiny platí D ≤ C. Obdobně definujeme horní závory a supremum podmnožiny L záměnou ≤ za ≥ v posledním odstavci. Konečné posety se přehledně zobrazují pomocí orientovaných grafů. Prvky K jsou představovány uzly a hranou jsou spojeny právě prvky v relaci s orientací od většího k menšímu. Hasseho diagram posetu je zakreslení takového grafu v rovině tak, že větší prvky jsou zobrazeny vždy výš než menší (a orientace hran je tedy dána takto implicitně). Zvláště u malého počtu prvků množiny K je to velmi přehledný způsob, jak diskutovat různé příklady, viz obrázek níže. Svazy Definice. Svaz je poset (K, ≤), ve kterém každá dvouprvková množina {A, B} má supremum A ∨ B a infimum A ∧ B. Hovoříme přitom o úplném svazu, jestliže existuje supremum a infimum každé podmnožiny v K. Na svazu (K, ≤) tedy máme definovány binární operace ∧ a ∨ a přímo z definice je zjevná asociativita a komutativita těchto operací (dokažte si podrobně!). Všimněme si také že jakýkoliv prvek v K je horní závorou pro prázdnou množinu, proto supremum prázdné množiny musí být menší než všechny prvky v K. Obdobně infimum prázdné množiny musí být větší než jakýkoliv prvek v K. Zejména tedy úplný svaz má vždy největší a nejmenší prvek. Protože jsou binární operace ∧ a ∨ asociativní a komutativní, jistě existují v každém svazu suprema a infima všech konečných neprázdných množin. V případě konečných posetů (K, ≤) jde proto o úplný svaz tehdy a jen tehdy, když v něm existuje jediný největší prvek 1 ∈ K a jediný nejmenší prvek 0 ∈ K. O svazu říkáme, že je distributivní, jestliže operace ∧ a ∨ splňují axiomy distributivity (4) a (5) z odstavce 11.46 na straně 513. Snadno lze ale nakreslit Hasseho diagram svazu, který není distributivní, viz obrázek níže. Nyní už můžeme snadno definovat Booleovskou algebru v jazyce svazů: Booleovská algebra je distributivní svaz s největším prvkem 1 a nejmenším prvkem 0 takový, že v něm 519 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY existují ke všem prvkům komplementy (tj. prvky splňující vlastnost 11.45(8). Ověřili jsme již, že v takovém případě jsou komplementy definovány jednoznačně (viz úvahy na začátku odstavce 11.46), takže je naše alternativní definice Booleovské algebry korektní. Všimněme si také, při diskusi dělitelů daného čísla nebo polynomu p jsme narazili na distributivní svazy Dp, které jsou Booleovskou algebrou právě tehdy, když rozklad p neobsahuje kvadráty, viz Lemma 11.50. 10.28 11.53. Homomorfismy. Jak jsme již viděli u mnoha matematických struktur, o objektech se dozvídáme informace pomocí tzv. homomorfismů, tj. zobrazení, které zachovávají příslušné operace. Obzvlášť jednoduché je to u posetů: Isotonní zobrazení Homomorfismem posetů (K, ≤K) a (L, ≤L) rozumíme takové zobrazení f : K → L, že z A ≤K B vždy vyplývá také f (A) ≤L f (B). Hovoříme přitom také o izotonních zobrazeních. V případě svazů a Booleovských algeber definujeme homomorfismy podobně jako u okruhů: Homomorfismy svazů a algeber Zobrazení f : (K, ∧, ∨, ) → (L, ∧, ∨, ) se nazývá homomorfismus Booleovských algeber, jestliže pro všechny A, B ∈ K platí (1) f (A ∧ B) = f (A) ∧ f (B) (2) f (A ∨ B) = f (A) ∨ f (B) (3) f (A ) = f (A) . Homomorfismus f je izomorfismus Booleovských algeber, jestliže je f bijektivní. Podobně definujeme homomorfismy svazů jako zobrazení, která splňují vlastnosti (1) a (2). Snadno se ověří, že bijektivnost f již zaručí, že f −1 je opět homomorfismem. Z definice uspořádání na Booleových algebrách nebo svazech je zřejmé, že každý homomorfismus f : K → L bude také splňovat f (A) ≤ f (B) pro všechny prvky A ≤ B v K, půjde tedy vždy o izotonní zobrazení. Jakkoliv umíme rekonstruovat operace suprema a infima z uspořádání, pokud toto vzniklo z Booleovy algebry, není pravda, že by každý homomorfismus posetů byl automaticky homomorfismem příslušných algeber nebo svazů, viz obrázek níže. 10.26a 11.54. Věty o pevném bodě. Mnoho praktických úloh spočívá v diskusi pevných bodů zobrazení f : K → K na nějaké množině K, tj. prvků x ∈ K s vlastností f (x) = x. Naše úvahy o infimech a supremech umožňují překvapivě snadno odvodit velice silná tvrzení tohoto typu. Dokážeme 520 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY si jednu takovou klasickou větu, kterou odvodili Knaster a Tarski (ve speciálním případě Booleovské algebry podmnožin dané množiny již koncem dvacátých let 20. století, obecné tvrzení pak publikoval Tarski v r. 1955): Věta (Tarského věta). Uvažujme libovolný úplný svaz (K, ∧, ∨) a libovolné isotonní zobrazení f : K → K. Pak f má pevný bod a množina všech pevných bodů f je (s uspořádáním zděděným z K) opět úplný svaz. Důkaz. Označme M = {x ∈ K; x ≤ f (x)}. Protože v K existuje minimální prvek, je jistě M neprázdná a protože f zachovává uspořádání, je f (M) ⊂ M. Označme dále z1 = sup M. Pak jistě pro x ∈ M platí x ≤ z1, tedy také f (x) ≤ f (z1). Přitom zároveň víme x ≤ f (x), takže f (z1) je horní závorou pro M. Pak ovšem nutně z1 ≤ f (z1), takže i z1 ∈ M a proto f (z1) ≤ z1. Dokázali jsme tedy f (z1) = z1 a pevný bod je nalezen. Trochu složitější je dokázat dovětek, že množina Z ⊂ K všech pevných bodů zobrazení f je úplný svaz. Zřejmě jsme již našli její největší prvek z1 = max Z a úplně stejným postupem s použitím infima a vlastnosti f (x) ≤ x, místo definice M a jejího suprema, bychom našli také nejmenší bod z0 = min Z. Uvažme nyní libovolnou neprázdnou množinu Q ⊂ Z a označme y = sup Q. Toto supremum sice nemusí ležet v Q, ukážeme ale, že bude přesto v Z existovat supremum i ve zděděném uspořádání ≤Z z uspořádání v K. Za tím účelem si označme R = {x ∈ K; y ≤ x}, tj. množinu všech prvků v K větších než naše y. Přímo z definic je zřejmé, že tato množina R je, spolu s uspořádáním zděděným z K, opět úplný svaz a zúžení zobrazení f na R bude opět izotonní zobrazení f|R : R → R. Podle výše dokázaného tedy bude mít f|R nejmenší pevný bod ¯y. Samozřejmě je ¯y ∈ Z a snadno nahlédneme, že ve skutečnosti je ¯y supremem námi zvolené množiny Q vůči zděděnému uspořádání na Z. Přitom je možné, že ¯y > y. Obdobným postupem se zaměněnými relacemi a volbou infima najdeme i infimum libovolné neprázdné podmnožiny v Z. Největší a nejmenší prvek jsme již našli dříve a důkaz je ukončen. Poznámka. V literatuře lze najít mnoho variant vět o pevných bodech v různých souvislostech. Jednou z velmi užitečných je tzv. Kleeneho věta, jejíž tvrzení můžeme vyčíst z právě dokázané věty následujícím způsobem. Jestliže (ve značení Tarského věty) uvážíme spočetnou podmnožinu v K tvořenou tzv. Kleeneho řetězcem 0 ≤ f (0) ≤ f (f (0)) ≤ . . . , pak supremum z této podmnožiny zjevně nemůže být větší, než kterýkoliv pevný bod zobrazení f . Skutečně, pokud je y pevný bod zobrazení f pak ze vztahu 0 ≤ y dostaneme f (0) ≤ f (y) = y atd. Pokud má f navíc vlastnost, že „dostatečně“ zachovává suprema, můžeme dovodit že f (z) bude opět supremem téhož řetězce a tedy pevný bod. Musí to 521 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY proto být nejmenší pevný bod. Toto tvrzení se nazývá Kleeneho věta o pevném bodě a má četná použití v teorii rekurzí, při diskusi zastavení algoritmů atd. Nebudeme zde zacházet do podrobností kolem tzv. spojitosti zobrazení mezi posety. Přesné formulace Kleeneho věty a dalších souvislostí lze nalézt např. v ??. 10.27 11.55. Normální tvary výrazů. Vrátíme se závěrem zpět k diskusi Booleovských algeber s konečným počtem prvků a ukážeme si jejich úplnou kla- sifikaci. Při diskusi výrokové logiky jsme se potýkali s problémem, co vlastně jsou prvky příslušné Booleovy algebry. Formálně vzato jsme je definovali jako třídy ekvivalentních výroků. Jinak řečeno, pracovali jsme s hodnotovými funkcemi pro výroky s daným počtem argumentů. Vůbec jsme přitom neřešili obtížný problém, jak rozpoznat stejné výroky v tomto smyslu. Také jsme neřešili, jestli všechny formálně možné hodnotové funkce (Z2)n → Z2 lze zadat pomocí základních logických operací. Zcela obdobně se můžeme tázat, jak poznat, zda dva systémy přepínačů mají stejnou funkci. Obdobně jako u výroků zde pro systém s n přepínači pracujeme s funkcemi (Z2)n → Z2 a zjevně existuje právě 22n různých takových přepínacích funkcí. Na těchto funkcích umíme přirozeným způsobem zadat strukturu Booleovy algebry (využíváme, že hodnoty, tj. Z2 jsou Booleovou algebrou). Odpovíme nyní na výše uvedené otázky tak, že pro libovolný prvek obecné Booleovy algebry sestrojíme jeho tzv. normální tvar, tj. napíšeme jej pomocí dobře vybrané skupiny nejjednodušších prvků a operace ∨. Porovnáním normálních tvarů dvou prvků pak už snadno poznáme, zda jsou stejné či nikoliv. Nejprve si tedy vybereme obzvlášť jednoduché prvky Booleovských algeber: Atomy v Booleovské algebře Prvek A ∈ K nazveme atom v Booleově algebře K, jestliže pro všechny B ∈ K platí A ∧ B = A nebo A ∧ B = 0. Jinak řečeno, A je atom, když pro všechny ostatní prvky B ≤ A implikuje B = 0 nebo B = A. Velmi jednoduché je to v Booleovské algebře všech podmnožin dané konečné množiny M. Zjevně budou atomy právě všechny jednoprvkové podmnožiny A = {x} v množině M. Skutečně, pro každou podmnožinu B budeme mít buď A ∧ B = A, pokud x ∈ B, nebo A ∧ B = 0, pokud x /∈ B. Podívejme se ještě, jak vypadají atomy v Booleově algebře funkcí přepínačového systému s n přepínači A1, . . . , An. Snadno ověříme, že zde je 2n atomů, které jsou tvaru Aσ1 1 ∧ · · · ∧ Aσn n , kde buď Aσi i = Ai nebo Aσi i = Ai. Skutečně, pro dvě funkce ϕ a ψ je jejich infimem funkce ϕ ∧ ψ, jejíž hodnoty jsou dány součinem jejich hodnot v Z2. Platí tedy ϕ ≤ ψ jestliže ϕ má hodnotu 1 ∈ Z2 všude tam, kde má ψ hodnotu 1 ∈ Z2. Odtud už plyne, že v naší Booleově algebře hodnotových funkcí je funkce ϕ atomem 522 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY právě, když z 2n hodnot ϕ na jednotlivých možnostech hodnot jednotlivých argumentů má právě jednou hodnotu 1 ∈ Z2. Všechny takové funkce ovšem lze vytvořit právě uvedeným způsobem. A nyní můžeme sformulovat slibovanou větu o normálním disjunktivním tvaru Věta. Každý prvek B v konečné Booleově algebře (K, ∧, ∨, ) lze zapsat jako supremum atomů B = A1 ∨ · · · ∨ Ak. Tato formule je navíc jednoznačná až na pořadí atomů. Důkaz nám zabere několik odstavců, ale základní idea je docela jednoduchá: Uvažme všechny atomy A1, A2, . . . , Ak v K, které jsou menší nebo rovny B. Z vlastností uspořádání na množině K (viz 11.51(3)) je okamžitě vidět, že také Y = A1 ∨ · · · ∨ Ak ≤ B. Hlavním naším krokem v důkazu bude ověřit, že B ∧ Y = 0, což podle 11.51(4) zaručuje B ≤ Y. Tím bude dokázána rovnost B = Y. 11.56. Tři pomocná tvrzení. Postupně si odvodíme několik technických vlastností atomů a pak teprve dokončíme důkaz věty o normálním disjunktivním tvaru. Pokračujeme v symbolice používané v minulém odstavci. Tvrzení. (1) Jestliže jsou Y, X1, . . . , X atomy v K, pak Y ≤ X1 ∨ · · · ∨ X tehdy a jen tehdy, když Y = Xi pro nějaké i = 1, . . . , . (2) Pro každý prvek Y = 0 v K existuje atom X, pro který je X ≤ Y. (3) Jestliže jsou X1, . . . , Xr všechny atomy v K, pak Y = 0 právě, když Y ∧ Xi = 0 pro všechny i = 1, . . . , r. Důkaz. (1) Jestliže platí nerovnost v tvrzení, pak Y ∧ (X1 ∨ · · · ∨ X ) = Y. Díky distributivitě můžeme rovnost přepsat jako (Y ∧ X1) ∨ . . . (Y ∧ X ) = Y, přitom ale je pro všechna i buď Y ∧Xi = 0 nebo Y ∧Xi = Xi. Pokud by tedy byly všechny tyto průniku 0, bylo by i Y = 0. Musí být tedy nějaké i, pro které je Y ∧ Xi = Xi. Prvek Y je přitom také atom, takže jsme dokázali požadovanou rovnost Y = Xi. Opačná implikace je zřejmá. (2) Pokud je Y samo atomem, pak stačí zvolit X = Y. Jestliže Y není atom, pak z definice vyplývá, že musí existovat nenulový prvek Z1, pro který je Z1 ≤ Y. Jestliže ani Z1 není atom, pak ze stejných důvodů najdeme Z2 ≤ Z1 a postupně tak sestrojíme posloupnost různých prvků . . . Zk ≤ Zk−1 ≤ · · · ≤ Z1 ≤ Y, 523 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY která nemůže být nekonečná, protože celá Booleovská algebra K je konečná. Proto musí skončit nějakým atomem Zk. (3) Předpokládejme nejprve, že Y ∧ Xi = 0 pro všechny indexy i. Pokud by ale bylo Y = 0, pak podle předchozího bodu musí existovat atom Xj , pro který Xj ∧ Y = Xj , což je spor. Opačná implikace je triviální. 11.57. Důkaz věty o normálním tvaru. Pokračujme v naší úvaze o přepsání prvku B pomocí výrazu Y = A1 ∨ · · · ∨ Ak ≤ B, kde Ai jsou všechny atomy v K menší nebo rovny B. Spočteme B ∧ Y = B ∧ (A1 ∨ · · · ∨ Ak) = B ∧ A1 ∧ · · · ∧ Ak. Jestliže je A = Ai atom obsažený ve sjednocení Y, pak tedy B ∧ Y ∧ A = 0. Pokud ale je A atom, který ve výrazu Y nevystupuje, dostáváme také B∧Y ∧A = 0, neboť Y obsahuje právě všechny atomy menší než B a proto B ∧ A = 0. Dokázali jsme tedy, že B ∧Y má nulový průnik se všemi atomy a proto je to nulový prvek podle našeho druhého pomocného tvrzení výše. Proto tedy B ≤ Y. Z definice Y ale víme Y ≤ B a antisymetrie uspořádání tedy zaručuje B = Y, jak jsme chtěli dokázat. Zbývá jednoznačnost výrazu, až na pořadí. Předpokládejme tedy, že jsme zapsali B dvěma způsoby v požadovaném tvaru B = A1 ∧ . . . Ak = ˜A1 ∧ . . . ˜A . Nyní každé Ai splňuje Ai ≤ B a proto je podle prvního pomocného tvrzení výše nutně rovno jednomu z ˜Aj . Opakováním tohoto argumentu dostáváme požadovanou jednoznačnost a důkaz je ukončen. 11.58. Klasifikace. Na závěr našich úvah ještě dokážeme, že ve skutečnosti byly všechny naše příklady konečných Booleovských algeber izomorfní. Zejména tedy uvidíme, že každou z 22n hodnotových funkcí pro n elementárních výroků umíme zapsat vhodným výrokem, stejně jako každou z 22n různých přepínacích funkcí umíme zadat pomocí vhodně sestavených n přepínačů. Ve obou případech se bude diskutovaná algebra chovat stejně jako Booleovská algebra všech podmnožin v množině s 2n prvky. Navíc jsme se naučili každý takový výraz napsat v jednoznačném normalizovaném tvaru, takže umíme algoritmicky určit, zda budou např. dva přepínačové systémy vykazovat stejné chování, aniž bychom porovnali hodnoty při všech 2n možných vstupech. 10.27c Věta. Každá konečná Booleova algebra je izomorfní Booleovské algebře K = 2M , kde M je množina atomů v K. Důkaz. Myšlenka důkazu je zcela přímočará. Při každém izomorfismu konečné Booleovské algebry (K, ∧, ∨, ) musí atomy být zobrazeny na atomy. Najděme si tedy množinu 524 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY M všech atomů v K a uvažme Booleovu algebru (2M , ∩, ∪, ) všech podmnožin v M. Tím máme i zadánu přirozenou korespondenci mezi atomy v K a 2M . Použijeme nyní disjunktivní normální formu k rozšíření zobrazení na celé K. Každý prvek X ∈ K lze psát jednoznačně, až na pořadí atomů Ai, ve tvaru X = A1 ∨ · · · ∨ Ak a definujeme tedy funkci f : K → 2M vztahem f (X) = f (A1) ∪ · · · ∪ f (Ak), tj. jako sjednocení jednoprvkových podmnožin Ai ⊂ M obsažených ve výrazu. Z jednoznačnosti normální formy vyplývá, že f je nutně bijekcí. Zbývá dokázat, že jde o morfismus Booleovských algeber. Jsou-li X a Y dva prvky v K, pak v normální formě jejich sjednocení jsou právě atomy, které vystupují v X nebo v Y, zatímco u průniku jsou to atomy vystupující v obou výrazech současně. To ale právě ověřuje, že f zachovává operace ∧ a ∨. Pro doplňky si všimněme, že atom A vystupuje v normální formě X , právě když X ∧ A = 0. Odtud již vidíme, že i komplementy f zachovává a důkaz je ukončen. Pro nekonečné Booleovské algebry obecně neplatí, že by byly izomorfní Booleovské algebře všech podmnožin nějké vhodné množiny M. Platí však, že je izomorfní Booleově podalgebře vhodné podmnožiny všech množin nějaké množiny M. Tomuto výsledku se říká Stoneova věta o reprezentaci, důkaz lze najít např. v ??. 5. Kódování Často potřebujeme přenášet informace a přitom zajišťovat jejich správnost. Někdy stačí zajistit, abychom poznali, zda je informace nezměněná, a při chybě si vyžádáme informaci znovu, jindy potřebujeme zajistit, aby chyby byly i opraveny bez nového přenášení zprávy. To vše je úkol kódování a v dalších odstavcích se tomuto úkolu budeme věnovat. Pokud navíc chceme, aby zprávu mohl číst pouze adresát, potřebujeme i tzv. šifrování. Tomu jsme se krátce věnovali na konci minulé kapitoly. 10.29 11.59. Kódy. Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (tj. prvky v Z2), říkáme jim bity, a přenášíme konečná slova o k bitech, pro nějaké pevně zvolené k ∈ N. Obdobné postupy jsou možné nad libovolnými konečnými poli, my ale zůstaneme u nejjednoduššího případu Z2. Přenosové chyby chceme rozpoznávat, případně i opravovat, a za tím účelem přidáváme ke k–bitovému slovu dodatečných n − k bitů informace pro pevně zvolené n > k. Hovoříme o (n, k)–kódech. 525 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Všech slov o k bitech je 2k a každé z nich má jednoznačně určovat jedno kódové slovo z 2n možných. Máme tedy u (n, k)-kódů ještě 2n − 2k = 2k (2n−k − 1) slov, které jsou chybové. Lze tedy tušit, že pro veliké k nám i malý počet přidaných bitů dává hodně redundantní informace. Úplně jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby přidáním prvního bitu ke k–bitovému slovu byl zaručen sudý počet jedniček ve slově. Jde tedy o (k + 1, k)–kód. Pokud při přenosu dojde k lichému počtu chyb, s použitím tohoto jednoduchého kódu na to přijdeme. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od alespoň dvou různých kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat, ani kdybychom věděli, že při přenosu došlo k právě jedné chybě. Přehledně jsou všechna možná slova o dvou bitech s jedním přidaným paritním bitem vidět na obrázku níže. Kódová slova jsou zvýrazněna tučným puntíkem. 100 110 101 111 001 010 011 000 Navíc kódem kontrolujícím pouze paritu neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních hodnot ve slově. 10.30 11.60. Vzdálenost slov. Na obrázku ilustrujícím (3, 2)–kód kontrolující paritu je vidět, že ve skutečnosti každé chybné slovo je „stejně“ daleko od tří kódových slov — jsou to ta, která se liší v právě jednom bitu. Ostatní jsou dál. Abstraktně můžeme takové pozorování zachytit definicí vzdálenosti: Vzdálenost slov Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. Pokud uvažujeme slova x, y, z a první dvě se liší v r bitech, zatímco y a z se liší v s bitech, pak se nutně x a z liší v nejvýše r + s bitech, je tedy splněna trojúhelníková nerovnost pro vzdálenosti. Aby kód mohl odhalovat chyby v r bitech, musí být minimální vzdálenost mezi kódovými slovy alespoň r + 1. Pokud budeme chtít i opravit nepřesně přenesené slovo s r chybami, pak nutně musí existovat jen jediné kódové slovo, které má od přijatého chybného slova vzdálenost nejvýše r. Ověřili jsme tedy jednoduchá tvrzení: 526 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY Věta. (1) Kód spolehlivě odhaluje nejvýše r chyb ve slově, právě když je minimální Hammingova vzdálenost kódových slov r + 1. (2) Kód spolehlivě odhaluje i opravuje nejvýše r chyb, právě když je minimální Hammingova vzdálenost kódových slov 2r + 1. 10.31 11.61. Konstrukce polynomiálních kódů. K praktickému použití potřebujeme efektivně konstruovat kódová slova tak, abychom je mezi všemi slovy sladno rozpoznali. Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů. Např. (3, 1)–kód bere jednotlivé bity a posílá je třikrát po sobě. Docela systematickou cestou ke konstrukci kódů je využití dělitelnosti polynomů. Zpráva b0b1 . . . bk−1 je reprezentována jako polynom nad polem Z2 m(x) = b0 + b1x + · · · + bk−1xk−1 . Polynomiální kód Nechť p(x) = a0 + · · · + an−kxn−k ∈ Z2[x] je polynom s koeficienty a0 = 1, an−k = 1. Polynomiální kód generovaný polynomem p(x) je (n, k)–kód jehož slova jsou polynomy stupně menšího než n dělitelné p(x). Zpráva m(x) je zakódována jako v(x) = r(x) + xn−k m(x), kde r(x) je zbytek po dělení polynomu xn−k m(x) polynomem p(x). Z definice kódového slova v(x) pro přenášené slovo m(x) čteme: v(x) = r(x) + xn−k m(x) = r(r) + q(x)p(x) + r(x) = q(x)p(x), protože nad Z2 je součet dvou stejných polynomů vždy nulový. Budou tedy skutečně všechna kódová slova dělitelná p(x). Naopak, je-li v(x) dělitelné p(x), můžeme číst poslední výpočet z opačné strany a vidíme, že jde skutečně o kódové slovo vzniklé uvedeným postupem. Z definice je také vidět, že kódové slovo vznikne přidáním n − k bitů na začátek slova. Původní zpráva je tedy obsažena přímo v polynomu v(x), takže dekódování správného slova je velmi snadné. Uveďme si dva jednoduché příklady, které už známe. Všimněme si nejprve, že 1 + x dělí polynom v(x) tehdy a jen tehdy, když v(1) = 0. To nastane právě tehdy, když je ve v(x) sudý počet nenulových koeficientů. Polynom p(x) = 1 + x proto generuje (n, n − 1)–kód kontroly parity pro všechna n ≥ 3. Obdobně se snadno ověří, že polynom p(x) = 1 + x + · · · + xn−1 527 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY generuje (n, 1)–kód n–násobného opakování bitů. Skutečně, dělením polynomu b0xn−1 polynomem p dostaneme zbytek b0(1 + · · · + xn−2 ) a tedy příslušné kódové slovo je b0p(x). 10.32 11.62. Detekce chyb. Označme si e(x) vektor chyb, které vzniknou při přenosu. Místo posílaného slova v ∈ (Z2)n tedy příjmeme polynom u(x) = v(x) + e(x). Chyba je rozpoznatelná pouze tehdy, když generátor kódu p(x) nedělí e(x). Máme proto zájem o polynomy p(x) v Z2[x], které nevystupují jako dělitelé zbytečně často. Definice. Ireducibilní polynom p(x) ∈ Z2[x] stupně m se nazývá primitivní, jestliže p(x) dělí polynom (1 + xk ) pro k = 2m − 1, ale nedělí jej pro žádná menší k. Věta. Je-li p(x) primitivní polynom stupně m, pak pro všechna n ≤ 2m − 1 odhaluje příslušný (n, n − m)–kód všechny jednoduché a dvojité chyby. Důkaz. Jestliže nastane právě jedna chyba, pak e(x) = xi pro vhodné 0 ≤ i < n. Protože je p(x) ireducibilní polynom, nemůže mít kořen v Z2. Zejména tedy nemůže dělit beze zbytku xi , protože rozklad xi je jednoznačný. Tedy je každá jednotlivá chyba rozpoznatelná. Jestliže nastanou chyby právě dvě, pak e(x) = xi + xj = xi (1 + xj−i ) pro jistá 0 ≤ i < j < n. Již víme, že p(x) nedělí beze zbytku žádné xi a protože je primitivní, nedělí beze zbytku ani 1 + xj−i , pokud je j − i < 2m − 1. Zároveň je p(x) ireducibilní, nedělí proto ani součin e(x) = xi (1 + xj−i ) a důkaz je ukončen. 10.32a 11.63. Dusledek. Je-li q(x) primitivní polynom stupně m, pak pro všechna n ≤ 2m − 1 rozpoznává (n, n − m − 1)–kód generovaný polynomem p(x) = q(x)(1 + x) všechny dvojité chyby a všechna slova s lichým počtem chyb. Důkaz. Kódová slova generovaná zvoleným polynomem p(x) jsou dělitelná jak x + 1, tak primitivním polynomem p1(x). Jak jsme již ověřili, faktor x + 1 má za důsledek kontrolu parity, tj. všechna kódová mají sudý počet nenulových komponent. Tím umíme odhalit výskyt lichého počtu chyb. Jak jsem již také viděli v předchozí větě, druhý faktor umí odhalit dvojnásobné chyby. Následující tabulka ilustruje sílu výsledků předchozích dvou tvrzení pro několik primitivních polynomů v nízkých stupních. Např. poslední řádek nám říká, že přidáním pouhých 11 kontrolních bitů ke slovu o délce 1012 bitů budeme umět pomocí polynomu (x + 1)p(x) odhalit jednotlivé, dvojité, trojité a všechny liché počty výskytů chyb v přenosu. Jde přitom o přenášení dosti velkých čísel, v desítkové soustavě by měly přes třista cifer. 528 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY primitivní polynom p(x) kontrolní bity délka slova 1 + x 1 1 1 + x + x2 2 3 1 + x + x3 3 7 1 + x + x4 4 15 1 + x2 + x5 5 31 1 + x + x6 6 63 1 + x3 + x7 7 127 1 + x2 + x3 + x4 + x8 8 255 1 + x4 + x9 9 511 1 + x3 + x10 10 1023 Nástroje pro konstrukci primitivních polynomů dává teorie konečných polí. Souvisí s tzv. primitivními prvky v Galoisových polích G(2m ). Ze stejné teorie lze také dovodit příjemnou realizaci dělení se zbytkem, tj. ověřování, zda je přijaté slovo kódové, pomocí zpožďovacích registrů. Jde o jednoduchý obvod s tolika prvky, kolik je stupeň polynomu.8 10.33 11.64. Lineární kódy. Polynomiální kódy lze efektivně popisovat také pomocí elementárního maticového počtu. Budeme přitom pracovat s vektorovými prostory nad Z2, takže musíme být opatrní při využívání výsledků elementární lineární algebry, protože jsme v ní často využívali vlastnost že v = −v zaručuje v = 0. To nyní samozřejmě neplatí. Základní definice vektorových prostorů, existence bazí a popis lineárních zobrazení pomocí matic ale zůstavají v platnosti. Bude užitečné připomenout si při čtení následujících odstavců obecnou teorii a ujistit se o její použitelnosti. Vyjdeme z obecnější definice kódů, která požaduje lineární závislost kódového slova na původní informaci: Lineární kódy Injektivní lineární zobrazení g : (Z2)k → (Z2)n je lineární kód. Matice G typu n/k reprezentující toto zobrazení ve standardních bazích se nazývá generující matice kódu. Pro každé slovo u je příslušným kódovým slovem delší vektor v = G · u. Věta. Každý polynomiální (n, k)–kód je lineární kód. Důkaz. Použijeme elementární vlastnosti dělení polynomů se zbytkem. Použijme naše přiřazení polynomu v(x) = r(x) + xn−k m(x) původní polynomiální zprávě m(x) na součet dvou různých zpráv m(x) = m1(x) + m2(x). Zbytek po dělení xn−k (m1(x) + m2(x)) je díky jednoznačnosti dělení dán jako součet zbytků r1(x) + r2(x) pro jednotlivé zprávy. Dostaneme tedy v(x) = r1(x) + r2(x) + xn−k (m1(x) + m2(x)), 8Více o této krásné teorii a jejích souvislostech s kódy se lze dočíst např. knize Gilbert, W., Nicholson, K., Modern Algebra and its applications, John Wiley & Sons, 2nd edition, 2003, 330+xvii pp., ISBN 0-471-41451-4. 529 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY což je požadovaná aditivita. Protože jediným nenulovým skalárem je v Z2 jednička, dokázali jsme požadovanou lineritu zobrazení slova m(x) na delší slovo v(x). Toto zobrazení je navíc injektivní, protože původní slovo m(x) je prostě zkopírováno za přidané bity. Např. uvažujme polynomiální (7, 4)–kód využívající primitivního polynomu p(x) = 1 + x + x3 pro kódování slov se čtyřmi bity (se třemi kontrolními bity). Vyčíslením na jednotlivých bázových prvcích mi(x) = xi−1 , i = 1, 2, 3, 4 dostáváme v1 = (1 + x) + x3 v2 = (x + x2 ) + x4 v3 = (1 + x + x2 ) + x5 v4 = (1 + x2 ) + x6 a tedy matice odpovídající tomuto (7, 4)–kódu je G =           1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1           . Tato matice ilustruje obecné vlasnosti polynomiálních kódů. Protože je u nich vždy původní slovo zkopírováno za přidané kontrolní bity, musí mít každý lineární kód vzniklý z polynomiálního matici s jednotkovým blokem Ik řádu k zabírajícím posledních k řádků matice, doplněným maticí P s n − k řádky a k sloupci. 10.34 11.65. Věta. Je-li g : (Z2)k → (Z2)n lineární kód s (blokově zapsanou) maticí G = P Ik , potom zobrazení h : (Z2)n → (Z2)n−k s maticí H = In−k P má následující vlastnosti (1) Ker h = Im g (2) Přijaté slovo v = G · u je kódové slovo právě, když je H · v = 0. Důkaz. Složení h ◦ f : (Z2)k → (Z2)n−k je dáno součinem matic (počítáme nad Z2) H · G = In−k P · P Ik = P + P = 0. Dokázali jsme tedy Im g ⊂ Ker h. Protože je prvních n − k sloupců v H tvořeno bázovými vektory v (Z2)n−k , má obraz Im h maximální dimenzi n − k a tedy má tento obraz 2n−k různých vektorů. Vektorové prostory nad Z2 jsou konečné 530 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY komutativní grupy, proto můžeme použít vztah mezi mohutnostmi pogrup a faktorgrup z odstavce 11.10 a dostáváme | Ker h| · | Im h| = |(Z2)n | = 2n . Proto je počet vektorů v Ker h roven 2n · 2k−n = 2k . K dokončení důkazu prvního tvrzení si nyní stačí povšimnout, že obraz Im f má také 2k prvků. Druhé tvrzení je samozřejmým důsledkem prvního tvr- zení. Matici H z věty se říká matice kontroly parity přílušného (n, k)–kódu. Např. matice H = (1 1 1) je zjevně takovou maticí pro (3, 2) kód přidávající jeden paritní bit k slovu o dvou bitech. Skutečně ji snadno dostaneme z matice G =   1 1 1 0 0 1   zadávající tento kód. Pro výše uvedený (7, 4)–kód to bude matice H =   1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1   . 10.35 11.66. Samoopravné kódy. Jak jsme viděli, přenos zprávy u dává výsledek v = u + e. To je ale nad Z2 ekvivalentní e = u + v. Pokud tedy známe vektorový podprostor V ⊂ (Z2)n správných kódových slov, víme u každého výsledku, že správné slovo se něj liší o případnou chybu, která je ve třídě rozkladu v + V ve faktorovém vektorovém prostoru (Z2)n /V . Zobrazení h : (Z2)n → (Z2)n−k zadané maticí kontroly parity má V za jádro, proto indukuje injektivní lineární zobrazení h : (Z2)n /V → (Z2)n−k . Jeho hodnoty jsou jednoznačně určeny hodnotami H · u. Syndromy slov Hodnota H ·u, kde H je matice kntroly parity pro lineární kód, se nazývá syndrom slova u v tomto kódu. Samozřejmým důsledkem této konstrukce je následující tvrzení. Věta. Dvě slova jsou ve stejné třídě rozkladu v + V právě, když sdílí syndrom. Samoopravné kódy nyní můžeme konstruovat tak, že pro každý syndrom určíme prvek v příslušné třídě, který je nejvhodnějším výběrem pro chybu. Budeme přitom vycházet z představy, že nejpravděpodobněji nastal nejmenší možný počet chyb. Ukážeme si postup na jednoduchém polynomiálním (6, 3) kódu zadaném polynomem 1 + x + x3 . Příslušné matice G a H obdržíme z těch z odstavce 11.65 tak, že prostě 531 KAPITOLA 11. ALGEBRAICKÉ STRUKTURY odebereme poslední sloupec a řádek u G a poslední sloupec u H. Sestavíme si nyní tabulku všech syndromů a jim odpovídajících kódových slov. Syndrom 000 mají právě všechna kódová slova. Všechna možná slova s daným syndromem pak dostaneme přičtením syndromu (doplněného nulami na délku kódového slova) ke všem kódovým slovům. V následujících dvou tabulkách jsou v prvním řádku příslušné syndromy, na dalším řádku pak uvádíme ten z vektorů v příslušné třídě, který má nejméně jedniček. Skoro ve všech případech jde o jedinou jedničku, jen v posledním řádku máme jedničky dvě a zvolili jsme si jako význačný prvek ten, který má jedničky vedle sebe (třeba protože věříme, že násobné chyby s větší pravděpodobností nastávají těsně po sobě) 000 100 010 001 000000 100000 010000 001000 110100 010100 100100 111100 011010 111010 001010 010010 111001 011001 101001 110001 101110 001110 111110 100110 001101 101101 011101 000101 100011 000011 110011 101011 010111 110111 000111 011111 110 011 111 101 000100 000010 000001 000110 110000 110110 110101 110010 011110 011000 011011 011100 111101 111011 111000 111111 101010 101100 101111 101000 001001 001111 001100 001011 100111 100001 100010 100101 010011 010101 010110 010001 Počínaje druhým sloupcem první tabulky, je každý sloupec afinním podprostorem v (Z2)6 , jehož zaměřením je vektorový prostor daný prvním sloupcem první tabulky. Je tomu tak, protože je daný kód lieární, všechna kódová slova tedy tvoří vektorový prostor a jednotlivé třídy ve faktorovém prostoru jsou afinní podprostory. Zejména je tedy rozdíl každých dvou slov ve stejném sloupci nějakým kódovým slovem. Tučně vyznačená slova představují tzv. vedoucí representanty třídy (afinního prostoru) odpovídajícího danému syndromu. Jsou to slova s nejmenším počtem jedniček v řádku. Udávají tak nejmenší počet bitových změn, které musíme v libovolném slovu v sloupci provést, abychom dostali kódové slovo. Např., pokud dostaneme kódové slovo v = 111101, má syndrom H · v = 110. Vedoucím representantem ve třídě tohoto syndromu je slovo 000100 a jeho odečtením od obdrženého kódového slova (což je nad Z2 totéž jako přičtení) dostaneme platné kódové slovo 111001. Je to platné kódové slovo s nejmenší možnou Hammingovou vzdáleností od obdrženého slova. Odeslaná zpráva tedy patrně byla 001. 532