06 - Teorie polí
pátek 13. května 2016
9:49
Teorie polí (minimální pole, rozšíření pole, konečná pole a jejich konstrukce).
[link]
Pole
Pole je komutativní okruh (R, + ,0, − , * ,1) s inverzním a jednotkovým prvkem kde 0≠1 a 𝑅\{0,∗) je abelovská grupa.
Příklady:
Množina racionálních čísel ℚ
Množina reálných čísel ℝ a její největší algebraické komutativní nadtěleso, množina komplexních čísel ℚ
Podpole
Pokud omezíme nosnou množinu pole a pořád to zůstane pole, je to podpole.
Pole (K, + ,0, − , * ,1) se nazývá minimální, pokud nemá žádná jiná podpole než sebe sama.
Pole, ze kterého když cokoliv odebereme tak už to nebude pole.
Každé pole má vždy jediné podpole, které je minimální.
Rozšíření pole
Pokud do pole něco přidáme, a stále to bude pole. Vlastně by se to dalo nazvat nadpole.
Buďte K,L pole a K podpole pole L. Potom se L nazývá nadpole nebo rozšíření pole K.
Je-li L nadpole pole K a 𝑆⊆𝐿, pak definujeme rozšíření K(S) pole K takto:
𝐾𝑆≔⋂{𝐸⊆𝐿|𝐸 𝑗𝑒 𝑝𝑜𝑑𝑝𝑜𝑙𝑒 𝑝𝑜𝑙𝑒 𝐿, 𝑘𝑡𝑒𝑟é 𝑜𝑏𝑠𝑎ℎ𝑢𝑗𝑒 𝐾∪𝑆}
Je-li 𝑆 = 𝑢1,...,𝑢𝑟 konečné, pak píšeme 𝐾(𝑆) = :𝐾(𝑢1,...,𝑢𝑟). Je-li speciálně 𝑆 = 𝛼 jednoprvkové, pak píšeme 𝐾(𝑆) = :𝐾(𝛼) (jednoduché rozšíření pole K).
Konečné pole (Galoisovo pole; 𝑮𝑭(𝒑𝒌))
[link]
Pole, které obsahuje konečný počet prvků je konečné pole.
Charakteristika okruhu char K je velikost množiny obsahující výsledky násobení všech celých čísel jedničkou (pokud je množina konečná, jinak 0).
char ℤ, ℕ, ℝ = 0 (není konečné)
char ℤn1) = n, když n-krát přičtu „1“ dostanu „0“.
Vlastnosti konečného tělesa (pole)
Počet prvků (řád) konečného tělesa je roven 𝒑𝒌, kde 𝒑 je prvočíslo a 𝒌 je kladné přirozené číslo.
Charakteristika tělesa 𝐺𝐹(𝑝𝑘) je rovna právě prvočíslu 𝑝.
Konečná tělesa jsou komutativní (Wedderburnova věta).
Wedderburnova věta je matematická věta z oboru algebry, která říká, že neexistuje žádné těleso, které je konečné a nekomutativní, jinými slovy každé konečné těleso je komutativní a naopak, je-li nějaké těleso nekomutativní, nemůže být konečné.
Konečná tělesa lze klasifikovat podle velikosti; platí totiž, že až na izomorfismus existuje vždy jen jediné konečné těleso o daném počtu prvků.
Žádné konečné těleso není algebraicky uzavřené neboť označíme-li prvky konečného tělesa po řadě 𝑎1,𝑎2,…,𝑎𝑘, můžeme zkonstruovat mnohočlen 𝒙−𝒂𝟏𝒙−𝒂𝟐⋯(𝒙−𝒂𝒌) + 𝟏, který je zřejmě stupně alespoň 1 a přitom žádný z 𝑎1,𝑎2,…,𝑎𝑘 není jeho kořenem.
Ireducibilní polynom je takový polynom, který nelze rozložit na součin jednodušších polynomů. V opačném případě mluvíme o reducibilním polynomu. Tedy ireducibilní polynom nemá v reálných číslech žádný kořen.
 x^2 + 1 je ireducibilní nad tělesem R.
 x^2 -1 = (x-1) * (x+1) a tedy není ireducibilní (je reducibilní).
