Hörnsats

Hörnsatsen är ett bevisat resultat i additiv kombinatorik som anger närvaron av någon ordnad (i aritmetisk mening) struktur som kallas ett hörn i tillräckligt stora tvådimensionella uppsättningar av vilken fast densitet som helst.

För naturliga tal talar vi faktiskt om att tillhöra en tillräckligt tät uppsättning celler på ett tvådimensionellt gitter med två ändar och en brytpunkt i en rät vinkel med sidor av samma längd parallella med koordinataxlarna.

Formulering

Satsen avser ett tvådimensionellt gitter och beaktar uppsättningar av talpar (koordinater i ett tvådimensionellt utrymme). För naturliga tal, låt oss kalla trippeln av koordinater för ett hörn. Vi kommer att säga att en uppsättning innehåller något hörn om den innehåller alla tre punkter i detta hörn. $x,y,d\ (d\not =0)$ $\{{(x,y),(x+d,y),(x,y+d)}\}$

För en delmängd av ett tvådimensionellt gitter definierar vi dess densitet som , det vill säga som andelen celler som tillhör uppsättningen bland hela gittret. $A\subset \{{1,\dots ,N}\}^{2}$ ${\displaystyle {\rho _{N}}(A)={\frac {|A|}{N^{2))))$

Hörnsats

För alla finns det så att om uppsättningen har densitet , så innehåller den ett hörn. $\delta$ $N=N(\delta )$ $A\subset \{{1,\dots ,N}\}^{2}$ $\rho _{N}(A)\geq \delta$

Historik för att förbättra resultat

Hörnsatsen bevisades [1] [ 2] av Miklos Ajtai och Endre Szemeredy 1974-1975 . År 1981 motbevisades detta resultat av Hillel Furstenberg med hjälp av metoderna för ergodisk teori . Det finns också [3] ett bevis av Jozsef Solymosi ( Hung. Jozsef Solymosi ), baserat på lemmat om att ta bort en triangel från en graf .

Förutom det faktum att förekomsten av , som är tillräcklig för att varje kvadratisk densitetsuppsättning ska innehålla ett hörn, är det också lämpligt att överväga tillväxtordningen för funktionen , eller omvänt, som den maximala densiteten för en given , för vilken delmängd utan hörn är möjlig. $N=N(\delta )$ $\delta$ ${\displaystyle \{1,\dots ,N\}^{2))$ $N(\delta )$ $\delta (N)$ $\delta$ $N$

Om den betecknas som tätheten av den maximala delmängden av kvadraten som inte innehåller några hörn, då är huvudhörnsatsen ekvivalent med påståendet att , och det är lämpligt att överväga den mer allmänna frågan om att förbättra övre gränser på . Denna fråga ställdes först [4] av William Timothy Gowers 2001. $L(N)$ ${\displaystyle \{1,\dots ,N\}^{2))$ $L(N)=o(1)$ $L(N)$

År 2002 bevisade Wu Ha Wang [5] att , där är inversen av tetration till bas 2 i samma mening som den naturliga logaritmen är inversen av exponenten . ${\displaystyle L(N)\leq {\frac {100}{(\log _{*}(N))^{1/4))))$ $\log _{*}$

Under 2005–2006 förbättrade Ilya Shkredov denna uppskattning [6] , först till , och sedan [7] till , där och är några absoluta konstanter. $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}$

Samband med Roths teorem

Hörnsatsen kan betraktas som en tvådimensionell analog till Roths sats (ett specialfall av Szemeredis sats för längdprogressioner ), eftersom det i problemformuleringen är likheten mellan de två "sidorna" av ett rektangulärt hörn som är viktigt, precis som i definitionen av en aritmetisk progression , är likheten mellan två skillnader mellan närliggande tal viktig. $3$

Roths teorem (1953)

För alla finns det så att om mängden har en densitet , så innehåller den en aritmetisk progression, det vill säga en trippel av tal för några och . $\delta$ $N=N(\delta )$ $A\subset \{{1,\dots ,N}\}$ ${\frac {|A|}{N}}>\delta$ $\{ad,a,a+d\}$ $a$ $d\not=0$

