Teorema colțului

Teorema colțului este un rezultat dovedit în combinatoria aditivă care afirmă prezența unei structuri ordonate (în sens aritmetic) numită colț în mulțimi bidimensionale suficient de mari de orice densitate fixă.

Pentru numerele naturale, de fapt, vorbim despre apartenența la un set suficient de dens de celule pe o rețea bidimensională de două capete și un punct de rupere a unui unghi drept cu laturile de aceeași lungime paralele cu axele de coordonate.

Formulare

Teorema se referă la o rețea bidimensională și ia în considerare mulțimi de perechi de numere (coordonate într-un spațiu bidimensional). Pentru numerele naturale, să numim triplul de coordonate colț. Vom spune că un set conține un colț dacă conține toate cele trei puncte ale acestui colț. $x,y,d\ (d\nu =0)$ $\{{(x,y),(x+d,y),(x,y+d)}\}$

Pentru o submulțime a unei rețele bidimensionale , definim densitatea acesteia ca , adică ca proporție de celule aparținând mulțimii între întreaga rețea. $A\subset \{{1,\dots ,N}\}^{2}$ ${\rho _{N}}(A)={\frac {|A|}{N^{2))}$

Teorema colțului

Pentru oricare există astfel încât, dacă setul are densitate , atunci acesta conține un colț. $\delta$ $N=N(\delta )$ $A\subset \{{1,\dots ,N}\}^{2}$ $\rho _{N}(A)\geq \delta$

Istoricul îmbunătățirii rezultatelor

Teorema colțului a fost demonstrată [1] [ 2] de Miklos Ajtai și Endre Szemeredy în 1974-1975 . În 1981, acest rezultat a fost respins de Hillel Furstenberg folosind metodele teoriei ergodice . Există, de asemenea, [3] o demonstrație a lui Jozsef Solymosi ( Hung. Jozsef Solymosi ), bazată pe lema privind îndepărtarea unui triunghi dintr-un grafic .

Pe lângă faptul că existența lui , care este suficientă pentru ca orice set de densități pătrate să conțină un colț, este indicat să se ia în considerare și ordinea de creștere a funcției , sau, dimpotrivă, ca densitate maximă pentru o anumită , pt. care este posibil un submult fără colțuri. $N=N(\delta )$ $\delta$ $\{1,\dots ,N\}^{2)$ $N(\delta )$ $\delta (N)$ $\delta$ $N$

Dacă este notat ca densitatea submulțimii maxime a pătratului care nu conține colțuri, atunci teorema principală a colțului este echivalentă cu afirmația că , și este adecvat să luăm în considerare întrebarea mai generală a îmbunătățirii limitelor superioare pe . Această întrebare a fost pusă pentru prima dată [4] de William Timothy Gowers în 2001. $L(N)$ $\{1,\dots ,N\}^{2)$ $L(N)=o(1)$ $L(N)$

În 2002, Wu Ha Wang a demonstrat [5] că , unde este inversul tetrației față de baza 2 în același sens în care logaritmul natural este inversul exponentului . $L(N)\leq {\frac {100}{(\log _{*}(N))^{1/4)))$ $\log _{*}$

În 2005–2006, Ilya Shkredov a îmbunătățit această estimare [6] , mai întâi la , și apoi [7] la , unde și sunt niște constante absolute. $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}$

Legătura cu teorema lui Roth

Teorema colțului poate fi considerată un analog bidimensional al teoremei lui Roth (un caz special al teoremei lui Szemeredi pentru progresiile lungimii ), deoarece în formularea problemei egalitatea celor două „laturi” unui colț dreptunghiular este cea care este important, la fel ca în definiția unei progresii aritmetice , egalitatea a două diferențe între numerele învecinate este importantă. $3$

Teorema lui Roth (1953)

Pentru oricare există astfel încât, dacă mulțimea are o densitate , atunci ea conține o progresie aritmetică, adică un triplu de numere pentru unele și . $\delta$ $N=N(\delta )$ $A\subset \{{1,\dots ,N}\}$ ${\frac {|A|}{N}}>\delta$ $\{ad,a,a+d\}$ $A$ $d\not=0$

Teorema lui Roth poate fi dedusă din teorema colțului ca o consecință directă.

Dovada

