Roths sats om aritmetiska progressioner

Roths teorem om aritmetiska progressioner är ett resultat i additiv kombinatorik om förekomsten av aritmetiska progressioner i delmängder av de naturliga talen . Det bevisades första gången av Klaus Roth 1953. Roths sats är ett specialfall av Szemerédis sats för fallet $k=3$ .

Påstående

En delmängd A av de naturliga talen sägs ha positiv övre densitet if

\limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0

.

Roths sats om aritmetiska progressioner (oändlig version) : En delmängd av de naturliga talen med positiv övre täthet innehåller en 3-term aritmetisk progression.

En alternativ, mer kvalitativ formulering av satsen handlar om den maximala storleken på en Salem-Spencer-mängd som är en delmängd av $[N]=\{1,\ prickar ,N\}$ . Låt $r_{3}([N])$ vara storleken på den största delmängden av $[N]$ som inte innehåller någon 3-term aritmetisk progression.

Roths sats om aritmetiska progressioner (finitär version) : $r_{3}([N])=o(N)$ .

Att förbättra övre och nedre gränser på $r_{3}([N])$ är fortfarande ett öppet forskningsproblem.

Historia

Det första resultatet i denna riktning var Van der Waerdens teorem 1927, som säger att för tillräckligt stort N, kommer färgning av heltal $1,\dots ,n$ med $r$ färger att resultera i i en $k$ term aritmetisk progression.

Senare 1936 antog Erdős och Turán ett mycket starkare resultat att varje delmängd av heltal med positiv densitet innehåller godtyckligt långa aritmetiska progressioner. 1942 Raphaël Salem och Donald C. Spencer en konstruktion av en 3-AP-fri uppsättning (dvs. en uppsättning utan 3-terms aritmetiska progressioner) av storlek ${ \displaystyle {\frac {N}{e^{O(\log N/\log \log N)}}}} ,$ motbevisar ytterligare en gissning av Erdős och Turán att $r_{3}([N])=N^{1-\delta }$ för vissa $\delta >0$ .

1953 löste Roth delvis den initiala gissningen genom att bevisa att de måste innehålla en aritmetisk progression av längd 3 med Fourier-analytiska metoder. Så småningom, 1975, bevisade Szemerédi Szemerédis sats med hjälp av kombinatoriska tekniker, vilket löste den ursprungliga gissningen i sin helhet.

Bevistekniker

Det ursprungliga beviset från Roth använde Fourier-analysmetoder. Senare gavs ytterligare ett bevis med hjälp av Szemerédis regularitetslemma .

Bevisskiss via Fourieranalys

1953 använde Roth Fourier-analys för att bevisa en övre gräns för $r_{3}([N])=O\left({\frac {N}{\log \log N}}\right)$ . Nedan är en skiss över detta bevis.

Definiera Fouriertransformen av en funktion $f:\mathbb {Z} \rightarrow \mathbb {C}$ för att vara funktionen ${\widehat {f}}$ som uppfyller

{\widehat {f}}(\theta )=\summa _{x\in \mathbb {Z} }f( x)e(-x\theta )

,

där $e(t)=e^{2\pi it}$ .

Låt $A$ vara en 3-AP-fri delmängd av $\{1,\dots ,N\}$ . Beviset fortsätter i 3 steg.

Visa att en $A$ tillåter en stor Fourierkoefficient.
Härleda att det finns en subprogression av $\{1,\dots ,N\}$ så att $A$ har en densitetsökning när den är begränsad till denna subprogression.
Iterera steg 2 för att få en övre gräns på $|A|$ .

Steg 1

För funktioner, $f,g,h:\mathbb {Z} \rightarrow \mathbb {C} ,$ definiera

\Lambda (f,g,h)=\summa _{x ,y\in \mathbb {Z} }f(x)g(x+y)h(x+2y)

Räkna Lemma Låt $f,g:\mathbb {Z} \ högerpil \mathbb {C}$ uppfyller $\sum _{n\in \mathbb {Z} }|f(n)|^{2},\summa _{n\in \mathbb {Z} }|g(n)|^ {2}\leq M$ . Definiera $\Lambda _{3}(f)=\Lambda (f,f,f)$ . Sedan $|\Lambda _{3}(f)-\Lambda _{3}(g)|\leq 3M\|{\widehat {fg}}\|_{ \infty }$ .

