Sok összeget

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. május 11-én felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

Az összegek halmaza az additív kombinatorika fogalma , amely a véges halmazok Minkowski-összegének felel meg .

Definíció

Legyen tetszőleges csoport és véges halmazok. Ekkor az összegük a halmaz ${\mbox{G}}$ $A,B\subset {\mbox{G))$

{\megjelenítési stílus A+B:=\{a+b:a\A-ban,\b\B-ben\))

Egy halmaz esetében annak összeghalmazát nevezzük . A többszörös összegek rövidítése [1] $A$ $A+A$

{\displaystyle kA=A+\dots +A=\{a_{1}+\dots +a_{k}:a_{i}\in A,\ i=1,\dots ,k\))

Kapcsolódó definíciók

Hasonlóképpen, a különbségek halmaza , a szorzatok halmaza , a hányadosok halmaza és hasonlók definiálva vannak bármely művelethez. Például a termékek halmazát a következőképpen határozzuk meg [2] :

A\times B=\{ab\ :\ a\in A,\ b\in B\}

Az értéket duplázási állandónak [3] nevezzük , és azokról a halmazokról, amelyekre korlátozva van, kis duplázó [4] . Az összegszorzat tétel kapcsán gyakran szóba jöhetnek a kis szorzóduplázással rendelkező halmazok , vagyis amelyeknek az értéke korlátozott [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac {|AA|}{|A|}}$

Tulajdonságok

Az összegek halmazának hatványa az additív energiához kapcsolódik a [6] egyenlőtlenséggel , ezért ez utóbbit gyakran használják a becsléshez. $A+B$ $E(A,B)$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Egy halmaz összegei

Freiman tétele a méretet egy halmaz strukturáltságának mutatójának tekinti (ha a duplázó állandó korlátozott, akkor a szerkezet hasonlít egy általánosított aritmetikai progresszióhoz ). [7] [8] $A+A$ $A$

Az összeg-szorzat tétel az összegek halmazának és a szorzatok halmazának a méretét hozza összefüggésbe. A fő hipotézis szerint . [9] Az összegzés és a szorzat egy kifejezésben való kombinációja az aritmetikai kombinatorika kialakulásához vezetett . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subset \mathbb {R}$

Azt vizsgáljuk, hogy egy konvex függvény elemenkénti alkalmazása összegezhető halmazokra hogyan befolyásolja az összegek halmazának méretét. Konvex sorozatok esetén a és alsó határai ismertek . [10] Általánosabban, konvex függvény és halmaz esetén a becslési problémát és néhány hasonlót néha az összeg-szorzat tétel általánosításának tekintik, mivel és ezért a függvény konvex. [tizenegy] $|A+A|$ $|AA|$ $f$ ${\displaystyle f(A):=\{f(a):a\in A\))$ ${\displaystyle \max\{|A+A|,|f(A)+f(A)|\))$ $AA=\exp \left({\log A+\log A}\right)$ $|AA|=|\log A+\log A|$ $\exp$

Több halmaz összegei

A Plünnecke-Rouge egyenlőtlenség kimondja, hogy a többszörös összegek növekedése (méretnövekedése az összegezhető halmazokhoz képest) átlagosan ( -hez képest) nem haladja meg nagymértékben a növekedést . $|kA+lB|,\ k,l\in {\mathbb {N} }$ $k,l$ $|A+B|$

A Rouge-háromszög -egyenlőtlenség bármely halmaz méreteit összefügg, és megmutatja, hogy a halmazok különbségének normalizált mérete pszeudometriának tekinthető, amely tükrözi e halmazok szerkezetének közelségét. [12] $AB,\ BC,\ CA$ $ABC$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Szerkezet

Az additív kombinatorika egyik alapkérdése: milyen szerkezetűek lehetnek vagy kellenek az összeghalmazok. 2020 eleje óta nem ismert olyan nem triviálisan gyors algoritmus, amely meghatározná, hogy egy adott nagy halmaz ábrázolható-e vagy . Ismeretes azonban néhány részeredmény az összeghalmazok szerkezetére vonatkozóan. $A+B,\ (|A|,|B|\geq 2)$ $A+A,\ |A|\geq 2$

Például a valós számok összegeinek halmazai nem rendelkezhetnek kis szorzóduplázással, azaz ha , akkor néhány esetén . [13] A modulo a prím maradékok csoportjában pedig csak olyan halmazok vannak , amelyek ként ábrázolhatók . [14] [15] $A=B+C$ $|AA|\geq |A|^{1+c}$ $c>0$ $p$ $2^{\left({{\frac {1}{2}}+o(1)}\right)p}$ $A+B,\ |A|,|B|\to \infty$

