Cauchy–Davenport-lemma

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

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\leq |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

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

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

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.

További információk

• PlanetMath szócikk Archiválva 2005. február 22-i dátummal a Wayback Machine-ben
• MathWorld szócikk
• Fórumrészlet a tétellel kapcsolatban
• Harold Davenportról a The MacTutor History of Mathematics archive-ból [1] Archiválva 2006. február 8-i dátummal a Wayback Machine-ben