Plünnecke-Rouge egyenlőtlenség

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

A Plünnecke-Rouge egyenlőtlenségek az additív kombinatorika klasszikus lemmája . Leírja a halmazok több összegére vonatkozó korlátozásokat a hasonló rövid összegekre vonatkozó ismert korlátozások mellett. Például korlátozások a következőre vonatkozó ismert korlátozásokkal: . $|A+ABB|$ $|A+B|$

A Plünnecke-Rouge egyenlőtlenségek bizonyítása általában nem annak a közös halmaznak a szerkezetét használja, amelyhez és tartozik, hanem csak a csoportművelet általános axiómáit használják , ami igazzá teszi őket tetszőleges csoportokra (különösen a természetes és valós számok halmazai , valamint egy adott szám osztási maradékai ) $A$ $B$

Nevét H. Plünnecke német matematikusról [1] és Rouge Imre magyar matematikusról kapta . [2]

Formulációk

A következő jelölést használjuk

$A+B=\left\lkapcsos zárójel {a+b:a\in A,b\in B}\right\rkapcsos zárójel$

$nA=\left\lkapcsos zárójel {a_{1}+\pontok +a_{n}:a_{1},\pontok ,a_{n}\in A}\right\rkapcsos zárójel$

$-A=\left\lkapcsos zárójel {-a:a\in A}\right\rbrace$

Egy készlethez

Legyen egy Abel-csoport , . Aztán abból következik ${\megjelenítési stílus (G,+)}$ $A\subset G,K\in {\mathbb {R} }$ $|A+A|\leq K|A|$ $|nA-mA|<K^{n+m}|A|$

Bizonyíték [3] [4] Lemma

Ha , akkor . $A,B,S\in G,|A+B|\leq K|B|,\all Z\all B(Z\not =B):\ |A+Z|\geq K|Z|$ $|A+B+S|\leq K|B+S|$

A lemmát méretindukcióval igazoljuk . Mert az állítás nyilvánvaló. Továbbá egyeseknél azt jelöljük . Az indukciós hipotézis szerint . $S$ $|S|=1$ $x\in S$ $S'=S\setminus \left\lbrace {x}\right\rbrace$ $|A+B+S'|\leq K|B+S'|$

Nézzünk egy készletet . Ha , akkor . Másképp $Z_{x}=\left\lkapcsos zárójel {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\lkapcsos zárójel {x}\right\rbrace )\setminus (A+Z_{x}+\left\lkapcsos zárójel {x}\jobbra\rkapcsos zárójel ))$

$|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}|)$

És definíció szerint ${\displaystyle 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|$

A tétel levezetése a lemmából

Olyan részhalmazt választunk, amely megfelel a lemma követelményeinek. Ezután a lemmája szerint $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|$

Ezután a Rouge-féle háromszög egyenlőtlenséget használjuk .

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

Két készlethez

Bármelyikre létezik olyan , hogy ha egy csoport , akkor ebből következik $n_{1},n_{2},n_{3},n_{4}\geq 0$ $c=c(n_{1},n_{2},n_{3},n_{4})$ ${\megjelenítési stílus (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|$

Bizonyíték [5] 1. lemma

Ha , akkor . $C,D\in G$ $|CC|<\left({\frac {|C+D|}{|D|}}\right)|C+D|$

Ez az állítás közvetlenül a Rouge-háromszög egyenlőtlenségéből következik

2. lemma

Ha , akkor ebből az következik, hogy létezik olyan, hogy és . ${\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|$

Ennek bizonyításához vegyük figyelembe azon elemek halmazát, amelyeknek legalább reprezentációi vannak a formában . A párok összlétszáma felülről becsülhető , így . $S\in A+B$ ${\frac {|A|}{2K}}$ ${\megjelenítési stílus a+b,a\A-ban,b\B-ben}$ ${\megjelenítési stílus (a,b)\in 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}}$

Sőt, ha a függvény definíciója : , akkor az alak bármely képéhez legalább különböző inverz képei vannak az alaknak , amelyek megfelelnek a különböző reprezentációknak . Fontos, hogy az előképben a kifejezések ilyen elrendezését vegyük figyelembe, mert nyilvánvalóan minden pár definíció szerint azonos. $\lambda :(A+B)\times (A+B)\to G$ $\lambda (x,y)=x+y$ $a+b+s\in A+B+S$ ${\frac {|A|}{2K}}$ ${\megjelenítési stílus (a+b',a'+b)}$ $a'+b'=s(a\in A,b\in B)$ ${\megjelenítési stílus (a+b,a'+b')}$

Mivel minden elemének legalább különböző előképei vannak, akkor $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|$

Az egyenlőtlenség származtatása lemmákból

Az adatokhoz tekintsük a 2. lemmában kapott halmazt, és jelöljük az 1. lemmára . Aztán az 1. lemma szerint ${\Displaystyle A,B\in 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|$ .

Az utolsó egyenlőtlenség igaz, mert . $K>{\frac {3}{2}}$ $|A|>1$

Tehát, és megismételve ugyanazt az eljárást a helyett , megkaphatjuk a , és általában $|(AA)+(BB)|\leq K^{8}|A|$ ${\megjelenítési stílus (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|\Jobbra |2nA-2nA+2nB-2nB|\leq (K^{c})^{8}|nA-nA |\leq K^{(9c)}|A|$ .

Eszközök,

$|(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|$

Általánosítás tetszőleges számú halmazra

Legyen egy Abeli csoport , , . Ezután van egy nem üres részhalmaz , így [2] [6] [7] ${\megjelenítési stílus (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}|$

Főbb következmények

Ha , akkor $|A+A|\leq K|A|$ $|AA|\leq K|A|$

Ha , akkor $|AA|\leq K|A|$ $|A+A|\leq K^{8}|A|$

Ezért, ha a és a növekedési sorrend ismert a növekedésére vonatkozóan , akkor $K\in {\mathbb {R} }$ ${\displaystyle |A+A|,A\subset {\mathbb {F} }_{p))$ $p$

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

Alkalmazások

A Plünnecke-Rouge egyenlőtlenség az összeg-szorzat tétel bizonyítására szolgál

Linkek

M. Z. Garaev, Halmazok összegei és szorzatai, valamint racionális trigonometrikus összegek becslései elsőrendű mezőkben Archiválva : 2017. december 11., a Wayback Machine -nél

Jegyzetek

↑ H. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math. 243:171–183, 1970
↑ 1 2 Ruzsa I. Z., „A gráfelmélet alkalmazása az additív számelméletre”, Sci. Ser. Egy matek. sci. (NS), 3 (1989), 97–109.
↑ Harald Helfgott előadásának szöveges összefoglalója a Szentpétervári Állami Egyetemen (elérhetetlen link)
↑ Harald Helfgott előadása a Szentpétervári Állami Egyetemen
↑ Boaz Barak, Luca Trevisan, Avi Wigderson, "Az additív kombinatorika mini tanfolyama" (hivatkozás nem elérhető) . Letöltve: 2017. október 8. Az eredetiből archiválva : 2015. február 6.. (határozatlan)
↑ IZ Ruzsa, „Véges halmazok összegei”, Számelmélet (New York, 1991–1995), Springer, New York, 1996, 281–293.
↑ M. Z. Garaev, Halmazok összegei és szorzatai, valamint racionális trigonometrikus összegek becslései főrendű mezőkben, USP, 2010, 65. kötet, 4. szám (394), DOI: http://dx.doi.org/10.4213/rm9367