Roths teorem är ett resultat av additiv kombinatorik , ett specialfall av Szemeredis sats för progressioner av längd 3; hävdar närvaron av aritmetiska progressioner i alla tillräckligt täta uppsättningar.
Den exakta formuleringen är: för alla , alla uppsättningar som har en asymptotisk densitet innehåller en aritmetisk progression av längd 3.
Liknande formuleringar som använder de övre och nedre asymptotiska tätheterna är ekvivalenta med [1] .
Formuleringen för finita mängder är också likvärdig med den ursprungliga: för alla finns det sådana att om , och , innehåller sedan en aritmetisk progression av längd 3. Den överväldigande majoriteten av bevis bevisar formuleringen för finita mängder.
Maximal delmängdsstorlek
utan progressioner av längd 3 | ||
---|---|---|
Utgivningsår | Storlek (upp till en konstant) |
Författarna) |
1953 | Mun [2] | |
1987 | Heath-Brown [3] [4] | |
1999 | Bourgain [5] | |
2008 | Bourgain [6] | |
2012 | Sanders [7] | |
2011 | Sanders [8] | |
2014 | Bloom [9] | |
2020 (förtryck) | Shoen [10] | |
2020 (förtryck) | Bloom, Sisask [11] |
Teoremet bevisades första gången 1953 av Klaus Roth [2] [12] genom att anpassa Hardy-Littlewood-cirkelmetoden. Beviset använde idén [13] , som sedan generaliserades för det allmänna beviset för Szémeredis sats: alla uppsättningar av en given densitet är uppdelade i två grupper - "uniform" och "icke-uniform", och "likformighet" betyder en övre bunden på Fourierkoefficienterna . Om mängden är enhetlig kan närvaron av progressioner i den bevisas direkt, annars är det möjligt att bevisa förekomsten av en subprogression där mängdens täthet är större än i segmentet av den naturliga serie som den tillhör .
Metoden låter dig härleda en uppskattning . De tekniska detaljerna i beviset, gränsen på Fourier-koefficienterna som definierar "likformighet" och de resulterande konstanterna kan skilja sig från källa till källa.
Beviset för Roths teorem kan härledas [14] som ett specialfall av Szemeredys teorem från Szemeredys bevis. Detta sätt att bevisa kräver användning av Szémerédys regularitetslemma och hörnsatsen , varifrån Roths sats följer direkt. Det är till och med möjligt [15] att avstå från användningen av hörnsatsen, och härleda Roths sats direkt från triangelborttagningslemma , men bara i formuleringen för ändliga cykliska grupper (se avsnittet "Generaliseringar till olika grupper").
Eftersom Szemeredis regelbundenhetslemma ger extremt stora övre gränser för värdet som erhålls genom det (åtminstone, torn av exponenter ), tillåter metoden i sig inte att erhålla bättre gränser än dessa.
Ronald Graham ger i sin bok om Ramsey-teorin en förenklad version av beviset, även det baserat på Szemeredi-metoden, men utan att använda regularitetslemma. Beviset använder generaliserade aritmetiska progressioner av formen , vilket är mycket lättare att bevisa närvaron av i mängden, och från detta är själva Roth-satsen redan härledd.
Grahams bevis ger inte uppskattningar för , utan visar bara existensen, eftersom det använder existensen av en punkt i sekvensen, från vilken alla punkter är tillräckligt nära gränsen , men bara existensen är också bevisad för gränsen, och karaktären av konvergens analyseras i princip inte.
Tillsammans med att hitta övre gränser för storleken på en mängd utan aritmetiska progressioner, finns det också ett omvänt problem – att konstruera den största möjliga mängden som inte innehåller aritmetiska progressioner, det vill säga ett motexempel för att beteckna gränserna för förbättring av uppskattningar på . Alla kända konstruktioner av sådana uppsättningar är baserade på idén om att överväga enskilda siffror av siffror i ett visst talsystem och ställa in villkor för värdena för dessa siffror.
Det första exemplet på en uppsättning utan progressioner gavs 1936 av Erdős och Turan, som föreslog att man skulle överväga siffror som i det ternära systemet endast innehåller siffrorna 0 och 2. En sådan uppsättning innehåller bara siffror, vilket är mycket litet jämfört med det övre gräns. [16]
Bevis på konstruktionens riktighetLåt --- Erdős--Turan ställa in.
Om och , då i det ternära systemet i den mest signifikanta siffran , där dessa siffror är olika, är likheter uppfyllda . Därför, i en aritmetisk progression , skulle vara uppfylld , och därmed, .
Salem och Spencer generaliserade 1942 idén om Erdős och Turan till nummersystem med en växande (beroende på uppsättningens storlek) bas och fick en uppsättning utan storleksförlopp . [17]
Kort beskrivning av designenI Erdős-Turan-konstruktionen är det fullt möjligt att tillåta siffrorna 0 och 1 istället för 0 och 2 (då kommer platsen för mittentalet i progressionen att ta en större plats i korrekthetsbeviset). I analogi med detta ansåg Salem och Spencer i det -ary-systemet siffror som endast innehåller siffror från 0 till , och lika många förekomster av varje siffra (med asymptotik kan det betraktas som udda, och det totala antalet siffror --- dividera ).
Förekomsten av progressioner blockeras av villkoret om förekomsten av enskilda siffror. Faktum är att om bäraren inte används under addition kan alla nollor i (och därmed i ) bara bildas genom att lägga till nollor från motsvarande siffror och . Vidare, genom induktion, kan vi bevisa sammanträffandet av positionerna för alla ettor, tvåor, etc. och komma till slutsatsen att .
Den angivna poängen erhålls genom att överväga .
År 1946 lade Behrend till en geometrisk tolkning genom att associera siffrorna i siffrorna med koordinaterna för punkter i ett flerdimensionellt utrymme och överväga siffrorna som i denna mening motsvarar punkterna i en sfär . Detta gjorde det möjligt att konstruera en progressionsfri uppsättning storlek . [arton]
Kort beskrivning av designenAlla tal med siffror som inte är större än -är representation delas in i grupper med samma värden . Den största av dessa grupper väljs som en uppsättning och dess storlek uppskattas enligt Dirichlet-principen .
På grund av de begränsade siffrorna, när sådana siffror läggs till, sker ingen överföring av siffror , så progressioner av längd 3 har också en geometrisk tolkning (som punkter på samma linje). Men eftersom bollen är en strikt konvex kropp , kan sfären, som dess gräns, inte innehålla tre punkter på en rak linje. Av detta följer att det inte finns några progressioner i den valda uppsättningen.
Uppsättningens storlek uppskattas bäst till
Därefter ökades Behrends uppskattning med en logaritmisk faktor genom en liten förfining av metoden [19] , men det finns inga signifikant bättre resultat från och med 2019.
Eftersom övre gränser av liknande typ är kända för vissa generaliseringar av Roths teorem [20] [21] finns det skäl att tro att Behrends gräns är skarp.
Både beviset genom harmonisk analys och det speciella sättet på vilket Szemeredis lemma tillämpas bevisar inte själva satsen, utan dess "cykliska" version.
För alla finns det sådana att if , och , då innehåller trippeln , där addition förstås som modulo addition |
De progressioner som utlovas av denna formulering kan vara progressioner i men inte i (till exempel ). Men Roths teorem följer uppenbarligen av det om vi betraktar mängden som en uppsättning rester i . Detta ändrar endast densiteten med en konstant, men gör alla progressioner lämpliga för . Därför är detta teorem ekvivalent med Roths huvudsats.
Följande sats, som till sin idé liknar Roths sats, följer inte av den och antyder den inte, men är av intresse för en separat studie.
Låt några fixas . Sedan för någon det finns sådan att om , då |
Teoremet för grupper bevisades först av Brown och Bahler 1982 [22] , men de bevisade bara att för mängder utan aritmetiska progressioner förblev , men mer exakta begränsningar på en öppen fråga.
1993 (publicerad 1995) bevisade Roy Meshulam [23] att . Hans bevis betraktade godtyckliga grupper och deras karaktärer . Det finns också mer förenklade [24] versioner av detta bevis, uteslutande för , som, med hjälp av Fourier-koefficienterna i , direkt generaliserar idéer från det analytiska beviset för Roths teorem. Beviset är tekniskt sett ännu enklare än beviset för Roths sats själv, så [24] [25] ges ofta som det första exemplet på att tillämpa metoden.
2012, Bateman och Katz, med tanke på fallet , bevisade [26] existensen av en absolut konstant , så att utan aritmetiska progressioner, .
Under 2016 bevisade Krut, Lev och Pach [27] för fallet att för set utan progressioner. Ellenberg och Gijswijt, generaliserande metoden för Krut, Löw och Pach, med hjälp av polynomalgebra , bevisade [28] [29] existensen för var och en av en helt enkelt konstant sådan att om den inte innehåller progressioner av längd 3. I deras artikel , . I synnerhet för fallet . Under antagandet följer det från optimeringen av funktionen att , där är en absolut konstant, vilket är lösningen av ekvationen , det vill säga , där
Nedre gränserDet bästa [28] från 2016 konstruktion-motexempel tillåter [30] att konstruera uppsättningar av storlek för grupper av formen som inte innehåller aritmetiska progressioner av längd 3.
Meshulam överväger [23] Roths teorem för en godtycklig grupp och härleder en uppskattning för en mängd utan aritmetiska progressioner av längd 3.
Detta innebär att det finns en absolut konstant så att för en uppsättning utan progressioner,
Den klassiska generaliseringen av Roths sats för tvådimensionella mängder är hörnsatsen . Även om det inte nämns något om aritmetiska progressioner (i tvådimensionell mening), följer Roths sats av den.