Inegalitatea Plünnecke-Rouge

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 martie 2020; verificările necesită 4 modificări .

Inegalitățile Plünnecke-Rouge sunt o lemă clasică în combinatoria aditivă . Descrie restricții asupra sumelor multiple de seturi sub restricții cunoscute asupra sumelor scurte similare. De exemplu, restricții pe cu restricții cunoscute pe . $|A+ABB|$ $|A+B|$

Demonstrațiile inegalităților Plünnecke-Rouge, de regulă, nu folosesc structura mulțimii comune căreia îi aparțin și , ci folosesc doar axiomele generale ale operației de grup , ceea ce le face adevărate pentru grupuri arbitrare (în special, pentru seturi de numere naturale și reale , precum și resturile de diviziune pentru un număr dat ) $A$ $B$

Numit după matematicianul german H. Plünnecke [1] și matematicianul maghiar Imre Rouge . [2]

Formulări

Se folosește următoarea notație

$A+B=\left\lbrace {a+b:a\in A,b\in B}\right\rbrace$

$nA=\left\lbrace {a_{1}+\dots +a_{n}:a_{1},\dots ,a_{n}\in A}\right\rbrace$

$-A=\left\lbrace {-a:a\in A}\right\rbrace$

Pentru un set

Să fie un grup abelian , . Apoi rezultă din $(G,+)$ $A\subset G,K\in {\mathbb {R} }$ $|A+A|\leq K|A|$ $|nA-mA|<K^{n+m}|A|$

Dovada [3] [4] Lema

Dacă , atunci . $A,B,S\in G,|A+B|\leq K|B|,\forall Z\subset B(Z\nu =B):\ |A+Z|\geq K|Z|$ $|A+B+S|\leq K|B+S|$

Lema este dovedită prin inducerea mărimii . Căci afirmația este evidentă. Mai mult, pentru unii notăm . Prin ipoteza inducției, . $S$ $|S|=1$ $x\în S$ $S'=S\setminus \left\lbrace {x}\right\rbrace$ $|A+B+S'|\leq K|B+S'|$

