Analytická a kombinatorická teorie čísel NDMI045, LS 2013/14

Místo a čas přednášky: Pá 9:00-10:30 v S7.
Výuka tohoto předmětu v minulých letech: zde .
Plán letošní přednášky. Chci probrat, podle časových možností, následující významné a pěkné výsledky z teorie čísel. 1. van der Waerdenova věta (každé konečné obarvení čísel 1, 2, ... obsahuje libovolně dlouhou jednobarevnou aritmetickou posloupnost) a Rothova věta (každá podmnožina čísel 1, 2, ... s kladnou horní hustotou obsahuje aritmetickou posloupnost délky 3). 2. Prvočíselná věta (počet prvočísel nepřesahujících x je asymptoticky x / log x). 3. Konečnost počtu řešení binomické rovnice (diofantická rovnice aX^n - bY^n = c, kde a, b, n jsou přirozená čísla, n > 2, a c je celé nenulové číslo, má jen konečně mnoho celočíselných řešení X, Y).  Dále uvidíme.

Otázky ke zkoušce. (Ohledně termínu zkoušky mne prosím kontaktujte emailem.) 1. Dokažte Rothovu větu. 2. Shelahův důkaz HJ věty. 3. Dolní odhady van der Waerdenových čísel W(k, r). 4. Důkaz Prvočíselné věty (přehledově). 5. Dokažte Jinovu větu z poslední přednášky.

Literatura. Bude uvedena na přednášce.