Roths teorem kan härledas från hörnsatsen som en direkt konsekvens.

Bevis

För att bevisa motsatsen, anta att hörnsatsen är sann och Roths sats inte är sann, det vill säga att det finns en densitet så att vem som helst kan hitta en delmängd av sådan densitet som inte innehåller en aritmetisk progression, utan en liknande densitet att täcka en kvadrat av godtycklig storlek utan hörnbildning finns inte. Vi måste, utifrån detta, komma till en motsägelse. $\delta>0$ $N$ $A\subset \{1,\dots ,N\}$

Betrakta en sådan mängd för en godtycklig och konstruera från den en tvådimensionell delmängd av kvadraten av storlek , som kommer att vara ett motexempel för hörnsatsen, det vill säga den kommer att ha en känd densitet som inte är noll och bör inte innehålla hörn . $N$ $A\subset \{1,\dots ,N\}$ $(|A|>\delta N)$ $2N$

En sådan uppsättning kommer att vara en uppsättning av formen , det vill säga en sekvens av linjer som representerar successiva förskjutningar av uppsättningen . Om det fanns ett hörn i en sådan uppsättning skulle detta innebära att mängden hade en aritmetisk längdförlopp , eftersom den är konstruerad på ett sådant sätt att om , då och , och sedan, förutom hörnet, innehåller den en trippel som mappar den aritmetiska progressionen till en specifik linje. $X=\{(a+(i-1),i):i\i {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)$

Vårt ursprungliga antagande var dock att det inte finns några sådana framsteg. Så det finns inga hörn. Betrakta nu densiteten i kvadrat . Eftersom det bara finns förskjutningar och alla ingår i uppsättningen helt, är densiteten lika med . $A$ $X$ $X$ ${\displaystyle \{1,\dots ,2N\}^{2))$ $N$ ${\frac {N|A|}{(2N)^{2}}}>{\frac {\delta N^{2}}{4N^{2}}}={\frac {\delta }{fyra}}$

Så vi har lärt oss hur man bygger en densitetsuppsättning som inte innehåller några hörn i en kvadrat av någon storlek. Detta motsäger dock vårt ursprungliga antagande att hörnsatsen är sann. ${\frac {\delta }{4}}$

Generalisering för grupper

Förutom visuellt representativa hörn på gittret , kan man överväga generaliserade "hörn" av formen , där , och är någon grupp med operationen . ${\displaystyle \{1,\dots ,N\}^{2))$ $\{(x,y),(x\circ d,y),(x,y\circ d)\}$ $x,y,d\in G$ $G$ $\cirkel$

För utrymme ${\displaystyle {\mathbb {Z} }_{2}^{n))$

Ben Green 2005 övervägde [8] [9] [10] frågan om hörn i gruppen , d.v.s. inte för uppsättningen naturliga tal. och för uppsättningen av bitar (bestående av nollor och ettor) sekvenser av längd , för vilka bitvis exklusiva eller används istället för addition . ${\displaystyle {\mathbb {Z} }_{2}^{n))$ $n$

Teorem (Greene, 2005)

För alla , finns det sådana att om mängden har en densitet , så innehåller den ett hörn av formen , där , och tillägget görs 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))$

Allmänt bevisschema för

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

Enhetlighetsindikatorer

Beviset använder två indikatorer på enhetligheten i fördelningen av mängder - en för "endimensionella" delmängder och den andra för "tvådimensionella" , där ${\displaystyle E\subset {\mathbb {Z} }_{2}^{n))$ ${\displaystyle A\subset E_{1}\ gånger E_{2))$ ${\displaystyle E_{1},E_{2}\subset {\mathbb {Z} }_{2}^{n))$

Som en indikator på enhetlighet för endimensionella mängder används en speciellt anpassad Fourier-transform , där rötter från enhet används som koefficienter och en analog av formens skalära produkt används i stället för multiplikation . Om , så betyder ett litet värde på sätt och vis att mängden är nära någon slumpmässigt fördelad mängd med samma densitet, vilket betyder att det finns fler strukturerade delmängder i den än i många andra. Om för vissa sägs uppsättningen vara -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 }}$ ${\displaystyle \max \limits _{\xi \not =0}{{\widehat {E}}(\xi )))$ $E$ $\max \limits _{\xi \not =0}{{\widehat {E}}(\xi )}<2^{n}\alpha$ $\alfa$ $E$ $\alfa$

