Cauchy–Davenport-lemma

A Wikipédiából, a szabad lexikonból.

A Cauchy–Davenport-lemma az additív számelmélet egyik fontos elemi tétele.

Tartalomjegyzék

[szerkesztés] A tétel állítása

Ha p prímszám, A és B p szerinti maradékosztályok nemüres halmazai és |A|+|B|\leq p+1 akkor

|A|+|B|-1 \le |A+B|.

Továbbá, ha | A | + | B | > p akkor A + B tartalmaz minden p szerinti maradékosztályt. Itt A + B az

\{x+y|x\in A, y\in B\}

komplexusösszeget jelöli.

[szerkesztés] A tétel bizonyítása

Először a második állítást igazoljuk. Tegyük tehát fel, hogy | A | + | B | > p. Legyen c tetszőleges p szerinti maradékosztály. Legyen B'=\{c-x|x\in B\}. Nyilván B és B' elemszáma ugyanannyi (hiszen B elemeit tükröztük p / 2-re és ciklikusan elforgattuk c-vel). Mivel így | A | + | B' | > p az A és B' halmazoknak van közös elemük. De ha x ilyen elem, akkor c\equiv x+(c-x)\pmod{p}, azaz c kongruens egy A-beli és egy B-beli elem összegével.

A tétel első, lényegesebb állítását B elemszámára vonatkozó teljes indukcióval igazoljuk. Ha B egyetlen elemből, mondjuk b-ből áll, akkor a halmazok összege \{x+b|x\in A\}, tehát A-nak b-vel való ciklikus körbetoltja, ennek valóban annyi eleme van, mint A-nak.

Tegyük most fel, hogy |B|\geq 2.

Lemma. Van olyan c maradékosztály hogy ha A' = A + c, akkor A'\cap B nemüres és nem egyenlő B-vel.

Bizonyítás. Válasszuk B-ből a különböző b,b' elemeket. Van olyan a\in A, amire a+(b'-b)\notin A, mert különben A zárt lenne a x\mapsto x+(b'-b) hozzárendelésre, de ekkor A bármelyik eleméből kiindulva ismételt hozzáadással p − 1 lépésben megkapnánk minden maradékosztályt, tehát A elemszáma p lenne, ellentmondás. Létezik tehát az említett a\in A elem. Azt állítjuk, hogy a c = ba választás jó. Valóban, A'\cap B nemüres, mert tartalmazza a b = a + (ba) elemet. Ugyanakkor b'\notin A'\cap B, hiszen, ha lenne a'\in A, amire a'+(b-a)\equiv b' teljesülne, akkor a'\equiv a+(b'-b) lenne, amit kizártunk.


A tétel bizonyításához visszatérve jegyezzük meg, hogy | A' | = | A | és | A' + B | = | A + B | hiszen mindkét esetben ciklikus eltoltról van szó. Elég tehát |A'+B|\geq |A'|+|B|-1-et igazolni.

Legyen A^*=A'\cup B, B^*=A'\cap B. Ezek nemüres halmazok és a szita formula szerint | A * | + | B * | = | A' | + | B | . Könnyű látni, hogy A^*+B^*\subseteq A'+B és mivel | B * | < | B | , az indukciós hipotézis szerint |A^*+B^*|\geq |A^*|+|B^*|-1. Ezzel viszont készen vagyunk, hiszen az eddigiek szerint

|A'+B|\geq |A^*+B^*|\geq |A^*|+|B^*|-1=|A'|+|B|-1.

[szerkesztés] Lásd még

A fenti egyenlőtlenség felhasználható az Erdős–Ginzburg–Ziv-tétel bizonyításánál.

[szerkesztés] Szakirodalom

  1. A. L. Cauchy: Recherches sur les nombers, J. Ecole Polytechniques, 9(1813), 99-123.
  2. H. Davenport: On the addition of residue classes, J. London Math. Soc., 10(1935), 30-32.
  3. H. Davenport: A historical note. J. London Math. Soc., 22 (1947), 100-101.

[szerkesztés] Külső hivatkozások