1. přednáška 28. 2. 2014. 1. Rothova věta (každá podmnožina čísel 1, 2, ... s kladnou horní hustotou obsahuje aritmetickou posloupnost délky 3). Řekli jsme si definici delta-posloupnosti a reformulaci Rothovy věty: každá delta-posloupnost obsahuje AP délky 3. Tři pomocná lemmata: L1 o l-kostkách, L2 o vybrání nasycené podposloupnosti z delta-posloupnosti a L3 o rozkladu konečné množiny X přirozených čísel na maximální intervaly v průnicích X s d třídami mod d. Začátek vlastního důkazu Rothovy věty (který v r. 1969 vymyslel Szemerédi): vezmu delta-posl. (X_i, n_i), jež je (díky L2) nasycená  a uvážím množiny U_i, resp. V_i, což jsou průniky X_i s první, resp. druhou, čtvrtinou. Pro velké i mají alespoň (delta/5)n_i prvků. Cílem je nalézt u v U_i a v ve V_i, že 2v - u je v X_i (pak je {u, v, w = 2v - u} AP v X_i). Viz tento text .
2. přednáška 7. 3. 2014. Dokončení důkazu Rothovy věty. Formulace van der Waerdenovy věty o aritmetických posloupnostech a Halesovy-Jewettovy věty o kombinatorických přímkách, první věta plyne z druhé. Důkazy příště. 
3. přednáška 14. 3. 2014. Klasický důkaz HJ věty založený na dvojité rekurzi: Je-li HJ(k, m, r) nejmenší n, že každé r-obarvení [k]^n obsahuje jednobarevný m-podprostor, potom zřejmě HJ(1, m, r) = HJ(k, m, 1) = m a platí rekurentní nerovnosti (i) HJ(k, m + 1, r) <= HJ(k, 1, r) + HJ(k, m, r^{k^{HJ(k, 1, r)}}) a (ii) HJ(k + 1, 1, r + 1) <= HJ(k, HJ(k + 1, 1, r), r+1). To dává pro HJ(k, r) = HJ(k, 1, r), a tedy i pro van der Waerdenova čísla W(k, r) (jež jsou nejvýše kHJ(k, r)), horní odhad řádu Ackermanovy funkce.  Příště si řekneme Shelahův důkaz, který poskytuje  odhad HJ(k,r) <= f_4(r + 2k), kde f_4(n) = f_3(f_3(...(f_3(1)...)) (n iterací funkce f_3), přičemž f_3(n) = 2^{2^{...{2^2}...}} (n dvojek). 
4. přednáška 21. 3. 2014. Shelahův důkaz, že HJ(k,r) <= f_4(r + 2k), kde f_4(n) = f_3(f_3(...f_3(1)...)) (n iterací funkce f_3(.)). Tento i předchozí důkaz jsou sepsány (anglicky) zde .  Příště: o dolních odhadech na W(k, r).
5. přednáška 28. 3. 2014. První triviální dolní odhad (shora odhadneme počet r-obarvení [n], pro něž je alespoň jedna AP jednobarevná, jako t.r^{n-k+1}, kde t je počet všech AP délky k v [n])  dává W(k, r) >> (k.r^{k - 1})^{1/2}. Druhý odhad pomocí pravděpodobnostní metody a Lovászova lokálního lemmatu dává W(k, r) >> r^{k - 1}) / k. I tyto důkazy jsou napsány zde. 2. Prvočíselná věta. Pro pi(x), počet prvočísel nepřesahujících x, dokážeme asymptotiku pi(x) = x / log x + o(x / log x) (Prvočíselná věta). Tvrzení 1: theta(x) := sum_{p < x}log p < (log 4)x, důkaz.  Tvrzení 2:  theta(x) = x + o(x) <=> Prvočíselná věta, důkaz příště. Postupuju podle tohoto textu (str. 23-35).
6. přednáška 4. 4. 2014. Tvrzení 3:  theta(x) = x + o(x) <=> int_0^{+infty} (theta(e^t) / e^t - 1) dt konverguje, důkaz.  Tvrzení 3: výpočet Laplaceovy transformace g(z) předešlého integrandu, důkaz. Věta 1: funkce g(z) má holomorfní rozšíření z Re(z) > 0 na Re(z) >= 0. Věta 2 (Wiener a Ikehara): když je funkce g(z) Laplaceovou transformací omezené a lokálně integrovatelné funkce f(t) a má holomorfní rozšíření z Re(z) > 0 na Re(z) >= 0, potom integrál int_0^{+infty} f(t) dt konverguje (a nutně se rovná g(0)). Důkazy příště.
7. přednáška 11. 4. 2014. Důkaz Věty 2. Zavedení komplexního logaritmu (log z := log |z| + i.arg(z), kde z není 0 a arg(z) je v [-pi, pi)) a jeho vlastnosti (bez důkazu). Vlastnosti funkce zeta(s): 1) je holomorfní v re(s) > 1, 2) tamtéž je vyjádřena Eulerovým součinem, 3) tamtéž je nenulová, 4) množina bodů, kde zeta(s) není záporné reálné číslo (a můžeme ji tak bez problému zlogaritmovat) je tamtéž hustá, 5) zeta(s) - (s - 1)^{-1} má holomorfní rozšíření na re(s) > 0 (fakticky na celé C) a konečně klíčová vlastnost 6) zeta(s) není 0 na re(s) = 1. Důkazy příště.
8. přednáška 18. 4. 2014. Důkaz Věty 1 pomocí vlastností funkce zeta(s).
9. přednáška 25. 4. 2014. 3. Binomická Thueho rovnice. Dokázali jsme si, modulo důkaz tvrzení o aproximačních polynomech (který ale není právě jednoduchý), že každá diofantická rovnice ax^n - by^n = c, kde n > 2, a, b jsou přirozená čísla a c je celé nenulové číslo, má jen konečně mnoho řešení x, y (v celých číslech). Viz str. 7-10 tohoto textu .
10. přednáška 2. 5. 2014. Thueho rovnice. Dokážeme Thueho nerovnost: |alpha - p/q|  >>_{alpha, ep} 1/q^{d/2+1+ep}, pro každý zlomek p/q, každé ep>0 a každé iracionální algebraické číslo stupně d. Z ní plyne, že každá Thueho rovnice P(x, y) = m, kde m je celé číslo a P je nenulový homogenní a ireducibilní celočíselný polynom stupně alespoň 3 má pouze konečně mnoho celočíselných řešení. Viz  tento text .
11. přednáška 9. 5. 2014. Pokračování v dokazování Thueho nerovnosti (podle tohoto textu). 
12. přednáška 16. 5. 2014. Dokončení důkazu Thueho nerovnosti a tím pádem i důkazu konečnosti počtu řešení Thueho rovnice. 
13. přednáška 23. 5. 2014. Na závěr elementární (bez použití nestandardní analýzy, s nímž přišel právě Jin) důkaz hezké Jinovy věty z aditivní teorie čísel: Jsou-li A, B dvě množiny celých čísel mající Banachovy hustoty a, b > 0, pak existuje taková konečná množina celých čísel F s nejvýše 1/ab prvky, že množina (A - B) + F obsahuje libovolně dlouhé intervaly. Viz str. 4-6 tohoto článku .


květen 2014.