Cauchy–Davenport-lemma

A Wikipédiából, a szabad enciklopédiából

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

A tétel állítása[szerkesztés | forrásszöveg szerkesztése]

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.

A tétel bizonyítása[szerkesztés | forrásszöveg szerkesztése]

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=b-a választás jó. Valóban, A'\cap B nemüres, mert tartalmazza a b=a+(b-a) 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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

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

Szakirodalom[szerkesztés | forrásszöveg szerkesztése]

  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.

További információk[szerkesztés | forrásszöveg szerkesztése]