För en uppsättning är det vettigt att överväga balansfunktionen , där är mängdens täthet, och uttrycket inom hakparenteser betyder indikatorn på att tillhöra mängden. För balansfunktionen bestäms den så kallade rektangulära normen . Om värdet av denna norm i någon mening är tillräckligt litet, betyder det också närhet till en slumpmässig mängd. Om , då kallas mängden -uniform med avseende på den rektangulära normen. $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}=\summa \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$

Beskrivning av algoritmen

Beviset görs genom motsägelse, det vill säga att det initialt antas att mängden har en densitet och inte innehåller hörn. Beviset är en algoritm för sekventiell övergång från en mängd till dess delmängd som ingår i produkten av utrymmen med lägre dimension och som har en högre densitet där. Vidare utförs övergången enligt samma schema från denna delmängd till sin egen delmängd, och så vidare, tills en aritmetisk progression hittas i nästa delmängd (som uppenbarligen kommer att tillhöra sig själv ). Att stoppa algoritmen vid någon tidpunkt garanteras av det faktum att densiteten för mängden inte kan överstiga en, och övergången från densitetsuppsättningen till dess densitetsdelmängd (i något smalare utrymme) , så att algoritmen genom avsmalningen av delmängden slutför sitt arbete. $A$ $\delta$ $A$ $A$ $\delta$ $\delta +2^{-32}\delta ^{24}$ $2^{32}\delta ^{-24}$

Nästa delmängd betraktas inte bara som , där är något delrum, utan också mer snävt, som , där mängder är godtyckliga mängder, men som har små Fourierkoefficienter. Formellt kan vi komma överens om att , , $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))$

Vidare kommer vi att överväga ett separat steg i algoritmen och beteckna densiteterna för uppsättningar som och . Dessa tätheter spelar också roll i beviset. $E$ $\beta _{1}={\frac {E_{1}^{(i)}}{|W|}}$ $\beta _{2}={\frac {E_{2}^{(i)}}{|W|}}$

I alla tre fall som behandlas nedan menas -likformighet av mängder med avseende på det aktuella utrymmet $\alfa$ $E$ $W_i$

I varje separat steg av algoritmen är tre fall möjliga:

Fall 1

Uppsättningarna och är -uniforma för vissa . Setet är enhetligt för vissa . ${\displaystyle E_{1}^{(i)))$ ${\displaystyle E_{2}^{(i)))$ $\alpha_{1}$ $\alpha _{1}=\alpha _{1}(\delta ,\beta _{1},\beta _{2})$ $A_{i}$ $\alfa_2$ $\alpha _{2}=\alpha _{2}(\delta )$

I det här fallet kan närvaron av hörn bevisas bokstavligen, utan att fördjupa sig i delmängder. Dessutom kan det bevisas att setet innehåller åtminstone hörn. Detta är den bästa uppskattningen i tillväxtordning, eftersom antalet hörn uppenbarligen inte kan överstiga (trots allt bestäms hörnet av tre siffror, ). $A$ ${\frac {\delta ^{3}\beta _{1}\beta _{2}}{2}}|W|^{3}$ $|W|^{3}$ $x,y,d\in W$

Fall 2

Uppsättningen är inte -uniform för samma som i föregående fall. $A$ $\alfa_2$ $\alfa_2$

Dessutom visar det sig att det är möjligt att välja delmängder så att deras storlek inte är mycket mindre än storlekarna (minskar med vid de flesta tillfällen, där är ett polynom ), och densiteten för mängden bland avsevärt överstiger dess densitet bland (överstiger var är ett polynom ) $F_{1}\subset E_{1}$ $F_{1}\subset E_{2}$ ${\displaystyle E_{1},E_{2))$ $p({\frac {1}{\delta )))$ $sid$ $A$ $F_{1}\times F_{2}$ $E_{1}\times E_{2}$ $q(\delta)$ $q$

