Multe sume

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 11 mai 2018; verificările necesită 7 modificări .

Mulțimea sumelor este conceptul de combinatorie aditivă , corespunzătoare sumei Minkowski de mulțimi finite .

Definiție

Fie orice grup și să fie mulțimi finite. Atunci suma lor este setul ${\mbox{G}}$ $A,B\subset {\mbox{G}}$

A+B:=\{a+b:a\in A,\b\in B\)

Pentru un set, setul său de sume se numește . Sumele multiple sunt prescurtate [1] $A$ $A+A$

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

Definiții înrudite

În mod similar, setul de diferențe , setul de produse , setul de coeficienti și altele asemenea sunt definite pentru orice operație. De exemplu, setul de produse este definit după cum urmează [2] :

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

Valoarea se numește constantă de dublare [3] , iar mulțimile pentru care este mărginită se spune că au o dublare mică [4] . În legătură cu teorema produsului sumă , se consideră adesea mulțimi cu dublare multiplicativă mică , adică pentru care valoarea este limitată [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac {|AA|}{|A|}}$

Proprietăți

Puterea mulțimii de sume este legată de energia aditivă prin inegalitatea [6] , deci cea din urmă este adesea folosită pentru estimarea acesteia. $A+B$ $E(A,B)$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Sumele unui set

Teorema lui Freiman consideră mărimea ca un indicator al structurii unei mulțimi (dacă constanta de dublare este limitată, atunci structura este similară cu o progresie aritmetică generalizată ). [7] [8] $A+A$ $A$

Teorema sumă-produs raportează dimensiunea mulțimii de sume și a mulțimii de produse. Ipoteza principală spune că pentru . [9] Combinația de însumare și produs într-o singură expresie a condus la apariția combinatoriei aritmetice . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subset \mathbb {R}$

Studiem influența aplicării element cu element a unei funcții convexe la mulțimi însumabile asupra mărimii mulțimii de sume. Pentru secvențele convexe , limitele inferioare ale și sunt cunoscute . [10] Mai general, pentru o funcție convexă și o mulțime, problema de estimare și unele similare sunt uneori considerate ca o generalizare a teoremei produsului sumă, deoarece și deci , iar funcția este convexă. [unsprezece] $|A+A|$ $|AA|$ $f$ $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$

Sumele mai multor seturi

Inegalitatea Plünnecke-Rouge afirmă că creșterea (creșterea în mărime față de seturile însumabile) a sumelor multiple nu depășește, în medie (în raport cu ), cu mult creșterea lui . $|kA+lB|,\ k,l\in {\mathbb {N} }$ $k,l$ $|A+B|$

Inegalitatea triunghiului Rouge raportează dimensiunile pentru orice mulțimi și arată că dimensiunea normalizată a diferenței de mulțimi poate fi considerată ca o pseudometrică care reflectă apropierea structurii acestor mulțimi. [12] $AB,\BC,\CA$ $A,B,C$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Structura

Una dintre întrebările fundamentale ale combinatoriei aditive este: ce structură pot sau ar trebui să aibă seturile de sume. De la începutul anului 2020, nu se cunoaște un algoritm netrivial de rapid care să determine dacă un anumit set mare poate fi reprezentat ca sau . Cu toate acestea, sunt cunoscute unele rezultate parțiale privind structura mulțimilor de sume. $A+B,\ (|A|,|B|\geq 2)$ $A+A,\ |A|\geq 2$

