Wykład rozwija aparat matematyczny niezbędny do konstruowania i analizy algorytmów. Składa się z elementów teorii grafów, teorii liczb i algebry.
Poznane już Twierdzenie Forda-Fulkersona orzeka, że w sieciach wartość maksymalnego przepływu i przepustowości minimalnego przekroju są sobie równe. Przyjrzymy się teraz dokładniej związkom tego typu, tzn. takim, w których maksymalizacja pewnej wartości jest równoważna minimalizacji innej. Związki takie są użyteczne, gdyż poszukiwanie jednej można zastąpić poszukiwaniem drugiej, co w praktyce może okazać się łatwiejsze. Zaczniemy od bliższego przyjrzenia się skojarzeniom i bardzo mocno z nimi związanym pokryciom grafu: wierzchołkowym i krawędziowym.
Skojarzenie w grafie \( \mathbf{G}=( V,E ) \) to taki zbiór krawędzi \( M\subseteq E \), w którym żadne dwie nie są incydentne z tym samym wierzchołkiem.
Skojarzenie maksymalne to skojarzenie o maksymalnej liczności.
Liczność maksymalnego skojarzenia w grafie \( \mathbf{G} \) oznaczamy przez \( \nu( \mathbf{G} ) \).
Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.
Pokrycie krawędziowe grafu \( \mathbf{G}=( V,E ) \) to taki podzbiór jego krawędzi \( E_0\subseteq E \), że każdy wierzchołek grafu \( \mathbf{G} \) jest incydentny z co najmniej jedną krawędzią w \( E_0 \).
Minimalne pokrycie krawędziowe to pokrycie krawędziowe wykorzystujące najmniejszą możliwą liczbę krawędzi. Liczbę krawędzi w minimalnym pokryciu krawędziowym oznaczamy przez \( \rho( \mathbf{G} ) \).
Pokrycie wierzchołkowe grafu \( \mathbf{G}=( V,E ) \) to taki podzbiór jego wierzchołków \( V_0\subseteq V \), że każda krawędź grafu \( \mathbf{G} \) jest incydentna z co najmniej jednym wierzchołkiem z \( V_0 \).
Minimalne pokrycie wierzchołkowe to najmniej liczne pokrycie wierzchołkowe. Liczność minimalnego pokrycia wierzchołkowego grafu \( \mathbf{G} \) oznaczamy przez \( \tau( \mathbf{G} ) \).
Zbiór niezależny w grafie \( \mathbf{G}=( V,E ) \) to taki zbiór wierzchołków \( I \), że graf indukowany \( \mathbf{G}|_I \) jest antykliką, tzn. \( {\sf E}\!(G|_I)=\emptyset \). Innymi słowy, zbiór niezależny składa się z wierzchołków niepołączonych.
Maksymalny zbiór niezależny to najbardziej liczny zbiór niezależny. Jego moc oznaczamy przez \( \alpha( \mathbf{G} ) \).
Twierdzenie 1.1 [T. Gallai 1959]
Dla grafu \( \mathbf{G} \) zachodzą:
Dowód <
Dla dowodu punktu pierwszego niech \( C_v \) będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze \( {\sf V}\!(\mathbf{G})- C_v \) istniały wierzchołki \( u,v \) połączone krawędzią, to taka krawędź \( uv \) nie byłaby incydentna z żadnym wierzchołkiem z \( C_v \), co przeczy temu, że \( C_v \) jest pokryciem. A zatem zbiór \( {\sf V}\!(\mathbf{G})- C_v \) jest niezależny i można go więc oszacować
\( \vert {\sf V}\!(\mathbf{G}) \vert-\tau( \mathbf{G} )=\vert {\sf V}\!(\mathbf{G})- C_v \vert\leq \alpha( \mathbf{G} ), \)
co daje \( \vert {\sf V}\!(\mathbf{G}) \vert\leq\tau( \mathbf{G} )+ \alpha( \mathbf{G} ). \) Z drugiej strony, jeśli \( I \) jest maksymalnym zbiorem niezależnym, to \( {\sf V}\!(\mathbf{G}) - I \) jest pokryciem wierzchołkowym. Tak więc
\( \tau( \mathbf{G} )\leq\vert {\sf V}\!(\mathbf{G}) - I \vert=\vert {\sf V}\!(\mathbf{G}) \vert-\alpha( \mathbf{G} ) \)
i w konsekwencji \( \tau( \mathbf{G} )+ \alpha( \mathbf{G} )\leq\vert {\sf V}\!(\mathbf{G}) \vert. \)
Dla dowodu punktu drugiego niech \( C_e \) będzie minimalnym pokryciem krawędziowym grafu \( \mathbf{G} \). Bez trudu można zauważyć, że pokrycie takie jest lasem (bo z każdego cyklu można usunąć jakąś krawędź i reszta dalej będzie pokryciem), w którym każda składowa spójna jest gwiazdą (bo z każdej ścieżki o długości co najmniej \( 3 \) można usunąć jedną wewnętrzna krawędź). Niech więc \( C_e \) składa się z \( s \) gwiazd. Wybierzmy z każdej gwiazdy po jednej krawędzi, konstruując w ten sposób jakieś skojarzenie \( M \) o mocy \( s \). Każda gwiazda ma o jeden więcej wierzchołków niż krawędzi, tak więc \( \vert {\sf V}\!(\mathbf{G}) \vert=\vert C_e \vert+s \), skąd natychmiast
\( \vert {\sf V}\!(\mathbf{G}) \vert=\vert C_e \vert+s=\vert C_e \vert+\vert M \vert\leq\rho( \mathbf{G} )+\nu( \mathbf{G} ). \)
Z drugiej strony, jeśli \( M' \) jest maksymalnym skojarzeniem w \( \mathbf{G} \), czyli \( \vert M' \vert=\nu( \mathbf{G} ) \), to zbiór \( I'={\sf V}\!(\mathbf{G})- {\sf V}\!(M) \) jest zbiorem niezależnym i ma \( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) \) elementów. Ponieważ \( \mathbf{G} \) nie ma punktów izolowanych, to każdy wierzchołek z \( I' \) jest połączony krawędzią z jakimś wierzchołkiem ze zbioru \( {\sf V}\!(M) \). Dla każdego wierzchołka \( v\in I' \) wybierzmy krawędź incydentną z \( v \). Tak powstały zbiór krawędzi w sumie z \( M \) tworzy pokrycie krawędziowe \( C_e' \) grafu \( \mathbf{G} \). W \( C_e' \) jest \( \nu( \mathbf{G} ) \) krawędzi ze skojarzenia \( M' \) oraz \( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) \) krawędzi incydentnych z elementami \( I' \). A zatem
\( \nu( \mathbf{G} )+( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) ) =\vert C_e' \vert\geq\rho( \mathbf{G} ), \)
i w konsekwencji \( \rho( \mathbf{G} )+\nu( \mathbf{G} )\leq \vert {\sf V}\!(\mathbf{G}) \vert \).
Twierdzenie 1.2
Jesli \( \mathbf{G} \) jest grafem prostym, to:
Dowód
Dla dowodu pierwszej równoważności zauważmy, jak w dowodzie Twierdzenia 1.1, że minimalne pokrycie \( C \) o \( \rho( \mathbf{G} ) \) krawędziach składa się z gwiazd. W każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków. Tak więc, na mocy Twierdzenia 1.1, liczba gwiazd jest równa \( \vert {\sf V}\!(\mathbf{G}) \vert-\rho( \mathbf{G} )=\nu( \mathbf{G} ) \). Wybierając teraz z każdej gwiazdy po jednej krawędzi dostaniemy ich dostatecznie dużo, by stanowiły skojarzenie maksymalne.
Dla dowodu implikacji odwrotnej znów skorzystamy z faktu, że pokrycie \( C \), jako minimalne w sensie inkluzji, składa się z gwiazd. A zatem, gdy \( C \) zawiera jakieś maksymalne skojarzenie \( M' \), to i \( M' \) musi zawierać po dokładnie jednej krawędzi z każdej gwiazdy pokrycia \( C \). Istotnie, gdyby jakaś gwiazda nie zawierała krawędzi z \( M' \), to \( M' \) nie było by maksymalne, a gdyby w gwieździe były dwie krawędzie z \( M' \), to \( M' \) nie byłoby skojarzeniem. Tak więc \( C \) składa się z \( \nu( \mathbf{G} ) \) gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie \( C \) ma \( \vert {\sf V}\!(\mathbf{G}) \vert-\nu( \mathbf{G} )=\rho( \mathbf{G} ) \) krawędzi, co kończy dowód.
Analogiczny dowód punktu drugiego pozostawiamy jako ćwiczenie 4.
Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych \( \mathbf{G}=( V_1\cup V_2,E ) \) wykorzystuje funkcję \( \Phi: \mathscr{P}\!( V_1 ) \longrightarrow \mathscr{P}\!( V_2 ) \) zdefiniowaną przez \( \Phi\!(A)=\lbrace v_2\in V_2:\ v_1 v_2\in E \mbox{ \rm i } v_1\in V_1 \rbrace \). Innymi słowy, \( \Phi\!(A) \) to zbiór tych wierzchołków z \( V_2 \), które sąsiadują z przynajmniej jednym wierzchołkiem w \( A\subseteq V_1 \). Przypomnijmy poznane już (z dowodem) Twierdzenie Hall'a.
Twierdzenie 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]
Niech \( \mathbf{G}=( V_1\cup V_2, E ) \) będzie grafem dwudzielnym. Wówczas pełne skojarzenie \( V_1 \) z \( V_2 \) istnieje wtedy i tylko wtedy, gdy \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego podzbioru \( A \) zbioru \( V_1 \).
Twierdzenie 1.4 [D. Konig 1931]
W grafie dwudzielnym \( \mathbf{G} \) liczba wierzchołków w minimalnym pokryciu wierzchołkowym jest równa maksymalnej liczności skojarzenia, tzn.
\( \tau( \mathbf{G} )=\nu( \mathbf{G} ). \)
Dowód
Niech \( M \) będzie maksymalnym skojarzeniem, a \( C_v \) minimalnym pokryciem wierzchołkowym w grafie \( \mathbf{G} \). Każda krawędź w \( M \) jest incydentna z jakimś wierzchołkiem pokrycia \( C_v \). Ponadto, każdy wierzchołek z \( C_v \) jest incydentny z co najwyżej jedną krawędzią skojarzenia \( M \). Tak więc
\( \nu( \mathbf{G} )\leq \tau( \mathbf{G} ). \)
Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli \( A\subseteq V_1\cap C_v \), to \( \vert A \vert \leq\vert \Phi\!(A)- C_v \vert \). Istotnie, inaczej zbiór \( (C_v\cup\Phi\!(A))- A \) byłby pokryciem wierzchołkowym o mocy istotnie mniejszej niż minimalne pokrycie \( C_v \). Tak więc Twierdzenie (Hall'a) 1.3 daje nam jakieś skojarzenie \( M_1 \) zbioru \( V_1\cap C_v \) z \( V_2- C_v \). Analogicznie otrzymamy jakieś skojarzenie \( M_2 \) zbioru \( V_2\cap C_v \) z \( V_1- C_v \). W efekcie zbiór \( M'=M_1\cup M_2 \) jest skojarzenie, wykorzystującym wszystkie punkty z \( C_v \). Ponadto, każda krawędź z \( M' \) jest incydentna z co najwyżej jednym wierzchołkiem z \( C_v \), co daje już pożądaną nierówność odwrotną
\( \tau( \mathbf{G} ) = \vert C_v \vert = \vert M' \vert \leq \nu( \mathbf{G} ). \)
Twierdzenie 1.5 [F.G.Frobenius, 1917]
Graf dwudzielny \( \mathbf{G}=( V_1\cup V_2, E ) \) ma skojarzenie doskonałe wtedy i tylko wtedy, gdy \( \vert V_1 \vert=\vert V_2 \vert \) oraz \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego podzbioru \( A \) zbioru \( V_1 \).
Dowód
Załóżmy najpierw, że \( M \) jest jakimś skojarzeniem doskonałym w grafie \( \mathbf{G} \). Oczywiście wierzchołki ze zbioru \( A\subseteq V_1 \) mogą być kojarzone tylko z własnymi sąsiadami, czyli z wierzchołkami ze zbioru \( \Phi\!(A) \). A zatem \( \vert A \vert \leq\vert \Phi\!(A) \vert \). Ponadto z faktu, że każdy element z \( V_1 \) jest skojarzony przez \( M \) z dokładnie jednym elementem z \( V_2 \), przy czym każdy wierzchołek z \( V_2 \) jest wykorzystany, otrzymujemy \( \vert V_1 \vert=\vert V_2 \vert \).
Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe \( C_v \) grafu \( \mathbf{G} \), czyli pokrycie o \( \tau( \mathbf{G} ) \) wierzchołkach. W grafie dwudzielnym zbiór \( V_1 \) jest też pokryciem, więc \( \vert C_v \vert\leq\vert V_1 \vert \). Z drugiej strony, aby krawędzie incydentne z wierzchołkami z \( V_1- C_v \) były pokryte przez \( C_v \), zbiór \( \Phi\!(V_1- C_v) \) musi zawierać się w \( C_v \). Tak więc
\( \vert V_1- C_v \vert\leq\vert \Phi\!(V_1- C_v) \vert\leq\vert V_2\cap C_v \vert, \)
co implikuje, że
\( \vert V_1 \vert=\vert V_1- C_v \vert+\vert V_1\cap C_v \vert\leq\vert V_2\cap C_v \vert+\vert V_1\cap C_v \vert=\vert C_v \vert. \)
Twierdzenie Koniga 1.4 daje teraz
\( \nu( \mathbf{G} )=\tau( \mathbf{G} )=\vert C_v \vert=\vert V_1 \vert=\vert V_2 \vert, \)
czyli dostarcza maksymalnego skojarzenia o \( \vert V_1 \vert=\vert V_2 \vert \) krawędziach. Skojarzenie takie musi być wobec tego doskonałe.
Pokazaliśmy jak wyprowadzić Twierdzienie Frobeniusa z Twierdzenia K{o}niga, a wcześniej jak otrzymać Twierdzenie K{o}niga z Twierdzenia Hall'a. Na zakończenie wykładu, wyprowadzimy Twierdzenie Hall'a z Twierdzenia Frobeniusa, pokazując tym samym, że w istocie te trzy twierdzenia mówią to samo.
Dowód [Inny dowód Twierdzenia Hall'a 1.3]
Niech \( \mathbf{G}=( V_1\cup V_2, E ) \) będzie grafem dwudzielnym. Załóżmy najpierw, że w \( \mathbf{G} \) istnieje pełne skojarzenie \( V_1 \) z \( V_2 \). W takim razie dla dowolnego zbioru \( A\subseteq V_1 \), zbiór \( \Phi\!(A) \) zawiera \( \vert A \vert \) różnych elementów skojarzonych odpowiednio z elementami z \( A \). A zatem \( \vert A \vert \leq\vert \Phi\!(A) \vert \).
Ciekawsza jest oczywiście implikacja odwrotna. Załóżmy więc, że
W szczególności \( \vert V_1 \vert\leq\vert \Phi\!(V_1) \vert\leq \vert V_2 \vert \).
Jeśli \( \vert V_1 \vert=\vert V_2 \vert \), to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc \( \vert V_1 \vert < \vert V_2 \vert \). Do grafu \( \mathbf{G} \) dodajmy zbiór nowych wierzchołków \( W \) o mocy \( \vert V_2 \vert-\vert V_1 \vert \) łącząc je ze wszystkimi elementami \( V_2 \). Otrzymamy w ten sposób nowy graf dwudzielny \( \mathbf{G}'=( V_1'\cup V_2',E' ) \), gdzie \( V_1'=V_1\cup W \) oraz \( V_2'=V_2 \). Jeśli \( A'\subseteq V_1' \) zawiera jakiś wierzchołek z nowo dodanego \( W \), to \( \Phi\!(A')=V_2=V_2' \), co pociąga za sobą, że \( \vert A' \vert\leq\vert \Phi\!(A') \vert \). Jeżeli zaś \( A' \) jest rozłączny z \( W \), czyli \( A'\subseteq V_1 \), to \( \Phi\!(A')=\Phi\!(A')\cap \Phi\!(V_1) \), a więc na mocy \( (*) \) dostajemy, że \( \vert A' \vert \leq\vert \Phi\!(A') \vert \).
To, wraz z oczywistą równością \( \vert V_1' \vert=\vert V_2' \vert \) czyni graf \( \mathbf{G}' \) podatnym na Twierdzenie Frobenius'a. Tym samym graf \( \mathbf{G}' \) ma jakieś skojarzenie doskonałe \( M' \). Usuwając teraz ze skojarzenia \( M' \) krawędzie incydentne z wierzchołkami w \( W \) dostajemy pożądane pełne skojarzenie \( V_1 \) z \( V_2 \) w grafie \( G \).
Zbiór częściowo uporządkowany (poset) to para \( \mathbf{P}=( X,\leq ) \), gdzie \( X \) jest zbiorem, zaś \( \leq \) jest dwuargumentową relacją określoną na \( X \), która dla dowolnie wybranych \( x,y,z\in X \) spełnia:
Uwaga
Częściowy porządek wygodnie przedstawiać jest przy użyciu tzw. diagramu Hassego, który przedstawia się na płaszczyźnie \( \mathbb{R}^2 \) w następujący sposób:
Dla elementów \( x,y\in X \), jeśli \( y < x \), to punkt przypisany elementowi \( x \) jest powyżej punktu przypisanemu elementowi \( y \).
Łańcuch w zbiorze częściowo uporządkowanym \( \mathbf{P}=( X,\leq ) \) to taki podzbiór \( C \) zbioru \( X \), że dla dowolnych \( x,y\in X \) zachodzi:
Antyłańcuch w zbiorze częściowo uporządkowanym \( \mathbf{P}=( X,\leq ) \) to taki podzbiór \( A \) zbioru \( X \), że dla dowolnych \( x,y\in X \) zachodzi:
Szerokość posetu \( \mathbf{P}=( X,\leq ) \) to maksymalny możliwy rozmiar antyłańcucha w \( \mathbf{P} \). Szerokość oznaczana będzie za pomocą \( {\sf width}\!( \mathbf{P} ) \).
W ogólności szerokość \( {\sf width}\!( Y ) \) można zdefiniować dla dowolnego podzbioru \( Y\subseteq X \), jako największy możliwy rozmiar antyłańcucha zawartego w \( Y \).
Pokrycie łańcuchowe posetu \( \mathbf{P}=( X,\leq ) \) to taka rodzina łańcuchów \( C_1,\ldots C_k \), że
Twierdzenie 2.1 [R. P. Dilworth 1950]
Minimalna liczba łańcuchów pokrywających poset \( \mathbf{P} \) jest równa szerokości posetu \( \mathbf{P} \).
Dowód
Oczywiście liczba łańcuchów pokrywających poset nie może być mniejsza niż jego szerokość, bo każdy punkt w antyłańcuchu realizującym tę szerokość musi być pokryty innym łańcuchem.
Dowód implikacji odwrotnej przeprowadzimy indukcyjnie ze względu na liczność \( n \) posetu \( \mathbf{P}=( P,\leq ) \). Niech \( w={\sf width}\!( \mathbf{P} ) \). Rozważmy maksymalny, w sensie inkluzji, łańcuch \( C \) zawarty w \( \mathbf{P} \). Po usunięciu łańcucha \( C \) szerokość posetu może zmniejszyć się co najwyżej o jeden. Dowód podzielimy więc na dwa przypadki:
Na mocy założenia indukcyjnego poset \( P- C \) daje się pokryć \( w-1 \) łańcuchami, które wobec tego wraz z \( C \) tworzą szukane pokrycie całego posetu \( \mathbf{P} \) za pomocą \( w \).
Niech \( A \) bedzie antyłańcuchem realizującym szerokość zbioru \( P- C \), tzn. \( \vert A \vert=w \). Połóżmy:
Jeśli \( U=P \), to łańcuch \( C \) całkowicie zawiera się w \( U \). Z definicji zbioru \( U \) wynika, że istnieje element \( a_0\in A \), który jest mniejszy od najmniejszego elementu łańcucha \( C \), a tym samym od wszystkich elementów w \( C \). Skoro \( A \subseteq P- C \), to \( a_0\not\in C \) i w konsekwencji \( \lbrace a_0 \rbrace\cup C \) jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha \( C \). To pokazuje, że \( \vert U \vert < \vert P \vert \). Podobnie możemy uzasadnić, że również \( \vert D \vert < \vert P \vert \). Do obu zbiorów \( U,D \) możemy więc zastosować założenie indukcyjne, dostając ich pokrycia łańcuchowe
\( U=C_1\cup\ldots\cup C_w,\quad D=C_1'\cup\ldots\cup C_w'. \)
Ponieważ \( A \subseteq D \cap U \), to każdy element z \( A \) należy do jakiegoś łańcucha \( C_i \) i do jakiegoś łańcucha \( C_j' \). Z drugiej strony fakt, że \( A \) jest \( w \)-elementowym antyłańcuchem gwarantuje, że w każdym łańcuchu postaci \( C_i \) lub \( C_j' \) jest jakiś element z \( A \). Pozwala to na takie przenumerowanie łańcuchów \( C_i \) i \( C_j' \), by \( C_i\cap C_j'\neq \emptyset \), tzn. że dla \( a\in A \) mamy \( a \in C_i \) wtedy i tylko wtedy, gdy \( a\in C_i' \). To z kolei oznacza, że każda suma \( C_i\cup C_i' \) jest łańcuchem. Oczywiście te nowe łańcuchy \( C_i\cup C_i' \) pokrywają zbiór \( D\cup U \). Zauważmy jednak, że \( D\cup U=P \), bo inaczej istniałby element \( p\in P \) nieporównywalny z żadnym elementem antyłańcucha \( A \), czyli \( A\cup \lbrace p \rbrace \) byłby antyłańcuchem istotnie większym niż maksymalny antyłańcuch \( A \). W konsekwencji otrzymujemy pokrycie łańcuchowe
\( P=(C_1\cup C_1')\cup\ldots\cup(C_w\cup C_w') \)
całego zbioru \( P \).
Pokrycie antyłańcuchowe posetu \( \mathbf{P}=( X,\leq ) \) to taka rodzina antyłańcuchów \( A_1,\ldots A_k \), że
\( A_1\cup\ldots\cup A_k=X. \)
Twierdzenie 2.2 [Dualne Twierdzenie Dilworth'a]]
Minimalna liczba antyłańcuchów pokrywających poset \( \mathbf{P}=( P,\leq ) \) jest równa maksymalnej liczności łańcucha zawartego w \( \mathbf{P} \).
Pokrycie antyłańcuchowe posetu \( \mathbf{P}_0 \)
Dowód
Moc najdłuższego łańcucha oznaczmy przez \( h \). Niech \( A_i \) będzie zbiorem elementów \( p\in P \) spełniających:
najliczniejszy łańcuch jest mocy \( i \).
Pokażemy, że każde \( A_i \) jest antyłańcuchem. Istotnie, gdyby dwa różne elementy \( p_1,p_2\in A_i \) były porównywalne, to możemy bez straty ogólności założyć, że \( p_1 < p_2 \). Ponieważ \( p_2 \in A_i \), to w zbiorze \( p_2\!\uparrow \) jest łańcuch o liczności \( i \).
Łańcuch ten jednak można by przedłużyć (od dołu) do liczniejszego łańcucha \( \lbrace p_1 \rbrace\cup C_2 \). To oczywiście przeczy temu, że \( p_1\in A_i \). Zatem istotnie każde \( A_i \) jest antyłańcuchem. Intuicyjnie antyłańcuchy \( A_i \) to kolejne piętra posetu \( \mathbf{P} \). Oczywiście każdy punkt \( p \in P \) musi być w którymś ze zbiorów \( A_1,\ldots,A_h \), bo \( p\!\uparrow \) nie może zawierać łańcuchów liczniejszych niż \( h \). Dostaliśmy więc następujące pokrycie antyłańcuchami:
Oczywiście pokrycie to jest najmniej liczne, bo w każdym pokryciu każdy spośród \( h \) punktów najdłuższego łańcucha musi leżeć w innym antyłańcuchu.
Wniosek 2.3
Każdy zbiór częściowo uporządkowany o \( rs+1 \) elementach zawiera łańcuch o liczności \( r+1 \) lub antyłańcuch o liczności \( s+1 \).
Dowód
Niech \( \mathbf{P}=( P,\leq ) \) będzie posetem, w którym każdy łańcuch jest liczności co najwyżej \( r \), a każdy antyłańcuch jest liczności co najwyżej \( s \). Dualne Twierdzenie Dilworth'a 2.2 dostarcza pokrycie antyłańcuchami
\( P=A_1\cup\ldots\cup A_{r'}, \)
gdzie \( r'\leq r \) jest mocą łańcucha o maksymalnej liczności. Ponieważ \( \vert A_i \vert\leq s \), to
\( \vert P \vert=\vert A_1 \vert+\ldots+\vert A_{r'} \vert\leq r's\leq rs. \)
Sprzeczność ta pokazuje, że jeśli \( \mathbf{P} \) ma co najmniej \( rs+1 \) elementów, to musi zawierać łańcuch o liczności \( r+1 \) lub antyłańcuch o liczności \( s+1 \).
Uwaga
Dowód wniosku 2.3 można równie dobrze przeprowadzić opierając się na Twierdzeniu Dilworth'a 2.1, co pozostawiamy jako ćwiczenie 3.
Jednym z ciekawszych wniosków z Twierdzenia Dilworth'a jest fakt, że każdy ciąg \( r^2+1 \) liczb rzeczywistych zawiera podciąg monotoniczny o \( r+1 \) elementach. Pierwszy dowód tego twierdzenia przedstawili P. Erd{o}s oraz G. Szekres w 1939 roku. Poniżej przedstawione jest uogólnienie tego twierdzenia, którego uzasadnienie będzie korzystało z wniosku 2.3.
Twierdzenie 2.4
Każdy ciąg \( n\geq rs+1 \) liczb rzeczywistych zawiera podciąg niemalejący o długości \( r+1 \) lub podciąg malejący o długości \( s+1 \).
Dowód
Niech \( A=( a_1,\ldots,a_n ) \) będzie ciągiem liczb rzeczywistych. Na parach postaci \( ( i,a_i ) \), wprowadzamy relację częściowego porządku kładąc
\( ( i,a_i )\leq( j,a_j ) \) wtedy i tylko wtedy, gdy \( i\leq j \) oraz \( a_i\leq a_j \).
Łańcuchy w tym porządku, to nic innego jak podciągi niemalejące ciągu \( A \), a antyłańcuchy to podciągi malejące ciągu \( A \). Po tym utożsamieniu wystarczy powołać się na Wniosek 2.3.
Dla dowolnego zbioru \( X \) rodzina \( \mathscr{P}\!( X ) \) jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany \( ( \mathscr{P}\!( X ),\subseteq ) \).
Rodzina Sperner'a podzbiorów zbioru \( X \) to antyłańcuch w posecie \( ( \mathscr{P}\!( X ),\subseteq ) \).
Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu \( ( \mathscr{P}\!( X ),\subseteq ) \). Poniższe twierdzenie pomaga odpowiedzieć na to pytanie.
Twierdzenie 2.5 [K. Yamamoto 1954; L. D. Meshalkin 1963; D. Lubell 1966]
Niech \( \lbrace A_1,\ldots,A_m \rbrace \) będzie rodziną Spernera podzbiorów zbioru \( X \). Wówczas
\( \sum_{i=1}^{m}{\vert X \vert \choose \vert A_i \vert}^{-1}\leq 1. \)
Dowód [D. Lubell]
Niech \( n=\vert X \vert \). W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) każdy maksymalny łańcuch
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X \)
musi spełniać \( \vert C_j \vert=j \). Zbiór \( C_1 \) może być wybrany na \( n \) sposobów, z kolei \( C_2 \) na \( n-1 \) sposobów. W ogólności \( C_j \) może być wybrany na \( n-j+1 \) sposobów. Czyli łącznie jest \( n! \) różnych łańcuchów maksymalnych.
Z drugiej strony policzymy ile jest łańcuchów, w których występuje konkretny zbiór \( A_i \) z rodziny Spernera, tzn.
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{\vert A_i \vert}=A_i \subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X \)
Ponieważ singleton \( C_1 \) musi zawierać się w \( A_i \), może być wybrany na \( \vert A_i \vert \) sposobów. Tak więc \( C_2 \) może być wybrane już jedynie na \( \vert A_i \vert-1 \) sposobów i tak dalej. A zatem różnych łańcuchów postaci
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{\vert A_i \vert}=A_i \)
jest \( \vert A_i \vert! \). W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci
\( A_i=C_{\vert A_i \vert}\subseteq C_{\vert A_i \vert+1}\subseteq\ldots\subseteq C_n=X \)
jest \( ( n-\vert A_i \vert )! \). Podsumowując, liczba maksymalnych łańcuchów, w których występuje \( A_i \) wynosi \( \vert A_i \vert!( n-\vert A_i \vert )! \).
Ponieważ \( \lbrace A_1,\ldots,A_m \rbrace \) jest antyłańcuchem, to dla \( i\neq j \) w łańcuchu nie mogą wystąpić równocześnie \( A_i \) i \( A_j \). Zliczając teraz maksymalne łańcuchy przechodzące przez któreś \( A_i \), możemy pominąć jakiś łańcuch maksymalny. Nie mniej jednak mamy
\( \sum_{i=1}^m{\vert A_i \vert!( n-\vert A_i \vert )!}\leq n!. \)
To w konsekwencji daje
\( \sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}} =\sum_{i=1}^m{\frac{\vert A_i \vert!( n-\vert A_i \vert )!}{n!}} \leq 1. \)
Przykład
Oczywiście, dla ustalonego \( k \) rodzina \( k \)-elementowych podzbiorów jest rodziną Spernera. Ponieważ wartość \( {n\choose k} \) jest maksymalna dla \( k=/n/2\rfloor \), to \( n \)-elementowy podzbiór ma rodzinę Spernera o mocy \( {n \choose /n/2\rfloor} \). Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.
Twierdzenie 2.6 [E. Sperner 1928]
Jeśli \( \mathscr{A} \) jest rodziną Spernera podzbiorów zbioru \( X \), to
\( \vert \mathscr{A} \vert\leq{\vert X \vert\choose\lfloor\vert X \vert/2\rfloor}. \)
Dowód
Niech \( n=\vert X \vert \) oraz \( \mathscr{A}=\lbrace A_1,\ldots,A_m \rbrace \). Wartość \( {n\choose k} \) jest maksymalna dla \( k=/2\rfloor \). Tak więc \( {n\choose\vert A_i \vert}\leq{n\choose{n/2}} \). Na mocy Twierdzenia 2.5 otrzymujemy:
\( m\frac{1}{{n \choose/2\rfloor }}\leq\sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}}\leq 1, \)
skąd natychmiast
\( m\leq{n\choose/2\rfloor}. \)
Uwaga
W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) dowolne dwa jego elementy \( A,B\in\mathscr{P}\!( X ) \) spełniają:
W takim razie dowolne dwa elementy posetu \( ( \mathscr{P}\!( X ),\subseteq ) \) mają najmniejsze ograniczenie górne oraz największe ograniczenie dolne. Posety o tej własności nazywane są kratami.
Krata to częściowy porządek \( \mathbf{P}=( P,\leq ) \), w którym dla dowolnych \( a,b\in P \) istnieją
Kres dolny oznaczać bedziemy przez \( a \wedge b \).
Kres dolny oznaczać bedziemy przez \( a \vee b \).
Przykład
Rozważmy zbiór liczb naturalnych \( \mathbb{N} \) oraz relacje \( \sqsubseteq \) zdefiniowaną w następujący sposób
\( a \sqsubseteq b\quad\textrm{wtedy i tylko wtedy, gdy}\quad a\ \textrm{dzieli}\ b\quad\textrm{dla}\ a,b\in\mathbb{N}. \)
Relacja \( \sqsubseteq \) jest zwrotna, antysymetryczna, i przechodnia. Tak więc para \( ( \mathbb{N},\sqsubseteq ) \) tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że \( ( \mathbb{N},\sqsubseteq ) \) jest kratą, oraz że kres dolny dwu liczb naturalnych to ich największy wspólny dzielnik, a kres ich kres górny to najmniejsza wspólna wielokrotność.
W tym wykładzie spróbujemy odpowiedzieć na niektóre pytania typu: jak bardzo musi być liczny dany zbiór, by wystąpiła w nim pożądana przez nas konfiguracja. Widzieliśmy, że na aby mieć gwarancję, że \( \mathbf{G}=( V,E ) \) jest spójny, potrzeba by miał on więcej niż \( \vert V \vert\cdot(\vert V \vert-1)/2 \) krawędzi. Najprostszym jednak warunkiem tego typu jest Zasada Szufladkowa Dirichleta i następujące jej uogólnienie.
Twierdzenie 3.1 [Uogólniona Zasada Szufladkowa Dirchlet'a]
Dla dowolnej liczby \( q\in\mathbb{N} \), jeśli \( X=X_1\cup\ldots\cup X_t \) oraz \( \vert X \vert\geq (q-1)t+1 \), to dla któregoś \( i \) mamy \( \vert X_i \vert\geq q \).
Dowód
Wykorzystując założenia twierdzenia otrzymujemy następujące oszacowanie:
\( (q-1)t+1\leq\vert X \vert =\vert X_1\cup\ldots\cup X_t \vert \leq\vert X_1 \vert+\ldots+\vert X_t \vert \leq t\cdot \max_{i=1,\ldots, t}{\vert X_i \vert}. \)
Tak więc
\( (q-1)+\frac{1}{t}=\frac{(q-1)t+1}{t}\leq\max_{i=1,\ldots, t}{\vert X_i \vert}. \)
Ponieważ moce zbiorów \( X_i \) są liczbami całkowitymi otrzymujemy, że ta maksymalna musi wynosić co najmniej \( q \).
Uogólniona Zasada Szufladkowa wymusza, że któryś składnik podziału musi mieć co najmniej \( q \) elementów. Zasadę tę można uogólnić w ten sposób, by zadając najpierw ciąg liczb naturalnych \( q_1,\ldots,q_k \), w miejsce jednej liczby \( q \), i podział \( X=X_1\cup\ldots\cup X_t \) żądać by któryś składnik \( X_i \) był co najmniej \( q_i \) elementowy. Otrzymujemy w ten sposób Zasadę Podziałową. Przy wszystkich \( q_i=q \) jest to Twierdzenie 3.1.
Twierdzenie 3.2 [Zasada podziałowa]
Niech \( q_1,\ldots,q_k \) będzie ciągiem liczb naturalnych. Jeśli
\( X=X_1\cup\ldots\cup X_t\quad\textrm{oraz}\quad\vert X \vert>( \sum_{i=1}^t{q_i} )-t, \)
to \( \vert X_i \vert\geq q_i \) dla pewnego \( i \).
Dowód
Załóżmy, wbrew tezie twierdzenia, że jakiś \( X \) o mocy \( \vert X \vert\geq( \sum_{i=1}^t{q_i} )-t+1 \) rozkłada się na sumę \( X=X_1\cup\ldots\cup X_t \), przy czym każdy składnik ma moc \( \vert X_i \vert\leq q_i-1 \). Wtedy nierówność dwu skrajnych liczb w
\( ( \sum_{i=1}^t{q_i} )-t+1\leq\vert X \vert =\vert X_1\cup\ldots\cup X_t \vert \leq\vert X_1 \vert+\ldots+\vert X_t \vert \leq \sum_{i=1}^t( q_i-1 ), \)
stoi w sprzeczności, i kończy dowód.
Można też pytać o liczbę wierzchołków w grafie wymuszających jedną z pożądanych konfiguracji.
Twierdzenie 3.3 [F.P.Ramsey 1930]
Dla dowolnej liczby \( r\in\mathbb{N} \), jeżeli tylko graf prosty \( \mathbf{G} \) posiada co najmniej \( 2^{2r-1} \) elementów, to \( \mathbf{G} \) zawiera jako podgraf indukowany klikę \( \mathcal{K}_{r} \) lub antyklikę \( \mathcal{A}_{r} \).
Dowód
Niech \( n:=\vert \mathbf{G} \vert\geq 2^{2r-1} \). Dla każdego \( x\in{\sf V}\!(\mathbf{G}) \) definiujemy dwa zbiory: odpowiednio zbiór sąsiadów wierzchołka \( x \) oraz zbiór elementów nie będących sąsiadami \( x \):
\( \begin{align*} {\sf N}_{\mathbf{G}}\!( x ) & =\lbrace y\in{\sf V}\!(\mathbf{G}):\ xy\in{\sf E}\!(\mathbf{G}) \rbrace, \\ {\sf A}_{\mathbf{G}}\!( x ) & =\lbrace y\in{\sf V}\!(\mathbf{G}):\ xy\notin{\sf E}\!(\mathbf{G}) \rbrace. \end{align*} \)
Zdefiniujemy ciąg grafów \( \mathbf{G}_0, \mathbf{G}_1, \ldots, \mathbf{G}_{2r-1} \). Niech \( \mathbf{G}_0:=\mathbf{G} \). Wybierzmy jakiś element \( x_1\in{\sf V}\!(\mathbf{G}) \) i zdefiniujmy podgraf \( \mathbf{G}_1 \) grafu \( \mathbf{G}_0=\mathbf{G} \) w następujący sposób
\( \mathbf{G}_1 = \left\{ \begin{array} {ll} {\mathbf{G}_0}|_{{\sf N}_{{\mathbf{G}_0}}\!( x_1 )}, & \textrm{jeżeli}\ \vert {\sf A}_{\mathbf{G}_0}\!( x_1 ) \vert\leq\vert {\sf N}_{\mathbf{G}_0}\!( x_1 ) \vert, \\ {\mathbf{G}_0}|_{{\sf A}_{\mathbf{G}_0}\!( x_1 )}, & \textrm{w przeciwnym wypadku.} \end{array} \right . \)
Zauważmy, że \( \vert {\sf V}\!(\mathbf{G}_1) \vert\geq2^{2r-2} \). Następnie wybieramy dowolny element \( x_2\in{\sf V}\!(\mathbf{G}_1) \) i analogicznie definiujemy \( \mathbf{G}_2 \). W ogólności dla \( i=1,\ldots,2r-1 \) graf \( \mathbf{G}_i \) definiujemy poprzez
\( \mathbf{G}_i = \left\{ \begin{array} {ll} {\mathbf{G}_{i-1}}|_{{\sf N}_{\mathbf{G}_{i-1}}\!( x_i )}, & \textrm{jeżeli}\ \vert {\sf A}_{\mathbf{G}_{i-1}}\!( x_i ) \vert\leq\vert {\sf N}_{\mathbf{G}_{i-1}}\!( x_i ) \vert, \\ {\mathbf{G}_{i-1}}|_{{\sf A}_{\mathbf{G}_{i-1}}\!( x_i )}, & \textrm{w przeciwnym wypadku,} \end{array} \right . \)
gdzie \( x_{i-1} \) jest dowolnie wybranym elementem ze zbioru \( {\sf V}\!(\mathbf{G}_{i-1}) \). Każdy kolejny graf zmniejszy się o co najwyżej połowę elementów, tak więc cały czas zachowana jest własność
\( \vert {\sf V}\!(\mathbf{G}_i) \vert\geq2^{2r-(i+1)}. \)
To z kolei implikuje, że dla \( i\leq 2r-1 \) zbiór \( {\sf V}\!(\mathbf{G}_i) \) jest niepusty, co pozwala zawsze na wybór kolejnych \( 2r-) \) wierzchołków \( x_1,\ldots,x_{2r-1} \) potrzebnych do zdefiniowania kolejnych grafów \( \mathbf{G}_i \). Każdy element \( x_i \) albo sąsiaduje ze wszystkimi wierzchołkami grafu \( \mathbf{G}_i \) albo też nie jest połączony krawędzią z żadnym z wierzchołków w \( \mathbf{G}_i \). Tak więc w ciągu \( x_1,\ldots,x_{2r-1} \) można wyróżnić podciąg \( x_{j_1},\ldots,x_{j_s} \) elementów pierwszego typu oraz podciąg \( x_{l_1},\ldots,x_{l_t} \) elementów drugiego typu. Element \( x_{j_1} \) sąsiaduje z każdym elementem z \( {\sf V}\!(\mathbf{G}_{j_1}) \), a więc także z każdym \( x_{j_i} \) dla \( i\geq 2 \). Z kolei \( x_{j_2} \) sąsiaduje z każdym elementem z \( {\sf V}\!(\mathbf{G}_{j_2}) \), a więc także z każdym \( x_{j_i} \) dla \( i\geq 3 \) i tak dalej. Zatem zbiór wierzchołków \( \lbrace x_{j_1},\ldots,x_{j_s} \rbrace \) w grafie \( \mathbf{G} \) indukuje \( s \)-elementową klikę. Analogicznie \( \mathbf{G}|_{\lbrace x_{l_1},\ldots,x_{l_t} \rbrace} \) jest \( t \)-elementową antykliką. Oczywiście \( s+t=2r-1 \). Tak więc na mocy Uogólnionej Zasady Szufladkowej Dirichlet'a otrzymujemy, że \( s\geq r \) albo \( t\geq r \), co kończy dowód.
Zauważmy, że zarówno Zasadę Podziałową (Twierdzenie 3.2), jak i Twierdzenie 3.3 można wypowiedzieć w tym samym języku. Niech \( \mathscr{P}_{r}\!( X ) \) będzie rodziną \( r \)-elementowych podzbiorów zbioru \( X \). Tak więc pokrycie \( X=X_1\cup\ldots\cup X_k \) to nic innego jak pokrycie rodziny \( \mathscr{P}_{1}\!( X )=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_k \), gdzie \( \mathscr{A}_i=\lbrace \lbrace x \rbrace:\ x\in X_i \rbrace \). Oznacza to, że w Zasadzie Podziałowej żądamy podzbioru \( Y\subseteq X \), dla którego istnieje \( i \), takie że \( \vert Y \vert= q_i \) oraz że dowolny singleton zawarty w \( Y \) należy do \( \mathscr{A}_i \).
Z drugiej strony graf prosty z Twierdzenia 3.3 to para \( \mathbf{G}=( V,E ) \), gdzie \( E\subseteq\mathscr{P}_{2}\!( V ) \). Daje to więc podział \( \mathscr{P}_{2}\!( V )=E\cup( \mathscr{P}_{2}\!( V )- E ) \). Żądanie \( r \)-elementowej kliki jest żądaniem \( r \)-elementowego podzbioru \( K \) zbioru \( V \) takiego, że dowolna "krawędź" pomiędzy elementami w \( K \), czyli dowolny element \( \mathscr{P}_{2}\!( K ) \), jest \( E \). Analogicznie poszukiwana antyklika jest po prostu podzbiorem \( A \) zbioru \( V \) takim, że \( \mathscr{P}_{2}\!( A )\subseteq \mathscr{P}_{2}\!( V )- E \).
Następne twierdzenie jest uogólnieniem Twierdzeń 3.1, 3.2, oraz 3.3. Warto zauważyć, że poniższe twierdzenie Ramsey'a nie podaje niestety minimalnego oszacowania na moc zbioru \( X \). Nie podamy też w tym wykładzie jego dowodu.
Twierdzenie 3.4 [F. P. Ramsey 1930]
Dla dowolnych \( r,t\in\mathbb{N} \) oraz dla dowolnego ciągu liczb naturalnych \( q_1,\ldots, q_t \) istnieje liczba \( n \) o następującej własności:
\( \mathscr{P}_{r}\!( X )=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t \), istnieje podzbiór \( Y \) zbioru \( X \) o co najmniej \( q_i \) elementach taki, że \( \mathscr{P}_{r}\!( Y )\subseteq \mathscr{A}_i \) przy pewnym \( i=1,\ldots,t \).
Liczba Ramseya \( {\sf R}_{r}\!( q_1,\ldots,q_t ) \) to najmniejsza taka liczba \( n\in\mathbb{N} \), dla której spełniony jest warunek \( (*) \).
Szczególnym przypadkiem jest \( {\sf R}\!( q_1,\ldots,q_t ):={\sf R}_{2}\!( q_1,\ldots,q_t ) \).
Wielu matematyków fascynowały i nadal fascynują liczby Ramsey'a. W szczególności dlatego, że bardzo mało nich wiemy. Poniższa tabela przedstawia dotychczasową wiedzę na temat liczb \( {\sf R}_{2}\!( m,n ) \). Jak widać nawet dla małych wartości \( n \) oraz \( m \), dokładne wartości liczb \( {\sf R}_{2}\!( m,n ) \) nie są znane.
\( \begin{array} {|c||c|c|c|c|c|c|c|c|} \hline n\downarrow\ marrow & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \hline 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 3 & & 6 & 9 & 14 & 18 & 23 & 28\leq\ldots\leq29 & 36 \\ \hline 4 & & & 18 & 25\ldots\leq29 & 34\leq\ldots\leq36 & & & \\ \hline 4 & & & & 42\leq\ldots\leq55 & 57\leq\ldots\leq94 & & & \\ \hline 4 & & & & & 102\leq\ldots\leq178 & & & \\ \hline \end{array} \)
Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a \( {\sf R}\!( q_1,\ldots,q_t ) \) przedstawimy kilka twierdzeń przybliżających te liczby.
Uwaga
Wartość liczby Ramsey'a z indeksem \( r=1 \) jest opisana w Zasadzie Podziałowej (Twierdzenie 3.2). Zasadę tę można przeformułować jako:
\( {\sf R}_{1}\!( q_1,\ldots,q_t )=( \sum_{i=1}^t{q_i} )-t+1. \)
Dla liczb Ramsey'a z indeksem \( r=2 \) podamy, bez dowodu, następujące oszacowanie górne.
Twierdzenie 3.5
\( {\sf R}\!( q_1,\ldots,q_t )\leq\frac{t^{q_1+\ldots+q_t-2t+1}-1}{t-1}+1. \)
Z uwagi na Twierdzenie 3.3, ważną rolę odgrywają liczby Ramsey'a postaci \( {\sf R}_{r}\!( m,n ) \) a w szczególności \( {\sf R}\!( m,n )={\sf R}_{2}\!( m,n ) \). O nich możemy powiedzieć już trochę więcej w tym wykładzie.
Twierdzenie 3.6
Dla dowolnych \( m, n \geq 2 \) oraz \( r \geq 1 \) mamy:
\( {\sf R}_{r}\!( m,n )\leq {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1. \)
Dowód
Niech \( X \) będzie zbiorem o \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1 \) elementach, \( x_0\in X \) i \( X'=X-\lbrace x_0 \rbrace \). Wtedy każdy podział \( \mathscr{P}_{r}\!( X )=\mathscr{A}_1\cup\mathscr{A}_2 \) indukuje podział \( \mathscr{P}_{r-1}\!( X' )=\mathscr{A}'_1\cup\mathscr{A}'_2 \), gdzie
\( \begin{align*} \mathscr{A}'_1 & = \lbrace A-\lbrace x_0 \rbrace :\ A\in\mathscr{A}_1\ \ & \ x_0\in A \rbrace, \\ \mathscr{A}'_2 & = \lbrace A-\lbrace x_0 \rbrace :\ A\in\mathscr{A}_2\ \ & \ x_0\in A \rbrace. \end{align*} \)
Ponieważ moc \( \vert X-\lbrace x_0 \rbrace \vert \) realizuje liczbę Ramsey'a \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) ) \), to w zbiorze \( X-\lbrace x_0 \rbrace \)
lub też
Bez straty ogólności załóżmy, że zachodzi przypadek pierwszy. Z definicji liczb Ramsey'a oraz z faktu, że \( \vert X_1 \vert={\sf R}_{r}\!( m-1,n ) \) otrzymujemy następujące dwa przypadki, których analiza jest podobna:
Z uwagi na symetrię przeanalizujemy jedynie pierwszy przypadek. Niech \( A\subseteq X_{11}\cup\lbrace x_0 \rbrace \) ma \( r \)-elementów. Jeśli \( x_0\not\in A \), to \( A \) zawiera się w \( X_{11} \), i co za tym idzie, \( A \) należy do \( \mathscr{A}_1 \). Jeśli zaś \( x_0\in A \), to \( A-\lbrace x_0 \rbrace \) jest \( (r-1) \)-elementowym podzbiorem zbioru \( X_1 \). A więc należy do \( \mathscr{A}'_1 \). Z definicji rodziny \( \mathscr{A}'_1 \) otrzymujemy, że i w tym przypadku \( A \) należy do \( \mathscr{A}_1 \).
W konsekwencji otrzymujemy, że w \( X \) istnieje podzbiór \( Y_1 \) (w rozpatrzonym przypadku jest to \( X_{11}\cup\lbrace x_0 \rbrace \)), którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_1 \), lub też w \( X \) istnieje podzbiór \( Y_2 \) (w rozpatrzonym przypadku jest to \( X_{12} \)), którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_2 \). Ponieważ zbiór \( X \) ma moc \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1 \), to
\( {\sf R}_{r}\!( m,n )\leq {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1. \)
Twierdzenie 3.7
Dla dowolnych \( m, n \geq 2 \)
\( {\sf R}\!( m,n )\leq {{m+n-2}\choose{m-1}}. \)
Dowód
Dowód przeprowadzimy indukcyjnie ze względu na \( n \) oraz \( m \). Dla \( n=2 \) zachodzi równość
\( {\sf R}\!( m,2 )=m={{m}\choose{1}}={{m+n-2}\choose{m- 1}}, \)
a dla \( m=2 \) zachodzi równość
\( {\sf R}\!( 2,n )=n={{n}\choose{1}}={{m+n-2}\choose{m-1}}. \)
Przejdźmy więc do przypadku, gdy \( n,m>2 \). Na mocy założenia indukcyjnego mamy:
\( {\sf R}\!( m-1,n )\leq{{m+n-3}\choose{m-2}},\quad{\sf R}\!( m,n-1 )\leq{{m+n-3}\choose{m-1}}. \)
Dla \( r=2 \) Twierdzenie 3.6 mówi, że
\( {\sf R}_{2}\!( m,n )\leq{\sf R}_{1}\!( {\sf R}_{2}\!( m-1,n ),{\sf R}_{2}\!( m,n-1 ) )+1 = {\sf R}_{2}\!( m-1,n ) + {\sf R}_{2}\!( m,n-1 ). \)
Tak więc
\( \begin{align*} {\sf R}\!( m,n ) & \leq{\sf R}\!( m-1,n ) + {\sf R}\!( m,n-1 ) \\ & \leq{{m+n-3}\choose{m-2}}+{{m+n-3}\choose{m-1}} \\ & ={{m+n-2}\choose{m-1}}, \end{align*} \)
co kończy dowód.
Przejdziemy teraz do szacowania liczb Ramsey'a od dołu. Do tego celu potrzebować będziemy następującej definicji.
Dwukolorowalna rodzina \( n \)-elementowych podzbiorów zbioru \( X \) to rodzina \( \mathscr{X}\subseteq\mathscr{P}_{n}\!( X ) \), dla której istnieje takie kolorowanie elementów zbioru \( X \) dwoma kolorami tak, by żaden zbiór \( A\in\mathscr{X} \) nie składał się z elementów tego samego koloru.
Innymi słowy, rodzina \( \mathscr{X} \) jest dwukolorowalna, jeśli istnieje podzbiór \( C\subseteq X \) taki, że
\( \emptyset\neq C \cap A \neq A\quad\textrm{dla każdego}\ A\in\mathscr{X}. \)
Twierdzenie 3.8
Niech \( n\geq 1 \) oraz \( \mathscr{X}\subseteq \mathscr{P}_{n}\!( X ) \). Jeśli \( \vert X \vert < 2^{n-1} \), to rodzina \( \mathscr{X} \) jest dwukolorowalna.
Dowód
Niech \( m:=\vert X \vert \). Policzmy pary w zbiorze
\( \mathscr{A}=\lbrace ( A,C ):\ A\in\mathscr{X} \mbox{ i } ( A\subseteq C \mbox{ albo } A\subseteq X- C ) \rbrace. \)
Liczba podzbiorów zbioru \( X \) zawierających \( A \) jest równa liczbie podzbiorów zbioru \( X \) rozłącznych z \( A \), i ponieważ \( \vert A \vert=n \), to wynosi ona \( 2^{m-n} \). Zatem
\( \vert \mathscr{A} \vert=\vert \mathscr{X} \vert\cdot 2^{m-n+1}. \)
Niech teraz rodzina \( \mathscr{X} \) nie będzie dwukolorowalna, czyli dla każdego zbioru \( C\subseteq X \) istnieje \( A\in\mathscr{X} \) taki, że \( A\subseteq C \) albo \( A\subseteq X- C \). Tak więc par w \( \mathscr{A} \) jest co najmniej tyle co podzbiorów \( C\subseteq X \), a więc
\( 2^m\leq\vert \mathscr{A} \vert=\vert \mathscr{X} \vert\cdot 2^{m-n+1}, \)
skąd natychmiast
\( \vert \mathscr{X} \vert\geq 2^{n-1}. \)
Twierdzenie 3.9 [P. Erd{o}s 1947]
\( {\sf R}\!( n,n )\geq n2^{n/2}( \frac{1}{e\sqrt{2}}-o( 1 ) ). \)
Dowód
Niech \( Y \) będzie zbiorem o \( m:={\sf R}\!( n,n ) \) elementach. Połóżmy
\( X=\mathscr{P}_{2}\!( Y ) \)
i dalej
\( \mathscr{X}=\lbrace \mathscr{P}_{2}\!( A ):\ A\in\mathscr{P}_{n}\!( Y ) \rbrace. \)
Wtedy \( \mathscr{X}\subseteq\mathscr{P}_{{n\choose2}}\!( X ) \). Ponieważ \( Y \) ma \( {\sf R}\!( n,n ) \) elementów, to rodzina \( \mathscr{X} \) nie jest dwukolorowalna, tak więc na mocy Twierdzenia 3.8 trzymujemy:
\( \vert \mathscr{X} \vert\geq 2^{{n\choose 2}-1} \)
Z kolei definicja rodziny \( \mathscr{X} \) daje \( \vert \mathscr{X} \vert={m\choose n} \), a więc
\( \frac{m^n}{n!} \geq\frac{m\cdot( m-1 )\cdot\ldots\cdot( m-n+1 )}{n\cdot( n-1 )\cdot\ldots\cdot 1} ={m\choose n} =\vert \mathscr{X} \vert \geq 2^{{n\choose 2}-1} \)
Otrzymujemy więc, że
\( m^n\geq n!\cdot2^{( n^2-n-2 )/2}, \)
co z kolei implikuje, że
\( m \geq\sqrt[n]{n!}\cdot2^{n/2}\cdot2^{-1/2}\cdot2^{-1/n} \geq\sqrt[n]{n!}\cdot2^{n/2}( \frac{1}{\sqrt{2}}-o( 1 ) ). \)
Oszacowanie Sterlinga na \( n! \) daje
\( \sqrt[n]{n!} =n( \frac{\sqrt[2n]{2n}\cdot\sqrt[2n]{\pi}}{e}+o( 1 ) ) =n( \frac{1}{e}+o( 1 ) ). \)
i w konsekwencji otrzymujemy:
\( {\sf R}\!( n,n )=m \geq\sqrt[n]{n!}\cdot2^{n/2}( \frac{1}{\sqrt{2}}-o( 1 ) ) \geq n\cdot2^{n/2}( \frac{1}{e\sqrt{2}}-o( 1 ) ). \)
Twierdzenie 3.3 ma jeszcze inne ciekawe uogólnienie, pozwalające na wyszukiwanie zadanych uprzednio podgrafów w grafie macierzystym.
Twierdzenie 3.10 [W. Deuber 1974]
Dla dowolnych dwóch grafów prostych \( \mathbf{H}_1 \) oraz \( \mathbf{H}_2 \) istnieje graf prosty \( \mathbf{G} \) taki, że jakkolwiek nie podzielimy zbioru krawędzi \( {\sf E}\!(\mathbf{G}) \) na zbiory \( E_1,E_2 \), to \( \mathbf{H}_1 \) będzie podgrafem indukowanym grafu \( ( {\sf V}\!(\mathbf{G}),E_1 ) \) lub \( \mathbf{H}_2 \) będzie podgrafem indukowanym grafu \( ( {\sf V}\!(\mathbf{G}),E_2 ) \).
to jeden z działów matematyki badający własności obiektów algebraicznych zwanych grupami. Wraz z zastosowaniami stanowi on obecnie ogromną, autonomiczną dziedzinę wiedzy. Historyczne korzenie teorii to: rozwiązywanie równań algebraicznych, teoria liczb oraz geometria. Euler, Gauss, Lagrange, Abel i Galois byli pionierami badań w tej dziedzinie. W szczególności, Galois jest uważany za pierwszego matematyka, 2który powiązał teorię grup z teorią ciał.
Grupa to uporządkowana czwórka \( {\mathbf G}=(G,*,',e) \), gdzie \( G \) jest dowolnym zbiorem niepustym, \( * \) działaniem dwuargumentowym, \( ' \) jest działaniem jednoargumentowym, a \( e\in G \), przy czym, dla dowolnych \( x,y,z\in G \), spełnione sa następujące warunki:
Rząd grupy skończonej \( {\mathbf G}=(G,*,e) \) to liczba \( \vert G \vert \) jej elementów. Gdy grupa \( {\mathbf G} \) nie jest skończona, to mówimy, że ma rząd nieskończony.
Uwaga
Czasem w grupie nie podaje się w sposób jawny elementu neutralnego lub jednoargumentowego działania zwracającego element odwrotny. Zobaczymy, że takie postępowanie jest uprawnione, bo zarówno element neutralny jak i element odwrotny do jakiegoś \( x \), jeśli istnieje to jest jedyny.
Przykład
\( \mathbf {Z}=(\mathbb{Z},+,0) \), czyli zbiór liczb całkowitych z dodawaniem i elementem neutralnym \( 0 \), jest grupą. Rzeczywiście:
Przykład
Dla dowolnej liczby naturalnej\( n\geq 1 \), zbiór reszt modulo \( n \) wraz z dodawaniem modulo \( n \), tzn. \( \mathbf {Z}_n=(\mathbb{Z}_n,+,0) \) jest grupą. Rzeczywiście:
Przykład
\( {\mathbf S}_n=(S_n,\circ) \) jest grupą, gdzie \( S_n \) to zbiór permutacji zbioru \( \mathbb{Z}_n={\{ {0,\ldots,n-1} \} } \), a \( \circ \) to składanie permutacji. Rzeczywiście:
Przykład
Gdy \( \mathbb{Z}_p^*=\mathbb{Z}_p-{\{ {0} \} }={\{ {1,\ldots,p-1} \} } \) oraz \( p \) jest liczba pierwszą, to \( {\mathbf {Z}}_p^*=(\mathbb{Z}_p^*,\cdot,1) \) jest grupą, gdzie działanie \( \cdot \) to mnożenie modulo \( p \). Rzeczywiście:
Liczba \( p \) byłaby więc rozkładzie \( ab=p_1\cdot\ldots\cdot p_k \), co jest niemożliwe wobec \( p_i\leq\max(a,b) < p \).
\( (ab \ {\sf mod} \ p )\cdot c \ {\sf mod} \ p =a\cdot(bc \{ {\sf mod} \ p ) \ {\sf mod} \ p . \)
Z pierwszości \( p \) mamy \( {\sf NWD}(a,p)=1 \) zatem istnieją \( x,y \) takie, że \( xa+yp=1 \), czyli \( xa \ {\sf mod}\ p =1 \). To oznacza, iż \( x \ {\sf mod} \ p \) jest elementem odwrotnym do \( a \) w \( {\mathbf {Z}_p^*} \).
Można też, używając Małego Twierdzenia Fermata sprawdzić, że elementem odwrotnym do \( a \) jest
Przykład
Rozważmy trójkąt równoboczny z poetykietowanymi wierzchołkami
oraz wybrane przekształcenia tego trójkąta pozostawiające go w tym samym miejscu płaszczyzny:
Wtedy \( ({\{ {i,p,l,x,y,z} \} },\circ, i) \) jest grupą, gdzie \( \circ \) jest składaniem przekształceń.
\( {\{ {i,p,l,x,y,z} \} } \).
\( \begin{array} {|c|cccccc|} \hline \circ & i & p & l & x & y & z \\ \hline i & i & p & l & x & y & z \\ p & p & l & i & y & z & x \\ l & l & i & p & z & x & y \\ x & x & z & y & i & l & p \\ y & y & x & z & p & i & l \\ z & z & y & x & l & p & i \\ \hline \end{array} \)
Zauważmy, że w każdym wierszu (i każdej kolumnie) występuje \( i \), skąd też można wywnioskować istnienie elementów odwrotnych.
Obserwacja 4.1 [prawo skracania]
Dla grupy \( (G,*,e) \) i \( x,y,z\in G \) mamy:
Dowód
Z uwagi na symetrię, pokażemy jedynie pierwszy punkt. Załóżmy zatem, że \( x*y=x*z \) i niech \( x' \) będzie elementem odwrotnym do \( x \). Wtedy \( y = 1*y =(x'*x)*y = x'*(x*y) = x'*(x*z) = (x'*x)*z = 1*z=z \).
Obserwacja 4.2
Jeśli \( (G,*,e) \) jest grupą i \( a,b\in G \), to równanie
\( a*x=b \)
ma dokładnie jedno rozwiązanie \( x \) w \( G \).
Dowód
Niech \( a' \) będzie elementem odwrotnym do \( a \) w \( (G,*) \). Wtedy \( x=a'*b \) jest rozwiązaniem równania, gdyż
\( a*(a'*b)=(a*a')*b=e*b=b. \)
Dla dowodu jednoznaczności załóżmy, że \( x_0 \) i \( x_1 \) są rozwiązaniami naszego równania. Wtedy mamy \( a*x_0=a*x_1 \) i z lewostronnego prawa skracania \( x_0=x_1 \).
Wniosek 4.3
Każda grupa ma dokładnie jeden element spełniający warunki elementu neutralnego oraz każdy jej element ma dokładnie jeden element odwrotny.
Dowód
Niech \( (G,*,e) \) będzie grupą i \( a\in G \). Element neutralny \( e \) jest jedynym rozwiązaniem równania \( e*x=e \). Element odwrotny do \( a \) jest jedynym rozwiązaniem \( a*x=e \).
W dalszych rozważaniach o abstrakcyjnych grupach porzucimy ornamentyczny symbol \( * \) i będziemy się posługiwać notacją multiplikatywną. Zatem dla dowolnego \( x,y\in G \), gdzie \( {\mathbf G} \) jest grupą
Pamietajmy, że symbol \( 1 \) w większości wypadków nie oznacza dobrze znanej liczby \( 1\in\mathbb{N} \). Podobnie nie możemy zakładać, iż działanie \( \cdot \) zachowuje prawa zwykłego mnożenia. W szczególności \( xy=yx \) zachodzi dalece nie w każdej grupie (np. nie zachodzi w grupie \( {\mathbf S}_n \) dla \( n>2 \)).
Grupa abelowa to \( {\mathbf G}=(G,\cdot \),1), w której działanie \( \cdot \) jest przemienne tzn. dla dowolnych \( x,y\in G \) mamy
\( xy=yx. \)
Nazwa grup abelowych pochodzi od nazwiska Nielsa Abela, norweskiego matematyka, w którego pracach implicite pojawia się to pojęcie.
Przykład
Grupy \( {\mathbf {Z}}_n \) i \( {\mathbf {Z}}_p^* \) są abelowe, gdyż tak dodawanie, jak i mnożenie modularne jest przemienne.
Grupa przekształceń trójkąta równobocznego \( ({\{ {i,p,l,x,y,z} \} },\circ,i) \) nie jest abelowa, gdyż np. \( xp\neq px \).
W naturalny sposób w notacji multiplikatywnej definiujemy rekurencyjnie:
Dodatnie i ujemne potęgi elementu \( x \) w grupie \( {\mathbf G}=(G,\cdot,1) \)
\( \begin{align*} x^0 & =1, \\ x^{n+1} & =x^n\cdot x, \\ x^{-n} & =(x^n)^{-1}. \end{align*} \)
Obserwacja 4.4
Dla dowolnej grupy \( {\mathbf G}=(G,\cdot,1) \), \( x\in G \) i \( m,n\in\mathbb{Z} \) zachodzi
\( 1^m=1,\qquad x^{m+n}=x^mx^n,\qquad x^{mn}=(x^m)^n. \)
Jeśli \( {\mathbf G} \) jest abelowa i \( x,y\in G \), to
\( (xy)^n = x^n y^n. \)
Jeśli grupa \( {\mathbf G}=(G,\cdot,1) \) ma rząd skończony, to oczywiście dla dowolnego \( x\in G \) w ciągu nieujemnych potęg: \( 1,x,x^2,x^3,\ldots \) elementy muszą zacząć się powtarzać. Załóżmy zatem, że \( m < n \) i \( x^m=x^n \). Mnożąc te równość przez \( x^{-m} \) otrzymujemy \( 1=x^{n-m} \). Udowodniliśmy zatem, iż w grupie o skończonym rzędzie każdy element w pewnej dodatniej potędze równy jest \( 1 \). Z Zasady Minimum dla każdego elementu istnieje więc najmniejsza taka dodatnia potęga.
Rząd elementu \( x\in G \) w grupie \( {\mathbf G}=(G,\cdot,1) \) o skończonym rzędzie to najmniejsza dodatnia liczba \( n \) taka, że \( x^n=1 \). Dla grup nieskończonych rząd elementu jest tak samo zdefiniowany o ile taka liczba istnieje. Jeśli nie to \( x \) ma rząd nieskończony.
Obserwacja 4.5
Dla elementu \( x \) rzędu \( m \) w grupie \( (G,\cdot,1) \) mamy \( x^n=1 \) wtedy i tylko wtedy, gdy \( m|n \).
Dowód
Jeśli \( m|n \) to \( n=q\cdot m \) dla pewnego \( q \), a zatem
\( x^n=x^{qm}=(x^{m})^q=1^q=1. \)
Na odwrót załóżmy, że \( x^n=1 \) dla pewnego \( n \). Niech \( n=qm+r \) gdzie \( 0\leq r < m \). Wtedy mamy
\( 1=x^n=x^{qm+r}=(x^m)^qx^r=1^qx^r=x^r, \)
co wraz z minimalnością \( m \) jako rzędu elementu \( x \) daje \( r=0 \), czyli \( m|n \).
Homomorfizm grup \( {\mathbf G}_0=(G_0,\cdot,1_{G_0}) \), \( {\mathbf G}_1=(G_1,\cdot,1_{G_1}) \) to dowolna funkcja \( f:G_0\to G_1 \) taka, że dla dowolnych \( x,y\in G_0 \) zachodzi
\( f(xy)=f(x)f(y). \)
Obserwacja 4.6
Dla dowolnego homomorfizmu \( f:G_0\to G_1 \) grup \( {\mathbf G_0} \) i \( {\mathbf G_1} \) mamy:
Dowód
Oczywiście \( f(1_{G_0})=f(1_{G_0}\cdot 1_{G_0})=f(1_{G_0})f(1_{G_0}) \). Prawo skracania w grupie \( {\mathbf G}_1 \) daje więc \( 1_{G_1}=f(1_{G_0}) \). Z kolei, gdy \( x\in G_0 \), to \( f(x)\cdot f(x^{-1})=f(xx^{-1})=f(1_{G_0})=1_{G_1} \), czyli \( f(x^{-1}) \) jest elementem odwrotnym do \( f(x) \) w \( {\mathbf G}_1 \).
Izomorfizm grup to homomorfizm, który jest bijekcją.
Grupy izomorficzne to grupy, miedzy którymi istnieje izomorfizm. Izomorficzność grup \( {\mathbf G_0} \) i \( {\mathbf G_1} \) zapisujemy \( {\mathbf G_0}\approx{\mathbf G_1} \).
Podgrupa grupy \( {\mathbf G}=(G,\cdot,1_G) \) to taka grupa \( {\mathbf H}=(H,\cdot,1_G) \), że \( H\subseteq G \) oraz mnożenie w grupie \( {\mathbf H} \) jest restrykcją mnożenia w \( {\mathbf G} \).
Obserwacja 4.7
Dla \( \emptyset\neq H\subseteq G \), gdzie \( {\mathbf G}=(G,\cdot,1) \) jest grupą, jeśli
to \( {\mathbf H}=(H,\cdot,1) \) jest podgrupą \( {\mathbf G} \). Ponadto jeśli \( {\mathbf G} \) ma rząd skończony, to już pierwszy punkt implikuje, iż \( {\mathbf H} \) jest podgrupą grupy \( {\mathbf G} \).
Dowód
Pierwszy punkt gwarantuje, że działanie \( \cdot \) nie wyprowadza poza zbiór \( H \). Łączność \( \cdot \) w \( H \) wynika bezpośrednio z łączności \( \cdot \) w \( G \). Drugi punkt świadczy, iż każdy element w \( H \) ma element odwrotny także w \( H \). Dla dowodu, że \( 1\in H \) skorzystamy z niepustości \( H \) i wybierzmy \( h\in H \). Wtedy, z drugiego punktu, \( h^{-1}\in H \), więc \( 1=hh^{-1}\in H \) na mocy punktu pierwszego.
Załóżmy teraz, że grupa \( {\mathbf G} \) ma rząd skończony oraz podzbiór \( H \subseteq G \) jest zamknięty na mnożenie. Wtedy oczywiście wszystkie potęgi o nieujemnych wykładnikach \( h,h^2,h^3,\ldots \) wpadają do \( H \). Ponieważ \( G \) ma rząd skończony, to rząd dowolnego elementu też jest skończony, czyli istnieje \( m \) takie, że \( h^m=1 \). Zatem \( 1\in H \) i \( h^{m-1}h=1=hh^{m-1} \), czyli \( h^{m-1}\in H \) jest elementem odwrotnym do \( h \).
Z Obserwacji 4.7 dostajemy natychmiast:
Wniosek 4.8
Przecięcie dowolnej rodziny podgrup grupy \( {\mathbf G} \) jest podgrupą \( {\mathbf G} \).
Podgrupa generowana przez podzbiór \( X \subseteq G \) grupy \( {\mathbf G} \), to przecięcie wszystkich podgrup \( {\mathbf G} \) zawierających zbiór \( X \). Podgrupę taką oznaczamy przez \( {\mathbf G}(X) \).
Zbiór generatorów grupy \( {\mathbf G}=(G,\cdot,1) \) to jakikolwiek zbiór \( X \subseteq G \) spełniający \( G(X)=G \).
Obserwacja 4.9
Dla dowolnej grupy \( {\mathbf G}=(G,\cdot,1) \) i \( \emptyset\neq X\subseteq G \)
\( G(X)={\{ {x_0\cdot\ldots\cdot x_{n-1} : n\in\mathbb{N} \mbox{ i } (x_i\in X \mbox{ lub }x_i^{-1}\in X)} \} }. \)
Dowód
Oczywiście wszystkie iloczyny postaci \( x_0\cdot\ldots\cdot x_{n-1} \) leżą w każdej podgrupie zawierającej \( X \), więc i w \( G(X) \). Nadto zbiór \( Z \) wszystkich takich iloczynów jest zamknięty na iloczyn i odwracanie, bo \( (x_0\cdot\ldots\cdot x_{n-1})^{-1}=x_{n-1}^{-1}\cdot x_{n-2}^{-1}\cdot\ldots\cdot x_0^{-1} \). A zatem Obserwacja 4.7 gwarantuje, że \( (Z, \cdot, 1) \) jest podgrupą. Musi zatem być czynnikiem przecięcia wyznaczającego \( G(X) \), czyli \( G(X)\subseteq Z \).
Grupa cykliczna to grupa generowana zbiorem jednoelementowym.
Jeśli \( {\mathbf G} = {\mathbf G}({\{ {x} \} }) \), to \( G={\{ {x^n : n\in \mathbb{Z}} \} } \). Gdy ponadto \( {\mathbf G} \) jest skończona, to jej rząd pokrywa się z rzędem elementu generującego \( x \), czyli \( G={\{ {1,x,x^2,\ldots, x^{\vert G \vert-1}} \} } \).
Przykład
Grupa addytywna liczb całkowitych \( {\mathbf {Z}}=(\mathbb{Z},+,0) \) jest cykliczna. Rzeczywiście \( {\{ {1} \} } \) generuje te grupę:
\( \begin{array} {lrrrrrrr} \mathbb{Z}=\{\ldots, & -3, & -2, & -1, & 0, & 1, & 2, & 3,\ldots\} \\ \mathbb{Z}=\{\ldots, & -1-1-1, & -1-1, & -1, & 1-1, & 1, & 1+1, & 1+1+1,\ldots\} \end{array} \)
Czy grupa ta ma jeszcze jakiś inny jednoelemtowy zbiór generujacy?
Przykład
Dla \( n>0 \) grupa \( {\mathbf {Z}}_n=(\mathbb{Z}_n,+,0) \) jest skończoną grupą cykliczną generowaną przez \( {\{ {1} \} } \). Rzeczywiście:
\( \mathbb{Z}_n=\left\{ {1,1+1,\ldots,\underbrace{1+1+\ldots+1}_{n\ razy}} \right \}. \)
Obserwacja 4.10
Dowolne dwie grupy cykliczne tego samego rzędu są izomorficzne.
Dowód
Niech \( g_i \) będzie generatorem grupy cyklicznej \( {\mathbf G_i} \), dla \( i=0,1 \). Łatwo sprawdzić, że równość rzędów tych grup daje, iż \( g_0^k =g_0^l \) wtedy i tylko wtedy, gdy \( g_1^k =g_1^l \). A zatem \( f:G_0\ni g_0^k \mapsto g_1^k \in G_1 \) ustala izomorfizm grup \( {\mathbf G_0} \) i \( {\mathbf G_1} \).
Wniosek 4.11
Dowolna skończona grupa cykliczna rzędu \( n \) jest izomorficzna z \( \mathbb{Z}_n \). Dowolna nieskończona grupa cykliczna jest izomorficzna z \( \mathbb{Z} \).
Przykład
Dla \( n\geq3 \) rozważymy pewne grupy przekształceń \( n \)-kątów foremnych jako podgrupy grupy \( S_n \). Poetykietujmy wierzchołki \( n \)-kąta foremnego liczbami \( 0,\ldots,n-1 \). Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku, odpowiada cyklicznej permutacji \( \pi=(0,1,\ldots,n-1) \). Zastanówmy się teraz jakie elementy składają się na \( {\mathbf S}_n(\pi) \) i jaka jest ich interpretacja geometryczna.
Rząd cyklu \( n \)-elementowego jest oczywiście równy \( n \). Kolejne złożenia \( \pi,\pi^2,\pi^3,\ldots,\pi^n \) odpowiadają kolejnym obrotom \( \pi^k \) w prawo naszego wielokąta o \( \frac{360^o}{k} \), aż \( \pi^n \) przekręca go do pozycji wyjściowej (czyli jest identycznością). Zatem \( {\mathbf S}_n(\pi) \) jest grupą cykliczną rzędu \( n \), czyli z Wniosku 4.11 mamy \( {\mathbf S}_n(\pi)\approx \mathbb{Z}_n \).
Zwiększmy trochę zbiór generatorów i do obrotu w prawo dołóżmy symetrię względem jednej z \( n \) osi symetrii naszego \( n \)-kąta foremnego. W przypadku gdy \( n \) jest parzyste osie symetrii przechodzą przez środki przeciwległych boków lub naprzeciwległe wierzchołki, jeśli zaś \( n \) jest nieparzyste to osie symetrii przechodzą przez wierzchołek i środek przeciwległego do niego boku.
Permutacja odpowiadająca symetrii osiowej posiada poza cyklami wielkości \( 2 \):
Na przykład, gdy \( n \) jest parzyste oraz :
\( \sigma=(0,n-1)(1,n-2)(2,n-3)\ldots(n/2-1,n/2+1), \)
to \( \sigma \) rozkłada się na cykle
\( \sigma=(0)(1,n-1)(2,n-2)\ldots(n/2-1,n/2+1)( (n+1)/2 ), \)
a dla nieparzystego \( n \):
\( \sigma=(0)(1,n-1)(2,n-2)(3,n-3)\ldots((n-1)/2,(n+1)/2). \)
Jakie elementy składają się na \( {\mathbf S}_n({\{ {\pi,\sigma} \} }) \)? Jaka jest ich interpretacja geometryczna?
Zbierzmy kilka prostych faktów:
Pokażemy tę własność jedynie dla \( n \) nieparzystych (dowód dla \( n \) parzystych znacząco się nie różni):
\( \begin{align*} \pi\sigma\pi(0) & =\pi\sigma(n-1)=\pi(1)=0=\sigma(0), \\ \pi\sigma\pi(1) & =\pi\sigma(0)=\pi(0)=n-1=\sigma(1), \\ \pi\sigma\pi(i) & =\pi\sigma(i-1)=\pi(n-i+1)=n-i=\sigma(i), \end{align*} \)
dla \( i\in{\{ {2,\ldots,n-1} \} } \).
Z Obserwacji 4.9 i naszych spostrzeżeń mamy:
\( \begin{align*} S_n({\{ {\pi,\sigma} \} }) & ={\{ {x_0\cdot\ldots\cdot x_{m-1}: m>0, x_i\in{\{ {\pi,\pi^{-1},\sigma,\sigma^{-1}} \} }} \} } \\ & ={\{ {\pi^k, \pi^k\sigma : 0 < k\leq n} \} } \end{align*} \)
Zatem podgrupa generowana przez \( {\{ {\pi,\sigma} \} } \) ma co najwyżej \( 2n \) elementów. Jako ćwiczenie zostawiamy dowód, że w istocie wymienione elementy są parami różne. Okazuje się, że
\( \begin{array} {ll} \pi,\pi^2,\pi^3,\ldots,\pi^n & \textrm{- to wszystkie obroty wraz z identycznością}, \\ \pi\sigma,\pi^2\sigma,\pi^3\sigma,\ldots,\pi^n\sigma & \textrm{- to symetrie wobec każdej z n osi symetrii n -kąta foremnego}. \end{array} \)
Grupa dihedralna \( {\mathbf D}_{n} \) to podgrupa grupy \( {\mathbf S_n} \) (dla \( n\geq3 \)) generowana przez \( {\{ {\pi,\sigma} \} } \).
Produkt grup \( {\mathbf G_0}=(G_0,\cdot,1_{G_0}) \) i \( {\mathbf G_1}=(G_1,\cdot,1_{G_1}) \) to grupa \( {\mathbf G_0}\times{\mathbf G_1}=(G_0\times G_1,\cdot,(1_{G_0},1_{G_1})) \), w której działanie \( \cdot \) zdefiniowane jest przez
\( (x,y)\cdot(z,w)=(x\cdot z,y\cdot w). \)
Weryfikację, że tak określone działanie po współrzędnych spełnia wszystkie warunki wymagane od grupy zostawiamy jako ćwiczenie.
Przykład
Rozważmy \( \mathbb{Z}_2\times\mathbb{Z}_3 \).
\( \mathbb{Z}_2\times \mathbb{Z}_3={\{ {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)} \} }. \)
Zauważmy, że \( f:\mathbb{Z}_6 \to \mathbb{Z}_2\times\mathbb{Z}_3 \) zadana przez
\( f(a) = (a \ {\sf mod} \ 2 , \ a \ {\sf mod} \ 3 ) \)
definiuje izomorfizm grup \( \mathbb{Z}_6 \) i \( \mathbb{Z}_2\times\mathbb{Z}_3 \).
Czy zawsze \( \mathbb{Z}_{mn}\approx\mathbb{Z}_m\times\mathbb{Z}_n \)? Zbadajmy jeszcze jeden przykład: \( \mathbb{Z}_2\times\mathbb{Z}_4 \) i \( \mathbb{Z}_8 \). Rzędy elementów w produkcie \( \mathbb{Z}_2\times\mathbb{Z}_4 \) przedstawia tabela:
\( \begin{array} {|c||c|c|c|c|c|c|c|c|} \hline \mathbb{Z}_2\times\mathbb{Z}_4 & (0,0) & (0,1) & (0,2) & (0,3) & (1,0) & (1,1) & (1,2) & (1,3) \\ \hline \textrm{rząd} & 1 & 4 & 2 & 4 & 2 & 4 & 2 & 4 \\ \hline \end{array} \)
A zatem grupa \( \mathbb{Z}_2\times\mathbb{Z}_4 \) nie ma elementu rzędu \( 8 \), nie może więc być izomorficzna z cykliczna grupą \( \mathbb{Z}_8 \).
Obserwacja 4.12
Jeśli \( m\perp n \), to \( \mathbb{Z}_m\times\mathbb{Z}_n \approx \mathbb{Z}_{mn} \).
Dowód
Wystarczy oczywiście pokazać, że rząd elementu \( (1,1)\in\mathbb{Z}_m\times\mathbb{Z}_n \) wynosi \( mn \), wtedy bowiem grupa \( \mathbb{Z}_m\times\mathbb{Z}_n \) będzie cykliczna i, jako \( mn \)-elementowa, musi być izomorficzna z \( \mathbb{Z}_{mn} \).
Niech więc \( r \) będzie rzędem \( (1,1) \) w grupie \( \mathbb{Z}_m\times\mathbb{Z}_n \). Licząc kolejno na obu osiach produktu dostajemy
\( \begin{align*} \underbrace{1+\ldots+1}_{r\ razy} \ {\sf mod} \ m & =r \ {\sf mod} \ m =0,\textrm{ czyli m|r,} \\ \underbrace{1+\ldots+1}_{r\ razy} \ {\sf mod} \ n & =r \ {\sf mod} \ n =0,\textrm{ czyli n|r}. \end{align*} \)
Zatem \( r \) jest najmniejszą wspólną wielokrotnością \( m \) i \( n \). Ponieważ \( m\perp n \), to
\( r={\sf NWW}(m,n)=\frac{mn}{\sf NWD}(m,n)=\frac{mn}{1}=mn.\)
Zajmiemy się teraz możliwymi rzędami podgrup grupy skończonej. Z rozważań tej części wykładu dowiemy się, że jeśli \( {\mathbf H} \) jest podgrupą skończonej grupy \( {\mathbf G} \), to rząd \( {\mathbf H} \) dzieli rząd \( {\mathbf G} \). Zwracamy jednak uwagę, iż to nie oznacza, że grupa \( {\mathbf G} \) ma podgrupy o rzędzie będącym jakimkolwiek dzielnikiem rzędu grupy \( {\mathbf G} \).
Przykład
Niech \( {\mathbf A}_4 \) będzie podgrupą grupy \( {\mathbf S}_4 \) składającą się z tych permutacji, które są złożeniami parzystej liczby transpozycji. Wtedy \( \vert A_4\vert=12 \), ale grupa \( {\mathbf A}_4 \) nie ma podgrup rzędu \( 4 \).
Lewa warstwa \( gH \) podgrupy \( {\mathbf H} \) grupy \( {\mathbf G} \) względem elementu \( g\in G \) to zbiór
\( gH={\{ {gh : h\in H} \} }. \)
Prawa warstwa \( Hg \) podgrupy \( {\mathbf H} \) grupy \( {\mathbf G} \) względem elementu \( g\in G \) to zbiór
\( Hg={\{ {hg : h\in H} \} }. \)
Skoncentrujemy się teraz na lewych warstwach. Oczywiście wszystkie rozumowania można powtórzyć dla warstw prawych
Przykład
Niech \( {\mathbf D}_4=({\{ {\pi,\ldots,\pi^4,\pi\sigma,\ldots,\pi^4\sigma} \} },\circ) \) będzie grupa dihedralną symetrii kwadratu. Posiada ona podgrupę cykliczną \( {\mathbf C}_4=({\{ {\pi,\pi^2,\pi^3,\pi^4} \} },\circ) \). Niech \( \sigma \) będzie symetrią osiową. Zauważmy, że elementy lewej warstwy
\( \sigma C_4={\{ {\sigma\pi,\sigma\pi^2,\sigma\pi^3,\sigma\pi^4} \} }. \)
wszystkie symetrie osiowe kwadratu. Jako ćwiczenie pozostawiamy wyznaczenie warstw \( \pi C_4 \), \( \pi^2 C_4 \) oraz \( \sigma\pi^2 C_4 \).
Zauważmy, że warstwa \( eH \) elementu neutralnego \( e \), to podgrupa \( H \). Nastepna obserwacja orzeka, że wszystkie warstwy lewo- i prawo-stronne są równoliczne.
Obserwacja 4.13
Jeśli \( {\mathbf H} \) jest skończoną podgrupą grupy \( {\mathbf G} \) i \( g\in G \), to \( \vert=\vert = \vert \).
Dowód
Niech \( H={\{ {h_0,\ldots,h_{m-1}} \} } \) i załóżmy, że \( gh_i=gh_j \). Wtedy z prawa skracania mamy \( h_i=h_j \). Zatem elementy \( gh_0,gh_1,\cdots,gh_{m-1} \) są parami różne i zbiór
\( gH={\{ {gh_0,gh_1,\cdots,gh_{m-1}} \} }, \)
ma dokładnie \( m \) elementów.
Obserwacja 4.14
Dla dowolnej podgrupy \( {\mathbf H} \) grupy \( {\mathbf G} \) i \( g_0,g_1\in G \) lewe warstwy \( g_0 H \), \( g_1H \) są albo identyczne albo rozłączne.
Dowód
Pokażemy, że jeśli \( g_0 H \) i \( g_1 H \) mają jakiś wspólny element to są one identyczne. Załóżmy zatem, że \( x\in g_0 H \cap g_1 H \), czyli \( g_0 h_0 =x= g_1 h_1 \) dla pewnych \( h_0,h_1\in H \). Wtedy \( g_0=g_1 h_1 h_0^{-1} \in g_1H \). Dla dowodu inkluzji \( g_0 H \subseteq g_1 H \), niech \( y\in g_0 H \), czyli \( y=g_0h \) dla pewnego \( h\in H \). Wtedy
\( y=g_0 h=g_1 h_1 h_0^{-1} h, \)
co wobec \( h_1,h_0^{-1},h\in H \) daje \( y\in g_1H \).
Twierdzenie 4.15[Lagrange'a]
Dla dowolnej podgrupy \( {\mathbf H} \) skończonej grupy \( {\mathbf G} \), rząd \( {\mathbf H} \) dzieli rząd \( {\mathbf G} \).
Dowód
Niech \( {\mathbf H}=({\{ {h_0,\ldots,h_{m-1}} \} },\cdot,1) \) oraz \( {\mathbf G}=({\{ {g_0,\ldots,g_{n-1}} \} },\cdot,1) \). Ponieważ:
to lewe warstwy \( g_0H,g_1H,\ldots,g_{n-1}H \) tworzą podział zbioru \( G={\{ {g_0,g_1\ldots,g_{n-1}} \} } \) na równoliczne bloki wielkości \( m \), skąd natychmiast \( m|n \).
Wniosek 4.16
Niech \( {\mathbf G}=(G,\cdot,1) \) będzie grupą rzędu \( n \). Wtedy dla \( g \in G \) mamy:
Dowód
Niech \( r \) będzie rzędem elementu \( g\in G \). Wtedy \( r \) jest rzędem podgrupy cyklicznej \( {\mathbf G}(g) = ({\{ {g,g^2,\ldots,g^r} \} },\cdot,1) \). Z Twierdzenia Lagrange'a \( r \), czyli rząd tej podgrupy cyklicznej, dzieli \( n \). Skoro teraz \( n=kr \) to oczywiście \( x^n= x^{kr} = (x^r)^k = 1^k =1 \)
Wniosek 4.17
Każda grupa \( {\mathbf G} \) której rząd jest liczbą pierwszą \( p \) jest cykliczna i izomorficzna z \( \mathbb{Z}_p \).
Dowód
Ponieważ \( p>1 \), to w \( G \) jest jakiś element \( g\neq1 \). Wtedy rząd \( g \) jest większy od \( 1 \) i dzieli \( p \), więc musi wynosić \( p \). To oznacza zaś, iż \( g \) generuje grupę \( {\mathbf G} \), czyli \( {\mathbf G} \) jest cykliczna. Reszta wynika już z Wniosku 4.11.
Obserwacja 4.18
Dla dowolnej grupy \( {\mathbf G}=(G,\cdot,1) \) rzędu \( n\geq 2 \) następujące warunki są równoważne:
1. \( {\mathbf G} \) jest grupa cykliczną,
2. dla każdego \( d|n \), grupa \( {\mathbf G} \) ma dokładnie \( d \) elementów \( x\in G \) takich, że \( x^d=1 \),
3. dla każdego \( d|n \), grupa \( {\mathbf G} \) ma dokładnie \( \varphi(d) \) elementów rzędu \( d \).
Dowód
Dla dowodu implikacji (1 \( \Rightarrow \) 2) załóżmy że grupa \( {\mathbf G} \) jest cykliczna i generowana przez \( g \). Niech \( d \) będzie dzielnikiem \( n \), czyli \( n=dq \) dla pewnego \( q \). Elementy
\( 1,g^q,g^{2q},\ldots,g^{(d-1)q} \)
są parami różne (bo \( g \) ma rząd \( n=dq \)) oraz wszystkie spełniają równanie \( x^d=1 \), gdyż
\( (g^{iq})^d=(g^{dq})^i=1^i=1. \)
Zatem elementów \( x\in G \) spełniających \( x^d=1 \) jest co najmniej \( d \). Załóżmy teraz, że pewien \( y\in G \) spełnia \( y^d=1 \). Ponieważ \( g \) generuje \( {\mathbf G} \), mamy \( y=g^k \) dla pewnego \( k \), skąd \( g^{kd}=y^d=1 \). Z Obserwacji 4.5 mamy \( n|kd \), czyli \( kd=fn=fdq \) i \( k=fq \) dla pewnego \( f \). Zatem \( y=g^{k}=g^{fq} \) znajduje się na naszej liście rozwiązań równania \( x^d=1 \). To dowodzi, że elementów \( x\in G \) spełniających \( x^d=1 \) jest dokładnie \( d \).
Dla dowodu implikacji (2 \( \Rightarrow \) 3) przypomnijmy, za Obserwacją 4.5, że element \( x \) rzędu \( r \) spełnia \( x^d=1 \) wtedy i tylko wtedy, gdy \( r|d \). A zatem założenie 2 daje
\( \displaystyle d=\sum_{r|d}f(r), \)
gdzie \( f(r) \) to liczba elementów rzędu \( r \) spełniających \( x^d \)=1. Wzór inwersyjny Mobiusa daje teraz
\( \displaystyle f(d)=\sum_{r|d}\mu(r)\frac{d}{r}. \)
Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa, tzn. \( \displaystyle \varphi(d)=\sum_{r|d}\mu(r)\frac{d}{f} \), mamy \( f(d)=\varphi(d) \).
Wreszcie, dla dowodu ostatniej implikacji (3 \( \Rightarrow \) 1) zauważmy najpierw, że zawsze \( \varphi(n)\geq 1 \). To oczywiście daje, że istnieje co najmniej jeden element rzędu \( n \) w \( {\mathbf G} \). Element ten generuje więc cały zbiór \( G \), stąd \( {\mathbf G} \) jest cykliczna.
Przykład
Zbadajmy rzędy elementów grupy cyklicznej \( \mathbb{Z}_{12} \).
\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline 1 & 12 & 6 & 4 & 3 & 12 & 2 & 12 & 3 & 4 & 6 & 12 \\ \hline \end{array} \)
\( \begin{array} {|c|c|c|c|c|c|c|} \hline \textrm{dzielnik d liczby {12}} & 1 & 2 & 3 & 4 & 6 & 12 \\ \hline \textrm{liczba elementów rzędu {d}} & 1 & 1 & 2 & 2 & 2 & 4 \\ \hline \end{array} \)
Kolorowanie zbioru \( X \) to funkcja
\( \omega:X\longrightarrow K, \)
gdzie \( K \) jest zbiorem kolorów.
Przykład
Rozważmy kolorowania naszyjnika złożonego z pięciu identycznych koralików \( k_0,k_1,k_2,k_3,k_4 \). Koraliki te mają takie same kształty i nie można ich rozróżnić. Możemy zatem zauważyć, że z jednego kolorowania \( \omega_{0} \) da się utworzyć inne kolorowanie, nieodróżnialne od pierwszego, np. przez cykliczną zmianę numeracji koralików: \( \omega_{1}\!( k_i )=\omega_{0}\!( k_{( i-1\ mod\ 5 )} ) \) jest nieodróżnialne od kolorowania \( \omega_{0}\!( k_i ) \). Przekształcenie indeksów \( i-1\ mod\ 5 \) jest równoważne z obrotem o \( 72^{\circ} \).
W ten sposób dostajemy \( 5 \) kolorowań naszego naszyjnika. Ale, naszyjnik można też odwracać w rękach, lub - co na jedno wychodzi - spojrzeć na niego z drugiej strony. Mamy więc dodatkowe \( 5 \) kolorowań naszego naszyjnika.
Zauważmy, ze w istocie każde \( 10 \) z kolorowań możemy otrzymać z innego poprzez przekształcenie naszyjnika (pięciokąta) przez jakąś symetrię. Zbiór zmian ułożeń naszyjnika (permutacje jego koralików) wraz ze składaniem tych zmian (permutacji) tworzy więc grupę (w tym przypadku znaną nam już grupę dihedralną \( {\mathbf D}_5 \) symetrii pięciokąta. W wykładzie tym poznamy metody zliczania tych kolorowań, które są odróżnialne.
G-zbiór to para \( ( {\mathbf G},X ) \), gdzie
Czasem, dla G-zbioru \( ( {\mathbf G},X ) \) mówimy, ze grupa \( {\mathbf G} \) działa na zbiorze \( X \).
Przykład
Rozważmy kwadrat o wierzchołkach \( v_0, v_1, v_2, v_3 \) oraz \( 4 \) permutacje jego wierzchołków powstałe przez: odbicia względem przekątnych i obrót o \( 180^\circ \), tak jak zostało to pokazane na rysunku.
Każde przedstawione przekształcenie geometryczne wyznacza jednoznacznie permutację zbioru indeksów wierzchołków kwadratu \( X_□=\lbrace 0,1,2,3 \rbrace \). Tak więc zbiór permutacji odpowiadających przekształceniom to \( G_□=\lbrace id,g_1,g_2,g_3 \rbrace \). Przekształcenia \( g_i \) można składać. Na przykład \( g_1\circ g_2 \) tworzy obrót o \( 180^{\circ} \) stopni, a więc \( g_3 \). Para \( ( G_□, \circ ) \) tworzy grupę, więc \( ( G_□, X_□ ) \) jest przykładem G-zbioru, który jest opisany przez poniższe tabelki:
\( \begin{array} {|c||c|c|c|c|} \hline j & 1 & 2 & 3 & 4 \\ \hline\hline id(j) & 0 & 1 & 2 & 3 \\ \hline g_1(j) & 0 & 2 & 1 & 3 \\ \hline g_2(j) & 3 & 1 & 2 & 0 \\ \hline g_3(j) & 3 & 2 & 1 & 0 \\ \hline \end{array} \quad\quad\quad\quad\quad \begin{array} {|c||c|c|c|c|} \hline g_i\circ g_j & id & g_1 & g_2 & g_3 \\ \hline\hline id & id & g_1 & g_2 & g_3 \\ \hline g_1 & g_1 & id & g_3 & g_2 \\ \hline g_2 & g_2 & g_3 & id & g_1 \\ \hline g_3 & g_3 & g_2 & g_1 & id \\ \hline \end{array} \)
Innymi słowy, grupa permutacji \( {\mathbf G}_□ \) działa na zbiorze \( X_□ \).
Orbita \( Gx \) elementu \( x \in X \) w G-zbiorze \( ( G,X ) \) to zbiór tych elementów zbioru \( X \), które są postaci \( g\!( x ) \) dla pewnego \( g\in G \), tzn.
\( Gx=\lbrace g\!( x )\in X: g\in G \rbrace. \)
Stabilizator \( G_x \) elementu \( x\in X \) w G-zbiorze \( ( G,X ) \) to zbiór tych permutacji z \( G \), które nie ruszają \( x \) z miejsca, tzn.
\( G_x=\lbrace g\in G:\ g\!( x )=x \rbrace. \)
Ponadto zbiór permutacji przeprowadzających \( x\in X \) w \( y\in X \) oznaczamy przez
\( G( x \to y )=\lbrace g\in G:\ g\!( x )=y \rbrace \)
Przykład
Dla grupy \( G_□ \) permutacji kwadratu z rysunku, orbita oraz stabilizator elementu \( 0 \) mają postać
\( G_□0=\lbrace 0,3 \rbrace \quad\quad\quad\quad G_{□, 0}=\lbrace id,g_1 \rbrace. \)
Mnożąc liczności obu tych zbiorów otrzymujemy liczbę elementów grupy \( G_□ \), czyli innymi słowy \( \vert G_□ 0 \vert\cdot\vert G_{□, 0} \vert=\vert G_□ \vert. \)
Przypadek? Nie sądzę.
Twierdzenie 5.2
Dla G-zbioru \( ( G,X ) \) oraz \( x \in X \) zachodzi
\( \vert Gx \vert\cdot\vert G_x \vert=\vert G \vert. \)
Dowód
Pokażemy, że istnieje wzajemnie jednoznaczna odpowiedniość między elementami orbity \( Gx \) a warstwami \( G \) względem stabilizatora \( G_x \). Teza twierdzenia wyniknie wtedy natychmiast z twierdzenia Lagrange'a.
Mamy \( g_1(x) = g_2(x) \Leftrightarrow g_1^{-1}g_2(x) = x \Leftrightarrow g_1^{-1}g_2(x)\in G_x \Leftrightarrow g_2\in g_1G_x.\)
Zbiór punktów stałych permutacji \( g\in G \) to
\( {\sf Fix}( g )=\lbrace x\in X:\ g\!( x )=x \rbrace. \)
Twierdzenie 5.4
Dla G-zbioru \( ( G,X ) \) oraz funkcji \( f \) stałej na każdej orbicie \( Gx \) zachodzi
\( \displaystyle \sum_{x\in D}f\!( x )=\frac{1}{\vert G \vert}\sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ), \)
gdzie \( D\subseteq X \) jest zbiorem reprezentantów orbit, tzn. \( \vert D \cap Gx \vert=1 \) dla dowolnego \( x\in X \).
Dowód
Policzymy, na dwa różne sposoby, sumę
\( \displaystyle \sum_{( g,x )\in B}f\!( x ) \)
gdzie \( B=\lbrace ( g,x ):g\!( x )=x \rbrace \). Zliczając najpierw po \(g\in G\), a potem po \(x\in {\sf Fix}( g )\), dostajemy sumę
\[\sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ), \]
natomiast zliczając najpierw po \(x\in X\), a potem po \(g\in G_x\), dostajemy sumę
\[\sum_{x\in X}\vert G_x \vert f\!( x ) = \vert G \vert\sum_{x\in X}\frac{f\!( x )}{\vert Gx \vert}.\]
Każdy element orbity \( Gx\) wnosi do sumy taką samą wartość \(\frac{f\!( x )}{\vert Gx \vert}\) (bo \(f\) jest stała na każdej orbicie), zatem cała orbita \( Gx\) wnosi \( f(x)\), czyli ostatecznie \( \sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ) = \vert G\vert \sum_{x\in D}f\!( x )\).
Wniosek 5.5
Liczba orbit w G-zbiorze \( ( G,X ) \) wynosi
\( \displaystyle \frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( g ) \vert. \)
Permutacje na zbiorze kolorowań. Niech \( ( G,X ) \) będzie G-zbiorem, a \( A \) zbiorem kolorowań zbioru \( X \). Każda permutacja \( g\in G \) wyznacza permutację \( \widehat{g}:A\longrightarrow A \) kolorowań ze zbioru \( A \) poprzez
\( ( \widehat{g}\!( \omega ) )\!( x ) =\omega\!( g\!( x ) )\quad\textrm{dla dowolnych}\ \omega\in A\ \textrm{i}\ x\in X. \)
Obserwacja 5.6
Niech \( ( G,X ) \) będzie G-zbiorem, a \( A \) zbiorem kolorowań zbioru \( X \). Dla \( \widehat{G} = \lbrace \widehat{g}: g \in G \rbrace \) zachodzi:
Izomorficzne kolorowania. Kolorowania \( \omega_{0} \) i \( \omega_{1} \) zbioru \( X \) są izomorficzne względem działania grupy \( G \) na zbiorze \( X \), gdy istnieje permutacja \( g\in G \) taka, że \( \widehat{g}\!( \omega_{0} ) = \omega_{1} \), czyli
\( \displaystyle \omega_{0}\!( g\!( x ) )=\omega_{1}\!( x )\quad\textrm{dla dowolnego}\ x\in X. \)
Przykład
Kolorowania z rysunku są izomorficzne względem działania grupy \( {\mathbf D}_5 \) wszystkich zmian ustawień \( 5 \)-elementowego naszyjnika.
Indeks permutacji \( g:X\longrightarrow X \) to funkcja \( n \) zmiennych
\( \zeta_{g}( x_1,\ldots,x_n ) =x_1^{\alpha_1}\cdot x_2^{\alpha_2}\cdot\ldots\cdot x_n^{\alpha_n}, \)
gdzie
dla \( i=1,2,\ldots,n \).
Indeks grupy \( G \) to funkcja \( n \) zmiennych
\( \displaystyle \zeta_{G}( x_1,\ldots,x_n )=\frac{1}{\vert G \vert}\sum_{g\in G}\zeta_{g}( x_1,\ldots,x_n ). \)
Przykład
Niech \( ( G_t,\circ ) \) będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w \( 3 \)-wymiarowej przestrzeni.
Obroty czworościanu mają więc następujące indeksy \( \zeta_{g}( x_1,x_2,\ldots,x_8 ) \), w zależności od rozkładu na cykle:
W sumie są \( 3 \) takie obroty. Permutacją o indeksie \( x_2^2 \) jest na przykład \( ( 03 )\!( 12 ) \) i odpowiada ona przekształceniu przedstawionym na rysunku.
Indeks całej grupy obrotów czworościanu to zatem:
\( \zeta_{G_t}( x_1,x_2,x_3,x_4 )=\frac{1}{12}( x_1^4+8x_1x_3+3x_2^2 ). \)
Twierdzenie 5.7
Liczba nieizomorficznych kolorowań zbioru \( X \) za pomocą \( k \) barw wynosi
\( \zeta_{G}( k,k,\ldots,k ), \)
gdzie \( G \) jest grupą możliwych permutacji elementów \( X \).
Dowód
Niech \( A \) będzie zbiorem wszystkich kolorowań \( k \) barwami zbioru \( X \). Szukana liczba nieizomorficznych kolorowań jest równa liczbie orbit G-zbioru \( ( \widehat{G},A ) \) i, na mocy Wniosku 5.5 oraz Obserwacji 5.6, wynosi:
\( \displaystyle \frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in\widehat{G}}\vert {\sf Fix}( \widehat{g} ) \vert =\frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( {g} ) \vert. \)
Pozostaje więc policzyć liczbę punktów stałych każdej z permutacji \( \widehat{g} \) . Jeśli \( \omega \) jest punktem stałym permutacji \( \widehat{g} \), a \( ( i_1,i_2,\ldots,i_l ) \) jest cyklem tej permutacji, to
\( \displaystyle \omega\!( i_{j+1} ) =\omega\!( g\!( i_j ) ) =( \widehat{g}\!( \omega ) )\!( i_j )=\omega\!( i_j ). \)
A zatem wszystkie elementy \( i_j \) tego cyklu są pokolorowane na ten sam kolor. Niech teraz permutacja \( g \) rozkłada się na \( m \) cykli. Ponieważ elementy każdego cyklu muszą być jednobarwne, a wszystkich możliwych do wykorzystania barw jest \( k \), to liczba możliwych kolorowań elementów \( X \) wynosi \( \vert {\sf Fix}( g ) \vert=k^m \). Z drugiej strony
\( \displaystyle \zeta_{g}( k,k,\ldots,k ) =k^{\alpha_1}\cdot k^{\alpha_2}\cdot\ldots\cdot k^{\alpha_s}, \)
gdzie \( \alpha_i \) jest liczbą cykli \( i \) elementowych. Ale oczywiście \( \alpha_1+\alpha_2+\ldots+\alpha_s=m \), skąd \( \vert {\sf Fix}( g ) \vert=\zeta_{g}( k,k,\ldots,k ) \). Liczba nieizomorficznych kolorowań jest więc równa
\( \displaystyle \frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( g ) \vert =\frac{1}{\vert G \vert}\sum_{g\in G} \zeta_{g}( k,k,\ldots,k ) =\zeta_{G}( k,k,\ldots,k ). \)
Przykład
Niech \( ( G_t,\circ ) \) będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w \( 3 \)-wymiarowej przestrzeni. Wiemy już, że indeks grupy \( G_t \) wynosi
\( \zeta_{G_t}( x_1,x_2,x_3,x_4 )=\frac{1}{12}( x_1^4+8x_1x_3+3x_2^2 ). \)
Aby zliczyć wszystkie, nieizomorficzne względem obrotów, kolorowania wierzchołków czworościanu na \( 2 \) kolory wystarczy, wobec Twierdzenia 5.7, policzyć wartość
\( \zeta_{G_t}( 2,2,2,2 )=5. \)
Faktycznie. Jedynymi kolorowaniami nieizomorficznymi względem obrotów są te, przedstawione na rysunku.
Wskaźnik kolorowania \( \omega:X\longrightarrow K \), dla zbioru kolorów \( K=\lbrace 1,2,\ldots,k \rbrace \) to
\( {\sf ind}( \omega )=x_1^{n_1}\cdot x_2^{n_2}\cdot\ldots\cdot x_k^{n_k}, \)
gdzie \( n_i \) to liczba elementów ze zbioru \( X \) pokolorowanych przez \( \omega \) na kolor \( i \).
Ponadto dla zbioru kolorowań \( A \) definiuje się funkcję tworzącą postaci
\( \displaystyle {\sf U}_{A}( x_1,x_2,\ldots,x_k )=\sum_{\omega\in A}{\sf ind}( \omega ) =\sum_{\omega\in A}x_1^{n_1( \omega )}\cdot x_2^{n_2( \omega )}\cdot\ldots\cdot x_k^{n_k( \omega )}. \)
Twierdzenie 5.8
Dla podziału zbioru \( X=Y_1\cup Y_2\cup\ldots\cup Y_l \) mamy
\( \displaystyle {\sf U}_{D}( x_1,x_2,\ldots,x_k )=\prod_{i=1}^l( x_1^{\vert Y_i \vert} +x_2^{\vert Y_i \vert} +\ldots+ x_k^{\vert Y_i \vert} ), \)
gdzie \( D \) jest zbiorem kolorowań stałych na zbiorach \( Y_i \).
Dowód
Niech \( \vert Y_i \vert=m_i \). Iloczyn
\( \displaystyle \prod_{i=1}^l( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} ) \)
jest sumą jednomianów postaci \( \beta x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \). Aby przeanalizować te jednomiany zauważmy, że mnożąc po jednym składniku \( x_j^{m_i} \) z każdego czynnika iloczynu, otrzymamy jednomian postaci \( x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \). Wartość \( \beta \) jest więc równa wszystkim możliwym iloczynom \( x_{j_1}^{m_1}\ x_{j_2}^{m_2}\ldots x_{j_l}^{m_l} \) dającym \( x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \). Porządkując składniki \( x_{j_i} \) otrzymujemy, że \( \beta \) jest liczbą wszystkich zestawów sum postaci
\( \begin{align*} \alpha_1 & =m_{i_{1,1}}+\ldots+m_{i_{1,{s_1}}} \\ \alpha_2 & =m_{i_{2,1}}+m_{i_{2,2}}+\ldots+m_{i_{2,{s_2}}} \\ & \cdots & \\ \alpha_k & =m_{i_{k,1}}+\ldots+m_{i_{k,{s_k}}}. \end{align*} \)
Każdy taki zestaw sum można utożsamić z kolorowaniem, które przyporządkowuje elementom z \( Y_{i_{1,1}}\cup\ldots\cup Y_{i_{1,{s_1}}} \) pierwszą barwę, elementom z \( Y_{i_{2,1}}\cup Y_{i_{2,2}}\cup\ldots\cup Y_{i_{2,{s_2}}} \) kolejną barwę, itd... Otrzymujemy w ten sposób, że \( \beta \) jest liczbą kolorowań stałych na każdym ze zbiorów \( Y_i \). Kolorowania te używają \( \alpha_1 \) razy pierwszej barwy, \( \alpha_2 \) razy drugiej barwy, itd..., czyli jednomian \( \beta x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \) jest składnikiem w sumie powstałej z iloczynu \( {\sf U}_{D}( x_1,x_2,\ldots,x_k ) \) przez wymnożenie wszystkich czynników.
Twierdzenie 5.9 [G. Pólya 1935]
Niech \( \vert X \vert=n \) a \( D \) będzie zbiorem wszystkich nieizomorficznych, ze względu na działanie grupy \( G \) na zbiorze \( X \), kolorowań zbioru \( X \) za pomocą \( k \) barw. Wtedy funkcja tworząca \( {\sf U}_{D} \) jest postaci
\( {\sf U}_{D}( x_1,x_2,\ldots,x_k )=\zeta_{G}( \sigma_1,\sigma_2,\ldots,\sigma_n ), \)
gdzie
\( \sigma_i=x_1^i+x_2^i+\ldots+x_k^i. \)
Dowód
Zbiór \( D \) jest zbiorem reprezentantów orbit G-zbioru \( ( \widehat{G},A ) \), gdzie \( A \) jest zbiorem wszystkich możliwych kolorowań zbioru \( X \). Podstawiając, w Twierdzeniu 5.4, za funkcję \( f \) wskaźnik kolorowania \( {\sf ind} \) otrzymujemy
\( \displaystyle \sum_{\omega\in D}{\sf ind}( \omega ) =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} ( \sum_{\omega \in {\sf Fix}( \widehat{g} )} {\sf ind}( \omega ) ). \)
Korzystając z definicji wskaźnika kolorowania dostajemy
\( \displaystyle {\sf U}_{D}( x_1,x_2,\ldots,x_k ) =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ). \)
Zbiór \( {\sf Fix}( \widehat{g} ) \) jest zbiorem kolorowań, przy których elementy z tego samego cyklu otrzymują tę samą barwę. A zatem, z Twierdzenia 5.8 wynika, że
\( \displaystyle {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) =\prod_{i=1}^l( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} )=\prod_{i=1}^l\sigma_{m_i}, \)
gdzie \( m_i \) jest rozmiarem \( i \)-tego cyklu. Niech \( \alpha_i \) będzie liczbą cykli w \( g \) o długości \( i \). Otrzymujemy więc
\( \begin{align*} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) & =\sigma_1^{\alpha_1}\cdot\sigma_2^{\alpha_2}\cdot\ldots\cdot\sigma_n^{\alpha_n} \\ & =\zeta_{g}( \sigma_1,\sigma_2,\ldots,\sigma_n ). \end{align*} \)
Obserwacja 5.6 daje więc teraz
\( \begin{align*} {\sf U}_{D}( x_1,x_2,\ldots,x_k ) & =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) \\ & =\frac{1}{\vert G \vert}\sum_{g\in G} \zeta_{g}( \sigma_1,\sigma_2,\ldots,\sigma_n ) \\ & =\zeta_{G}( \sigma_1,\sigma_2,\ldots,\sigma_n ). \end{align*} \)
Przykład
Użyjemy opisanych twierdzeń do wyznaczenia liczby wszystkich nieizomorficznych pokolorowań wierzchołków kwadratu na dwa kolory. Rozważmy więc wszystkie osiem symetrii kwadratu, jak przedstawiono na animacji.
Grupa permutacji \( G_{\diamondsuit} \) wyznaczona przez te symetrie ma \( 8 \) następujących elementów:
\( \begin{array} {lp{20mm}l} id\ =\ ( 0 )\!( 1 )\!( 2 )\!( 3 ) & & g_4\ =\ ( 0 )\!( 3 )\!( 12 ) \\ g_1\ =\ ( 0123 ) & & g_5\ =\ ( 1 )\!( 2 )\!( 03 ) \\ g_2\ =\ ( 02 )\!( 13 ) & & g_6\ =\ ( 02 )\!( 13 ) \\ g_3\ =\ ( 0321 ) & & g_7\ =\ ( 01 )\!( 23 ) \end{array} \)
Z podanego rozkładu na cykle dostajemy, że indeks grupy \( G_{\diamondsuit} \) to
\( \zeta_{G_{\diamondsuit}}( x_1,x_2,x_3,x_4 ) =\frac{1}{8}( x_1^4+2x_1^2x_2+3x_2^2+2x_4 ). \)
Aby znaleźć liczbę nieizomorficznych kolorowań takich, że \( i \) wierzchołków jest pokolorowanych na biało \( □ \), a pozostałe \( 4-i \) na czarno \( ■ \), wystarczy wyliczyć współczynnik przy \( □^i ■^{4-i} \) w funkcji tworzącej postaci
\( \begin{align*} {\sf U}_{D}( □,■ ) & =\zeta_{G_{\diamondsuit}}( □+■,\ □^2+■^2,\ □^3+■^3,\ □^4+■^4 ) \\ & =□^4+□^3■+2□
^2■^2+□ ■^3+■^4. \end{align*} \)
Rysunek przedstawia wszystkie możliwe nieizomorficzne kolorowania.
Nieizomorficzne kolorowania wierzchołków kwadratu
Ciała odgrywają olbrzymią rolę we wszystkich prawie dziedzinach matematyki. Chyba najbardziej znanym ciałem jest zbiór liczb rzeczywistych z dodawaniem i mnożenie. Wraz z ciałem liczb zespolonych, ciało liczb rzeczywistych stanowi podstawę Analizy Matematycznej. Ten wykład poświęcony jest podstawowym własnościom ciał skończonych.
Koncepcje ciała stosowali jako pierwsi Niels Abel i Evariste Galois w swoich pracach dotyczących rozwiązywalności równań algebraicznych. W 1893, Heinrich Weber podał pierwszą kompletną definicję abstrakcyjnego ciała. W 1910, Ernst Steinitz opublikował pracę, która dała podstawy współczesnej teorii ciał.
Ciało to struktura \( {\bf F}=(F,+,\cdot,0,1) \), gdzie \( F \) jest zbiorem, \( 0,1\in F \) i \( 0\neq1 \), a \( + \) i \( \cdot \) to dwuargumentowe działania na \( F \) spełniające następujące warunki:
Ciało \( {\bf F}=(F,+,\cdot,0,1) \) jest skończone jeśli zbiór \( F \) jest skończony, w przeciwnym wypadku \( {\bf F} \) jest nieskończone.
Zgodnie z ogólnie przyjętą konwencją posługujemy się następującą notacją:
Przykład
Obserwacja 6.1
Dla elementu \( x \) ciała \( {\bf F}=(F,+,\cdot,0,1) \) mamy \( x\cdot0=0 \).
Dowód
Mamy \( x\cdot0=x\cdot(0+0)=x\cdot0+x\cdot0 \), co wobec prawa skracania dla grupy \( (F,+,0) \) daje \( 0=x\cdot0 \).
Obserwacja 6.2
Dla elementów \( x,y\in F \) ciała \( {\bf F}=(F,+,\cdot,0,1) \), jeśli \( xy=0 \), to \( x=0 \) lub \( y=0 \).
Dowód
Załóżmy, że \( xy=0 \) i \( x\neq0 \). Ponieważ \( x\in F^* \), to \( x \) ma element odwrotny w \( (F^*,\cdot,1) \), i wtedy \( y=1\cdot y=(x^{-1}x)y=x^{-1}(xy)=x^{-1}\cdot0=0 \).
W wykładzie tym pominiemy własności ciała liczb rzeczywistych. Skoncentrujemy naszą uwagę na charakteryzacji ciał skończonych, nazywanych też ciałami Galois. W tym celu potrzebujemy jednak wielu dodatkowych pojęć.
Pierścień to struktura \( {\mathbf R}=(R,+,\cdot,0,1) \), gdzie \( R \) jest zbiorem, \( 0,1\in R \) i \( 0\neq1 \), a \( + \) i \( \cdot \) to działania dwuargumentowe spełniające następujące warunki:
\( \begin{align*} x\cdot(y\cdot z) & =(x\cdot y)\cdot z \\ (x+y)\cdot z & =x\cdot z+y\cdot z, \\ x\cdot(y+z) & =x\cdot y+x\cdot z, \\ 1\cdot x & =x\cdot1=x. \end{align*} \)
Pierścień \( {\mathbf R}=(R,+,\cdot,0,1) \) jest przemienny jeśli \( xy=yx \) dla dowolnych \( x,y\in R \).
Oczywiście każde ciało jest pierścieniem. W pierścieniu mnożenie nie musi być jednak przemienne, a jego elementy nie muszą mieć elementów odwrotnych ze względu na mnożenie \( \cdot \). W pierścieniach, tak jak i w ciałach, \( 0 \) przemnożone przez cokolwiek pozostaje zerem (niezależnie z której strony mnożymy \( 0 \)). Dowód przebiega analogicznie jak dla ciał.
Obserwacja 6.3
Dla dowolnego pierścienia \( {\mathbf R}=(R,+,\cdot,0,1) \) i \( x\in R \)
\( x\cdot0=0\cdot x=0. \)
W odróżnieniu od ciał pierścienie mogą posiadać dzielniki zera, czyli niezerowe elementy, których iloczyn daje zero.
Przykład
\( \left(\begin{array} {cc}3 & 1 \\ 0 & 4\end{array} \right)\cdot\left(\begin{array} {cc}4 & 2 \\ 5 & 5\end{array} \right)=\left(\begin{array} {cc}17 & 11 \\ 20 & 20\end{array} \right),\qquad \left(\begin{array} {cc}4 & 2 \\ 5 & 5\end{array} \right)\cdot\left(\begin{array} {cc}3 & 1 \\ 0 & 4\end{array}\right )=\left(\begin{array} {cc}12 & 12 \\ 15 & 25\end{array} \right). \)
Dotychczas przyjmowaliśmy, że wielomian to funkcja \( f(x) \), określona np. na zbiorze liczb całkowitych, postaci:
\( f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0, \)
gdzie \( a_i \) były współczynnikami wielomianu. Jest to podejście analityczne. Przedstawimy teraz algebraiczny odpowiednik tego pojęcia. Istotną zmianą będzie rozróżnienie formalnego wyrażenia jakim jest wielomian od funkcji wielomianowej (czyli ewaluacji wielomianu). Zobaczymy później, że takie rozróżnienie jest potrzebne, zwłaszcza w pierścieniach i ciałach skończonych.
Wielomian \( a(x) \) nad pierścieniem \( {\mathbf R}=(R,+,\cdot,0,1) \) to formalne wyrażenie postaci
\( a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0, \)
gdzie \( n\in\mathbb{N} \), \( a_i\in R \) i \( a_n\neq0 \). Elementy \( a_i \) to współczynniki wielomianu. Współczynnik \( a_n \) to współczynnik wiodący. Wielomian postaci \( a_0 \) nazywamy stałą i często utożsamiamy go z odpowiednim elementem pierścienia \( {\mathbf R} \). Dopuszczamy również wielomian stały \( a_0=0 \) (mimo że współczynnik wiodący równy jest \( 0 \)) - jest to wielomian zerowy. Symbole \( x^i \) należy traktować jedynie jako etykiety pozycji dla współczynników. Wielomiany równie dobrze można zapisywać w tradycyjnej notacji dla ciągów, czyli \( (a_n,\ldots,a_0) \).
Wielomiany równe to wielomiany (ciągi) w których kolejne współczynniki są równe.
Zbiór wszystkich wielomianów nad pierścieniem \( {\mathbf R} \) oznaczamy przez \( R[x] \).
Suma wielomianów \( a(x),b(x)\in {R}[x] \), dla \( a(x)=a_mx^m+\ldots+a_0 \), \( b(x)=b_nx^n+\ldots+b_0 \) to wielomian \( a(x)+b(x)\in{R}[x] \) zadany przez
\( a(x)+b(x)=(a_k+b_k)x^k+(a_{k-1}+b_{k-1})x^{k-1}+\ldots+(a_0+b_0), \)
gdzie \( k=\max(m,n) \) oraz niezdefiniowane wartości \( a_i \) bądź \( b_i \) traktujemy jako \( 0 \).
Iloczyn wielomianów \( a(x),b(x)\in {R}[x] \), dla \( a(x)=a_mx^m+\ldots+a_0 \), \( b(x)=b_nx^n+\ldots+b_0 \) to wielomian \( a(x)\cdot b(x)\in {R}[x] \) zadany przez
\( \begin{align*} a(x)\cdot b(x) & =(a_mb_n)x^{m+n}+(a_{m-1}b_n+a_mb_{n-1})x^{m+n-1}+\ldots \\ & +(\sum_{j=0}^ia_jb_{i-j})x^i+\ldots+(a_1b_0+a_0b_1)x+(a_0+b_0). \end{align*} \)
Przykład
Suma i iloczyn wielomianów
\( a(x)=3x^2+2x,\qquad b(x)=2x+3. \)
nad pierścieniem \( (\mathbb{Z}_4,+,\cdot,0,1) \) to odpowiednio:
\( \begin{align*} a(x)+b(x) & =(3+0)x^2+(2+2)x+(0+3)=3x^2+3, \\ a(x)\cdot b(x) & =(3+0)x^3+(0\cdot0+2\cdot2+3\cdot3)x^2+(0\cdot2+2\cdot3)x+(0+3) \\ & =3x^3+x^2+2x+3. \end{align*} \)
Zauważmy, że zgodnie z nawykami pomijamy symbole \( x^i \), dla \( a_i=0 \), np.: \( 3x^2+3 \) formalnie oznacza \( 3x^2+0x+3 \).
Elementarny, ale żmudny dowód następnej obserwacji pozostawiamy jako ćwiczenie.
Obserwacja 6.4
Jeśli \( {\mathbf R} \) jest pierścieniem (przemiennym), to \( {\mathbf R}[x]=(R[x],+,\cdot,0,1) \) jest pierścieniem (przemiennym), gdzie \( + \) i \( \cdot \) to operacje sumy i iloczynu wielomianów.
Pierścień wielomianów nad pierścieniem \( {\mathbf R} \) to pierscień \( {\mathbf R[x]}=({R}[x],+,\cdot,0,1) \).
Przedstawimy teraz całą serię obserwacji dla pierścienia wielomianów, które są analogią do własności pierścienia liczb całkowitych. Będą to pewnego rodzaju uogólnienia dzielenia całkowitego liczb, algorytmu Euklidesa, pojęcia liczby pierwszej i Fundamentalnego Twierdzenia Arytmetyki.
Stopień wielomianu \( a(x) \) to liczba \( {\sf deg}(a(x)) \) równa indeksowi jego współczynnika wiodącego. Uwaga: wielomian zerowy ma stopień niezdefiniowany (lub czasem przyjmowany jako \( -\infty \)).
Dodając znane nam, "zwykłe" wielomiany, powiedzmy nad \( \mathbb{Z} \) lub \( \mathbb{R} \), wiemy, iż stopień sumy nie przekracza większego ze stopni wielomianów sumowanych. Podobnie iloczyn takich wielomianów zawsze ma stopień równy sumie stopni mnożonych wielomianów. Analogiczne prawo dla dodawania zachodzi dla wielomianów nad dowolnym pierścieniem. Niestety stopień iloczynu wielomianów nad dowolnym pierścieniem może, odbiegając od tych intuicji, być mniejszy niż suma stopni. Winne temu są dzielniki zera. Dlatego czasem pozostaniemy z wielomianami o współczynnikach z jakiegoś ciała.
Obserwacja 6.5
Dla dowolnego pierścienia \( {\mathbf R} \) i niezerowych wielomianów \( a(x),b(x)\in{\mathbf R}[x] \), mamy:
\( {\sf deg}(a(x)+b(x))\leq\max({\sf deg}(a(x)),{\sf deg}(b(x)) ). \)
Przykład
Suma wielomianów nad skończonym ciałem może mieć stopień silnie mniejszy, niż stopień każdego składnika sumy. Na przykład dla wielomianów pierwszego stopnia \( 2x+1 \) i \( 3x+1 \) nad ciałem \( \mathbb{Z}_5 \) ich suma \( (2x+1)+(3x+1)= 2 \) jest wielomianem stałym. Podobnie iloczyn wielomianów nad skończonym pierścieniem może mieć stopień silnie mniejszy od sumy stopni mnożonych wielomianów. Na przykład, nad pierścieniem \( \mathbb{Z}_6 \) wielomiany \( 3x^3+2x^2-1 \) i \( 2x^2+1 \) są stopnia \( 2 \), podczas gdy ich iloczyn \( 6x^5+3x^3+4x^4+2x^2-2x^2-1=4x^4+3x^3-1 \) jest stopnia \( 4 \).
Obserwacja 6.6
Dla dowolnego pierścienia \( {\mathbf R} \) i wielomianów \( a(x),b(x)\in{\mathbf R}[x] \), mamy
\( {\sf deg}(a(x)\cdot b(x))\leq {\sf deg}(a(x))+{\sf deg}(b(x)). \)
Jeśli pierścień \( {\mathbf R} \) jest ciałem, a wielomiany są niezerowe, to
\( {\sf deg}(a(x)\cdot b(x))= {\sf deg}(a(x))+{\sf deg}(b(x)). \)
Dowód
Pierwsza część wynika wprost z definicji iloczynu wielomianów. Niech teraz współczynnikami wiodącymi wielomianów \( a(x),b(x) \) będą odpowiednio \( a_m \) i \( b_n \) Wtedy najwyższym zdefiniowanym, \( (m+n) \)-tym, współczynnikiem iloczynu jest \( a_mb_n \). Z Obserwacji 6.2 mamy \( a_mb_n\neq0 \), zatem jest to współczynnik wiodący.
Obserwacja 6.6 jest teoretyczną podstawą dla jednoznacznego dzielenia z resztą w pierścieniu wielomianów nad ciałem. Następny przykład jest modyfikacją algorytmu dzielenia wielomianów nad \( \mathbb{R} \).
Przykład
Wydzielmy wielomian \( x^5+5x^4+5x^3+x+5 \) przez \( x^2+4 \) nad ciałem \( {\bf \mathbb{Z}_7} \):
\( \begin{array} {lrrrrrr} & x^3 & +5x^2 & +x & +1 \\ \hline x^2+4| & x^5 & +5x^4 & +5x^3 & +0x^2 & +x & +5 \\ & x^5 & & +4x^3 \\ \hline & & 5x^4 & +x^3 & +0x^2 & +x & +5 \\ & & 5x^4 & & +6x^2 \\ \hline & & & x^3 & +x^2 & +x & +5 \\ & & & x^3 & & +4x \\ \hline & & & & x^2 & +4x & +5 \\ & & & & x^2 & & +4 \\ \hline & & & & & 4x & +1 \end{array} \)
Iloraz równy jest \( x^3+5x^2+x+1 \), zaś reszta \( 4x+1 \).
Obserwacja 6.7
Dla dowolnych wielomianów \( a(x),b(x) \) nad ciałem \( {\bf F} \), gdzie \( b(x)\neq0 \) istnieją unikalne wielomiany \( q(x),r(x)\in{\bf F}[x] \) takie, że
\( a(x)=q(x)b(x)+r(x), \)
gdzie \( r(x)=0 \) lub \( {\sf deg}(r(x)) < {\sf deg}(b(x)) \).
Dowód
Najpierw wykażemy istnienie takich wielomianów. Dla ustalonego wielomianu \( b(x) \) poprowadzimy indukcję względem stopnia wielomianu \( a(x) \). Jeśli \( a(x)=0 \), to \( q(x)=r(x)=0 \) są szukanymi wielomoanami. Dla \( {\sf deg}(a(x)) < {\sf deg}(b(x)) \) mamy
\( a(x)=0\cdot b(x)+a(x). \)
Gdy zaś \( {\sf deg}(a(x))\geq{\sf deg}(b(x)) \), zakładamy indukcyjnie, iż dla wszystkich wielomianów stopnia mniejszego niż stopień \( a(x) \) istnieją postulowane w tezie wielomiany. Niech
\( a(x)=a_mx^m +\ldots+a_0,\qquad b(x)=b_nx^n+\ldots+b_0\qquad \) dla \( a_m\neq 0 \), \( b_n\neq 0 \),
oraz
\( a'(x)=a(x)-a_mb_n^{-1}x^{m-n}b(x). \)
Wtedy współczynnik wielomianu \( a'(x) \) przy \( x^{m} \) jest równy \( 0 \), gdyż
\( a'_m=a_m-a_mb_n^{-1}b_n=0. \)
Zatem \( {\sf deg}(a'(x)) < {\sf deg}(a(x)) \) (lub \( a'(x)=0 \)) i z założenia indukcyjnego
\( a'(x)=q'(x)b(x)+r(x), \)
gdzie \( {\sf deg}(r(x)) < {\sf deg}(b(x)) \) lub \( r(x)=0 \). Zauważmy, że
\( a(x)=(q'(x)+a_mb_n^{-1}x^m)b(x)+r(x), \)
czyli szukane wielomany to \( q(x)=q'(x)+a_mb_n^{-1}x^m \) i \( r(x) \).
Dla dowodu jednoznaczności załóżmy, że
\( a(x)=q_0(x)b(x)+r_0(x)=q_1(x)b(x)+r_1(x), \)
gdzie \( r_i(x)=0 \) lub \( {\sf deg}(r_i(x)) < {\sf deg}(b(x)) \) dla \( i=0,1 \). Przekształcając ostatnią równość otrzymujemy
\( (q_0(x)-q_1(x))b(x)=r_1(x)-r_0(x). \)
Z Obserwacji 6.5 i 6.6, jeśli \( q_0(x)\neq q_1(x) \), to \( {\sf deg}((q_0(x)-q_1(x))b(x))\geq{\sf deg}(b(x)) \). Natomiast dla \( r_0(x)\neq r_1(x) \) mamy \( {\sf deg}(r_1(x)-r_0(x)) < {\sf deg}(b(x)) \). Zatem jedyna możliwość aby równość zaszła to \( q_0(x)=q_1(x) \) i \( r_0(x)=r_1(x) \).
Zajmiemy się teraz dokładniej pierścieniem \( {\bf F}[x] \) wielomianów nad ciałem \( {\bf F} \).
Wielomian \( b(x) \) dzieli (jest dzielnikiem) wielomian \( a(x) \) (co zapisujemy \( b(x)|a(x) \)), jeśli \( a(x)=q(x)b(x) \) dla pewnego \( q(x)\in{\bf F}[x] \). Mówimy też wtedy, że \( q(x) \) jest wielokrotnością \( b(x) \).
Okazuje się, iż dowolny niezerowy wielomian stały jest trywialnym dzielnikiem dowolnego wielomianu. W tym sensie wielomiany stałe zachowują się podobnie do liczb \( -1,1 \) w pierścieniu liczb całkowitych.
Obserwacja 6.8
Dowolny, niezerowy wielomian stały nad ciałem \( {\bf F} \) dzieli dowolny wielomian nad \( {\bf F} \).
Dowód
Dla dowolnego \( c\in F^* \) i wielomianu \( a(x)\in{\mathbf F}[x] \) mamy
\( a(x)=(c^{-1}a(x))\cdot c. \)
Obserwacja 6.9
Dla dowolnego ciała \( {\bf F} \) i \( a(x),b(x)\in{\mathbf F}[x] \) jeśli \( a(x)|b(x) \) i \( b(x)|a(x) \) to \( a(x)=c\cdot b(x) \) dla pewnego \( c\in F^* \).
Dowód
Załóżmy, że \( a(x)=q(x)b(x) \) i \( b(x)=q'(x)a(x) \). Mamy wtedy
\( a(x)=q(x)b(x)=q(x)q'(x)a(x). \)
Z Obserwacji 6.6 \( {\sf deg}(a(x)) ={\sf deg}(q(x))+{\sf deg}(q'(x))+{\sf deg}(a(x)) \), czyli \( {\sf deg}(q(x))={\sf deg}(q'(x))=0 \). Zatem \( a(x)=c\cdot b(x) \) dla pewnego \( c\in F^* \).
Największy wspólny dzielnik wielomianów \( a(x),b(x)\in{\bf F}[x] \) to taki wielomian \( g(x) \), że
W przeciwieństwie do liczb całkowitych największy wspólny dzielnik dwu wielomianów nie jest jednoznacznie określony. Wykażemy jednak najpierw, że taki wielomian zawsze istnieje. Pomocne w wykazaniu tego jest pojęcie ideału pierścienia.
Ideał pierścienia \( (R,+,\cdot,0,1) \) to niepusty podzbiór \( I\subseteq R \) o własnościach:
Obserwacja 6.10
Przecięcie dowolnej rodziny ideałów pierścienia jest ideałem tego pierścienia.
Ideał generowany przez zbiór \( X\subseteq R \) to przecięcie wszystkich ideałów zawierających \( X \).
Ideał główny to ideał generowany przez zbiór jednoelementowy.
Obserwacja 6.11
W pierścieniu wielomianów \( {\mathbf F}[x] \) nad ciałem \( {\bf F} \) każdy ideał jest główny.
Dowód
Niech \( I \) będzie ideałem pierścienia \( {\bf F}[x] \). Jeśli \( I \) składa się tylko z wielomianu zerowego, to \( I \), jako generowany przez \( {\{ {0} \} } \), jest główny. Niech teraz \( g(x) \) będzie niezerowym wielomianem z \( I \) o minimalnym stopniu. Pokażemy, że \( {\{ {g(x)} \} } \) generuje ideał \( I \). Istotnie, niech \( p(x)\in I \). Wydzielając \( p(x) \) przez \( g(x) \) otrzymujemy
\( p(x)=q(x)g(x)+r(x), \)
gdzie \( r(x)=0 \) lub \( {\sf deg}(r(x)) < {\sf deg}(g(x)) \). Zatem \( r(x)\in I \) bo \( r(x)=p(x)-q(x)g(x) \) i \( p(x),q(x)g(x)\in I \). Ale \( g(x) \) ma minimalny stopień wśród wielomianów w \( I \). Zatem \( r(x)=0 \). To oznacza, iż \( p(x)=q(x)g(x) \), czyli \( {\{ {g(x)} \} } \) generuje \( I \).
Obserwacja 6.12
Dowolne dwa wielomiany \( a(x),b(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) mają największy wspólny dzielnik. Ponadto dla dowolnych \( g(x),h(x) \) największych wspólnych dzielników \( a(x) \) i \( b(x) \) zachodzi \( g(x)=c\cdot h(x) \) dla pewnego \( c\in F \).
Dowód
Niech \( I \) będzie ideałem pierścienia \( {\mathbf F[x]} \) generowanym przez \( {\{ {a(x),b(x)} \} } \). Wtedy \( I={\{ {a'(x)a(x)+b'(x)b(x): a'(x),b'(x)\in{\mathbf F}[x]} \} } \). Z drugiej strony, na podstawie Obserwacji 6.11, ideał \( I \) jest główny. Niech więc \( g(x) \) generuje \( I \) Postulujemy, iż \( g(x) \) jest największym wspólnym dzielnikiem \( a(x) \) i \( b(x) \). Ponieważ \( a(x),b(x)\in I \) a \( I \) jest zbiorem wielokrotności \( g(x) \), to \( g(x)|a(x) \) i \( g(x)|b(x) \). Ponadto, dla dowolnego \( d(x) \) wspólnego dzielnika \( a(x) \) i \( b(x) \) mamy \( d(x)|g(x) \), gdyż \( g(x)=a'(x)a(x)+b'(x)b(x) \) dla pewnych \( a'(x),b'(x)\in{\mathbf F}[x] \).
Dla dowodu drugiej części załóżmy, że \( g(x),h(x)\in{\mathbf F}[x] \) są największymi wspólnymi dzielnikami \( a(x) \) i \( b(x) \). Wtedy mamy \( g(x)|h(x) \) i \( h(x)|g(x) \) i z Obserwacji 6.9 \( g(x)=c\cdot h(x) \) dla pewnego \( c\in F \).
Wniosek 6.13
Dla dowolnych wielomianów \( a(x),b(x) \) nad ciałem \( {\bf F} \) jeśli \( g(x) \) jest największym wspólnym dzielnikiem \( a(x),b(x) \), to \( g(x)=\lambda(x)a(x)+\mu(x)b(x) \) dla pewnych \( \lambda(x),\mu(x)\in{\mathbf F}[x] \).
Dowód
W dowodzie Obserwacji 6.12 wykazaliśmy, iż wszystkie największe wspólne dzielniki \( a(x) \) i \( b(x) \) są w ideale generowanym przez \( {\{ {a(x),b(x)} \} } \), co jest równoważne z tezą wniosku.
Wielomian unormowany nad ciałem \( {\bf F} \) to wielomian, którego współczynnik wiodący równy jest \( 1 \). Oczywiście dowolny, niezerowy wielomian \( p(x) \) może być przedstawiony w postaci \( p(x)=c\cdot u(x) \), gdzie \( c\in F \), a \( u(x) \) jest wielomianem unormowanym tego samego stopnia co \( p(x) \).
Wniosek 6.14
Dla dowolnych wielomianów \( a(x),b(x) \) nad ciałem \( {\bf F} \) istnieje dokładnie jeden unormowany największy wspólny dzielnik \( a(x),b(x) \).
Algorytm Euklidesa pozwalający na znalezienie największego wspólnego dzielnika dwu liczb całkowitych, może być łatwo rozszerzony z pierścienia liczb całkowitych na pierścienie wielomianów.
Dane są wielomiany \( a(x),b(x) \) nad ciałem \( {\bf F} \). Dla obliczenia największego wspólnego dzielnika wykonujemy następującą sekwencję dzieleń:
\( \begin{align*} a(x) & =b(x)q_0(x)+r_0(x), \\ b(x) & =r_0(x)q_1(x)+r_1(x), \\ r_0(x) & =r_1(x)q_2(x)+r_2(x), \\ & \ldots & \\ r_{n-2} & =r_{n-1}(x)q_n(x)+r_n(x), \\ r_{n-1} & =r_n(x)q_{n+1}(x). \end{align*} \)
Ponieważ stopnie wielomianów \( r_i \) dają ciąg silnie malejący, to po skończonej liczbie kroków uda nam się przeprowadzić dzielenie bez reszty. Ostatnia (niezerowa) reszta \( r_n(x) \) okazuje się być szukanym wielomianem - największym wspólnym dzielnikiem \( a(x) \) i \( b(x) \).
Z ostatniej równości wynika, iż \( r_n(x) \) dzieli \( r_{n-1}(x) \). Przedostatnia równość implikuje, że \( r_n(x) \) dzieli także \( r_{n-2}(x) \), itd., zatem \( r_n(x)|a(x) \) i \( r_n(x)|b(x) \). Ponadto dowolny \( d(x) \) dzielnik \( a(x) \) i \( b(x) \) dzieli \( r_0(x) \), bo \( r_0(x)=a(x)-q_0(x)b(x) \). Ponieważ \( d(x) \) dzieli \( b(x) \) i \( r_0(x) \), to ma podstawie drugiej równości \( d(x) \) dzieli też \( r_1(x) \). Idąc wzdłuż kolejnych równości dostajemy \( d(x)|r_n(x) \).
Analogicznie jak w przypadku pierścienia liczb całkowitych, algorytm Euklidesa może posłużyć do wskazania wielomianów \( \lambda(x),\mu(x) \) takich, że \( \lambda(x)a(x)+\mu(x)b(x)=r_n(x) \).
Przykład
Znajdźmy największy wspólny dzielnik wielomianów \( 5x^3+3x^2+5x+5 \) i \( 3x^2+1 \) nad ciałem \( \mathbb{Z}_7 \) używając algorytmu Euklidesa dla wielomianów:
Pomocnicza tabelka elementów odwrotnych względem mnożenia:
\( \begin{array} {|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline n^{-1} & - & 1 & 4 & 5 & 2 & 3 & 6 \\ \hline \end{array} \)
\( \begin{array} {crrrr} & 4x & +1 \\ \hline 3x^2+1| & 5x^3 & +3x^2 & +5x & +5 \\ & 5x^3 & & +4x \\ \hline & & 3x^2 & +x & +5 \\ & & 3x^2 & & +1 \\ \hline & & & x & +4 \end{array} \)
\( \begin{array} {crrr} & 3x & +2 \\ \hline x+4| & 3x^2 & & +1 \\ & 3x^2 & +5x \\ \hline & & 2x & +1 \\ & & 2x & +1 \\ \hline & & & 0 \end{array} \)
\( \begin{align*} x+4 & =(5x^3+3x^2+5x+5)-(4x+1)(3x^2+1) \\ & =(5x^3+3x^2+5x+5)+(3x+6)(3x^2+1). \end{align*} \)
Kulminacją naszych rozważań o pierścieniach wielomianów będzie odpowiednika Fundamentalnego Twierdzenia Arytmetyki. Odpowiednikiem liczb pierwszych w pierścieniu wielomianów są oczywiście wielomiany nierozkładalne na iloczyn wielomianów o silnie mniejszym stopniu.
Wielomian nierozkładalny nad ciałem \( {\bf F} \) to taki niezerowy wielomian \( p(x) \), dla którego \( p(x)=a(x)b(x) \) implikuje, że \( a(x) \) jest stały lub \( b(x) \) jest stały.
Przykład
\( x,\qquad x+1. \)
\( x\cdot x=x^2,\qquad x\cdot(x+1)=x^2+x,\qquad (x+1)\cdot(x+1)=x^2+1. \)
\( x^2+x+1. \)
Obserwacja 6.15 [lemat Euklidesa dla wielomianów]
Dla dowolnych wielomianów \( a(x),b(x),p(x) \) nad ciałem \( {\bf F} \), jeśli \( p(x) \) jest nierozkładalny i \( p(x)|a(x)b(x) \), to \( p(x)|a(x) \) lub \( p(x)|b(x) \).
Dowód
Załóżmy, że \( p(x) \) nie dzieli \( a(x) \). Z nierozkładalności \( p(x) \) wiemy, że największym wspólnym dzielnikiem \( p(x) \) i \( a(x) \) jest dowolna stała, w szczególności \( 1\in{\bf F}[x] \). Z Wniosku 6.13 mamy \( \lambda(x)p(x)+\mu(x)a(x)=1 \) dla pewnych \( \lambda(x),\mu(x)\in{\bf F}[x] \). Mnożąc obie strony równości przez \( b(x) \) otrzymujemy
\( \lambda(x)p(x)b(x)+\mu(x)a(x)b(x)=b(x). \)
Zauważmy, że \( p(x) \) dzieli lewą stronę równości. Musi zatem dzielić i prawą.
Rozkład wielomianu unormowanego \( u(x) \) nad \( {\bf F} \) na nierozkładalne, unormowane czynniki to przedstawienie go w postaci \( u(x)=u_0(x)\cdot\ldots\cdot u_{n-1}(x) \), gdzie wszystkie \( u_i\in{\bf F}[x] \) są nierozkładalne i unormowane. Każdy, niezerowy, unormowany wielomian ma taki rozkład - wystarczy rozbijać kolejne rozkładalne czynniki na iloczyn wielomianów o mniejszym stopniu (wszystkie będą unormowane).
Rozkład dowolnego wielomianu \( p(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) to przedstawienie go w postaci \( p(x)=c\cdot u(x) \), gdzie \( c\in F \) a \( u(x) \) jest wielomianem unormowanym, i później rozłożenie \( u(x) \) na nierozkładalne, unormowane czynniki.
Obserwacja 6.16
Dowolny, niezerowy, unormowany wielomian nad ciałem \( {\bf F} \) ma jednoznaczny (z dokładnością do kolejności czynników) rozkład na nierozkładalne, unormowane czynniki.
Dowód
Indukcja po stopniu wielomianu \( u(x) \). Dla \( {\sf deg}(u(x))\leq1 \) wielomian \( u(x) \) jest nierozkładalny i sam stanowi swój jedyny rozkład. Rozważmy zatem dowolny \( u(x) \) stopnia \( n+1 \) i rozważmy jego dwa rozkłady na nierozkładalne czynniki
\( a_0(x)\cdot\ldots\cdot a_{m-1}(x)=u(x)=b_0(x)\cdot\ldots\cdot b_{n-1}(x). \)
Widzimy, iż \( a_0(x)|b_0(x)\cdot\ldots\cdot b_{n-1}(x) \). Z nierozkładalności \( a_0(x) \) i lematu Euklidesa mamy, iż \( a_0(x)|b_i(x) \) dla pewnego \( i \). Z nierozkładalności \( b_i(x) \) i faktu, iż \( a_0(x) \) i \( b_i(x) \) są unormowane otrzymujemy \( a_0(x)=b_i(x) \). Dzieląc obie strony równości przez ten wielomian \( a_0(x) \) otrzymujemy wielomian istotnie mniejszego stopnia. Zatem z założenia indukcyjnego ma on jednoznaczny rozkład, co kończy dowód.
Powyższa obserwacja nie daje niestety żadnych wskazówek jak znaleźć rozkład wielomianu. W ogólności jest to bardzo trudny problem. Istnieją jednak proste kryteria znajdowania pewnych szczególnych czynników rozkładu. W szczególności przedstawiamy warunek konieczny i wystarczający na to, by w rozkładzie wystąpił czynnik liniowy (tzn. wielomian pierwszego stopnia). Najpierw jednak musimy wprowadzić zapowiadane już pojęcie ewaluacji wielomianu.
Ewaluacja wielomianu \( p(x)=p_nx^n+\ldots+p_0 \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) to funkcja \( \overline{p}:F\longrightarrow F \) zadana przez
\( \overline{p}(x)=p_nx^n+\ldots+p_1x+p_0. \)
Dlaczego rozróżniamy wielomian od jego ewaluacji? Okazuje się, iż różne wielomiany mogą mieć taką samą ewaluację.
Przykład
Zgodnie z definicją dwa wielomiany są równe tylko wtedy, gdy wszystkie odpowiednie ich współczynniki są takie same. Rozważmy zatem dwa różne wielomiany nad ciałem \( {\bf \mathbb{Z}_2} \) i ich ewaluacje:
\( a(x)=x^2,\qquad b(x)=x^4+x^3+x^2, \)
\( \begin{array} {rclrcl} \overline{a}(0) & =0^2+0=0, & \overline{b}(0) & =0^2+0=0, \\ \overline{a}(1) & =1^2+1=0, & \overline{b}(1) & =1^2+1=0. \end{array} \)
Zatem \( a(x)\neq b(x) \) ale \( \overline{a}(x)=\overline{b}(x) \).
Obserwacja 6.17 [Bezout]
Dla dowolnego wielomianu \( p(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) i \( c\in F \) następujące warunki są równoważne:
Dowód
Załóżmy najpierw, iż \( x-c|p(x) \). Zatem \( p(x)=q(x)(x-c) \) dla pewnego \( q(x)\in{\bf F}[x] \). Ewaluacja wielomianu \( p(x) \) na elemencie \( c \) daje \( \overline{p}(c)=\overline{q}(c)\cdot(c-c)=0 \).
Dla dowodu implikacji odwrotnej załóżmy, że \( \overline{p}(c)=0 \). Dzieląc \( p(x) \) przez \( x-c \) otrzymujemy
\( p(x)=q(x)(x-c)+r(x), \)
dla pewnych \( q(x),r(x) \) gdzie \( r(x)=0 \) lub \( {\sf deg}(r(x)) < {\sf deg}(x-c)=1 \). Zatem \( r(x) \) jest wielomianem stałym i jego ewaluacja \( \overline{r} \) to funkcja stała, przyjmująca zawsze tę samą wartość \( r \in F \). Wtedy
\( 0=\overline{p}(c)=\overline{q}(c)\cdot(c-c)+r =r, \)
czyli \( r(x) \) jest wielomianem zerowym i \( x-c|p(x) \).
Pierwiastek wielomianu \( p(x) \) nad ciałem \( {\bf F} \) to taki element \( c\in F \), że \( \overline{p}(c)=0 \).
Przykład
Posługując się twierdzeniem Bezout znajdźmy rozkład wielomianu \( 3x^2+12x+8 \) nad ciałem \( {\bf \mathbb{Z}_{13}} \).
Pomocnicza tabela elementów odwrotnych w grupie multyplikatywnej \( (\mathbb{Z}_{13}^*,\cdot,1) \):
\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline n^{-1} & - & 1 & 7 & 9 & 10 & 8 & 11 & 2 & 5 & 3 & 4 & 6 & 12 \\ \hline \end{array} \)
\( \begin{align*} 3x^2+12x+8 & =3\cdot(3^{-1}\cdot3x^2+3^{-1}\cdot12x+3^{-1}\cdot8) \\ & =3(x^2+4x+7) \end{align*} \)
Obserwacja 6.18
Wielomian stopnia \( n \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) ma co najwyżej \( n \) pierwiastków.
Dowód
Załóżmy, że \( c_0,c_1,\ldots,c_{m-1}\in F \) są wszystkimi pierwiastkami wielomianu \( p(x) \) stopnia \( n \). Wtedy z Obserwacji 6.17 mamy \( x-c_i|p(x) \) dla \( i\in{\{ {0,\ldots,m-1} \} } \). Ponieważ \( x-c_i \) są nierozkładalne, z jednoznaczności rozkładu mamy
\( p(x)=c\cdot(x-c_0)\cdot\ldots\cdot(x-c_{m-1})q(x), \)
dla pewnego \( c\in F \) i unormowanego wielomianu \( q(x) \). Ale wtedy Obserwacja 6.6 daje \( n={\sf deg}(p(x))={\sf deg}((x-c_0)\cdot\ldots\cdot(x-c_{m-1})q(x))\geq m \).
Wracamy teraz do ciał skończonych. Jedyne ciała skończone jakie poznaliśmy do tej pory to \( (\mathbb{Z}_p,+,\cdot,0,1) \), gdzie \( p \) jest liczbą pierwszą. Czy istnieją inne ciała skończone? Jaką liczność mogą mieć inne ciała skończone? Czy wszystkie ciała liczności \( p \) są izomorficzne z ciałem \( \mathbb{Z}_p \)? Odpowiedzi na te pytania poznamy w pozostałej części wykładu.
Charakterystyka ciała \( {\bf F}=(F,+,\cdot,0,1) \) to rząd elementu \( 1 \) w grupie addytywnej \( (F,+,0) \). Oczywiście, jeśli ciało jest skończone to jego charakterystyka też jest skończona. Co więcej, ponieważ rząd elementu musi dzielić rząd grupy, to charakterystyka ciała skończonego \( {\bf F} \) dzieli \( \vert \).
Przykład
Obserwacja 6.19
Charakterystyka ciała skończonego jest liczbą pierwszą.
Dowód
Dla dowodu nie wprost załóżmy, że charakterystyka pewnego ciała jest liczbą złożoną \( n=pq \). Wtedy
\( 0=(\underbrace{1+\ldots+1}_{n\ razy}) =(\underbrace{1+\ldots+1}_{p\ razy})\cdot(\underbrace{1+\ldots+1}_{q\ razy}). \)
Ponieważ \( p,q < n \) oba czynniki prawej strony ostatniej równości są niezerowe, to są one dzielnikami zera. Sprzeczność z Obserwacją 6.2.
Obserwacja 6.20
Grupa addytywna dowolnego ciała skończonego \( {\bf F}=(F,+,\cdot,0,1) \) jest izomorficzna z \( ({\mathbf {Z}_p})^k \) dla pewnej liczby pierwszej \( p \) i \( k\geq 1 \). Zatem \( \vert=p^k \).
Dowód
Niech \( {\bf F}=(F,+,\cdot,0,1) \) będzie ciałem o charakterystyce \( p \). Z Obserwacji 6.19, \( p \) jest liczbą pierwszą. Niech \( {\bf 2},{\bf 3},\ldots,{\bf p-1}\in F \) będą zadane przez
\( \begin{align*} {\bf 2} & =1+1, \\ {\bf 3} & =1+1+1, \\ & \ldots & \\ {\bf p-1} & =\underbrace{1+\ldots+1}_{p\ razy}. \end{align*} \)
Ponieważ \( 1 \) ma rząd \( p \) w grupie \( (F,+,0) \), to \( {\bf 2},\ldots,{\bf p-1} \) są parami różne. Ponadto zbiór \( ({\{ {0,1,{\bf 2},\ldots,{\bf p-1}} \} },+,\cdot,0,1) \) jest zamknięty na dodawanie i mnożenie. A zatem jest podciałem ciała \( {\bf F} \), i to izomorficznym z ciałem \( \mathbb{Z}_p \).
Samo natomiast ciało \( {\bf F} \) można traktować jako przestrzeń wektorową nad swoim podciałem \( \mathbb{Z}_p \). Zatem, jako taka właśnie przestrzeń wektorowa, \( {\bf F} \) jest izomorficzna z \( \mathbb{Z}_p^k \), gdzie \( k \) jest wymiarem \( {\bf F} \) nad \( \mathbb{Z}_p \). Stąd w szczególności grupa addytywna ciała \( {\bf F} \) jest izomorficzna z produktem \( k \) kopii grupy \( \mathbb{Z}_p \).
Obserwacja 6.21
Grupa multyplikatywna ciała skończonego jest cykliczna.
Dowód
Niech \( (F,+,\cdot,0,1) \) będzie ciałem o \( q \) elementach. Jednym z warunków równoważnych cykliczności grupy multyplikatywnej \( (F^*,\cdot,1) \) jest to, że
Ponieważ rząd elementu grupy dzieli rząd grupy, to
\( f^{q-1}=1\qquad \) dla dowolnego \( f \in F^* \).
To oznacza, że wszystkie elementy \( F^* \) są pierwiastkami wielomianu \( x^{q-1}-1 \). Niech teraz \( d|q-1 \), czyli \( q-1=dk \) dla pewnego \( k \). Łatwo sprawdzić, iż
\( x^{q-1}-1=(x^d-1)(x^{d(k-1)}+x^{d(k-2)}+\ldots+x^d+1). \)
Z Obserwacji 6.18 wielomian \( x^d-1 \) ma co najwyżej \( d \) pierwiastków, a \( x^{d(k-1)}+x^{d(k-2)}+\ldots+x^d+1 \) ma co najwyżej \( d(k-1) \). Jednak ich iloczyn \( x^{q-1}-1 \) ma dokładnie \( q-1 \) pierwiastków, więc oba wielomiany mają odpowiednio \( d \) i \( d(k-1) \) pierwiastków.
Fakt, iż \( x^d-1 \) ma dokładnie \( d \) pierwiastków to dokładnie warunek (*).
Podsumowując nasze rozważania, pokazaliśmy, że:
W tym kontekście nie jest zbyt zaskakujące, iż dowolne dwa ciała \( p^k \)-elementowe okażą się być izomorficzne. W dowodzie Obserwacji 6.20 widzieliśmy, że ciało skończone charakterystyki \( p \) zawiera ciało izomorficzne z \( \mathbb{Z}_p \). Odtąd będziemy więc zakładać, że \( \mathbb{Z}_p \) jest po prostu podciałem takiego ciała.
Dla lepszego zrozumienia grupy i multyplikatywnej ciała przeanalizujemy jeszcze pojęcie pokrewne do pojęcia rzędu elementu \( a \). W ciele skończonym, o \( p^k \) elementach, rząd \( r \) elementu \( a \) dzieli rząd \( p^k-1 \) grupy multyplikatywnej, w szczególności \( {\sf NWD}(p,r)=1 \). Ale również lista
\( a, a^p, a^{p^2}, a^{p^3},\ldots \)
nie może być nieskończona. Wyrazy na niej muszą się powtarzać. Co więcej, \( a^{p^i} = a^{p^j} \) wtedy i tylko wtedy, gdy \( p^i-p^j \) dzieli się przez rząd \( r \) elementu \( a \). Niech więc \( i < j \) czyli \( a^{p^i(p^{j-i} -1)}=1 \). Wtedy \( r \mid p^i(p^{j-i} -1) \) i wobec \( {\sf NWD}(p,r)=1 \) mamy \( p^{j-i} \equiv_r 1 \). Niech \( s \) będzie multyplikatywnym rzędem liczby \( p \) modulo \( r \), tzn najmniejsza taka liczba naturalną \( s \), że \( p^s \equiv_r 1 \). Wtedy mamy
\( a^{p^i} = a^{p^j} \) wtedy i tylko wtedy, gdy \( i \equiv_s j \).
A zatem nasza lista redukuje się do:
\( a, a^p, a^{p^2}, a^{p^3},\ldots, a^{p^{s-1}}. \)
Stopień elementu \( a\neq 0 \) ciała charakterystyki \( p \) to najmniejsza liczba \( d \), dla której \( a^{p^{s}}=a \).
Wniosek 6.22
W skończonym ciele o \( p^k \) elementach, stopień każdego elemetu jest dzielnikiem liczby \( k \).
Obserwacja 6.23
Dla dowolnego ciała \( {\bf F} \) charakterystyki \( p \) oraz \( n\in\mathbb{N} \) mamy:
Dowód
Tak jak w ciele liczb rzeczywistych, można łatwo pokazać, że
\( (a+b)^p = \sum_{i=0}^p {p \choose i}a^ib^{p-i}. \)
To, wraz z faktem, że \( p \) jako liczba pierwsza dzieli wszystkie współczynniki dwumianowe poza \( {p \choose 0} \) i \( {p \choose p} \) oraz, że \( {\bf F} \) ma charakterystykę \( p \), daje \( (a+b)^p = a^p+b^p \). Łatwa indukcja względem \( n \) pokazuje teraz punkt pierwszy.
Dla dowodu punktu drugiego załóżmy, że \( w(x)=\sum_i c_i x^i \). Mamy wtedy \( w(x)^{p^n} = \sum_i c_i^{p^n} x^{ip^n} = \sum_i c_i x^{ip^n} = w(x^{p^n}) \), gdzie równość \( c_i^{p^n} = c_i \) użyta w środkowym przejściu wynika z faktu, że \( c_i\in \mathbb{Z}_p \).
Obserwacja 6.24
Niech \( {\bf F} \) będzie ciałem skończonym charakterystyki \( p \). Wtedy dla dowolnego \( a\in F^* \) istnieje dokładnie jeden unormowany i nierozkładalny wielomian \( w_a(x) \in \mathbb{Z}_p[x] \) taki, że w ciele \( {\bf F} \) zachodzi \( w_a(a)=0 \). Wielomian ten to:
\( w_a(a) = \prod_{i=0}^{d-1} (x-a^{p^i}), \)
gdzie \( d \) jest stopniem elementu \( a \).
Dowód
Wielomian \( w_a \) zdefiniowany w wypowiedzi obserwacji używa współczynników z ciała \( {\bf F} \), które nie muszą być w ciele \( \mathbb{Z}_p \). Aby zobaczyć, że w istocie po wymnożeniu dostajemy współczynniki z \( \mathbb{Z}_p \) niech \( w_a(x)= \sum_{i=0}^{d-1} c_i x^i \). Zauważmy, że zgodnie z Obserwacją 6.23
\( w_a(x)^p = w_a(x^p) = \sum_{i=0}^{d-1} c_i^p x^{ip}. \)
Z drugiej strony fakt, że \( d \) jest stopniem elementu \( a \), czyli równość \( a^{p^d} = a= a^{p^0} \), daje środkowe przejście w ciągu:
\( w_a(x)^p = \prod_{i=0}^{d-1} (x-a^{p^i})^p =\prod_{i=0}^{d-1} (x^p-a^{p^{i+1}}) =\prod_{i=0}^{d-1} (x^p-a^{p^{i}}) =w_a(x^p)=\sum_{i=0}^{d-1} c_i x^{ip} \)
Przyrównując więc teraz współczynniki, dostajemy \( c_i^p=c_i \). Oznacza to, że \( c_0,\ldots,c_{d-1} \in F \) są pierwiastkami wielomianu \( x^p-x \in {\bf F}[x] \). Ponieważ wszystkie elementy z ciała \( \mathbb{Z}_p \subseteq {\bf F} \) są już pierwiastkami tego wielomianu stopnia \( p \), to \( c_0,\ldots,c_{d-1} \) muszą być wśród nich, a zatem \( c_0,\ldots,c_{d-1} \in \mathbb{Z}_p \).
Oczywiście wielomian \( w_a(x) \) jest unormowany. By zobaczyć, że jest nierozkładalny, załóżmy, że \( w_a(x)=p(x)q(x) \). Skoro \( w_a(a)=0 \), to bez straty ogólności możemy założyć, że \( p(a)=0 \). Ale gdyby wielomian \( p(x) \) miał współczynniki w podciele \( \mathbb{Z}_p \), to wobec Obserwacji 6.23 mielibyśmy \( p(a^{p^{d-1}}) = p(a^{p^{d-2}})= \ldots = p(a^{p^2})=p(a^p) = p(a)=0 \), czyli
\( a^{p^{d-1}}, a^{p^{d-2}},\ldots,a^{p^2}, a^p, a \)
byłyby różnymi pierwiastkami wielomianu \( p(x) \), skąd \( {\sf deg}(p(x))=d={\sf deg}(w_a(x)) \) i wielomian \( q(x) \) jest stały.
Pozostaje pokazać, że \( w_a(x) \) jest jedynym wielomianem spełniającym warunki podane w Obserwacji. Niech więc \( v(a) \) będzie takim wielomianem. Wtedy, ponieważ \( v(x) \) ma współczynniki w \( \mathbb{Z}_p \), to wraz z \( a \) również potęgi \( a^p, a^{p^2},\ldots, a^{p^{d-2}}, a^{p^{d-1}} \) są pierwiastkami wielomianu \( v(x) \). To na mocy Twierdzenia Bezout daje, że \( w_a(x) \) dzieli \( v(x) \). Ponieważ jednak \( v(x) \) jest nierozkładalny (nad \( \mathbb{Z}_p \)), to \( v(x) = c \cdot w_a(x) \) dla pewnego \( c\in \mathbb{Z}_p \). Ale skoro obydwa wielomiany \( v(x) \) i \( w_a(x) \) sa unormowane, to \( c=1 \) i \( v(x)=w_a(x) \).
Następne twierdzenie wskaże nam jak konstruować ciała liczności \( p^k \) dla \( k>1 \). Dla niezerowego wielomianu \( q(x) \) nad ciałem \( {\bf F}=(F,+,\cdot,0,1) \) rozważmy dwuargumentową relację \( \sim_{q(x)} \) na zbiorze \( F \) zadaną przez
\( a(x)\sim_{q(x)}b(x) \textrm{ wtedy i tylko wtedy, gdy } q(x)|a(x)-b(x). \)
Łatwo sprawdzić, iż \( \sim_{q(x)} \) jest relacja równoważności zachowującą dodawanie i mnożenie wielomianów. W istocie jest to kongruencja wyznaczona przez ideał główny pierścienia wielomianów \( {\bf F}[x] \) generowany wielomianem \( q(x) \). Zbiór klas równoważności tworzy więc pierścień ilorazowy \( {\bf F}[x]/q(x) \).
Twierdzenie 6.25
Jeśli \( q(x) \) jest nierozkładalnym wielomianem stopnia \( k \) nad ciałem \( \mathbb{Z}_p \), to pierścień ilorazowy \( \mathbb{Z}_p[x]/q(x) \) jest \( p^k \)-elementowym ciałem.
Dowód
Po pierwsze w każdej klasie równoważności relacji \( \sim_{q(x)} \) jest jakiś wielomian stopnia mniejszego niż \( k \). Istotnie, gdy \( p(x)=a(x)\cdot q(x)+r(x) \), gdzie \( r(x) \) jest wielomianem zerowym lub stopnia mniejszego niż \( k \), to \( p(x) \sim_{q(x)} r(x) \). Ponadto, różne wielomiany stopnia mniejszego niż \( k \) nie mogą być \( \sim_{q(x)} \) równoważne. A zatem każda klasa równoważności jest wyznaczona przez dokładnie jeden wielomian stopnia mniejszego niż \( k \). Wielomianów takich jest tyle co wektorów postaci \( (a_{k-1},\ldots,a_0) \), gdzie \( a_i\in\mathbb{Z}_p \). A więc \( \sim_{q(x)} \) ma dokładnie \( p^k \) klas równoważności.
Pozostało sprawdzić, że (przemienny) pierścień ilorazowy jest ciałem, tzn. każdy jego niezerowy element jest odwracalny. W tym miejscu kluczowa jest nierozkładalność wielomianu \( q(x) \).
Niech więc \( a(x) \) będzie niezerowym wielomianem stopnia mniejszego od \( k \). Z nierozkładalności \( q(x) \) wiemy, że \( 1\in\mathbb{Z}_p[x] \) jest największym wspólnym dzielnikiem \( a(x) \) i \( q(x) \). Z Wniosku 6.13 istnieją \( \lambda(x),\mu(x)\in{\bf F}[x] \) takie, że
\( \lambda(x)a(x)+\mu(x)q(x)=1. \)
To oczywiście oznacza, że
\( \lambda(x)a(x) \sim_{q(x)} 1, \)
czyli klasa \( [\lambda]_{q(x)} \) jest odwrotna do \( [a(x)]_{q(x)} \).
Ciało reszt modulo nierozkładalny wielomian \( w(x)\in \mathbb{Z}_p[x] \), to ciało ilorazowe \( \mathbb{Z}_p[x]/q(x) \) opisane w Twierdzeniu 6.25.
Twierdzenie 6.26
Jeśli dwa skończone ciała są równoliczne, to są izomorficzne.
Dowód
Niech ciała \( {\bf F} \) i \( {\bf G} \) mają \( p^k \) elementów. Przez \( a \) oznaczmy generator grupy multyplikatywnej ciała \( {\bf F} \). Wtedy stopień elementu \( a \) wynosi \( k \). Pokażemy, że \( {\{ {1,a,a^2, \ldots, a^{k-1}} \} } \) stanowi bazę dla przestrzeni wektorowej \( {\bf F} \) nad \( \mathbb{Z}_p \). Istotnie, gdyby zbiór ten był liniowo zależny, to \( \sum_{i=0}^{k-1} c_i a^i =0 \) dla pewnych współczynników \( c_i\in\mathbb{Z}_p \). Ale wtedy wielomian \( \sum_{i=0}^{k-1} c_i x^i \) miałby w swoim rozkładzie pewien nierozkładalny i unormowany wielomian \( w'(x) \) stopnia co najwyżej \( k-1 \) taki, że \( w'(a)=0 \). To jednak na mocy Twierdzenia 6.24 nie jest możliwe, bo jedyny taki wielomian w \( \mathbb{Z}_p[x] \) to \( w_a(x) \) stopnia \( k \). Ponieważ liniowo niezależny zbiór \( {\{ {1,a,a^2, \ldots, a^{k-1}} \} } \) ma liczność równa wymiarowi przestrzeni wektorowej \( {\bf F} \) nad \( \mathbb{Z}_p \), to jest jej bazą.
Podobnie, startując od generatora \( b \) grupy multyplikatywnej ciała \( {\bf G} \), dostaniemy bazę \( {\{ {1,b,b^2, \ldots, b^{k-1}} \} } \) przestrzeni wektorowej \( {\bf G} \) nad \( \mathbb{Z}_p \). Teraz łatwo już sprawdzić, że jedyne odwzorowanie liniowe \( F \longrightarrow G \) posyłające \( a^i \) w \( b^i \) jest izomorfizmem nie tylko przestrzeni wektorowych, ale i ciał \( {\bf F} \) i \( {\bf G} \).
Twierdzenie 6.25 pozwala na konstrukcję ciał skończonych o \( p^k \) elementach, gdzie \( p \) jest liczbą pierwszą i \( k>1 \), o ile tylko mamy nierozkładalny wielomian \( k \)-tego stopnia nad \( \mathbb{Z}_p \). Fakt, iż taki wielomian istnieje dla dowolnej liczby pierwszej \( p \) i dowolnego \( k\geq 1 \) jest nietrywialny i jego dowód przeprowadzimy w serii ćwiczeń do tego wykładu.
Twierdzenie 6.27
Dla dowolnej liczby pierwszej \( p \) i \( k\geq1 \) istnieje nierozkładalny wielomian \( k \)-tego stopnia nad ciałem \( \mathbb{Z}_p \).
Wniosek 6.28
Dla dowolnej liczby pierwszej \( p \) i \( k\geq 1 \) istnieje dokładnie jedno, z dokładnością do izomorfizmu, ciało \( p^n \)-elementowe.
Ciało Galois \( {\bf GF}(q) \), gdzie \( q=p^k \) jest potęgą liczby pierwszej, to jedyne z dokładnością do izomorfizmu ciało \( q \)-elementowe.
Przykład
Opiszemy ciała \( {\bf GF}(4) \) i \( {\bf GF}(9) \).
W jednym z poprzednich przykładów widzieliśmy, iż jest tylko jeden taki wielomian:
\( x^2+x+1. \)
\( \begin{array} {c|cccc} + & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end{array} \)
\( \begin{array} {c|cccc} \cdot & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end{array} \)
zatem rzeczywiście wielomian \( x^2+2x+2 \) jest nierozkładalny nad \( \mathbb{Z}_3 \).
Kryptografia jest dziedziną informatyki, zajmującą się zagadnieniami bezpieczeństwa informacji. W szczególności kryptografia traktuje o: kodowaniu/dekodowaniu, autoryzacji, kontroli dostępu. W drugiej połowie XX wieku kryptografia całkowicie zmieniła swoje oblicze, głównie dzięki stworzeniu kryptosystemów o publicznym kluczu. Obecnie jest to dziedzina, w której znajduje zastosowanie wiele rozważań z teorii informacji, złożoności obliczeniowej, statystyki, kombinatoryki i, na co zwracamy uwagę, z teorii liczb.
W tym wykładzie przedstawiamy, bardzo pobieżnie, model matematyczny kodowania/dekodowania wiadomości. Później opisujemy dwa kryptosystemy: Cezara (bardziej jako przykład dydaktyczny) oraz RSA. W drugiej części wykładu poznamy algorytmy sprawdzające czy liczba jest pierwsza.
Rozważamy zagadnienie kryptograficzne polegające na przesłaniu wiadomości, od nadawcy do obiorcy, w taki sposób, by żadna trzecia (przypadkowa) osoba nie była w stanie jej odczytać.
Tekst jawny to ciąg symboli (znaków) w pewnym języku (np. w polskim). Wiadomość zakodowana, czyli szyfrogram, to także ciąg symboli. Podczas naszych rozważań zakładamy, iż szyfrogram jest ciągiem nad tym samym alfabetem co tekst jawny. Przed zakodowaniem nadawca dzieli tekst jawny na tzw. jednostki. Jednostką tekstu jawnego może być pojedynczy symbol, dwójka symboli, itp.. Dopiero jednostkę tekstu jawnego poddaje się procesowi kodowania otrzymując jednostkę szyfrogramu. Kolejne jednostki szyfrogramu mogą być niezależnie wysyłane od nadawcy do odbiorcy. Odbiorca poddaje otrzymany szyfrogram procesowi dekodowania dostając jednostkę tekstu jawnego.
Funkcja kodująca \( f \) to permutacja
\( f:\mathcal{J}\longrightarrow\mathcal{J}, \)
gdzie \( \mathcal{J} \) to zbiór wszystkich, możliwych jednostek tekstu jawnego i szyfrogramu (w skrócie jednostki wiadomości).
Funkcja dekodująca jest permutacją odwrotną do funkcji kodującej. Oznaczamy ją przez \( f^{-1} \), gdzie \( f \) jest odpowiednią funkcją kodującą.
Funkcja kodująca/dekodująca zależy zazwyczaj od parametrów, zwanych kluczami. Przyjmuje się, iż funkcja kodująca (jej wzór, bądź algorytm ją realizujący) jest ogólnie dostępna. Zachowane w tajemnicy są jedynie klucze.
Kryptosystem to para \( (\mathcal{J},f) \), czyli zbiór jednostek wiadomości \( \mathcal{J} \) i funkcja kodująca \( f \).
Pierwszym krokiem do określenia kryptosystemu jest poetykietowanie jednostek wiadomości pewnymi obiektami matematycznymi, na których będzie można określić funkcję kodującą (permutację). W naszych rozważaniach zawsze będą to kolejne liczby naturalne, jednak w ogólności rozważa się w tym miejscu także wektory bądź np. krzywe eliptyczne czy obecnie nawet już hipereliptyczne.
Przykład
Rozważmy alfabet jako zbiór cyfr, polskich liter oraz dodatkowych kilku znaków interpunkcyjnych.
Poetykietujmy symbole alfabetu kolejnymi liczbami naturalnymi.
\( \begin{array} {rrrrrrrrrrrrrrrr} A & Ą & B & C & Ć & D & E & Ę & F & G & H & I & J & K & L & Ł \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline M & N & Ń & O & Ó & P & R & S & Ś & T & U & W & Y & Z & Ż & Ź \\ 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\ \hline & . & ? & ! & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 \end{array} \)
Niech jednostki wiadomości zawierają tylko jeden symbol. Wtedy zbiór jednostek wiadomości to \( \mathbb{Z}_{46}={\{ {0,\ldots,45} \} } \). Podzielmy tekst 'MATEMATYKA DYSKRETNA 2' na jednostki wiadomości. Na podstawie tabeli powyżej kolejne jednostki to:
\( 16,0,25,6,16,0,25,28,13,0,32,5,28,23,13,22,6,25,17,0,32,38. \)
Rozważmy teraz jednostki wiadomości zawierające dwie litery. Wtedy łatwo policzyć, że mamy \( 46\cdot46=2116 \) możliwych jednostek. Ponumerujmy je w sposób naturalny: jednostka \( xy \) otrzymuje numer
\( 46x+y\in{\{ {0,\ldots,2115} \} }. \)
Zatem zbiór jednostek wiadomości to \( \mathbb{Z}_{2116}={\{ {0,\ldots,2115} \} } \). Jak teraz wyglądają jednostki wiadomości 'MATEMATYKA DYSKRETNA 2'?
\( \begin{align*} \textrm{MA} & \equiv & 16\cdot46+0=736, \\ \textrm{TE} & \equiv & 25\cdot46+6=1156, \\ & \ldots & \end{align*} \)
To przykład bardzo prostego systemu kryptograficznego. Są poszlaki świadczące o tym, że Juliusz Cezar używał tej metody do porozumiewania się ze swoimi generałami.
Funkcja kodująca jest tu oparta na dodawaniu modulo rozmiar \( \vert\mathcal{J}\vert \) zbioru jednostek wiadomości:
\( f(P)=(P+b) {\sf mod} \vert \mathcal{J}\vert . \)
Parametr \( b\in{\{ {0,\ldots,\vert\mathcal{J}\vert-1} \} } \) (choć wartość \( 0 \) jest niepraktyczna :)) jest kluczem, który powinien pozostać tajny. Odbiorca otrzymując szyfrogram \( C \) dekoduje go następująco:
\( f^{-1}(C)=(C-b) \ {\sf mod} \vert \mathcal{J}\vert . \)
Zauważmy, że ten sam parametr \( b \) jest kluczem funkcji dekodującej.
Przykład
Zakodujmy w kryptosystemie Cezara wiadomość: `FARSALOS'. Przyjmijmy, iż jednostki wiadomości zawierają jeden symbol. Wtedy, zgodnie z tabelą, numeryczny odpowiednik naszej wiadomości to:
\( 8,0,22,23,0,14,19,23. \)
Jeśli klucz funkcji (de)kodującej to \( b=33 \), to szyfrogram składa się z następujących jednostek:
\( 41,33,9,10,33,1,6,10, \)
czyli `5.GH.EA' jest treścią szyfrogramu.
Wyobraźmy sobie, iż nie jesteśmy nadawcą ani odbiorcą wiadomości, lecz osobą trzecią, bardzo zainteresowaną treścią przesyłanej wiadomości. Jak już wcześniej wspomnieliśmy zakładamy, iż wiadomo jaki kryptosystem jest użyty (w szczególności jaki jest zbiór jednostek wiadomości). Nieznane są jedynie klucze funkcji (de)kodującej.
Kryptoanaliza to dział kryptografii badający możliwość dekodowania wiadomości bez znajomości kluczy użytego kryptosystemu. W ogólności badane są tu też możliwości zamiany wiadomości, fałszowania podpisów, itp..
Załóżmy, iż przechwyciliśmy wiadomość zakodowaną w poprzednim przykładzie. Ponieważ istnieje tylko \( 46 \) możliwych wartości klucza, możemy szybko sprawdzić każdą ewentualność i prawie na pewno tylko w jednym przypadku zdekodowana wiadomość będzie miała sens. Widzimy więc, iż złamanie tego szyfru jest dziecinnie proste.
Jak poprawić bezpieczeństwo kryptosystemu Cezara? Można powiększyć zbiór jednostek wiadomości poprzez zwiększenie liczby symboli alfabetu w jednej jednostce. Wtedy automatycznie będzie więcej możliwych wartości klucza i trudniej będzie je wszystkie przeglądnąć.
Rozwiązanie to jest jednak podatne na tzw. analizę częstotliwości. Wróćmy na chwilę do jednostek wiadomości zawierających jeden symbol. W każdym języku naturalnym pewne symbole występują częściej, np. w języku polskim najczęściej używamy liter: A, E, I, itp. Gdy w przechwyconej wiadomości pewien symbol powtarza się częściej, możemy podejrzewać, iż reprezentuje on jedną z wymienionych liter. W przypadku gdy jednostki wiadomości zawierają więcej symboli analizujemy częstotliwość występowania odpowiednio długich zbitek liter. Jest to skuteczna metoda o ile mamy wystarczająco dużą próbkę zakodowanego tekstu.
Przykład
Przyjmijmy, iż przechwyciliśmy zakodowaną wiadomość: '5.GH.EA' (z poprzedniego przykładu). Wiedząc, iż zakodowana jest ona w kryptosytemie Cezara z jednostką informacji zawierającą pojedynczy symbol dokonując analizy częstotliwości symboli możemy zgadywać, iż symbol '.' (wartość \( 33 \)) reprezentuje symbol o dużej częstotliowści. Zgadując, iż jest to 'A' (wartość \( 0 \)) mamy
\( f('A')='5',\ \textrm{czyli}\ f(0)=0+b {\sf mod} 45 =33,\ \textrm{czyli}\ b=33. \)
Zatem bez sprawdzania wszystkich możliwych wartości udało nam się poznać wartość klucza, a co za tym idzie treść wiadomości
To nieznaczne udoskonalenie kryptosystemu Cezara. Funkcja kodująca jest tym razem, tzw. funkcją afiniczną na zbiorze \( \mathbb{Z}_{\vert J \vert} \), czyli
\( f(P)=a\cdot P+b {\sf mod} \vert\mathcal{J}\vert , \)
gdzie \( a,b\in\mathbb{Z}_{\vert\mathcal{J}\vert} \) są kluczami \( f \) i co bardzo ważne \( a\perp\vert\mathcal{J}\vert \) (dlaczego?). Sprawdźmy, iż po zakodowaniu i zdekodowaniu wrócimy do tego samego elementu
\( \begin{align*} f^{-1}(f(P)) & =f^{-1}(a\cdot P+b {\sf mod} \vert\mathcal{J}\vert ) \\ & =a^{-1}(a\cdot P+b {\sf mod} \vert\mathcal{J}\vert )+a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =a^{-1}(a\cdot P+b)-a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =P+a^{-1}b-a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =P {\sf mod} \vert\mathcal{J}\vert . \end{align*} \)
Pozostawiamy czytelnikowi wypracowanie szybkiego sposobu"złamania" tego kryptosystemu.
Klucz kodowania - \( K_K \) to parametr(y) funkcji kodującej. Znając je można wysyłać zakodowane wiadomości.
Klucz dekodowania - \( K_D \) to paramert(y) funkcji dekodującej. Znając je można dekodować wiadomości.
Przez wieki uważano, że w dowolnym kryptosystemie znajomość klucza kodujacego \( K_K \) pozwala na szybkie poznanie klucza dekodującego znajomość \( K_D \), czyli że każdy kto umie kodować wiadomości może je też dekodować. Tak jest w rozważanym powyżej kryptosystemie Cezara. Jeśli Cezar używał tego samego kryptosystemu do kontaktu ze wszystkimi swoimi generałami, wtedy mogło dochodzić do sytuacji niepożądanych np. gdy generał A wysłał Cezarowi zaszyfrowaną wiadomość, generał B przechwytując kuriera po drodze mógł ją odczytać.
Kryptosystem z kluczem publicznym to system \( (\mathcal{J},f,K_K, K_D) \), gdzie \( K_K \) i \( K_D \) są odpowiednio kluczem kodującym i dekodującym, w którym
Szukamy więc funkcji \( f \) którą w jedną stronę liczy się relatywnie szybko na podstawie znajomości \( K_K \). Natomiast jej odwrotna \( f^{-1} \) jest bardzo trudna do policzenia bez dodatkowej informacji \( K_D \). W sposób naturalny przychodzi tu na myśl problem znajdowania rozkładu na czynniki pierwsze liczb naturalnych. W szczególności: wymnożenie dwu dużych liczb pierwszych jest łatwe (można to zrobić w czasie wielomianowym od długości ich zapisu), natomiast szybkie znalezienie rozkładu na czynniki pierwsze ich iloczynu (bez znajomości wyjściowych liczb lub innych dodatkowych informacji) wydaje się być problemem ekstremalnie trudnym. Właśnie na tym spostrzeżeniu oparta jest idea kryptosystemu RSA.
Nazwa kryptosystemu pochodzi od pierwszych liter nazwisk jego trzech pomysłodawców: Rivest, Shamir i Adelman. Choć jest to jeden z najstarszych kryptosystemów z kluczem publicznym (wynaleziony w 1977 roku) wciąż jest szeroko stosowany w komercyjnych protokołach. Jedynie długości kluczy rosną wraz ze wzrostem mocy obliczeniowej komputerów.
Uwaga: jest to oczekiwany czas działania, a nie maksymalny (pesymistyczny).
Poprawność tego kryptosystemu, czyli że \( f^{-1}(f(P))=P \), dla dowolnego \( P\in\mathbb{Z}_n \) wynika bezpośrednio z następującej obserwacji:
Obserwacja 7.1 [Poprawność RSA]
\( P^{ed}\ \equiv_{n}1 ,\qquad \) dla dowolnego \( P \in \mathbb{Z}_n \).
Dowód
Ponieważ \( ed\ \equiv_{\varphi(n)}1 \) mamy \( ed=a\varphi(n)+1 \) dla pewnego \( a \).
Załóżmy najpierw, ze \( p\perp n \). Wtedy z Twierdzenia Eulera dostajemy \( P^{\varphi(n)}\ \equiv_{n}1 \), a zatem \( P^{ed}=P^{a\varphi(n)+1}\equiv_n P \).
Jeśli zaś \( p\not\perp n \), to \( p|P \) lub \( q|P \). Załóżmy, bez straty ogólności, że \( q|P \), czyli \( P=bq \) dla pewnego \( 0 < b < p \), bo \( bq=P < n=pq \). Na mocy Małego Twierdzenia Fermata mamy:
\( \begin{align*} b^{p-1} & \equiv_p & 1, \\ q^{p-1} & \equiv_p & 1, \end{align*} \)
skąd:
\( \begin{align*} b^{a(p-1)(q-1)} & \equiv_p & 1, \\ q^{a(p-1)(q-1)} & \equiv_p & 1, \end{align*} \)
i dalej
\( \begin{align*} b\cdot(bq)^{a(p-1)(q-1)} & \equiv_p & b \cdot 1 = b. \end{align*} \)
Mnożąc obie strony ostatniej kongruencji przez \( q \) dostajemy
\( \begin{align*} bq\cdot(bq)^{a(p-1)(q-1)} & \equiv_{pq} & bq \end{align*} \)
czyli
\( P^{ed} = (bq)^{a(p-1)(q-1)+1}= (bq)\cdot (bq)^{a(p-1)(q-1)} \equiv_n bq = P, \)
co było do udowodnienia.
Bezpieczeństwo kryptosystemu RSA opiera się na domniemaniu trudności następującego problemu:
Szybkie rozwiązanie problemu faktoryzacji rozwiązałoby problem RSA. Gdyby ktoś znał rozkład \( n \), to znaczy liczby \( p \) i \( q \), miałby także \( \varphi(n)=(p-1)(q-1) \). Wtedy, korzystając z publicznie dostępnego \( e \), obliczyłby rozszerzonym algorytmem Euklidesa \( d \). Dopóki nie jest znany efektywny algorytm rozwiązujący jeden z tych problemów (problem RSA, problem faktoryzacji) kryptosystem RSA pozostaje bezpieczny. Wzrastająca szybkość komputerów zmusza użytkowników RSA do zwiększania długości kluczy. Obecnie stosowane klucze mają najczęściej \( 1024 \) lub \( 2048 \) bitów. Największy złamany klucz (klucz dla którego znaleziono rozkład) ma długość \( 663 \) bity (stan z roku 2005).
W praktyce wiadomość przed zakodowaniem podlega wstępnej obróbce (padding). Zauważmy, że wartości \( 0 \) i \( 1 \) nie podlegają zmianie przy kodowaniu (z własności potęgowania), przez co stanowią one część informacji czytelnej dla wszystkich nawet w szyfrogramie. W praktyce różnymi metodami unika się takich wartości. Rozważania te już jednak wykraczają poza tematykę tego wykładu.
Przykład
Widzieliśmy, że znając rozkład \( n= pq \) można łatwo obliczyć \( \varphi(n) \), a tym samym klucz \( d \) odpowiadający publicznemu kluczowi \( e \). Na odwrót, znając \( n \) oraz \( \varphi(n) \) można szybko rozłozyć liczbę \( n \) na czynniki pierwsze:
a zatem mamy rozwiązać układ równań postaci:
\( \begin{align*} x \cdot y & = a \\ x + y & = 2b \end{align*} \)
skąd \( x,y \) wynoszą \( b \pm \sqrt{b^2-a} \).
Pokazuje to, że wartości funkcji Eulera sa równie trudne do policzenia, jak faktoryzacja liczb.
Uwaga
Kryptosystem RSA wykorzystywany jest poza szyfrowaniem również w wielu innych protokołach kryptograficznych. Na bazie tego systemu można na przykład zbudować podpis elektroniczny. Mimo, że zagadnienia te wykraczają już znacznie poza treść tego wykładu, pokazują one jak wielką rolę odgrywa obecnie teoria liczb w informatyce.
We współczesnej kryptografii w wielu sytuacjach wymagana jest duża losowa liczba pierwsza. Omówiony właśnie kryptosystem RSA jest takim przykładem.
Test pierwszości to algorytm determinujący, czy liczba podana na wejściu jest pierwsza. Wszystkie testy pierwszości szukają, tak naprawdę, świadka na złożoność liczby. Jeśli go nie znajdą odpowiadają, że liczba jest pierwsza. Powszechnie rozważane są dwa rodzaje testów pierwszości:
Jest istotna różnica pomiędzy stwierdzeniem, że liczba jest złożona (poprzez brak zaliczenia testu pierwszości), a wskazaniem jej rozkładu (faktoryzacją). W szczególności istnieje efektywny (wielomianowy) algorytm testujący pierwszość natomiast dotychczas poznane algorytmy faktoryzujące są o wiele wolniejsze.
To najprostszy deterministyczny test pierwszości. Daną na wejściu liczbę \( n \) wydziela kolejno przez \( m=2,3,\ldots,\lfloor \sqrt{m}\rfloor \). Jeśli przy którymkolwiek dzieleniu reszta równa jest \( 0 \) test zwraca, że \( n \) jest złożona w przeciwnym wypadku, że \( n \) jest pierwsza. Zwróćmy uwagę, że jeśli \( n \) okaże się złożona, to znajdziemy także nietrywialny jej dzielnik. Niestety jest to bardzo wolna metoda sprawdzania pierwszości - wymaga \( O(\sqrt{n}\lg^2{n}) \) kroków.
Probabilistyczne testy pierwszości działają według następującego schematu:
Małe Twierdzenia Fermata mówi, że jeśli \( n \) jest pierwsza, to dla dowolnego \( b\in{\{ {1,2,\ldots,n-1} \} } \) zachodzi
\( b^{n-1}\ \equiv_{n}1 . \)
Powyższe zdanie może być prawdziwe dla pewnych złożonych \( n \) i pewnych \( 1 < b < n \). Jeśli jednak dla danego \( n \) i pewnego \( 1 < b < n-1 \), tożsamość \( b^{n-1}\ \equiv_{n}1 \) nie zachodzi, to \( n \) jest złożona i \( b \) jest świadkiem złożoności.
Liczba pseudopierwsza przy podstawie \( b \) to złożona liczba nieparzysta \( n \) taka, że:
Przykład
Liczba \( 91=7\cdot13 \) jest pseudopierwsza przy podstawie \( 3 \).
Zatem \( 3^{90}\ \equiv_{91}1 \), czyli \( 91 \) jest pseudopierwsze przy podstawie \( 3 \).
Sprawdźmy, czy \( 91 \) jest również pseudopierwsze przy podstawie \( 2 \).
Zatem \( 2^{90}\not\equiv_{91}1 \). Gdybyśmy nie wiedzieli, że \( 91 \) jest złożona, byłby to dowód tego faktu (\( 2 \) jest świadkiem złożoności \( 91 \)).
Zauważmy, że dla dowolnego \( n \), wszystkie podstawy pseudopierwszości \( n \) znajdują się w grupie \( \mathbb{Z}_n^{*}=(\mathbb{Z}_n^{*},\cdot,1) \) elementów odwracalnych względem mnożenia modulo \( n \), bo \( bb^{n-2}\equiv_n 1 \) oznacza, że \( b^{n-2}= b^{-1} \). W szczególności podstawy takie są względnie pierwsze z \( n \).
Obserwacja 7.2
Dla złożonej nieparzystej liczby \( n \) zachodzi:
wtedy i tylko wtedy, gdy rząd \( b \) w \( \mathbb{Z}_n^{*} \) (tzn. najmniejsza, dodatnie \( k \) takie, że \( b^k\equiv_n 1 \)) dzieli \( n-1 \),
Dowód
Dla dowodu punktu pierwszego niech \( k \) będzie rzędem \( b \) w \( \mathbb{Z}_n^* \) oraz \( n-1=q\cdot k+r \), gdzie \( 0\leq r < k \). Wtedy
\( 1\equiv_n b^{n-1}\equiv_n b^{qk+r}\equiv_nb^{qk}b^r\equiv_nb^r. \)
Zatem \( b^r\equiv_n 1 \), ale ponieważ \( r < k \) i \( k \) jest najmniejszą dodatnią liczbą spełniającą \( x^k\equiv_n1 \) to \( r=0 \) i \( k|n-1 \).
Dla dowodu drugiego punktu załóżmy, że \( n \) jest pseudopierwsze przy obu podstawach \( b_1 \) oraz \( b_2 \), czyli \( b_1^{n-1}\ \equiv_{n}1 \) i \( b_2^{n-1}\ \equiv_{n}1 \). Po pomnożeniu tych kongruencji otrzymujemy \( (b_1b_2)^{n-1}\equiv_n1 \), czyli \( n \) jest pseudopierwsze przy podstawie \( b_1b_2 \). Mnożąc zaś \( b_1^{n-1}\equiv_n b_2^{n-1} \) przez \( (b_2^{-1})^{n-1} \) otrzymujemy \( (b_1b_2^{-1})^{n-1}\equiv_n1 \), co było do pokazania.
Wreszcie, załóżmy, że \( {\{ {b_1,\ldots,b_m} \} } \) to zbiór wszystkich podstaw, przy których \( n \) jest pseudopierwsze i \( 1 < b_i < n \). Niech \( b \) będzie świadkiem złożoności \( n \). Wtedy \( bb_i \) nie może być podstawą pseudopierwszości \( n \). Rzeczywiście, gdyby było, to drugi punkt dawałby, że \( bb_ib_i^{-1}=b \) też musiałoby być. Sprzeczność. A zatem mamy przynajmniej \( m \) różnych świadków pierwszości \( bb_1,\ldots,bb_m \), co było do pokazania.
Na podstawie ostatnich rozważań opiszemy probabilistyczny test pierwszości, znany jako test pierwszości Fermata. Mając daną na wejściu liczbę \( n \):
Jeśli nie, to \( n \) jest złożona i \( b \) jest świadkiem złożoności \( n \). Jeśli tak, to \( n \) przechodzi test.
Załóżmy, że wykonaliśmy \( k \) powtórzeń. Wtedy zgodnie z Obserwacją 7.2 szansa na to, że \( n \) nie ma świadka złożoności wynosi \( \frac{1}{2^k} \). To jednak nie oznacza, że z taką szansą \( n \) jest pierwsza. Okazuje się, że istnieją liczby które nie mają świadka złożoności, a mimo to są złożone.
Liczba Carmichaela to liczba złożona, która nie ma świadków złożoności. Zatem liczba \( n \) jest liczbą Carmichaela jeśli
\( b^{n-1}\equiv_n 1. \)
Oto lista kilku pierwszych liczb Carmichaela:
\( 561,1105,1729,2465,2821,6601,8911,\ldots. \)
Liczbami o tych właściwościach zajmował się już Korselt pod koniec XIX wieku. Co ciekawe nie wiedział on czy takie liczby w ogóle istnieją. Niemniej podał on następującą ich charakteryzację.
Twierdzenie 7.3 [Korselt 1899]
Liczba złożona \( n \) jest liczbą Carmichaela wtedy i tylko wtedy, gdy \( n \) nie jest podzielna przez żaden kwadrat liczby pierwszej i dla wszystkich dzielników pierwszych \( p \) liczby \( n \) zachodzi \( p-1|n-1 \).
Dowód
Załóżmy najpierw, że \( p^2|n \) dla pewnej liczby pierwszej \( p \). Ponieważ elementy odwracalne w \( (\mathbb{Z}_{p^2}, \cdot) \) to dokładnie względnie pierwsze z \( p^2 \), więc grupa \( \mathbb{Z}_{p^2}^{*} \) ma \( \varphi(p^2)=p(p-1) \) elementów. Gdy \( p=2 \) to grupa ta ma \( 2 \) elementy więc jest cykliczna. Niech więc \( g \) będzie jej generatorem, tzn. jedynym elementem rożnym od \( 1 \). Dla \( p\neq 2 \) niech \( g=p-1 \). Ponieważ
\( g^p = (p-1)^p = \sum_{i=0}^p {p \choose i}p^i (-1)^{p-i} \)
i wszystkie składniki poza \( i=0,1 \) są podzielne przez \( p^2 \), to
\( g^p = 1 + {p \choose 1}(-1)^{p-1} = 1+p^2 \equiv_{p^2} =1. \)
Oznacza to, że \( g \) jest odracalnym elementem \( \mathbb{Z}_{p^2}^{*} \) i wobec \( g \neq 1 \) rząd \( g \) wynosi \( p \).
Niech \( n' \) będzie iloczynem wszystkich liczb pierwszych dzielących \( n \) poza samą liczbą \( p \). Wtedy, oczywiście \( {\sf NWD}(p^2,n')=1 \) i z Chińskiego Twierdzenia o Resztach wiemy, iż istnieje \( b \) takie, że
\( \begin{align*} b & \equiv_{p^2} & g, \\ b & \equiv_{n'} & 1. \end{align*} \)
W szczególności
\( {\sf NWD}(b,n)=1, \)
gdyż \( p \) nie dzieli \( b \) (jako, że \( b\equiv_{p^2}g \) a \( g \) leżąc w \( \mathbb{Z}_{p^2}^{*} \) nie może być wielokrotnością \( p \)) i żadna inna liczba pierwsza z rozkładu \( n \) nie dzieli \( p \), bo \( b\equiv_{n'}1 \). Ponieważ \( n \) jest liczbą Carmichaela, to \( b^{n-1}\equiv_n1 \). A zatem \( g^{n-1}\equiv_{p^2}b^{n-1}\equiv_{p^2}1 \). Ale ponieważ \( g \) ma rząd \( p \) w grupie \( \mathbb{Z}_{p^2}^{*} \), to \( p|n-1 \), co stoi w sprzeczności z \( p|n \). Udowodniliśmy zatem, że liczby Carmichaela rozkładają się na iloczyn różnych liczb pierwszych.
Niech teraz \( p|n \) i \( p-1∤ n-1 \). Ponieważ \( p^2∤ n \), to \( p \) i \( \frac{n}{p} \) są względnie pierwsze. Grupa \( \mathbb{Z}_p^* \) jest grupą multyplikatywną ciała \( {\bf GF}(p) \), więc jest cykliczna. Niech \( g \) będzie jej generatorem. Znów, z Chińskiego Twierdzenia o Resztach, mamy \( b \) takie, że
\( \begin{align*} b & \equiv_{p} & g, \\ b & \equiv_{\frac{n}{p}} & 1. \end{align*} \)
Oczywiście \( {\sf NWD}(b,n)=1 \). Ponieważ \( n \) jest liczbą Carmichaela, to wtedy \( b^{n-1}\equiv_n1 \). Ale \( b^{n-1}\equiv_pg^{n-1}\not\equiv_p1 \), gdyż \( g \) ma rząd \( p-1 \), a \( p-1∤ n-1 \).
Na odwrót, niech \( n \) będzie iloczynem różnych liczb pierwszych \( p \), i to takich, że \( p-1|n-1 \). Chcemy pokazać, że dowolne \( b\perp n \) jest podstawą pseudopierwszości dla \( n \). Zauważmy, że \( b^{n-1} \) jest potęgą liczby \( b^{p-1} \), a Twierdzenie Fermata daje \( b^{p-1}\equiv_p 1 \). To oznacza, że \( b^{n-1}\equiv_p 1 \) dla wszystkich liczb pierwszych \( p|n \). Ponieważ \( n \) nie dzieli się przez kwadrat żadnej liczby pierwszej, to \( b^{n-1}\equiv_n 1 \).
Wniosek 7.4
Liczba Carmichaela jest iloczynem przynajmniej trzech różnych liczb pierwszych.
Dowód
Opierając się na Twierdzeniu 7.3 wystarczy pokazać, że jeśli \( n=pq \) dla różnych liczb pierwszych \( p,q \), to \( n \) nie jest liczbą Carmichaela. Bez straty ogólności przyjmijmy, iż \( p < q \). Gdyby \( n \) była liczbą Carmichaela to \( q-1|n-1 \) ale \( n-1=p(q-1)+p-1\equiv_{q-1}p-1 \). Sprzeczność.
Przykład
Liczba \( 561 \) jest liczbą Carmichaela ponieważ
Jak dużo jest liczb Carmichaela? Pierwszą taką liczbę wskazał Robert Carmichael w 1910 i była to liczba \( 561 \). Liczby Carmichaela okazują się bardzo rzadkie. W przedziale \( [1,\ldots,10^7] \) jest ich jedynie \( 585 355 \), czyli średnio jedna liczba Carmichaela na 170 bilionów liczb naturalnych. Dopiero w 1994 udowodniono, że jest ich nieskończenie wiele.
Podsumujmy naszą wiedzę o probabilistycznym teście Fermata. Poddając \( k \) krotnie liczbę \( n \) temu testowi:
Test Millera-Rabina bazuje na koncepcji silnej pseudopierwszości, którą zdefiniujemy poniżej. Niech \( n \) będzie pseudopierwsza przy podstawie \( b \), czyli \( b^{n-1}\equiv_n1 \). Zauważmy, że jeśli \( n \) jest pierwsza, to w ciągu
\( b^{(n-1)/2} {\sf mod} n ,\quad b^{(n-1)/4} {\sf mod} n , \quad \ldots \quad b^{(n-1)/2^s} {\sf mod} n , \)
gdzie \( s \) jest tak dobrane że \( (n-1)/2^s \) jest nieparzysta, pierwsza wartość modulo \( n \) różna od \( 1 \) to \( -1 \). Wynika to z następującej obserwacji.
Obserwacja 7.5
Dla dowolnej liczby pierwszej \( p \) jeśli \( x^2\equiv_p 1 \), to \( x\equiv_p \pm1 \).
Dowód
Załóżmy, ze \( x^2\equiv_p1 \). Wtedy \( (x-1)(x+1)\equiv_p 0 \), czyli \( p|(x-1)(x+1) \). Ponieważ \( p \) jest pierwsza, to musi ona dzielić jedną z liczb \( x-1 \) lub \( x+1 \). To jest z kolei równoważne z \( x\equiv_p1 \) lub \( x\equiv_p-1 \).
W praktyce ciąg ten analizowany jest z drugiej strony. Niech \( n-1=2^st \), gdzie \( t \) jest nieparzysta. Najpierw obliczamy \( b^t {\sf mod} n \) później (jeśli otrzymaliśmy coś różnego jest od \( 1 \)) obliczamy \( b^{2t} {\sf mod} n \), później \( b^{4t} {\sf mod} n \), aż otrzymamy wartość \( 1 \). Wtedy jeśli poprzednia wartość jest różna od \( -1 \), to \( n \) jest złożona.
Niech \( n \) będzie nieparzystą liczbą złożoną i niech \( n-1=2^st \), gdzie \( t \) jest nieparzysta, \( b\in{\{ {1,2,\ldots,n-1} \} } \). Jeśli
to \( n \) jest silnie pseudopierwsza przy podstawie \( b \).
Oczywiście, wprost z definicji, każda liczba silnie pseudopierwsza przy podstawie \( b \) jest też pseudopierwsza przy podstawie \( b \).
Sformułujemy najpierw algorytm testu, a później udowodnimy, że - po kilku powtórzeniach - z bardzo dużym prawdopodobieństwem odróżni on liczbę pierwszą od złożonej. Test ten nie ma żadnych wyjątków typu liczby Carmichaela w teście Fermata!
Dla danej na wejściu liczby nieparzystej \( n \) algorytm działa następująco:
\( b^{2t} {\sf mod} n ,2^{2^2t} {\sf mod} n ,2^{2^3t} {\sf mod} n ,\ldots,2^{2^{s-1}t} \ {\sf mod} n , \)
aż otrzymasz \( -1 \). Jeśli uzyskałeś \( -1 \), to \( n \) przechodzi test. Jeśli zaś \( -1 \) nie wystąpiło w obliczonym ciągu, to \( n \) jest złożona i \( b \) jest świadkiem złożoności. Zatem wykonanych będzie co najwyżej \( O(\lg{n}) \) kroków i w każdym kroku przeprowadzamy szybkie potęgowanie w \( O(\lg^3{n}) \), czyli sumaryczny czas to \( O(\lg^4{n}) \).
W praktyce licząc kolejne wyrazy \( b^{2t} {\sf mod} n ,2^{2^2t} {\sf mod} n ,2^{2^3t} {\sf mod} n ,\ldots \) jeśli otrzymamy na którymś miejscu \( 1 \) (a wcześniej nie było \( -1 \)), to możemy przerwać test i zwrócić, że \( n \) jest złożona (gdyż pozostałe wyrazy ciągu pozostaną równe \( 1 \)).
Przykład
Wykonajmy test Millera-Rabina dla \( n=561 \) (jest to najmniejsza liczba Carmichaela, nieodróżnialna od liczb pierwszych testem Fermata):
Wykład ten zakończymy podaniem twierdzenia (bez dowodu), uzasadniajacego, że jeśli liczba nieparzysta \( n \) przeszła \( k \) testów Millera-Rabina to liczba \( n \) jest złożona z prawdopodobieństwem jedynie \( \frac{1}{4^k} \). A więc po \( 10 \) testach Millera-Rabina \( n \) jest złożona z prawdopodobieństwem \( 0.0000009 \).
Twierdzenie 7.6
Jeśli \( n \) jest nieparzystą liczbą złożoną, to \( n \) jest silnie pseudopierwsze dla co najwyżej \( 25\% \) liczb \( b\in{\{ {1,\ldots,n-1} \} } \).
W praktyce okazuje się, że prawie we wszystkich wypadkach wystarczy kilka testów Millera-Rabina. Na przykład policzono, że jest tylko jedna złożona liczba nieparzysta mniejsza od \( 2.5\cdot10^{10} \), konkretnie 3215031751, która jest silnie pseudopierwsza dla podstaw \( 2,3,5 \) i \( 7 \). Mimo to matematycy wciąż szukają szybkich deterministycznych testów pierwszości. Niedawno, w roku 2002, Agrawal, Kayal i Saxena pokazali pierwszy, efektywny \( O(\lg^{12}{n}) \) deterministyczny test pierwszości. Po pewnych przeróbkach algorytm ten działa w czasie \( O(\lg^6{n}) \)). Jednak w praktyce algorytm ten jest dużo wolniejszy od szybkich testów probabilistycznych. Z drugiej strony, jeśli prawdziwa jest Uogólniona Hipoteza Riemanna, to każda nieparzysta, złożona liczba \( n \) ma świadka złożoności \( b \) w teście Millera-Rabina takiego, że \( 0 < b < 2\log^2{n} \). To oznaczałoby, że test Millera-Rabina jest testem deterministycznym i to działającym bardzo szybko.
W pewnych sytuacjach łatwiejsze do uzyskania, ale słabsze oszacowanie zastosowane w odpowiedni sposób może prowadzić do lepszego końcowego szacowania zachowania asymptotycznego. Poznamy tę metodę w kilku kolejnych przykładach.
Przykład
Dla ciągu zadanego przez
\( \displaystyle \begin{align*} a_0 & =1, \\ a_{n+1} & =\frac{1}{n^3}\sum_{i=0}^{n-1}a_i, \end{align*} \)
najpierw dowodzimy indukcyjnie, że \( \displaystyle 0 < a_n\leq 1 \), czyli \( \displaystyle a_n=O(1) \). Podstawiając uzyskane oszacowanie do równania rekurencyjnego otrzymujemy:
\( \displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^{n}a_i=\frac{1}{n^3}\cdot \sum_{i=0}^n O(1)=\frac{1}{n^3}\cdot O( \sum_{i=0}^n1 )=\frac{1}{n^3}\cdot O(n)=O( \frac{1}{n^2} ). \)
Operację tę możemy powtórzyć uzyskując jeszcze lepsze oszacowanie
\( \displaystyle \begin{align*} a_n & =\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}( a_0+\sum_{i=1}^na_i )=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^{n}O( \frac{1}{n^2} )= \frac{1}{n^3}+\frac{1}{n^3}O(1) \\ & =O( \frac{1}{n^3} ). \end{align*} \)
Wykorzystaliśmy tu fakt, iż szereg \( \displaystyle \sum_{i=0}^{\infty}\frac{1}{i^2} \) jest zbieżny. Zauważmy też, że następne powtórzenie podobnej procedury szacującej już nam nic nie da.
\( \displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^nO( \frac{1}{n^3} )=\frac{1}{n^3}+\frac{1}{n^3}\cdot O( \frac{1}{n^2} )=O( \frac{1}{n^3} ). \)
Przykład
Niech ciąg \( \displaystyle b_n \) spełnia
\( \displaystyle b_n\cdot\ln{b_n}=n. \)
Z monotoniczności funkcji \( \displaystyle n\ln{n} \) dostajemy, że \( \displaystyle 0 < b_n < n \). Podstawiając to oszacowanie za drugie wystąpienie \( \displaystyle b_n \) w równaniu otrzymujemy:
\( \displaystyle n=b_n\cdot\ln{b_n} < b_n\ln{n}, \)
czyli \( \displaystyle b_n>\frac{n}{\ln{n}} \). Podstawiając powtórnie dostajemy:
\( \displaystyle n=b_n\ln{b_n}>b_n\cdot\ln{\frac{n}{\ln{n}}}, \)
czyli \( \displaystyle b_n < \frac{n}{\ln{n}-\ln{\ln{n}}} \). Uzyskaliśmy zatem, że \( \displaystyle b_n=\Theta( \frac{n}{\ln{n}} ) \).
Na zakończenie tego wykładu poznamy jeszcze jeden symbol asymptotyczny. Jest on podobny do \( \displaystyle \Theta \) lecz znacznie precyzyjniejszy.
Funkcje asymptotycznie równe to takie funkcje \( \displaystyle f(n) \) i \( \displaystyle g(n) \), że
\( \displaystyle \lim_{narrow\infty}\frac{f(n)}{g(n)}=1. \)
Fakt, że funkcje \( \displaystyle f(n) \) i \( \displaystyle g(n) \) są asymptotycznie równe zapisujemy jako \( \displaystyle f(n)\sim g(n) \).
Jednym z najbardziej znanych przybliżeń asymptotycznych jest tzw. Wzór Stirlinga przybliżający zachowanie silni.
Twierdzenie 9.5 [wzór Stirlinga]
\( \displaystyle n!\sim \sqrt{2\pi n}( \frac{n}{e} )^n. \)
Wzór ten został odkryty przez Abrahama de Moivre w postaci
\( \displaystyle n!\sim c \cdot n^{n+1/2} e^{-n}, \)
dla pewnej stałej \( \displaystyle c \). Wkładem Jamesa Stirlinga było pokazanie, że stałą tą jest \( \displaystyle c=\sqrt{2\pi} \). Dowód tego oszacowania wykracza poza metody tego kursu. W oszacowaniach przez nierówności przydatna jest następująca wersja wzoru Stirlinga:
\( \displaystyle \sqrt{2\pi n}( \frac{n}{e} )^ne^{-(12n+1)}\leq n!\leq \sqrt{2\pi n}( \frac{n}{e} )^{n}e^{-12n} \)
Innym ważnym przybliżeniem asymptotycznym jest wzór na liczbę podziałów liczby naturalnej \( \displaystyle n \) na sumy dodatnich liczb naturalnych, tzn. asymptotyczne przybliżenie funkcji \( \displaystyle p_n = \sum_{k=1}^n P(n,k) \) .
Twierdzenie 9.6
\( \displaystyle p_n \sim \frac{e^{\pi\sqrt{\frac{2n}{3}}}}{4n\sqrt{3}} \)
Podamy też asymptotyczne przybliżenie na liczbę liczb pierwszych nie większych niż \( \displaystyle n \).
Twierdzenie 9.7
Jeśli \( \displaystyle \pi(n) \) oznacza liczbę liczb pierwszych w zbiorze \( \displaystyle \lbrace 1,2,3,\ldots,n \rbrace \), to
\( \displaystyle \pi(n) \sim \frac{n}{\ln n} \)
Zadanie 1
Wierzchołki grafu permutacji $G_n$ są etykietowane permutacjami zbioru $n$-elementowego. Dwa wierzchołki w tym grafie są połączone krawędzią, jeśli odpowiadające im permutacje różnią się transpozycją sąsiednich elementów. Dla jakich $n$ graf $G_n$ jest planarny?
Zadanie 2
Pokaż nieplanarność grafu Petersena
(a) z tw. Kuratowskiego (zawiera podgraf homeomorf. z K3,3 lub K5);
(b) wyprowadzając ograniczenie górne na liczbę krawędzi dla grafów planarnych o obwodzie r.
Zadanie 3
Dla jakich k hiperkostka Qk jest planarna? Dla jakich r,s,t pełny graf trojdzielny Kr,s,t jest planarny?
Zadanie 4
Pokaż, że jeśli G ma co najmniej 11 wierzchołków, to G i dopełnienie G nie mogą być jednocześnie planarne. Podaj przykład 8-wierzchołkowego G takiego, że G i dopełnienie G są planarne.
Zadanie 5
Ile co najwyżej krawędzi może mieć n-wierzchołkowy graf zewnętrznie planarny? Pokaż, że każdy graf zewnętrznie planarny można pokolorować 3 kolorami.
Zadanie 6
Udowodnij "twierdzenie o 7 barwach" dla torusa:
a) K7 można narysować na torusie => czasem trzeba użyć 7 kolorów.
b) odpowiednik wzoru Eulera: n-m+f=0
c) odpowiednik m<=3n-6: m<=3n
d) odpowiednik faktu o istnieniu wierzchołka stopnia <=5: istnieje wierzchołek stopnia <=6
e) 7 kolorow zawsze wystarczy.
Zadanie 7
Graf Knesera K(r,n): V = {r-podzbiory {1..n}}
{A,B} jest krawędzia <=> część wspólna A i B jest pusta (Np. K(2,5) -
graf Petersena). Pokaż, ze χ(K(2,5))=3, χ(K(2,6))=4, ogólnie
χ(K(r,n))<=n-2r+2.
Zadanie 8
Graf Mycielskiego Mn: M2 = krawędź, Mk+1: do Mk dokładamy kopię M' samych wierzchołków z Mk. Każdy wierzchołek-kopia w M' jest połączony z sąsiadami swojego oryginału w Mk. Dokładamy jeszcze nowy wierzchołek połączony ze wszystkimi w M'. Pokaż, że
a) w Mk nie ma trójkątów
b) χ(M_k)=k.
Zadanie 9
Udowodnij tw. Koniga: kolorowanie krawędziowe grafu dwudzielnego o maksymalnym stopniu D wymaga tylko D kolorow.
Zadanie 10
Znajdź wielomian chromatyczny cyklu Cn, "koła o n szprychach", grafu K3,3.
Udowodnij, że każdy prostokąt łaciński można rozszerzyć do kwadratu.
Do kwadratu n x n wpisano po n liczb 1, 2,..., k (łącznie kn liczb) w taki sposób, że w żadnym wierszu ani kolumnie nie ma dwóch takich samych liczb. Udowodnij, że można uzupełnić ten kwadrat do kwadratu łacińskiego (tzn. w każdym wierszu i w każdej kolumnie zawierającego permutację liczb 1,...,n).
Pokaż, że jeśli w grafie dwudzielnym (V1, V2) stopnie wierzchołków w V1 są ≥ niż stopnie wierzchołków w V2, to istnieje pełne skojarzenie z V1 do V2.
Udowodnij, że jeśli w grafie dwudzielnym (V1, V2) jest spełniony warunek Halla i stopień każdego wierzchołka w V1 jest ≥ t, to pełne skojarzenie z V1 do V2 można wybrać na co najmniej t! sposobów, jeśli t≤|V1| i na co najmniej t!/(t-|V1|)! sposobów jeśli t>|V1|.
Problem haremu: jak wygląda warunek Halla w przypadku, kiedy i-ty chłopiec chce poślubić di dziewcząt?
Udowodnij, że przeliczalna rodzina zbiorów skończonych ma System Różnych Reprezentantów wtedy i tylko wtedy, gdy dla każdego naturalnego k dowolnych k zbiorów z tej rodziny zawiera w sumie co najmniej k elementów. Pokaż, że założenie o skończoności zbiorów jest istotne.
Pokaż, że jeśli n>2, to w sieci komutacyjnej Closa każdą permutację można zrealizować na przynajmniej dwa sposoby. Zaoprojektuj optymalny algorytm ustawiania przełączników.
Udowodnij, że iloczyn k kolejnych liczb całkowitych jest podzielny przez k!.
Udowodnij, że jeśli liczba 2n-1 jest pierwsza, to liczba n jest pierwsza.
Udowodnij, że jeśli liczba 2n+1 jest pierwsza, to n jest potęgą 2. Niech fn = 22n+1 oznacza n-tą liczbę Fermata. Uprość iloczyn f0...fn i udowodnij, że każde dwie różne liczby Fermata są względnie pierwsze.
Udowodnij, że
(a) NWD(na-1, nb-1) = nNWD(a,b)-1;
(b) NWD(Fa, Fb) = FNWD(a,b), gdzie Fn to n-ta liczba Fibonacciego.
Ile rozwiązań ma kongruencja ax ≡ b (mod n) w zbiorze {0,...,n-1}. Jak je efektywnie znajdować?
Udowodnij twierdzenie Wilsona: liczba n jest pierwsza <=> (n-1)! ≡ -1 (mod n).
Oto konstrukcja drzewa Sterna-Brocota:
zaczynamy od dwóch ułamków: 0⁄1 i 1⁄0 (ten drugi reprezentuje +∞)
między każde dwa kolejne elementy m⁄n i m'⁄n' wstawiamy ułamek (m+m')/(n+n').
Udowodnij, że w ten sposób uzyskamy wszystkie dodatnie ułamki nieskracalne, każdy dokładnie raz.
Udowodnij, że iloczyn trzech kolejnych liczb naturalnych, z których środkowa jest sześcianem, dzieli się przez 504.
Niech n = 100. Czy φ(n) to najmniejsza liczba λ o tej własności, że jeśli a⊥n, to aλ≡1(mod n)? Uogólnij tę obserwację.
Udowodnij, że istnieje 2011 kolejnych liczb naturalnych, z których każda jest podzielna przez sześcian liczby naturalnej >1.
Niech F(1) = 2, F(k+1) = 2F(k). Oblicz F(5) mod 2009.
Znajdź najmniejszą liczbę o sumie cyfr 204 podzielną przez 204.
Znajdź konstruktywny dowód chińskiego twierdzenia o resztach (czyli podaj efektywny algorytm znajdowania elementu spełniającego stosowny układ kongruencji).
W kryptosystemie RSA: niech p = 11, q = 29, klucz jawny e = 3. Znajdź klucz tajny d, zaszyfruj komunikat M = 100, a następnie zdeszyfruj go z powrotem.
Znajdź wszystkie rozwiązania kongruencji
x2≡1 (mod 784)
x2≡-1 (mod 4225)
10x≡8 (mod 17)
Wiedząc, że n = 3598057 jest iloczynem dwóch różnych liczb pierwszych oraz że 20779 jest pierwiastkiem z 1 modulo n, znajdź rozkład n na czynniki pierwsze.
Uogólnij chińskie twierdzenie o resztach na przypadek, kiedy moduły niekoniecznie są względnie pierwsze.
Rozważmy system kryptograficzny RSA z modułem n = 71⋅103 i wykładnikiem publicznym e=19. Oblicz, ile komunikatów M∈{0,...,n-1} jest punktami stałymi szyfrowania, tzn. spełnia warunek S(M) = M.
Iloczynem kartezjańskim grafów \(G_1 = \langle V_1, E_1\rangle\) i \(G_2 = \langle V_2, E_2\rangle\) nazywamy graf \(G_1\otimes G_2 = \langle V_1\times V_2, E\rangle\), gdzie
\[\{\langle v_1,v_2\rangle,\langle w_1,w_2\rangle\} \in E \Leftrightarrow (\{v_1,w_1\} \in E_1 \wedge \{v_2,w_2\} \in E_2)\ .\]
Udowodnij, że graf \(G_1\otimes G_2\) jest spójny wtedy i tylko wtedy, gdy obydwa grafy \(G_1\) i \(G_2\) są spójne i przynajmniej jeden z nich zawiera cykl nieparzystej długości.
Oblicz \(7^{8^9} \bmod 100\).
Udowodnij uogólnione Chińskie Twierdzenie o Resztach: Niech \(m_1,m_2>0\) niekoniecznie względnie pierwsze, \(m = \mbox{NWW}(m_1,m_2)\). Wtedy dla dowolnych \(u_1,u_2\geq 0\) istnieje dokładnie jedno u takie, że \( 0\leq u < m\) oraz \(u \equiv u_i (\mbox{mod } m_i)\) dla i=1,2, o ile \(u_1\equiv u_2 (\mbox{mod NWD}(m_1, m_2))\), a jeśli ten ostatni warunek nie jest spełniony, to takie u nie istnieje.
Znajdź minimalny zbiór generatorów grupy Sn.
Opisz wszystkie grupy rzędów 1,...,7.
Udowodnij, że grupa A4 nie zawiera podgrupy rzędu 6.
Rozstrzygnij, czy grupa S4 zawiera podgrupę
(a) Z2⊕Z3
(b) Z2⊕Z4
Podaj liczbę elementów każdego rzędu w grupie Z4⊕Z10.
Znajdź rząd podgrupy Sn generowanej przez n-cykle.
Rozstrzygnij, czy
(a) grupa obrotów sześcianu jest izomorficzna z S4 (grupą wszystkich permutacji zbioru 4-elementowego);
(b) grupa izometrii sześcianu jest izomorficzna z grupą automorfizmów grafu złożonego z 4 trójkątów A, B, C, D takich, że B, C, D sa rozłączne, zaś A ma dokładnie jeden wierzchołek wspólny z każdym z nich.
Niech P(G,k,j) oznacza liczbę istotnie różnych kolorowań grafu $G$, w których dokładnie $k$ wierzchołków jest białych, a $j = |V|-k$ wierzchołków jest czarnych. Dla grafu G niech S(G) oznacza stożek nad G, czyli graf powstający z G przez dodanie nowego wierzchołka połączonego ze wszystkimi w G.
Pokaż, że jeśli
(*) G nie ma wierzchołka stopnia |V(G)|-1,
to P(S(G),k,j) = P(G,k-1,j)+P(G,k,j-1), i podaj przykład pokazujacy, że założenie (*) jest istotne.
Podaj przykład grafu, którego grupą automorfizmów jest
(a) Z2 + Z2 (grupa czwórkowa Kleina); (b) Z3.
Podaj przykład grafu G o nietrywialnej grupie automorfizmów i takiego, że po usunięciu z G dowolnej krawędzi otrzymujemy graf o trywialnej grupie automorfizmów.
Wariant uproszczony:
słowo dowolnej zastąp przez pewnej.
Oblicz, ile jest nieizomorficznych turniejów o 5 wierzchołkach.
Kolorujemy wierzchołki czworościanu foremnego z użyciem 3 kolorów, a krawędzie z użyciem 2 kolorów. Oblicz, na ile istotnie różnych sposobów można to zrobić, jeśli utożsamiamy takie kolorowania, że jedno przechodzi na drugie przy pewnym obrocie czworościanu w R3.
Podaj przykład funkcji f takiej, że f(n) = ω((log n)a) oraz f(n) = o(nb) dla dowolnych a,b>0.
Pokaż, że jeśli b>1, T,S - niemalejące, T(bk) = Θ(S(bk)) i dodatkowo S spełnia warunek
S(bn) = Θ(S(n))
to T(n) = Θ(S(n)).
Sprawdź, czy ten warunek jest spełniony dla (a) S(n) = na; (b) S(n) = an.
Niech n oznacza łączną liczbę włosów na głowach wszystkich ludzi żyjących obecnie na Ziemi. Rozstrzygnij, co jest większe: długość zapisu dziesiętnego liczby 2n czy liczba końcowych zer w zapisie dziesiętnym liczby n!.
Niech f(n) będzie rozwiązaniem równania funkcyjnego x log1001x = n. Znajdź rząd wielkości funkcji f.
Znajdź rząd wielkości funkcji f(n) określonej zależnością \(f(n)^{f(n)^{f(n)}} = n\) dla \(n>0\).
Oszacuj sumę \(\sum_{n\geq 1} 1/n^3\) z błędem bezwzględnym 1/12.
Oszacuj sumę \(\frac{1}{n^2+1}+\frac{2}{n^2+2}+\cdots+\frac{n}{n^2+n}\) z błędem bezwzględnym \(O(1/n^2)\).
Oszacuj sumę \[\sum_{i=1}^n \frac{\mbox{lg }i}{\sqrt{i}}\] z błędem bezwzględnym \(O(1)\).
(a) Udowodnij, że \(|\{\langle a,b \rangle \in \mathbb{N}\times\mathbb{N}: a^2+b^2\le n\}| = \frac{\pi}{4}n +O(\sqrt{n})\).
(b) Oszacuj \(|\{\langle a,b,c \rangle \in \mathbb{N}^3: a^2+b^2+c^3\le n\}|\) z błędem bezwzględnym \(O(n)\).
Oblicz sumę \(\displaystyle\sum_k {{n}\choose{2k}} 2^{n-2k}\).
Oblicz, na ile sposobów można rozstawić n nieatakujących się wież na planszy
(a) \(\{(i,j): 1\leq i,j\leq n\mbox{ oraz }j\geq i-1\}\);
(b) \(\{(i,j): 1\leq i,j\leq n\mbox{ oraz }|i-j|\leq 1\}\).
Udowodnij, że każdy spójny, regularny graf dwudzielny jest dwuspójny. Podaj przykład pokazujący, że założenie o dwudzielności jest istotne.
Znajdź najmniejszą wielokrotność liczby 130013, której zapis w systemie dziesiątkowym składa się z samych dziewiątek.
Z ośmiu sześcianów o krawędzi 1, z których trzy mają po jednej ścianie czarnej i po pięć białych, a pozostałe mają wszystkie ściany białe, sklejamy sześcian o boku 2. Oblicz, na ile sposobów można to zrobić, jeśli dwa sposoby sklejenia utożsamiamy, gdy jeden z uzyskanych sześcianów o boku 2 przechodzi na drugi przy pewnym obrocie sześcianu w \(\mathbb{R}^3\) (zakładamy, że ścianki są nieprzezroczyste, więc wnętrze sześcianu jest niewidoczne).