Erdős–Ginzburg–Ziv-tétel

Az Erdős–Ginzburg–Ziv-tétel (röviden EGZT) egy matematikai (azon belül kombinatorikus számelméleti) tétel, melyet 1961-ben bizonyított három névadója (Erdős Pál, Abraham Ginzburg és Abraham Ziv: Theorem in additive number Theory. Bull. Research Council, Israel, 10F; 41-43; 1961.).

A tétel azt mondja ki, hogy ha m pozitív egész, akkor 2m-1 db egész szám között biztosan van m darab, melyek összege osztható m-mel. (Nem feltétlenül szükséges, hogy páronként különböző egész számok legyenek, hisz úgyis modulo m számolunk.)

Ezeknél némiképp többet állító átfogalmazás („extremális EGZT”) a következő: Az a legkisebb k pozitív egész, melyre igaz, hogy ennyi szám között már biztosan vagy egy adott m pozitív egésszel osztható szám m-es, épp k = 2m-1. E megfogalmazás következménye a fentieknek (ld. lentebb).

A tételt különösen érdekessé teszi részint Erdős Pál neve (és így magyar vonatkozása), részint „filozófiai” kapcsolata az ún. Ramsey-problémakörrel (ld. lentebb), részint pedig alapvető szerepe a kombinatorikus számelmélet egy új ága, a nullösszeg-problémakör létrejöttében.

Bizonyítások

Az alábbi három bizonyítás közül mindkettő arra a segédtételre épül, hogy elegendő az állítást prím m-ekre bizonyítani.

Segédtétel

Ha az EGZT igaz a p,q pozitív egész számokra, akkor igaz pq-ra is.

Először teljes indukcióval belátjuk, hogy kp+(p-1) darab egész számból álló felsorolásból (k pozitív egész) kiválaszthatók az $a_{1},\dots ,a_{kp}$ egész számok úgy, hogy minden $0\leq i\leq k-1$-re $a_{ip+1}+a_{ip+2}+\dots +a_{(i+1)p}$ osztható legyen p-vel.

Ez k=1-re igaz, hisz ez az EGZT p-re. Feltéve, hogy az állítás igaz valamely k-ra, látható, hogy egy kp+(2p-1) darab egész számból álló listából kiválaszthatók az $a_{1},\dots ,a_{kp}$ egész számok a megadott tulajdonsággal. Ha ezeket a számokat kihúzzuk a listából, marad 2p-1 darab egész szám: mivel az EGZT p-re teljesül, így kiválaszthatók közülük az $a_{kp+1},\dots ,a_{(k+1)p}$ egészek úgy, hogy összegük p-vel legyen osztható. Ezzel megtettük az indukciós lépést, hisz megadtuk a módot az alkalmas számok kiválasztására (k+1)-re is.

Alkalmazzuk az imént belátott állítást k=2q-1 esetben! Ezzel kapjuk, hogy (2q-1)p+(p-1)=2pq-1 darab egész szám közül kiválaszthatók az $a_{1},\dots ,a_{(2q-1)p}$ egész számok azzal a tulajdonsággal, hogy $b_{i}:={\frac {a_{ip+1}+a_{ip+2}+\dots +a_{(i+1)p}}{p}}$ minden 0 és 2q-2 közötti i-re egész szám.

Ha most az EGZT állítását q-ra alkalmazzuk, látjuk, hogy a $b_{0},b_{1},\dots ,b_{2q-2}$ felsorolásból kiválasztható q darab szám oly módon, hogy összegük q-val osztható legyen. Visszahelyettesítve a $b_{i}$ számok definícióját, láthatóvá válik, hogy ezzel pq darab $a_{i}$ számot sikerült kiválasztani, melyeknek összege pq-val is osztható. Ez pedig éppen az EGZT pq-ra. A segédtételt igazoltuk.

Bizonyítás prímekre I.

Belátjuk a tételt az $(a_{1},a_{2},\dots ,a_{2p-1})$ számsorozatra, ahol p prím. Tekintsük ehhez a következő kongruenciarendszert:

$x_{1}^{p-1}+x_{2}^{p-1}+\dots +x_{2p-1}^{p-1}\equiv 0{\pmod {p}}$,

$a_{1}x_{1}^{p-1}+a_{2}x_{2}^{p-1}+\dots +a_{2p-1}x_{2p-1}^{p-1}\equiv 0{\pmod {p}}$.