Räknelemmat säger oss att om Fouriertransformerna av $f$ och $g$ är "nära", så bör antalet 3-terms aritmetiska progressioner mellan de två också vara "nära". Låt $\alpha =|A|/N$ vara densiteten för $A$ . Definiera funktionerna $f=\mathbf {1} _{A}$ (dvs. indikatorfunktionen för $A$ ), och $g= \alpha \cdot \mathbf {1} _{[N]}$ . Steg 1 kan sedan härledas genom att tillämpa räknelemman på $f$ och $g$ , vilket talar om för oss att det finns någon $\theta$ så att

\left|\sum _{n=1}^{N}(1_{A}-\alpha )(n)e(\theta n)\right|\geq {\frac { \alpha ^{2}}{10}}N

.

Steg 2

Med tanke på $\theta$ från steg 1 visar vi först att det är möjligt att dela upp $[N]$ i relativt stora subprogressioner så att tecknet $x\mapsto e(x\theta )$ är ungefär konstant på varje subprogression.

Lemma 1: Låt $0<\eta <1,\theta \in \mathbb {R}$ . Antag att $N>C\eta ^{-6}$ för en universell konstant $C$ . Sedan är det möjligt att dela upp $[N]$ i aritmetiska följder $P_{i}$ med längden $N^{1/3}\leq |P_{i}|\leq 2N^{1/3}$ ${\displaystyle \sup _{x,y\in P_{i}}|e(x\theta )-e(y\theta )|<\eta } för alla i {\$ att displaystyle $}$ .

Därefter tillämpar vi Lemma 1 för att få en partition i subprogressioner. Vi använder sedan det faktum att $\theta$ producerade en stor koefficient i steg 1 för att visa att en av dessa subprogressioner måste ha ett densitetsökning:

Lemma 2: Låt $A$ vara en 3-AP-fri delmängd av $[N]$ , med $|A|=\alpha N$ och $N>C\alpha ^{-12}$ . Sedan finns det en subprogression $P\subset [N]$ så att $|P|\geq N^{1/3}$ och $|A\cap P|\geq (\alpha +\alpha ^{2}/40)|P|$ .

Steg 3

Vi itererar nu steg 2. Låt $a_{t}$ vara densiteten för $A$ efter ${\displaystyle t}:$ te iterationen. Vi har att $\alpha _{0}=\alpha ,$ och $\alpha _{t+1}\geq \alpha + \alpha ^{2}/40.$ Se först att $\alpha$ fördubblas (dvs. når $T$ så att $\alpha _{T}\geq 2 \alpha _{0}$ ) efter högst $40/\alpha +1$ steg. Vi dubblar $\alpha$ igen (dvs når $\alpha _{T}\geq 4\alpha _{0}$ ) efter högst $20 /\alpha +1$ steg. Eftersom $\alpha \leq 1$ måste denna process avslutas efter högst $O(1/\alpha )$ steg.

Låt $N_{t}$ vara storleken på vår nuvarande progression efter $t$ iterationer. Genom Lemma 2 kan vi alltid fortsätta processen närhelst $N_{t}\geq C\alpha _{t}^{-12},$ och alltså när processen avslutas har att ${\displaystyle N_{t}\leq C\alpha _{t}^{-12}\leq C\alpha ^{-12}.} Observera också att när vi går över till en subprogression, minskar storleken på vår$ uppsättning av en kubrot. Därför

N\leq N_{t}^{3^{t}}\leq (C\alpha ^{-12})^{3^{O(1/\alpha )}}=e^{e^ {O(1/\alpha )}}.

Därför $\alpha =O(1/\log \log N),$ så $|A|=O\left({\frac {N}{\log \log N}}\right),$ enligt önskemål. $\blacksquare$

Tyvärr generaliserar denna teknik inte direkt till större aritmetiska progressioner för att bevisa Szemerédis teorem. En förlängning av detta bevis gäckade matematiker i årtionden fram till 1998, när Timothy Gowers utvecklade området för Fourieranalys av högre ordning specifikt för att generalisera ovanstående bevis för att bevisa Szemerédis teorem.

Bevisskiss via grafregelbundenhet

Nedan är en översikt över ett bevis som använder Szemerédi regularity lemma .

Låt $G$ vara en graf och $X,Y\subseteq V(G)$ . Vi kallar $(X,Y)$ ett $\epsilon$ -reguljärt par om för alla $A\subset X,B\subset Y$ med ${\displaystyle |A|\geq \epsilon |X|,|B|\geq \epsilon |Y|} ,$ man har $|d(A,B)-d(X,Y)|\leq \epsilon$ .

En partition ${\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}$ av $V (G)$ är en $\epsilon$ -vanlig partition if

\sum _{(i,j)\in [k]^{2},(V_{i},V_{j}){\text{ inte }}\epsilon {\text{-regular} }}|V_{i}||V_{j}|\leq \epsilon |V(G)|^{2}

