Uvod do teorie cisel MAI040

 Zkousky

Terminy zkousek (jsou spolecne s Diskretni matematikou):
22. 1. E1 od 8:30 (nejvyse 3 lide)
23. 1. T2 od 8:30
30. 1. T1 od 8:30
5. 2.   T1 od 8:30
13. 2.  S nejvetsi pravdepodobnosti v 10:00 na Male Strane. Predposledni patro (stejne, kde byly prednasky), c. dveri 40.

Na zkousku se prihlaste predem emailem.



8. 10. 2001. 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 Eulerovy 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). Cviceni: Dokazte, ze pro tri sousedni F. zlomky a/b<c/d<e/f plati c/d=(a+e)/(b+f). Cviceni: Dokazte, ze vzdy alespon jeden ze dvou sousednich F. zlomku aproximuje mezilehle cislo s presnesnosti <1/(2q^2). Dukaz prvni poloviny Hurwitzovy vety (kazde irac. cislo ma nekonecne mnoho rac. aproximaci s presnosti <1/(5^{1/2}q^2). )


15. 10. 2001.  Dukaz druhe poloviny Hurwitzovy vety (pro zadne A>5^{1/2} se (5^{1/2}-1)/2 neda nekonecne mnoha zlomky p/q priblizit na <1/(Aq^2)). Zavedeni retezovych zlomku, zakladni rekurence pro sblizene zlomky a jiz 3. dukaz Dirichletovy vety. Nektere zajimave retezove zlomky: e = //2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1,1 , 10, ...// (Euler 1737), pi = 1/(6+9/(6+25/(6+49/(6+...)))) (Lange 1999), 1 + B_1x + B_2x^2 + ... = 1/(1 - x - x^2/(1 - 2x - 2x^2/(1 - 3x - 3x^2/(1 - 4x -  ...)))) (Flajolet 1980; B_n jsou Bellova cisla = pocty rozkladu {1, 2, ..., n}) a 1 + exp(-2pi)/(1 + exp(-4pi)/(1 + exp(-6pi)/(1 + ...))) = exp(2pi/5).(((5+5^{1/2})/2)^{1/2}-(5^{1/2}+1)/2) (Ramanujan 1913). Formulace Liouvilleovy vety: Je-li a realne algebraicke cislo stupne n > 1, plati pro kazdy zlomek p/q nerovnost |a-p/q| > c/q^n, kde c>0 zavisi jen na a. Takze cislo 0.11000100000000000000000100... je transcendentni (dokazte podrobne jako cviceni).


22. 10. 2001. Dukaz Liouvilleovy vety. Zbytek prednasky odpadl, nahradou rozdan rozmnozeny text s Hilbertovym dukazem transcendence cisla e = 2.71828... .


29. 10. 2001. Poznamky o Liouvilleove vete: jeji zesileni Thuem a Rothem. 2. Diofanticke rovnice. Charakterizace primitivnich pythagorejskych trojic. Fermatova metoda nekonecneho sestupu: x^4+y^4 = z^2 nema reseni v prir. cislech. Pellova rovnice x^-dy^2 = 1 (d neni ctverec). Lagrangeova veta o Pellove rovnici: vzdy ma netrivialni reseni (a tedy nekonecne mnoho).


5. 11. 2001.  Grupova struktura reseni Pellovy rovnice. Zobecnena Pellova rovnice x^2-dy^2 = m. Tri aplikace Pelliany: 1. Nekonecne mnoho celoc. reseni rovnice x^3+y^3+z^3+w^3 = 2. 2. Mocna cisla: ex. nekonecne mnoho dvojic cisel n, n+1, ktera maji v prvoc. rozkladu vsechny exponenty alespon 2.  3. Informativne o Matijasevicove vete. Jak z Thueho vety plyne, ze x^3-2y^3 = 1 ma jen konecne mnoho reseni. Thueho rovnice (bez dukazu). Zacatek dukazu Lagrangeovy vety o 4 ctvercich.


