Roth tétele az additív kombinatorika eredménye, a Szemedi-tétel speciális esete a 3 hosszúságú progresziókra; azt állítja , hogy minden kellően sűrű halmazban aritmetikai progressziók vannak.
A pontos megfogalmazás a következő: bármely , minden aszimptotikus sűrűségű halmaz tartalmaz egy 3 hosszúságú aritmetikai progressziót .
A felső és alsó aszimptotikus sűrűséget használó hasonló formulációk egyenértékűek [1] -vel .
A véges halmazok formulája is ekvivalens az eredetivel: bármely létezik olyan, hogy ha , és , akkor 3 hosszúságú aritmetikai sorozatot tartalmaz. A bizonyítások túlnyomó többsége a véges halmazokra vonatkozó formulációt bizonyítja.
Maximális részhalmaz mérete
hosszugrások nélkül 3 | ||
---|---|---|
Megjelenés éve | Méret (maximum állandó) |
A szerzők) |
1953 | Száj [2] | |
1987 | Heath-Brown [3] [4] | |
1999 | Bourgin [5] | |
2008 | Bourgin [6] | |
2012 | Sanders [7] | |
2011 | Sanders [8] | |
2014 | Bloom [9] | |
2020 (előnyomat) | Shoen [10] | |
2020 (előnyomat) | Bloom, Sisask [11] |
A tételt először Klaus Roth [2] [12] bizonyította 1953 -ban a Hardy-Littlewood kör módszer adaptálásával. A bizonyítás azt a gondolatot használta [13] , amelyet utólag Szémeredi tételének általános bizonyítására általánosítottak: egy adott sűrűségű összes halmaz két csoportra van osztva - "uniform" és "non-uniform", az "uniformity" pedig egy felsőt jelent. a Fourier-együtthatókhoz kötve . Ha a halmaz egyenletes, akkor a progressziók jelenléte benne közvetlenül igazolható, ellenkező esetben bizonyítható olyan részprogresszió létezése, amelyben a halmaz sűrűsége nagyobb, mint a természetes sorozat azon szegmensében, amelyhez tartozik. .
A módszer lehetővé teszi becslések származtatását . A bizonyítás technikai részletei, az "uniformitást" definiáló Fourier-együtthatók korlátai és a kapott állandók forrásonként eltérőek lehetnek.
A Roth-tétel bizonyítása Szemeredy tételének speciális eseteként levezethető [14] a Szemedy-féle bizonyításból. Ez a bizonyítási mód megköveteli a Szémerédy-féle szabályszerűségi lemmának és a saroktételnek a használatát , amelyből Roth tétele közvetlenül következik. Még az is lehetséges [15] , hogy mellőzzük a saroktételt, és a Roth-tételt közvetlenül a háromszög-eltávolítási lemmából származtatjuk , de csak a véges ciklikus csoportok megfogalmazásában (lásd a „Különböző csoportokra vonatkozó általánosítások” című részt).
Mivel a Szemedi-reguláris lemma rendkívül nagy felső korlátokat ad az általa kapott értékre (legalábbis kitevőtornyokat ) , a módszer maga nem teszi lehetővé ezeknél jobb korlátok megszerzését.
Ronald Graham Ramsey-elméletről szóló könyvében a bizonyítás egyszerűsített változatát adja, szintén Szemedi-módszer alapján, de a szabályossági lemma használata nélkül. A bizonyítás a forma általánosított aritmetikai progresszióit használja , amivel sokkal könnyebb bizonyítani a halmazban való jelenlétét, és ebből már maga a Roth-tétel is levezethető.
Graham bizonyítása nem ad becsléseket a -ra , hanem csak a létezést mutatja meg, mivel egy olyan pont létezését használja fel a sorozatban, amelyből kiindulva minden pont kellően közel van a határértékhez , de csak a létezést bizonyítja a határértékre is, ill. a konvergencia jellegét elvben nem elemzik.
Az aritmetikai progresszió nélküli halmaz méretének felső határának megtalálása mellett van egy inverz probléma is: a lehető legnagyobb halmaz megalkotása , amely nem tartalmaz aritmetikai progressziót, vagyis egy ellenpélda a becslések javulásának korlátainak jelölésére . Az ilyen halmazok összes ismert konstrukciója azon az elgondoláson alapul, hogy egy bizonyos számrendszerben figyelembe kell venni a számok egyes számjegyeit, és feltételeket kell meghatározni e számjegyek értékére.
A progresszió nélküli halmaz első példáját 1936-ban adta Erdős és Turan, akik olyan számok figyelembevételét javasolták, amelyek a hármas rendszerben csak a 0 és a 2 számjegyeket tartalmazzák. Egy ilyen halmaz csak számokat tartalmaz, ami nagyon kicsi a felsőhöz képest. határait. [16]
A konstrukció helyességének igazolásaLegyen --- az Erdős--Turán halmaz.
Ha és , akkor a háromtagú rendszerben a legjelentősebb számjegyben , ahol ezek a számok különbözőek, teljesülnek az egyenlőségek . Ezért egy aritmetikai sorozatban teljesülne , és így .
Salem és Spencer 1942-ben általánosította Erdős és Turan gondolatát növekvő (a halmaz méretétől függően) bázisú számrendszerekre, és kapott egy halmazt, amely nem haladja meg a méretet . [17]
A tervezés rövid leírásaAz Erdős-Turan konstrukcióban teljesen lehetséges a 0 és 1 számok megengedése 0 és 2 helyett (akkor a középső szám helye a haladásban nagyobb helyet foglal el a helyesség bizonyításában). Ezzel analógiával Salem és Spencer az -ary rendszerben olyan számokat vett figyelembe, amelyek csak 0-tól ig számjegyeket tartalmaznak , és minden számjegynek azonos számú előfordulása van (az aszimptotikával páratlannak tekinthető, és a számjegyek teljes száma --- felosztás ).
A progressziók jelenlétét az egyes számjegyek előfordulásának feltétele blokkolja. Valójában, ha az összeadás során nem használjuk a hordozást , akkor az összes nulla -ban (és így -ben is) csak úgy alakítható ki, hogy a megfelelő és számjegyekből nullákat adunk hozzá . Továbbá indukcióval igazolhatjuk az egyesek, kettesek stb. pozícióinak egybeesését, és arra a következtetésre juthatunk, hogy .
A megadott pontszámot figyelembe véve kapjuk meg .
1946-ban Behrend egy geometriai értelmezést adott hozzá azzal, hogy a számok számjegyeit a többdimenziós tér pontjainak koordinátáihoz rendelte, és figyelembe vette az ebben az értelemben megfelelő számokat egy gömb pontjainak . Ez lehetővé tette egy progressziómentes méretkészlet felépítését . [tizennyolc]
A tervezés rövid leírásaMinden olyan szám , amelynek számjegyei nem nagyobbak, mint -áris reprezentáció , azonos értékű csoportokra vannak osztva . E csoportok közül a legnagyobbat választjuk halmazként, és méretét a Dirichlet-elv szerint becsüljük meg .
A korlátozott számjegyek miatt ilyen számok összeadásakor nincs számjegyátvitel , így a 3 hosszúságú progresszióknak is van geometriai értelmezésük (mint ugyanazon a vonalon lévő pontok). De mivel a golyó szigorúan domború test , a gömb, mint határa, nem tartalmazhat három pontot egy egyenesen. Ebből az következik, hogy a választott halmazban nincs progresszió.
A készlet mérete a legjobban becsülhető
Ezt követően Behrend becslését logaritmikus tényezővel növelték a módszer enyhe finomításával [19] , de 2019-től nincs lényegesen jobb eredmény.
Mivel Roth tételének [20] [21] egyes általánosításaihoz hasonló típusú felső határok ismertek , okkal feltételezhető, hogy Behrend korlátja éles.
Mind a harmonikus elemzéssel történő bizonyítás, mind a Szemedi-lemma konkrét alkalmazási módja nem magát a tételt bizonyítja, hanem annak „ciklikus” változatát.
Bármelyikre létezik olyan, hogy if , és , akkor tartalmazza a hármast , ahol az összeadás modulo összeadást jelent |
Az e megfogalmazás által ígért progressziók lehetnek bennük, de nem (például ). Roth tétele azonban nyilvánvalóan következik belőle, ha a halmazt a -beli maradékok halmazának tekintjük . Ez csak egy állandóval változtatja meg a sűrűséget, de minden progressziót alkalmassá tesz a -ra . Ezért ez a tétel egyenértékű Roth főtételével.
A következő, Roth tételéhez hasonló elgondolású tétel nem következik belőle, és nem is implikálja azt, de egy külön tanulmány szempontjából érdekes.
Néhányat javítsanak ki . Akkor minden létezik olyan, hogy ha , akkor |
A csoportokra vonatkozó tételt először Brown és Bahler bizonyította 1982-ben [22] , de ők csak azt bizonyították, hogy aritmetikai progresszió nélküli halmazok esetén , de a pontosabb megszorítások nyitott kérdés maradt.
1993-ban (1995-ben publikálva) Roy Meshulam bebizonyította [23] , hogy . Bizonyítása tetszőleges csoportokat és azok szereplőit vette figyelembe . Ennek a bizonyításnak vannak leegyszerűsített [24] változatai is, amelyek kizárólag -ra vonatkoznak , amelyek a -ban szereplő Fourier-együtthatókat használva közvetlenül általánosítják a Roth-tétel analitikus bizonyításából származó ötleteket. A bizonyítás technikailag még egyszerűbb, mint magának Roth-tételnek a bizonyítása, ezért gyakran [24] [25] adják meg a módszer alkalmazásának első példáját.
2012-ben Bateman és Katz az esetet mérlegelve bebizonyították [26] egy abszolút állandó létezését , úgy, hogy számtani progresszió nélkül .
2016-ban Krut, Lev és Pach bebizonyította [27] a progresszió nélküli halmazok esetét . Ellenberg és Gijswijt , Krut, Löw és Pach módszerét általánosítva a polinomiális algebra segítségével , bebizonyították [28] [29] , hogy mindegyik olyan egyszerű állandóra létezik , amely nem tartalmaz 3 hosszúságú progressziót. . Különösen az esetre . Feltevés szerint a függvény optimalizálásából az következik, hogy ahol egy abszolút állandó, ami az egyenlet megoldása , azaz , ahol
Alsó határokA legjobb [28] 2016-os szerkesztési ellenpélda lehetővé teszi [30] számára, hogy mérethalmazokat hozzon létre olyan alakú csoportokhoz , amelyek nem tartalmaznak 3-as hosszúságú aritmetikai progressziót.
Meshulam figyelembe veszi [23] Roth tételét egy tetszőleges csoportra , és levezeti a becslést a 3-as hosszúságú aritmetikai progresszió nélküli halmazra.
Ez egy olyan abszolút állandó létezését jelenti , amely progresszió nélküli halmaz esetén
A Roth-tétel klasszikus általánosítása kétdimenziós halmazokra a saroktétel . Bár szó sincs aritmetikai progresszióról (kétdimenziós értelemben), Roth tétele következik belőle.