Prowadzący
Marcin Kotowski
Michał Kotowski
Opis
Nowość: Poświęcony hipotezie Kakeyi artykuł z "Delty" (nr 04/2013)
Dostępny jest skrypt z zajęć.
Wyobraźmy sobie igłę jednostkowej długości, którą chcemy obrócić wewnątrz pewnego zbioru o 360 stopni. Jak dużo potrzebujemy do tego miejsca? Nietrudno zauważyć, że najprostsze rozwiązanie - koło o promieniu 1/2 - nie jest optymalne (ćwiczenie - znajdź zbiór o mniejszym polu niż ww. koło, w którym można obrócić igłę). Każdy taki zbiór musi zawierać odcinek wzdłuż każdej prostej - taki zbiór nazwiemy zbiorem Kakeyi. Okazuje się - co nie jest oczywiste - że istnieją zbiory o tej własności mające dowolnie małe pole (a nawet - objętość zero!). Hipoteza Kakeyi - bardzo istotny problem otwarty zahaczający o wiele dziedzin współczesnej matematyki - pyta o wymiar (tzw. wymiar Minkowskiego lub wymiar Hausdorffa) zbiorów Kakeyi w przestrzeni n-wymiarowej.
Ciało to obiekt algebraiczny, w którym można dodawać, odejmować, mnożyć i dzielić - przykładem ciał są np. liczby wymierne i rzeczywiste, a mniej oczywistym - $\mathbb{Z}_p$ (zbiór liczb $\{1,\dots,p\}$ z działaniami modulo p). To ostatnie ciało zawiera skończenie wiele elementów, czyli jest ciałem skończonym. Okazuje się, że hipoteza Kakeyi posiada naturalny analog dla ciał skończonych, który został udowodniony w 2009 roku z użyciem bardzo elementarnej (zrozumiałej niemal na poziomie licealnym!) i eleganckiej techniki.
Dowód hipotezy Kakeyi dla ciał skończonych będzie dla nas pretekstem do zaprezentowania związków kombinatoryki i algebry ciał skończonych. Zobaczymy, że metody oparte o wielomiany nad ciałami skończonymi znajdują szerokie zastosowanie w problemach kombinatorycznych - od kodów poprawiających błędy przez informatykę teoretyczną (ekstraktory losowości) po trudne zadania "olimpijskie". Zajęcia będą dość elementarne, ale dotkną też "poważnych" działów matematyki (tzw. kombinatoryka addytywna).
Program zajęć
W zależności od możliwości czasowych poruszymy wybór następujących zagadnień:
- hipoteza Kakeya dla ciał skończonych (i może coś w $\mathbb{R}^n$)
- kody poprawiające błędy nad ciałami skończonymi: kod Reeda-Solomona
- inne metody kombinatoryczno-algebraiczne: combinatorial Nullstellensatz i jego pochodne wraz z zastosowaniami
- zastosowania w informatyce: ekstrakcja losowości
- desery: coś więcej o geometrii kombinatorycznej, incydencjach etc.
Wymagania
- podstawowe obycie w kombinatoryce i algebrze (wielomiany)
- bardzo elementarna wiedza dotycząca ciał i algebry liniowej (będzie wprowadzona w zadaniach kwalifikacyjnych)
Zadania kwalifikacyjne
Skrypt zawierający podstawy teorii ciał i algebry liniowej, autorstwa Piotrka Suwary i Pawła Siedleckiego, znajduje się tu: Skrypt. Będziemy z niego potrzebować rzeczy z sekcji 1 oraz 3. Jest on dość formalny i materiału o algebrze liniowej jest sporo, ale nie należy się tym przejmować, chodzi głównie o obeznanie się z i zrozumienie podstawowych definicji w stopniu wystarczającym do zrobienie poniższych zadań. W szczególności, nie trzeba czytać wszystkich dowodów, chodzi raczej o zrozumienie podstawowych pojęć, jak baza, macierz, przekształcenie liniowe itp., na tyle, by umieć się nimi posługiwać.
Jest też dostępna ściągawka o pierścieniach ilorazowych (do zadania 1).
Zasady oceniania:
- rozwiązania należy przysyłać na adres: moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim
- zrobienie zadań wymaga przyswojenia sobie kawałka teorii o ciałach i algebrze liniowej; w razie problemów ze zrozumieniem bardzo zachęcamy do konsultacji, zadawania pytań itp. (te rzeczy mogą być trudne tylko dlatego, że są nowe, a nie dlatego, że są naprawdę trudne ;))
- w razie niejasności, wątpliwości itd. co do treści zadań - piszcie, a pojawią się dodatkowe wyjaśnienia
- zadania 1-3 są obowiązkowe; zadania o wyższych numerach należy rozwiązać w ilości $\geq 1$ (w przypadku dużej liczby chętnych o kwalifikacji zadecyduje łączna liczba poprawnie zrobionych zadań)
- można wysyłać częściowe rozwiązania; rozwiązania przysłane odpowiednio wcześnie (nie dzień przed terminem lub, co gorsza, dzień po) będą ocenione i można będzie nadesłać poprawki
Zadania obowiązkowe
Zadanie 1
a) Które z poniższych zbiorów (z naturalnymi działaniami) są ciałami, a które nie (sprawdź tylko te aksjomaty, które nie są od razu oczywiste):
- $\mathbb{N}$ (liczby naturalne)
- $\mathbb{Z}$ (liczby całkowite)
- $\mathbb{Q}$ (liczby wymierne)
- $\mathbb{Q_{+}}$ (liczby wymierne dodatnie)
- $\mathbb{R}$ (liczby rzeczywiste)
- $\mathbb{Z_2}$ (zbiór {0,1} z dodawaniem modulo 2)
- $\mathbb{Z_3}$ (analogicznie j.w.)
- $\mathbb{Z_4}$ (analogicznie j.w.)
Uogólnij ostatnie trzy przykłady.
b) Dla $p$ - liczby pierwszej, pokaż wielomian o współczynnikach z $\mathbb{Z}_p$, który nie ma żadnych pierwiastków w $\mathbb{Z}_p$ (wskazówka - co możesz powiedzieć o wielkości $a^p$?).
c) Rozpatrzmy wielomian $f(x)=x^2-x-1$ nad $\mathbb{Z}_2$. Niech $F=\mathbb{Z}_2[x]/ (f)$ będzie pierścieniem ilorazowym modulo $f$ (patrz ściągawka). Pokaż, że każdy element $F$ można reprezentować wielomianem nad $\mathbb{Z}_2[x]$ stopnia co najwyżej $1$. Ile elementów ma $F$? Pokaż, że $F$ jest ciałem i wypisz tabelkę mnożenia dla $F$.
d*) (podpunkt "z gwiazdką", nieco trudniejszy) Uogólnij konstrukcję z poprzedniego podpunktu,zastępując $\mathbb{Z}_2$ przez $\mathbb{Z}_p$, gdzie $p \neq 2$. (w razie problemów z szukaniem odwrotności w $\mathbb{Z}_p[x]/ (f)$ - przypomnieć sobie algorytm Euklidesa w formnie $ax+by=NWD(a,b)$, on działa też dla wielomianów; w ostateczności zostawić na później)
e) Czy nad każdym ciałem skończonym może istnieć wielomian o nie wszystkich współczynnikach zerowych zerujący się na każdym elemencie tego ciała? Pokaż, że dla każdego ciała skończonego $\mathbb{F}$ istnieje wielomian, który nie ma żadnych pierwiastków w $\mathbb{F}$.
Zadanie 2
a) Niech $A$ będzie macierzą $n \times k$ nad $\mathbb{Z}_2$ i niech $C \subseteq \mathbb{Z}_2^n$ będzie zbiorem wszystkich wektorów postaci $Ax$ dla $x \in \mathbb{Z}_2^k$. Pokaż, że $C$ jest podprzestrzenią liniową $\mathbb{Z}_2^n$.
b) Niech $C^{\perp}$ oznacza przestrzeń prostopadłą do $C$, tzn. zbiór wszystkich $y \in \mathbb{Z}_2^n$ takich, że dla każdego $x \in C$ $\langle y,x \rangle=0$, gdzie $\langle y,x \rangle = \sum_{i=1}^{n}x_i y_i$. Jak opisać $C^{\perp}$ z użyciem jakiejś macierzy? Czy może się zdarzyć, że $C \cap C^{\perp} \neq \{0\}$?
c) Niech $V$ będzie przestrzenią liniową rozpiętą przez skończenie wiele wielomianów nad dowolnym ciałem $\mathbb{F}$ (np. możemy myśleć o $\mathbb{F}=\mathbb{R}$). Dla $x \in \mathbb{F}$ niech $val_{x}: V \rightarrow \mathbb{F}$ oznacza ewaluację w punkcie $x$, tzn. $val_{x}(P)=P(x)$. Pokaż, że $val_{x}$ jest odwzorowaniem liniowym.
d) Niech $X$ będzie zbiorem punktów $x_1, \dots, x_n \in \mathbb{F}$. Analogicznie jak poprzednio, niech $val_{X}: V \rightarrow \mathbb{F}^n$ oznacza ewaluację w punktach z $X$ (tj. przeprowadza $P$ w wektor wartości $\{P(x_i)\}_{i=1}^{n}$). To też jest odwzorowanie liniowe. Pokaż, że jeśli $\mathrm{dim}V > n$, to istnieje niezerowy wielomian $P \in V$, który zeruje się we wszystkich punktach $x_i$.
Zadanie 3
a) Kodem poprawiającym błędy nad $\mathbb{Z}_{p}$ nazwiemy dowolny podzbiór $C \subseteq \mathbb{Z}_{p}^{n}$. Dla dowolnych dwóch elementów $x,y \in C$ ich odległością Hamminga $d(x,y)$ nazywamy liczbę pozycji, na których się różnią (gdzie każdy element traktujemy jako ciąg $n$ wyrazów z $\mathbb{Z}_{p}$). Załóżmy, że kod $C$ ma tę własność, że każde dwa jego elementy znajdują się w odległości co najmniej $d$. Udowodnić, że:
$|C| \leq \frac{p^n}{\sum\limits_{k=0}^{t} \binom{n}{k}(p-1)^k}$
gdzie $t = \lfloor \frac{d-1}{2} \rfloor$
b) Rozpatrzmy kod $C$ nad $\mathbb{Z}_{2}$ otrzymany w następujący sposób: każdemu możliwemu ciągowi $(x_{1}, x_{2} ,x_{3}, x_{4}) \in \{0,1\}^4$ przyporządkowujemy ciąg $(x_{1}, x_{2} ,x_{3}, x_{4}, x_{2} + x_{3} + x_{4}, x_{1} + x_{3} + x_{4}, x_{1} + x_{2} + x_{4})$. Elementami kodu są wszystkie otrzymane w ten sposób ciągi z $\{0,1\}^7$. Znaleźć minimalną odległością między dowolnymi dwoma elementami $C$. Jak ma się rozmiar kodu i minimalna odległość do nierówności z poprzedniego podpunktu? Znaleźć macierz $G$ o wymiarach $4 \times 7$ taką, że $C = \{x \cdot G : x \in \{0,1\}^4 \}$.
Zadania dodatkowe
Zadanie 4
Skończoną płaszczyzną rzutową rzędu $q$ nazwiemy zbiór $X$ o $q^2 + q + 1$ elementach, zwanych punktami, wraz z rodziną podzbiorów $X$, oznaczaną $\mathcal{L}$ i zwaną rodziną prostych, o następujących własnościach:
1) Każda prosta zawiera dokładnie $q+1$ punktów
2) Dowolne dwa punkty leżą na dokładnie jednej prostej
a) Udowodnić, że każdy punkt leży na dokładnie $q+1$ prostych, prostych jest dokładnie $q^2 + q +1$ oraz dowolne dwie proste przecinają się w dokładnie jednym punkcie.
b) Podać przykład płaszczyzny rzutowej rzędu 2.
c) Rozpatrzmy trójki elementów $(x_{0}, x_{1}, x_{2})$, gdzie $x_{i} \in \mathbb{Z}_{q}$ i $q$ jest liczbą pierwszą. Rozpatrzmy zbiór $X$ złożony z elementów oznaczanych $[x_{0} : x_{1} : x_{2}]$ zdefiniowanych jako:
$[x_{0} : x_{1} : x_{2}] = \{ (cx_{0}, cx_{1}, cx_{2}) : c \in \mathbb{Z}_{q}, c \neq 0 \}$
gdzie zakładamy, że nie wszystkie $x_{0}, x_{1}, x_{2}$ są jednocześnie równe $0$. Innymi słowy, dla każdej trójki $(x_{0}, x_{1}, x_{2})$ utożsamiamy z nią wszystkie trójki otrzymane z niej przez pomnożenie przez niezerowy element z $\mathbb{Z}_{q}$.
Określamy zbiór $\mathcal{L}$ jako złożony z elementów oznaczanych $L(a_{0}, a_{1}, a_{2})$ i zdefiniowanych jako:
$L(a_{0}, a_{1}, a_{2}) = \{ [x_{0} : x_{1} : x_{2}] : a_{0}x_{0} + a_{1}x_{1} + a_{2}x_{2} = 0 \}$
dla wszystkich trójek takich, że nie wszystkie $a_{0}, a_{1}, a_{2}$ są jednocześnie równe $0$.
Udowodnić, że zbiór punktów $X$ wraz ze zbiorem prostych $\mathcal{L}$ tworzy płaszczyznę rzutową rzędu $q$.
Zadanie 5
Niech $\mathbb{F}_q$ będzie ciałem skończonym mocy $q$. Niech $X=\{X_1,\dots,X_m\}$ będą losowo wybranymi elementami $\mathbb{F}_q$ (być może z niejednostajnym rozkładem) - rodzinę $X$ nazwiemy $2$-niezależną, jeśli dla dowolnych $i \neq j$ i dowolnych $a,b \in \mathbb{F}_q$ mamy:
$\mathbb{P}(X_i = a \cap X_j = b) = \mathbb{P}(X_i = a)\mathbb{P}(X_j = b)$
gdzie $\mathbb{P}(A)$ oznacza prawdopodobieństwo zajścia zdarzenia $A$
(innymi słowy, wszystkie zmienne są parami niezależne; jest to własność słabsza od łącznej niezależności)
Analogicznie, rodzinę zmiennych nazywamy $k$-niezależną, jeśli dla dowolnych $i_1, \dots, i_k$ oraz dowolnych $a_1, \dots, a_k \in \mathbb{F}_q$ zachodzi:
$\mathbb{P}(\bigcap_{j=1}^{k}X_{i_j}=a_j) = \prod_{j=1}^{k}\mathbb{P}(X_{i_j}=a_j)$
Niech $X_0, X_1$ będą niezależnie i jednostajnie wylosowanymi elementami $\mathbb{F}_q$. Rozpatrzmy rodzinę zmiennych $Y_1,\dots,Y_q$ określoną jako:
$Y_k = X_0 + X_1 k$
a) pokaż, że $Y_k$ tworzą rodzinę $2$-niezależnych zmiennych - jaki płynie pożytek z wprowadzenia takich zmiennych, jeśli naszym celem jest otrzymanie jak największej rodziny $2$-niezależnych zmiennych przy użyciu jak najmniejszej liczby losowych bitów? (porównaj np. z sytuacją, gdy wszystkie $Y_k$ losujemy niezależnie)
b) pokaż, że $Y_k$ nie są $3$-niezależne
c) uogólnij tę konstrukcję na rodzinę zmiennych $k$-niezależnych dla dowolnego $k$
Zadanie 6
Niech $V$ będzie przestrzenią liniową nad $\mathbb{F}_q$ wymiaru $n$ (ciało ma moc $q$). Ile jest podprzestrzeni $V$ wymiaru $k$, $0 \leq k \leq n$?
Zadanie 7
Przypuśćmy, że $n$ osób posiada pewien sekret (losowo wybraną liczbę $x \in \mathbb{Z}_p$), który chcą podzielić na $n$ części tak, aby:
- każde $k$ osób na podstawie swoich części mogło odtworzyć sekret
- części posiadane przed dowolny podzbiór $i < k$ osób nie dawały żadnej informacji o sekrecie (tzn. z punktu widzenia tych osób każda wartość sekretu jest równie prawdopodobna)
Jak można tego dokonać? (wskazówka: rozpatrz wielomian stopnia $k-1$ nad $\mathbb{Z}_p$ o losowych współczynnikach)