Podstawy teorii grup i jej zastosowania

Prowadzący

Joachim Jelisiejew (Yogi)

Opis

Teoria grup skończonych jest bardzo naturalnym rozwinięciem teorii liczb, choć jest bardziej wypasiona i jej zastosowania można streścić jako: "grupy są wszędzie". Jest to też dział algebry, co znaczy, że będziemy poruszać się po gruncie skończonym i dużo intuicji z liczb całkowitych przeniesie się, tylko w nieco zmienionej ("prostszej" — uwaga to nie moje zdanie, ale zdanie uczestnika mojego wykładu z algebry :) formie.

Na warsztatach udowodnię podstawowe twierdzenia tej teorii, ale przede wszystkim skupię się na szeroko rozumianych zastosowaniach.

Jak widać poniżej, jest dużo możliwych kierunków rozwoju warsztatów. Uważam, że po próbce, jaką będzie pierwszy dzień, przegłosujemy wspólnie dalszy program. Nie należy sądzić, że zamierzam w 9h przerobić wszystkie niżej wymienione punkty, gdyż wtedy (prawdopodobnie) właściwsze byłoby określenie przemielić. Wybierając te zajęcia można wziąć pod uwagę, że mógłbym przyspieszyć prawie nieograniczenie, ale nie zrobię tego, chyba, że jakiś uczestnik będzie chciał mieć dużo zadanek domowych, ale nawet wtedy nie będzie to przyspieszenie dla wszystkich.

Program zajęć

Zadania domowe: oswojenie z definicją grupy pewne naturalne własności grup i trochę przykładów (zresztą zobaczycie niedługo).

Pierwszy dzień:

  • przypomnienie materiału z zadań domowych,
  • polemika: "Do czego nam grupy?",
  • porządne przeliczenie przykładów,
  • twierdzenie Lagrange i jego zastosowania w teorii liczb: małe twierdzenie Fermata, twierdzenie Lagrange, lemat o rzędzie,
  • zadania z poziomu OM związane z powyższą teorią,
  • głosowanie na temat linii partii w dalszych dniach.

Możliwości rozwoju:

  1. Rozwinięcie zastosowań w teorii liczb — m. in. zadania olimpijskie dotyczące reszt z dzielenia itp. Ilość takich zadań jest praktycznie nieograniczona ;) Teoria grup nie jest tutaj bezpośrednim narzędziem, ale moim subiektywnym zdaniem odmienia spojrzenie na takie problemy.
  2. Trochę teorii z bezpośrednim zastosowaniem — istnienie tzw. pierwiastka pierwotnego $\mod p$, gdzie liczba $p$ jest pierwsza, czyli takiej liczby $g$, że reszty z dzielenia przez $p$ liczb ze zbioru $g,g^2,...,g^{p-1}$ są parami różne. Na OM cieszy się to niesłabnącym uznaniem np. zadanie 5. na tegorocznym finale.
  3. Działanie grupy na zbiorze — relatywnie nowe (pierwsze próby u Galois) spojrzenie na teorię grup, dzięki któremu jest ona dzisiaj ważna, a nawet była (wg. Kleina) kandydatem na opis całej matematyki. Co dziwniejsze, ten dział ma także dużo zastosowań np. w zliczaniu. Co jeszcze dziwniejsze nie jest to żadna wielka teoria — pomysł staje się naturalny, jeżeli popatrzy się wystarczająco długo, a definicji i formalizmów nie ma dużo.
  4. [zależne od działania grupy na zbiorze] Coś entuzjastów ładnych wyników i osób mających do czynienia z algebrą — zabawimy się w abstrakcyjne myślenie o grupach i udowodnimy (jeśli ktoś nie wie o co chodzi, proszę się nie bać) prostotę grupy $A_n$ dla $n\geq 5$ bez brzydkich rachunków z którymi zwykle ma się do czynienia przy tym dowodzie.
  5. Możemy też, no cóż … iść klasycznie, poudowadniać twierdzenia nauczane na zwykłym wykładzie z algebry i powiedzieć, że one mają zastosowania. Tak, możemy… Ten punkt będzie zrealizowany tylko jeżeli uczestnicy naprawdę będą chcieli. A zamieszczam go, bo może jednak ktoś zechce.

