Rohová věta

Rohová věta je osvědčeným výsledkem aditivní kombinatoriky , která uvádí přítomnost nějaké uspořádané (v aritmetickém smyslu) struktury zvané roh v dostatečně velkých dvourozměrných množinách jakékoli pevné hustoty.

U přirozených čísel ve skutečnosti mluvíme o příslušnosti k dostatečně husté množině buněk na dvourozměrné mřížce se dvěma konci a bodem zlomu pravého úhlu se stranami stejné délky rovnoběžnými se souřadnicovými osami.

Formulace

Věta se týká dvourozměrné mřížky a uvažuje množiny dvojic čísel (souřadnic ve dvourozměrném prostoru). U přirozených čísel říkejme trojici souřadnic roh. Řekneme, že množina obsahuje nějaký roh, pokud obsahuje všechny tři body tohoto rohu. $x,y,d\ (d\not =0)$ $\{{(x,y),(x+d,y),(x,y+d)}\}$

Pro podmnožinu dvourozměrné mřížky definujeme její hustotu jako , tedy jako podíl buněk patřících do množiny mezi celou mřížkou. $A\subset \{{1,\dots ,N}\}^{2}$ ${\displaystyle {\rho _{N}}(A)={\frac {|A|}{N^{2))))$

Rohová věta

Pro všechny existuje taková , že pokud má množina hustotu , pak obsahuje roh. $\delta$ $N=N(\delta )$ $A\subset \{{1,\dots ,N}\}^{2}$ $\rho _{N}(A)\geq \delta$

Historie zlepšování výsledků

Rohovou větu dokázali [1] [ 2] Miklos Ajtai a Endre Szemeredy v letech 1974-1975 . V roce 1981 tento výsledek vyvrátil Hillel Furstenberg pomocí metod ergodické teorie . Existuje také [3] důkaz od Jozsefa Solymosiho ( maď. Jozsef Solymosi ), založený na lemmatu o odstranění trojúhelníku z grafu .

Kromě faktu existence , které stačí na to, aby jakákoliv množina čtvercové hustoty obsahovala roh, je vhodné uvažovat i pořadí růstu funkce , nebo naopak jako maximální hustotu pro danou , pro která podmnožina bez rohů je možná. $N=N(\delta )$ $\delta$ ${\displaystyle \{1,\tečky ,N\}^{2))$ $N(\delta )$ $\delta (N)$ $\delta$ $N$

Pokud je označena jako hustota maximální podmnožiny čtverce neobsahující žádné rohy, pak věta o hlavním rohu je ekvivalentní tvrzení, že , a je vhodné zvážit obecnější otázku zlepšení horních hranic na . Tuto otázku poprvé položil [4] William Timothy Gowers v roce 2001. $L(N)$ ${\displaystyle \{1,\tečky ,N\}^{2))$ $L(N)=o(1)$ $L(N)$

V roce 2002 Wu Ha Wang dokázal [5] , že , kde je převrácená hodnota tetrace k základu 2 ve stejném smyslu, že přirozený logaritmus je inverzní k exponentu . ${\displaystyle L(N)\leq {\frac {100}{(\log _{*}(N))^{1/4))))$ $\log _{*}$

V letech 2005–2006 Ilja Shkredov zlepšil tento odhad [6] , nejprve na , a poté [7] na , kde a jsou nějaké absolutní konstanty. $L(N)=O\left({\frac {1}{(\log \log \log N)^{C_{1))))\right)$ $L(N)=O\left({\frac {1}{(\log \log N)^{C_{2))))\right)$ $C_{1}$ $C_{2}$

Souvislost s Rothovou větou

Rohovou větu lze považovat za dvourozměrnou obdobu Rothovy věty (speciální případ Szemerediho věty pro průběhy délek ), protože při formulaci problému jde o rovnost dvou „stran“ pravoúhlého rohu. důležité, stejně jako v definici aritmetické posloupnosti , je důležitá rovnost dvou rozdílů mezi sousedními čísly. $3$

Rothova věta (1953)

Pro všechny existuje taková , že pokud má množina hustotu , pak obsahuje aritmetickou posloupnost, tedy trojnásobek čísel pro některé a . $\delta$ $N=N(\delta )$ $A\subset \{{1,\tečky ,N}\}$ ${\frac {|A|}{N}}>\delta$ ${\displaystyle \{ad,a,a+d\))$ $A$ $d\not=0$

Rothův teorém lze odvodit z rohového teorému jako přímý důsledek.

Důkaz