Fall 3

En av uppsättningarna är inte -uniform (för samma som i det första fallet). ${\displaystyle E_{1}^{(i)},E_{2}^{(i)))$ $\alpha_{1}$ $\alpha_{1}$

Observera att detta fall inte kan uppstå i det allra första steget, eftersom , och utrymmet med avseende på sig självt, naturligtvis, alltid är -enhetligt. ${\displaystyle E_{1}^{(0)}=E_{2}^{(0)}={\mathbb {Z} }_{2}^{n))$ $0$

I det här fallet används tillväxten av mängden c i föregående steg, nämligen om mängden har en densitet bland , då förekomsten av något delrum och några skiftningar av uppsättningarna , så att när de passerar till deras (skift) skärningspunkter med detta delutrymme visar sig de nya endimensionella uppsättningarna vara -uniforma för godtyckliga förvalda , och densiteten för den nya tvådimensionella uppsättningen visar sig inte vara mindre än . $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))$

Som här kan du välja , och som ökningen av uppsättningen som tillhandahålls i föregående steg i algoritmen. Således minskar vi endast något (fyra gånger) ökningshastigheten i mängdens täthet under algoritmens gång, men vid varje steg säkerställer vi enhetligheten i uppsättningarna , och detta gör att vi kan hävda att fall 1 och 2 uttömma alla möjliga fall. $\sigma$ $\alpha_{1}$ $\tau$ $A$ $\alpha_{1}$ ${\displaystyle E_{1}^{(i)},E_{2}^{(i)))$

För godtyckliga Abeliska grupper

Ilya Shkredov 2009 visade sig vara en generalisering för abelska grupper. [elva]

Sats

Det finns en absolut konstant sådan att om är en abelsk grupp , , så följer den av närvaron i hörnet $c>0$ $(G,\cirkel)$ $A\subset G\times G$ ${\displaystyle |A|\geq {\frac {|G|^{2}}{({\log \log {|G|}})^{c))))$ $A$ $\{(x,y),(x\circ d,y),(x,y\circ d)\}$

Anteckningar

↑ M. Ajtai, E. Szemeredi: Uppsättningar av gitterpunkter som inte bildar några kvadrater, Studia Sci. Matematik. hungar. , 9 (1974), 9-11 (länk ej tillgänglig)
↑ Bevis för hörnsatsen Arkiverad 30 augusti 2012 på Wayback Machine på polymath
↑ J. Solymosi: Anmärkning om en generalisering av Roths sats, Algorithms Combin. , 25 , 2003, Springer, Berlin, 825-827
↑ Ett nytt bevis för Szemeredis sats . Hämtad 5 juli 2017. Arkiverad från originalet 23 januari 2018. (obestämd)
↑ Vu V. H, Om en fråga om Gowers . Hämtad 5 juli 2017. Arkiverad från originalet 9 januari 2018. (obestämd)
↑ I. D. Shkredov, On a problem of Gowers . Hämtad 5 juli 2017. Arkiverad från originalet 9 januari 2018. (obestämd)
↑ ID Shkredov, om en generalisering av Szemeredis sats (förtryck) . Hämtad 5 juli 2017. Arkiverad från originalet 9 januari 2018. (obestämd)
↑ Ben Green, "Finita fältmodeller i additiv kombinatorik" . Hämtad 5 juli 2017. Arkiverad från originalet 13 juni 2017. (obestämd)
↑ Ben Green, "Finita fältmodeller i aritmetisk kombinatorik" (förtryck) . Hämtad 5 juli 2017. Arkiverad från originalet 9 januari 2018. (obestämd)
↑ I. D. Shkredov, Szemeredys teorem och problem om aritmetiska progressioner Arkiverad 24 juli 2018 på Wayback Machine , s. 147-159
↑ I. D. Shkredov, Om en tvådimensionell analog av Szemeredis sats i Abelska grupper . Hämtad 5 juli 2017. Arkiverad från originalet 9 januari 2018. (obestämd)