Ismeretes, hogy ha a természetes számok sűrű halmazai, akkor hosszú aritmetikai sorozatokat tartalmaznak . [16] Mindazonáltal ismertek példák olyan sűrű halmazokra, amelyeknek erős felső határa van az ilyen progressziók hosszának. [17] [18] $A,B$ $A+B$ ${\displaystyle {\mathbb {Z} }_{p))$

Lásd még

Irodalom

Freiman, Grigorij Abelevics . A strukturális halmazelmélet kezdetei . - "Tatpoligraf" nyomda. – 1966. (Orosz)

T. Tao , Van H. Vu. Additív kombinatorikusok . — Cambridge University Press. - 2006. - ISBN 0-511-24530-0 .

I. D. Shkredov . Számos új eredmény a magasabb energiákkal kapcsolatban // Proceedings of the Moscow Mathematical Society. - 2013. - T. 74 , sz. 1 . - S. 35-73 . (Orosz)

Erdős Pál , Szemedi Endre . Az egész számok összegeiről és szorzatairól (angol) // Studies in Pure Mathematics. - 1983. - P. 213-218 .

George Shakan. A magasabb energiafelbontásokról és az összeg-szorzat jelenségről // Mathematical Proceedings of the Cambridge Philosophical Society. - 2019. - 1. évf. 167 , iss. 3 . - P. 599-617 .

Ilya D. Shkredov, Dmitrii Zhelezov. Kis termékkészlettel rendelkező készletek additív alapjain . - 2016. - arXiv : math/1606.02320 .

B.Green . Aritmetikai progressziók összeghalmazokban (angol) // Geometriai és funkcionális elemzés GAFA. - 2002. - 20. évf. 12 . - P. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Aritmetikai progressziók összeghalmazokban és -szinte periodicitásban $L^{p}$ // Kombinatorika, valószínűség és számítás. - 2013. - Kt. 22 , iss. 3 . - P. 351-365 .

N. Alon, A. Granville, A. Ubis. Összegek száma véges mezőben // Bulletin of the London Mathematical Society. - 2010. - 20. évf. 42 , iss. 4 .

Imre Z Ruzsa. Aritmetikai progressziók összeghalmazokban (angol) // Acta Arithmetica. - 1991. - 1. évf. 60 , iss. 2 . - P. 191-202 .

J. Bourgain. Az aritmetikai progresszióról egész számok halmazainak összegeiben // A Tribute to Paul Erdos. - 1990. - P. 105-110 .

Ernie Croot, Z. Ruzsa Imre, Tomasz Schoen. Aritmetikai progresszió ritka összegekben . – 2007.

ID Shkredov, T. Schoen. Konvex halmazok összegeiről // Kombinatorika, valószínűség és számítás. - 2011. - P. 793-798 . - arXiv : math/1105.3542 .

G. Elekes, MB Nathanson, IZ Ruzsa. Konvexitás és összeghalmazok (angol) // Journal of Number Theory. - 2000. - Vol. 83 , iss. 2 . - P. 194-201 .

Jegyzetek

↑ Freiman, 1966 , p. 7-8
↑ Tao, Wu, 2006 , p. 54. o. 92
↑ Tao, Wu, 2006 , p. 57
↑ Tao, Wu, 2006 , p. 240
↑ Tao, Wu, 2006 , p. 188; Shkredov, 2013 , 5. §
↑ A Cauchy-Bunyakovsky-egyenlőtlenség szerint , hol a reprezentációk száma $(|A||B|)^{2}={\left({\sum \limits _{x\in A+B}{(A*B)(x)))\right)}^ {2}\leq |A+B|\sum \limits _{x\in A+B}{(A*B)(x)^{2}}=|A+B|E(A,B)$ ${\megjelenítési stílus (A*B)(x)}$ $x=a+b,\ a\in A,\ b\in B$
↑ Freiman, 1966 .
↑ Ezt a kérdést gyakran az additív kombinatorika inverz problémájának nevezik (lásd például Freiman, 1966 , 1.8. szakasz, 19. o.)
↑ Erdős, Szemedi, 1983 ; Shakan, 2019
↑ Shkredov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , p. 60
↑ Shkredov, Zhelezov, 2016 , 2. következmény
↑ Alon, Granville, Ubis, 2010 .
↑ Míg a készletek teljes száma ebben a csoportban nyilvánvalóan $2^{p}$
↑ Bourgain ezt először Bourgainben bizonyította be , 1990-ben . A 2020-as év legjobb eredményét a Green, 2002 érte el , majd ezt követően egy új, általánosabb módszerrel megerősítették: Croot, Laba, Sisask, 2013
↑ Ruzsa, 1991 .
↑ A témával kapcsolatos eredmények áttekintése megtalálható itt: Croot, Ruzsa , Schoen, 2007