Uvod do teorie cisel MAI040

Syllabus viz bila karolinka. Umluveno na CTVRTEK od 17:30 do 19:00 v seminarni mistnosti KAM. Zaciname UZ 30. ZARI !

POZOR POZOR: Od 14.10. se vyuka kona uz doufejme az na vecne casy v seminarni mistnosti KAM ve 3. patre.


30.9. 1999: 1. Diofanticke aproximace. Aproximace realnych cisel zlomky p/q s presnosti <1/q^2, Dirichletova veta (kazde irac. cislo ma nekonecne mnoho takovych aproximaci), dukaz Fermatovy vety (kazde prvocislo p=4n+1 je soucet dvou ctvercu) pomoci diof. aproximaci, Fareyovy zlomky a Cauchyho veta (rozdil sousednich F. zlomku je nejmensi mozny), formulace Hurwitzovy vety (kazde irac. cislo ma nekonecne mnoho aproximaci p/q presnejsich nez 5^(-1/2)/q^2 a 5^(-1/2) je nejlepsi takova konstanta). DOM CV: Dokazte, ze pro tri sousedni F. zlomky a/b<c/d<e/f plati c/d=(a+e)/(b+f).

7.10. 1999: Dukaz Hurwitzovy vety. Zakladni vlastnosti retezovych zlomku (definice, dve lemmata a pak shrnuti). Lagrangeova veta (retezovy rozvoj realneho cisla je periodicky prave kdyz to je kv. iracionalita) zminena bez dukazu. Liouvilleova veta (je-li c alg. realne cislo stupne n>1, mame |c-p/q|>>1/q^n pro kazdy zlomek p/q, kde konstanta v >> zavisi jen na c). DOM CV:  Zkuste si nalezt nekolik retezovych rozvoju kvadratickych iracionalit sqrt(2), sqrt(7) apod. 

14.10. 1999: Kriterium transcendence plynouci z L. vety (c je  irac. a pro kazde n existuje zlomek p/q s q > 1 takovy, ze |c-p/q| < 1/q^n: pak je c nutne transc.). Informativne o zesilenich L. vety (zlepseni Thueho, Siegela, Gelfonda a Dysona, a konecne Rotha). Dulezitost techto zlepseni  (jiz z Thueho zlepseni plyne, ze diof. rovnice jako x^3-2y^3=1 maji jen konecne mnoho reseni). Hilbertuv dukaz transcendence cisla e. Informativne o 7. Hilbertove problemu (pro c, b alg. , kde c je ruzne od 0, 1 a b je irac., je c^b transc. - dokazali v r. 1934 Gelfond a Schneider) DOM CV: Dokazte, ze 1/10^(1!)+1/10^(2!)+... je transc.

