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 ${\displaystyle p}$ prímszám, ${\displaystyle A}$ és ${\displaystyle B}$ ${\displaystyle p}$ szerinti maradékosztályok nemüres halmazai és ${\displaystyle |A|+|B|\leq p+1}$, akkor

${\displaystyle |A|+|B|-1\leq |A+B|}$.

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

${\displaystyle \{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 ${\displaystyle |A|+|B|>p}$. Legyen ${\displaystyle c}$ tetszőleges ${\displaystyle p}$ szerinti maradékosztály. Legyen ${\displaystyle B'=\{c-x|x\in B\}}$. Nyilván ${\displaystyle B}$ és ${\displaystyle B'}$ elemszáma ugyanannyi (hiszen ${\displaystyle B}$ elemeit tükröztük ${\displaystyle p/2}$-re és ciklikusan elforgattuk ${\displaystyle c}$-vel). Mivel így ${\displaystyle |A|+|B'|>p}$ az ${\displaystyle A}$ és ${\displaystyle B'}$ halmazoknak van közös elemük. De ha ${\displaystyle x}$ ilyen elem, akkor ${\displaystyle c\equiv x+(c-x){\pmod {p}}}$, azaz ${\displaystyle c}$ kongruens egy ${\displaystyle A}$-beli és egy ${\displaystyle B}$-beli elem összegével.

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

Tegyük most fel, hogy ${\displaystyle |B|\geq 2}$.

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

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

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

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

${\displaystyle |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