Informace k přednášce "Kombinatorická a výpočetní geometrie II" 
(Jiří Matoušek, Pavel Valtr, KAM)

LS 2009/2010
Rozsah výuky: LETNÍ semestr 2/2 Z, Zk

Umluveno na středu 15:40 v S10

Anotace

Obsah

Přednáška 24.2.2010 (JM)

• Připomenutí Szemerédiho-Trotterovy věty.
• Připomenutí příkladu n přímek a n bodů s řádově n^{4/3} incidencemi ("protáhlá mřížka" k x 4k^2).
• Jiný příklad (původní Erdosův): mřížka k x k, přímky se směrnicemi a/b, a,b nesoudělná přirozená čísla mezi 1 a vhodným t (bez důkazu).
• Pojem normy v rovině, striktně konvexní norma, problém jednotkových vzdáleností pro normu, Valtrův příklad striktně konvexní normy s řádově n^{4/3} jednotkovými vzdálenostmi.
• Erdosův příklad s mnoha jednotkovými vzdálenostmi (pro euklidovskou normu v rovině): mřížka n^{1/2} x n^{1/2} vhodně škálovaná (viz skripta část 4.2). Bez důkazu číselně-teoretické výsledky: každé prvočíslo tvaru 4k+1 se dá napsat jako součet dvou čtverců; Gaussova celá čísla Z[i] mají jednoznačné rozklady na prvočinitele. Dokončení příště.

Přednáška 3.3.2010 (JM)

