Mnoho částek

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. května 2018; kontroly vyžadují 7 úprav .

Množina součtů je koncept aditivní kombinatoriky , odpovídající Minkowského součtu konečných množin .

Definice

Nechť je libovolná grupa a jsou konečné množiny. Pak je jejich součet množinou ${\mbox{G}}$ $A,B\subset {\mbox{G))$

A+B:=\{a+b:a\v A,\ b\v B\}

Pro jednu množinu se její množina součtů nazývá . Vícenásobné součty jsou zkráceny [1] $A$ $A+A$

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

Související definice

Podobně je pro libovolnou operaci definována množina rozdílů , množina produktů , množina kvocientů a podobně. Například sada produktů je definována takto [2] :

{\displaystyle A\times B=\{ab\ :\ a\v A,\ b\v B\))

Hodnota se nazývá konstanta zdvojení [3] a množiny, pro které je omezena, mají malé zdvojnásobení [4] . V souvislosti s teorémem součtu o součinu se často uvažuje o množinách s malým multiplikativním zdvojením , tedy takové, pro které je omezená hodnota [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac {|AA|}{|A|}}$

Vlastnosti

Mocnina množiny součtů souvisí s aditivní energií pomocí nerovnosti [6] , proto se k jejímu odhadu často používá druhá jmenovaná. $A+B$ $E(A,B)$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Součty jedné množiny

Freimanův teorém považuje velikost za indikátor strukturovanosti množiny (pokud je konstanta zdvojení omezená, pak je struktura podobná zobecněné aritmetické progresi ). [7] [8] $A+A$ $A$

Věta o součtu o součinu se vztahuje k velikosti množiny součtů a množiny produktů. Hlavní hypotéza říká, že pro . [9] Kombinace součtu a součinu v jednom výrazu vedla ke vzniku aritmetické kombinatoriky . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subset \mathbb {R}$

Studujeme vliv aplikace konvexní funkce prvek po prvku na sčítatelné množiny na velikost množiny součtů. Pro konvexní posloupnosti jsou známy dolní meze na a . [10] Obecněji, pro konvexní funkci a množinu, problém odhadu a některé podobné jsou někdy považovány za zobecnění věty o součtu-součinu, protože a proto je funkce konvexní. [jedenáct] $|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$

Součty několika množin

Nerovnost Plünnecke-Rouge uvádí, že růst (zvětšení velikosti s ohledem na sčítatelné množiny) násobných součtů v průměru (vzhledem k ) výrazně nepřevyšuje růst . $|kA+lB|,\ k,l\in {\mathbb {N} }$ $k,l$ $|A+B|$

Rougeova trojúhelníková nerovnost dává do souvislosti velikosti libovolných množin a ukazuje, že normalizovanou velikost rozdílu množin lze považovat za pseudometriku, která odráží blízkost struktury těchto množin. [12] $AB,\ BC,\ CA$ $A, B, C$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Struktura

Jednou ze základních otázek aditivní kombinatoriky je: jakou strukturu mohou nebo by měly mít množiny součtů. Od začátku roku 2020 není znám žádný netriviálně rychlý algoritmus, který by určil, zda lze danou velkou množinu reprezentovat jako nebo . Jsou však známy některé dílčí výsledky o struktuře součtových množin. $A+B,\ (|A|,|B|\geq 2)$ $A+A,\ |A|\geq 2$

