Plünnecke-Rougen epätasa-arvo

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8.3.2020 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Plünnecke-Rougen epäyhtälöt ovat klassinen lemma additiivisessa kombinatoriikassa . Kuvaa rajoituksia useille joukkojen summille tunnetuilla rajoituksilla samanlaisille lyhyille summille. Esimerkiksi rajoitukset tunnetuilla rajoituksilla . $|A+ABB|$ $|A+B|$

Todisteet Plünnecke-Rougen epäyhtälöistä eivät yleensä käytä yhteisen joukon rakennetta, johon ja kuuluvat , vaan käyttävät vain ryhmäoperaation yleisiä aksioomia , mikä tekee niistä totta mielivaltaisille ryhmille (erityisesti luonnollisten ja reaalilukujen joukot sekä tietyn luvun jakojäännökset ) $A$ $B$

Nimetty saksalaisen matemaatikon H. Plünnecken [1] ja unkarilaisen matemaatikon Imre Rougen mukaan . [2]

Formulaatiot

Käytetään seuraavaa merkintää

$A+B=\left\lhakasulke {a+b:a\in A,b\in B}\oikea\rsulku$

$nA=\left\lhakasulke {a_{1}+\pisteet +a_{n}:a_{1},\pisteet ,a_{n}\in A}\oikea\rhaulu$

$-A=\left\lhakasulku {-a:a\in A}\right\rhaulu$

Yhdelle sarjalle

Olkoon Abelin ryhmä . _ Siitä seuraa sitten ${\näyttötyyli (G,+)}$ $A\subset G,K\in {\mathbb {R} }$ $|A+A|\leq K|A|$ $|nA-mA|<K^{n+m}|A|$

Todiste [3] [4] Lemma

Jos , niin . ${\näyttötyyli A,B,S\in G,|A+B|\leq K|B|,\kaikki Z\alajoukot B(Z\not =B):\ |A+Z|\geq K|Z| }$ $|A+B+S|\leq K|B+S|$

Lemma todistetaan kokoinduktiolla . Sillä lausunto on ilmeinen. Lisäksi joillekin merkitsemme . Induktiohypoteesin mukaan . $S$ $|S|=1$ $x\in S$ $S'=S\setminus \left\lbrace {x}\right\rbrace$ $|A+B+S'|\leq K|B+S'|$

Harkitsemme sarjaa . Jos , niin . Muuten $Z_{x}=\left\lhakasulke {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\lhakasulke {x}\oikea\rhakasulke )\setminus (A+Z_{x}+\left\lhakasulku {x}\oikea\rhaulu ))$

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

Ja määritelmän mukaan ${\displaystyle Z_{x))$

$B+S=(B+S')\cup ((B\setminus Z_{x})+\left\lhakasulku {x}\oikea\rhakasulke )$

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

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

Lauseen johtaminen lemasta

Valitsemme osajoukon , joka täyttää lemman vaatimukset. Sitten lemman mukaan , $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|$

Seuraavaksi käytämme Rougen kolmion epäyhtälöä .

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

Kahdelle sarjalle

Jokaiselle on olemassa sellainen, että jos on ryhmä , , Sitten se seuraa $n_{1},n_{2},n_{3},n_{4}\geq 0$ $c=c(n_{1},n_{2},n_{3},n_{4})$ ${\näyttötyyli (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|$

Todiste [5] Lemma 1

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

Tämä väite seuraa suoraan Rougen kolmion epäyhtälöstä

Lemma 2

Jos , niin siitä seuraa, että on olemassa sellainen, että ja . ${\näyttötyyli 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|$

Tämän todistamiseksi harkitse elementtijoukkoa, jolla on vähintään esitykset muodossa . Parien kokonaismäärä voidaan arvioida ylhäältä , joten . $S\in A+B$ ${\frac {|A|}{2K}}$ ${\näyttötyyli a+b,a\in A,b\in B}$ ${\näyttötyyli (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))$

Lisäksi, jos funktio on määritelty muodossa , niin mille tahansa muodon kuvalle on olemassa ainakin erilaisia käänteiskuvia muodosta, jotka vastaavat :n eri esityksiä . On tärkeää ottaa huomioon juuri tällainen termien järjestys esikuvassa, koska kaikki parit ovat ilmeisesti määritelmän mukaan samoja. $\lambda :(A+B)\times (A+B)\to G$ $\lambda (x,y)=x+y$ ${\näyttötyyli a+b+s\in A+B+S}$ ${\frac {|A|}{2K}}$ ${\näyttötyyli (a+b',a'+b)}$ $a'+b'=s(a\in A,b\in B)$ ${\näyttötyyli (a+b,a'+b')}$

Koska jokaisella elementillä on ainakin eri esikuvat, niin ${\näyttötyyli 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|$

Epätasa-arvon johtaminen lemmoista

Tarkastellaan dataa varten Lemmassa 2 saatua joukkoa ja merkitään Lemmalla 1 . Sitten, Lemma 1, ${\näyttötyyli 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|$ .

Viimeinen epätasa-arvo on totta, koska . $K>{\frac {3}{2))$ $|A|>1$

Joten, ja toistamalla saman menettelyn sijasta , voimme saada , ja yleensä $|(AA)+(BB)|\leq K^{8}|A|$ ${\näyttötyyli (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|$ .

tarkoittaa,

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

Yleistys mielivaltaiseen määrään joukkoja

Olkoon Abelin ryhmä , , . Sitten on ei-tyhjä osajoukko siten, että [2] [6] [7] ${\näyttötyyli (G,+)}$ $X,B_{1},\dots ,B_{k}\subset G$ $|B_{i}+X|\leq K_{i}|X|,i=1,\dots ,k$ $|B_{1}+\pisteet +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}|$