Az aritmetikai kombinatorika a matematikának egy interdiszciplináris területe, amely egy területen (ritkábban egy gyűrűben ) az összeadás és a szorzás műveletével kialakult struktúrák közötti kapcsolatot vizsgálja.
A struktúra fogalmának megközelítése itt hasonló az additív kombinatorikához , és főként az összegek ( vagy szorzatok) halmazának méretén, az additív (vagy multiplikatív) energián és ezek különféle kombinációin alapul. Mezőként általában a valós vagy racionális számokat ( , ) és a modulo prím ( ) maradékokat veszik figyelembe.
Az additív és aritmetikai kombinatorika fiatal, aktívan fejlődő tudományok. Módszereik és problémafelállítási módjaik nagyon hasonlóak, ezért az additív kombinatorika általában az aritmetika részének tekintendő. [1] Ez a cikk csak azokat a témaköröket írja le, amelyek mindkét mezőműveletet egy vagy olyan formában vagy azok inverzeit tartalmazzák, vagyis amelyek nem tartoznak a tisztán additív kombinatorikába (bár ez utóbbi az aritmetika meglehetősen jelentős részét teszi ki).
Ráadásul itt nem térünk ki a multiplikatív részcsoportok és a kapcsolódó halmazok additív-kombinatorikus tulajdonságaira vonatkozó kérdésekre, mivel bár definíciójuk a szorzáshoz kapcsolódik, a multiplikatív szerkezetük mereven rögzített, és ennek a tudománynak a kombinatorikus komponense magában foglal egyet-mást. általánosság a szerkezet fokát illetően (legalábbis állandóként működő paraméterrel).
Az aritmetikai kombinatorika fejlődését nagymértékben az összeg-szorzat tétel megjelenése motiválta , amely a halmazok nélkülözhetetlen növekedéséről beszél attól, hogy akár kombinatorikus összegzést, akár szorzást alkalmazunk rá, azaz két művelet egyikét:
Ebből következik, hogy e műveletek kombinációja növekedést is von maga után: ha , akkor
,véges számú elem hozzáadása pedig csak marginálisan befolyásolja a növekedést. Mivel az összeg-szorzat tételt csak gyenge formában igazolták (a hipotézistől távol), egyes tudósok érdeklődést mutattak az ilyen jellegű állítások megszerzésében, amelyek a hipotézis bizonyítottnál erősebb formáiból következnének, és ezt követően az általános tanulmányozásban. két műveleti mező különböző kombinációinak eredményei közötti kapcsolat.
Például az Erdős-Szemeredy összeg-szorzat sejtés azt állítja, hogy [2]
Ebből a hipotézisből az következne, hogy , de halmazokra egyszerű kombinatorikus érveléssel könnyen elérhető ilyen eredmény anélkül is. [3]
Ez a szakasz hagyományos jelöléseket használ az eredmények leírására (az O-jelölés magyarázata ):
Legyen a halmazok feletti racionális kifejezés a köztük lévő számtani műveletek ( ) tetszőleges kombinációja . A művelet itt a többszörös összeg elve szerinti alkalmazást jelenti:
Például a következő halmazok racionális kifejezések a következőre :
Az additív energiával analóg módon, amelyet gyakran használnak összegek halmazának becslésére, célszerű figyelembe venni egy racionális kifejezéssel rendelkező szimmetrikus egyenlet megoldásainak számát. Például,
[négy]Az aritmetikai kombinatorika problémáinak egy lényeges részét a következő kérdés megfogalmazással fejezhetjük ki.
Legyen — valamilyen mező (akár végtelen, akár kellően nagy egy adott végesek családjából), — racionális kifejezések, és ezek közül legalább az egyik használja a vagy és legalább egy vagy . Legyen néhány és beállítja a kapcsolatokat is Kérdés Hogyan függ a lehetséges értékek halmaza ? jegyzet Ha a mező véges, akkor célszerű a halmazt kiegészíteni a paraméterrel , ahol . [5] |
Például az összeg-szorzat hipotézis kimondja, hogy ha , , , akkor (itt ).
Általában kiderül, hogy lineáris összefüggéseket vezet le a mennyiségek között , azaz egyenlőtlenségeket a különböző mennyiségek szorzatai és hatványai között .
Néhány eredményAz összegek és termékek általánosításáról:
[6] [7] [8] ; [9] ; [tíz] [tizenegy]Az energiák általánosításáról:
A különböző műveleteket kombináló racionális kifejezések kiértékelésének ötlete abból a tényből származik, hogy egy halmazra additív művelet alkalmazása megfosztja multiplikatív szerkezetétől. Ugyanez az elv kiterjeszthető arra az esetre is, amikor a halmazt nem az elemenkénti összeadás összetett kombinatorikus műveletével változtatjuk meg, hanem egy közönséges additív eltolással - a halmaz összes eleméhez egy szám hozzáadásával. Ez várhatóan a legtöbb esetben megváltoztatja a halmaz multiplikatív szerkezetét (például ha , akkor egyeseknél az összesre vagy majdnem az összesre ). [tizennégy]
Kérdés Rögzített (de tetszőleges) multiplikatív tulajdonságai (a szorzathalmaz mérete és a multiplikatív energia) a halmazok egymástól függenek . És azt is, hogy mik a különböző halmazok együttes multiplikatív tulajdonságai (például vannak-e nem triviális becslések a -n )? |
Az összeadás és szorzás kombinálásának gondolata természetesen a polinomok figyelembevételéhez vezet , vagyis ugyanazok a racionális kifejezések, amelyekben egy változó többször is megjelenhet (és így összetettebb hatással lehet a kapott halmaz szerkezetére). . Kiderült, hogy ebben az esetben a feltétel nélküli növekedés biztosításához nem szükséges a halmaz három példányát használni (mint a kifejezésben ), hanem elegendő két változóban kiválasztani a kívánt polinomot. [22] Bourgin vette észre először a polinom ilyen tulajdonságát . [23]
Ezenkívül, az összeg-szorzat tételével analóg módon, tetszőleges polinomok alsó határait tanulmányozzuk .
Néhány eredményBourgain első eredménye: ha . Aztán egyesek számára ez igaz
[24]A és összehasonlításakor a polinom degeneráltsága nagy jelentőséggel bír . Ha degenerált, azaz így ábrázoljuk , ahol polinomok és , akkor mindkét összeg kicsinek bizonyulhat, ha egy aritmetikai progresszió, mert . Ezért az eredmények csak nem degenerált polinomokra vannak megfogalmazva:
Vannak eredmények az egyik vagy másik mátrix-alcsoportból (például a Heisenberg-csoportból ) származó mátrixkészletek szorzathalmazairól. Szigorúan véve ezek az eredmények egyetlen csoportműveletre vonatkoznak ( mátrixszorzás ), így additív kombinatorikáknak nevezhetjük őket . Ám az elemek összeadása és szorzása [27] e műveletének definícióján belüli összeolvadása , valamint az ebből fakadó kommutációmentesség nagyon atipikussá teszi tulajdonságait a hétköznapi csoportműveletekhez, például a valós számok összeadásához képest.
Például egy mátrixhalmaz gyakran úgy nőhet, hogy nagyon egyszerű feltételek mellett (nagy méret, az egyes elemek korlátozása vagy az alcsoportoktól való eltérés) önmagát megszorozhatja.
Néhány eredményA mátrixcsoportokra vonatkozó eredmények többsége, amikor tetszőleges mátrixhalmazokról van szó, a , nem pedig az értékét elemzi . Ez nem véletlen, hanem a kommutativitás hiányához kapcsolódó technikai szükségszerűség. [28]
A csoport és a Chevalley csoport növekedésének vizsgálatára szolgáló analitikai módszerek felhasználhatók a Zaremba sejtés egy speciális formájának levezetésére . [33] [34]