Pentru a demonstra contrariul, să presupunem că teorema colțului este adevărată și teorema lui Roth nu este adevărată, adică există o densitate astfel încât oricine poate găsi o submulțime a unei astfel de densități care nu conține o progresie aritmetică, ci o densitate similară. a acoperi un pătrat de dimensiuni arbitrare fără formarea colțurilor nu există. Trebuie, plecând de aici, să ajungem la o contradicție. $\delta>0$ $N$ $A\subset \{1,\dots ,N\}$

Luați în considerare o astfel de mulțime pentru una arbitrară și construiți din ea o submulțime bidimensională a pătratului mărimii , care va fi un contraexemplu pentru teorema colțului, adică va avea o densitate cunoscută diferită de zero și nu ar trebui să conțină colțuri. . $N$ $A\subset \{1,\dots ,N\}$ $(|A|>\delta N)$ $2N$

O astfel de mulțime va fi o mulțime de forma , adică o succesiune de linii reprezentând deplasări succesive ale mulțimii . Dacă ar exista un colț într-un astfel de set, atunci aceasta ar însemna că mulțimea a avut o progresie aritmetică a lungimii , deoarece este construită în așa fel încât, dacă , atunci și , și atunci, pe lângă colț, conține un triplu care mapează progresia aritmetică la o anumită linie. $X=\{(a+(i-1),i):i\in {1,\dots, N},a\in A\}$ $A$ $A$ $3$ $X$ $(x,y+d)\in X$ $(xd,y)\in X$ $(xd,y),(x,y),(x+d,y)$

Cu toate acestea, presupunerea noastră inițială a fost că nu există astfel de progresii. Deci nu există colțuri. Acum luați în considerare densitatea la pătrat . Deoarece există doar schimburi și toate sunt incluse complet în set, densitatea este egală cu . $A$ $X$ $X$ $\{1,\dots ,2N\}^{2)$ $N$ ${\frac {N|A|}{(2N)^{2}}}>{\frac {\delta N^{2}}{4N^{2}}}={\frac {\delta {patru}}$

Așadar, am învățat cum să construim un set de densități care nu conține colțuri într-un pătrat de orice dimensiune. Totuși, acest lucru contrazice presupunerea noastră inițială că teorema colțului este adevărată. ${\frac {\delta }{4}}$

Generalizare pentru grupuri

În plus față de colțurile reprezentabile vizual pe zăbrele , se pot lua în considerare „colțuri” generalizate de forma , unde , și este un grup cu operația . $\{1,\dots ,N\}^{2)$ ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\))$ $x,y,d\în G$ $G$ $\circ$

Pentru spațiu ${\mathbb {Z} }_{2}^{n)$

Ben Green în 2005 a analizat [8] [9] [10] problema colțurilor în grup , adică nu pentru mulțimea numerelor naturale. și pentru setul de secvențe de biți (format din zerouri și unu) de lungime , pentru care se folosește exclusiv biți sau în loc de adunare . ${\mathbb {Z} }_{2}^{n)$ $n$

Teorema (Greene, 2005)

Pentru oricare , există astfel încât, dacă mulţimea are o densitate , atunci ea conţine un colţ al formei , unde , iar adăugarea se face modulo 2 . $\delta$ $n=n(\delta )$ $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)\))$ $x,y,d\in {\mathbb {Z} }_{2}^{n)$

Schema de probă generală pentru

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

Indicatori de uniformitate

Dovada folosește doi indicatori ai uniformității distribuției mulțimilor - unul pentru submulțimile „unidimensionale” , iar celălalt pentru cele „bidimensionale” , unde $E\subset {\mathbb {Z} }_{2}^{n)$ $A\subset E_{1}\times E_{2}$ $E_{1},E_{2}\subset {\mathbb {Z} }_{2}^{n)$

Ca indicator al uniformității pentru mulțimile unidimensionale, este utilizată o transformată Fourier special adaptată, în care rădăcinile din unitate sunt folosite ca coeficienți și un analog al produsului scalar al formei este utilizat în locul înmulțirii . Dacă , atunci o valoare mică într-un sens înseamnă că mulțimea este aproape de o mulțime distribuită aleatoriu de aceeași densitate, ceea ce înseamnă că există mai multe submulțimi structurate în ea decât în multe altele. Dacă pentru unii , atunci se spune că setul este -uniform. ${\overline {x}}\cdot {\overline {y}}=\sum \limits _{i=1}^{n}{x_{i}y_{i}}{\pmod {2} }$ ${\widehat {E}}(\xi )=\sum \limits _{x\in E}{e^{-(x\cdot \xi )\pi i}}=\sum \limits _{ x\in E}{(-1)^{x\cdot \xi }}$ $\max \limits _{\xi \not =0}{{\widehat {E}}(\xi ))$ $E$ $\max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}<2^{n}\alpha$ $\alfa$ $E$ $\alfa$

