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 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 )
Nevét H. Plünnecke német matematikusról [1] és Rouge Imre magyar matematikusról kapta . [2]
A következő jelölést használjuk
Legyen egy Abel-csoport , . Aztán abból következik |
Ha , akkor .
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 .
Nézzünk egy készletet . Ha , akkor . Másképp
És definíció szerint
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
Ezután a Rouge-féle háromszög egyenlőtlenséget használjuk .
Bármelyikre létezik olyan , hogy ha egy csoport , akkor ebből következik |
Ha , akkor .
Ez az állítás közvetlenül a Rouge-háromszög egyenlőtlenségéből következik
2. lemmaHa , akkor ebből az következik, hogy létezik olyan, hogy és .
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ő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.
Mivel minden elemének legalább különböző előképei vannak, akkor
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
.
Az utolsó egyenlőtlenség igaz, mert .
Tehát, és megismételve ugyanazt az eljárást a helyett , megkaphatjuk a , és általában
.
Eszközök,
Legyen egy Abeli csoport , , . Ezután van egy nem üres részhalmaz , így [2] [6] [7] |
Ha , akkor
Ha , akkor
Ezért, ha a és a növekedési sorrend ismert a növekedésére vonatkozóan , akkor
A Plünnecke-Rouge egyenlőtlenség az összeg-szorzat tétel bizonyítására szolgál