Cyklické grupy a grupy permutací

Podgrupy a Lagrangeova věta Cyklické (pod)grupy Grupy permutací

Cyklické grupy a grupy permutací

Jiří Velebil: A7B01MCS

5. prosince 2011: Cyklické grupy, permutace

1/26


Z minula: grupa je důležitý ADT Dnešní přednáška: hlubší pohled na strukturu konečných grup. Aplikace: 1

Řád prvku v grupě („logaritmováníÿ v grupách), Eulerova věta.

2

Grupy permutací, šifrovací stroj Enigma, Change Ringing.

3

A řada dalších aplikací. . .

Možná doplňující literatura: Ladislav Bican: Lineární algebra a geometrie, Academia, Praha 2002. Nathan Jacobson, Basic Algebra, vol I, Dover Publications, 2009.



2/26


Definice Ať hX , ?, e, (−)−1 i je grupa. Podmnožině W ⊆ X říkáme podgrupa, když pro každé x, y platí: 1

Jestliže x ∈ W a y ∈ W , pak x ? y ∈ W (uzavřenost W na operaci ?).

2

e ∈ W (uzavřenost W na nulární operaci e).

3

Jestliže x ∈ W , pak x −1 ∈ W (uzavřenost W na operaci (−)−1 ).

Příklad hZ, +, 0, −(−)i je grupa. Definujte pro přirozené číslo m množinu Wm = {km | k ∈ Z} Pak Wm je podgrupa hZ, +, 0, −(−)i. Jiří Velebil: A7B01MCS


3/26


Tvrzení (abstraktní počítání modulo) Ať W je podgrupa grupy hX , ?, e, (−)−1 i. Relace ∼W definovaná následovně x ∼W y iff x ? y −1 ∈ W je relace ekvivalence na X . Příklad Pro hZ, +, 0, −(−)i a Wm je x ∼Wm y

iff

x − y = km pro nějaké k ∈ Z

Tudíž pro m ≥ 2 je Z/∼Wm množina Zm . Z/∼W1 je jednoprvková množina a Z/∼W0 je množina Z. Poznámka Skutečné počítání modulo: faktorisace okruhu. Jiří Velebil: A7B01MCS


4/26


Lagrangeova věta Ať W je podgrupa konečné grupy hX , ?, e, (−)−1 i. Potom počet prvků W dělí počet prvků X . Důkaz. Ukážeme: pro a ∈ X platí: počet prvků [a]∼W = počet prvků W . Důvod: zobrazení f : [a]∼W → W , x 7→ a ? x −1 , je bijekce.



5/26


Tvrzení Ať hM, ?, ei je monoid. 0značte jako M ∗ množinu všech invertibilních prvků v M. Potom M ∗ je grupa vzhledem k operaci ?. Důkaz: 1 Uzavřenost M ∗ na operaci ?. Socks & Shoes Theorem: (x ? y )−1 = y −1 ? x −1 (součin invertibilních prvků je invertibilní). 2

3

Uzavřenost M ∗ na operaci e. e ∈ M ∗ , protože: e −1 = e (e je invertibilní prvek). Existence inversí: M ∗ je definována tak, že inverse v M ∗ existují, a platí: (x −1 )−1 = x (inverse invertibilního prvku je invertibilní).



6/26


Problém logaritmu 1

2

hZ∗8 , ·, 1, (−)−1 i je grupa invertibilních prvků v Z8 , prvky jsou 1, 3, 5, 7. Počítejme mocniny: 31 = 1, 32 = 1, atd. Tudíž: v hZ∗8 , ·, 1, (−)−1 i nelze „logaritmovatÿ se základem 3. hZ∗7 , ·, 1, (−)−1 i je grupa invertibilních prvků v Z7 , prvky jsou 1, 2, 3, 4, 5, 6. Počítejme mocniny: 30 = 1, 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1, 37 = 2, 38 = 6, . . .



7/26


Problém logaritmu 1

2

