Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Drsná matematika IV – 3. přednáška Okruhy polynomů a tělesa Jan Slovák Masarykova univerzita Fakulta informatiky 5. 3. 2009 Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Obsah přednášky 1 Literatura 2 Okruhy 3 Polynomy 4 Dělitelnost a nerozložitelnost 5 Polynomy více proměnných 6 Podílová tělesa Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Kde je dobré číst? vlastní poznámky, texty současného přednášejícího, GOOGLE, atd. Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods for Physics and Engineering, second edition, Cambridge University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii + 1232 pp. Zvára, Štěpán: Pravděpodobnost a matematická statistika ISBN 80-86732-71-7, 4.. vydn, 232 str., Matfyzpres, Praha. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa S grupami se potkáváme nejčastěji jako s množinami transformací. U skalárů i vektorů ale vystupovalo hned více obdobných struktur zároveň. Jako standardní příklady mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, komplexní čísla C) a množiny polynomů nad takovými skaláry K. Definition 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Poslední vlastnosti v našem výčtu axiomů okruhu se říká distributivita. Pokud neplatí vlastnost komutativity operace ·, hovoříme o (nekomutativním okruhu). V dalším se ovšem omezíme pouze na okruhy komutativní. Operaci + budeme říkat sčítání a operaci · násobení. 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů: je-li b = a · c a b = 0, pak c je jednoznačně dáno volbou a, b. Pro b = ac = ac totiž platí 0 = a · (c − c ) a a = 0, proto c = c . Dělitelé jedničky, tj. invertibilní prvky v K, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu. 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Typickým příkladem komutativních okruhů, 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Polynomem rozumíme 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í: Definition 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 ai xi 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 právě nenulové prvky v K, kterým říkáme konstantní polynomy. 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]. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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í. Zároveň ale platí tvrzení, které dokážeme zanedlouho: Theorem Jestliže je K nekonečný okruh, pak dva polynomy f (x) a g(x) nad K jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Dva polynomy f (x) = i ai xi a g(x) = i bi xi 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) + · · · + (a0b + + · · · + a b0)x + . . . kde uvažujeme nulové koeficienty všude, kde v původním výrazu pro polynomy nenulové koeficienty nejsou a u sčítání nechť je k maximální ze stupňů f a g. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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. 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Směřujeme nyní ke zobecnění rozkladů polynomů nad číslenými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu K samotném. Uvažujme proto nějaký pevně zvolený obor integrity K, třeba celá čísla Z nebo okruh Zp s prvočíselným p. je-li a|b a zároveň b|c pak také a|c; a|b a zároveň a|c pak také a|(αb + βc) pro všechny α, β ∈ K; a|0 pro všechny a ∈ K (je totiž a · 0 = 0); 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) Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Ř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 . Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Example 1 Z je obor integrity s jednoznačným rozkladem. 2 Každé pole (komutativní těleso) je obor integrity s jednoznačným rozkladem (a každý nenulový prvek je jednotka). 3 Nechť K má prvky tvaru a0 + k i=1 ai 2ni √ xmi kde a0, . . . , ak ∈ Z, mi , n ∈ Z>0. Pak jednotky jsou 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 je zde příliš málo.) Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Z je 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ě. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f (x) ∈ K[x], deg f > 0, a dělme jej 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 ∈ R. Tzn., že hodnota polynomu f v b ∈ K je rovna právě f (b) = r. Proto je prvek b ∈ K 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í: Corollary Každý polynom f ∈ K[x] má nejvýše deg f kořenů. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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. Protože rozdíl polynomů má jen konečný stupeň, pokud není nulový, dokázali jsme tak již dříve uvedené tvrzení: Theorem Jestliže je K nekonečný okruh, pak dva polynomy f (x) a g(x) nad K jsou stejné právě, když jsou stejná příslušná zobrazení f a g. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Polynom 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. Theorem (Bezoutova rovnost) 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Důkaz následujícího tvrzení je poměrně technický a nebudeme jej prezentovat v detailech (i když jsme si vše potřebné pro něj již v podstatě připravili). Theorem Je-li K obor integrity s jednoznačným rozkladem, pak také okruh polynomů K[x] je obor integrity s jednoznačným rozkladem. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Důsledkem této věty je skutečnost, že každý polynom nad komutativním okruhem s jednoznačným rozkladem můžeme rozložit tak, jak to známe s polynomy s reálnými nebo komplexními koeficienty. Pokud má polynom tolik kořenů, včetně násobnosti, jako je jeho stupeň deg f = k, je odpovídající rozklad tvaru f (x) = (x − a1) · (x − a2) . . . (x − ak). 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: Theorem (Základní věta algebry) Pole C je algebraicky uzavřené, tj. každý polynom stupně alespoň 1 má kořen. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Okruhy polynomů v proměnných x1, . . . , xr definujeme 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 se ověří, že polynomy v proměnných x1, . . . , xr lze 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 + . . . Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostáváme: Corollary 1 Jestliže v okruhu K nejsou dělitelé nuly, pak také v okruhu polynomů K[x1, . . . , xr ] nejsou dělitelé nuly. 2 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. Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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 . Literatura Okruhy Polynomy Dělitelnost a nerozložitelnost Polynomy více proměnných Podílová tělesa 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.