Ebben a kongruenciarendszerben a változók száma 2p-1, míg a fokszámok összege 2p-2, továbbá a kongruenciarendszert kielégíti a triviális $x_{1}=\dots =x_{2p-1}=0\mod p$ megoldás. A Chevalley-tételt alkalmazva, kapjuk, hogy van a kongruenciarendszernek nemtriviális $(x_{1},\dots ,x_{2p-1})$ megoldása.

Mit jelent mindez? Az $x_{i}^{p-1}$ érték a Kis-Fermat-tétel szerint 0 vagy 1 lehet modulo p, és az első kongruencia szerint az 1-gyel kongruens $x_{i}^{p-1}$-k száma p-vel osztható, így 0 vagy p lehet. Előbbi esetben lesz minden $x_{i}$ osztható p-vel, ami a triviális megoldást adja. A nemtriviális megoldásban éppen p darab $x_{i}^{p-1}$ érték lesz 1, a többi pedig nulla lesz (modulo p). De ekkor a második kongruenciát tekintve, a bal oldalon modulo p pontosan p darab $a_{i}$ összege fog állni, ami a kongruencia szerint p-vel osztható. Ezt állítja az EGZT p-re.

Bizonyítás prímekre II.

Forrás.

Bizonyítás prímekre III.

A tétel következik az ún. Cauchy–Davenport-lemmából is, nevezetesen, hogy ha A,B a p prím modulusú maradékosztálycsoport két nemüres részhalmaza (azaz ∅≠A,B⊆ℤ_p), akkor érvényes a következő egyenlőtlenség:

|A+B| ≥ min{p, |A|+|B|-1}

.

Ebből az egyenlőtlenségből is levezethető az EGZT.

A tétel következik a segédtételből és a prímekre vonatkozó változatából

Az EGZT m=1-re semmitmondó: 1 darab egész szám osztható lesz 1-gyel.

Tegyük fel indirekt, hogy valamely m>1-re nem igaz az EGZT, és válasszuk ki az ilyen m-ek közül a legkisebbet. Az m nem lehet prímszám, hisz azokra az imént beláttuk az állítást. Ezért m összetett: felírható m=pq alakban, ahol 1<p,q<m. Mivel m-et a legkisebb "rossznak" választottuk, azért EGZT érvényes p-re és q-ra is. Azonban a segédtétel szerint m=pq-ra is teljesül az EGZT, ami ellentmondás. Vagyis minden m>1 egészre fennáll az EGZT.

A tétel „rokonsága” a Ramsey-elmélettel

A tétel által vizsgált probléma hasonlít a gráfelméletben Ramsey-féle problémáknak nevezett feladatokhoz ((ld. pl. itt)), melyek olyan kérdéseket vizsgálnak, hogy – pontatlanul fogalmazva – adott gráf, alakzat vagy hasonló struktúra (például egy kétféle színnel élszínezett gráf) esetén mekkora méretűnek kell legalább lennie azoknak az alakzatoknak, amelyekben részalakzatként az adott alakzat előfordul. A Ramsey-problémakör filozófiáját nagyjából a következőképp foglalhatjuk össze: „Ha egy struktúra elég nagy, akkor az nem kerülheti el az igen szabályos részstruktúrákat” ^;.

A tétel további megfogalmazásai és általánosításai

Fő szócikk: nullösszeg-problémák

Átfogalmazás maradékosztályokra

A tételnek eredeti publikálása óta sokféle általánosítása látott napvilágot.

• Néhány évvel az 1961-es cikk után Erdős következő formában is átfogalmazta a tételt: Legyen m>0 természetes szám, ekkor 2m-1 db ℤ_m-beli mod m maradékosztály között biztosan van m darab, melyek összege a 0 maradékosztály (ez az állítás közvetlen következménye az EGZ-tételnek). Ez még nem igazán általánosítás, de a probléma átkódolása egy olyan matematikai ismeretterület nyelvezetére-felfogására, melyen belül mozogva e probléma könnyen és sokféleképp általánosítható. A tételt ezután jobbára a maradékosztályok nyelvén fogalmazták meg és általánosították.
• Az általánosításnak egy útja egy két változót tartalmazó feladatból három változót tartalmazót konstruál, ilyen volt 1969-ben J. E. Olsoné: Legyen 1<k<m, k és m egészek, és k|m. Ekkor egész számok bármely m+k-1 elemű halmazában található egy m elemű részhalmaz úgy, hogy elemei S összegére igaz legyen S ≡ 0 (mod k). (On a combinatorial problem of finite Abelian groups; I. and II., J. Number Theory, 1 (1969), 8-10, 195-199.)

