Plünnecke-Rouge nerovnost

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é 8. března 2020; kontroly vyžadují 4 úpravy .

Nerovnice Plünnecke-Rouge jsou klasickým lemmatem v aditivní kombinatorice . Popisuje omezení na více součtů množin pod známými omezeními na podobné krátké součty. Například omezení na se známými omezeními na . $|A+ABB|$ $|A+B|$

Důkazy Plünnecke-Rougeových nerovností zpravidla nepoužívají strukturu společné množiny, do které a patří , ale používají pouze obecné axiomy skupinové operace , což je činí pravdivými pro libovolné skupiny (zejména pro množiny přirozených a reálných čísel , stejně jako zbytky dělení pro dané číslo ) $A$ $B$

Pojmenováno po německém matematikovi H. Plünnecke [1] a maďarském matematikovi Imre Rouge . [2]

Formulace

Používá se následující zápis

$A+B=\left\lbrace {a+b:a\v A,b\v B}\vpravo\rbrace$

$nA=\left\lbrace {a_{1}+\tečky +a_{n}:a_{1},\tečky ,a_{n}\in A}\vpravo\rbrace$

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

Pro jednu sadu

Nechť je abelovská skupina , . Pak z toho vyplývá $(G,+)$ $A\subset G,K\in {\mathbb {R} }$ $|A+A|\leq K|A|$ $|nA-mA|<K^{n+m}|A|$

Důkaz [3] [4] Lemma

Pokud , tak . $A,B,S\v G,|A+B|\leq K|B|,\forall Z\subset B(Z\ne =B):\ |A+Z|\geq K|Z|$ $|A+B+S|\leq K|B+S|$

Lema je dokázáno indukcí velikosti . Neboť prohlášení je zřejmé. Dále pro některé označujeme . Podle indukční hypotézy, . $S$ $|S|=1$ $x\in S$ $S'=S\setminus \left\lbrace {x}\right\rbrace$ $|A+B+S'|\leq K|B+S'|$

Podívejme se na sadu . Pokud , tak . v opačném případě $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}\vpravo\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}|)$

A podle definice , ${\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|$

Odvození věty z lemmatu

Vybereme podmnožinu , která splňuje požadavky lemmatu. Pak podle lemmatu pro , $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|$

Dále použijeme Rougeho trojúhelníkovou nerovnost .

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

Pro dvě sady

Pro všechny existuje taková, že pokud je skupina , , pak to vyplývá z $n_{1},n_{2},n_{3},n_{4}\geq 0$ $c=c(n_{1},n_{2},n_{3},n_{4})$ $(G,+)$ $A,B\podmnožina 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|$

důkaz [5] Lemma 1

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

Toto tvrzení vyplývá přímo z Rougeho trojúhelníkové nerovnosti

Lemma 2

Jestliže , pak z toho vyplývá, že existuje taková, že a . ${\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|$

Chcete-li to dokázat, zvažte množinu prvků, které mají alespoň reprezentace ve tvaru . Celkový počet párů lze odhadnout shora jako , tak . $S\in A+B$ ${\frac {|A|}{2K}}$ $a+b,a\in A,b\in B$ $(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))$

Navíc, pokud je funkce definována jako , pak pro jakýkoli obrázek formuláře existují alespoň různé inverzní obrázky formuláře odpovídající různým reprezentacím . Je důležité uvažovat právě o takovém uspořádání termínů v předobraze, protože všechny páry jsou zjevně z definice stejné. $\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\v A,b\v B)$ $(a+b,a'+b')$

Protože každý prvek má alespoň různé předobrazy $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|$

Odvození nerovnosti z lemmat

Pro data zvažte množinu získanou v lemmatu 2 a označte pro lemma 1 . Pak lemma 1, $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|$ .

Poslední nerovnost je pravdivá, protože pro . $K>{\frac {3}{2))$ $|A|>1$

Takže, a opakováním stejného postupu pro místo , můžeme dostat , a obecně $|(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|$ .

Prostředek,

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

Zobecnění na libovolný počet množin

Nechť je abelovská skupina , , . Pak existuje neprázdná podmnožina taková, že [2] [6] [7] $(G,+)$ $X,B_{1},\tečky ,B_{k}\subset G$ $|B_{i}+X|\leq K_{i}|X|,i=1,\tečky ,k$ $|B_{1}+\tečky +B_{k}|\leq K_{1}\tečky K_{k}|X|$ $X'\subset X$ $|X'+B_{1}+\tečky +B_{k}|\leq \alpha _{1}\tečky \alpha _{k}|X_{1}|$