Să luăm în considerare un set . Dacă , atunci . In caz contrar $Z_{x}=\left\lbrace {b+x\in B+S':b\in B}\right\rbrace$ $Z_{x}=B$ $|A+B+S|=|A+B+S'|\leq K|B+S'|=K|B+S|$

$A+B+S=(A+B+S')\cup ((A+B+\left\lbrace {x}\right\rbrace)\setminus (A+Z_{x}+\left\lbrace {x}\dreapta\rbrace ))$

$|A+B+S|=|A+B+S'|+|A+B|-|A+Z_{x}|\leq K|B+S'|+K|B|-K |Z_{x}|=K(|B+S'|+|B|-|Z_{x}|)$

Și, prin definiție , $Z_{x)$

$B+S=(B+S')\cup ((B\setminus Z_{x})+\left\lbrace {x}\right\rbrace )$

$|B+S|=|B+S'|+|B|-|Z_{x}|$

$|A+B+S|\leq K|B+S|$

Derivarea teoremei din lemă

Alegem o submulțime care satisface cerințele lemei. Apoi, conform lemei pentru , $B=\arg \min \limits _{B\subset A,|B|\geq 1}{\frac {|A+B|}{|B|}}$ $S=(n-1)A$

$|nA+B|=|A+B+(n-1)A|\leq K|(n-1)A+B|=|A+B+(n-2)A|\leq K^{ 2}|(n-2)A+B|\leq ...\leq K^{(n-1)}|A+B|\leq K^{n}|A|$

În continuare, folosim inegalitatea triunghiului Rouge .

$|B||nA-mA|=|-B||nA-mA|\leq |nA+B||mA+B|\leq K^{(n+m)}|A|$

Pentru două seturi

Pentru orice există astfel încât dacă este un grup , , atunci rezultă din $n_{1},n_{2},n_{3},n_{4}\geq 0$ $c=c(n_{1},n_{2},n_{3},n_{4})$ $(G,+)$ $A,B\subset G,|A|=|B|>1$ $K\in {\mathbb {R} }$ $|A+B|\leq K|A|$ $|n_{1}A+n_{2}A-n_{3}B-n_{4}B|\leq K^{c}|A|$

Dovada [5] Lema 1

Dacă , atunci . $C,D\în G$ $|CC|<\left({\frac {|C+D|}{|D|}}\right)|C+D|$

Această afirmație decurge direct din inegalitatea triunghiului Rouge

Lema 2

Dacă , atunci rezultă din faptul că există astfel încât și . ${\displaystyle A,B\in G,|A|=|B|,K\in {\mathbb {R} ))$ $|A+B|\leq K|A|$ $S\subset A+B$ $|S|>{\frac {|A|}{2}}$ $|A+B+S|<K^{3}|A|$

Pentru a demonstra acest lucru, luați în considerare mulțimea elementelor care au cel puțin reprezentări în forma . Numărul total de perechi poate fi estimat de sus ca , deci . $S\in A+B$ ${\frac {|A|}{2K}}$ $a+b,a\in A,b\in B$ $(a,b)\în A\times B$ $|A|^{2}=|A||B|\leq |S||A|+(|A+B|-|S|){\frac {|A|}{2K}}\ leq |S||A|+{\frac {K|A|^{2}}{2K}}=|S||A|+{\frac {|A^{2}|}{2}}$ $|S|>{\frac {|A|}{2}}$

Mai mult, dacă funcția este definită ca , atunci pentru orice imagine a formei există cel puțin diferite imagini inverse ale formei corespunzătoare diferitelor reprezentări ale lui . Este important să luăm în considerare doar o astfel de aranjare a termenilor în preimagine, deoarece toate perechile sunt în mod evident aceleași prin definiție. $\lambda:(A+B)\times (A+B)\to G$ $\lambda (x,y)=x+y$ $a+b+s\in A+B+S$ ${\frac {|A|}{2K}}$ $(a+b',a'+b)$ $a'+b'=s(a\in A,b\in B)$ $(a+b,a'+b')$

Deoarece fiecare element al are cel puțin preimagini diferite, atunci $A+B+S$ ${\frac {|A|}{2K}}$

$|A+B+S|{\frac {|A|}{2K}}\leq |A+B|^{2}$

$|A+B+S|\leq {\frac {(K|A|)^{2}}{\left({\frac {|A|}{2K}}\right)))=K ^{3}|A|$

Derivarea inegalității din leme

Pentru date, se consideră mulțimea obținută în Lema 2 și se notează pentru Lema 1 . Apoi, după Lema 1, $A,B\în G$ $S$ $C=A+B,D=S$

$|(A+B)-(A+B)|\leq \left({\frac {|A+B+S|}{|S|}}\right)|A+B+S|\ leq {\frac {(K^{3}|A|)^{2}}{\left({\frac {|A|}{2}}\right)}}\leq 2K^{6}|A |\leq K^{8}|A|$ .

Ultima inegalitate este adevărată, deoarece pentru . $K>{\frac {3}{2}}$ $|A|>1$

Deci, și, repetând aceeași procedură pentru în loc de , putem obține , și în general $|(AA)+(BB)|\leq K^{8}|A|$ $(AA), (BB)$ $A,B$ $|(A+AAA)+(B+BBB)|\leq (K^{8})^{8}|AA|\leq K^{64}K^{8}|A|=K^ {72}|A|$

$|nA-nA+nB-nB|\leq K^{c}|A|\Rightarrow |2nA-2nA+2nB-2nB|\leq (K^{c})^{8}|nA-nA |\leq K^{(9c)}|A|$ .

Mijloace,

$|(2^{k})A-(2^{k})A+(2^{k})B-(2^{k})B|\leq K^{(9^{(}) k+1))}|A|$

$|n_{1}A-n_{2}A+n_{3}B-n_{4}B|\leq K^{81\max(n_{1},n_{2},n_{3 },n_{4})^{\log _{2}{9}}}|A|\leq K^{(81(n_{1}+n_{2}+n_{3}+n_{4} )^{3.17})}|A|$

Generalizare la un număr arbitrar de mulțimi

Fie un grup abelian , , . Apoi , există o submulțime nevid , astfel încât [2] [6] [7] $(G,+)$ $X,B_{1},\dots,B_{k}\subset G$ $|B_{i}+X|\leq K_{i}|X|,i=1,\dots ,k$ $|B_{1}+\dots +B_{k}|\leq K_{1}\dots K_{k}|X|$ $X'\subset X$ $|X'+B_{1}+\dots +B_{k}|\leq \alpha _{1}\dots \alpha _{k}|X_{1}|$

Principalele consecințe

Dacă , atunci $|A+A|\leq K|A|$ $|AA|\leq K|A|$

Dacă , atunci $|AA|\leq K|A|$ $|A+A|\leq K^{8}|A|$

Prin urmare, dacă ordinea de creștere pentru și este cunoscută pentru creșterea lui , atunci $K\in {\mathbb {R} }$ $|A+A|,A\subset {\mathbb {F} }_{p)$ $p$

$|A+A|\leq K^{\Theta (1)}|A|\iff |AA|\leq K^{\Theta (1)}|A|$

Aplicații

Inegalitatea Plünnecke-Rouge este folosită pentru a demonstra teorema produsului sumă

Link -uri

M. Z. Garaev, Sume și produse ale mulțimilor și estimări ale sumelor trigonometrice raționale în câmpuri de ordin primar Arhivat 11 decembrie 2017 la Wayback Machine

Note

↑ H. Pl¨unnecke. Eine zahlenttheoretische anwendung der graphtheorie. J. Reine Angew. Math. 243:171–183, 1970
↑ 1 2 I. Z. Ruzsa, „An application of graph theory to additive number theory”, Sci. Ser. O matematică. sci. (NS), 3 (1989), 97–109.
↑ Rezumatul text al prelegerii lui Harald Helfgott la Universitatea de Stat din Sankt Petersburg (link inaccesibil)
↑ Prelegere de Harald Helfgott la Universitatea de Stat din Sankt Petersburg
↑ Boaz Barak, Luca Trevisan, Avi Wigderson, „Mini course of additive combinatorics” (link nu este disponibil) . Consultat la 8 octombrie 2017. Arhivat din original pe 6 februarie 2015. (nedefinit)
↑ IZ Ruzsa, „Sume de mulțimi finite”, Teoria numerelor (New York, 1991–1995), Springer, New York, 1996, 281–293.
↑ M. Z. Garaev, Sums and products of sets and estimates of rational trigonometric sums in fields of prime order, USP, 2010, volumul 65, numărul 4(394), DOI: http://dx.doi.org/10.4213/rm9367