Pentru o mulțime, este logic să luăm în considerare funcția de echilibru , unde este densitatea mulțimii, iar expresia dintre paranteze drepte înseamnă indicatorul apartenenței la mulțime. Pentru funcția de echilibru se determină așa-numita normă dreptunghiulară . Dacă valoarea acestei norme este într-un anumit sens suficient de mică, atunci aceasta înseamnă și apropierea de un set aleatoriu. Dacă , atunci mulțimea se numește -uniformă față de norma dreptunghiulară. $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$ $\alfa$

Descrierea algoritmului

Dovada se face prin contradicție, adică inițial se presupune că mulțimea are o densitate și nu conține colțuri. Dovada este un algoritm de tranziție secvențială de la o mulțime la submulțimea sa conținută în produsul spațiilor de dimensiune mai mică și care au o densitate mai mare acolo. În plus, tranziția conform aceleiași scheme se efectuează de la acest submult la propriul submult, și așa mai departe, până când se găsește o progresie aritmetică în următorul submult (care, evident, își va aparține ). Oprirea algoritmului la un moment dat este garantată de faptul că densitatea mulțimii nu poate depăși unu și trecerea de la setul de densitate la submulțimea sa de densitate (într-un spațiu mai îngust) , astfel încât prin îngustarea submulțimii, algoritmul își finalizează munca. $A$ $\delta$ $A$ $A$ $\delta$ $\delta +2^{-32}\delta ^{24}$ $2^{32}\delta ^{-24}$

Următoarea submulțime este considerată nu numai ca , unde este un anumit subspațiu, ci și mai restrâns, ca , unde mulțimile sunt mulțimi arbitrare, dar având coeficienți Fourier mici. În mod formal, putem fi de acord că , , $A_{i}\subset A$ $A_{i}\subset W_{i}\times W_{i)$ $W_{i}\subset {\mathbb {Z} }_{2}^{n)$ $A_{i}\subset E_{1}^{(i)}\times E_{2}^{(i))$ $E_{1}^{(i)}, E_{2}^{(i)}\subset W_{i)$ $A_{0}=A$ $W_{0}={\mathbb {Z} }_{2}^{n)$ $E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n)$

În plus, vom lua în considerare o etapă separată a algoritmului și vom desemna densitățile mulțimilor ca și . Aceste densități contează și în demonstrație. $E$ $\beta _{1}={\frac {E_{1}^{(i)}}{|W|}}$ $\beta _{2}={\frac {E_{2}^{(i)}}{|W|}}$

În toate cele trei cazuri considerate mai jos, -uniformitatea mulțimilor se înțelege în raport cu spațiul curent $\alfa$ $E$ $W_i$

La fiecare etapă separată a algoritmului, sunt posibile trei cazuri:

Cazul 1

Seturile și sunt -uniforme pentru unii . Setul este -uniform pentru unii . $E_{1}^{(i))$ $E_{2}^{(i))$ $\alpha_{1}$ $\alpha _{1}=\alpha _{1}(\delta,\beta _{1},\beta _{2})$ $A_{i}$ $\alpha_2$ $\alpha _{2}=\alpha _{2}(\delta )$

În acest caz, prezența colțurilor poate fi dovedită la propriu, fără a pătrunde în subseturi. Mai mult, se poate dovedi că setul conține cel puțin colțuri. Aceasta este cea mai bună estimare în ordinea creșterii, deoarece numărul de colțuri, evident, nu poate depăși (la urma urmei, colțul este determinat de trei numere, ). $A$ ${\frac {\delta ^{3}\beta _{1}\beta _{2}}{2}}|W|^{3}$ $|W|^{3}$ $x,y,d\in W$

Cazul 2

Setul nu este -uniform pentru aceeași ca în cazul precedent. $A$ $\alpha_2$ $\alpha_2$

Tooda, se dovedește că este posibil să alegeți submulțimi astfel încât dimensiunea lor să nu fie cu mult mai mică decât dimensiunile (scade de cele mai multe ori, unde este un polinom ), iar densitatea mulțimii între depășește semnificativ densitatea sa între (depășește de unde este un polinom) $F_{1}\subset E_{1}$ $F_{1}\subset E_{2}$ $E_{1},E_{2)$ $p({\frac {1}{\delta )))$ $p$ $A$ $F_{1}\times F_{2)$ $E_{1}\times E_{2)$ $q(\delta )$ $q$

