Re: Prednášky LS 2022/23 - algebra
Posted: Thu Apr 27, 2023 11:38 am
by jaroslav.gurican
10. prednáška: (24. 4. 2023)
Polynomické funckie - "neoficiálna" definícia polynomickej funkcie, povedali sme len pár poznámok o tom, že polynomické funkcie a polynómy v všeobecnosti nie sú to isté (napr. polynómov v $Z_2[x]$ je nekonečne veľa, zatiaľ čo funkcie $f\colon Z_2 \to Z_2$ sú len 4 (zhodou okolností - nie je to náhoda - sú to všetko polynomické funkcie). Okruh polynómov nad poľom, t.j. $F[x]$ je izomorfný s okruhom polynomických funkcií z $F$ do $F$ (tento okruh sme označilo ako $F\langle x\rangle$) ak $F$ obsahuje ako svoj podokruh (až na izomorfizmus) $(\mathbb Z,+,\cdot)$ - to sme len skonštatovali, v skutočnosti sú $F[x]$ a $F\langle x\rangle$ izomorfné práve vtedy, keď je $F$ nekonečné pole (vyplýva to z vety 4.2.13).
Deliteľnosť v oboroch inegrity, najväčší spoločný násobok prvkov v oboroch integrity ($\gcd(a,b)$), Euklidov algoritmus. Definícia a základné vlastnosti deliteľnosti v o.i., pojem asociovaného prvku, pojem deliteľa jednotky a množina $\mathrm U(R)$ všetkých deliteľov jednotky v okruhu $R$. Ukázali sme, že $\mathrm U(\mathbb Z)=\{-1,1\}$ a pre okruhy polynómov nad poľom $F$, platí, že $\mathrm U(F[x])=F\setminus\{0\}$, t.j. je to množina nenulových konštantných polynómov.
Pojem (definícia) najväčšieho spoločného deliteľa $\gcd(a,b)$ dvoch prvkov $a,b$ v o.i. $R$.
Ukázali sme tvrdenie o $\gcd(a,b)=\gcd(a+bx,b)$ (Lema 4.3.12, "oficiálna" formulácia je trochu podrobnejšia). Na základe tejto lemy sme pre okruh $R$ taký, že je to $\mathbb Z$ alebo okruh typu $F[x]$ pre pole $F$ ukázali tzv. Euklidov algoritmus, pomocou ktorého sa dá pre ľubovoľné dané prvky $a,b\in R$ vypočítať $\gcd(a,b)$ a naviac, že vieme pomocou neho nájsť $s,t\in R$ také, že $\gcd(a,b)=sa+tb$ (keďže ich vieme nájsť pomocou Euklidovho algoritmu, znamená, to, že pre $a, b\in R$ existujú také $s,t\in R$. Nie sú určené jednoznačne, ak napr. $\gcd(a,b)=1$ a pomocou Euklidovho algoritmu nájdeme $s,t\in R$, tak bude aj $1=sa+tb=sa+(ba-ab)+tb=(s+b)a+(t-a)b$, podobne $1=(s+2b)a+(t-2a)b$,...)
Sformulovali a dokázali sme dôležitý dôsledok, Dôsledok 4.3.14.
Ireducibilné prvky. Definovali sme ireducibilné prvky v obore integrity, dokázali sme, že ak $p$ je ireducibilný prvok v o.i. $R$ a $a\in R$, tak existuje $\gcd(a,p)$ a platí, že je to buď $1$ alebo je to $p$ (t.j. ak $p$ je ireducibilný prvok v o.i. $R$, $a\in R$, tak $\gcd(a,p)=1 \vee \gcd(a,p)=p$).
Sformulovali a dokázali sme dôsledok 4.3.21.
Domáca úloha je zverejnená
tu.
Po dohode s vašimi kolegami sme presunuli písomky na cvičeniach na posledný týždeň, čiže budú podľa skupín 9. - 11. mája.
Na písomky by bolo dobre, aby ste prišli každý do svojej "oficiálnej" skupiny, aby cvičiaci nemuseli opravovať písomky ľuďom, ktorí k nim podľa rozpisu skupín nepatria.
Najbližšie prednášky budú 15. 5. a 16. 5. (náhrada za 1. 5. a 8. 5.) Na týchto prednáškach sa nič nemení, t.j. konajú sa v tieto dni rovnakej miestnosti ako to bolo podľa rozvrhu, t.j. v
F1-328 a rovnakom čase, t.j.
11.30 - 13.00 (akurát v pondelok je to presne podľa rozvrhu, v utorok je to "dodefinované").
Re: Prednášky LS 2022/23 - algebra
Posted: Thu May 18, 2023 11:32 am
by jaroslav.gurican
12. prednáška: (16. 5. 2023)
Viacnásobné korene polynómov, formálna derivácia polynómu. Kritérium na zistenie, či má polynóm $f\in F[x]$ v nejakom nadpoli $F^\prime$ viacnásobný koreň (je to práve vtedy, keď je $\mathrm{st}(\gcd(f(x), Df(x))) \ge 1$).
Spravili sme ešte jeden dôkaz, že polynóm $f\in F[x]$ stupňa $n\ge 0$ má v $F$ najviac $n$ koreňov (spravili sme to trochu všeobecnejšie, že pre obor integrity $R$ a polynóm $f\in R[x]$, ktorý je stupňa $n\ge 0$, tak $f$ má v $R$ najviac $n$ koreňov).
Z tohoto tvrdenia okrem iného vyplýva, že ak je $F$ nekonečné pole, ak pre polynomickú funkciu $f:F\to F$ danú predpisom $f(r)=a_nr^n+a_{n-1}r^{n-1}+\dots +a_1r+a_0$ pre $r\in F$ platí, že je identicky rovná nule (t.j. pre všetky $r\in F$ je $f(r)=0$, tak $a_n=a_{n-1}=\dots a_1=a_0=0$) lebo toto znamená, že každý prvok z $F$ je koreň $f(x)$, a pre každé $n$ má teda polynóm $f(x)$ viac ako $n$ koreňov, preto $f$ nemôže mať stupeň $n\ge 0$).
Charakteristika poľa $F$, $\mathrm{char}(F)$ - len definícia. Pre pole $F$ také, že $\mathrm{char}(F)$ a polynóm $f\in F[x]$ je zaujímavý polynomóm $g(x)=\frac{f(x)}{\gcd(f(x), Df(x))}$. Polynóm $g(x)$ má v $F$ rovnaké korene ako $f(x)$, len ich má jednoduché. To znamená, že ak sú $c_1,\dots,c_k\in F$ po dvoch rôzne korene $f(x)$ a
$$f(x)=a(x-c_1)^{a_1}\dots(x-c_k)^{a_k}h(x),$$
kde $a\in F$ a $h(x)$ nemá v $F$ korene (t.j. $a_1,\dots,a_k$ sú násobnosti koreňov $c_1,\dots,c_k$), tak $g(x)=(x-c_1)\dots(x-c_k)h^\prime(x)$, kde $h^\prime(x)$ nemá v $F$ korene. Keď je pole $F$ algebraicky uzavreté, tak v predošlých vyjadreniach je $h(x)=1$ a $h^\prime(x)=1$ (lebo tam má každý polynóm stupňa aspoň 2 koreň). Toto tvrdenie sme len povedali, dôkaz sme nerobili, nebudem ho ani skúšať.
Racionálne korene polynómov $f\in \mathbb Z[x]$ - ak je $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+a_0\in \mathbb Z[x]$ a $\frac pq\in \mathbb Q$ ktoré, je koreň $f(x)$ a $\gcd(p,q)=1$, tak $p|a_0$ a $q|a_n$ (toto tvrdenie bolo dokazované na cvičeniach, takže na prednáške sme už dôkaz nerobili). Ešte sme bez dôkazu povedali vetu, že ak $f\in \mathbb Z[x]$, ak pre $g(x)\in \mathbb Q[x]$ platí $f(x)=g(x)(x-\frac pq)$ (toto samozrejme znamená, že $\frac pq$ je koreň $f(x)$, aj teraz predpokladáme, že $\gcd(p,q)=1$), tak $g(x)\in \mathbb Z$, t.j. koeficienty $g(x)$ sú celočíselné, dokonca sú všetky deliteľné číslom $q$. Tieto dve tvrdenia umožňujú nájsť racionálne korene polynómu s celočíselnými koeficientami - pomocou prvého získame "kandidátov", druhé urýchli výpočet, lebo ak pre kanditáta $\frac pq$ počítame, či je koreň (pomocou Hornerovej schémy) a pri výpočte sa objaví zlomok, už nemusíme pokračovať, určite to nie je koreň. Dokonca sa môžeme zastaviť v momente, keď pri výpočte v Hornerovej schéme dostaneme číslo, ktoré nie je deliteľné číslom $q$.
Spomenuli sme zaujiímavú vetu: Ak je $R$ gaussovský okruh, tak aj $R[x]$ je gaussovský okruh. Keďže $Z$ je gaussovský, je aj $\mathbb Z[x]$ gaussovský, ale aj $\mathbb Z[x,y]$ gaussovský,... (pri tomto sme povedali, že náš dôkaz, ktorý sme použili pri dôkaze, že $Z$ a $F[x]$ pre pole $F$ sú gaussovské sa nedá použiť pre $\mathbb Z[x]$, lebo v našom dôkaze sme použili tvrdenie 4.3.13 - v skutočnosti sme potrebovali Dôsledok 4.3.21, ktorý je dôsledkom 4.3.14, ktoré je dôsledkom 4.3.13 - taký bol náš postup a iný spôsob nemáme k dispozícii). Ale v $\mathbb Z[x]$ z dôsledku 4.3.13 neplatí druhá časť, že pre $a,b\in \mathbb Z[x]$ existujú $s,t\in\mathbb Z[x]$ také, že $\gcd(a,b)=sa+tb$. Pre $a=2$, $b=x$ očividne $s,t$ nenájdeme, lebo $\gcd(2,x)=1$ a pre $s,t\in\mathbb Z[x]$ má polynóm $s\cdot 2+t\cdot x$ koeficient $a_0$ párny, takže to nie je $1$. A práve túto vlastnosť sme použili v dôkaze dôsledku 4.3.13.
Korene polynómov $f(x)\in \mathbb R[x]$, t.j. polynomóv s reálnymi koeficientami. Vychádzali sme z toho, že pole $\mathbb C$ je algebraicky uzavreté a teda aj všetky korene $f(x)\in \mathbb R[x]$ budú (v "najhoršom" prípade) komplexné.
Definovali sme komplene združené komplene číslo, bez dôkazu (sú to jednoduché výpočty) sme povedali, že $\overline{(a+bi)+(c+di)}=\overline{(a+bi)}+\overline{(c+di)}$ a tie $\overline{(a+bi)\cdot(c+di)}=\overline{a+bi}\cdot\overline{c+di}$, t.j. zobrazenie "komplexného združenia" je homomorfizmus (z okruhu $\mathbb C$ do okruhu $\mathbb C$, je to aj bijektívne zobraenie).
Dokázali sme: Ak je $f(x)\in \mathbb R[x]$ a komplené číslo $z$ je koreň $f$, tak aj $\overline z$ je koreň $f(x)$. Dokonca ak je komplené číslo $z$ $k$-násobný koreň $f$, tak aj $\overline z$ je koreň $k$-násobný $f(x)$.
Naviac, ak je $z=a+bi$ je koreň $f$ a $b\ne 0$, tak $(x-z)$ a $(x-\overline z)$ sú nesúdeliteľné polynómy, t.j. $f(x$) je deliteľný súčinom $(x-z)(x-\overline z)$ a je vidieť, že $(x-z)(x-\overline z)=x^2-(z+\overline{z})x+z\cdot\overline{z}=x^2-2ax+(a^2+b^2)$ je polynóm s koeficientami z $\mathbb R$, a preto pre vhodný polynóm $h(x)\in \mathbb R[x]$ je $f(x)=(x^2-2ax+(a^2+b^2))h(x)$ rozklad nad $\mathbb R$ a $x^2-2ax+(a^2+b^2)$ je nad $\mathbb R$ ireducibilný (lebo je to polynóm stupňa 2 a nemá reálny koreň - totiž už má v $\mathbb C$ dva korene $z$ a $\overline z$, ďalší, reálny koreň (čo je tiež komplexné číslo) by bol tretí koreň polynómu $f(x)$ stupňa 2.
Ak je polynóm $f\in \mathbb R[x]$ ireducibilný, tak má stupeň 1 alebo 2. Polynóm $f\in \mathbb R[x]$ stupňa $n=3$ (alebo všeobecnejšie nepárneho stupňa) musí mať aspoň jeden reálny koreň.
Taylor rozvoj polynómu $f(x)\in F[x]$ so stredom v bode $c\in F$ - výpočet pomocou Hornerovej schémy (robí sa to nad ľubovoľným poľom, nielen nad reálnymi číslami).
Po prednáške sa ma jeden kolega opýtal, či existuje nejaké pole, ktoré je väčšie ako $\mathbb C$. Toto teda nemusíte čítať, je to naviac.
Jedna nie zložitá procedúra, ktorá z daného poľa $F$ spraví "väčšie" pole je takáto:
Keď má pole $F$, máme okruh polynómov $F[x]$. Tento okruh je obor integrity (to sme dokazovali). Pole $F$ je podokruh okruhu $F[x]$.
Teraz, keď máme nejaký obor integrity $R$, existuje pole, ktoré ho obsahuje ako podokruh. Je dobre známa konštrukcia tzv. poľa zlomkov daného oboru integrity, z $R$ sa spraví niečo, čo sa označuje ako $Q(R)$ - podrobnosti sú napr. v "Katriňák a kol., Teoretická aritmetika", časť 4.5 Podielové pole, veta 4.5.2. V podstate sa jedná o konštrukciu, ktorá aj z oboru intergity $\mathbb Z$ "vyrobí" pole racionálnych čísiel $\mathbb Q$, zlomky sú v podstate "dvojice" $(p,q)$, kde $p, q\in R$, pričom $q\ne 0$. Tieto dvojice sa potom píšu v tvare $\frac pq$ - tak ste na to zvyknutí.
Ono to nie je celkom presne, lebo napr. $\frac 12, \frac 24, \frac 5{10}, \frac{-1}{-2}$ predstavujú rovnaký zlomok, takže na tej množine "formálnych zlomkov" ešte treba spraviť nejakú reláciu ekvivalencie a potom súčet, súčin, inverzný prvok treba definovať pre triedy ekvivalencie a nie pre jednotlivé prvky, ale to sú "len" technické detaily. Pri tejto konštrukcii bude $R\subseteq Q(R)$ (vďaka "zlomkom" typu $\frac r1$)
Takže spojením konštrukcie okruhu polynómov a podielového poľa dostaneme pre pole $F$ pole $Q(F[x])$, ktorého je $F$ podpole (a dokonca platí $F\subsetneq F[x]\subsetneq Q(F[x])$).
Iná, tiež algebraická konštrukcia využíva existenciu ireducibilného polynómu stupňa aspoň $2$ nad daným poľom (takže táto konštrukcia sa nedá použiť pre pole $\mathbb C$, lebo toto je algebraicky uzavreté pole).
Napr. nad $\mathbb Q$ je $x^2-2$ ireducibilný polynóm, jeho koreň je $\sqrt 2$ a vieme, že $\{a+b\sqrt 2;\ a,b\in \mathbb Q\}$ je s operáciami $+, \cdot$ "zdedenými" z poľa $\mathbb R$ pole (toto bolo ako cvičenie v prvom semestri, pri poliach, tie operácie sa dajú jednoducho definovať, napr. pre súčin je to $(a+b\sqrt 2)(c+d\sqrt 2)=(ac+2bd)+(bc+ad)\sqrt 2$, len pri tejto definícii musíme napr. overiť aj asociativitu, distributívne zákony,...), podobne je polynóm $x^2+1$ ireducibilný nad $\mathbb R$, jeho koreň je $i$ a z týchto "údajov" vyrobíme pole so "základnou" množinou $\{a+bi;\ a,b\in \mathbb R\}$ (komplexné čísla).
Skúsme vyrobiť jeden zaujímavý príklad. Zoberme pole $Z_2$, zoberme okruh polynómov $Z_2[x]$ a polynóm $x^2+x+1$ ireducibilný nad $Z_2$.
Zobreme polynómy, ktoré sú zvyškami polynómov zo $Z_2[x]$ pri delení polynómom $x^2+x+1$. Keďže sú to zvyšky pri delení polynómom stupňa $2$, sú to práve polynómy stupňa 1. Teda naša "základná množina" je $\{0,1,x,x+1\}$. Súčet/súčin zadefinujeme ako "pôvodný" súčet/súčin, ale modulo náš polynóm $x^2+x+1$. Pre súčet ponecháme znak $+$, pre násobenie použijeme znak $\odot$. (Teda ak pri násobení dosiahneme stupeň 2, tu sa viac nedá, nahradíme súčin zvyškom pri delení polynómom $x^2+x+1$, napr.
normálne je $(x+1)(x+1)=x^2+1$ - pozor, pri počítani v $Z_2$ je "$2=0$". Polynóm $x^2+1$ má stupeň viac ako 1, preto musíme vydeliť, ľahko vidieť, že $x^2+1=(1)(x^2+x+1)+x$, čiže zvyšok po delení je $x$, takže pre nás bude $(x+1)\odot(x+1)=x$). Pri súčte žiadne takéto problémy nehrozia.
Tabuľka pre súčet a súčin potom budú
$$
\begin{array}{cc}
\begin{array}{|c|cccc|} \hline
% after \\ : \hline or \cline{col1-col2} \cline{col3-col4} ...
+ & 0 & 1 & x & x+1 \\ \hline
0 & 0 & 1 & x & x+1\\
1 & 1 & 0 & x+1 & x\\
x & x & x+1 & 0 & 1\\
x+1 & x+1 & x & 1 & x\\ \hline
\end{array}
&
\begin{array}{|c|ccccc|} \hline
\odot & 0 & 1 & x & x+1\\ \hline
0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & x & x+1\\
x & 0 & x & x+1 & 1\\
x+1 & 0 & x+1 & 1 & x\\ \hline
\end{array}
\end{array}
$$
To, čo sme práve spravili je v podstate presne to, ako sme z množiny $\{0, 1,\dots, n-1\}$ spravili okruh $(Z_n,\oplus,\odot)$, tam sme ale museli upraviť aj definíciu súčtu, čo teraz nemusíme. Aj tu bude platiť, že operácie sú komutatívne (to je vidieť z tabuliek), sú asociatívne (to je vďaka tomu, že sučet a súčin sú asociatívne v $Z_2[x]$ a pri súčine ešte využívame to, že robíme aj "modulo", t.j. zvyšky pri delení, asociativita sa "presenie", aj distributívnosť). Takže $(\{0,1,x,x+1\}, +, \odot)$ je komutatívny okruh s 1 keď sa dobre pozriete na tabuľku pre násobenie, vidíte, že
$(\{0,1,x,x+1\}\setminus \{0\}, \odot)$ je tiež komutatívna grupa, t.j. $(\{0,1,x,x+1\}, +, \odot)$ je pole (ktoré má 4 prvky a obsahuje $Z_2$ ako svoje podpole). Ak označíme $c=x, d=x+1$, máme vlastne niečo ako $(\{0,1,c,d\}, +, \odot)$ a vidieť (tu aj podľa tabuliek pre operácie) $c^2+c+1=0$
(podľa tabuľky je $c\cdot c=d$, $c^2+c+1=(d+c)+1=1+1=0$), t.j. $c$ je koreň polynómu $x^2+x+1$ - aj $d$ je koreň tohoto polynómu, skúste si to skontrolovať, vypočítať. Takže sme pre polynóm $x^2+x+1$, ktorý je ireducibilný nad $Z_2$ vyrobili pole $GF(4)=(\{0,1,c,d\}, +, \odot)$, ktoré obsahuje $Z_2$ a aj koreň $c$ polynómu $x^2+x+1\in GF(4)[x]$ (keďže sú $x^2+x+1\in GF(4)[x]$ aj $x-c\in GF(4)[x]$, je aj ich podiel z $GF(4)[x]$, teda existuje $u\in GF(4)$ také že $x^2+x+1=(x-c)(x-u)$. Ale $x^2+x+1$ nemá koreň v $Z_2$, takže $u$ nie je ani 0 ani 1. Je to teda $c$ alebo $d$. Ale $\gcd(x^2+x+1,D(x^2+x+1))=\gcd(x^2+x+1,1)=1$ (počítame v $Z_2$, platí to hlavne preto, lebo $x^2+x+1$ je ireducibilný a preto je jeho $\gcd$ s čímkoľvek nižšieho stupňa 1, jediný problém by bol, keby bola derivácia nulová, čo sa pre ireducibilný polynóm z istého dôvodu stať nemôže), t.j. $\mathrm{st} (\gcd(x^2+x+1,D(x^2+x+1)))=0$, t.j. $x^2+x+1$ nemá viacnásobný koreň a preto $u=d$ (čo ste si už mohli overiť aj priamym výpočtom).
Prvky $GF(4)$ sa teraz dajú napísať v tvare $\{a+b\cdot c;\ a,b\in Z_2\}$ - porovnajte so zápisom $\{a+b\sqrt 2;\ a,b\in \mathbb Q\}$ pre ireducibilný polynóm $x^2-2$ a/alebo so zápisom $\{a+bi;\ a,b\in \mathbb R\}$ pre ireducibilný polynomial $x^2+1$. Tie konštrukcie sú úplne rovnaké.
Pri $Z_2$ môžete zobrať ireduciblilný polynóm $p_3$ stupňa 3 (skúste si taký nájsť) s praviť analogickú konštrukciu, zvyšky budú vsetky polynómy stupňa najviac 2, bude ich 8, súčin bude tiež modulo $p_3$ (so súčtom netreba robiť nič, lebo súčet polynómov stupňa menšieho ako 3 bude polynóm stupňa menšieho ako 3). Dostaneme pole $GF(8)$ s 8 prvkami obsahujúce $Z_2$ a obsahujúce koreň polynómu $p_3$, ktorý ako polyóm s koeficientami zo $Z_2$ je aj polynóm s koeficientami z $GF(8)$ (pozor, toto pole NEOBSAHUJE $GF(4)$ ako svoje podpole). Rovnako vieme spraviť pole $GF(16)$, ..., $GF(2^n)$, lebo nad $Z_2$ nájdete ireducibilné polynómy stupňov 2, 3, 4,...,n,... (pre všetky $n\ge 2$).
Podobne by ste spravili polia $GF(p^n)$ pre ľubovoľné prvočíslo $p$ a prirodzené číslo $n$. Naviac takto skonštruované pole $GF(p^n)$ je (až na izomorfizmus) jediné pole, ktoré má $p^n$ prvkov (to je ale teraz trochu mágia. Mágia v matematike znamená, že to vyplýva z nejakej, zvyčajne nie úplne jednoduchej vety.)
Ešte je v tejto konštrukcii jedna vec, ktorú sme pre získanie $GF(4)$ vyčítali z tabuľky, a to je existencia inverzných prvkov. To je ale v podstate dosť ľahké aj univerzálne: ak $p$ je ireducibilný polynóm nad poľom $F$, nech je taký, že $p(x)=x^n+a_{n-1}x^{n-1}+\dots+a_1x+a+0$, t.j. pri najvyššej mocnine máme 1. Zoberme niektorý zvyšok pri delení polynómom $p$, to je polynóm stupňa najviac $n-1$, nech je to $g$. Potom $\gcd(p,g)=1$, lebo $p$ je ireducibilný. Preto existujú $s,t\in F[x]$ také, že $s(x)g(x)+t(x)p(x)=1$. Preto $s(x)g(x)+t(x)p(x)=1\mod p(x)$ a dokonca ak zoberieme $s^\prime(x) = s(x)\mod p(x)$, tak $s^\prime(x)g(x)=1\mod p(x)$, čiže $s^\prime(x)$ je tiež zvyšok, ktorý je inverzný ku $g(x)$ vzhľadom na súčin $\odot$, t.j. pri počítaní modulo $p(x)$. Inverzné prvky teda vieme hľadať pomocou (rozšíreného) Euklidovho algoritnmu.