21.10.1999: 2. Geometrie cisel. Gaussova veta (r(0)+r(1)+...+r(n)=pi.n+O(n^(1/2)), kde r(n)=# reseni rovnice n=x^2+y^2 v celych cislech x, y). O kruhovem problemu (vylepsovani te 1/2). Lemma o harmonickych cislech (1/1+1/2+...+1/n=log(n)+g+O(1/n)). Dirichletova veta (d(1)+...+d(n)=n.log(n)+(2g-1)n+O(n^(1/2)), kde d(n) je # delitelu n). O problemu delitelu (vylepsovani te 1/2). Minkowskiho veta (konvexni, stredove soumerne teleso v R^n s objemem >2^n obsahuje mrizovy bod ruzny od pocatku) s 2 dukazy. 

 28.10.1999: Statni svatek.

4.11.1999: Obecna formulace  M. vety pro mrizky (konvexni, stredove soumerne teleso v R^n s objemem >2^n.Vol(mrizka) obsahuje bod mrizky ruzny od pocatku). Tvrzeni o nezavislosti objemu zakladniho rovnobezniku mrizky na volbe baze a jeho pouziti-geometricky dukaz Cauchyovy vety o Fareyovych zlomcich. 1. aplikace M. vety-uloha o nemeckem lesiku. 2. aplikace M. vety-dukaz Lagrangeovy vety (kazde prir. cislo je souctem 4 ctvercu). 

11.11.1999: Poznamky k poslednimu dukazu (M. veta ma aplikace v algebraicke teorii cisel, vzorec pro objem n-rozmerne 1-koule, nejvetsi je 5-rozmerna). 3. Diofanticke rovnice. Charakterizace Pythagorejskych trojic (vsechna celoc. reseni rovnice x^2+y^2=z^2 jsou popsana vztahy x=2ab, y=a^2-b^2, z=a^2+b^2). Fermatova veticka (x^4+y^4=z^2 nema reseni v prir. cislech) pomoci nekonecneho sestupu. Aritmeticky dukaz Lagrangeovy vety o 4 ctvercich. Lagrangeova veta o Pellove diofanticke rovnici (je-li d>0 a neni ctverec, ma x^2-dy^2=1 vzdy celoc. reseni s y>0) - dukaz priste. DOM CV: (uloha M. Rosenfelda) Dokazte, ze existuje nekonecne mnoho trojic n-2, n-1, n po sobe jdoucich prir. cisel, z nichz kazde je souctem 2 ctvercu. 

 18.11.1999: Dukaz, ze kazda Pellova rovnice ma netrivialni reseni. Struktura reseni Pelliany (mnozina U={x+ yd^(1/2)>0:  x, y je celociselne reseni} je nekonecna cyklicka multiplikativni grupa). Zobecnena Pelliana (ma-li x^2-dy^2=m jedno netrivialni reseni x, y, ma jich nekonecne mnoho). Priklad pouziti Pelliany ve slozitejsim diof. problemu  (x^3+y^3+z^3+w^3=2 ma nekonecne mnoho reseni). Informativne o 10. Hilbertove problemu (neexistuje algoritmus, ktery by rozhodoval resitelnost diof. rovnic - dokazal v r. 1970 Matyjasevic). 4. Prvocisla. Eukliduv dukaz nekonecnosti poctu prvocisel. 

25.11.1999: DOM CV: Analyzujte dukaz z predchozi prednasky, ze kazda Pelliana ma netrivialni reseni, a zjistete, zda je efektivni. To jest, zda z nej lze odvodit explicitni (rekneme primitivne rekurzivni) funkci F(d) takovou, ze pro kazde nectvercove d>0 ma x^2-dy^2=1 reseni a, b splnujici 0<a, b<F(d).

Goldbachuv dukaz. Euleruv dukaz. Erdosuv dukaz. Lemma o logaritmu faktorialu (log 1+log 2+...+log n=n.log n -n+(log n)/2+c+O(1/n)). von Mangoldtova funkce (L(n)=log p, je-li n mocnina p, =0 jinak) a lemma pro ni (soucet hodnot L(n)([x/n]-2[x/2n]) pro n=1, 2, ..., [x] je asymptoticky x(log 2)+O(log x)). Prvociselna funkce (pi(x)=pocet prvocisel nepresahujicich x), Cebysevova funkce (th(x)=soucet log p pro p nepresahujici x) a lemma pro ni (th(x)<(4log 2)x). Cebysevova veta (x/log x << pi(x) << x/log x) a jeji dukaz pomoci dvou predeslych lemmat. 


2.12.1999: Abelova sumace (je-li h_n posloupnost realnych cisel, h(x) jeji sumatorni funkce a f(x) spojite diferencovatelna funkce, je sumatorni funkce posloupnosti h_n.f(n) rovna h(x)f(x)-integral_1^x h(t)f(t)'dt). Mertensovy odhady M1 (soucet log p/p pro prvocisla p nepresahujici x je log x+O(1)), M2 (soucet 1/p pro -"- je log log x+c+O(1/log x)) a M3 (soucin (1-1/p) pro -"- je c/log x +O(1/(log x)^2)). Prumerny a normalni rad aritmeticke funkce. Prumerny rad funkce poctu prvocinitelu a funkce poctu prvocinitelu s nasobnostmi je log log x. Veta Hardyho a Ramanujana (i jejich normalni rad je v obou pripadech log log x)-kvuli zmateni v definici normalniho radu dokonceni dukazu priste. DOM CV: Uloha o nasobilce. Je pocet vsech ruznych vysledku v tabulce velke nasobilky 1 x 1, 1 x 2, . . . , 1 x n, 2 x 1, . . . , 2 x n, . . . , . . . , n x n alespon cn^2 pro nejakou absolutni konstantu c>0 ? 

9.12.1999: Dokonceni dukazu Hardy-Ramanujanovy vety. Jeji aplikace: pro kazde eps>0 funkce poctu delitelu d(n) splnuje pro vsechny argumenty n, n<x, krome nejvyse eps.x z nich, nerovnosti (log n)^{0.69...-eps} < d(n) < (log n)^{0.69...+eps}, kde 0.69...=log 2. Jak ale vime z prednasky 21.10., aritmeticky prumer (d(1)+d(2)+...+d(n))/n  je asymptoticky mnohem vetsi: log n. 5. Kongruence. Pripomenuti vlastnosti konecnych teles. Chevalley-Warningova veta (kazda polynomialni soustava nad F=GF(p^r) s m neznamymi, pricemz soucet stupnu polynomu je mensi nez m, ma pocet reseni (v F) delitelny p). Dukaz priste. Zatim aplikace: Erdos-Ginzburg-Zivova veta (mezi kazdymi 2n-1 celymi cisly je vzdy nejakych n, jejichz soucet je nasobek n). Dukaz v pripade, ze n=p. 

16.12.1999: Dokonceni dukazu vety tri panu (pro slozeny modul). Dukaz  Chevalley-Warningovy vety. Dalsi aplikace, sice v teorii grafu (kazdy graf, ktery vznikne ze 4-regularniho grafu pridanim hrany, obsahuje neprazdny 3-regularni podgraf). Zakladni poznatky o kvadratickych zbytcich - Legendreuv symbol (a/p),  jeho multiplikativita, Eulerovo kriterium ((a/p) je, modulo p, kongruentni a^{(p-1)/2}). Doplnky k zakonu reciprocity ((-1/p)=(-1)^{(p-1)/2} a (2/p)=(-1)^{(p^2-1)/8}) a zakon reciprocity kvadratickych zbytku ((p/q)=(q/p).(-1)^{(p-1)(q-1)/4}). Dukaz v roce 2000. 

6.1.2000: Gaussovo lemma ((a, p)=1, m(a) je pocet tech nasobku 1.a, 2.a, ..., ((p-1)/2.a, ktere po redukci mod p padnou do (p+1)/2, ..., p-1; pak (a/p)=(-1)^{m(a)}). Dukaz 2. doplnku a dukaz zakona reciprocity kv. zbytku (elementarni dukaz pomoci obrazkoveho lemmatu a Gaussova lemmatu). 6. Ciselne rozklady. Definice ciselneho rozkladu. Rozkladova funkce p(n)=pocet rozkladu n a jeji generujici funkce (1+p(1)x+p(2)x^2+...=1/((1-x)(1-x^2)(1-x^3)...) ). Eulerova identita (pocet rozkladu n na ruzne casti = pocet rozkladu n na liche casti; dukaz generujicimi funkcemi a bijekci). Ferreruv diagram. Pentagonalni cili petiuhelnikova cisla (n je 5uhelnikove, prave kdyz n=(3m^2+-m)/2): 1, 2, 5, 7, 12, 15, ... . Eulerova pentagonalni identita ((1) (1-x)(1-x^2)(1-x^3)...=1-x^1-x^2+x^5+x^7-x^12-x^15+... , jinymi slovy, (2) pocet rozkladu nepentagonalniho n na lichy pocet ruznych casti = pocet jeho rozkladu na sudy pocet ruznych casti, pro pentagonalni n pricteme vpravo (-1)^m, jeste jinymi slovy receno, (3) plati rekurence  p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-..., kde p(0)=1 a p(n)=0 pro n<0). Dukaz priste. 

13.1.2000: Dukaz pentagonalni identity pomoci Ferrerovych diagramu (dukaz formulace 2 pomoci involuce, ktera paruje rozklady n s ruznou paritou poctu casti). Horni odhad partitni funkce ( p(n)< (pi/(6(n-1))^{1/2}).e^{(2n/3)^{1/2}} ), dukaz pomoci generujici funkce. 

leden 2000