% Sem3.tex

\section{Cauchy-Frobeniusov izrek}

\hrule
\smallskip
Pripravil "Ziga Povalej
\smallskip
\hrule
\medskip



%\begin{itemize}
%\item 
%Doka"zi Izrek 1.7A in re"si Naloge 1.7.1, 1.7.2, 1.7.4, 1.7.5, 1.7.6 iz \cite{DixonMortimer}.
%\item 
%Predstavi rezultate poglavja 1.4 v  \cite{BiggsWhite}.
%\end{itemize}
 
 
 \subsection{Cauchy-Frobeniusov izrek in njegova posledica}
 
 Izrek, ki povezuje "stevilo orbit kon"cne grupe, ki deluje na kon"cni mno"zici, s "stevilom 
 fiksnih to"ck, se imenuje \textsl{Cauchy-Frobeniusova lema}, sre"camo pa ga tudi pod imenom 
 \textsl{Burnsideova lema}.
 
 \begin{izrek}
 \Label{Sem3izr1}
   Naj bo $G$ kon"cna grupa, ki deluje na kon"cni mno"zici $\Omega$, pri tem pa ima to delovanje
   $m$ orbit. Velja enakost
   $$m |G| = \sum_{x\in G} |\Fix(x)|.$$
 \end{izrek}
 
 \dokaz
   Za dokaz izreka si bomo ogledali mno"zico \newline
   $\mathcal{F} = \{(a,x) \in \Omega \times G ; a^x = a\}$.
   "Stevilo elementov mno"zice $\mathcal{F}$ bomo pre"steli na dva na"cina.
   
   Ozna"cimo orbite grupe $G$ z $\Omega_1, \Omega_2, \ldots, \Omega_m$. 
   Te orbite so ravno razbitje mno"zice $\Omega$. Elemente bomo najprej se"steli po $a \in \Omega$
   in dobili
   $$|\mathcal{F}| = \sum_{a \in \Omega} |\{x \in G; a^x = a \}| = 
     \sum_{i=1}^m \sum_{a \in \Omega_i} |\{x \in G; a^x = a \}| = 
     \sum_{i=1}^m \sum_{a \in \Omega_i} |G_a|.$$
   Iz lastnosti orbita-stabilizator (trditev \ref{Sem1trd3}) dobimo $|G_a| = \frac{|G|}{|\Omega_i|}$ 
   za vsak $a \in \Omega$.
   Torej velja enakost
   $$|\mathcal{F}| = \sum_{i=1}^m \sum_{a \in \Omega_i} |G_a| = 
   \sum_{i=1}^m \sum_{a \in \Omega_i} \frac{|G|}{|\Omega_i|} = 
   \sum_{i=1}^m |G| = |G| \sum_{i=1}^m 1 = m |G|.$$
   
   Po drugi strani pa lahko elemente $\mathcal{F}$ se"stejemo najprej po $x \in G$:
   $$|\mathcal{F}| = \sum_{x \in G} |\{a \in  \Omega ; a^x = a \}| = \sum_{x \in G} |\Fix(x)|.$$
   
   S tem je izrek dokazan.
 \Qed
 \vspace{5mm}
 
 Ena"cbo bi radi preoblikovali tako, da bi v njej nastopali konjugiranostni razredi. Zato pa bomo 
 najprej potrebovali lemo.
 
 \begin{lema}
 \Label{Sem3lema2}
   Naj bo $C$ konjugiranostni razred. Tedaj je mno"zica $\Fix(x)$ enako mo"cna za vse $x \in C$.
 \end{lema}
 
 \dokaz
   Naj grupa $G$ deluje sama nase s konjugiranjem, hkrati pa naj deluje tudi na mno"zico $\Omega$.
   Vemo, da sta dva elementa $g, h \in G$ v istem konjugiranostnem razredu natanko tedaj, ko zanju
   velja $h = x^{-1}gx$, kjer je $x \in G$.
   Naj sedaj $g$ fiksira to"cko $a \in \Omega$. Upo"stevajmo "se $1 = x^{-1} x$. Dobimo
   $$a^g = a \iff a^{gx} = a^x \iff (a^1)^{gx} = (a^{xx^{-1}})^{gx} = a^x \iff $$
   $$\iff (a^x)^{x^{-1}gx} = a^x \iff (a^x)^h = a^x.$$
   
   Od tod sledi, da je preslikava $a \mapsto a^x$ bijekcija med mno"zicama $\Fix(g)$ in $\Fix(h)$.
 \Qed
 
 V posledici si oglejmo preoblikovano ena"cbo iz izreka \ref{Sem3izr1}.
 \begin{posledica}
 \Label{Sem3posl3}
   Naj bodo $C_1, C_2, \ldots, C_k$ konjugiranostni razredi grupe $G$, element $x_i$ pa naj bo 
   predstavnik razreda $C_i$ za vsak $i = 1, 2, \ldots, k$. Potem velja
   $$m |G| = \sum _{i=1}^k |C_i| |\Fix(x_i)|.$$
 \end{posledica}
 
 \dokaz
   Konjugiranostni razredi so med seboj paroma disjunktni, njihova unija pa je cela grupa $G$.
   Torej sestavljajo njeno razbitje. Lahko zapi"semo
   $$m |G| = \sum_{x \in G} |\Fix(x)| = \sum _{i=1}^k \sum_{x_i \in C_i} |\Fix(x_i)|.$$
   Iz leme \ref{Sem3lema2} pa sledi, da je mo"c pribite mno"zice enaka v vsakem konjugiranostnem razredu.
   Zato dobimo novo enakost
   $$m |G| = \sum _{i=1}^k |\Fix(x_i)| \sum_{x_i \in C_i} 1 = \sum _{i=1}^k |\Fix(x_i)| |C_i|.$$
 \Qed
 
 
 \newpage
 \subsection{Naloge}
 
 Za prikaz uporabe tega izreka in njegove posledice re"simo nekaj nalog.
 \vspace{5mm} 
 
 \naloga{}{Naj bo $G$ tranzitivna podgrupa grupe $S_n$ in naj bo $r$ "stevilo orbit 
   stabilizatorja grupe $G$. Poka"zi, da velja 
   $$\sum_{x \in G} |\Fix(x)| = |G| \> \hbox{ in } \> \sum_{x \in G} |\Fix(x)|^2 = r |G|.$$}
  
 \noindent \textbf{Re"sitev:} 
   Prvi del naloge sledi neposredno iz definicije tranzitivnosti, ki 
   pravi, da je delovanje grupe $G$ tranzitivno, "ce ima le eno orbito. Tako v ena"cbo 
   izreka \ref{Sem3izr1} vstavimo $m = 1$ in dobimo "zelen rezultat. \vspace{2mm}
   
   Za re"sitev drugega dela naloge si najprej pomagamo z lastnostjo orbita - stabilizator 
   ter izrekom \ref{Sem3izr1}, ki ga uporabimo na $G_a$. Dobimo
   $$r |G| = r |\Omega| |G_a| = \sum_{a \in \Omega} \sum_{x \in G_a} |\Fix(x)|.$$
   Sedaj v tem premisleku zamenjamo vsoti in sledi
   $$r |G| = \sum_{x \in G} \sum_{a \in \Fix(x)} |\Fix(x)| = \sum_{x \in G} |\Fix(x)|^2.$$
   To pa je re"sitev na"se naloge.
   \medskip
 
 \naloga{}{Naj bo $G$ tranzitivna podgrupa grupe $S_{n}$. Poka"zi, da ima $G$ vsaj $n - 1$ 
   elementov, ki ne fiksirajo nobene to"cke. Poka"zi "se, da "ce je $G$ katerakoli kon"cna grupa
   in $H$ njena podgrupa z indeksom $n$, potem ima $G$ vsaj $n - 1$ elementov, ki niso konjugirani 
   elementom iz $H$.}
   
 \noindent \textbf{Re"sitev:}
   Grupa $G$ je tranzitivna, zato uporabimo kar prvo formulo iz prej"snje naloge. Vemo tudi, da
   ima vsaka grupa enoto, ki jo bomo ozna"cili z $1$. Grupo $G$ lahko torej zapi"semo kot
   $G = (G \setminus \{1\}) \cup \{1\}$. Tako dobimo formulo
   $$1 \cdot |G| = \sum_{x \in G \setminus \{1\}} |\Fix(x)| + |\Fix(1)|.$$
   Vemo pa, da je enota element, ki fiksira vse elemente mno"zice $\Omega$ \newline
   ($a^1 = a, \forall a \in \Omega$). Torej je mo"c mno"zice $\Fix(1)$ enaka $n$.
   
   Sedaj definirajmo mno"zici $A := \{ x \in G ; |\Fix(x)| = 0 \}$ in \newline
   $B := \{ x \in G ; |\Fix(x)| \neq 0 \}$. Ugotovimo, da sta ti dve mno"zici particija grupe G 
   ter da je enota $1$ zajeta v mno"zici $B$, saj $|\Fix(1)| = n \neq 0$. Z mno"zicama $A$ in $B$
   ter dejstvom, da je $|\Fix(1)| = n$, lahko prej"snjo formulo zapi"semo kot
   $$|A| + |B| = n + \sum_{x \in A} |\Fix(x)| + \sum_{x \in B \setminus \{1\}} |\Fix(x)|.$$
   Po definiciji mno"zice $A$ je $\sum_{x \in A} |\Fix(x)| = 0$, 
   vsota $\sum_{x \in B \setminus \{1\}} |\Fix(x)|$ pa je zagotovo ve"cja od $|B| - 1$, 
   saj je $|\Fix(x)| \geq 1$ za vsak $x \in B \setminus \{1\}$. Iz tega sledi, da je 
   $|A| + |B| \geq n + |B| - 1$ in zato $|A| \geq n - 1$.
   
   To smo hoteli dokazati, saj je $A$ mno"zica tistih elementov grupe $G$, ki ne fiksirajo to"ck.
   \vspace{5mm}
   
   Naj bo sedaj $G$ neka kon"cna grupa in $H$ taka njena podgrupa, da velja $|G : H| = n$. Na grupi 
   desnih odsekov $G / H$ mo"ci $n$ definirajmo mno"zenje $(Hx)^g := H(xg)$, kjer sta $x \in G$ in 
   $g \in G$. Za grupo $G$ velja $G \in \Sym(G / H)$, kar pa je izomorfno $S_{n}$. V tem primeru je 
   grupa $G$ tudi tranzitivna. Sedaj to nalogo lahko prevedemo na problem, ki smo ga re"sili 
   v prvem delu. 
   
   Vemo, da v $G$ obstaja vsaj $n - 1$ elementov, ki ne fiksirajo to"ck.
   Pa vzemimo tak $g \in G$, ki ne fiksira nobene to"cke. Zanj torej velja \newline
   $(Hx)^g = Hxg \neq Hx, \forall x \in G$. Sedaj pomno"zimo z $x^{-1}$ z desne in velja 
   $Hxgx^{-1} \neq H, \forall x \in G$. To pomeni, da za noben $x \in G$ element $xgx^{-1}$ 
   ne bo v podgrupi $H$. Torej tudi za noben $x \in G$ element $g$ ne bo konjugiran elementom 
   iz $H$. 
   
   Takih $g \in G$ je, kot smo dokazali, vsaj $n - 1$. Tako je naloga re"sena.
   \medskip

 \naloga{}{Naj bo $G$ kon"cna grupa, ki ima $k$ konjugiranostnih razredov. Poka"zi, da je mo"c mno"zice 
   $F = \{(x,y) \in G \times G ; xy = yx \}$ enaka $k |G|$.}
   
 \noindent \textbf{Re"sitev:}
   Delovanje grupe $G$ na sebi naj bo kar konjugacija $y^x = x^{-1}yx, \newline x, y \in G$. 
   Vemo, da so v tem primeru orbite delovanja kar konjugiranostni razredi, teh pa je $k$. Torej $m = k$.
   Mno"zico $F$ pa lahko zapi"semo tudi druga"ce: \newline
   $F = \{(x,y) \in G \times G ; xy = yx \} = \{y \in G ; xy = yx \}, x \in G$, to pa je enako 
   $\{y \in G ; xy = yx \} = \{y \in G ; y = x^{-1}yx \} = \Fix(x)$, ko $x\in G$.
   Uporabimo formulo izreka \ref{Sem3izr1} in dobimo
   $$k |G| = \sum_{x \in G} |\Fix(x)| = \sum_{x \in G} |\{y \in G ; y = x^{-1}yx \}| = $$
   $$ = |\{(x,y) \in G \times G ; xy = yx \}| = |F|,$$
   kar pa je ravno to, kar smo hoteli dokazati.
   \medskip
 
 \naloga{}{Naj bo $C$ konjugiranostni razred kon"cne grupe $G$, ki tranzitivno deluje na mno"zici 
   $\Omega$. Poka"zi, da velja $$|\Fix(x)| |C| = |G_a \cap C| |\Omega|$$ za vsak $a \in \Omega$ in
   $x \in C$.}
   
 \noindent \textbf{Re"sitev:}
   Definirajmo mno"zico $\mathcal{F} = \{(a,x) \in \Omega \times C ; a^x = a \}$. Podobno kot v 
   dokazu izreka \ref{Sem3izr1} bomo tudi tu izra"cunali mo"c mno"zice $\mathcal{F}$ na dva na"cina.
   
   Najprej pre"stejemo po elementih mno"zice $\Omega$. Po trditvi \ref{Sem1trd3} velja, da sta si 
   stabilizatorja $G_a$ in $G_b$ to"ck $a$ in $b$ konjugirana, "ce velja $a^x = b$. Zato tudi le"zita
   v istem konjugiranostnem razredu. Seveda je potem presek $G_{a} \cap C$ neodvisen od $a$ in velja
   $$|\mathcal{F}| = \sum_{a \in \Omega} |\{x \in C ; a^x = a\}|= \sum_{a \in \Omega} |G_{a} \cap C| = 
     |\Omega| |G_{a} \cap C|.$$
   
   Sedaj pre"stejemo elemente "se po razredu $C$. Po lemi \ref{Sem3lema2} vemo, da je $|\Fix(x)|$ 
   konstantna v vseh konjugiranostnih razredih. Tako sledi 
   $$|\mathcal{F}| = \sum_{x \in C} |\Fix(x)| = |C| |\Fix(x)|, \forall x \in C.$$
   
   Naloga je s tem kon"cana.
   
   
 
 \subsection{Primeri uporabe lastnosti orbita - stabilizator}
 
 Poglejmo si nekaj primerov, na katerih lahko uporabimo do sedaj izpeljano teorijo grup, predvsem 
 je koristna lastnost orbita - stabilizator (trditev \ref{Sem1trd3}).
   \vspace{2mm}
 
 \zgled{Najprej si oglejmo dve delovanji grupe $G$  na mno"zici $2^G$ podmno"zic mno"zice $G$:
   \vspace{2mm}
   
 $K^g := Kg, \> g \in G, K \subseteq G$ \vspace{2mm}
   
   Naj bo $K$ podgrupa grupe $G$. Potem je orbita tega delovanja kar mno"zica desnih odsekov grupe
   $K$ po grupi $G$, stabilizator grupe $K$ pa je kar sam $K$. To sledi iz definicije orbite
   in stabilizatorja. Po lastnosti orbita - stabilizator in dejstvu, da $|K|$ deli $|G|$, sklepamo, 
   da je indeks $|G : K|$ enak mo"ci orbite delovanja, kar pa je "stevilo vseh desnih odsekov 
   podgrupe $K$. \vspace{2mm}
   
 $K^g := g^{-1}Kg, \> g \in G, K \subseteq G$ \vspace{2mm}
 
   Sedaj vzemimo $K = \{k\}$. Orbita delovanja je sedaj konjugiranostni razred, ki vsebuje $k$, 
   stabilizator $G_k$ pa je centralizator $C(k)$. Tudi to je lahko preveriti, zato dokaza ne bomo
   navajali. Spet uporabimo lastnost orbita - stabilizator ($|k^G| = |G : C(k)|$) in
   vidimo, da je "stevilo h $k$ konjugiranih elementov enako $|G : C(k)|$. Natan"cneje, vsak 
   element centra $Z(G)$ je svoj konjugiranostni razred. Zato tudi dobimo ena"cbo 
   $$|G| = |Z(G)| + \sum |G : C(g)|,$$
   kjer te"ce vsota po vseh nekonjugiranih necentralnih elementih $g$.
   
   Sledi tudi, da ima netrivialna $p$-grupa netrivialen center. Naj bo $G$ mo"ci $p^k$.
   "Ce je $g \in G \setminus Z(G)$, potem je $C(g)$ prava podgrupa grupe $G$ (ni enaka $G$). 
   Zato je $\sum |G : C(g)| = p^l$, kjer je $l < k$. Sledi, da je tudi $|Z(G)|$ pozitivna potenca
   $p$.}
 
 
 \zgled{Kot naslednji primer si oglejmo dokaz izreka Sylowa:
 
   \textsl{Naj bo pra"stevilo $p$ delitelj mo"ci kon"cne grupe in naj bo $p^r$ najve"cja potenca
   "stevila $p$, ki "se deli mo"c te grupe. Tedaj obstaja v grupi podgrupa mo"ci $p^r$.}
 
   Naj bo $p^r$ najvi"sja potenca pra"stevila $p$, ki "se deli $|G|$. Oglejmo si podmno"zice grupe $G$,
   ki imajo mo"c $p^r$. Teh je ${|G| \choose p^r}$,
   ta binomski koeficient pa ni deljiv s $p$, kar se da hitro videti. Zato obstaja vsaj ena orbita 
   delovanja $K^g = Kg$, katere mo"c $m$ ni deljiva s $p$, stabilizator $G_L$ podmno"zice $L$ v tej
   orbiti pa ima po lastnosti orbita - stabilizator mo"c $\frac{|G|}{m}$, kar je deljivo s $p^r$.
   Torej je $|G_L| \geq p^r$.
 
   Naj bo $l \in L$. Zato je $G_L (l) \subseteq L$ in velja $|G_L| = |G_L (l)| \leq |L| = p^r$.
   Torej je $|G_L| = p^r$, stabilizator $G_L$ pa je tudi podgrupa grupe $G$.
   Grupa $G_L$ je iskana podgrupa mo"ci $p^r$.}{}
 
 
 \zgled{Oglejmo si "se povezevo med podgrupo $G$ in tranzitivno permutatsko reprezentacijo G:
 
   \textsl{Grupa $G$ ima tranzitivno permutatsko reprezentacijo stopnje $n$ natanko tedaj, ko v $G$
   obstaja podgrupa indeksa $n$.}
 
   Naj bo grupa $G$, ki tranzitivno deluje na mno"zici $\Omega$, stopnje $n$. Po izreku \ref{Sem1trd4}
   velja $|G:G_a| = |\Omega| = n$ za vsak $a \in \Omega$. Stabilizator $G_a$ je torej podgrupa
   z indeksom $n$.
 
   Doka"zimo ekvivalenco "se v drugo smer. Naj bo $H$ podgrupa indeksa $n$ in 
   $\Omega = \{H, H g_1 , \ldots, H g_{n-1} \}$ mno"zica desnih odsekov podgrupe $H$ pogrupi $G$.
   Potem $G$ deluje tranzitivno na $\Omega$ z operacijo $(H g_i)^g = H (g_i g), \forall i = 1, 2, \ldots
   n-1$.}{}