De exemplu, seturile de sume de numere reale nu pot avea o dublare multiplicativă mică, adică dacă , atunci pentru unii . [13] Și în grupul de reziduuri modulo un prim există doar mulțimi care pot fi reprezentate ca . [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$

Se știe că dacă sunt mulțimi dense de numere naturale, atunci conține progresii aritmetice lungi . [16] Cu toate acestea, sunt cunoscute exemple de seturi dense cu o limită superioară puternică pe lungimea unor astfel de progresii. [17] [18] $A,B$ $A+B$ ${\mathbb {Z} }_{p)$

Vezi și

Literatură

Freiman, Grigori Abelevici . Începuturile teoriei multimelor structurale . - Tipografia „Tatpoligraf”. — 1966. (Rusă)

T. Tao , Van H. Vu. Combinatorii aditivi . — Cambridge University Press. - 2006. - ISBN 0-511-24530-0 .

I. D. Shkredov . Câteva rezultate noi privind energiile superioare // Proceedings of the Moscow Mathematical Society. - 2013. - T. 74 , nr. 1 . - S. 35-73 . (Rusă)

Paul Erdős , Endre Szemeredi . Despre sume și produse de numere întregi (engleză) // Studii în matematică pură. - 1983. - P. 213-218 .

George Shakan. Despre descompunerea de energie superioară și fenomenul de produs sumă // Mathematical Proceedings of the Cambridge Philosophical Society. - 2019. - Vol. 167 , iss. 3 . - P. 599-617 .

Ilya D. Shkredov, Dmitrii Zhelezov. Pe baze aditive ale seturilor cu set mic de produse . - 2016. - arXiv : math/1606.02320 .

B.Verde . Progresii aritmetice în sumsets (engleză) // Analiză geometrică și funcțională GAFA. - 2002. - Vol. 12 . - P. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Progresii aritmetice în sume și -aproape -periodicitate $L^{p}$ // Combinatorică, probabilitate și calcul. - 2013. - Vol. 22 , iss. 3 . - P. 351-365 .

N. Alon, A. Granville, A. Ubis. Numărul de sume într-un câmp finit // Buletinul Societății de Matematică din Londra. - 2010. - Vol. 42 , iss. 4 .

Imre Z Ruzsa. Progresii aritmetice în sumsets (engleză) // Acta Arithmetica. - 1991. - Vol. 60 , iss. 2 . - P. 191-202 .

J. Bourgain. Despre progresiile aritmetice în sume de mulțimi de numere întregi // A Tribute to Paul Erdos. - 1990. - P. 105-110 .

Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Progresii aritmetice în sume rare . — 2007.

ID Shkredov, T. Schoen. Despre sume de mulțimi convexe // Combinatorică, probabilitate și calcul. - 2011. - P. 793-798 . - arXiv : math/1105.3542 .

G. Elekes, MB Nathanson, IZ Ruzsa. Convexitate și sume (engleză) // Journal of Number Theory. - 2000. - Vol. 83 , iss. 2 . - P. 194-201 .

Note

↑ Freiman, 1966 , p. 7-8
↑ Tao, Wu, 2006 , p. 54, p. 92
↑ Tao, Wu, 2006 , p. 57
↑ Tao, Wu, 2006 , p. 240
↑ Tao, Wu, 2006 , p. 188; Shkredov, 2013 , § 5
↑ Conform inegalității Cauci-Bunyakovsky , , unde este numărul de reprezentări $(|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)$ $(A*B)(x)$ $x=a+b,\a\in A,\b\in B$
↑ Freiman, 1966 .
↑ Această întrebare este adesea numită problema inversă a combinatoriei aditive (vezi, de exemplu, Freiman, 1966 , secțiunea 1.8, p. 19)
↑ Erdős, Szemeredi, 1983 ; Shakan, 2019
↑ Shkredov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , p. 60
↑ Shkredov, Zhelezov, 2016 , consecința 2
↑ Alon, Granville, Ubis, 2010 .
↑ În timp ce numărul total de seturi din acest grup este evident $2^{p}$
↑ Bourgain a demonstrat pentru prima dată acest lucru în Bourgain, 1990 . Cel mai bun rezultat pentru 2020 a fost obținut în Green, 2002 , și ulterior reproșat printr-o nouă metodă, mai generală, în Croot, Laba, Sisask, 2013
↑ Ruzsa, 1991 .
↑ O prezentare generală a rezultatelor pe această temă poate fi găsită în Croot, Ruzsa , Schoen, 2007