Kontrukce konečných polí - příklad
GF(2)
Okay, so we have a finite field on two elements. What’s that mean? Well a field is a set of elements with an addition and a multiplication satisfying some rules:
Addition is defined on every element in the field. Multiplication is defined on everything except the zero element (more on him later).
Closure of addition and multiplication. This just means if you add two elements of your field, you get an element in the field (we never stray outside). Same goes for multiplication.
Associativity. Namely 
. It’s something nice and familiar.
Commutativity. Namely
. This is nice.
Additive identity (aka zero). There’s a single element denoted 0 such that 
. Seems like a dumb thing to have until you get to…
Additive inverses. For every element 
 there is an element denoted 
. That is, we can cancel in addition. We use the negative sign to make the analogy with normal negative numbers. You can think of the negative sign as being a function that takes an element to its additive inverse, if you like. Note that the additive inverse need not be a different element. It just has to satisfy 
.
Multiplicative identity. This is a similar deal. There is an element, denoted 1, such that for every element 
.
Multiplicative inverses. This is also a similar deal, but for multiplication. Every element 
 (except zero) has a multiplicative inverse, denoted 
.
Distributivity. Addition and multiplication work together in the way you think, namely: 
.
Phew! That’s a fair bit of stuff to remember. Actually, all you have to do is expect everything to work how you expect it to work with normal numbers, but the actual “addition” and “multiplication” might be a little weird.
So let’s create 
. Well we have two elements and we have to have 0 and 1. We’re pretty much done and dusted, except if in this field 
. But if that were the case and we had some other element 
, which we said wasn’t 0 or 1! Therefore they have to be different.
Notice this logic forbids a field from having exactly 1 element. Therefore we are constructing the smallest example possible.
We can specify the addition and multiplication by lookup tables:
+
0
1
0
0
1
1
1
0
.
0
1
0
0
0
1
0
1
We can also simplify it by setting 
 with the usual addition and multiplication modulo 2. Easy!