hZ∗8 , ·, 1, (−)−1 i je grupa invertibilních prvků v Z8 , prvky jsou 1, 3, 5, 7. Počítejme mocniny: 31 = 1, 32 = 1, atd. Tudíž: v hZ∗8 , ·, 1, (−)−1 i nelze „logaritmovatÿ se základem 3. hZ∗7 , ·, 1, (−)−1 i je grupa invertibilních prvků v Z7 , prvky jsou 1, 2, 3, 4, 5, 6. Počítejme mocniny: 30 = 1, 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 = 1, 37 = 2, 38 = 6, . . . Takže: např. „logaritmusÿ 2 se základem 3 v Z∗7 je 2, ale také 7. Logaritmus má periodu 5? Řešení: log3 2 = 2 v Z5 Jiří Velebil: A7B01MCS


7/26


Definice Grupa hX , ?, e, (−)−1 i je cyklická, když existuje g ∈ X (tzv. generátor) tak, že platí X = {g ?k | k ∈ Z} kde k-tá ?-mocnina x ?k prvku x je definována takto:  pro k = 0  e, ?k ?k x ?x , pro k ≥ 0 x =  ?(−k) −1 (x ) , pro k < 0 Příklad hZ, +, 0, −(−)i je cyklická grupa, číslo 1 je generátor. Každá grupa hZm , +, 0, −(−)i, m ≥ 2, je cyklická. Až na isomorfismus jiné konečné cyklické grupy nejsou. Jiří Velebil: A7B01MCS


8/26


Definice Ať hX , ?, e, (−)−1 i je konečná grupa, ať g ∈ X . Množině S(g ) = {g ?k | k ∈ N} říkáme cyklická podgrupa generovaná prvkem g . Řád prvku g je počet prvků podgrupy S(g ). Cyklické podgrupy aditivní grupy Zm hZm , +, 0, −(−)i je konečná cyklická grupa řádu m . Ať g ∈ Zm . 1

Řád prvku g je nejmenší kladné k ∈ N takové, že kg = 0, tj. kg = lcm(g , m).

2

Protože lcm(g , m) = gm/gcd(g , m), platí k = m/gcd(g , m).

3

Tedy S(g ) = Zm iff řád g je m iff gcd(g , m) = 1.

4

Existuje tedy ϕ(m) prvků v Zm , které mají řád m (tzv. primitivní elementy). Jiří Velebil: A7B01MCS


9/26


Příklad v aditivní grupě Z10 1

S(4) = {4, 8, 2, 6, 0} = 6 Z10 , tj. řád 4 je 5.

2

S(7) = {7, 4, 1, 8, 5, 2, 9, 6, 3, 0} = Z10 , tj. řád 7 je 10.

3

Existují ϕ(10) = 4 prvky řádu 10, konkrétně 1, 3, 7, 9.

4

Ostatní prvky mají řád menší. Konkrétně S(0) = {0}, S(5) = {0, 5} a S(2) = S(4) = S(6) = S(8) = {0, 2, 4, 6, 8}.

Tvrzení Pro každého dělitele d čísla m ≥ 2 má grupa hZm , +, 0, −(−)i právě jednu cyklickou podgrupu řádu d. Důsledek (Möbiův vzorec) Pro přirozené číslo m ≥ 2 platí: m =


P

{d|d dělí m} ϕ(d).


10/26


Příklad: „logaritmováníÿ v Z∗11 Generátor hZ∗11 , ·, 1, (−)−1 i je 7: e 7→ 7e v hZ∗11 , ·, 1, (−)−1 i 0 7→ 1 1 7→ 7 2 7→ 5 3 7→ 2 4 7→ 3 5 7→ 10 6 7→ 4 7 7→ 6 8 7→ 9 9 7→ 8 10 7→ 1

x 7→ log7 x v hZ10 , +, 0, −(−)i 1 7→ 0 7 7→ 1 5 7→ 2 2 7→ 3 3 7→ 4 10 7→ 5 4 7→ 6 6 7→ 7 9 7→ 8 8 7→ 9 1 7→ 10



11/26