Abychom dokázali opak, předpokládejme, že rohová věta je pravdivá a Rothova věta neplatí, to znamená, že existuje nějaká hustota taková, že pro každého lze najít podmnožinu takové hustoty, která neobsahuje aritmetickou progresi, ale podobnou hustotu. k pokrytí čtverce libovolné velikosti bez tvorby rohů neexistuje. Na základě toho musíme dojít k rozporu. $\delta>0$ $N$ $A\subset \{1,\tečky ,N\}$

Uvažujme takovou množinu za libovolnou a sestrojte z ní dvourozměrnou podmnožinu čtverce velikosti , která bude protipříkladem pro větu o rohu, to znamená, že bude mít známou nenulovou hustotu a neměla by obsahovat rohy. . $N$ $A\subset \{1,\tečky ,N\}$ $(|A|>\delta N)$ $2N$

Takovou množinou bude množina tvaru , tedy posloupnost čar představujících postupné posuny množiny . Pokud by v takové množině byl roh, pak by to znamenalo, že množina měla aritmetickou progresi délky , protože je konstruována tak, že pokud , pak a , a pak kromě rohu obsahuje trojice , která mapuje aritmetický postup na konkrétní řádek. $X=\{(a+(i-1),i):i\in {1,\tečky ,N},a\in A\}$ $A$ $A$ $3$ $X$ $(x,y+d)\in X$ $(xd,y)\in X$ $(xd,y),(x,y),(x+d,y)$

Náš původní předpoklad však byl, že žádné takové progrese neexistují. Nejsou zde tedy žádné rohy. Nyní zvažte hustotu na druhou . Protože existují pouze posuny a všechny jsou zahrnuty v množině úplně, hustota je rovna . $A$ $X$ $X$ ${\displaystyle \{1,\tečky ,2N\}^{2))$ $N$ ${\frac {N|A|}{(2N)^{2}}}>{\frac {\delta N^{2}}{4N^{2}}}={\frac {\delta {čtyři}}$

Takže jsme se naučili, jak vytvořit sadu hustoty, která neobsahuje žádné rohy ve čtverci jakékoli velikosti. To je však v rozporu s naším původním předpokladem, že věta o rohu je pravdivá. ${\frac {\delta }{4}}$

Zobecnění pro skupiny

Kromě vizuálně reprezentativních rohů na mřížce lze uvažovat zobecněné „rohy“ formuláře , kde , a je nějaká skupina s operací . ${\displaystyle \{1,\tečky ,N\}^{2))$ ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\))$ $x,y,d\in G$ $G$ $\circ$

Pro prostor ${\displaystyle {\mathbb {Z} }_{2}^{n))$

Ben Green v roce 2005 zvažoval [8] [9] [10] otázku rohů ve skupině , tedy ne pro množinu přirozených čísel. a pro množinu bitů (skládající se z nul a jedniček) sekvence délky , pro které se místo sčítání používá bitově exkluzivní nebo . ${\displaystyle {\mathbb {Z} }_{2}^{n))$ $n$

Věta (Greene, 2005)

Pro libovolnou existuje taková , že pokud má množina hustotu , pak obsahuje roh formuláře , kde a sčítání se provádí modulo 2 . $\delta$ $n=n(\delta )$ ${\displaystyle A\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n))$ ${\frac {|A|}{2^{2n}}}\geq \delta$ ${\displaystyle \{(x,y),(x+d,y),(x,y+d)\))$ ${\displaystyle x,y,d\in {\mathbb {Z} }_{2}^{n))$

Obecné schéma důkazu pro

{\displaystyle {\mathbb {Z} }_{2}^{n))

Ukazatele jednotnosti

Důkaz používá dva ukazatele rovnoměrnosti rozložení množin – jeden pro „jednorozměrné“ podmnožiny a druhý pro „dvourozměrné“ , kde ${\displaystyle E\subset {\mathbb {Z} }_{2}^{n))$ ${\displaystyle A\subset E_{1}\times E_{2))$ ${\displaystyle E_{1},E_{2}\subset {\mathbb {Z} }_{2}^{n))$

Jako indikátor uniformity pro jednorozměrné množiny se používá speciálně upravená Fourierova transformace , kde se jako koeficienty používají kořeny z jednoty a namísto násobení se používá analog skalárního součinu formy . Jestliže , pak malá hodnota v jistém smyslu znamená, že množina je blízká nějaké náhodně rozložené množině stejné hustoty, což znamená, že je v ní více strukturovaných podmnožin než v mnoha jiných. Pokud pro některé , pak se o množině říká , že je -uniformní. ${\overline {x}}\cdot {\overline {y}}=\sum \limits _{i=1}^{n}{x_{i}y_{i}}{\pmod {2} }$ ${\widehat {E}} (\xi )=\součet \limits _{x\in E}{e^{-(x\cdot \xi )\pi i}}=\součet \limits _{ x\in E}{(-1)^{x\cdot \xi }}$ ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )))$ $E$ $\max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}<2^{n}\alpha$ $\alpha$ $E$ $\alpha$

