Cauchy–Davenport-lemma
A Wikipédiából, a szabad lexikonból.
A Cauchy–Davenport-lemma az additív számelmélet egyik fontos elemi tétele.
Tartalomjegyzék |
[szerkesztés] A tétel állítása
Ha p prímszám, A és B p szerinti maradékosztályok nemüres halmazai és
akkor
.Továbbá, ha | A | + | B | > p akkor A + B tartalmaz minden p szerinti maradékosztályt. Itt A + B az
komplexusösszeget jelöli.
[szerkesztés] 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
. 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
, 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
, tehát A-nak b-vel való ciklikus körbetoltja, ennek valóban annyi eleme van, mint A-nak.
Tegyük most fel, hogy
.
Lemma. Van olyan c maradékosztály hogy ha A' = A + c, akkor
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
, amire
, mert különben A zárt lenne a
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
elem. Azt állítjuk, hogy a c = b − a választás jó. Valóban,
nemüres, mert tartalmazza a b = a + (b − 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 | A' | = | A | és | A' + B | = | A + B | 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 | A * | + | B * | = | A' | + | B | . Könnyű látni, hogy
és mivel | B * | < | B | , az indukciós hipotézis szerint
. Ezzel viszont készen vagyunk, hiszen az eddigiek szerint

[szerkesztés] Lásd még
A fenti egyenlőtlenség felhasználható az Erdős–Ginzburg–Ziv-tétel bizonyításánál.
[szerkesztés] 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.
[szerkesztés] Külső hivatkozások
- PlanetMath szócikk
- MathWorld szócikk
- Fórumrészlet a tétellel kapcsolatban
- Harold Davenportról a The MacTutor History of Mathematics archive-ból [1]



Based on work by