Funkcje arytmetyczne w teorii liczb

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}\cdot f_{q_2}\)". Takimi funkcjami są m.in.: funkcja Eulera \(\phi (n)\) określająca liczebność zbioru \(\{ k \in \mathbb{N} | k \leq 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^n_{k=1} \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^n_{k=1} \phi(k) = \frac{3}{\pi^2} n^2 + O(nlog{n})\) (tutaj "duże O" oznacza, że błąd szacowania sumy przez \(\frac{3}{\pi^2} n^2\) wynosi co najwyżej \(Cn\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 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 karaskas@wp.pl.
•  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 μ Möbiusa. Wykazać, że dla naturalnych \(n \geq 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}\rightarrow \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)| \leq 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^{n}_{k=1} \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^{\infty}_{n=1} \frac{1}{n}\) (1 pkt.)

b) \(\sum^{\infty}_{n=1} \frac{1}{n^{\alpha}}\) dla każdego \(\alpha > 1\) (*) (3 pkt.)

c) \(\sum^{\infty}_{n=1} \frac{ (-1)^{ [n \sqrt2]} }{n} \), gdzie \([n \sqrt2 ]\) 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} \rightarrow \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.