Například množiny součtů reálných čísel nemohou mít malé multiplikativní zdvojení, tedy pokud , tak pro některé . [13] A ve skupině zbytků modulo a prime jsou pouze množiny, které lze reprezentovat jako . [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$

Je známo, že pokud jsou husté množiny přirozených čísel, pak obsahuje dlouhé aritmetické posloupnosti . [16] Nicméně jsou známy příklady hustých množin se silnou horní hranicí délky takových progresí. [17] [18] $A,B$ $A+B$ ${\displaystyle {\mathbb {Z} }_{p))$

Viz také

Literatura

Freiman, Grigorij Abelevič . Počátky strukturální teorie množin . - Tiskárna "Tatpoligraf". — 1966. (Ruština)

T. Tao , Van H. Vu. Aditivní kombinatoria . — Cambridge University Press. - 2006. - ISBN 0-511-24530-0 .

I. D. Shkredov . Několik nových výsledků o vyšších energiích // Proceedings of the Moscow Mathematical Society. - 2013. - T. 74 , č. 1 . - S. 35-73 . (Ruština)

Paul Erdős , Endre Szemeredi . O součtech a součinech celých čísel (anglicky) // Studies in Pure Mathematics. - 1983. - S. 213-218 .

George Shakan. O rozkladech vyšších energií a fenoménu součtu // Mathematical Proceedings of the Cambridge Philosophical Society. - 2019. - Sv. 167 , iss. 3 . - str. 599-617 .

Ilja D. Škredov, Dmitrij Železov. Na aditivní bázi sad se sadou malých produktů . - 2016. - arXiv : math/1606.02320 .

B.Zelená . Aritmetické posloupnosti v součtech (anglicky) // Geometric & Functional Analysis GAFA. - 2002. - Sv. 12 . - str. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Aritmetické progrese v množinách a -téměř periodicita $L^{p}$ // Kombinatorika, pravděpodobnost a výpočetní technika. - 2013. - Sv. 22 , iss. 3 . - S. 351-365 .

N. Alon, A. Granville, A. Ubis. Počet součtů v konečném poli // Bulletin of the London Mathematical Society. - 2010. - Sv. 42 , iss. 4 .

Imre Z Růžsa. Aritmetické posloupnosti v součtech (anglicky) // Acta Arithmetica. - 1991. - Sv. 60 , iss. 2 . - S. 191-202 .

J. Bourgain. O aritmetických postupech v součtech množin celých čísel // Pocta Paulu Erdovi. - 1990. - S. 105-110 .

Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Aritmetické posloupnosti v řídkých součtech . — 2007.

ID Shkredov, T. Schoen. O součtech konvexních množin // Kombinatorika, pravděpodobnost a počítání. - 2011. - S. 793-798 . - arXiv : math/1105.3542 .

G. Elekes, MB Nathanson, IZ Ruzsa. Convexity and Sumsets (anglicky) // Journal of Number Theory. - 2000. - Sv. 83 , iss. 2 . - S. 194-201 .

Poznámky

↑ Freiman, 1966 , str. 7-8
↑ Tao, Wu, 2006 , str. 54, str. 92
↑ Tao, Wu, 2006 , str. 57
↑ Tao, Wu, 2006 , str. 240
↑ Tao, Wu, 2006 , str. 188; Shkredov, 2013 , § 5
↑ Podle Cauchyho-Bunyakovského nerovnosti , , kde je počet zobrazení $(|A||B|)^{2}={\left({\sum \limits _{x\in A+B}{(A*B)(x)))\right)}^ {2}\leq |A+B|\součet \limits _{x\in A+B}{(A*B)(x)^{2}}=|A+B|E(A,B)$ $(A*B)(x)$ $x=a+b,\ a\v A,\ b\v B$
↑ Freiman, 1966 .
↑ Tato otázka se často nazývá inverzní problém aditivní kombinatoriky (viz např. Freiman, 1966 , oddíl 1.8, s. 19)
↑ Erdős, Szemeredi, 1983 ; Shakan, 2019
↑ Shkredov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , str. 60
↑ Shkredov, Zhelezov, 2016 , následek 2
↑ Alon, Granville, Ubis, 2010 .
↑ Zatímco celkový počet sad v této skupině je zjevně $2^{p}$
↑ Bourgain to poprvé dokázal v Bourgain, 1990 . Nejlepší výsledek za rok 2020 byl získán v Green, 2002 a následně potvrzen novou, obecnější metodou v Croot, Laba, Sisask, 2013
↑ Ruzsa, 1991 .
↑ Přehled výsledků na toto téma lze nalézt v Croot, Ruzsa , Schoen, 2007