.

Sedan säger Szemerédi regularitetslemma att för varje $\epsilon >0$ finns det en konstant $M$ så att varje graf har en $\epsilon$ -regular partition i högst $M$ delar.

Vi kan också bevisa att trianglar mellan $\epsilon$ -regelbundna uppsättningar av hörn måste komma tillsammans med många andra trianglar. Detta är känt som triangelräknelemmat.

Triangel Counting Lemma: Låt $G$ vara en graf och $X,Y,Z$ vara delmängder av hörnen på $G$ så att $(X,Y),(Y,Z),(Z,X)$ är alla $\epsilon$ -regelbundna par för vissa $\epsilon >0$ . Låt $d_{XY},d_{XZ},d_{YZ}$ beteckna kantdensiteterna $d(X,Y),d(X,Z),d(Y,Z)$ respektive. Om ${\displaystyle d_{XY},d_{XZ},d_{YZ}\geq 2\epsilon } ,$ då antalet trippel $(x,y,z)\in X\times Y\times Z$ så att $x,y,z$ bildar en triangel i ${\ displaystyle G}$ är minst

$(1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )\cdot |X||Y||Z|$ .

Med hjälp av triangelräknelemmat och Szemerédi-regelbundenhetslemma kan vi bevisa triangelborttagningslemma, ett specialfall av grafborttagningslemma .

Lemma för borttagning av triangel: För alla $\epsilon >0$ finns det $\delta >0$ så att vilken graf som helst på $n$ hörn med mindre än eller lika med $\delta n^{3}$ trianglar kan göras triangelfria genom att ta bort högst $\epsilon n^{2}$ kanter.

Detta har en intressant följd som hänför sig till graferna $G$ på $N$ hörn där varje kant av $G$ ligger i en unik triangel. Mer specifikt måste alla dessa grafer ha $o(N^{2})$ kanter.

Ta en uppsättning $A$ utan 3-terms aritmetiska progressioner. Konstruera nu en tredelad graf $G$ vars delar $X,Y,Z$ alla är kopior av $\mathbb {Z} / (2N+1)\mathbb {Z}$ . Anslut ett vertex $x\in X$ till ett vertex $y\in Y$ om $yx\in A$ . På liknande sätt kopplar du $z\in Z$ med $y\in Y$ om $zy\in A$ . Slutligen, anslut $x\in X$ med $z\in Z$ if $(zx)/2\in A$ .

Denna konstruktion är uppställd så att om $x,y,z$ bildar en triangel så får vi elementen $yx,{\frac {zx}{2}},zy$ att alla tillhör $A$ . Dessa siffror bildar en aritmetisk progression i listad ordning. Antagandet på $A$ talar om för oss att denna utveckling måste vara trivial: elementen som listas ovan är alla lika. Men detta villkor är ekvivalent med påståendet att $x,y,z$ är en aritmetisk progression i $\mathbb {Z} /(2N+1 )\mathbb {Z}$ . Följaktligen ligger varje kant av ${\displaystyle G} i exakt en triangel.$ Den önskade slutsatsen följer. $\blacksquare$

Tillägg och generaliseringar

Szemerédis teorem löste den ursprungliga gissningen och generaliserade Roths teorem till aritmetiska progressioner av godtycklig längd. Sedan dess har det utökats på flera sätt för att skapa nya och intressanta resultat.

Furstenberg och Katznelson använde ergodisk teori för att bevisa en flerdimensionell version och Leibman och Bergelson utvidgade den till polynomprogressioner också. Senast Green och Tao bevisade Green-Tao-satsen som säger att primtalen innehåller godtyckligt långa aritmetiska progressioner. Eftersom primtalen är en delmängd av densitet 0, introducerade de en "relativ" Szemerédi-sats som gäller delmängder med densitet 0 som uppfyller vissa pseudoslumphetsvillkor. Senare Conlon , Fox och Zhao denna teorem genom att försvaga det nödvändiga pseudoslumpmässiga tillståndet. År 2020 bevisade Bloom och Sisask att varje uppsättning $A$ så att $\sum _{n\in A}{\frac {1}{n}}$ avviker måste innehålla aritmetiska progressioner av längd 3; detta är det första icke-triviala fallet av en annan gissning av Erdős som postulerar att en sådan mängd faktiskt måste innehålla godtyckligt långa aritmetiska progressioner.

Förbättra gränser

Det har också gjorts arbete med att förbättra bunden i Roths teorem. Bindningen från det ursprungliga beviset för Roths teorem visade det

r_{3}([N])\leq c\cdot {\frac {N}{\log \log N}}