Ezek az átfogalmazások adnak lehetőséget az EGZT kiterjesztése egész számokról vagy akár egész maradékosztályokról additív Abel-csoportokra, ld. lentebb.

Extremális EGZT: a 2m-1 korlát (nem-)javíthatósága

Ha elfogadjuk, amit az EGZT állít, akkor az az erősebb megfogalmazás is elég könnyen belátható, hogy a tételben megfogalmazott alsó korlát, 2m-1, már nem javítható, azaz 2m-2 db. szám már esetleg lehet olyan, hogy akárhogyan is választunk ki közülük m darabot, ezeket összeadva, a kapott összeg nem lesz m-mel osztható. Pl.

• m = 1-re 2m-2 = 0; és 0 darab szám közt tényleg nincs mindig (sőt, sosincs) 1 darab, mely(ek összege) 1-gyel osztható lenne.
• m = 2-re 2m-2 = 2, és 2 darab szám között sincs mindig 2 darab, melyek összege 2-vel osztható lenne. Például az {1,2} kételemű halmazban nincs két darab ilyen szám, mert 1+2 = 3, ami nem páros.
• m = 3-ra 2m-2 = 4, és 4 darab szám közt sincs mindig 3 darab, melyek összege 3-mal osztható. Például ha a számok 3-mal való osztásai maradékai rendre 0,0,1,1; akkor akárhogy is kombináljuk őket, mindig 1 vagy maximum 2 3-mal való osztási maradékú összeget kapunk.
• … általában, tetszőleges m-re 2m-2 olyan szám, melyek között m-1 darab 0 maradékot ad m-mel osztva, a többi m-1 pedig 1 maradékot, egy olyan "szerencsétlenül" választott szám-(2m-2)-esre példa, melyek közül akárhogy is válasszunk ki m darabot, sosem kapunk m-mel oszthatót, hisz tetszőleges m-tagú összeg osztási maradéka legfeljebb m-1.

Könnyen belátható az is (B. Peterson – T. Yuster: A generalization of an addition theorem for solvable groups, Can. J. Math. XXXVI (3), 1984; 529.–536., ettől függetlenül A. Bialostocki – P. Dierker: On Erdős–Ginzburg–Ziv theorem and the Ramsey numbers for stars and matchings, Discrete Mathematics 110; 1992, 1.–8.), hogy bármely ℤ_n-beli 2n−2 hosszúságú sorozat, ha a következő alakú:

$\underbrace {a,a,...,a}$ ;	$\underbrace {b,b,...,b}$
${\mbox{ }}_{n-1-szer}$	${\mbox{ }}_{n-1-szer}$

– feltéve, ha a,b∈ℤ_n és a≠b – tartalmaz egy n hosszúságú nem nullával kongruens összegű részsorozatot.

Szimpla és extremális átfogalmazások additív csoportokra

Ezek az átfogalmazások adnak lehetőséget az EGZT kiterjesztése egész számokról vagy akár egész maradékosztályokról additív Abel-csoportokra.

• Ezt már az előbb említett Olson is megtette 1976-ban a következőképp: Legyen m egész, és G véges m-edrendű, egyébként tetszőleges additív csoport (nem szükségképp Abel-csoport). Ekkor tetszőleges 2m-1 db. (nem feltétlenül különböző) G-beli elem közül kiválasztható m darab úgy, hogy ezek összege a csoport nulleleme legyen – az ilyen, nulla összegű részhalmazokat vagy sorozatokat egyébként az additív számelmélet nyelvén, némileg helytelenül, zérósorozatnak (zero sequences) nevezik, bár helyesebb lenne nullasorozatnak vagy (hogy ne legyen összekeverhető az analízisbeli nullsorozat fogalmával) nullösszegsorozatnak nevezni (On a combinatorial problem of Erdős, Ginzburg and Ziv, J. Number Theory, 8 (1976), 52.-57.).