12. 11. 2001.  Dokonceni dukazu Lagrangeovy vety o 4 ctvercich. 3. Geometrie cisel. Pythagorejske trojice pomoci racionalni parametrizace jednotkove kruznice. Zakladni pojmy teorie mrizek: mrizka, baze,  zakladni rovnobeznik. Objem rovnobezniku je +determinant. Objem zakl. rovnobezniku mrizky nezavisi na bazi. Nacrt dukazu vety o Fareyovych zlomcich (1. predn.) pomoci mrizek.


19. 11. 2001. Dukaz vety o Fareyovych zlomcich (1. predn.) pomoci mrizek. Pickova veta: Plocha konv. mnohouhelniku M s vrcholy v mrizovych bodech = pocet mr. bodu v M - 1/2 poctu mr. bodu na hranici M - 1. Minkowskiho veta: omezene, centralne sym. konvexni teleso v R^n s objemem vetsim nez 2^n krat objem mrizky L obsahuje nutne nenulovy bod mrizky L. Aplikace: dukaz Lagrangeovy vety o 4 ctvercich.


26. 11. 2001. Uloha o nemeckem lesiku. Gaussuv kruhovy problem: r_2(0) + r_2(1) + ... + r_2(n) = pi.n + O(n^{1/2}), kde r_2(n) je pocet reseni rovnice n = x^2 + y^2 v celych cislech. Dirichletuv problem delitelu: d(1) + d(2) + ... +d(n) = n.log(n) + (2g-1)n + O(n^{1/2}), kde d(n) je pocet delitelu cisla n (a g = 0.57221... je Eulerova-Mascheroniova konstanta). 4. Prvocisla. Nekonecnost poctu prvocisel a ctyri dukazy tehoz: Eukliduv, Goldbachuv, Euleruv a Erdosuv.


3. 12. 2001. Erdosuv dukaz Bertrandova postulatu: Pro kazde prir. cislo n existuje prvocislo p v intervalu n < p <= 2n. Cebysevovy odhady: x/log(x) << pi(x) << x/log(x). Lemma: asymptotika von Mangoldtovy funkce. Lemma: parcialni (Abelova) sumace.


10. 12. 2001. Tri Mertensovy odhady. Prumerne rady poctu prvocinitelu cisla n bez nasobnosti om(n) a s nasobnostmi Om(n). Problem s dukazem: Jak odhadnout shora (pomoci x) sumu 1/p^m, kde p je prvocislo, m >= 2 a p^m > x ? Polovina dukazu Hardy-Ramanujanovy (-Turanovy) vety, ze i normalni rad om(n) a Om(n) je log(log(n)).


17. 12. 2001.  Odhad sumy z minula: sum_{p^m>x, m>1} 1/p^m = O(log(x)/x^{1/2}). Dokonceni dukazu Hardy-Ramanujanovy vety a jeji dve aplikace: 1. pro kazde eps>0 ex. x_0, ze pro x > x_0 pro alespon (1-eps).x z cisel 1, 2, ..., x plati nerovnosti (log n)^{log 2-eps} < d(n) < (log n)^{log 2+eps} (zde d(n) je pocet delitelu cisla n), a 2. uloha o nasobilce.  5. Kongruence. Kvadraticke zbytky a nezbytky modulo p. Legendreuv symbol a jeho zakladni vlastnosti (multiplikativita, Eulerovo kriterium). Formulace zakona reciprocity, dukaz priste.


7. 1. 2002.  Gaussovo lemma: (a/p) = (-1)^{m(a)}, kde m(a) je pocet nasobku a, 2a, ..., (p-1)/2.a kongruetnich mod p s cislem z intervalu [-(p-1)/2, ...,-1]. Lemma o reciprocite jiste sumy. Dukaz kvadratickeho zakona reciprocity. Konkretni pocitani Legendreova symbolu. Formulace Chevalley-Warningovy vety; bez dukazu. Jeji aplikace v kombinatorice multigrafu: kazdy multigraf vznikly ze 4-regularniho multigrafu pridanim hrany obsahuje neprazdny 3-regularni podmultigraf.

Prednaska se konala v pondeli od 17:35 v seminarni mistnosti KAM na Male Strane.

unor 2002