Sbírka příkladů z odborné soutěže pro předmět Algebra I konané v semestru Jaro 2014 Autorský kolektiv: Radan Kučera, Ondřej Klíma a Jaromír Kuben Příklady jsou určeny těm studentům, kteří mají hlubší zájem o algebru. Jsou tedy zamýšleny nejen pro studenty Obecné matematiky nebo studenty Statistiky a analýzy dat, ale také pro všechny ostatní studenty včetně studentů učitelství matematiky, tedy bez ohledu na studijní obor - zkrátka pro všechny, kterým je blízký abstraktní styl myšlení a kteří budou, například při volbě tématu bakalářské práce, inklinovat ke studiu abstraktních matematických oborů. První část sbírky obsahuje zadání 10 příkladů, jež byly v semestru Jaro 2014 pravidelně zadávány v rámci soutěže podpořené FRMU a jsou proto označeny jako kolo 1 až 10. Druhá část sestává ze vzorových řešení k jednotlivým kolům, které jsou někdy rozšířeny o zadání souvisejících příkladů řešených na semináři, který byl nepovinnou součástí soutěže. U každého kola jsou v úvodu uvedeny doporučené znalosti, odkazy míří na přednášky o grupách probírané v Algebře I v jarním semestru 2014; tyto přednášky jsou k dispozici na stránce https://is.muni.cz/el/1431/jaro2014/M2150/um/Algebra2014grupy.pdf. 1 Část I — Zadání 2 1. kolo — Zápis permutací pomocí druhých mocnin Doporučené znalosti: permutace - po str. 9 v přednášce. Zadání: Buď n > 1 přirozené číslo, pro které uvažujme permutační grupu (8n,o). Pro libovolnou permutaci a G Sn označme ri( 1 označme ľfc( 2, proto se v zadání vyhýbáme pojmu „cyklus délky jedna". Pro první seznámení s použitými pojmy položme n = 8 a uvažme permutaci a = (l,2)(4,5,6,7) G S8. Pro tuto permutaci ihned vidíme, že ^(a) = 1 a r4(a) = 1. Dále ri(a) = 2, protože prvky 3 a 8 se zobrazují v permutaci a samy na sebe a každý z nich je tedy pevným bodem permutace a. Pro ostatní k je potom hodnota ^(a) rovna 0. Proto vidíme, že rovnost v části a) platí: 1-2 + 2-1+4-1 =8. Podle definice funkce r je dále r{a) = 4. Odtud dostáváme, že hodnota (—1)8~4 v části b) je skutečně rovna paritě premutace a, která je sudou permutací. Poznamenejme ještě, že pro permutaci a vhodná permutace r v části c) neexistuje, ovšem dvojice permutací r, p v části d) naopak existuje. Při práci s paritou nemusíte používat přímo definici, ale můžete využít některý ekvivalentní způsob výpočtu, který se používá ve skriptech nebo byl dokázán na přednášce. Při řešení se snažte příslušné použité věty z teorie vhodně citovat. (Např. „dle základní definice", „dle věty číslo x.y ze skript", „dle poznámky na straně x ze slajdů k přednášce" apod.) Druhou mocninou permutace r použitou v částech c) a d) se rozumí, v souladu s obvyklým značením v teorii grup, permutace tot. Řešení - str. 16. 3 2. kolo — Exponent permutační grupy Doporučené znalosti: řád prvků a exponent grupy - po str. 28 v přednášce. Zadání: a) (2 body) Určete, která komplexní čísla a mají v grupě (C*, •) konečný řád. b) (2 body) Pro libovolné přirozené číslo n určete, kolik existuje v grupě (C*, •) prvků řádu n. c) (3 body) Pro každé přirozené číslo n < 12 zjistěte, jaký největší řád může mít prvek grupy (Sn, o), a napište jeden prvek, který tento maximální řád má. Pro tato přirozená čísla n < 12 spočítejte také exponent grupy (Sn,o). d) (3 body) Pro libovolné přirozené číslo ti označme en exponent grupy (Sn,o). Nalezněte vhodný vzorec popisující rozklad čísla en na součin prvočísel. Nalezený vzorec dokažte. Komentář: Protože se někdy objevuje i jiná definice, připomeňme, že jsme definovali přirozená čísla jako kladná celá čísla, nulu tedy nepovažujeme za přirozené číslo. Na přednášce jsme definovali množinu C* jako množinu všech nenulových komplexních čísel, tedy (C*, •) je grupa na této množině vzhledem k operaci násobení komplexních čísel. Pro libovolné přirozené číslo n označme mn největší z řádů prvků grupy (Sn, o). Podle definice je (§i,o) grupa všech bijekcí na množině {1}, tedy Si = {id}. Jediný prvek této grupy, identita, má tedy řád m\ = 1, exponent této grupy je také e\ = 1. Vaším úkolem v části c) je určit největší možný řád mn prvku i exponent en grupy (Sn, o) pro všechna přirozená n < 12. Naproti tomu v části d) máte najít vzorec jen pro 6n, nikoli pro mri. Připomeňme ještě Moivreovu větu, která by mohla být při řešení užitečná. Každé nenulové komplexní číslo z lze psát ve tvaru z = r ■ (cos a + i sin a) pro vhodná r G M, r > 0, a G M, přičemž r = \z\ je dáno jednoznačně a a je dáno jednoznačně až na přičtení celočíselného násobku 2tv. Pak pro libovolné celé číslo n platí z =r ■ [cos na + i svária). Řešení - str. 18. 4 3. kolo — Grupy s exponentem 2 Doporučené znalosti: exponent konečné grupy a homomorfismus grup - po str. 36 v přednášce. Zadání: a) (1 bod) Nechť p : G —> H je surjektivní homomorfismus konečných grup. Dokažte, že pokud má grupa G exponent 2, potom je exponent grupy H roven 1 nebo 2. b) (1 bod) Dokažte, že každá konečná grupa s exponentem 2 je komutativní. c) (4 body) Nechť man jsou přirozená čísla. Uvažujme předpis tp : Z^ ->• Z*, p{[a]m) = [a]n, kde a G Z. Dokažte, že tento předpis definuje korektně zobrazení p : Z^ —> Z* právě tehdy, když n \ m. Dále dokažte, že za tohoto předpokladu je p surjektivní homomorfismus grupy (Z^, •) do grupy (Z*, •)• d) (2 body) Určete, pro které mocniny prvočísel n = pk, kde p je prvočíslo a A: je číslo přirozené, má grupa (Z*, •) exponent 2. e) (2 body) Určete všechna přirozená čísla n taková, že grupa (Z*, •) má exponent 2. Komentář: Pro zisk kladného počtu bodů není nezbytně nutné odevzdávat kompletní řešení jednotlivých úloh. Například v části c) je třeba dokázat více faktů a za každý z nich lze získat nějaké body. Zde důkaz nejobtížnější části, tj. surjektivity zobrazení p, je možné provést například vhodným využitím tzv. čínské zbytkové věty. Tato věta říká, že pro libovolná nesoudělná přirozená čísla kala libovolná celá čísla a, b existuje celé číslo c takové, že [c]k = [a]k a [c]i = [b]i. Navíc je toto c určeno jednoznačně modulo kí. (Jinými slovy [a]fc n [6]^ = [c]^.) Její důkaz plyne okamžitě z důkazu věty na straně 21 slajdů z přednášky, neboť jediné tvrzení, které potřebujeme, je fakt, že tam definované zobrazení / je bijektivní. Proto čínskou zbytkovou větu již nemusíte dokazovat, ale můžete ji použít při důkaze v části c) - i se znalostí této nápovědy není úplně jednoduché surjektivitu zobrazení p uvidět. Podobně se nebojte v řešení jedné části zadání použít tvrzení z jiné části, přestože jste potřebné tvrzení sami nedokázali. Řešení - str. 20. 5 4. kolo — Maximální podgrupy v permutačních grupách Doporučené znalosti: podgrupy a Lagrangeova věta - po str. 40 v přednášce. Zadání: Řekneme, že podgrupa H grupy G je maximální, pokud H 7^ G a zároveň neexistuje podgrupa M grupy G s vlastnostmi HCM&H^M^G. a) (2 body) Nechť /: G± —> G2 je surjektivní homomorfismus grup a H < G± je maximální podgrupa grupy G± taková, že ker / C H. Dokažte, že potom f(H) je maximální podgrupa grupy G2- b) (2 body) Nechť /: G± —> G2 je surjektivní homomorfismus grup & K < G2 je maximální podgrupa grupy G2. Dokažte, že potom /_1(.K') je maximální podgrupa grupy G\. c) (1 bod) Pro libovolné n £ N, n > 2 ukažte, že libovolná podgrupa grupy Sn, která obsahuje některou lichou permutaci, má sudý počet prvků. d) (1 bod) Pro libovolné n G N, n > 4 dokažte, že každá maximálni podgrupa Sn má sudý počet prvků. e) (4 body) Nechť n G N, n > 2. Hráči A a B hrají následující hru: hráči střídavě vybírají prvky grupy Sn (v každém tahu vždy jeden prvek), přičemž nelze vybrat prvek, který už byl vybrán dříve (tzn. jde o výběr bez vracení). Jako první vybírá hráč A. Hra končí v momentě, kdy množina všech vybraných prvků generuje celou grupu Sn. Hráč, který vybíral naposledy, prohrává, ten druhý vyhrává. a) Dokažte, že pro n = 2 a n = 3 má hráč A vítěznou strategii. b) Dokažte, že pro n > 4 má hráč B vítěznou strategii. Komentář: Nemusíte odevzdávat kompletní řešení jednotlivých úloh - například v části e) se bude hodnotit i dokázání jednotlivých případů. Lze také řešit pouze jednotlivé úlohy - můžete například řešit pouze části a) nebo b), jež nijak nesouvisí se zbývajícími částmi. Pojem maximální podgrupa je samozřejmě motivován terminologií z uspořádaných množin. Uspořádanou množinou, která se zde uvažuje, je množina všech podgrup grupy G. Zde je evidentně největším, a tudíž jediným maximálním prvkem sama grupa G. Toto triviální pozorování vede k otázce, co se stane, když tento prvek z uspořádané množiny odstraníme. Proto se uvažují pouze tzv. vlastní podgrupy grupy G (tedy podgrupy grupy G různé od G) a mezi nimi nás pak zajímají maximální prvky v uspořádnání inkluzí. Proto bychom správně měli definovat pojem maximální vlastní podgrupa, nicméně slůvko vlastní se v této definici vypouští, neboť termín pouze zbytečně prodlužuje. Poznamenejme ještě, že pro některé (nekonečné) grupy maximální podgrupy neexistují. V našem případě, vzhledem ke konečnosti uvažovaných grup, můžeme dokonce tvrdit, že pro libovolnou vlastní podgrupu grupy Sn existuje maximální podgrupa, která ji obsahuje. Předchozí odstavec tedy můžeme shrnout: maximální podgrupy jsou právě ty, které jsou v uspořádané množině všech podgrup těsně pod největší podgrupou G. Řešení - str. 21. 6 5. kolo — Podgrupy Doporučené znalosti: rozklady grup a normální podgrupy - po str. 43 v přednášce. Zadání: a) (2 body) Nechť (G, •) je libovolná grupa a X, Y jsou libovolné podmnožiny nosné množiny G grupy (G, •). Zjistěte, které inkluze (i) mezi podmnožinami (X) D (Y) a (X D Y) množiny G (ii) mezi podmnožinami ((X) U (Y)} a (X U Y) množiny G jsou obecně platné, tj. platí pro každé podmnožiny X, Y v každé grupě (G, •). b) (2 body) Nechť G je libovolná grupa a H je její podgrupa taková, že index podgrupy H v grupě G je roven dvěma. Dokažte, že H je normální podgrupa grupy G. c) (3 body) Nechť G je libovolná grupa a H je její normální podgrupa, která je cyklická. Dokažte, že libovolná podgrupa K podgrupy H je normální podgrupa grupy G. d) (3 body) Nechť 1Z je libovolný rozklad nosné množiny grupy (G, •) takový, že pro každý prvek g (z G a každou třídu rozkladu A £ 1Z platí {g ■ a; a £ A} G 1Z. Dokažte, že rozklad 1Z je rozkladem grupy G podle vhodné podgrupy H. Komentář: Úloha a) se týká čtyř možných inkluzí, z nichž každou máte buď obecně dokázat anebo naopak vyvrátit nějakým konkrétním příkladem. Uvědomte si, že jsme dokazovali, že průnik podgrup grupy G je podgrupa grupy G, a že tedy všechny čtyři zmiňované podmnožiny jsou podgrupy. Také se Vám může hodit následující postřeh plynoucí ihned z definice podgrupy (M) grupy G generované množinou M: pro každou podgrupu H grupy G jsou výroky M C H a (M) C H ekvivalentní (promyslete si proč). Řešení - str. 22. 7 6. kolo — Polopřímý součin grup Doporučené znalosti: věty o faktorových grupách a Burnsidovo lemma - po str. 55 v přednášce. Zadání: a) (7 bodů) Připomeňme, že Aut(H) značí grupu automorfismů grupy H. (i) Nechť {H, •) a {K, •) jsou grupy, tp : K —> Aut (H) homomorfismus grup. Na množině G = H x K definujeme operaci • takto: pro libovolné hi,h2 G H a libovolné k±, k2 G K klademe Ol, fci) • {h2, k2) = {hi ■ {(p{ki){h2)), h ■ k2). Dokažte, že {G,-) je grupa. Dále dokažte, že její podmnožiny {{h,l): h G H} resp. {(1, k): k (z K} tvoří podgrupy grupy G izomorfní s H resp. K, a navíc ta první z nich je normálni podgrupa grupy G. Grupu {G, •) definovanou v části (i) nazýváme polopřímý součin grup {H, •) a {K, •) vzhledem k akci p a značíme ji H xv K. (ii) Nechť n G N, n > 3. Dokažte, že dihedrální grupa Dn je izomorfní grupě Zn x(pZ2, kde (p: 7j2 —> Aut(Zn) je dáno vztahem ^(ŕbXHn) = [( —l)ř'a]n Pro všechna a, b G Z. (iii) Uvažujme polopřímý součin grup Zx(ŕZ2, kde akce tp: Z2 —> Aut(Z) je určena vztahem Z dané předpisem /((a, [6)2)) = 2a + 1 ^2 1-> pro všechna a, 6 G Z. Dokažte, že / je izomorfismus grupy Z x^ Z2 a grupy (Z, o), v níž pro libovolné x, y G Z je definováno x o y = x + ( — l^y. b) (3 body) Nechť konečná grupa G má tranzitivní akci (definice viz níže) na konečné množině X, kde \X\ > 2, je tedy dán homomorfismus tp : G —> S{X). Dokažte, že potom existuje o G G takové, že pro všechna x G A platí Aut{H) zadává akci grupy K na množině H, v níž je dokonce každá užitá permutace automorfismem. Polopřímý součin, který jsme definovali v úloze a)-(i), zobecňuje součin grup, který jsme definovali na přednášce a kterému se (pro odlišení od polopřímého součinu) říká také přímý součin: promyslete si, že jej dostaneme, pokud homomorfismus tp je definován tak, že p{k) je identita na H pro každé k £ K. V úloze a)-(iii) považujte skutečnost, že (Z, o) je grupa, za dokázanou - viz. příklad 2.1.3 ze sbírky ke cvičení. Vysvětleme ještě použitý pojem tranzitivní akce: o akci grupy G na množině X řekneme, že je tranzitivní, pokud pro libovolné x,y G X existuje g G G tak, že p{g){x) = y, což lze ekvivalentně vyjádřit tím, že orbita libovolného prvku x G A je rovna celé množině A. Řešení - str. 23. 8 7. kolo — Permutační grupy a vnitřní automorfismy grup Doporučené znalosti: vnitřní automofismy grup - po str. 57 v přednášce. Zadání: a) (6 bodů) (i) Nechť G je konečná grupa řádu n a a G G je prvek řádu k. Uvažme homomorfismus r: G —> S (G) z Cayleyho věty (definici připomínáme v komentáři dole). Určete (v závislosti na n a k) délky cyklů v rozkladu permutace ra na nezávislé cykly a určete také paritu této permutace. (ii) Nechť G je konečná grupa řádu 2m, kde m je liché. Dokažte, že existuje podgrupa grupy G indexu 2. b) (4 body) (i) Nechť G je grupa. Dokažte, že množina Inn(G) vnitřních automorfismů grupy G je normální podgrupa grupy (Aut(G),o) automorfismů grupy G. (ii) Dokažte, že Aut(§3) = Inn(§3). Komentář: Připomeňme, že homomorfismus r: G —> S (G) z Cayleyho věty byl definován takto: pro každé x G G je r (x) = rx, kde bijekce rx : G —> G je definována předpisem rx{g) = x ■ g pro libovolné g G G. Připomeňme také, že pro libovolnou grupu (G, •) platí, že množina Aut (G) všech automorfismů grupy G (tj. izomorfismů G —> G) vzhledem k operaci skládání zobrazení tvoří grupu: vždyť z toho, že identita na G je automorfismus, že složení dvou izomorfismů je izomorfismus a že inverzní zobrazení k izomorfismů je izomorfismus, plyne, že Aut (G) je podgrupou grupy (S(G),o). Symbolem Inn(G) rozumíme množinu všech vnitřních automorfismů grupy G, tedy Inn(G) = {pa', o, G G}, kde pro libovolný prvek a G G je vnitřní automorfismus pa : G —> G definován předpisem pa(g) = a ■ g ■ a-1 pro libovolné g G G. Z tvrzení uvedeného v úloze b) (i) vyplývá, že pro každou grupu G existuje faktorgrupa Aut(G)/Inn(G). Tato grupa se nazývá grupa vnějších automorfismů grupy G a značí se Out(G) (nicméně její prvky nejsou automorfismy G, ale množiny těchto automorfismů, které jsou třídy rozkladu grupy Aut(G) podle podgrupy Inn(G)). Tvrzení v úloze b) (ii) je tedy ekvivalentní tomu, že grupa Out(§3) vnějších automorfismů grupy (§3,0) má jediný prvek, t.j. je triviální. Řešení - str. 25. 9 8. kolo — Normalizér a centralizér množiny v grupě a automorfismy součinu grup Doporučené znalosti: centrum grupy - po str. 57 v přednášce. Zadání: Definice centralizéru a normalizéru jsou uvedeny v komentáři. Připomeňme, že Aut (Ir) značí grupu automorfismů grupy K. a) (4 body) Nechť G a H jsou grupy. (i) Dokažte, že grupa Aut(G x H) obsahuje podgrupu, která je izomorfní grupě Aut(G) x Aut(F). (ii) Ukažte na příkladu, že grupa Aut(G x H) nemusí být grupě Aut(G) x Aut(H) izomorfní. (iii) Jestliže navíc G a H jsou konečné a |-řř|) = 1, dokažte, že Aut(G x H) = Aut(G) x Aut(F). b) (3 body) Nechť G je grupa a H < G je její podgrupa. (i) Dokažte, že H C NG(H). (ii) Dokažte, že H je normálni podgrupa grupy G, právě když Ng(H) = G. (iii) Na vhodném příkladu ukažte, že je-li A pouze podmnožinou G, pak A C Ng(A) platit nemusí. c) (3 body) Nechť G je grupa a H < G je její podgrupa. Dokažte, že centralizér Cg{H) je normální podgrupa normalizéru Nq{H) a že faktorgrupa Ng{H)/Cg{H) je izomorfní vhodné podgrupě grupy Aut(H). Komentář: Nechť (G, •) je grupa, A C G podmnožina množiny G. Centralizérem množiny A v grupě G rozumíme množinu Cg{A) = {g G G; Va G A : g ■ a- g^1 = a}. Pro libovolné g G G definujeme g • A - g^1 = {g ■ a ■ g-1; a G A}. Normalizérem množiny A v grupě G rozumíme množinu NG(A) = {geG; g-A-9^= A}. Uvědomte si, že ihned z definice plyne: • CG{A) C NG(A): • CG{A) i NG(A) jsou podgrupy grupy G: • pro centrum Z{G) grupy G platí Z{G) = Cg{G)\ • je-li G komutativní, pak CG(A) = NG(A) = G. Řešení - str. 27. 10 9. kolo — Jednoduchost alternujících grup Doporučené znalosti: vnitřní automofismy - po str. 56 v přednášce. Zadání: a) (3 body) (i) Dokažte, že pro každé n G N množina všech cyklů v An délky 3 generuje celou grupu (ii) Popište třídy konjugace grupy A5 (definice viz níže). b) (7 bodů) Cílem tohoto příkladu je dokázat, že pro každé n > 5 je grupa An jednoduchá (definice viz níže). Budeme postupovat indukcí vzhledem k n. (i) Dokažte, že A5 je jednoduchá grupa. Nyní předpokládejme, že n > 6 a že grupa An_i je jednoduchá. Pro každé i G {1,... ,n} označme Hi = {a G An : a (i) = i}. Nechť dále H je libovolná netriviální normální podgrupa grupy An. Potřebujeme ukázat, že H = Án. (ii) Dokažte, že pro každé i G {1,..., n} je Hi podgrupa grupy An izomorfní grupě An_i. Dále dokažte, že H D Hi je normální podgrupa grupy Hi. (iii) Dokažte, že existuje i G {1,... , n} takové, že H D Hi 7^ {id}. [Návod: Vezměte si libovolné a G H, a 7^ id. Ukažte, že existuje a' G H takové, že u 7^ a1 a a (i) = o~'{i) pro nějaké i (můžete rozlišit případy, kdy a obsahuje cyklus délky aspoň 3 a kdy nikoliv).] (iv) Dokažte, že H = Án. Komentář: Prvky g, h grupy (G, •) se nazývají konjugované, jestliže existuje prvek a G G tak, že g = a • h • a^1. Snadno se vidí, že relace „být konjugované" je relací ekvivalence na množině G; třídy rozkladu podle této ekvivalence se nazývají třídy konjugace grupy G. Třídy konjugace grupy G můžeme popsat také jinak. Nechť p : G —> S(G) je akce grupy G na sobě vnitřními automorfismy, tedy pro libovolný prvek a G G je p(a) = pa, kde pa : G —> G je vnitřní automorfismus grupy G definovaný předpisem pa(g) = a - g ■ a-1 pro libovolné g G G. Pak pro libovolné prvky g, h grupy G platí, že jsou konjugované, právě když patří v akci p do stejné orbity; třídy konjugace grupy G jsou tedy právě orbity v této akci. Dále si ukážeme, jak funguje konjugace v grupě Sn. Nechť a G Sn je permutace, jejíž rozklad na nezávislé cykly je (ai5i,..., a1A) o (a2,i, • • •, a2/2) o ... o (aM,..., ak/k). Zvolme libovolné r G Sn. Pro každé i G {1,... , k}, j G {1,... lí} platí 1 ne jediné) r G §n takové, že platí a' = r o a o r_1. Celkem jsme tedy dokázali, že permutace v S„ jsou konjugované právě tehdy, když jsou stejného typu. Zkoumejme nyní stejnou otázku v grupě An. Stejným výpočtem jako výše se ukáže, že konjugované permutace v An jsou stejného typu. Opačná implikace ovšem obecně neplatí (důvod je ten, že žádné příslušné r nemusí být sudé). Například permutace (1, 2, 3) a (1, 3, 2) jsou stejného typu, ale nejsou v grupě A3 konjugované, neboť A3 je komutativní grupa, tedy každý její prvek je konjugovaný pouze sám se sebou. Grupa se nazývá jednoduchá, pokud je netriviální a nemá žádnou vlastní netriviální normální podgrupu. Jednoduché grupy hrají důležitou roli v teorii grup, významným hlubokým výsledkem je klasifikace konečných jednoduchých grup, jejíž kompletní důkaz má několik tisíc stran a samotná formulace tvrzení této klasifikace je velmi netriviální. Snadno se ale odvodí, jak vypadají všechny komutativní jednoduché grupy. Zřejmě pro každé prvočíslo p je grupa Zp jednoduchá, neboť dokonce nemá žádné vlastní netriviální podgrupy. Naopak zřejmě pro každou komutativní jednoduchou grupu platí, že nemůže mít žádnou vlastní netriviální podgrupu (neboť v komutativní grupě je každá podgrupa normální), proto každý nenulový prvek takové grupy musí generovat celou tuto grupu. Tudíž jde o cyklickou grupu. Každá cyklická grupa je izomorfní buď Z nebo Zn pro nějaké n G N; snadno se uvidí, že Z není jednoduchá a Zn je jednoduchá právě pro prvočíselné n. Řešení - str. 28. 12 10. kolo — Nástin pojmu prezentace grup Doporučené znalosti: předchozí kola soutěže. Zadání: a) (7 bodů) Nechť jsou dány konstanty k,£,r G N. Řekneme, že grupa (G, •) splňuje prezentaci (x,y | xk = l,ye = l,xy = yrx), (*) jestliže existují v grupě G prvky a, b takové, že grupa G je jimi generována a platí ak = 1, be = 1, a ■ b = br ■ a. i) Dokažte, že každá grupa G splňující prezentaci (*) je konečná a platí pro ni |G| < k-£. ii) Dokažte, že pokud existuje grupa G velikosti k ■ £ splňující prezentaci (*), potom platí rk = l(mod £). iii) Dokažte, že pokud platí rk = l(mod £), pak existuje grupa G velikosti k ■ £, která splňuje prezentaci (*). iv) Ukažte, že pro libovolné dvě grupy G a H splňující prezentaci (*) existuje grupa K splňující prezentaci (*) a surjektivní homomorfismy grup a : K ^ G a (3 : K ^ H. v) Ukažte, že existuje grupa K splňující prezentaci (*) taková, že pro libovolnou grupu G splňující prezentaci (*) existuje surjektivní homomorfismus grup a : K —?► G. b) (3 body) Nechť je pevně zvoleno číslo m G N. Řekneme, že grupa (G, •) splňuje prezentaci (x,y\x2 = l,y2 = l,(xy)m = 1), (**) jestliže existují v grupě G prvky a, b takové, že grupa G je jimi generována a platí a2 = l,b2 = l,{a-b)m = 1. i) Dokažte, že každá grupa G splňující prezentaci (**) je konečná a platí pro ni |G| < 2m. ii) Dokažte, že existuje grupa G velikosti 2m splňující prezentaci (**). Komentář: Při řešení části a)-iii) může být užitečné si všimnout, že z předpokladu rk = l(mod £) plyne nesoudělnost čísel r a £. V částech a)-iii) a b)-ii) samozřejmě dokazujte existenci příslušné grupy tak, že dáte příklad všeobecně známé grupy, která má požadované vlastnosti. Za všeobecně známé mějte grupy, s kterými jste se seznámili ve výuce nebo v naší soutěži. Poznamenejme, že grupa K, jejíž existenci máte za úkol dokázat v části a)-v), je dána jednoznačně až na izomorfismus. Skutečně, pokud K\ a K2 jsou grupy splňující podmínku z a)-v), pak máme k dispozici dva surjektivní homomorfismy a : K\ —> K2 a (3 : K2 —> K±, jejichž existence implikuje \K\\ = \K%\ a jedná se tedy o izomorfismy grup. Podobně by se stejné tvrzení dokázalo i v případě prezentace (**). Říkáme potom, že grupa K má prezentaci (*) resp. (**). V obou případech ovšem argumentace dokazující existenci a jednoznačnost grupy K vhodně využívá konečnosti uvažovaných grup a obecně se pojem prezentace grup musí zavést jiným způsobem. Stejně jako v zadání se prezentací grupy rozumí seznam generátorů grupy a seznam relací, které mají být v grupě splněny. (Relace vyjadřuje, že prvek, zapsaný pomocí generátorů v jistém tvaru, 13 lze zapsat pomocí generátorů i dalším způsobem.) Grupa K s touto prezentací se konstruuje za pomocí abstraktní grupy sestávající ze všech možných výrazů vytvořených z generátorů, která se vhodně faktorizuje. Takto zkonstruovaná grupa K má potom vlastnosti popsané v bodě a)-v), tj. libovolná grupa G, která splňuje stejnou prezentaci, je homomorfním obrazem K. Nicméně v této obecné podobě se s prezentacemi grup seznámíme až v kurzu Algebra II. Řešení - str. 32. 14 Část II — Řešení 15 1. kolo — řešení Za účelem zjednodušení formulací v následujícím řešení budeme pevné body permutace považovat za cykly délky jedna, čemuž jsme se v zadání vyhnuli (viz komentář k zadání). Při tomto pojetí lze také modifikovat definici rozkladu na nezávislé cykly, tak, že cykly délky jedna jsou jeho součástí. Věta o jednoznačnosti rozkladu (věta 2.5 ve skriptech, resp. str. 7 na slajdech) pak zůstává v platnosti a navíc je ji možné rozšířit i na případ identické permutace. Přesněji, rozklad na nezávislé cykly identické permutace id je součin n cyklů délky jedna. Zejména charakteristiky definované v zadání nabývají hodnot: ri (id) = n, (id) = 0 pro všechna k > 1 a následně r(id) = n. a) Buď o G Sn. Číslo n na pravé straně dokazované rovnosti značí počet prvků množiny Xn = {1,... ,n}, kterou permutujeme. Pro zadanou permutaci a : Xn —> Xn je každý prvek množiny Xn prvkem právě jednoho cyklu v rozkladu na součin nezávislých cyklů. Pro každé k. včetně případu k = 1, je součin k ■ ľfc( n, pak dle definice platí ^(u) = 0. Pokusme se tedy výraz v zadání ( — l)n~r(°") upravit do tvaru ( — l)s(°"). Nejdříve upravíme exponent n— r( _ J~J(_-g(fc-l)-rfe(V) _ J^J(_l)r2£W = (_l)ELir2ťW = (_1)S(CT) = p(o-) . k=l l=\ Alternativní řešení: Permutace o se napíše jako součin nezávislých cyklů a = a\oa2°- • •°cr(cr) a parita a se určí jako součin parit jednotlivých permutací a í , které jsou p(o"j) = kde ki je délka cyklu o i. Potom p(o-) = (-l)SSfe-1) = ; neboť dle části a) víme, že Yli=i = n- c) Hledaná ekvivalence pro zadanou permutaci a je tato: 3t G Sn : a = T2 VťeN : 2 | r2í(a) . : Nechť tedy a = r2. Pokud použijeme rozklad permutace r na nezávislé cykly, tj. r = n o t2 o • • • o tj, tak z nezávislosti jednotlivých cyklů plyne, že a = r2 = r2 o r| ° • • • ° t2. Pokud je Ti cyklus liché délky, pak r2 je cyklus stejné liché délky. Pokud je n cyklus sudé délky, pak r2 16 má rozklad na nezávislé cykly ve tvaru součinu dvou cyklů téže sudé délky, která je polovinou délky cyklu n. Nás zajímají cykly sudé délky v rozkladu permutace o na nezávislé cykly Pro libovolné í je tedy ^(u) rovno dvojnásobku počtu cyklů délky 4£ v rozkladu permutace r, tj. r2e(a) = 2 • tu(t), tudíž 2 | r2e(a). :í^=" Nejdříve vyřešíme případ, kdy a je součinem dvou nezávislých cyklů stejné sudé délky. Tedy buď a = (x±,X2, • • •, ^2r)(yi> 2/2> ■ ■ ■, V2í)- Pokud vytvoříme cyklus r délky 4£, kde se pravidelně a přitom postupně střídají čísla z dané dvojice cyklů, tj. cyklus r = (#1, yi, #2> 2/2> • • • > x2£, V2l)-, pak platí t2 = o. Této konstrukce později ještě využijeme. Nechť je nyní dána permutace o splňující předpoklad W G N : 2 | ^(u). Můžeme přepokládat, že a není identická permutace, pro niž je hledaná permutace r ona sama. Uvažujme rozklad a na nezávislé cykly U = 0\ o • • • o am o pi o p'x o p2 o P2 ° • • • ° Pr ° Pr : kde pro i = l,...,m je o i cyklus liché délky pi, a pro j = l,...,r jsou oba cykly p j i p'- cyklem stejné sudé délky qj. Označíme-li pro i = l,...,m permutaci n = ■ Sn dané předpisem ipn,k(o~) = o~k. Určete pro které dvojice čísel n, k je zobrazení (pn^k bijekce. 17 2. kolo — řešení Na přednášce jsme definovali množinu C* jako množinu všech nenulových komplexních čísel, tedy (C*, •) je grupa na této množině vzhledem k operaci násobení komplexních čísel, a-b) Užijeme Moivreovu větu: Každé nenulové komplexní číslo a lze psát ve tvaru a = r ■ (cos 7 + i sin 7) pro vhodná r é m, r > 0, 7 é 1, přičemž r = \a\ je dáno jednoznačně a 7 je dáno jednoznačně až na přičtení celočíselného násobku 2tv. Pak pro libovolné celé číslo n platí an = rn ■ (cos rvy + i sin rvy). Jestliže má a G C* konečný řád v grupě (C*, •), existuje n G N tak,že platí an = 1. To pak znamená, že rn = 1 a že existuje A: G Z splňující rvy = 2k-k. Odtud r = 1, neboť r je kladné reálné číslo, a 7 = ^7r je součinem racionálního čísla ^ a čísla 2tv. Tedy každé číslo a G C*, které má konečný řád v grupě (C*, •), je tvaru a = cos(u ■ 2tv) + ism(u ■ 2tv) pro vhodné iiěQ. Protože jsou funkce cos a sin periodické s periodou 2tv, je možné ještě přidat požadavek 0 < u < 1. Naopak, libovolné racionální číslo u lze jednoznačně zapsat ve tvaru u = |, kde p G Z, g G N a čísla p, q jsou nesoudělná. Označme (3 = cos(| • 2tv) + isin(| • 27r). Pro každé í G N pak podle Moivreovy věty platí p =cos(| -2ir) +isin(| -2ir). Platí tedy /3* = 1. právě když ^ eZ, což je ekvavalentní s q \ pt. Protože jsou čísla p, q nesoudělná, je poslední podmínka ekvivalentní s q \ t. Dokázali jsme, že číslo (3 má řád q v grupě (C*, •). Dostali jsme tedy řešení úlohy a): Množinou všech komplexních čísel, které mají konečný řád v grupě (C*, •), je {cos(u • 2ir) + isin(u ■ 2ir); u G Q, 0 < u < l}. Rovněž odvodíme řešení úlohy b): číslo (3 má řád n, právě když /3 = cos(£-27r)+isin(£-27r), kde p G Z, (p, n) = 1. Přidáme-li podmínku 0 < p < n, dostaneme tak každé takové (3 jednoznačně. V grupě (C*, •) tedy existuje prvků řádu n právě tolik, kolik je takových p, tj. právě 5 mají grupy příliš mnoho prvků, nebudeme tedy procházet všechny možné prvky, ale budeme postupovat jinak: Libovolná neidentická permutace a G Sn je složením nezávislých cyklů délky alespoň 2, přičemž součet jejich délek je nejvýše n. Je-li mezi nimi cyklus délky k, přičemž k = rs pro nesoudělná čísla r > 2, s > 3, je k nejmenší společný násobek čísel r, s a platí r + s < rs = k, neboť 1 < (r — 1) (s — 1) = 1 — r — s + rs. Je-li tedy k = p^1 ■ ■ ■ p^, kde p\ < ■ ■ ■ < pt jsou prvočísla a ei,... ,et G N, lze cyklus délky k nahradit nezávislými cykly délek p^1, ..., p^, přičemž na to ani nevyužijeme všech k prvků zmiňovaného cyklu. Tím získáme permutaci r G Sn, r 7^ a. přičemž r a u mají stejný řád. Provedeme-li to se všemi cykly permutace u, jejichž délka není mocnina prvočísla, dostaneme nakonec permutaci, jejíž každý nezávislý cyklus má délku, která je mocninou prvočísla, přičemž tato permutace má stále stejný řád jako permutace a. Zřejmě se její řád nezmění, pokud pro každé prvočíslo p ponecháme jen ten z nejdelší z cyklů, jejichž délka je mocninou prvočísla p. Tím jsme dostali, že mn je největší možný součin činitelů, které jsou 18 mocninami různých prvočísel, přičemž součet těchto mocnin prvočísel nepřevýší n. V následující tabulce je uveden vždy takový největší součin, spolu spříkladem permutace řádu mn: m5 = 2 • 3 = 6, (1,2) o (3,4,5): me = 2 • 3 = 6, (1,2) o (3,4,5): rrij = 22 •3 = 12, (1,2,3,4) o (5,6,7): m8 = 3 • 5 = 15, (l,2,3)o(4,5,6,7,8): mg = 22 • 5 = 20, (l,2,3,4)o(5,6,7,8,9): mio = 2 • 3 • 5 = 30, (l,2)o(3,4,5)o(6,7,5 ,9,10): mn = 2 • 3 • 5 = 30, (l,2)o(3,4,5)o(6,7,5 ,9,10): mi2 = 22 • 3 • 5 = 60, (l,2,3,4)o(5,6,7)o( 8,9,10,11,12) Exponenty grup Sn pro n < 12 spočítáme odvozeným vzorcem v následující části. d) Protože grupa Sn obsahuje cykly všech délek 2, 3, ..., n a cyklus délky k má řád k v grupě Sn, je hledaný exponent dělitelný každým z čísel 2, 3, ..., n, a tedy je dělitelný i jejich nejmenším společným násobkem. Na druhou stranu je libovolná neidentická permutace z Sn složením nezávislých cyklů, z nichž každý má délku nejvýše n. Rád této permutace je pak nejmenší společný násobek délek použitých cyklů, a tedy dělitelem nejmenšího společného násobku čísel 2, 3, ..., n. Dostali jsme, že hledaný exponent en je nejmenší společný násobek čísel 2, 3, ..., n. Zbývá ještě nalézt vzorec popisující rozklad čísla, cn na součin prvočísel. Číslo en je dělitelné jen prvočísly dělícími některé z čísel 2, 3, ..., n, tedy prvočísly p < n. Navíc z jednoznačného rozkladu na součin prvočísel plyne, že pro libovolné A; G N platí pk | en, právě když pk je dělitelem některého z čísel 2, 3, ..., n, tedy právě když pk < n. Platí tedy en = 11 Pkp; prvočíslo p 3. 19 2. Nalezněte exponent grupy všech rotací čtyřstěnu, resp. krychle. 3. Nalezněte exponent grupy všech shodností čtyřstěnu, resp. krychle. 3. kolo — řešení a) Vezměme si libovolné b G H. Jelikož je homomorfismus p surjektivní, existuje a G G takové, že b = p{a). Dále víme, že grupa G má exponent 2, a tak platí a2 = 1. Odtud plyne b2 = p{a)2 = p(a2) = p{l) = 1, a tak má b řád 1 nebo 2. Toto platí pro všechny prvky H, a tedy H má exponent 1 nebo 2. b) Vezměme si libovolné prvky a, b zadané grupy. Pak platí a2 = b2 = (ab)2 = 1, a tak ab = a(ab)2b = a2bab2 = ba a tedy zadaná grupa je komutativní. c) Předpokládejme nejprve, že předpis korektně zádava zobrazeni. Platí [1]^ — G Z^, a tak musí být [l]n = coz zřejmě platí právě tehdy, když n | m. Nyní naopak předpokládejme, že n \ m. Pokud pro a, b G Z platí [a]m = [b]m, pak zřejmě [a]n = [b]n, a tak předepsaná hodnota nezáleží na volbě reprezentanta dané zbytkové třídy. Dále (a, m) = 1 implikuje (a, n) = 1, a tedy pro každé [ platí G Z^, předpis tedy skutečně zadává korektně definované zobrazení Z^ —>■ Z^. Odteď tedy předpokládejme, že n \ m. Nejprve ukážeme, že je p homomorfismus grup. To plyne z toho, že pro libovolné [a]m, [b]m G Z^ platí p([a]m ■ [b]m) = p([ab]m) = [ab]n = [a]n ■ [b]n = '^p([a]m) • v([a]m)- Zbývá ukázat, že je p surjektivní. Nechť m=n pap p\m je prvočíselný rozklad čísla m, kde ap G N pro všechna prvočísla p dělící m. Označme V množinu všech prvočísel, které dělí m a zároveň nedělí n, a Q množinu všech prvočísel dělících n. Dále označme r = Y[paf,s = Y\paľ. peV peQ Potom zřejmě m = rs, (r,s) = (r, n) = 1, a tak n \ s. Vezměme si libovolné [a]n G Z^. Potom (a,n) = 1, a tak (a, s) = 1, neboť n a s jsou dělitelné stejnými prvočísly. Podle čínské zbytkové věty existuje x G Z takové, že x = 1 (mod r) a x = a (mod s). Potom (x,r) = 1 a (x, s) = (a, s) = 1, a tak (x, m) = 1. Navíc platí x = a (mod n). Tudíž [x]m G Z^ a 5. Potom [3]pfc G Zxfe ale [3]\ 7^ [l]pfc (neboť pk \ 8) a tak Z^fe nemá exponent 2. Nyní předpokládejme, že p = 3. Přímým ověřením se snadno zjistí, že Z3 má exponent 2, ale Zg má exponent větší než 2, a tak z tvrzení v částech a) a c) plyne, že Zxfe nemá exponent 2 ani pro žádné k > 2. Nakonec předpokládejme, že p = 2. Opět přímým ověřením snadno zjistíme, že Z2 má exponent 1, Z^ a Zg mají exponent 2 a Z^6 má exponent větší než 2, z čehož stejně jako výše plyne, že Z^fe nemá exponent 2 pro žádné A: > 4. Celkem jsme tedy dostali, že Z^fe má exponent 2 pro pfc G {3,4, 8}. e) Nechť n = Y[paP p\n 20 je prvočíselný rozklad čísla n, kde ap£N pro všechna prvočísla p dělící n. Z čínské zbytkové věty potom plyne (znv)=n •) • p\n Snadno se uvidí, že exponent součinu konečně mnoha konečných grup je roven nejmenšímu společnému násobku exponentů těchto grup, a tak (Z*, •) bude mít exponent 1 nebo 2 právě tehdy, když grupy (Z^p, •) budou mít exponent 1 nebo 2 pro všechna prvočísla p dělící n. Grupa (Z*fe,-) má exponent 1 (tj. je triviální) pouze pro p = 2 a k = 1, neboť ve všech ostatních případech je |Z*fe| = ip(pk) = (p — l)pk~1 > 1, a má exponent 2 pro pk G {3,4,8} podle části d). Z toho je snadno vidět, že (Z*, •) má exponent 1 nebo 2 právě tehdy, když n | 24. Pro n = 1 a n = 2 je (Z*, •) triviální, tedy má exponent 1, v ostatních případech, tj. pro n G {3,4, 6, 8,12, 24}, má exponent 2. Poznámka: Na závěr zmíníme jednu aplikaci předchozího výsledku. Dirichletova věta o prvočíslech v aritmetických posloupnostech říká, že pro každé a G Z, n G N takové, že (a, n) = 1, existuje nekonečně mnoho prvočísel p takových, že p = a (mod n). Důkaz tohoto tvrzení v plné obecnosti je relativně obtížný, v některých speciálních případech jej ale lze dokázat elementárnějším způsobem. Konkrétně platí, že pro danou dvojici a, n existuje elementární (ve smyslu, který lze exaktně definovat) důkaz tvrzení právě tehdy, když a2 = 1 (mod n). Zejména pro dané n lze tvrzení dokázat elementárně pro všechna a s ním nesoudělná právě tehdy, když má grupa (Z*, •) exponent 1 nebo 2, což jak jsme ukázali je právě tehdy, když n | 24. 4. kolo — řešení a) Ukážeme nejprve, že f{H) 7^ G2. Předpokládejme sporem, že tomu tak není. Vezměme si libovolné g G G\\H. Jelikož }'{H) = G2, existuje h G H takové, že f (h) = f (g). Potom /(gh^1) = 1, tedy ghT1 G ker/, a tudíž ghr1 G H. Pak g = (gh~1)h G H, což je spor. Předpokládejme nyní, že existuje podgrupa M < G2 taková, že f (H) C M a f (H) ^ M ^ G2. Pak zřejmě f-1 {f{H)) C f'1 {M). Platí H C f-1(f(H)), a tak H C f'1 (M). Ze surjektivity / snadno plyne, že Í\f-\M)) = M. Kdyby bylo H = f'1 {M), pak f (H) = f (f'1 (M)) = M, což je spor. Kdyby bylo /_1(M) = Gu pak M = f (f'1 (M)) = /(d) = G2, opět spor. Celkem tedy H /_1(M) ^ Gi, což je spor s maximalitou H v G\. Žádná taková podgrupa M tedy neexistuje, a tedy f (H) je maximálni podgrupa G2. b) Ze surjektivity / snadno plyne, že /(/_1(A)) = K. Kdyby bylo /_1(A) = G±, pak K = f{f^1{K)) = f(G±) = G2, což je spor. Předpokládejme nyní, že existuje podgrupa M < G\ taková, že f'1 {K) C M a f'1 {K) ± M ± G\. Pak K = f(f-1(K)) C f (M). Kdyby bylo K = f {M), pak si vezměme libovolné m G M \ /_1(A). Potom ze surjektivity / plyne, že existuje k G f~ľ(K) takové, že f (k) = f (m). Pak /(mfc-1) = 1 G K, a tedy mk^1 G /_1(A'). Pak m = (mk~1)k G /_1(A), spor. Analogicky kdyby f (M) = G2, pak si vezměme libovolné g G Gri \M. Potom existuje n G M takové, že /(n) = /( {±1}. Permutaci a lichá, tedy p{a) = —1. Rád p (a) musí dělit řád a. Zřejmě řád prvku 21 — 1 v grupě {±1} je 2, a tak je řád a sudý. Podle Lagrangeovy věty je pak i řád dané podgrupy sudý. d) Pokud daná maximální podgrupa grupy Sn obsahuje nějakou lichou permutaci, pak je její řád sudý podle části c). Jediná maximální podgrupa grupy Sn obsahující pouze sudé permutace je evidentně podgrupa An, jejíž řád je n\/2, což je sudé číslo pro n > 4. e) 1. Pro n = 2 hráč A vyhraje, pokud v prvním tahu vybere identitu. Pro n = 3 si může hráč A zaručit výhru následujícím způsobem. V prvním tahu vybere (1,2,3). Potom hráč B musí vybrat sudou permutaci, jinak by prohrál. V následujícím tahu vybere A zbývající sudou permutaci (grupa 83 obsahuje 3 sudé permutace) a B v následujícím tahu nutně prohraje. 2. Předpokládejme nyní, že n > 4. Potom má hráč B následující vítěznou strategii. Pokaždé, když je B na tahu, vybere si nějakou maximální podgrupu M < Sn, která obsahuje všechny již vybrané prvky (taková zřejmě existuje). Jelikož podle části d) má M sudý řád a počet vybraných prvků v daný moment musí být lichý, existuje prvek podgrupy M, který ještě nebyl vybrán. Pokud hráč B vybere libovolný takový prvek, tak má zaručeno, že neprohraje, neboť i po jeho tahu budou všechny vybrané prvky obsaženy v M, a tak nemůžou generovat celou Sn. Jelikož hra může trvat jenom konečný počet tahů, hráč B musí při této strategii po dostatečně velkém počtu tahů vyhrát. 5. kolo — řešení a) Jsou-li A, B libovolné podmnožiny nosné množiny G grupy (G, •), pak z inkluze A C B plyne (A) C (B), vždyť (A) je nejmenší podgrupa grupy G obsahující množinu A a (B) je (nejmenší) podgrupa grupy G obsahující množinu B, a tedy (B) obsahuje i množinu A. (i) Inkluze (X) (1 (Y) C (X D Y) neplatí. Protipříkladem jsou například množiny X = {1} a Y = {-1} v grupě (Z, +), kdy (X) (1 (Y) = Z n Z = Z a (X (1 Y) = (0) = {0}. Z inkluze InľCX plyne (X (1 Y) C (X). Podobně z X H Y C Y plyne (X íl Y) C (Y). Dohromady (Iílľ) C (X) (1 (Y). (ii) Z inkluze X CXUY plyne (X) C (X U Y). Podobně zľCIUľ plyne (Y) C (X U Y). Dohromady (X) U (Y) C (X U Y). Odtud ((X) U (Y)) C ((X U Y)). Protože (X U Y) je podgrupa grupy G, je ((lUľ)) = (X U Y). Z inkluzí X C (X) a y C (Y) plyne XUY C (X)(J (Y), odtud (X U Y) C ((X) U (Y)). b) Uvažme grupu ({1, —1}, •) a zobrazení / : G —> {1, —1} určené předpisem 1 jestliže x d H. — 1 jestliže x £ G — H. Ukážeme, že / je homomorřismus. Zvolme libovolné a, b £ G a rozlišme čtyři případy: • Jestliže a £ H, b £ H, pak i a ■ b £ H, protože H je podgrupa. Pak f(a) ■ f(b) = 1-1 = 1 = f(a-b). • Jestliže a £ H, b ^ H, pak a • b ^ H, neboť z a • b £ H by plynulo b = a-1 • (a • b) £ H. Je tedy f(a) ■ f(b) = 1 • (-1) = -1 = f(a ■ b). • Jestliže a ^ H, b £ H, pak a ■ b ^ H, neboť z a ■ b £ H by plynulo a = (a • b) • b^1 £ H. Je tedy /(a) • f(b) = (-1) • 1 = -1 = f(a ■ b). 22 • Jestliže a ^ H, b ^ H, pak a-1 ^ H, neboť z a-1 E H by plynulo a E H. Proto obě levé třídy a-1 • H a b • H jsou různé od H. Protože je index podgrupy H v grupě G roven dvěma, existují jen dvě levé třídy, proto a-1 • H = b ■ H, což je ekvivalentní s a ■ b G H. Je tedy /(a) • /(6) = (-1) • (-1) = 1 = /(a - 6). Je tedy / homomorfismus. Jeho jádro ker / = H je normální podgrupa grupy G. c) Označme h generátor podgrupy H, tj. H = (h) = {h11; n G Z}. Nechť g G G a k G K jsou libovolné, existuje tedy n G Z tak, že k = hn. Protože je normální podgrupa grupy G, je g • h • g^1 G .řř, a proto existuje m G Z tak, ie g • h • g^1 = hm. Použitím niže dokázané rovnosti (g • h • g_1)n = g • hn • g^1 dostáváme 9 • fc • íT1 = g ■ hn ■ g'1 = (g • h ■ g'1)" = (hm)n = (hn)m = km G K. Dokažme nyní slibovanou rovnost (g • h • g_1)n = g • hn • g^1 pro každé n G Z. Pro n = 0 zřejmě platí, stačí tedy dokázat pro libovolné přirozené číslo n, že {g-h.g-1)n=g.hn.g-\ {g ■ h ■ g'1)^ = g ■ h'n ■ g'1. To uděláme indukcí. Pro n = 1 je první rovnost zřejmá a druhá plyne z odvozeného vzorce pro inverzní prvek k součinu. Předpokládejme tedy, že rovnosti platí pro libovolné dané přirozené n a dokažme jej pro n + 1. Užitím indukčního předpokladu (g-h-g-1)n+1 = (g-h-g-1)n-(g-h-g-1)=g-hn-g-1-g-h-g-1=g-hn+1-g-1, (g-h- g-1)-^ = {g-h- g'1)-" ■ (g ■ h ■ g'1)'1 = g ■ h~n • g'1 • g • h'1 • g'1 = g • JT^1) • g"1. d) Nechť H G 72- je ta třída rozkladu 72-, která obsahuje neutrální prvek 1 grupy G. Dokážeme, že H je podgrupa grupy G. Pro libovolný prvek a G H je A = {a ■ h; h G ií"} G 7£. Protože 1 G H, platí a G A. Tedy a (z AD H a z toho, že 7£ je rozklad, plyne A = H. Proto a ■ h £ H pro každé a, h £ H. Podobně pro libovolný prvek 6 G H je 73 = ■ h; h £ H} £ 7Z. Pak 1 = čr1 • 6 G 73, tedy B = H, odkud b^1 = b^1 • 1 G B = H. Je tedy Tí podgrupa grupy G. Ze zadání je každá levá třída grupy G podle podgrupy H prvkem 1Z. Ukažme také, že každá třída T G 1Z je levou třídou grupy G podle podgrupy H. Třídy rozkladu jsou podle definice neprázdné, existuje tedy t G T. Pak levá třída t ■ H G 1Z a platí t G T D (t ■ H), tedy T = t ■ H. 6. kolo — řešení a) (i) Je zřejmé, že operace na G je korektně definovaná. Nejprve ověříme, že je tato operace asociativní. Nechť hi,h2,h3 G H, ki,k2,k3 £ K. Potom platí {{hi, ki) ■ {h2, k2)) ■ {h3, k3) = {hi{(p{ki){h2)), kik2) ■ {h3, k3) = {hi{p{ki){h2)){v{kik2){h3)), {kik2)k3) = {hi{ip{ki){h2)){ip{ki){ip{k2){h3))), kik2k3) (tp je homomorfismus K —> Aut{H)) = {hi{(p{ki){h2{(p{k2){h3)))),ki{k2k3)) ( Aut(H). a tedy íp(1k) = Id/f), takže (1//, lx) je neutrální prvek této operace. Navíc ukážeme, že prvek ( Aut(H)) = (h( Aut(H), tudíž G dané předpisy í(/i) = (h, 1k) a j(fc) = (l//,fc). Pro každé hi,h2 g ií, k±,k2 g -řr platí í(hi) • i(/i2) = {h\,lK) ■ (h2,lK) = (h1(íp(lK)(h2)), 1k ■ lx) = {hih2,lK) = i{hih2) a j(fci) •j(fc2) = (líř, &i) • (líř, k2) = (1h ■ ^p(h)0-h), k\k2) = fcifc2) = j{kik2), takže i a j jsou homomorfismy. Navíc jsou oba zřejmě injektivní a jejich obrazy jsou H' resp. Ä"', takže H' a Ä"' jsou podgrupy G izomorfní H resp. ií. Ukážeme ještě, že H' je normální podgrupa G. Nechť h g H. Pro každé x g H, y g Ä" platí (x, y) = (x, lx) • (líř, y), a tak (x, y) • (h,lK) • (x, y)"1 = (x, lK) ■ (l/f, y) • (Mat) • (OMa:) • (lH.y))-1 = (x, lK) ■ (lH,y) ■ (h, lK) ■ (Ih.v)-1 ■ (x, Ik)-1 = (x, lK) ■ (lH,y) ■ (h, lK) ■ (1H .y"1) ■ (x-1, lK) = (x, lK) ■ ((l//,y) • (h, 1a-) • (lH.y-1)) • (x'1, 1a-) = (x, 1a-) • (( Aut(Zn). Označme r rotaci pravidelného n-úhelníku o úhel 2tt/n proti směru hodinových ručiček a s jeho libovolnou (ale pevně zvolenou) osovou souměrnost. Definujme zobrazení f \ 2^ x^Z2 —> D„ předpisem f(([a]n, [b]2)) = ra o sb. Rád r je n a řád s je 2, / je proto korektně definované. 24 Navíc prvky Dn jsou právě r'1 a r'1 o s, kde i G {0,... ,n — 1}, z čehož je snadno vidět, že / je bijekce. Ukážeme, že / je také homomorfismus. Snadno se nahlédne, že platí s o r = r-1 o s (nakreslete si obrázek), a tak pro všechna 01,02,61,62 G Z je /(([ai]n> [61J2)) 0 /(([a2]n> [^2)2)) = raiosblora2QSb2 =raior(-l)»ia2osblQSb2 = ra1+(-lfia2 osh+b2 = /(([ai+ (-l)bia2]n, ^+62]2)) = /(([ai]n + V([fei]2)([a2]n), [hh + [hh)) = f(([ai]n, [bih) ■ (Kin, [hh))- Tudíž / je izomoríismus, a proto Dn = Zn Z2. (iii) Opět se snadno zkontroluje, že předpis pro tp zadává korektně definovaný homomorfismus Z2 —> Aut (Z). Stejně tak se snadno ověří, že zobrazení / je korektně definované. Ukážeme, že / je homomorfismus. Platí, že pro každé 6 G Z mají čísla 6 a (1 — (—l)b)/2 stejnou paritu, proto pro každé 01,03,61,62 £ Z Platí /((oi, [&i]2)) ° f((a2, [62]2)) = (2oi + (1 - (-l)6l)/2) o (2o2 + (1 - (-l)62)/2) = 2oi + (1 - (-l)6l)/2 + (-l)2ffli+(1-(-1)í,1)/2(2a2 + (1 - (-l)62)/2) = 2oi + (1 -(-l)bl)/2 + (-l)bl(2a2 + (l-(-l)b2)/2) =2(ai + (-l)^a2) + (l-(-l)ř'1+(-l)ř'1-(-l)ř'1+ř'2)/2 = 2(ai + (-l)6la2) + (1 - {-l)h^)/2 = + (-l)6la2, [61 +62]2)) = /((ai + ^([6i]2)(a2), [&i]2 + [62)2)) = f((ai, [61J2) • (a2, [62)2))- Zobrazení / je tedy skutečně homomorfismus, navíc je snadno vidět, že má triviální jádro (neutrální prvek grupy (Z, o) je 0), a tudíž je injektivní. Pro každé a G Z platí /((a, [0)2)) = 2a a /((a, [1)2)) = 2a + 1, a tak je / taky surjektivní, a celkem je to tedy izomorrismus. b) Pro každé g G G označme Xg = {x G X: ip{g){x) = x} množinu pevných bodů permutace množiny X indukované prvkem g. Předpokládejme sporem, že pro všechna g G G platí Xg 7^ 0, tedy \Xg\ > 1. Podle Burnsidova lemmatu je počet orbit dané akce roven aritmetickému průměru čísel \Xg\ (přes všechna g G G). Tato akce je ale tranzitivní, tudíž orbita je jenom jedna. Čísla \Xg\ jsou tedy všechna větší nebo rovny než 1 a jejich aritmetický průměr je 1. To je možné jedině tak, že \Xg\ = 1 pro všechna g G G. Platí ale X\ = X, a tak \X±\ = \X\ > 2, spor. Poznámka: V situaci z příkladu b) si můžeme všimnout toho, že pokud jsou dva prvky grupy G konjugované, potom permutace množiny X indukované těmito prvky mají stejné délky cyklů v rozkladu na nezávislé cykly. Z dokázaného tvrzení tedy plyne, že nejenom existuje g G G takové, že Xg = 0, ale dokonce existuje třída konjugace v G taková, že všechny její prvky mají tuto vlastnost. Ukažme si ještě jednu aplikaci tohoto tvrzení, jejíž formulace je zcela elementární, nicméně její důkaz je hlubší. Nechť f{x) G Z [x] je polynom s celočíselnými koeficienty stupně n > 2, který je ireducibilní (tj. nejde napsat jako součin dvou polynomů kladného stupně s koeficienty v Z). Potom existuje nekonečně mnoho prvočísel p takových, že kongruence f{x) = 0 (mod p) nemá řešení (jinými slovy pro každé x G Z je p f f (x)). Naše tvrzení se zde využije tak, že za X vezmeme množinu všech kořenů polynomu f{x) (ten má v tělese C komplexních čísel právě n různých kořenů) a za G tzv. Galoisovu grupu polynomu f(x), kterou lze v tomto případě definovat jako grupu automorfismů nejmenšího podtělesa tělesa C, která obsahuje všechny kořeny f{x). Snadno se nahlédne, že G má kanonickým způsobem akci na X. Trochu těžší je dokázat, že je tato akce tranzitivní. Z našeho tvrzení potom plyne existence automorfismů z této Galoisovy grupy, který nezobrazuje žádný kořen polynomu f{x) sám na sebe. Zbytek důkazu ale využívá věci, které jsou příliš nad rámec tohoto předmětu, zejména je potřeba tzv. Gebotarevova věta o hustotě. 7. kolo — řešení a) (i) Poznamenejme, že ze zadání ihned plyne, že k dělí n. Protože prvek a G G je řádu k. jsou prvky a° = 1, a, a2,..., afc_1 po dvou různé. Pro libovolné g G G jsou po dvou různé tedy i prvky g = 1 • g, a • g, a2 • g,..., afc_1 • g. Dále pro libovolné i G {0,... , k — 1} platí ra(alg) = aí+1g. kde v případě i = k — l dostáváme ra(ak~1g) = akg = g. Tudíž uvažujeme-li rozklad permutace ra 25 na nezávislé cykly, pak libovolný prvek g £ G je součástí cyklu (g, ag,... , ak~1g) délky k. Proto je rozklad ra tvořen ^ nezávislými cykly délky k. Parita cyklu délky k je (—a tudíž je parita permutace ra je rovna =(-lf-t. (ii) Uvažujme opět injektivní homomorfismus r: G —> S(G) z Cayleyho věty a označme H = r(G) podgrupu grupy S(G) izomorfní s grupou G. Nechť a G G je prvek řádu 2, jehož existence je zaručena dle Cauchyho věty (slajdy str. 62, učebnice věta 10.9). Dle předchozího příkladu je parita permutace ra G H rovna ( —l)m = —1 a jedná se tedy o lichou permutaci. Stejně jako v řešení příkladu c) z 4. kola, uvažujeme přiřazení parity tp : S(G) —> {1, — 1} o nemž víme, že je homomorfismus grup. Protože (f(ra) = —1, je zúžení zobrazení tp na podmnožinu H, tj. p\h '■ H —> {1, —1}, surjektivní homomorfismus grup. Jeho jádro K = ker( or : G —> {1,-1}. b) (i) Za dokázané mějme Inn(G) < Aut(G) < S(G) - viz komentář k zadání a str. 57 slajdů. Zbývá tedy dokázat, že podgrupa Inn(G) grupy Aut(G) je normální podgrupou. Nechť tedy a G Aut (G) je libovolný automorfismus grupy G a a G G je libovolný prvek G, který zadává vnitřní automorfismus pa. Potřebujeme dokázat, že /3 = a o pa o ar1 je vnitřní automorfismus grupy G. Musíme tedy najít vhodný prvek b G G tak, aby (3 = pt>. Z toho důvodu pro libovolný prvek x G G určíme /3(x). Platí /3(x) = (a o pa o a_1)(x) = a(pa(a^1 (x))) = a(a ■ a_1(x) • a-1). Protože a je automorfismus, je předchozí výraz dále roven a(a ■ a^1(x) ■ a-1) = a(a) ■ a(a^1(x)) ■ a(a_1) = a(a) ■ x ■ a(a_1). Zde a(a_1) = (a(a))-1, neboť a G Aut (G). Proto označme b = a(a) a platí (3(x) = a(a) ■ x ■ (a(a))-1 = b ■ x ■ b^1 = pb(x) . Protože x byl libovolně zvolený prvek z G, dostáváme (3 = p^ G Inn(G). (ii) Pro libovolnou grupu G platí, že jádro homomorfismu p : G —?► Inn(G) je rovno centru grupy G - podrobnosti na str. 57 slajdů. V případě grupy G = 83 víme, že ^(83) = {id}, neboť (1, 2) o (1, 2, 3) = (2, 3) 7^ (1, 3) = (1, 2, 3) o (1, 2) atd. Homomorfismus p : §3 ->• Aut(S3) je tedy injektivní a obraz homomorfismu p, tj. podgrupa 11111(83), má 6 prvků. Ukážeme, že Aut(Sa) má nejvýše 6 prvků, čímž bude, díky 11111(83) < Aut(Ss), rovnost Aut(Sa) = 11111(83) dokázána. Platí 83 = ((1, 2), (1, 2, 3)), a proto je libovolný automorfismus a grupy 83 jednoznačně zadán hodnotami a((l, 2)) a a((l, 2, 3)). Přitom a((l, 2)) musí být prvek řádu 2, tj. cyklus délky 2, a podobně «((1,2,3)) musí být cyklus délky 3. Pro výběr hodnoty a((l,2)) máme 3 možnosti a pro výběr hodnoty «((1,2,3)) 2 možnosti. Skutečně tedy existuje nejvýše 6 automorfismů grupy 83. Pro zdůvodnění \ Aut(83)! < 6 lze místo generátorů vzít trojici transpozic, která v každém automorfismů musí být nějak zpermutována a tudíž je automorfismů nejvýše tolik, kolik je permutací této tříprvkové množiny. Seminář: Dokažte Aut(Sn) = Inn(Sn) pro všechna 26 8. kolo — řešení a) (i) Stačí sestrojit vnoření 9 : Aut(G) x Aut(H) —> Aut(G x H). Je tedy třeba libovolné dvojici (o~, p) G Aut (G) x Aut(i-f) přiřadit automorfismus #((o~, p)) grupy G x H. Na libovolný prvek (g,h) G G x H necháme dvojici automorfismů působit po složkách, tedy 9((a, p))((g, h)) = (2°Pl Odtud plyne, že #((o~ 1,p x)) je inverzní zobrazení k #((o~, p)), a tedy #((o~, p)) je bijekce, proto 0((<7,p)) G Aut(G x Rovnost ^((0"2,P2)) 0 0((01,pi)) = ^((0"2 0 0"l, P2 O pi)) = 0(((J2,P2) O ( Aut (G x H) je homomorfismus grup. Jestliže 9 ((a, p)) = id-GxH, Pak pro každé (g,h) G G x H platí ( (v,u). (Pro úplnost dodejme, že Z2 x Z2 je dvourozměrný vektorový prostor nad tělesem Z2, a tedy metodami lineární algebry snadno dostaneme, že Aut(Z2 x Z2) = GL2(^2) — S3.) (iii) Zobrazení i\ : G —» G x H a i2 : H —» G x H definovaná pro libovolná g G G, h G H předpisem i\{g) = (g, l/f), í2(h) = (Iq, h), kde Iq a 1// značí neutrálni prvky příslušných grup, jsou jistě vnoření. Pro libovolné a G Aut (G x H) máme komutativní diagram G -> G x H <- H nl SI ' TT ^2 TT G <-G x H-> H 27 kde a = Tiioaoii a p = tv2°oíoÍ2. Protože ^octoii je homomorfismus grup, pro libovolné g G G je řád prvku ^2(0(21(5))) dělitelem řádu prvku g, tedy i řádu |G| grupy G. Současně je to prvek grupy H, a tedy jeho řád je dělitelem řádu \H\ grupy H. Z předpokladu (|G|, |-řř|) = 1 plyne, že tímto řádem musí být 1, tedy ^2(0(21(5))) = 1h- Analogicky TVi(a(Í2(h))) = Iq pro každé h G H. Z definice je ker u množina všech prvků grupy G, které splní o~(g) = Iq- Protože a = Tiioaoi1 a -K2{a{ii{g))) = 1h, z cr(g) = Iq plyne a{ii{g)) = (1g,1jí). Ovšem a je automorfismus, a tedy dostáváme i\{g) = (1g, ^h), tj. g = Iq- Proto ker u = {1g} a u je vnoření G —» G. Protože G je konečná grupa, je u G Aut(G). Analogicky p G Aut(i-f). Pro libovolná g G G, h G H platí (g, h) = (g, 1)-(1, h) = ii(g)-Í2(h). Proto a((g, h)) = a(ii(g)-i2(h)) = (aoi1)(g)-(aoi2)(h). Přitom (aoi1)(g) = (TT1((aoi1)(g)),Tr2((aoi1)(g))) = (a(g),lH)-. protože fi o a o = a a {112 o a o i\){g) = ljj- Podobně (a o Í2){h) = (Iq, p(h)), dohromady a((g,h)) = (a(g),lH) ■ 0-g,p(h)) = (a(g),p(h)). To znamená, že a = 9((a,p)), a tedy 9 je surjektivní. Dokázali jsme, že Aut (G x H) = Aut (G) x Aut (H). b) (i) Protože H je podgrupa grupy G, pro každé g, h G H platí g • h • g^1 G H, a tedy g • H • g^1 C H. Rovněž g^1 • h • g G H, a proto h G g • H • g-1, tedy H C g • H • g-1. To znamená g-H-g-1=H, tedy H C Nq{H). (ii) Jestliže N q {H) = G, pak pro každé g G G platí g ■ H ■ g^1 = H, a proto pro každé h e H je g • h • g^1 G Zř, což znamená, že podgrupa grupy G je normálni. Je-li naopak H normálni podgrupa grupy G, pak pro každé g G G je g ■ H ■ g-1 Q H. To musí ovšem platit i pro g-1 G G, tedy rovněž g^1 • H • g c. H, tedy H Q g • H • g-1, dohromady H = g ■ H ■ g^1, odkud g G Nq(H), tedy G C Nq(H). Opačná inkluze platí z definice. (iii) Zvolme G = S3, A = {(1, 2), (1, 3)}. Pak platí (1, 2) o (1, 2) o (1, 2)"1 = (1, 2) a (1, 2) o (1, 3) o (1, 2)-1 = (2, 3) , a tedy (1, 2) o A o (1, 2)"1 = {(1, 2), (2, 3)} ^ A Proto (1, 2) £ WG(A). c) Pro libovolné g G Nq(H) definujme zobrazení pg : H —» -řř předpisem )=n (z.fei i=l kde homomorŕismy ■ Aut (^ki^j jsou dány vztahy • • • > [tkili)) = {[to-i(i)]i, [te-^ki)}^: přičemž izomorŕismus /: nľ=i {^í% ~~^ Csn(cr) je dán vztahem /((([íi,i]i,...,[íi,fcl]i),ř?i),...,(([ín,i]n,... )A)) = = cl,l ° • • • ° C1M ° TMi ° • • • ° Cn,l ° • • • ° Cn,fc„ ° T«,^ kde Tífi G §n je dáno vztahy Tifi{cLi,j,k) = aí,e(j),k a Tí,d(aí',j,k) = a«',i,fc Pro 7^ Odtud se snadno nahlédne (neboť sgn(cjj) = ( —l)í_1 a sgn^Éi) = sgn(ř?)*), že pokud a obsahuje v rozkladu na nezávislé cykly buď cyklus sudé délky nebo dva stejně dlouhé cykly liché délky, pak C§n(a) obsahuje nějakou lichou permutaci, v opačném případě C§n(a) obsahuje pouze sudé permutace. b) (i) Nechť H < A5 je normální podgrupa grupy A5. Z části a)(ii) víme, že třídy konjugace grupy A5 mají velikosti 1, 20,15,12,12. Jelikož H je normální podgrupa A5, musí být sjednocením některých z těchto tříd, přičemž musí určitě obsahovat třídu {id}. Snadno se ověří, že takové sjednocení bude mít počet prvků dělící |As| = 5!/2 = 60 pouze pokud buď vezmeme pouze třídu {id} nebo když vezmeme všechny třídy, a tak z Lagrangeovy věty plyne, že H = {id} nebo H = A5, a tudíž A5 je jednoduchá grupa. 29 (ii) Grupa Hn je zřejmě izomorfní An_i a grupy H±,..., Hn jsou navzájem izomorfní, neboť pro každé a G An vnitřní automorfismus pa zobrazuje Hi na Ha^. Dále ukážeme, že H D Hj je normální podgrupa Hi. Nechť a G H n Hi a r G Hi. Zřejmě rur-1 G Hi, a jelikož je H normální podgrupa An, tak rur-1 G H. Celkem tedy rur-1 G HC\Hi, a tedy HnHi je normální podgrupa H i. (iii) Vezměme si libovolné a G H, a 7^ id. Pokud a obsahuje v rozkladu na nezávislé cykly cyklus délky aspoň 3, pak ho můžeme napsat jako a = (01,02,03,...) o 9, kde cyklus (01,02,03,...) je disjunktní s permutací 9. Označme r = (03, 04, 05) G An, kde 04, 05 jsou libovolné navzájem různé prvky různé od a±, 02, 03 (takové prvky existují, neboť n > 6). Potom a' = t o a o r-1 G H. Platí a'(ai) = r(o"(r_1(ai))) = t (a (ai)) = t(ci2) = a2 = a(a±) a a'(a2) = r(a(r^1(a2))) = t( 6). Potom opět a' = t o a o r-1 G H. Platí u'(ai) = r(a(r~1(a1))) = r(a(ai)) = r(a2) = a2 = a(at) a a'(a3) = r(a(T^1(a3))) = r(a(a3)) = t(04) = 05 ý °(a%)^ takže a'^1a G Hai n H, o'^xo 7^ id. Dokázali jsme tedy, že existuje i G {1,..., n} takové, že H D Hi 7^ {id}. (iv) Vezměme si i z předchozí části. Podle části (ii) a indukčního předpokladu je Hi jednoduchá grupa. Víme, že H D Hi je její netriviální normální podgrupa, tudíž H D Hi = Hi, a tak Hi C H. Jelikož Hi obsahuje cyklus délky 3, a stejně jako v části a)(ii) se ukáže, že všechny cykly délky 3 v An jsou v An konjugované, tak H obsahuje všechny cykly délky 3 v An. Z tvrzení části a)(i) potom plyne, že H = Án. Pozn.: Ukážeme si ještě jiný důkaz faktu, že grupa An je pro n > 5 jednoduchá. Nechť tedy n > 5 a H je netriviální normální podgrupa An. Ukážeme, že H obsahuje cyklus délky 3. Opět si vezměme libovolné a G H, a 7^ id. Pokud a obsahuje v rozkladu na nezávislé cykly cyklus délky aspoň 4, pak ho můžeme napsat jako a = (di, 02,..., ar) o 0, kde r > 4 a cyklus (a±, a2,..., ar) je disjunktní s permutací 6. Označme r = (01,02,03). Potom je r o u o r-1 G H, a tak r o u o r-1 o u-1 G H. Jelikož t je disjunktní s 9, tak platí r o u o r-1 o u-1 = (a±, a2, a3) o (ai, 02,..., ar) o 9 o (03, 02, a±) o 9~x o (ar, ar_i..., oi) = (ai, a2, a3) o (oi, a2,..., ar) o (o3, a2, ai) o (or, ar_i..., ai) o 9 o 9~x = (ai, a2, a3) o (oi, a2,..., ar) o (o3, a2, aľ) o (or, ar_i... ,aľ) = (a1}a2, a4). Pokud a obsahuje v rozkladu na nezávislé cykly aspoň dva cykly délky 3, pak ho můžeme napsat jako a = (01,02,03) o (04,05,00) o 9, kde prvky 01,02,03,04,05,00 jsou navzájem různé a permutace (a±, a2, a3) o (04, 05, ag) je disjunktní s permutací 9. Označme r = (a±, a2, 04). Opět platí t o u o t-1 o u ^ G H, přičemž r o u o t-1 o u-1 = (a±, a2, 04) o (ai, 02, 03) o (04, 05, 00) o 9 o (o4, a2, oi) o 9~x o (o6, a5, a4) o (o3, a2, ai) = (ai, a2, a4) o (ai, a2, a3) o (o4, a5, a6) o (o4, a2, ai) o (a6, a5, a4) o (o3, a2, ai) o 9 o = (ai, a2, a4) o (ai, a2, a3) o (o4, a5, a6) o (o4, a2, ai) o (o6, a5, a4) o (03, 02, oi) = (di, 02, 05, 03, 04). Na tento cyklus potom aplikujeme postup z předchozího odstavce a tím dostaneme cyklus délky 3 patřící do H. Pokud o obsahuje v rozkladu na nezávislé cykly jeden cyklus délky 3 a jinak pouze cykly délky 1 a 2, pak ho můžeme napsat jako o = (a±, a2, a3) o 9, kde cyklus (a±, a2, a3) je disjunktní s permutací 9 a navíc 92 = id. Pak platí a2 = ((a±, a2, 03) oř?)2 = (ai, 02, a3)2o92 = (a±, a3, a2) G H. Pokud a obsahuje v rozkladu na nezávislé cykly pouze cykly délky 1 a 2, pak musí obsahovat aspoň dva cykly délky 2, takže ho můžeme napsat jako a = (a±,a2) o (03,04) o 9, kde prvky «1,02,03,04 jsou navzájem různé a permutace (01,02) o (03,04) je disjunktní s permutací 9. 30 Označme r = (ai, a2, 03). Opět platí r o a o r 1o(j 1 G ií, přičemž t o a o t 1o(j 1 = (ai, 02, 03) o (ai, a2)o(a3, a4)o#o(a3, a2, ai)o(a4,a3)o(a2,ai) = (ai, a2, a3)o(ai, a2)o(a3, a4)o(a3, a2, aľ)o (a4,a3) o (a2,ai) oíot1 = («1,02,03) 0 («1,^2) 0 (0.3,0.4) 0 (03,^2,^1) 0 («4,^3) 0 (0.2,0.1) = (a±, 03) o (a2, 04). Dále označme ip = (a±, 03, 05), kde 05 je libovolný prvek různý od a±, a2, 03, 04 (zde využíváme toho, že n > 5). Potom platí tp o (ai, 03) o (02, 04) o -r/A1 o ((a±, 03) o (02, o^))-1 = (ai,a3, a5) o (ai, a3) o (a2, a4) o (a5, a3, ai) o (a4, a2) o (a3, ai) = (ai, a5, a3) G F. Ukázali jsme tedy, že H obsahuje cyklus délky 3, z čehož stejně jako v části b)(iv) plyne, že H = An. V části b)(iii) i v tomto druhém důkazu jsme několikrát našli permutaci s požadovanými vlastnostmi jako prvek tvaru a/3o!_1/3_1, kde a, f3 byly nějaké vhodné permutace. Prvky tohoto tvaru hrají obecně v teorii grup důležitou roli, nyní si o nich řekneme něco více. Mějme grupu G. Pro prvky x,y G G definujeme komutátor prvků x,y jako prvek xyx~1y~1 a značíme [x,y]. Snadno se nahlédne, že x a y spolu komutují právě tehdy, když [x,y] = 1 (což vysvětluje ten název). Potom definujeme komutátorovou podgrupu grupy G (anglicky se někdy používá název derived subgroup) jako podgrupu grupy G generovanou všemi komutátory prvků grupy G. Značíme ji [G, G] (někdy se taky používá značení G' nebo G^). Tedy [G, G] = {{[x,y]:x,y G G}) = ({xyx^y-1: x, y G G}). (Některé zdroje definují komutátor x,y jako x~1y~1xy. To sice obecně nemusí být stejný prvek jako xyx^y^1, ale i při této definici bude platit, že x a y spolu komutují právě tehdy, když je jejich komutátor roven 1, a navíc podgrupa bude při obou definicích stejná, neboť komutátor x, y v tomto smyslu je roven komutátoru ve smyslu definovaném výše. Pro tyto účely je tedy jedno, kterou z definic používáme.) Značení [G, G] vyvolává (bohužel) dojem, že prvky komutátorové podgrupy grupy G jsou právě všechny komutátory v G. Ukazuje se ale, že tomu tak obecně není, neboť součin dvou komutátorů nemusí být komutátorem. Nicméně platí to pro konečné grupy malých řádů, nejmenší konečná grupa, ve které to neplatí, má 96 prvků (přesněji existují dvě takové navzájem neizomorfní grupy řádu 96). Není těžké ověřit, že [G, G] je normální podgrupa G a že má následující vlastnost: pro každou normální podgrupu H grupy G platí, že grupa G/H je komutativní právě tehdy, když [G, G] C H. Grupa [G, G] je tedy nejmenší normální podgrupa grupy G taková, že příslušná faktorgrupa je komutativní. Zejména tedy [G, G] = {1} právě tehdy, když je G komutativní (což je vidět rovnou z definice). Grupa G/[G,G] se potom nazývá abelizace grupy G a značí se Gab. Ukažme si pár příkladů. Pro n G {1, 2, 3} je An komutativní, takže její komutátorová podgrupa je triviální a Aab = An. Pro n = 4 není těžké přímo spočítat, že [A4, A4] = V4, kde V4 = {id, (1, 2) o (3,4), (1,3) o (2,4), (1,4) o (2,3)}, a tak A|b = A4/V4 = Z3. Pro n > 5 je An jednoduchá grupa, takže její jediné normální podgrupy jsou {id} a An. Jelikož není komutativní, tak [An, An] = A„ (grupa G taková, že [G, G] = G se nazývá perfektní grupa) a Aab = {1}. Pro symetrické grupy Sn. kde n G {1, 2, 3,4} se snadno spočítá, že [Sn, Sn] = An. Pro n > 5 není těžké dokázat (s využitím toho, že An je jednoduchá), že jediné normální podgrupy Sn jsou {id}, An a Sn, z čehož snadno plyne, že opět [Sn,Sn] = An. Pro všechna n G N tedy platí Sab = Sn/An, a tedy Sfb = {1} a S^b = Z2 pro n > 2. S trochou úsilí lze navíc dokázat, že pro všechny grupy Sn a An platí, že každý prvek jejich komutátorových podgrup je přímo komutátor. Komutátorové podgrupy se rovněž používají k definici tzv. řešitelných grup. Mějme grupu G. Potom můžeme sestrojit posloupnost grup G^°\ G^\ G^2\ ... rekurentně tak, že G^ = G a G{k+i) = [G(fe))G!(fe)] (coz vysvětluje, proč se [G, G] někdy značí jako G^). Potom řekneme, že G je řešitelná grupa, pokud existuje fe É No takové, že G^ je triviální grupa. Opět si ukážeme několik příkladů. Pro každou komutativní grupu G platí G^ = {1}, a tak je každá komutativní grupa řešitelná. Grupy Ai a A2 jsou triviální, takže A^ = {id}, A^ = {id}. 31 Grupa A3 je komutativní, takže A3 ' = {id}. Pro n = 4 platí K\' = V4 a A4 — [V4, V4] = {id} (neboť v4 je komutativní). Tudíž pro n < 4 je An je řešitelná grupa. Pro n > 5 platí A^ = A„ pro všechna A; G No, takže An není řešitelná. Dále = {id}, = A2 = {id}, = A3, Sg2'' = {id}, = A4, = v4, = {id}. Tudíž pro n < 4 je Sn řešitelná grupa. Pro n > 5 (k) je Sn = A n pro všechna A; G N, takže Sn není řešitelná grupa. Řešitelné grupy se využívají např. v tzv. Galoisově teorii, například to, že pro n > 5 grupa Sn není řešitelná úzce souvisí s tím, proč pro polynomy nad C stupně většího nebo rovno než 5 nelze obecně vyjádřit jeho kořeny z jeho koeficientů použitím aritmetických operací a odmocnin (obecněji platí, že to jde právě tehdy, když je tzv. Galoisova grupa tohoto polynomu řešitelná, odtud taky pochází ten název). 10. kolo — řešení a) (i) Nechť grupa G splňuje prezentaci (*) a a, b G G jsou její prvky vyhovující požadovaným rovnostem. Stačí dokázat, že podgrupa G generovaná prvky a, b je dána vztahem ({a, b}) = {V ■ a* I i G {0,..., l - l},j G {0,..., k - 1}} , protože z předpokladu ({a, b}) = G pak dostaneme požadované tvrzení ohledně řádu grupy G. Označme tedy A = {tf-a1 \ i G {0,... ,£—l},j G {0,..., k — l}} podmnožinu grupy G a dokažme, že 1) A obsahuje prvky a, b, 2) A je podgrupa grupy G a 3) A je nejmenší podgrupa grupy G obsahující prvky a, b. Nejdříve poznamenejme, že ze vztahu ak = 1 plyne, že pro libovolné p G Zje prvek ap roven ad. kde d G {0,... , k — 1} je zbytek po dělení čísla p číslem k. Podobně lze psát libovolnou mocninu prvku b jako bd, kde d G {0, ...,£ — 1}. Zejména tedy platí rovnost A = {b1 ■ a? \ i, j G Z}. Přistupme nyní k důkazu jednotlivých tvrzení 1-3). 1) Snadno vidíme, že a = b° ■ a1 G A a b = b1 ■ a° G A. 2) Zřejmě 1 = 6° • a° G A. Abychom ukázali, že A je uzavřená vzhledem k násobení, ukážeme nejdříve, pro libovolné p G No platí a ■ W G A. Skutečně, indukcí lze dokázat rovnost a ■ bP = brp ■ a: pro p = 0 je rovnost zřejmá a pokud předpokládáme platnost tohoto vztahu pro p, pak pro p + 1 dostaneme a ■ bP+1 = a ■ W ■ b = brp ■ a ■ b = brp ■ br ■ a = br^ ■ a. Ukážeme dále, že pro libovolná j, p G No platí a? ■ lf = brJ-p • a? . (f) Platnost rovnosti (f) dokazujeme indukcí vzhledem k j: pro j = 0 rovnost (f) zřejmě platí a pokud předpokládáme platnost tohoto vztahu pro j, pak pro j + 1 dostaneme aj+1 -bP = a-a^ -bP = a- brJ'p ■ a' = č/"7^ • a ■ a' = brJ+Kp ■ a^+1. Použitím rovnosti (f) dostáváme, že pro libovolná přirozená čísla i,j,p,q G No platí (6ť • aj) • (&P • aq) = bl ■ brJ-p • a? ■ ap = bi+rJ-p • aj+p a dokázali jsme, že A je uzavřená na násobení. Zbývá ukázat, že pro libovolný prvek bl ■ a3 G A, kde i G {0, ...,£— l},j G {0,..., k — 1}, platí {bl ■ a1)^1 G A. To plyne z následujících rovností: (6* • a-5)-1 = a~J ■ b~% = ak~J ■ , kde poslední prvek zřejmě náleží do množiny A, protože A je podmnožina uzavřená na násobení. Tím je dokončen důkaz bodu 2). 32 3) Nechť H je libovolná podgrupa grupy G, která obsahuje prvky a, b. Pak vzhledem k uzavřenosti H na násobení, obsahuje podgrupa H i prvky tvaru b3 - a'1, kde i, j G N. Zejména tedy X C H & důkaz bodu 3), a tím i části i), je dokončen. (ii) Vzhledem k předchozí části znamená předpoklad |G| = k ■ £, že jsou prvky b% ■ a1, kde i G {0, ...,£— 1}, j G {0,... , k — 1}, po dvou různé. Zejména je prvek b řádu £. Prvek b1 ■ a° = b = ak ■ b vyjádříme pomocí odvozeného vztahu pro násobení (f) jako ak ■ b = brk ■ ak = brk = bd. kde d je zbytek po dělení čísla rk číslem £. Tudíž = 1 a protože b má řád £, tak dostáváme £ | d - 1, tj. d = 1. Odtud rk = l(mod £). (iii) Začněme neformálně: pokud budeme libovolný prvek b% ■ a? G G uvažovat jako příslušnou uspořádanou dvojici exponentů pak vzhledem ke vztahům ak = 1 a č/ = 1 lze hledanou grupu G reprezentovat jako množinu x kde prvek b%a? bude reprezentován jako ([i]e, [j]k)- Podle části i) pro operaci • platí ([i]e, [j]k) • ([p]e, [ Z^, dané předpisem ,jJx{9) = x " 9i homomorfismus grup. Lze přitom dokázat, že jiné homomorfismy z grupy do sebe neexistují, protože každý homorfismus z grupy je jednoznačně dán obrazem prvku [1]^. Dále pro libovolné x,y G platí ux o uy = uxy, = id a ux je izomorfismus právě tehdy, když x je invertibilní prvek monoidu (Z^, •), tj. x G Z*. Proto je grupa Aut(Z^) izomorfní grupě Z předpokladu rfc = l(mod £) víme, že (r,£) = 1 a tedy [r]g G Z*. Pro x = [r]g je proto lox automorfismus grupy (Z^, +). Navíc pro libovolné m G N platí (wx)m = Ujm. Pro m = k máme xk = [rk]c = a tedy {ujx)k = w^t = id. Definujme nyní zobrazení p : —?► Aut(Z^) předpisem ;/?([A]fc) = {u]x)h pro libovolné íiěZ. Toto zobrazení je korektně definováno, protože = id. Snadno se také nahlédne, že p je homomorfismus grup. Podle již zmíněného příkladu a)-i) z 6. kola soutěže tak máme definovánu grupu (G, •), pro niž platí G = Z; x a operace • je dána vztahem ([*k> [J]k) ■ ([p]e, [q]k) = ([i]e + {uxy{\p]t), [J]k + [q]k) = {[i + r1p]e, [j + q]k), pro i,j,p,q G Z. Pokud nyní zvolíme v G dva prvky b = ([l]e, [0]k) a a = ([Pk> [l]fc)> Pak se snadno ověří, že G splňuje prezentaci (*). Skutečně, pro libovolné m G Z platí 6m = ([m]^, [0]^), protože x {[0]^} je podgrupa grupy G izomorfní grupě Z^, kde izomorfismem je projekce na první složku. Tedy č/ = ([0]^, [0]fc) a podobně afc = ([0]^, [0]^), protože podgrupa {[0]^} x grupy G je izomorfní s grupou Zfc. Konečně a • 6 = ([0],, [l]fe) • ([1],, [0]fe) = ([0 + r1 • 1],, [l]fc) = ([r],, [0]fc) • {[0]e, [l]k) =br -a. Celkem je G = x^ grupa řádu • £, která splňuje prezentaci (*). Poznamenejme, že v případě k = 1 je triviální grupa a je zbytečné uvažovat polopřímý součin, protože ten je izomorfní grupě a lze tedy za grupy G vzít rovnou Z^. Podobně v případě l = 1. Také je dobré si uvědomit, že v případě r = 1 je každá grupa splňující prezentaci (*) komutativní. V tomto případě je ux = id, čímž pádem homomorfismus p zobrazuje každý prvek Zfc na id G Aut(Z^) a tedy polopřímý součin x^ je přímý součin x (iv) Buďte G & H dvě grupy splňující prezentaci (*) a v nich označme příslušné prvky a,6 G G a a',č/ G iA Uvažujeme-li přímý součin grup G x H, pak projekce na první a druhou složku 7Ti : G x H ^ G, resp. tv2 '■ G x H ^ H, jsou homomorfismy grup. Označme v grupě 33 G x H prvky A = {a, a') a B = (b, b'). Vzhledem k tomu, že operace násobení je v grupě G x H definována po složkách, snadno se nahlédne, že Ak = (ak,(a')k)=(lG,lH) = lGxH, a podobně Bí = 1Gxh a A ■ B = Br ■ A. Označíme-li K podgrupu grupy G x H generovanou prvky A a B, pak K splňuje prezentaci (*). Navíc {a,b} C tvi(K) a tudíž tt\ je surjektivní homomorfismus z K na G. Stejně se ukáže, že i 7T2 je surjektivní homomorfismus. (v) Označme K některou grupu, která má největší řád ze všech grup splňujících prezentaci (*). Její existence plyne z části i). Buď nyní G libovolná grupa splňující (*). Podle části iv) existuje grupa N splňující prezentaci (*) a surjektivní homomorfismy grup a : N —» K a (3 : N —» G. Protože K byla největší možná grupa splňující prezentaci (*), platí pro velikosti grup K a N nerovnost \K\ > \N\. Zároveň \N\ > \K\, protože a je surjektivní zobrazení konečných množin. Tudíž ji^l = \N\ a a : N —> K ]e bijekce, tj. izomorfismus grup. Proto /3 o ar1 : K —> G je surjektivní homomorfismus z grupy K na grupu G. Poznamenejme, že v části ii) jsme ukázali, že vždy b = br , tj. br _1 = 1. Vzhledem k č/ = 1 tak máme bd = 1 pro největší společný dělitel d čísel rk — 1 a l. Lze dokázat, že jako největší grupu splňující prezentaci (*), jejíž existenci jsme dokázali v části v), a která je určena jednoznačně až na izomorfismus, jak jsme si povšimli v komentáři zadání, lze vzít polopřímý součin grup a Zfc. Z popsaného totiž plyne, že každá grupa splňující prezentaci (*) pro trojici k,í,r splňuje prezentaci (*) i pro trojici k,d,r, přitom pro tuto trojici je předpoklad rk = l(mod d) již splněn. b) (i) Nechť G splňuje prezentaci (**) a a, b G G jsou příslušné prvky. Uvědomme si, že prvek a je inverzní sám k sobě a totéž platí pro prvek b. Z rovnosti {ab)m = 1 pronásobením prvkem a zleva a prvkem b zprava dostaneme a • b = a • (a • b)m ■ b = (b • a)m_1. Stačí dokázat, že podgrupa G generovaná prvky a, b je dána vztahem ({a, b}) ={(a-b)i -a' | i e {0,... , m - 1}, j G {0,1}} , protože dle předpokladu ({a, b}) = G pak dostáváme požadované. Postupujme podobně jako v části a)-i): označme X = {(a • b)'1 ■ a3 \ i G {0,..., m — l},j G {0,1}} podmnožinu grupy G. 1) Zřejmě a = (a ■ b)° ■ a1 G X a platí b = (a ■ b)m ■ b = (a ■ b)™-1 ■ a. 2) Zřejmě 1 = (a-b)°-a° G X. Dále pro libovolné i G {0,... ,m-l} platí ((a-6)*)-1 = (a-b)m^i a lze vidět, že prvek (a • b)la je inverzní sám k sobě. Množina X tak obsahuje s každým prvkem i prvek k němu inverzní. Potřebujeme ještě ukázat, že X je uzavřená na násobení. Buď nyní (a • b)'1 ■ a3 G X a (a • b)p ■ aq G X libovolné - zde předpokládáme i, p G {0,..., m — 1} a j, q G {0,1}. Pokud j = 0 pak (a • b)% ■ aJ ■ (a • b)p ■ aq = (a • b)t+p ■ ag G X, protože v případě i + p > m platí (a • b)'t+p ■ aq = (a • b)l+p~m ■ aq. Pokud j = 1, pak použijeme v úvodu dokázanou rovnost a • b = (6 • a)m_1 a dostaneme (a • bý ■ ai ■ (a • b)p ■ aq = (a • tíf ■ a ■ ((6 • a)™-1)* • aq = (a • b)' ■ a ■ (b ■ a)pi-m-^ ■ aq = = (a • bý(a • b)p(m-V -a-aq = (a • b)l+pi-m-^ ■ a1^ = (a • b)d ■ a1^ G X , kde d je zbytek po dělení čísla i +p{m — 1) číslem m. 3) Dokáže se naprosto stejně jako v části a)-i). (ii) Vhodnou grupou, pro pevně zvolené m > 3, která má řád 2m, je (Dm,o), tj. grupa symetrií pravidelného m-úhelníku. V grupě Dm označme a některou osovou souměrnost. Platí a2 = id. Dále označme r rotaci kolem středu o úhel Platí = m. Protože řád podgrupy ({a, r}) je větší než = m a dělí 2m = |Dm|, platí ({a, r}) = Dm. Označme nyní b = a o r. Zjevně se jedná o nějakou osovou souměrnost, a proto b2 = id. Navíc ao6 = aoaor = r,a proto (a o b)m = id. Konečně z rovnosti a o b = r plyne ({a, b}) = ({a, r}) = Dm. Celkem dostáváme, že grupa (Dm,o) splňuje prezentaci (**). 34 Pro m = 1 má platit a ■ b = 1, tj. a = b = b. Jako grupu řádu 2m = 2 lze vzít cyklickou grupu (Z2, +) a v ní prvky a = b = [1)2. Pro m = 2 má platit (a • 6)2 = 1, tj. 6 • a = (a • 6)m_1 = a ■ b (viz část i)). Uvažovaná grupa je tedy komutativní (pokud komutují generátory, pak komutují všechny prvky). Jako grupu řádu 2m = 4 lze vzít komutativní grupu (Z2, +) x (Z2, +) a v ní prvky a = ([1)2, [0)2) a 6 = ([0)2, [1]2)- Poznamenejme, že úlohu b) lze řešit také převedením na úlohu a). Nechť G je grupa splňující prezentaci (**) a a, b její vhodné prvky. Označíme-li c = a ■ b, pak platí b = a-1 ■ c = a ■ c a tedy G je generována dvojicí prvků a a c. Navíc a2 = 1, cm = 1 a protože pro b = a • c máme b2 = 1, dostáváme a • c • a • c = 1. Odkud plyne, pronásobením cm_1 • a zleva, rovnost a ■ c = cm_1 • a. Tedy G splňuje prezentaci (*) pro trojici čísel k = 2, £ = m, r = m — 1. C"ásí aj-(j íaA; ihned dává b)-i) a část a-iii) implikuje b-ii), neboť předpoklad rk = l(mod í) je splněn. V řešení části a)-iii) popsaný polopřímý součin grup Zm a Z2 je samozřejmě izomorfní grupě Om (pro tíi ^ 3) popsané v řešení b-ii), což bylo dokázáno v příkladu a)-ii) v 6. kole. Seminář: Určete grupy symetrií pravidelných těles (krychle, čtyřstěnu, dvanáctistěnu, atd.). 35