U množiny má smysl uvažovat balanční funkci , kde je hustota množiny a výraz v hranatých závorkách znamená indikátor příslušnosti k množině. Pro bilanční funkci je stanovena tzv. pravoúhlá norma . Pokud je hodnota této normy v určitém smyslu dostatečně malá, znamená to také blízkost k náhodné množině. Jestliže , pak se množina nazývá -uniformní vzhledem k pravoúhlé normě. $A\subset E_{1}\times E_{2}\subset {\mathbb {Z} }_{2}^{n}\times {\mathbb {Z} }_{2}^{n}$ ${f_{A}}(x,y)=[(x,y)\in A]-\rho [(x,y)\in E_{1}\times E_{2}]$ $\rho =\rho (A)={\frac {|A|}{|E_{1}||E_{2}|}}$ $\lVert {f_{A}}\rVert ^{4}=\sum \limits _{x_{1},y_{1},x_{2},y_{2}}{{f_{A} }(x_{1},y_{1}){f_{A}}(x_{1},y_{2}),{f_{A}}(x_{2},y_{1}),{f_ {A}}(x_{2},y_{2})}$ $A$ $\lVert {f_{A}}\rVert ^{4}<\alpha |E_{1}|^{2}|E_{2}|^{2}$ $A$ $\alpha$

Popis algoritmu

Důkaz je proveden kontradikcí, to znamená, že se zpočátku předpokládá, že soubor má hustotu a neobsahuje rohy. Důkazem je algoritmus pro sekvenční přechod z množiny do její podmnožiny obsažené v součinu prostorů nižší dimenze a majících zde vyšší hustotu. Dále se provádí přechod podle stejného schématu z této podmnožiny do její vlastní podmnožiny a tak dále, dokud není nalezena aritmetická progrese v další podmnožině (která samozřejmě bude patřit sama sobě ). Zastavení algoritmu v určitém bodě je zaručeno tím, že hustota množiny nemůže překročit jedničku a přechod z množiny hustot do její podmnožiny hustoty (v nějakém užším prostoru) , takže přes zúžení podmnožiny algoritmus dokončí svou práci. $A$ $\delta$ $A$ $A$ $\delta$ $\delta +2^{-32}\delta ^{24}$ $2^{32}\delta ^{-24}$

Další podmnožina je považována nejen za , kde je nějaký podprostor, ale také úžeji jako , kde množiny jsou libovolné množiny, ale mající malé Fourierovy koeficienty. Formálně se můžeme shodnout, že , , $A_{i}\subset A$ ${\displaystyle A_{i}\subset W_{i}\times W_{i))$ ${\displaystyle W_{i}\subset {\mathbb {Z} }_{2}^{n))$ ${\displaystyle A_{i}\subset E_{1}^{(i)}\times E_{2}^{(i)))$ ${\displaystyle E_{1}^{(i)},E_{2}^{(i)}\subset W_{i))$ $A_{0}=A$ ${\displaystyle W_{0}={\mathbb {Z} }_{2}^{n))$ ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n))$

Dále budeme uvažovat o samostatném kroku algoritmu a označíme hustoty množin jako a . Na těchto hustotách také záleží v důkazu. $E$ $\beta _{1}={\frac {E_{1}^{(i)}}{|W|}}$ $\beta _{2}={\frac {E_{2}^{(i)}}{|W|}}$

Ve všech třech níže uvažovaných případech je míněna -uniformita množin s ohledem na aktuální prostor $\alpha$ $E$ $W_i$

V každé samostatné fázi algoritmu jsou možné tři případy:

Případ 1

Sady a jsou -uniformní pro některé . Sada je pro některé -uniformní . ${\displaystyle E_{1}^{(i)))$ ${\displaystyle E_{2}^{(i)))$ $\alpha_{1}$ $\alpha _{1}=\alpha _{1}(\delta ,\beta _{1},\beta _{2})$ $A_{i}$ $\alpha_2$ $\alpha _{2}=\alpha _{2}(\delta )$

V tomto případě lze přítomnost rohů dokázat doslova, aniž bychom se ponořili do podmnožin. Navíc lze prokázat, že sada obsahuje minimálně rohy. Toto je nejlepší odhad v pořadí růstu, protože počet rohů samozřejmě nemůže překročit (koneckonců roh je určen třemi čísly, ). $A$ ${\frac {\delta ^{3}\beta _{1}\beta _{2}}{2}}|W|^{3}$ $|W|^{3}$ $x,y,d\in W$

Případ 2

Sada není -uniformní pro totéž jako v předchozím případě. $A$ $\alpha_2$ $\alpha_2$