Cazul 3

Una dintre seturi nu este -uniformă (pentru la fel ca în primul caz). $E_{1}^{(i)}, E_{2}^{(i))$ $\alpha_{1}$ $\alpha_{1}$

Rețineți că acest caz nu poate apărea chiar la primul pas, deoarece , și spațiul față de el însuși, desigur, este întotdeauna -uniform. $E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n)$ $0$

În acest caz, se folosește creșterea mulțimii c din pasul anterior și anume, dacă mulțimea are o densitate între , atunci existența unui subspațiu și a unor deplasări ale mulțimilor , astfel încât la trecerea la intersecțiile lor (deplasări) cu acest subspațiu, noile mulțimi unidimensionale se dovedesc a fi -uniforme pentru preselectate arbitrare , iar densitatea noii mulțimi bidimensionale se dovedește a fi nu mai mică de . $A_{i}$ $\delta _{0}+\tau$ $E_{1}^{(i)}\times E_{2}^{(i))$ $W_{i+1}\subset W_{i)$ $E_{1}^{(i)},E_{2}^{(i)},A$ $\sigma$ $\sigma$ $\delta _{0}+{\frac {\tau }{4}}$

Ca și aici, puteți alege , și ca creșterea setului furnizat la pasul anterior al algoritmului. Astfel, reducem doar puțin (de patru ori) rata de creștere a densității mulțimii în cursul algoritmului, dar la fiecare pas asigurăm uniformitatea mulțimilor , iar acest lucru ne permite să afirmăm că cazurile 1 și 2 epuiza toate cazurile posibile. $\sigma$ $\alpha_{1}$ $\tau$ $A$ $\alpha_{1}$ $E_{1}^{(i)}, E_{2}^{(i))$

Pentru grupuri abeliene arbitrare

Ilya Shkredov în 2009 a dovedit o generalizare pentru grupurile abeliene. [unsprezece]

Teorema

Există o constantă absolută astfel încât dacă este un grup abelian , , atunci rezultă din prezența în colț $c>0$ $(G,\circ )$ $A\subset G\times G$ $|A|\geq {\frac {|G|^{2}}{({\log \log {|G|}})^{c)))$ $A$ ${\displaystyle \{(x,y),(x\circ d,y),(x,y\circ d)\))$

Note

↑ M. Ajtai, E. Szemeredi: Sets of lattice points that form no squares, Studia Sci. Matematică. Ungaria. , 9 (1974), 9-11 (link nu este disponibil)
↑ Dovada teoremei colțurilor Arhivat 30 august 2012 la Wayback Machine on polymath
↑ J. Solymosi: Notă despre o generalizare a teoremei lui Roth, Algorithms Combin. , 25 , 2003, Springer, Berlin, 825-827
↑ O nouă demonstrație a teoremei lui Szemeredi . Consultat la 5 iulie 2017. Arhivat din original la 23 ianuarie 2018. (nedefinit)
↑ Vu V. H, Despre o problemă a lui Gowers . Consultat la 5 iulie 2017. Arhivat din original la 9 ianuarie 2018. (nedefinit)
↑ I. D. Shkredov, Despre o problemă a lui Gowers . Consultat la 5 iulie 2017. Arhivat din original la 9 ianuarie 2018. (nedefinit)
↑ ID Shkredov, Despre o generalizare a teoremei lui Szemeredi (preprint) . Consultat la 5 iulie 2017. Arhivat din original la 9 ianuarie 2018. (nedefinit)
↑ Ben Green, „Modele de câmp finit în combinatorică aditivă” . Consultat la 5 iulie 2017. Arhivat din original la 13 iunie 2017. (nedefinit)
↑ Ben Green, „Modele de câmp finit în combinatorică aritmetică” (preprint) . Consultat la 5 iulie 2017. Arhivat din original la 9 ianuarie 2018. (nedefinit)
↑ I. D. Shkredov, Teorema lui Szemeredy și problemele progresiilor aritmetice Arhivat 24 iulie 2018 la Wayback Machine , pp. 147-159
↑ I. D. Shkredov, Pe un analog bidimensional al teoremei Szemeredi în grupuri abeliene . Consultat la 5 iulie 2017. Arhivat din original la 9 ianuarie 2018. (nedefinit)