Wymagania

Najwięcej radości ten wykład może dać osobom, które uważały, że $n|a-b \quad n|c-d \Rightarrow n|ac - bd$ jest ciekawym faktem.
A bardziej serio: naprawdę potrzebne będzie porządne zrobienie zadań domowych, gdyż jedna jedyna definicja — definicja grupy — jest kluczowa. Obycie z prostą teorią liczb (np. fakt, że ktoś widział kiedyś małe twierdzenie Fermata) jest również bardzo ważne.

Zadania kwalifikacyjne

Definicja grupy:

Zbiór $G$ z określonym działaniem $\ast$ nazywamy grupą jeżeli

  1. Dla wszystkich $a,b\in G$ jest $a\ast b\in G$,
  2. Dla wszystkich $a,b,c\in G$ jest $(a\ast b)\ast c =a\ast (b\ast c)$ — kolejność wykonywania działań nie ma znaczenia.
  3. Istnieje “jedynka” — element neutralny działania, innymi słowy istnieje pewne $e\in G$ takie, że $\forall x\in G\ \ x\ast e = x \wedge e\ast x = x$
  4. Dla każdego elementu $a\in G$ istnieje taki element $b\in G$, że $a\ast b = e \wedge b\ast a = e$. (przypominam: $e$ to element neutralny grupy).

Zadania:

  1. Z naszej definicji grupy wynika, że grupa ma co najmniej jeden element neutralny. Udowodnij, że grupa ma dokładnie jeden element neutralny tj., jeżeli $e,f$ są elementami neutralnymi grupy to $e=f$
  2. Udowodnij, że każdy element grupy ma dokładnie jedną odwrotność tj. jeżeli $b,c$ są takie, że $ab=ac=e,ba=ca=e$, to $b=c$
  3. Rozstrzygnij, czy liczby rzeczywiste z dodawaniem, liczby rzeczywiste z mnożeniem, liczby całkowite z mnożeniem tworzą grupy?
  4. Uzasadnij, że funkcje ze zbioru $\{1,2,...,n\}$ w $\{1,2,...,n\}$ które są różnowartościowe i na (tj. przyjmują każdą możliwą wartość) z działaniem "składanie funkcji" tworzą grupę.
  5. Niech$p$ będzie liczbą pierwszą. Uzasadnij, że $\{1,...,p-1\}$ z działaniem $a\ast b =$ reszta z dzielenia $ab$ przez $p$ tworzą grupę. Czy założenie, że liczba jest pierwsza jest potrzebne?

Zadania należy przesyłać na maila, będę wysyłać maila zwrotnego z informacją nt. wyników (w miarę szybko) oraz umieszczać informację na aplikacji warsztatowej. Można wysyłać zadania kilkakrotnie. Próg kwalifikacji to 4 zadania zrobione na 5 — jest on dość wysoki, ale zadania są proste. Zadania będą oceniane punktacją 0,2,5,6. Wszelkie pytania dot. zadań można również wysyłać na maila.
Uwaga: Zadania należy wysyłać w załączniku w formacie pdf lub w treści maila. Do przerabiania plików doc (i nie tylko) na pdfy polecam Bullzip printera.

Literatura

Z zamiarem nie podaję literatury — zadania przygotowawcze są na tyle podstawowe, że w każdej literaturze znajdziecie je na początku, a więcej zabawy (i zrozumienia) jest ze zrobienia ich samodzielnie. Każdy, kto wyśle mi zadania może poprosić o literaturę i ją otrzyma.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License