Program
Warsztaty mają na celu zaprezentowanie pewnych metod teorii liczb. Przedmiotem badań będą głównie funkcje arytmetyczne (duży nacisk położymy na funkcje multiplikatywne), asymptotyki, metody sitowe oraz związki pomiędzy tymi pojęciami.
- Funkcjami arytmetycznymi nazywamy funkcje postaci $f:\mathbb{N} \rightarrow \mathbb{R}$ (lub $\mathbb{C}$); w istocie są to po prostu ciągi nieskończone. W szczególności funkcję taką nazwiemy multiplikatywną, jeżeli spełniony jest warunek "dla względnie pierwszych $q_1,q_2$ zachodzi $f(q_1 q_2) = f(q_1)f(q_2)$". Takimi funkcjami są m.in.: funkcja Eulera $\phi (n)$ określająca liczebność zbioru $\{ k \in \mathbb{N}~|~ k \leqslant n,~ \gcd(k,n)=1 \}$; funkcje przypisujące każdej liczbie naturalnej liczbę jej dzielników, sumę jej dzielników itp.; funkcja $\mu (n)$ Möbiusa. Wprowadzone zostanie działanie splotu funkcji tej postaci, którego analiza pozwoli znaleźć pewne zależności liczbowe.
- Badanie asymptotyki polega na zdobywaniu informacji na temat tego, w jaki sposób zachowuje się pewna funkcja w porównaniu do jakiejś innej dobrze już znanej. Nas będą interesowały w szczególności sumy zawierające funkcje multiplikatywne oraz liczby pierwsze. Do ich badania zostanie wprowadzona notacja "duże O". Np. zapis $f(n)=\sum_{k=1}^{n} \frac{1}{k} = \log n + O(1)$ oznacza, że funkcja $f$ w każdym punkcie swojej dziedziny różni się od logarytmu naturalnego o co najwyżej pewną stałą. Za ciekawszy przykład może posłużyć twierdzenie: $\sum_{k=1}^n \phi (k) = \frac{3}{\pi^2} n^2 + O(n\log n)$ (tutaj "duże O" oznacza, że błąd szacowania sumy przez $\frac{3}{\pi^2} n^2$ wynosi co najwyżej $C n \log n$, gdzie $C$ oznacza pewną stałą; $\phi$ oznacza oczywiście funkcję Eulera).
- W dalszej części zajęć zmierzymy się z metodami sitowymi: służą one do szacowania liczebności różnych skończonych podzbiorów $\mathbb{N}$ określonych przy pomocy funkcji multiplikatywnych. Takimi zbiorami mogą być np. liczby pierwsze z pewnego przedziału lub jego podzbiory jak np. liczby bliźniacze. Wprowadzone zostanie sito Legendre'a, a następnie przy jego pomocy rozwiążemy kilka problemów takich jak zagadnienie gęstości liczb bezkwadratowych (zaskakującym może wydawać się wniosek, że liczby bezkwadratowe "zajmują" dokładnie $\frac{6}{\pi^2}$ całego $\mathbb{N}$), czy twierdzenie Bruna o zbieżności szeregu odwrotności liczb pierwszych bliźniaczych. Jeżeli wystarczy czasu zmierzymy się także z bardziej wyrafinowaną metodą - sitem Selberga; prowadzi ona do wyników głębszych i bardziej zaskakujących, niż sito Legendre'a.
Wymagania
- Znajomość elementarnej kombinatoryki.
- Znajomość podstawowych pojęć analizy matematycznej - ciąg, granica ciągu, granica funkcji w nieskończoności, szereg.
- Przydatna może być znajomość podstaw rachunku całkowego; nie jest jednak ich znajomość czymś koniecznym - korzystać z nich będziemy co najwyżej kilka razy.
Zadania kwalifikacyjne
- Rozważamy $\mathbb{N} = \{1,2,3,...\}$; $\log x$ oznacza logarytm naturalny.
- Zadania, które wymagają znajomości analizy na poziomie wykraczającym poza liceum, lub które są trudne w ogólnym sensie, oznaczam gwiazdkami. "Trudność" zadania widzę czysto subiektywnie; jej stopień w wypadku poniższych problemów jest bardzo różny.
- W razie wątpliwości można śmiało kierować pytania dotyczące zadań i warsztatów na adres lp.pw|saksarak#lp.pw|saksarak.
- Rozwiązania proszę przesyłać na powyższy adres; najlepiej w postaci pliku PDF.
- Aby zakwalifikować się na warsztaty, nie trzeba wykonywać wszystkich zadań - warunkiem wystarczającym (niekoniecznie koniecznym) jest zdobycie 18 punktów.
- Wykonanie zadania oznaczonego trzema gwiazdkami gwarantuje wstęp na warsztaty.
1.
Proszę zapoznać z definicją funkcji $\mu$ Möbiusa. Wykazać, że dla naturalnych $n \geqslant 2$ zachodzi
$\sum_{d|n} \mu (d) = 0$. (3 pkt.)
Uwaga odnośnie notacji: suma powyżej przebiega wszystkie dzielniki liczby $n$. Mamy więc np. dla $n=12$:
$\sum_{d|12} \mu(d) = \mu(1) + \mu(2) +\mu(3) + \mu(4) + \mu(6) + \mu(12) = 1 - 1 - 1 + 0 + 1 + 0 = 0$.
2.
Powiemy, że ciągi $f,g:\mathbb{N} \longrightarrow \mathbb{R}$ spełniają zależność $f(n) = O(g(n))$, jeżeli
istnieją stałe $n_0, C$ takie, że dla wszystkich $n>n_0$ zachodzi $|f(n)| \leqslant C|g(n)|$
(jest to pewna szczególna wersja notacji "duże O").
Wykaż, że:
a) $4n^2 + 5n - 12 = O(n^2)$ (1 pkt.)
b) $\log n = O(n)$ (1 pkt.)
c) $\log n! = O(n \log n)$ (2 pkt.)
3.*
Uzasadnij, że dla każdego naturalnego $n$ wartość sumy $\sum_{k=1}^{n} \frac{1}{k}$ różni się od $\log n$ o co najwyżej $1$. (6 pkt.)
Prohint: Warto skorzystać z geometrycznej interpretacji całki oznaczonej.
Uwaga: Nie trzeba (oczywiście jeżeli ktoś się tego podejmie, to świetnie) w ramach rozwiązania proponować
formalnego dowodu; wystarczy graficzna interpretacja zjawiska, ewentualnie inne "heurystyczne, acz
dostatecznie przekonujące" wyjaśnienie.
4.
Udowodnij, że układ równań:$~ x^2 + y = z^2$, $y^2 + x = t^2$ nie ma rozwiązań w liczbach naturalnych. (4 pkt.)
5.
Zbadaj zbieżność szeregów:
a) $\sum_{n=1}^{\infty} \frac{1}{n}$ (1 pkt.)
b) $\sum_{n=1}^{\infty} \frac{1}{n^{\alpha}}$ dla każdego $~\alpha>1$ (*) (3 pkt.)
c) $\sum_{n=1}^{\infty} \frac{(-1)^{\left[n \sqrt{2} \right] }}{n}$, gdzie $[n \sqrt 2]$ oznacza zaokrąglenie w dół danej liczby rzeczywistej do części całkowitej. (***)
6.
Wykaż, że funkcje $\phi$ Eulera oraz $\mu$ Möbiusa są multiplikatywne (odpowiednie definicje wymieniłem
w opisie warsztatów). (3 pkt.)
7.
Uzasadnij, że odległość (moduł różnicy) między dwiema kolejnymi liczbami pierwszymi może być dowolnie duża. (3 pkt.)
8.*
Znajdź liczbę rozwiązań kongruencji $x^2 \equiv 1 \mod 20!$ w zbiorze $\{1,2,...,20!-1 \}$. (6 pkt.)
9.
Dla "dużego O" zdefiniowanego w zadaniu 2. oraz ciągów $f,g,h:\mathbb{N} \longrightarrow \mathbb {R}$
wyprowadź zależności:
a) Jeżeli $f=O(g)$ i $g=O(h)$, to $f=O(h)$. (1 pkt.)
b) Jeżeli $f,g=O(h)$, to $f+g,~f-g=O(h)$. (1 pkt.)
c) Jeżeli $f=O(g)$, to $fh=O(g|h|)$. (1 pkt.)
Miłej zabawy.
Wyniki
Przepraszam za duże opóźnienie; wszystkie wyniki zostały już wpisane. Jeżeli ktoś uważa, że został źle oceniony (np. jeżeli ktoś dostał 0 punktów na 6, ponieważ odpowiednie rozwiązania nie pojawiły się w mojej skrzynce mailowej), to proszę o pilny kontakt.