Roth tétele

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.

A javított pontszámok története

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]

Különféle bizonyítások

Harmonikus elemzés

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.

Kombinatorikus (Szemedi lemmáján keresztül)

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.

Elemi (általánosított aritmetikai progresszión keresztül)

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.

Ellenpéldák nem sűrű halmazokhoz

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.

Erdős, Turan (1936)

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ása

Legyen --- 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, Spencer (1942)

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ása

Az 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 .

Berend (1946)

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ása

Minden 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.

Változatok és általánosítások különböző csoportokhoz

Véges ciklikus csoportokhoz

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.

Kis fix torziós csoportoknak

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

Felső határok

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árok

A 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.

Tetszőleges csoportokhoz

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

Kétdimenziós általánosítás

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.

Lásd még

Irodalom

Jegyzetek

  1. I. D. Shkredov, „Szemeredi-tétel és az aritmetikai progressziók problémái”, Uspekhi Mat. Nauk, 61:6(372) (2006), 111-178; Orosz matematika. Surveys, 61:6 (2006), 1101-1166 . Letöltve: 2017. december 23. Az eredetiből archiválva : 2017. december 24..
  2. Roth 12. , 1953 .
  3. Heath-Brown, 1987 .
  4. Szemerédi, 1990 .
  5. Bourgin, 1999 .
  6. Bourgin, 2008 .
  7. Sanders, 2012 .
  8. Sanders, 2011 .
  9. Bloom, 2014 .
  10. Schoen, 2020 .
  11. Bloom, Sisask, 2020 .
  12. Roth bizonyítása Harold Helfgott által oroszul (elérhetetlen link) . Letöltve: 2017. december 23. Az eredetiből archiválva : 2017. december 24.. 
  13. Postnauka, Ilja Shkredov – Semeredi tétele
  14. Csebisev Laboratórium, előadások kurzusa "Additív kombinatorika", 3. előadás
  15. Egy minikurzus az additív kombinatorikáról Archiválva : 2017. augusztus 29. a Wayback Machine -nál , p. 6
  16. Erdős P., Turán P., "On some sequences of integers", Journal of the London Mathematical Society (1936. június) . Letöltve: 2019. december 23. Az eredetiből archiválva : 2019. december 23.
  17. R. Salem, DC Spencer, Proc. Natl. Acad. sci. USA 28, 561-563 (1942) . Letöltve: 2017. december 23. Az eredetiből archiválva : 2018. június 3.
  18. FA Behrend, "Az egész számok halmazairól, amelyek nem tartalmaznak három tagot az aritmetikai progresszióban", Proc. Natl. Acad. sci. USA 32 (1946), 331-332. . Letöltve: 2017. december 23. Az eredetiből archiválva : 2018. június 4.
  19. Michael Elkin, "Progressziómentes halmazok továbbfejlesztett felépítése", Israel Journal of Mathematics, 184:93 (2011. augusztus) . Letöltve: 2019. december 23. Az eredetiből archiválva : 2018. november 27.
  20. T. Schoen, ID Shkredov, "Roth-tétel sok változóban", Israel Journal of Mathematics, 199. kötet, 287-308. oldal (2014) Archivált : 2019. december 23. a Wayback Machine -nél ( arXiv:1106.1601 at the December Archived 2012. gép )
  21. T. Schoen, O. Sisask, "Roth tétele négy változóra és additív struktúrákra ritka halmazok összegében", Matematikai fórum, Sigma, 4, E5. doi:10.1017/fms.2016.2 Archivált 2020. május 1-én a Wayback Machine -nél ( arXiv:1408.2568 Archivált 2019. december 23-án a Wayback Machine -nél )
  22. TC Brown és JP Buhler, Egy geometriai Ramsey-tétel sűrűségváltozata, Journal of Combinatorial Theory, Series A 32 (1982), no. 1, 20-34. . Letöltve: 2017. december 23. Az eredetiből archiválva : 2017. augusztus 9..
  23. 1 2 R. Meshulam, A 3 tagú aritmetikai progresszió nélküli véges Abel-csoportok részhalmazairól, Journal of Combinatorial Theory, Series A 71 (1995), no. 1, 168-172.  (nem elérhető link)
  24. 1 2 Egy minikurzus az additív kombinatorikáról Archiválva : 2017. augusztus 29. a Wayback Machine -nél , p. 39-42
  25. Csebisev Laboratórium, Ilja Shkredov, Analitikai módszerek az additív kombinatorikában, áttekintő előadás
  26. M. Bateman és N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), no. 2, 585-613. . Letöltve: 2017. december 23. Az eredetiből archiválva : 2018. január 9..
  27. E. Croot, V. Lev és PP Pach, Progressziómentes halmazok a Z_n^4-ben exponenciálisan kicsik (2016). arXiv preprint 1605.01506. . Letöltve: 2017. december 23. Az eredetiből archiválva : 2018. június 12.
  28. 1 2 Roth-tétel bizonyítása kis torziós csoportokra az arxiv.org oldalon . Letöltve: 2017. december 23. Az eredetiből archiválva : 2018. június 12.
  29. Ellenberg és Gijswijt bizonyításának bemutatása oroszul
  30. Y. Edel, Az általánosított terméksapkák kiterjesztése, Tervek, kódok és kriptográfia 31 (2004), 3. sz. 1, 5-14. . Letöltve: 2017. december 23. Az eredetiből archiválva : 2018. január 10.