Az összeg-szorzat tétel az aritmetikai kombinatorika tétele, amely megállapítja bármely kellően nagy halmaz strukturálatlanságát legalább egy mezőművelet (összeadás és szorzás) tekintetében. A strukturáltság mutatójaként az összegek halmazának, illetve a szorzathalmaz méretét használjuk.
Legyen valamilyen gyűrű részhalmaza (általában egy mező , de formálisan egy gyűrű is szóba jöhet) és műveletekkel . A halmaz két származékát tekintjük:
Ha a halmaz az összeadás szempontjából strukturált (például sok aritmetikai sorozata van, vagy általánosított aritmetikai sorozata van, vagy ezek nagy darabjai), akkor a halmaz viszonylag kicsi lesz - elvégre sok elempár összege egybeesik .
Ha a szorzás szempontjából strukturált, akkor a halmaz hasonló okokból nem lesz túl nagy .
A tétel kimondja, hogy a halmazok közül legalább az egyik nagyon nagy -hoz képest , azaz legalább egy művelethez képest a struktúra szabálytalan lesz.
Pontosabban, a tétel hatványtörvény növekedést hoz létre a származtatott halmazok közül a legnagyobb méretében az eredeti méretéhez képest:
Tétel Valamely konstansra és tetszőleges halmazra (végesre , méretkorlátozással) igaz, hogy |
Különböző gyűrűkre különböző becsléseket lehet kapni . Ezenkívül egyes (különösen véges ) gyűrűk esetén lehetőség van feltételeket hozzáadni a halmaz méretéhez, amely mellett a tétel az adott gyűrűre érvényes .
A tanulmányozás szempontjából legkényelmesebbek a hipotézis szélsőséges esetei:
A klasszikus példák az összeg-szorzat tétel illusztrálására az aritmetikai és a geometriai haladás .
Egy aritmetikai sorozat az összeadás tekintetében maximálisan rendezett, így azonban a számokból sokféle szorzat készíthető, így [3] , tehát a szorzás szempontjából teljesen rendezetlen.
Ugyanígy egy geometriai haladásnál is , de nyilvánvaló (ha a számok bináris ábrázolását vesszük figyelembe), hogy .
Amikor az összeg-szorzat tételt néha Erdős-Szemeredi tételnek is nevezik , hiszen 1983-ban ők vetették fel az összegek és szorzatok számarányának figyelembevételét. Ugyanebben a munkában azt a hipotézist terjesztették elő, hogy az érték tetszőlegesen közel állhat az egységhez (vagyis ). Ugyanebben a cikkben azonban több további hipotézist is felállítottak, különösen egy hasonlót a kifejezésekre és halmazokra vonatkozóan: .
Az értékelés javulásának kronológiája | ||
---|---|---|
Év | Jelentése | A szerzők) |
1983 | (*)(**) | Erdős , Szemedy [4]
ahelyett |
1998 | (*)(**) | Ford [5] |
1997 | (**) | Elekesh [6] |
2005 | Shoimoshi [7] | |
2009 | Shoimoshi [8] | |
2015 | Konyagin , Shkredov [9] | |
2016 | Konyagin , Shkredov [10] | |
2016 | Rudnev, Shkredov, Stevens [11] | |
2019 | Shakan [12] | |
2020 (előnyomat) |
Rudnev, Stevens [13] | |
(*) Csak a (**) esetén igaz a fokozat helyett |
Terence Tao monográfiájában megjegyzi, hogy Erdős és Szemedy terepeken elért eredményeinek analógiáját 1999-ben T. Wolf vetette fel (egy magánbeszélgetésben) a rendi kardinalitás részhalmazaira .
Az összeg-szorzat problémát Burgain , Glibbichuk és Konyagin , valamint Burgain, Katz és Tao oldotta meg . Bebizonyították a következő tételt
Bármelyikre létezik olyan, hogy ha és , akkor a becslés |
A tétel feltételében a követelmény természetes, hiszen ha közeli sorrendje van , akkor a és a mennyiségek is közel lesznek ahhoz, hogy . [tizennégy]
Terence Tao megvizsgálta a tétel tetszőleges gyűrűkre történő általánosításának határait, és különösen a kis érték és a nulla osztók számának szélsőséges eseteinek kapcsolatát egy halmazban , valamint szerkezetének közelségét egy halmazhoz. subring . [tizenöt]
Erdős és Szemedi bizonyítása azt használta, hogy kicsiknek és van megoldás a rendszerre
ahol egyes (különböző) részhalmazokhoz tartoznak, és magára a halmazra speciális feltételek vonatkoznak. Egy ilyen állítást lemmaként használva igazolható a tétel tetszőleges halmazra is . [16]
A Semeredi-Trotter tétel (Elekesh, 1997)
Ha minden elemnek sok reprezentációja van a formában néhány kis halmazhoz , akkor az egyenlet megoldásainak számának becsléséhez
bármely halmaz esetén használhatja az egyenletet
Másrészt egy ilyen egyenlet megoldásai megfelelnek a párokkal paraméterezett vonalak és a párokkal paraméterezett pontok közötti beeséseknek . Ezért ezek becsléséhez célszerű általános eredményeket használni az előfordulásokra vonatkozóan, amelyek közül a legjobb a Szemedy-Trotter tétel . [17] [18]
Pontosan ezt használta Elekesh a kitevőtétel bizonyításakor . [6] Bizonyítása implicit módon két szakaszra osztható:
Ez a dekompozíció fontos a későbbi módszerek megértéséhez .
Shoimoshi konstrukciója (Shoimoshi, 2009)Shoimoshi azt a tényt használta, hogy ha , akkor
Ebből az következik, hogy ha , akkor
Ugyanakkor fix értékek esetén az összes reprezentációval alkotott pár
eltérő lesz, ezért a „szomszédos” párokra összegezve becslést kaphatunk az ilyen reprezentációk számáról. És ez viszont (közvetve) keresztül fejeződik ki . [19]
Ezt az elképzelést legvilágosabban geometriailag lehet kifejezni, mivel az ebből származó pontok összegzése a koordináták középpontjából kiinduló szomszédos egyeneseken fekszik.
Shoimoshi építésének bontása (Konyagin, Shkredov, 2015)
Ha azt a feltételt, hogy az összegzett pontoknak a szomszédos vonalakhoz kell tartozniuk, kikerülünk Shoimoshi konstrukciójából, akkor semmi sem garantálja, hogy az összes kapott összeg eltérő lesz. Például általánosságban elmondható, hogy a -tól származó összes pontösszeg csak szélsőséges esetben térhet el egymástól , és ez már teljesíti az összeg-szorzat hipotézist.
Ennek alapján Konyagin és Shkredov megbecsülte az ilyen összegek egybeesésének minimális számát köztes esetben (amikor és egyenlő az alsó becsléssel, azaz ). Az egyezések számának becsléséhez az összes sort felosztották ugyanannyi egymást követő blokkra, és a legtöbb esetben megbecsülték az egyes blokkokban található egyezések számát. Ezeket a becsléseket felhasználva eredményt kaptak: . [húsz]
Nem triviális multiplikatív expanzió (Rudnev és Stevens, 2020)
A Konyagin és Shkredov által figyelembe vett két pontösszeg egybeesése azt jelenti, hogy van megoldás az egyenletrendszerre
ahol mind és a párok is különböznek. A rendszer Gauss-módszer szerinti redukálásával (egy lépésben) megkaphatjuk az egyenletet
állandó és azonos feltételekkel a . Rudnev és Stevens ezt egy nagy részhalmaz multiplikatív kiterjesztésének explicit megalkotására alkalmazta, amely jobb tulajdonságokkal rendelkezik, mint a triviális. [21]
Az Elekesh-féle bizonyítással analóg módon ez lehetővé teszi, hogy a kitevős becslések bizonyítását két lépésre bontsuk:
Magasabb energiák felhasználása
Az egyenletek legelterjedtebb becslési módja az additív energia és annak általánosításai. A Szemedy-Trotter tétel alkalmazásának eredményei lehetővé teszik az alakegyenletek legjobb elemzését.
önkényes . Rudnev és Stevens egy módszert javasolt ennek az additív energiának az egyenlet figyelembevételével történő hasznosítására.
ahol a népszerű (nagy számú reprezentációval rendelkező) különbségek halmazának felel meg, és a népszerű összegek halmazához tartozik. A konvex sorozatok összegének becsléséhez az összegszorzatok problémája mellett az ilyen módszerek kidolgozása is releváns . [23]
Létezik egy hasonló operátori módszer, amely kevésbé hatékony a becsléshez , de lehetővé teszi a és közötti kapcsolat jobb tanulmányozását . [24]
A tétel bizonyításakor széles körben használatos az additív energia fogalma , a Plünnecke-Rouge egyenlőtlenség és a Balogh-Szemeredi-Gowers becslés. Az egyik lehetséges bizonyítás a halmaz méretének alsó korlátját és azt a tényt használja, hogy a felső határtól a méretekre , és egy ellentmondásos alsó felső korlátot követ a méretre . [25] [26]
Bourgain , Glibichuk és Konyagin [27] a tétel egy sajátos esetét használta többlineáris trigonometrikus összegek becslésére . Ez különösen lehetővé tette a Gauss-összegek nem triviális felső határának meghatározását kis multiplikatív alcsoportok felett . [28] Bourgain, Katz és Tao , ugyanazt az esetet használva, megerősítették a becslést a Szemedy-Trotter problémában -ben , bizonyítva, hogy a -ból származó pontok és a vonalak párjainak halmaza esetén a becslés bizonyos -ra érvényes . [29]
Ugyanebben a munkában alkalmazták a tételt a Kakeyi-halmazok nagydimenziós térben történő vizsgálatára . Egy ilyen halmaz méretére becslést kaptak . [26] [29]
Ugyanabban a cikkben, ahol Erdős és Szemedi azt feltételezték, hogy a számára , példát mutattak be egy tetszőleges nagy halmaz felépítésére is , amelyhez . A legfeljebb prímszámok (nem feltétlenül különböző) szorzataként kapott számok halmazaként szolgált , amelyek mindegyike nem haladja meg a -t , ahol egy tetszőlegesen nagy szám. [16]
Bourgain és Chang figyelembe vették a forma becsléseit
egy tetszőleges és . [harminc]
Sok műben az összeadás és a szorzás egyetlen kifejezésben van kombinálva : például feltétel nélküli alsó korlátokat kapunk a -ra . [31]
A sejtés egyik általánosítása egy halmaz elemein tetszőleges gráf éleinek megfelelő összegek és szorzatok kérdése.
Legyen egy gráf, , . Jelölje és az egyenlőségekkel
Hogyan függnek egymástól az értékek és hogyan függenek egymástól ? |
Az esettel ellentétben előfordulhat , hogy sem az összegek, sem a szorzatok extrém növekedése nem következik be: -nél az a helyzet lehetséges, amikor [32] . Ezért az alsó határok mellett a felső határok kérdése is . Ugyanakkor az alsó határokat is tanulmányozzák. [33] [34]
Az összeghalmaz méretének alsó korlátja könnyen levezethető az additív energia felső határaiból , így természetes, hogy az elsőről szóló hipotézist a másodikra vonatkozó hipotézisre általánosítjuk, a multiplikatív energia hasonló fogalmát használva .
De lehet, hogy egy számhalmaz mindkét energiája egyszerre nagy, mivel az alacsonyabb becslés egy külön részhalmaz közreműködésével szabályozható. Például ha , akkor egy halmazra igaz, hogy
Ezért a megfelelő energiatétel megfogalmazásakor a különböző részhalmazok energiáinak arányát használjuk .
Balogh-Wooly tétel Van egy olyan konstans , hogy minden halmazhoz van egy partíció a feltétellel |
Ennek a tételnek a legjobb változatát bebizonyították . [12] Ismeretes, hogy ugyanez nem igaz a -ra . [35]
Két szám szorzása logaritmusaik összeadásának függvényében ábrázolható: . Egy szigorúan növekvő függvény elemenkénti alkalmazása egy halmazra nem változtatja meg a méretét, tehát
és az alapösszeg-szorzat hipotézis újrafogalmazható úgy
vagy (helyettesítő ) as
Kiderült, hogy hasonló becslések bizonyíthatóak tetszőleges konvex függvény helyett .
Tétel [36] Ha egy tetszőleges halmaz, egy tetszőleges szigorúan konvex függvény, akkor |
Nyitva marad az a kérdés, hogy a jobb oldali mutatóval megegyező becslések helyesek-e.
Hasonló eredményeket kaptunk nagyobb számú kifejezésre is. [37]