GF(5)
Let’s try for a slightly bigger example. This field has 5 elements in it. Two of them have to be 0 and 1, and we’ll call the other three 
. Now, following the lead of the previous example, we could just say 
 are just 2, 3, and 4 respectively. This is fine and convenient. Here’s the addition and multiplication tables:
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
.
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
There’s a nice symmetry to the tables, which is because addition and multiplication are abelian groups.
From <[link]> 
(zdroj: [link])
Algoritmus
Příklad
Notes
Měl jsem si napsat GF(2^3) a naznačit co to generuje a jak to generuje V prvé řadě, vygeneruje to 8 prvků. Ta dvojka značí zbytkovou třídu, podle které ověřuje se ireducibilita a trojka imho udává maximální stupeň polynomu. Měl jsem si napsat nějaký polynom tak jsem nadhodil x^3 = x + 1, načež se zeptal co pro něj musí platit. Říkám že právě ireducibilita, tedy že nesmí ten polynom mít vlastní dělitele. Kdy nemá polynom vlastní dělitele? Tehdy, kdy nemá kořen. Má nebo nemá tento konkrétní polynom kořen? Nemá, protože zbytková třída 2 generuje prvky 0 a 1, přičemž ani jedno z těchto čísel není kořenem. Kdyby ten polynom nebyl ireducibilní, tak se nevygenerují všechny varianty těch polynomů.
From <[link]> 
2. Otazka (predmet) (okruh): Teorie polí, ..., konečná pole a jejich generování.
Kdo me primarne zkousel: doc. Drábek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem tím, co je to pole, jaké jsou na něm nastavené operace a jaké splňují vlastnosti (komutativita, asociativita). Doc. Drábek si přešel blíž, aby viděl, co píšu. Chvilku jsem ještě povídal, ale on chtěl, abych se zaměřil na konečná pole, vysvětlit, co znamená jejich konečnost, a abych to ukázal na příkladu GF(2) a GF(2^m). Tam jsem si vzpomněl na PDS a kódy, začal jsem s ireducibilním polynomem x^3 + x + 1 a z něj jsem vygeneroval celou algebru. Ještě se ptal, kolik bitů je potřeba na reprezentaci té algebry a pak mě propustil. Celkově se šikovně ptal a byl velmi milý a nápomocný.
From <[link]> 
1. Otázka (předmět) (okruh): 6. Teorie polí (zaměřit se na konečná pole)
Kdo mě primárně zkoušel: Švéda
Co jsem k tomu řekl/na co se ptali/co mne vytkli: 
Začal jsem tím, že je to algebraická struktura typu (2,0,1,2,0) popsal jsem jednotlivý operace. Švéda se pak zeptal jaké jsou ty dvě algebry, tak jsem řekl, že obě abelovské grupy, což prý nejsou, ale že ta aditivní část je abelovská grupa souhlasil. Pak se došlo ke GF(2), kdy jsem mu řekl něco o ireducibilních polynomech a už nic moc víc jsem nevěděl, tak jsem přímo řekl, že si nějaké to GF zkonstruujeme (zazvonil budík). Vybral jsem si polynom a začal konstruovat. U řekl, že to stačí a k čemu se to používá. Řekl jsem, že pro lineární zabezpečovací kódy, on mě usměrnil že to taky, ale že chce cyklické kódy. Tak jsem mu tam vysypal zbytek po dělení polynomem a to mu stačilo.
Celkem za C.
From <[link]> 
2. Otazka (předmět) (okruh): Teorie polí (6 - MAT)
Kdo me primarne zkousel: Švéda Miroslav, prof. Ing., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Pro mě jedna z nejhorších otázek, co jsem mohl dostat. Zachránilo mě to, že přede dveřmi toto téma rozebírali další kolegové. Naštěstí jsem si to vše zapamatoval a to jsem tam vše také řekl. Začal jsem tím, co jsem věděl sám. Řekl jsem, že Pole je vlastně abelovská grupa a pologrupa. Hned jsem ho napsal na tabuli a Švéda chtěl, abych detailně popsal ten zápis (K, +, 0, -, ., 1) -2,0,1,2,0 -- následně chtěl vztahy a vlastnosti. Popsal jsem vztahy, binární operace, asociativitu a vše kolem atd. (v tuto chvíli už jsem tušil, že to musí být na E). Snažil jsem se pořád mluvit. (No a to bylo tak vše, na co jsem si vzpomněl. Teď jsem říkal to, co jsem slyšel od kolegů na chodbě a měl v živé paměti) Tak jsem hned navázal na minimální pole, co to je. Švéda pak chtěl vědět, co je to GF. Chtěl abych mu napsal GF2. Jelikož už jsem nějak nevěděl, tak mě navigoval. Ať udělám nějaký vektor. Pak chtěl vztahy mezi vektory a polynomy. Pak ať ten vektor reprezentuju polynomem. (CRRR -- teď zazvonil budík, ale zkoušelo se furt dál) Pak prof. Švéda říkal, že se to používá v cyklických kódech, čehož jsem se hned chytl a něco k tomu řekl, ale po chvíli jsme přešli zase zpět. Řekl jsem o generování toho pole, kořeny, ireducibilní polynom, ... Dost mi v tom ale pomáhal a navigoval mě. Když viděl, že nevím, tak buď pomohl anebo jsme přešli jinam. Důležité bylo ale MLUVIT. Když jsem nevěděl, tak jsem to vyplnil větou typu "no, cyklické kódování ... další jsou konvoluční a lineární"...atd. Každopádně jsem při této otázce propotil sako. 
Pak pronesl "má někdo doplňující otázku? ... (5s ticho) ... OK, to mi stačí".
From <[link]> 