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

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^{\prime }=\{c-x|x\in B\}$. Nyilván $B$ és $B^{\prime }$ elemszáma ugyanannyi (hiszen $B$ elemeit tükröztük $p/2$-re és ciklikusan elforgattuk $c$-vel). Mivel így $|A|+|B^{\prime }|>p$ az $A$ és $B^{\prime }$ halmazoknak van közös elemük. De ha $x$ ilyen elem, akkor $c\equiv x+(c-x)(\mathrm{mod}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|\ge 2$.

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

Bizonyítás. Válasszuk $B$-ből a különböző $b,b^{\prime }$ elemeket. Van olyan $a\in A$, amire $a+(b^{\prime }-b)\notin A$, mert különben $A$ zárt lenne a $x\mapsto x+(b^{\prime }-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^{\prime }\cap B$ nemüres, mert tartalmazza a $b=a+(b-a)$ elemet. Ugyanakkor $b^{\prime }\notin A^{\prime }\cap B$, hiszen, ha lenne $a^{\prime }\in A$, amire $a^{\prime }+(b-a)\equiv b^{\prime }$ teljesülne, akkor $a^{\prime }\equiv a+(b^{\prime }-b)$ lenne, amit kizártunk.

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

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

$|A^{\prime }+B|\ge |A^{*}+B^{*}|\ge |A^{*}|+|B^{*}|-1=|A^{\prime }|+|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 Sablon:Wayback
• MathWorld szócikk
• Fórumrészlet a tétellel kapcsolatban
• Harold Davenportról a The MacTutor History of Mathematics archive-ból [1] Sablon:Wayback