Literatura Součiny grup Rozklady podle podgrup Normální podgrupy ooooo OOOOO oooooooooo Diskrétní matematika B - 7. týden Teorie grup Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Rozklady podle podgrup ooooo Obsah přednášky Q Součiny grup Rozklady podle podgrup Q Normálni podgrupy • Hlavní věty o grupách Literatura Součiny grup ooooo Rozklady podle podgrup OOOOO Normální podgrupy oooooooooo • Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). • Nathan Carter. Visual Group Theory, The Mathematical Association of America, 2009, 297 s. (Viz web). Literatura Součiny grup Rozklady podle podgrup Normální podgrupy •oooo ooooo oooooooooo Definice Pro každé dvě grupy (G, •), (H, o) definujeme součin grup (G x H, *) takto: Jako množina je G x H skutečně (kartézský) součin, na kterém definujeme grupové násobení po složkách, tj. (a,x) * (b,y) = (a ■ b,xoy). Poznámka Rozmyslete si, že jde o grupu a že součin komutativních grup je zase komutativní! Zobrazení Pg : G x H 3 (a,x) 4 a £ G, ph : G x H 9 (a,x) 4 x é H jsou surjektivní homomorfismy (tzv. projekce) s jádry kerpG = {(eG,x); x e H} kerpH = {{a, eH)\a G G}. Literatura Součiny grup o»ooo Rozklady podle podgrup OOOOO Normální podgrupy oooooooooo Příklad (1) Grupa je izomorfní součinu Z2 x Z3. Toto lze nahlédnout bud' geometrickou úvahou (prostřednictvím grup symetrií v rovině) nebo přímou konstrukcí izomorfismu. V aditivní notaci vypadá izomorfismus takto: [0]6->([0]2,[0]3), [l]e ^ ([1]2, [2]3) [2]6^([0]2,[1]3), [3]6 m- ([1]2, [0]3) KW([0]2,[2]3), [5]6 m. ([1]2) [1]3) (2) Dihedrální grupa D% (tj. grupa symetrií čtverce, (r, s\ŕ = 1, s2 = 1, srs = r_1) ) není izomorfní součinu Z2 x Z4, přestože mají stejný počet prvků (D% není komutativní). Literatura Součiny grup oo»oo Rozklady podle podgrup ooooo Normální podgrupy oooooooooo e re Rinisninssnsnn Předchozí příklad je speciálním případem tzv. Čínské zbytkové věty. ' Věta ^ Jsou-li k, m G N nesoudělná, pak a obecněji Věta Jsou-li m\, ni2, • • • , mk po dvou nesoudělná, pak (Znm.,+) ^ (Zmi,+) x (Zm2,+) x ••• x (Zm/t,+). Literatura Součiny grup ooo»o Rozklady podle podgrup ooooo Normální podgrupy oooooooooo Sestrojíme požadovaný izomorfismus f. Označme m = flj mi a Pro libovolné [a]m G Zm položme r([a]m) = ([a]mu ■ ■ ■, [a]mk)- Snadno se ověří, že jde o injektivní homomorfismus (co je jádrem?). Zbývá dokázat, že jde i o surjekci, tedy, že libovolný prvek ([al]mi, • • •, [3k] mít) £ (^mi> + ) x • • • x {%mk, +) je obrazem nějakého a G Zm. To je ale totéž jako najít a G Z takové, že a = ai (mod m{),... a = a^ (mod m^), což se udělá malým (ale šikovným) trikem:1 Pro libovolné 1 < / < k položme n, = m/m-, a protože (m,-, n,) = 1 (zde jsme využili nesoudělnost po dvou), najdeme podle Bezoutovy věty u; a v, tak, že u;m; + v,n; = 1, tj. v,n; = 1 (mod m,-). Hledané a pak najdeme jako a = V" a/i/7/7/. 1A nešlo by to ještě šikovněji? Pokud nám stačí existence izomorfismu, tak qtaří i7Ít toho 7P inipktix/nf 7nhra7pnf mp7Í mnnŤinami o qtpinpm nnřtn nr\/ků Literatura Součiny grup oooo» Rozklady podle podgrup ooooo Normální podgrupy oooooooooo Libovolný prvek a v grupě G je obsažen v minimální podgrupě {e = a°, a = a1, a2, s3,... }, 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á, je-li celé G generované nějakým svým prvkem a výše uvedeným způsobem. Zjistit pro konkrétní cyklickou grupu generátor je obecně obtížný problém. I při znalosti generátoru g G G je ale obecně velkým problémem zjistit pro dané a G G číslo k, pro které gk = a (tzv. problém diskrétního logaritmu). Z definice přímo vyplývá, že každá cyklická grupa je izomorfní bud' grupě celých čísel Z (pokud je nekonečná) nebo některé grupě zbytkových tříd (Z^,+) (když je konečná). Literatura Součiny grup ooooo Rozklady podle podgrup •oooo Normální podgrupy oooooooooo Uvažme grupu G a její podgrupu H. Na množině prvků grupy G definujeme relaci a ~h b jestliže b^1 ■ a G H, tj. a-1 • b G H (tyto dvě podmínky jsou zřejmě ekvivalentní, není to ale totéž jako podmínky a ■ b^1 nebo b • a-1). Je to relace ekvivalence: • a-1 • a = e G H, • je-li b^1 ■ a = h G H, potom a-1 • b = (b^1 ■ a)-1 = h'1 G H, • je-li c-1 • b G H a zároveň je Ď-1 • a G H, potom c-1 • a = c-1 • b • b-1 • a G H. Literatura Součiny grup ooooo Rozklady podle podgrup o#ooo Normální podgrupy oooooooooo Celá grupa G se tedy 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 (zřejmě a 6 a • H) a skutečně platí, že a ■ H = {a ■ h; h e 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 6 H. Proto H\G = {H ■ a; a £ G}. Literatura Součiny grup ooooo Rozklady podle podgrup oo»oo Normální podgrupy oooooooooo Věta Pro třídy rozkladu grupy platí: O Levé a pravé třídy rozkladu podle podgrupy H < G splývají právě tehdy, když pro každé a G G, h G H platí a ■ h ■ a-1 G H. & Všechny třídy (levé i pravé) mají shodnou mohutnost jako podgrupa H. O Zobrazení a ■ H i-> H ■ a-1 zadává bijekci mezi levými a pravými třídami rozkladu G podle H. Poznámka Rozmyslete si, proč je v posledním tvrzení a a nikoliv a. Literatura Součiny grup ooooo Rozklady podle podgrup ooo»o Normální podgrupy oooooooooo Důsledek Necht G je konečná grupa s n prvky (tj. G je řádu n), H její podgrupa. Potom O Mohutnost n = \G\ je součinem mohutnosti H a mohutnosti G/H, tj. \G\ = \G/H\ ■ \H\ 0 Přirozené číslo \H\ je dělitelem čísla n. 0 Je-li a G G prvek řádu k, pak k dělí n. O pro každé a G G je an = e. O je-li mohutnost grupy G prvočíslo p , pak je G izomorfní cyklické grupě Zp. Druhému tvrzení se říkává Lagrangeova věta, předposlednímu malá Fermatova věta (častěji ovšem ve speciálním případě grupy (ZpV))- Literatura Součiny grup ooooo Rozklady podle podgrup oooo» Normální podgrupy oooooooooo Snadnými důsledky předchozího jsou následující věty: Věta (Malá Fermatova) Pro libovolné prvočíslo p a číslo a e Z nedělitelné p platí ap- 1 = 1 (mod p). Věta (Eulerova) "* Pro libovolné m e N a každé a G Z splňující (a, m) = 1 platí 3^m) = 1 (mod m). Součiny grup Rozklady podle podgrup Normální podgrupy OOOOO OOOOO »000000000 Normální podgrupy Podgrupy H, pro které platí, že a ■ h ■ a 6 H pro všechna a £ G, h 6 H, se nazývají normální podgrupy (značíme H < G). Snadno se nahlédne platnost následujícího Podgrupa H je normální právě tehdy, když pro každé a £ G platí a ■ H = H ■ a (jinými slovy: levý rozklad G podle podgrupy H je shodný s pravým rozkladem). Důsledek • 1 < G, G < G • V komutativní grupě je každá podgrupa normální. • Je-li H podgrupa konečné grupy G, kde \ H\ = \ G\/2, pak je H normální. Literatura Součiny grup ooooo Rozklady podle podgrup OOOOO Normální podgrupy o«oooooooo Příklad • Dihedrální grupa D2n má vždy normální podgrupu izomorfní Z„. Levý (i pravý) rozklad podle této podgrupy je dvojprvková množina {Z„,s • Z„}. • (f2) = {'d, ľ2} je normální podgrupa v D$. Levý rozklad podle této podgrupy je čtyřprvková množina {{id, r2},{r,r3},{s,sr2},{sr,sr3}}. Literatura Součiny grup ooooo Rozklady podle podgrup OOOOO Normální podgrupy oo»ooooooo 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) ■ (ZT1 -h-b)-h')-H. Věta Je-li H normálnípodgrupou G, tvoří rozklad G/H s násobením definovaným prostřednictvím reprezentantů grupu. Je-li G komutativní, je i G/H komutativní. Příklad nZ = {na; a £ Z} c Z zadává pro libovolné íiéN podgrupu Z a její faktorgrupou (až na izomorfismus) je aditivní grupa zbytkových tříd Z„ (přitom pro n = 1 jde o triviální grupu). Literatura Součiny grup ooooo Rozklady podle podgrup OOOOO Normální podgrupy ooo«oooooo Příklad Nechť G je grupa řádu 14, která má normální podgrupu řádu 2. Dokažte, že G je komutativní. Řešení Označme danou normální podgrupu N. Pak G/A/ je grupa a její řád je | G/N\ = jj^j = 7. Podle Lagrangeovy věty je řád každého jejího prvku bud' 1 nebo 7. To ovšem znamená, že řád aspoň jednoho prvku je 7, a tedy že G/A/ je cyklická. Nechť N = {e, n}, kde e je neutrální prvek G a generátor grupy G/A/ je [a]. Protože N je normální, je ana^1 G A/, ale protože ana^1 = e n = e, musí být ana^1 = n, tedy na = an. Protože [a] generuje G/A/, je každý prvek G/A/ tvaru [a]k, k = 0,... ,6, tedy [ak\. Každý prvek G je tak tvaru ak, nebo akn, a protože prvky a a n spolu komutují, komutují spolu libovolné prvky G. [Později uvidíme, že nutně G ^ Zi4.] Literatura Součiny grup Rozklady podle podgrup Normální podgrupy ooooo OOOOO oooo»ooooo 1 /"\ /"l V\ /~\ /"l 1 I , /"* \~\ /~\ 1 t~\ v /~\ f* "l~ /"\ 1 (T V 1 1 ľ*N\ / jeanoau( cne ^prosiej grupy Naproti tomu existují i grupy, které nemají žádné vlastní normální podgrupy, takové grupy se nazývají jednoduché (simple). Znalost těchto grup je velmi důležitá, protože z nich je v jistém smyslu složena každá konečná grupa. Mezi konečnými komutativními grupami je situace skutečně jednoduchá - prostými jsou pouze grupy Zp pro prvočíselné p (podobně i každá prostá grupa lichého řádu je nutně izomorfní Zp - důkaz tohoto faktu je ale značně netriviální2). V nekomutativním případě je situace výrazně složitější - až v roce 1982 (samozřejmě s pomocí počítačů) se podařilo završit úsilí o úplnou klasifikaci jednoduchých grup. Například alternující grupa An (tj. podgrupa sudých permutací grupy Z„) je jednoduchá pro n > 5 , z čehož (s pomocí tzv. Galoisovy teorie) plyne nemožnost existence obecných vzorců pro kořeny polynomů stupně 5 a vyššího. 2255 stran "tvrdé" matematiky Součiny grup Rozklady podle podgrup Normální podgrupy ooooo ooooo ooooo»oooo Charakterizace konečných komutativních grup Věta (Hlavní věta konečných komutativních grup) Je-li G konečná komutativní grupa, pak platí: pro vhodná ri\,..., n^ 6 N \ {1} splňující nl+i \ n, pro 1 < / < k — 1. Tento rozklad je přitom jednoznačný. Důsledek Každé prvočíslo p, dělící řád grupy G, dělí n^. Je-li n součinem různých prvočísel, pak jedinou komutativní grupou řádu n je (až na izomorfismus) cyklická grupa Z„. Literatura Součiny grup Rozklady podle podgrup Normální podgrupy ooooo OOOOO oooooo»ooo Příklad Určete všechny komutativní grupy řádu 180. Řešení Protože 180 = 22 • 32 • 5, dostáváme, že možné hodnoty rt\ jsou ni = 22 • 32 • 5, 22 • 3 • 5, 2 • 32 • 5 nebo 2-3-5. Pro rt\ = 2 • 3 • 5 dostáváme možné hodnoty r>2 = 2, 3 nebo 6. V prvních dvou případech dostáváme díky podmínce nj | r>2 spor. Jediná komutativní grupa řádu 6 je proto v tomto případě dostáváme grupu z30 x Z6. Ve zbylých (ještě jednodušších) případech dostáváme další komutativní grupy řádu 180: ZgQ x Z3,Zgo x z2,Zi80- Literatura Součiny grup ooooo Rozklady podle podgrup OOOOO Normální podgrupy ooooooo»oo Věta (Cauchy) Je-li konečná grupa G řádu dělitelného prvočíslem p, pak obsahuje prvek řádu p. Důkaz. Důkaz není úplně triviální, naznačme jej alespoň v případě komutativní grupy G. Budeme postupovat úplnou matematickou indukcí. Je tedy \ G\ > 1. Pokud \ G\ = p, jsme hotovi. Bud' nyní \G\ > p a x G G libovolný. Pokud p dělí řád r prvku x, tj. r = p ■ n, pak p je řádem prvku x". Nechť tedy p f r a označme N = (x). Zřejmě N < G a | G/N\ < \ G\. Protože p f \N\, nutně p | | G/N\ a můžeme využít indukční předpoklad. V grupě G/N tedy existuje prvek y/V řádu p (odkud y ^ A/,yp G N), odkud dostáváme (yp) 7^ (y), zejména je tedy řád yp menší než řád y. Ze znalosti vztahu pro řád mocniny (viz teorie čísel) dostáváme, že řád y je násobkem p a jsme v situaci z předchozího odstavce. □ Literatura Součiny grup Rozklady podle podgrup Normální podgrupy ooooo OOOOO oooooooo»o Jordan-h lólderova věta Jak jsme viděli, v některých případech jsme schopni z informací o normální podgrupě N < G a o faktorgrupě G/N získat informaci o celé grupě G. Jednoduché grupy, které tento proces nepřipouštějí, jsou základními stavebními kameny grup (analogie prvočísel). Definice Posloupnost podgrup grupy G {e} = N0 < A/i <■■■< Nk = G se nazývá kompoziční řada (též J.-H. řada), pokud N, < A//+i a Ni+i/Nj je prostá. Příklad Pro Dg máme např. kompoziční řady {e} < (s) < (s, r2) < D% a {e} < (r2) < (r) < D8. Literatura Součiny grup ooooo Rozklady podle podgrup OOOOO Normální podgrupy ooooooooo# Věta (Jordan-Hólderova) Konečná grupa má vždy kompoziční řadu, která je jednoznačně určená až na izomorfismus faktorů (tj. počet členů dvou takových řad je stejný a příslušné faktorgrupy jsou izomorfní.