Eme általánosításnál maradva már nem lesz igaz az, hogy a 2m-1 alsó korlát nem javítható, ez G=ℤ_m-re ugyan igaz, más csoportokra nem feltétlenül.

• W. D. Gao 1996-os dolgozatában (A combinatorial problem on fnite Abelian group, J. Number Theory 58 (1996), 100-103.) vezette be e probléma könnyebb tárgyalhatósága a nullösszeg-konstans és – Davenport nyomán (ld. a következő bekezdést) az additív számelméleti Davenport-konstans fogalmát. A G csoport nullösszeg-állandója, Zs(G) (Zero-sum constant of group G) legyen az a legkisebb z∈ℕ természetes szám, melyre igaz, hogy bármely z hosszúságú G-beli sorozat tartalmaz egy |G| hosszúságú nullösszeg részsorozatot (az EGZT pontosan azt állítja, hogy Zs(ℤ_m)=2m-1). A G csoport Davenport-állandója legyen d a legkisebb természetes d szám, melyre igaz, hogy ha adott tetszőleges S⊆G |S| hosszúságú véges G-beli elemsorozat úgy, hogy |S|≥d legyen, akkor ennek van egy nulla összegű T részsorozata. Gao e dolgozatának fontos eredménye szerint a tovább már nem javítható alsó korlát a következő: |G|+D(G)-1 azaz m+D(G)-1, ahol D(G) a G csoport ún. Davenport-állandója – egyébként D(ℤ_m)=m.
  • 1966-ban Harold Davenport bevezette azt a fogalmat gyűrűkre, amit róla Davenport-állandónak neveztek el. A D(G) Davenport-állandót adott G additív csoportra Davenport eredetileg úgy definiálta, mint a prímideálok maximális számát (multiplicitással együtt) azon algebrai számtest egész elemei (tehát a gyűrű egységeleme egész számú többszörösei) gyűrűje valamely irreducibilis eleme prímideál-felbontásában, mely algebrai számtest ideális osztálycsoportja G [3].
  • mindennek egy részletesebb, talán jobb leírása: B. Sury – R. Thangadurai: Gao’s conjecture on zero-sum sequences Archiválva 2007. május 10-i dátummal a Wayback Machine-ben

Pieter Cornelis Baayen fogalmazták meg a következő kérdéseket Let G be an abelian group of order n.

Hivatkozások

Lásd még

• nullösszeg-problémák
• Ramsey-elmélet, Ramsey-problémakör
• Cauchy–Davenport-lemma
• Chevalley–Warning-tétel
• additív számelmélet

Források

Ld. még itt: Külső hivatkozások

További információk

• Rokon additív számelméleti problémák témakörét feldolgozó linkgyűjtemény Archiválva 2013. február 3-i dátummal a Wayback Machine-ben

PDF dokumentumok

• R. Thangadurai: Az EGZT nem-kanonikus általánosításai; a tétel általánosításairól
• R. Balasubramaniam – Gautami Bhowmik: Upper bound for the davenport constant A Davenport-konstans és becslések az EGZT általánosításaival kapcsolatban – e cikkben csak a nullösszeg-konstans miatt fontos.

---

• Nullösszeg-sorozatok:
  • A problémakör történetéről
  • Gao-Geroldinger: On Zero-sum sequences ..., az EGZT Davenport-Baayen-féle, zéróösszeg-problémakörbe való ágyazásáról
  • V. Ponomarenko: Minimal zero sequences
• Adhikari-Chen-Friedlander-Konyagin-Pappalardi: Contribution to zero-sum-problems Az EGZT további általánosításai (nyomtatásban: Discrete Mathematics, Volume 306, Issue 1, 2006 jan 28.; 1.-10. old.)
• Hao Wang: Note on a variant of EGZT, az EGZT szélsőértékvizsgálat-szempontú megfogalmazásáról, általánosításairól
• A lefedőrendszerek és a nullösszeg-problémák kapcsolatáról
  • Zhi-Wei Sun: Covering systems and their connection to zero-sums Archiválva 2007. szeptember 29-i dátummal a Wayback Machine-ben
  • Zhi-Wei Sun: Unification of zero-sum problems, subset sums and covers of ℤ
• Az eredeti EGZ-cikk Zentralblatt profilja Archiválva 2005. december 23-i dátummal a Wayback Machine-ben
• Ramsey-elmélet