Kompozice permutačních grup
Začněme připomenutím několika pojmů z teorie grup. Nechť H a K jsou libovol grupy. Symbolem Ant H značíme grupu všech automorfismů grupy H. Budeme aplikovat automorfismy grupy H na prvky grupy H zprava. To znamená, že pro libovolný prvek h g H a pro libovolný automorfismus a grupy H budeme obraz prvku h po aplikaci automorfismů a značit symbolem ha. Tomu také bude odpovídat pořadí skládání automorfismů v grupě Aut H. Totiž součinem a • (3 dvou automorfismů a a (3 grupy H budeme rozumět automorfismus grupy H daný pro libovolný prvek /jeH předpisem h(a • (3) = (ha)(3. Nechť dále (f : K —>* Aut H je nějaký homomorfismus grupy K do grupy Aut H. Pak na množině K x H definujeme binární operaci a následujícím předpisem. Pro libovolné prvky /?, hf g H a /c, /c7 g K klademe
(/c, /?) a (/c7, //) = (/c • /c7, /7(^(/c7) • tí).
Přímo lze ověřit, že pak množina K x H spolu s binární operací a tvoří grupu. Tuto grupu značíme symbolem K * H a nazýváme ji obráceným polopřímým součinem grup H b K určeným homomorfismem tp.
Nechť dále M a N jsou libovolné neprázdné množiny. Předpokládejme, že /-/je nějaká podgrupa grupy Sm všech permutací množiny M a že K je nějaká podgrupa grupy S/v všech permutací množiny N.
Uvažme dále mocninu H   grupy H. Jejími prvky jsou všechny soubory prvků (crp)pG/v grupy H indexované prvky množiny /V, takže ap G H pro všechna p G N. Tato mocnina HN je vybavena binární operací násobení definovanou po složkách předpisem
Spolu s touto operací tvoří mocnina HN grupu, nazývanou přímá mocnina grupy H. Pro libovolný prvek r G K uvažme zobrazení i/j(t) : HN     HN dané předpisem
((crp)pG/v)^(r) = (ar{p))peN.
Přímo lze ověřit, že pak i/j(t) je automorfismus mocniny HN grupy H. Vzniká tak zobrazení ^ : K     Aut HN přiřazující každému prvku r G K automorfismus i/j (r) grupy HN. Rovněž přímo lze ověřit, že toto zobrazení ^ je homomorfismus grupy K do grupy Aut HN. Tato situace konečně umožňuje uvažovat o obráceném polopřímém součinu grup K * HN určeném homomorfismem -0. Tento obrácený polopřímý součin budeme značit symbolem K[H] a budeme ho nazývat kompozicí permutačních grup H a K. Z teorie grup je tato kompozice K[H] grup H a K známa jako obrácený věnčitý součin (reverse wreath product) permutačních grup H a K.
Grupy H a K byly permutačními grupami, totiž byly podgrupami grup Sm a S/v všech permutací množin M b N. Ukážeme, že i jejich kompozici K[H] lze reprezentovat jako permutační grupu, a to jako podgrupu grupy S/vx/w všech permutací množiny N x M. Prvky kompozice K[H], to jest prvky obráceného polopřímého součinu K * HN, jsou tvaru (r, (<rp)p(E/v), kde r G K a <rp G H pro všechna p G N. Ke každému takovému prvku (r, (<rp)p(E/v) uvažme zobrazení
pG/v
: N x M ^ N x M dané pro každá a G /W a q G /V předpisem
JV, K)pg/v]] (q, a) = (r(q), <rq(a)).
Je snadné nahlédnout, že pak takto definované zobrazení [[r, (<rp)pG/v je permutací množiny N x M. Navíc zobrazení £ : K [H] —>* S/vx/w dané předpisem
C(r,(crp)pG/v) = [[r, (ap)pG/v]]
je prostý homomorfismus grupy K [H] do grupy S/vx/w- Je snadné ověřit, že toto zobrazení £ je prosté. Ukážeme, že £ je homomorfismus grup. K tomu je třeba ukázat, že platí
[[(T5(crp)pe/v) a (r ,(ap)pG/v)]] = [[r, (ap)pG/v]] o [[r', (ap)pG/v] .
Ale (r, (ap)peN) a (t', (<7p)pG/v) = (r o r', (ar/(p) o <jp)pGA/). Takže máme ukázat, že platí
r o t', (crr/(p) o ap)peN]] = [[r, (ap)pG/v]] o [[r7, (crřp)peN
Overíme, že zobrazení na obou stranách dávají tutéž hodnotu na každé dvojici (q, a), kde a G M a q G N. Ale skutečně
[r o T', (crT/(p) o crp)peW]] (q, a) = ((r o r )(g), (crT,(í?) o cr^)(a))
= (r(r'(í7)),(7T,((7)K(a))),
zatímco
[TÁ^p)PeN]]{[[r/,(ap)peN]](q,a)) = [[r, {ap)peN]] (r (q), ^(a))
Celkem je tedy zobrazení ( : /^[H] —)► S/vx/w vnorením grupy /^[H] do grupy permutací S/vx/w- Lze tedy kompozici K[H] grup H 3 K vnímat jako podgrupu grupy S/vxM všech permutací množiny N x M.
Bude nás dále zajímat cyklový index Z(K[H]) kompozice K[H] grup H 3 K v případě, že množiny M b N jsou konečné, a tedy i permutační grupy H b K jsou konečné. V tom případě předpokládejme, že množina M má m prvků a množina N má n prvků. V takovém případě je pak i kompozice K[H] konečnou grupou, na kterou lze rovněž nahlížet jako na permutační grupu výše popsaným způsobem. Příslušná množina N x M, na níž se permutace odehrávají, pak má mn prvků. Cyklový index Z(K[H]) grupy K[H] je pak polynomem v proměných
a K následujícím způsobem
, tmrh který vyjádříme pomocí cyklových indexů Z(H) a Z{K) grup H
Pro cyklový index Z(K[H]) grupy K[H] platí rovnost
Z(K[H]\ fy, fy, • • •, tmn) = Z(K\ Z(H\ fy, fy, • • •, fy?),
Z(H, Í2 5 í"4 5 • • • 5 fy/77), • • • 5 Z(H, fy, fy/7, • • • 5 ^/77/7)) •
Výraz vpravo vznikne tak, že do cyklového indexu Z(K; fy, fy, • • •, fy) dosadíme pro každé í = 1, 2,..., n výraz Z(H\ ty, fy^,..., W) za proměnnou ty.
Důkaz.
Buď Y libovolná konečná dostatečně velká množina mající r\ prvků. Je možné si přímo představit, že Y je množina čísel {1,2,... ,77}. Připomeňme znovu, že pak pro každé kladné celé číslo k jsme označili symbolem Sk sumu mocnin proměnných xi + x2 + ''' + X7? ■ Výše uvedenou rovnost cyklových indexů grup dokážeme tak, že ukážeme, že platí rovnost polynomů v proměnných xi,x2,... ,xv, která vznikne, když do shora uvedené rovnosti polynomů v proměnných fy, fy,..., tmn dosadíme pro každý index k = 1, 2,..., mn sumu Sk za proměnnou fy. Z posledního důsledku uvedeného v předchozím paragrafu plyne, že toto skutečně stačí k tomu, abychom ověřili shora uvedenou rovnost cyklových indexů grup.
Chystáme se tedy dokázat, že platí rovnost polynomů
Z(K[H] ) = Z(K\ Z(H] si, s2,..., sm),
Z(H, S2, S4,..., S2m),..., Z(H, S/7, S2/7,..., 5/77/7)).
Podle Pólyovy věty je polynom Z(K[H]\ si, S2,..., s^) stojící nalevo v této rovnosti roven enumerátoru ^(YNxM, K[H]). Potřebujeme tedy ukázat, že také polynom stojící napravo v této rovnosti je roven témuž enumerátoru j(YNxM, K[H]). Označili jsme symbolem %JIynxm,k[H\ nnnožinu všech orbit libovolných zobrazení WxM^Vv podgrupě EK^H\ Pak podle definice enumerátoru máme pro zmíněný enumerator rovnost
7{Y»*M,K[H\) =
Sčítají se zde členy v(0) přes všechny orbity O G QJty/vxM^H]- Staráme se tedy dále o orbity libovolných zobrazení N x M —>► Y v podgrupě EK^H\ Buď f : N x M —)► V libovolné takové zobrazení. Pak pro jeho orbitu v podgrupě f^, kterou značíme symbolem fK[H], máme vztah
fK[H\ = {f o p : p e K[H\}
= {f o [[r, (crp)pG/v]] : r G K, ap G H pro všechna p G A/}.
Přitom pro libovolná a G M a q G N máme
(fo QV, (<Tp)p€N]])(q,a) = f ([[t, (<Tp)p€N]](q, a)) = f(r(q),aq(a)).
Priraďme k našemu zobrazení f : N x M —>► Y soubor zobrazení (fp)pei\i, kde pro každé p e N je fp : M ^ Y zobrazení dané předpisem fp(a) = /"(p, a) pro všechna a G M. Vezměme dále k danému zobrazení f orbity zobrazení fp v podgrupě EH pro všechna p G A/. Pro tyto orbity, které značíme fpH, máme vztah
fpH = {fpoq:qeH}.
Označili jsme symbolem WlyMH množinu všech orbit libovolných zobrazení M —)► Y v podgrupě EH. Uvažme konečně zobrazení f : A/ —>► WIymh dané pro každé p G A/ předpisem /"(p) = /pH. Vezměme k tomuto zobrazení /"jeho orbitu v podgrupě EK. Tuto orbitu značíme symbolem /"/< a máme pro ni vztah
7K = {? o r : r G K}.
Pro množinu všech orbit libovolných zobrazení N —>* WXymh v podgrupě EK máme označení OTt^/v    K. Orbita f K je prvkem této poslední množiny orbit.
YM ,h'
Abychom se vyhnuli komplikovanému značení, zavedeme pro množinu orbit DJtyMH krátké označení 2). Pak orbita f K je prvkem množiny orbit ^í1^qnk
Ukážeme, že pak existuje vzájemně jednoznačná korespondence
yn*m,k[H]
definovaná formulí
X(fK[H}) = f K
pro libovolná zobrazení f : N x M definice je korektní.
Y. Je ovšem třeba zprvu ukázat, že tato
Nechť tedy f,g:NxM^ Y jsou dvě zobrazení náležející téže orbitě
pro nějaká r e K a ap e H, M —>* Y zobrazení daná předpisy
v podgrupě EK[H1, takže g = f o [[r, (ap)peN kde p e N. Pak pro každé p e N jsou fpigp : /p(a) = /"(p, a) a g"p(a) = g"(p, a) pro všechna a e M. Ovšem viděli jsme výše, že pak gp(a) = g(p, a) = f(r(p), ap(a)) = fr(p)(crp(a)) pro všechna a e M, takže dostáváme rovnost gp = fr(p) o crp platnou pro všechna p e N. Dále
připomeňme, že zobrazení f,g:N^ dJtYMH jsou pro každé p e N dána
předpisy 7(p) = fpH = {fp o^GHJa g(p) = gpH = {gP ° s : s e H}.
Kromě toho víme, že f K = {f o $ : ů e K} a      = {g o $ : $ e K}.
Odvodíme odtud, že f K = gK. Mějme tedy libovolné zobrazení tvaru g o ??, kde ů E K, které náleží orbitě gK. Pak pro každé p E N platí
(ŕ ° #)(p) = £(#(P)) = &»(p)w = {&>(p) °^^«}
= {^(^(p)) ° <7ů(P) °s ■■ s £ H} = {fr(ů(P)) o c : c g H}
= fTWp))H = 7(r(0(p))) = (7 o r o ů)(p).
Takže dostáváme rovnost g o ů = f oroi). Ovšem r o ů E K, takže zobrazení f o t o $ náleží orbitě f K, a tedy i zobrazení J o # náleží orbitě fK. Dokázali jsme tak inkluzi gK C f K. Obrácená inkluze se dokáže analogicky, takže celkem platí rovnost f K = gK. Je tedy výše uvedená definice korespondence x korektní.
Ukážeme dále, že korespondence x Je prosté zobrazení. Nechť tedy
fjg : N x M —)► Y jsou dvě zobrazení taková, že f K = gK. To znamená, že
{f o ů : ů E K} = {g o ů : ů E K}. Zejména tedy existuje r E K takové, že
g = f o r. Takže pro každé p E N máme rovnost g(p) = f(r(p))1 čili gp/-/ = fr(p)/-/, a tedy {gp o ^ : ^ g H} = {Yr(p) o ^ : ^ g /-/}. Zejména tedy pro každé p E N existuje ap E H takové, že gp = fr(p) o ap. Odtud pro každé a E M a pro každé p g N plyne, že g(p, a) = gp{a) = fT{p)(<TP(a)) = f{r{p),ap{a)).
To ale podle našich dřívějších zjištění znamená, že g = f o [r, (crp)p(E/v pro nalezená t E K a ap E H, kde p E N. Náležejí tedy obě zobrazení f,g téže orbitě v podgrupě EK^H\ takže platí, že fK[H] = g"/<[/-/]. To dokládá prostotu zobrazení x-
Ukážeme nakonec, že korespondence x Je surjektivní zobrazení. Nechť tedy Q je libovolná orbita v množině ^l^)nk. Tato orbita se skládá z nějakých zobrazení N —)► OJly/w H. Zvolme libovolné zobrazení h : N —>► WIymh z této orbity Q. Pro každé p G A/je /?(p) nějaká orbita v množině OJlyw H. Tato orbita se zase skládá z nějakých zobrazení M —>► V. Zvolme pro každé p E N nějaké zobrazení fp-.M^Yz orbity /?(p). Definujme konečně zobrazení f : N x M ^ Y pro
každá a E M b p E N předpisem /"(p, a) = /p(a). Ukážeme, že pak platí f K = Q.
K tomu stačí ukázat, že f E Q. My ukážeme, že ve skutečnosti platí rovnost f = h, kde h je odpočátku zvolené zobrazení z orbity Q. Ale pro každé p E N máme f (p) = fpH = /7(p), neboť fp je zobrazení z orbity h(p). Takže skutečně
máme rovnost f = h. To potvrzuje surjektivitu zobrazení x-
Buď nyní O libovolná orbita v množině WXynxm        Tato orbita je tvaru f K [H]
pro nějaké zobrazení f : N x M ^ Y. Clen je určen jako člen v(f), a tento poslední člen je definován jako součin proměnných
ko= n Xf(p,*)-
aeM, p<EN
Rozepišme tento součin ve tvaru
=n (n *'<*•))■
Zavedeme-li stejně jako výše zobrazení fp:M^Y pro všechna p g N předpisem fp(a) = f (p, a) pro všechna a e M, můžeme poslední součin ještě přepsat ve tvaru
v(o=n(ruc>)-
p<E/v aeM
Vnitřní součin v závorkách lze ale nyní vnímat jako člen v(fp), a to je člen v(fpH), kde fpH je orbita zobrazení /p v podgrupě EH. To je ale orbita v množině dJtymh. Dostáváme tak vyjádření
*(o=n v(fp)-
pG/v
Podle našeho dřívějšího zjištění máme vzájemně jednoznačnou korespondenci X '■ ^JIynxm,k[H\ ~~^ yR%)n,k danou formulí x{fK\H\) = fK.
Naší shora vybrané orbitě O z množiny %JIynxm,k[h] tak odpovídá orbita x(O) z množiny 9Jtz)nk. Naše původní orbita O byla tvaru fK[H] pro nějaké
zobrazení    naše nynější orbita x(O) je tvaru f K pro totéž zobrazení f.
Připomeňme, že zobrazení f : N —>► $JIymh je dáno pro každé p G A/ předpisem
/"(p) = /pH. Přiřaďme nyní každé orbitě 7£ v množině WXymh nějakou novou
proměnnou x-r. Pak bychom mohli uvažovat pro zobrazení f o členu
v(o=n*?(pr
pG/v
Tento člen by bylo možno vzít jako člen V(x(0)). Tím by však byl definován člen v(Q) pro každou orbitu Q G QJI^a/^. Dále bychom mohli zavést enumerator
7(2}W,K)=    ]T V(Q). Pro tento enumerator bychom pak ovšem měli rovnost
7(2)W, K) =       £ V(x(C?)).
Podle Polyovy vety pro tento enumerator platf rovnost
7(2)/v,K) = Z(K;s1,s2,...,sA?),
kde pro každé í = 1, 2,..., n je S£ = X^eoft M Porovnejme nyní mezi
sebou enumerátory ^(YNxM, K[H]) ve vyjadrení uvedeném zkraje tohoto důkazu a 7(2)^, K') ve vyjadrení uvedeném v předminulé formuli. V obou případech se sčítá přes všechny orbity O G DJtyNxM K^Hy V prvním případě se sčítají členy v((D), ve druhém případě se sčítají členy V(x(0)). Je-li orbita O tvaru fK[H] pro nějaké
zobrazení f, pak orbita x(O) je tvaru f K pro totéž zobrazení f. Příslušný člen v(0) je pak roven členu v(fK[H]), to jest členu v(f), kdežto člen V(x(0)) je pak
roven členu v(fK), to jest členu v(f). Konečně porovnejme nyní mezi sebou tyto
členy v(f) a v(f) ve vyjádřeních uvedených výše v tomto důkazu:
v(f)=l[v(fp)      a      v(f) = H*f(py
pG/v pG/v
Vidíme, že člen v(f) vznikne dosazením členů v(fp) za proměnné *7(p) do člene
v(f) pro všechna p G N. Je třeba zde ovšem připomenout, že v(fp) = v(fpH)
a f(p) = rpH, kde fpH je orbita zobrazení /p v podgrupě EH, tedy orbita v množině WXym h. Navíc odtud vyplývá následující závěr.
Poslední pozorovaní ohledně dosazování lze přeformulovat následovně. Člen v(f)
vznikne dosazením členů v(JZ) za proměnné x^ do člene v(f) pro všechny orbity TZ G WlyMH. Provedeme-li toto dosazení ve všech sčítancích enumerátoru 7(2) ^ K), dospějeme nakonec k závěru, že enumerátor ^(YNxM, K[H]) vznikne dosazením členů v(!Z) za proměnné x-jz do enumerátoru 7(2)^, K) pro všechny orbity 1Z G WlyM H. Vraťme se nyní k výše uvedenému vztahu vyjadřujícímu enumerátor 7(2)^, K) prostřednictvím cyklového indexu Z(K) grupy K a prostřednictvím sum mocnin proměnných ši,Š2,... ,š„. Dosadíme-li pro dané £ = 1, 2,..., n členy v(!Z) za proměnné x-r, do polynomu     pro všechny orbity 1Z G yytymh, přejde tak polynom     v sumu J2ne%n M   v^fá)- Pro ^ = 1 se jedná o sumu J2ne$n M   vfá)- To je ale podle definice enumerátoru právě enumerátor ^{YMH). Pro něj podle Pólyovy věty máme rovnost
j(YM,H) = Z(H;s1,s2,...,sm).
Pro obecné í = 1, 2,..., n pak vznikne suma X^eoft M   v(TZ) ze sumy J2ne%n M   vfó) dosazením mocnin proměnných x^xl,..., x^ za proměnné xi,X2,... 5X77. To znamená, že suma X^eoft M   ^(7£) vznikne takovýmto
m
dosazením z enumerátoru ^{Y , A7)
Vzhledem k předchozímu vyjádření enumerátoru j(Y , H) to pak má za následek, že dotyčná suma je rovna polynomu
Z(H] S£, S2£, ..., smi).
Celkem to znamená, že enumerator r){YNxM, K[H]) vznikne nahrazením
polynomů ši,Š2,... ,šn v enumerátoru 7(2)^, K) postupně polynomy
Z(H, Si, s2,..., 5/77), Z(H, S2, S4,..., S2/77), ..., Z(H, S/7, S2/7, • • •, •S/77/7).
Vzhledem k výše uvedené podobě enumerátoru 7(2)^, K) to ale říká, že
enumerator j(YNxM1 K[H]) vznikne dosazením polynomů Z(H; si, S2,..., sm),
Z(H] s2, s4,..., S2/77), .. •, Z(H; S/,, s2/7,..., smn) za proměnné fy, fy,..., fy do
polynomu Z(K; fy, fy,..., fy). To je ale ta skutečnost, kterou bylo potřeba
dokázat. □ --4