Příklad: „logaritmováníÿ v Z∗11 (pokračování) e 7→ 7e je isomorfismus grup hZ∗11 , ·, 1, (−)−1 i a hZ10 , +, 0, −(−)i. Jednoduché aplikace: 1

Spočtěte 10−3 · 812 v Z∗11 . V Z10 : log7 (10−3 · 812 ) = −3 · log7 10 + 12 · log7 8 = −3 · 5 + 12 · 9 = −15 + 108 = 3 Tedy 10−3 · 812 = 73 = 2 v Z∗11 .

2

Vyřešte 3x = 10 v Z∗11 . Platí: log7 3 + log7 x = log7 10 v Z10 . Tedy: log7 x = log7 10 − log7 3 = 5 − 4 = 1 v Z10 . Tedy: x = 71 = 7 v Z∗11 .



12/26


Složitější aplikace řádu prvku Například Shorův faktorisační algoritmus: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, http://fr.arxiv.org/abs/quant-ph/9508027 Faktorisace čísel na kvantovém počítači v polynomiálním čase. Viz předmět Kvantové počítání, Libor Nentvich & Jiří Velebil.



13/26


Eulerova věta v konečných grupách Ať hX , ?, e, (−)−1 i je libovolná konečná grupa. Označme jako n počet prvků množiny X . Pak pro každé a ∈ X platí a?n = e Důkaz: Vezměme libovolné a ∈ X . Ať řád a je m. Tedy a?m = e. Lagrangeova věta: m | n. Tedy n = m · k, pro nějaké k. Takže: x ?n = (x ?m )?k = e ?k = e.



14/26


Poznámka: Eulerova věta a cykličnost grup Ať hX , ?, e, (−)−1 i je konečná grupa. Označme jako n počet prvků množiny X . 1

2

3

Víme: pro každé a ∈ X platí a?n = e (Eulerova věta v konečných grupách). Exponent n nemusí být nejmenší takové k, že platí x ?k = e. Příklad: v hZ∗8 , ·, 1, (−)−1 i je 11 = 1, 32 = 1, 52 = 1, 72 = 1, ale ϕ(8) = 4. To je: exponent v Eulerově větě nemusí být řád prvku. Ale: Pokud v hX , ?, e, (−)−1 i existuje prvek a řádu n, pak grupa hX , ?, e, (−)−1 i je isomorfní grupě hZn , +, 0, −(−)i. Důkaz: víme S(a) = X . Pak postupujeme jako při definici „logaritmuÿ.



15/26


Permutace a šifrovací stroj Enigma — nepovinné Permutace a vyzvánění zvonů — nepovinné

Definice Ať n = {1, . . . , n}, n ≥ 1. Bijekci f : n → n říkáme permutace na n. Příklad — string diagrams pro permutace Permutaci f (1) = 3, f (2) = 2, f (3) = 4, f (4) = 1 znázorníme buď jako matici 1 2 3 4 3 2 4 1 nebo jako string diagram 1

2

3

4

1

2

3

4



16/26



Příklad — skládání permutací 1 2 3 4 1 2 3 4 Složení f = ag= je 2 4 1 3 3 2 4 1 1 2 3 4 1 2 3 4 1 2

f ?g = 1

2

3

4 =

1

2 3 4 1 1 2 3 4 neboli f ? g = 2 1 3 4 Jiří Velebil: A7B01MCS

3

4

3

4

=

2

3

4

1

2


17/26



Tvrzení Označte jako Sn množinu všech permutací na n = {1, . . . , n}. Potom Sn = hSn , ?, id, (−)−1 i tvoří grupu. Budeme jí říkat grupa permutací (nebo symetrická grupa). Cayleyho representace konečných grup Každá konečná grupa řádu n je isomorfní podgrupě grupy Sn . Důkaz: Ať hX , ?, e, (−)−1 i je grupa o prvcích {x1 , . . . , xn }. Pak zobrazení Rxi : X → X ,

x 7→ x ? xi