Tooda se ukazuje, že je možné vybrat podmnožiny tak, že jejich velikost není o mnoho menší než velikosti (nejvýše se zmenší o , kde je polynom ), a hustota množiny mezi výrazně převyšuje její hustotu mezi (přesahuje kde je polynom) $F_{1}\subset E_{1}$ $F_{1}\subset E_{2}$ ${\displaystyle E_{1},E_{2))$ $p({\frac {1}{\delta )))$ $p$ $A$ ${\displaystyle F_{1}\times F_{2))$ ${\displaystyle E_{1}\times E_{2))$ $q(\delta )$ $q$

Případ 3

Jedna z množin není -uniformní (stejně jako v prvním případě). ${\displaystyle E_{1}^{(i)},E_{2}^{(i)))$ $\alpha_{1}$ $\alpha_{1}$

Všimněte si, že tento případ nemůže nastat hned v prvním kroku, protože , a prostor vzhledem k sobě samému je samozřejmě vždy -jednotně. ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n))$ $0$

V tomto případě se použije růst množiny c předchozího kroku, totiž pokud má množina hustotu mezi , pak existence nějakého podprostoru a nějaké posuny množin , takové, že při přechodu do jejich (posunů) průsečíků s tímto podprostorem se nové jednorozměrné množiny ukáží jako -uniformní pro libovolně předem vybrané , a hustota nové dvourozměrné množiny není menší než . $A_{i}$ $\delta _{0}+\tau$ ${\displaystyle E_{1}^{(i)}\times E_{2}^{(i)))$ ${\displaystyle W_{i+1}\subset W_{i))$ $E_{1}^{(i)},E_{2}^{(i)},A$ $\sigma$ $\sigma$ $\delta _{0}+{\frac {\tau }{4))$

Jako zde můžete zvolit , a jako zvýšení množiny poskytnuté v předchozím kroku algoritmu. Rychlost nárůstu hustoty množiny v průběhu algoritmu tedy pouze mírně (čtyřikrát) snížíme , ale v každém kroku zajistíme uniformitu množin , což nám umožňuje tvrdit, že případy 1 a 2 vyčerpat všechny možné případy. $\sigma$ $\alpha_{1}$ $\tau$ $A$ $\alpha_{1}$ ${\displaystyle E_{1}^{(i)},E_{2}^{(i)))$

Pro libovolné abelovské skupiny

Ilya Shkredov v roce 2009 prokázal zobecnění pro abelovské skupiny. [jedenáct]

Teorém

Existuje absolutní konstanta taková, že pokud je abelovská skupina , , pak vyplývá z přítomnosti v rohu $c>0$ $(G,\circ )$ $A\subset G\times G$ ${\displaystyle |A|\geq {\frac {|G|^{2}}{({\log \log {|G|}})^{c))))$ $A$ ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\))$

Poznámky

↑ M. Ajtai, E. Szemeredi: Množiny mřížkových bodů, které netvoří žádné čtverce, Studia Sci. Matematika. hungar. , 9 (1974), 9-11 (odkaz není k dispozici)
↑ Důkaz věty o rozích Archivováno 30. srpna 2012 na Wayback Machine na polymath
↑ J. Solymosi: Poznámka ke zobecnění Rothovy věty, Algorithms Combin. , 25 , 2003, Springer, Berlín, 825-827
↑ Nový důkaz Szemerediho věty . Získáno 5. července 2017. Archivováno z originálu 23. ledna 2018. (neurčitý)
↑ Vu V. H, K otázce Gowerse . Získáno 5. července 2017. Archivováno z originálu 9. ledna 2018. (neurčitý)
↑ I. D. Shkredov, O Gowersově problému . Získáno 5. července 2017. Archivováno z originálu 9. ledna 2018. (neurčitý)
↑ ID Shkredov, O zobecnění Szemerediho věty (předtisk) . Získáno 5. července 2017. Archivováno z originálu 9. ledna 2018. (neurčitý)
↑ Ben Green, „Modely konečných polí v aditivní kombinatorice“ . Získáno 5. července 2017. Archivováno z originálu 13. června 2017. (neurčitý)
↑ Ben Green, „Modely konečných polí v aritmetické kombinatorice“ (předtisk) . Získáno 5. července 2017. Archivováno z originálu 9. ledna 2018. (neurčitý)
↑ I. D. Shkredov, Szemeredyho věta a problémy na aritmetických postupech Archivováno 24. července 2018 na Wayback Machine , s. 147-159
↑ I. D. Shkredov, O dvourozměrné analogii Szemerediho věty v Abelovských grupách . Získáno 5. července 2017. Archivováno z originálu 9. ledna 2018. (neurčitý)