• Formulace prvočíselné věty a Dirichletovy věty o hustotě prvočísel v aritmetických posloupnostech.
• Odvození odhadu n^{1+c/log log n} pro počet jednotkových vzdáleností ve vhodně škálované mřížce.
• Značení A+A a AA pro množiny reálných čísel. Příklady: pro A rychle rostoucí či "generickou" je |A+A| kvadratické, pro aritmetickou posloupnost je |A+A|=2n-1 (n=|A|).
• Pojem d-dimenzionální aritmetické posloupnosti. Freimanova věta (jen znění, popisuje strukturu množin A splňujících |A+A| < Cn pro nějakou konstantu C.
• Problém součtů a součinů (Erdos, Szemeredi): musí vždycky aspoň jedno z |A+A|,|AA| velké? (Nedokázaná) domněnka: maximum z nich je vždy téměř kvadratické. Nejlepší známý výsledek: max(|A+A|,|AA|) je aspoň zhruba |A|^{4/3}.
• Slabší výsledek [Elekes]: max(|A+A|,|AA|) aspoň řádu n^{5/4}. Důkaz ze Szemerédiho-Trotterovy věty.
• Silnější věta [Solymosi, z tohoto clanku]: max(|A+A|,|AA|) aspoň řádu n^{4/3}/(log n)^{1/3}.
• Dokážeme |A+A|^2.|AA| aspoň řádu n^4/log n.
• Pomocná veličina: "multiplikativní energie" E(A). Lemma (převlečená Cauchyho-Schwarzova nerovnost): E(A) >= n^4/|AA|. Dokončení příště.

Přednáška 10.3.2010 (JM)

• K dokončení důkazu stačí ukázat, že E(A)/log n = O(|A+A|^2). Interpretujeme (A+A)x(A+A) jako (AxA)+(AxA) (součty 2dim vektorů), chceme najít hodně navzájem různých součtů.
• Definujeme m_q jako počet dvojic (a,b) z A^2, pro něž a/b=q. Platí E(A)=\sum m_q^2. Geometricky: na přímce y=qx leží m_q bodů z AxA.
• Teď se vybereme vhodný soubor z těchto přímek, uvažujeme sumy vektorů ze sousedních přímek. Ukáže se, že jich je řádově aspoň E(A)/log n (je potřeba zvlášť ošetřit případ, kdy bychom vybrali jenom jednu přímku). Tím je důkaz hotov.
• Sumy a součiny v konečných tělesech. Varovné příklady: Szemerédiho-Trotterova věta pro konečné projektivní roviny neplatí (mohou mít mnohem víc incidencí). Závažnější: podtěleso je uzavřené na sumy i součiny, a tedy nemůžeme čekat, že by max(|A+A|,|AA|) bylo vždycky větší než |A|.
• Dvě věty s mnoha aplikacemi v několika oblastech:
  • [Bourgain-Katz-Tao] Pro každé epsilon>0 existuje delta>0 tak, že je-li F těleso s prvočíselným počtem prvků a je-li A podmnožina F velikosti nejvýš |F|^{1-epsilon}, pak max(|A+A|,|AA|) je aspoň |A|^{1+delta}. (To delat nebudeme, bylo by to na vic prednasek, pro zajemce zde dosti pristupna prezentace, kterou sepsal Ben Green.)
  • [Garajev] Je-li F q-prvkové těleso a |A| je mezi q^{1/2+epsilon} a q^{1-epsilon}, potom max(|A+A|,|AA|) je aspoň |A|^{1+delta}.
• Dokážeme Garejevovu větu ve tvaru: pro libovolnou podmnožinu A q-prvkového tělesa F platí max(|A+A|,|A|) aspoň min((q|A|)^{1/2}, |A|^2/q^{1/2}). Solymosiho prezentace zde.
• Začátek důkazu: Definujeme graf G=(V,E), vrcholy jsou dvojice (a,b), a je nenulové z F, b je libovolné z F, hrany tvaru {(a,b),(c,d)}, kde ac=b+d (se smyčkami, (q-1)-regulární, n=q(q-1) vrcholů).
• Matice sousednosti M, její vlastní čísla, největší je q-1 s vlastním vektorem (1,1,...,1), všechny ostatní vlastní vektory k němu ortogonální.

Přednáška 17.3.2010 (JM)

• Lemma: Jsou-li (a,b) a (c,d) vrcholy grafu G, pro něž a je různé od c a b je různé od d, pak mají právě jednoho společného souseda. Jinak nemají žádného.
• Odtud: M^2=J+(q-2)I-E, kde E je "chybová" matice jistého (2q-3)-regulárního grafu. Z toho se spočte, že je-li v_i vlastní vektor matice M s vlastním číslem lambda_i, a je-li v_i ortogonální k 1, pak v_i je vlastní vektor E s vlastním číslem lambda_i^2-q+2.
• Z toho: |lambda_i| je menší než odmocnina z 3q.
• Garajevova věta se dostane z následujícího tvrzení pro S:=(AA)x(-A), T:=(A^{-1})x(A+A).
• Obecné tvrzení (je-li druhé vlastní číslo malé, pak jsou velké množiny vrcholů hodně propojené): Je-li G d-regulární graf a všechna vlastní čísla mimo prvního mají absolutní hodnotu nejvýš lambda, pak pro každé dvě podmnožiny S a T vrcholů, s=|S|,t=|T| platí |e(S,T)-(d/n)st| <= lambda odmocnina(st). Dukaz z knihy Alon-Spencer zde.
• Pojem prostorového kříženípro množinu L přímek v R^d. Dolní odhad pomocí vhodné mřížky: n přímek může mít řádově n^{d/(d-1)} prostorových křížení.

Přednáška 24.3.2010 (JM)

• Věta: libovolných n přímek v dimenzi d má nejvýš C_d n^{d/(d-1)} prostorových křížení.
• Lemma: je-li S množina m bodů v R^d a b je číslo splňující b+d nad d je větší než m, pak existuje nenulový mnohočlen stupně nejvýš b v d proměnných, který se anuluje ve všech bodech S. (Důkaz - lineární algebra.)
• Důkaz věty: množina L přímek, množina J jejich prostorových křížení, |J|=m. Můžeme zařídit (přípravný krok), že každá přímka prochází aspoň k=m/2n body z J.
• Zvolme nenulový polynom p nejmenšího možného stupně, který je nulový všude na J (z lemmatu horní odhad na stupeň). Ukážeme, že je nulový na každé přímce z L, z toho: jeho parciální derivace jsou všechny nulové v každém bodě z J. Jedna z těchto d parciálních derivací je nenulový mnohočlen stupně menšího než p, který je také nulový všude na J, spor. Odtud nerovnost pro k a odhad m.
• Kakeyův problém. Definice Kakeyovy množiny, konstrukce Kakeyovy množiny v rovině libovolně malé plochy (bez důkazu, že má malou plochu). Kakeyova domněnka, definice Hausdorffovy dimenze. Dvirova věta (= Kakeyova domněnka pro konečná tělasa) - jen znění. Zde text k tomuto bodu, i s Dvirovým důkazem (ale bez Schwartzovy-Zippelovy věty).

Přednáška 31.3.2010 (JM)

• Uvažme dvě přímky v rovině, na jedné z nich body p_1,...,p_n, na druhé q_1,...,q_n. Kolika různých hodnot nabývá euklidovská vzdálenost ||p_i-q_j||, i,j=1,2,...,n? Pro rovnoběžné či kolmé přímky najdeme příklady s jen 2n-1 vzdáleností.
• Purdyho domněnka: pokud přímky rovnoběžné ani kolmé nejsou, je počet vzdáleností vždy větší než lineární v n. Dokázali to Elekes a Ronyai.
• Algebraická formulace: Zavedeme polynom P(x,y):= x^2+y^2-2 lambda xy. Pro množiny S, T reálných čísel pišme Z:=P(S,T)={P(s,t):s\in S, t\in T}. Purdy algebraicky: pro lambda různé od 0,+1,-1 roste |Z| rychleji než lineárně pro |S|=|T|=n.
• Elekesova-Ronyaiova věta: Je-li p(x,y) polynom, který není speciální, potom |P(S,T)| roste rychleji než lineárně pro n=|S|=|T|. Zde speciální polynomy jsou tvaru f(g(x)+h(y)) nebo f(g(x)h(y)) pro nějaké polynomy f,g,h, tj. "zakuklený součet nebo součin". Důkaz potřebuje výsledky algebraické geometrie, nebudeme dělat.
• Dokázali jsme speciální případ, totiž Purdyho domněnku, s odhadem |Z| aspoň cn^{7/6}. Tam se dají algebraické výsledky nahradit konkrétním výpočtem.
• Potřebujeme větu o incidencích bodů a křivek (ze cvičení, v přednášce nedokazujeme): Je-li Gama množina jednoduchých křivek v rovině, a žádné dvě z nich se neprotínají v k nebo více bodech, potom počet jejich incidencí s m-bodovou množinou je nejvýš řádu m^{k/(2k-1)}|Gama|^{1-1/(2k-1)}+|Gama|+m.
• Naše křivky budou gama_{ij}={(P(s_i,t),P(s_j,t)): t\in R}, i různé od j, kde S={s_1,...,s_n}. Body budou ZxZ. Každá gama_{ij} má aspoň n incidencí s ZxZ (dosazujeme hodnoty t \in T).
• Ukážeme (výpočtem): gama_{ij} jsou paraboly (otočené o 45 stupňů), splývají nanejvýš po dvojicích, splňují předpoklady věty pro k=3. Z odhadu pro incidence pak vyjde |Z| aspoň n^{7/6}, hotovo.

Prednaska 7.4.2010 (PV)

• tri motivacni priklady (bodovy pozorovatel v souboru n usecek v rovine, dolni obalka n usecek v rovine, dolni obalka n polynomu stupne nejvyse d)
• Davenport- Schinzelovy posloupnosti, jednodussi odhady na jejich delku
• zacatek horniho odhadu max. delky DS-posloupnosti radu 3

Prednaska 14.4.2010 (PV)

• dokonceni horniho odhadu max. delky DS-posloupnosti radu 3

Prednaska 21.4.2010 (PV)

• dolni odhad max. slozitosti dolni obalky n usecek
• konstrukce n bodu na povrchu koule v R^3 o prumeru odmocnina z 2 s cn^{4/3} jednotkovymi vzdalenostmi mezi nimi (radove nejlepsi mozne)
• horni odhad O(n^{4/3}) pro povrch koule libovolneho prumeru se dela stejne jako pro rovinu (pres nakresleni grafu a lemma o prusecikovem cisle)

Prednaska 28.4.2010 (PV)

• konstrukce n bodu na povrchu koule libovolneho pevneho prumeru vetsiho nez 1 s cn.(odmocnina z n) jednotkovymi vzdalenostmi mezi nimi
• obdobna konstrukce: n bodu v rovine urcujicich alespon cn.(odmocnina z n) jednotkovych usecek, z nichz zadne dve nejsou rovnobezne
• jednoducha konstrukce n bodu v rovine s alespon cnlogn pulicimi useckami (dlouho nebyl znam zadny lepsi dolni odhad)
• Tothova konstrukce n bodu v rovine s alespon n e^{c.(odmocnina z n)} pulicimi primkami

Prednaska 12.5. nebude (rektorsky den)