je bijekce pro každé xi (vzpomeňte na Eulerovu větu). Zobrazení Rxi určuje právě jednu permutaci fi na množině n. Zobrazení xi 7→ fi je hledaný isomorfismus grupy hX , ?, e, (−)−1 i s podgrupou grupy Sn . Jiří Velebil: A7B01MCS


18/26



Definice Ať x1 , x2 jsou různé prvky n. Transpozice (x1 x2 ) je taková permutace, že x1 7→ x2 a x2 7→ x1 , ostatní prvky nechává na místě: 1 . . . x1 . . . x 2 . . .

n

1 . . . x1 . . . x2 . . .

n



19/26



Definice Ať x1 , x2 , . . . , xr jsou navzájem různé prvky n. r -cyklus (x1 x2 . . . xr ) je permutace (x1 x2 ) ? (x1 x3 ) ? · · · ? (x1 xr ) Dvěma cyklům (x1 x2 . . . xr ), (y1 y2 . . . ys ) říkáme disjunktní, pokud {x1 , x2 , . . . , xr } ∩ {y1 , y2 , . . . , ys } = ∅. Tvrzení 1 Disjunktní cykly komutují, tj. f ? g = g ? f , pro disjunktní cykly f a g . 2

Řád cyklu (x1 , . . . , xr ) je r .

3

Každou permutaci lze vyjádřit jako součin transpozic. (Dokonce jako součin transpozic sousedních prvků.)

4

Každou permutaci lze zapsat jako součin disjunktních cyklů. Jiří Velebil: A7B01MCS


20/26


Příklad Permutace


1 2 3 4 5 6 7 8 2 4 3 5 1 6 8 7

je součin (1 2 4 5) ? (3) ? (6) ? (7 8) = (1 2 4 5) ? (7 8). Tvrzení Ať f = f1 ? f2 ? · · · ? fk je rozklad permutace na disjunktní cykly. Pak řád f je nejmenší společný násobek řádů f1 , . . . , fk .



21/26



Definide Permutaci f nazveme lichou (resp. sudou), pokud ji lze vyjádřit jako součin lichého (resp. sudého) počtu transpozic. Poznámka Identická permutace id je sudá. Věta Každá permutace je buď lichá nebo sudá (nikdy ne obojí). Tj. liché permutace jdou vyjádřit pouze jako součin lichého počtu transpozic a sudé permutace sudého počtu transpozic.



22/26



Enigma Enigma je šifrovací přístroj používající symetrickou polyalfabetickou šifru. Chod přístroje je určen: 1

3 rotory — permutace %1 , %2 , %3 , počáteční nastavení a nastavení zarážek,

2

Plugboard — součin disjunktních transpozic τ ,

3

Reflektor — součin disjunktních transpozic %,

Viz např. http://www.cryptomuseum.com/crypto/enigma/



23/26



To znamená, že šifrování se odehrává permutací j-té písmeno zprávy je zašifrováno následovně: εj

= τ ? (σ i1 ? %1 ? σ −i1 ) ? (σ i2 ? %2 ? σ −i2 ) ? (σ i3 ? %3 ? σ −i3 ) ? % ? −i2 −i1 −i3 ) (σ i3 ? %−1 ) ? (σ i2 ? %−1 ) ? (σ i1 ? %−1 1 ?σ 3 ?σ 2 ?σ

? τ kde σ = (ABCD · · · Z ) a i1 , i2 , i3 závisí na j a nastavení rotorů. Jiří Velebil: A7B01MCS


24/26



Change ringing Metoda vyzvánění zvonů ve Velké Británii (ze 17. století). Hrají se permutace, „notový zápisÿ je string diagram

http://en.wikipedia.org/wiki/Change ringing Jiří Velebil: A7B01MCS


25/26



Change ringing Viz také kniha Dorothy L. Sayers, The Nine Tailors, 1934 česky: Devět hran, Svoboda 1994 ve které Lord Peter Wimsey znalostí change ringing vyřeší vraždu. Název detektivky poukazuje na metodu zvonění umíráčku.



26/26

Cyklické grupy a grupy permutací

Recommend Documents