A Cauchy–Davenport-lemma az additív számelmélet egyik fontos elemi tétele.
A tétel állítása
Ha
prímszám,
és
szerinti maradékosztályok nemüres halmazai és
, akkor
. Továbbá, ha
akkor
tartalmaz minden
szerinti maradékosztályt. Itt
az
![{\displaystyle \{x+y|x\in A,y\in B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5f514aaf89218c486fe07487419d3b7c4af9582)
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
. Legyen
tetszőleges
szerinti maradékosztály. Legyen
. Nyilván
és
elemszáma ugyanannyi (hiszen
elemeit tükröztük
-re és ciklikusan elforgattuk
-vel). Mivel így
az
és
halmazoknak van közös elemük. De ha
ilyen elem, akkor
, azaz
kongruens egy
-beli és egy
-beli elem összegével.
A tétel első, lényegesebb állítását
elemszámára vonatkozó teljes indukcióval igazoljuk. Ha
egyetlen elemből, mondjuk
-ből áll, akkor a halmazok összege
, tehát
-nak
-vel való ciklikus körbetoltja, ennek valóban annyi eleme van, mint
-nak.
Tegyük most fel, hogy
.
Lemma. Van olyan
maradékosztály hogy ha
, akkor
nemüres és nem egyenlő
-vel.
Bizonyítás. Válasszuk
-ből a különböző
elemeket. Van olyan
, amire
, mert különben
zárt lenne a
hozzárendelésre, de ekkor
bármelyik eleméből kiindulva ismételt hozzáadással
lépésben megkapnánk minden maradékosztályt, tehát
elemszáma
lenne, ellentmondás. Létezik tehát az említett
elem. Azt állítjuk, hogy a
választás jó. Valóban,
nemüres, mert tartalmazza a
elemet. Ugyanakkor
, hiszen, ha lenne
, amire
teljesülne, akkor
lenne, amit kizártunk.
A tétel bizonyításához visszatérve jegyezzük meg, hogy
és
hiszen mindkét esetben ciklikus eltoltról van szó. Elég tehát
-et igazolni.
Legyen
,
. Ezek nemüres halmazok és a szita formula szerint
. Könnyű látni, hogy
és mivel
, az indukciós hipotézis szerint
. Ezzel viszont készen vagyunk, hiszen az eddigiek szerint
Lásd még
A fenti egyenlőtlenség felhasználható az Erdős–Ginzburg–Ziv-tétel bizonyításánál.
Szakirodalom
- A. L. Cauchy: Recherches sur les nombers, J. Ecole Polytechniques, 9(1813), 99–123.
- H. Davenport: On the addition of residue classes, J. London Math. Soc., 10(1935), 30–32.
- H. Davenport: A historical note. J. London Math. Soc., 22 (1947), 100–101.
További információk