för någon konstant $c$ . Under åren har denna gräns kontinuerligt sänkts av Szemerédi, Heath-Brown , Bourgain och Sanders . Den nuvarande (juli 2020) bästa gränsen beror på Bloom och Sisask som har visat att det finns en absolut konstant c>0 så att

r_{3}([N])\leq {\frac {N}{(\log N)^{1+c}}}.

I februari 2023 gav ett förtryck av Kelley och Meka en ny gräns

r_{3}([N])\leq 2^{-O((\log N)^{c} )}\cdot N

.

och fyra dagar senare förenklade Bloom och Sisask resultatet och med en liten förbättring till $r_{3}([N] )\leq \exp(-c(\log N)^{1/11})N$ .

Det har också gjorts arbete i andra änden, att konstruera den största uppsättningen utan tre-terms aritmetiska progressioner. Den bästa konstruktionen har inte förbättrats sedan 1946 när Behrend förbättrade den ursprungliga konstruktionen av Salem och Spencer och bevisade

r_{3}([N])\geq N\exp(-c{\sqrt {\log N}})

.

På grund av inga förbättringar på över 70 år, förmodas det att Behrands uppsättning är den största möjliga uppsättningen utan tre terminer.

Roths sats i ändliga fält

Som en variation kan vi betrakta det analoga problemet över ändliga fält. Betrakta det finita fältet $\mathbb {F} _{3}^{n}$ , och låt $r_{3}(\mathbb {F} _{3 }^{n})$ vara storleken på den största delmängden av $\mathbb {F} _{3}^{n}$ som inte innehåller någon 3-term aritmetisk progression. Detta problem är faktiskt likvärdigt med cap-mängdproblemet , som frågar efter den största delmängden av $\mathbb {F} _{3}^{n}$ så att inga 3 punkter ligger på en linje. Cap set problemet kan ses som en generalisering av kortspelet Set .

1982 var Brown och Buhler de första som visade att $r_{3}(\mathbb {F} _{3}^{n})=o(3^{n}).$ 1995 använde Roy Mesuhlam en liknande teknik som det Fourieranalytiska beviset för Roths sats för att visa att ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O\left({\frac {3^{n}}{n}}\right).} Denna gräns har$ förbättrats till $O(3^{n}/n^{1+\epsilon })$ 2012 av Bateman och Katz.

2016 utvecklade Ernie Croot , Vsevolod Lev, Péter Pál Pach, Jordan Ellenberg och Dion Gijswijt en ny teknik baserad på polynommetoden för att bevisa att $r_{3} (\mathbb {F} _{3}^{n})=O(2,756^{n})$ .

Den mest kända nedre gränsen är ungefär ${\displaystyle 2.218^{n}} ,$ given 2022 av Tyrrell.

Roths sats med populära skillnader

En annan generalisering av Roths sats visar att det för positiva densitetsundermängder inte bara existerar en 3-term aritmetisk progression, utan att det finns många 3-AP:er alla med samma gemensamma skillnad.

Roths teorem med populära skillnader: För alla $\epsilon >0$ finns det några $n_{0}=n_{0}(\epsilon )$ så att för varje $n>n_{0}$ och $A\subset \mathbb {F} _{3}^{n}$ med $|A|=\alpha 3^{n},$ det finns några $y\neq 0$ så att $|\{x:x,x+y,x+2y\in A\}|\geq (\alpha ^{3}-\epsilon )3^{n}.$

Om $A$ väljs slumpmässigt från $\mathbb {F} _{3}^{n},$ så skulle vi förvänta oss att det finns $\alpha ^ {3}3^{n}$ progressioner för varje värde på $y$ . Den populära skillnadssatsen säger alltså att för varje $|A|$ med positiv densitet finns det någon $y$ så att antalet 3-AP:er med gemensam skillnad $y$ är nära vad vi skulle förvänta oss.

Denna sats bevisades första gången av Green 2005, som gav en gräns för $n_{0}={\text{släp}}((1/\ epsilon )^{O(1)}),$ där ${\text{släp}}$ är tornfunktionen. Under $n_{0}={\text{tow}}(O(\log {\frac {1}{\epsilon }})).$ förbättrade Fox och Pham nyligen gränsen till

Ett motsvarande påstående är också sant i $\mathbb {Z}$ för både 3-AP:er och 4-AP:er. Påståendet har dock visat sig vara falskt för 5-AP:er.

externa länkar

Edmonds, Chelsea; Koutsoukou-Argyraki, Angeliki; Paulson, Lawrence C. Roth's Theorem on Arithmetic Progressions (Formell bevisutveckling i Isabelle/HOL, Archive of Formal Proofs)