Erdős–Ginzburg–Ziv-tétel

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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\le i\le 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.[szerkesztés | forrásszöveg szerkesztése]

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_1x_1^{p-1}+a_2x_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. [1]

Bizonyítás prímekre II.[szerkesztés | forrásszöveg szerkesztése]

Forrás.[2]

Bizonyítás prímekre III.[szerkesztés | forrásszöveg szerkesztése]

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.[3]

A tétel következik a segédtételből és a prímekre vonatkozó változatából[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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” [4] ;.[5]

A tétel további megfogalmazásai és általánosításai[szerkesztés | forrásszöveg szerkesztése]

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

Átfogalmazás maradékosztályokra[szerkesztés | forrásszöveg szerkesztése]

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.[6]
  • 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.) [6]

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[szerkesztés | forrásszöveg szerkesztése]

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.[7]

Szimpla és extremális átfogalmazások additív csoportokra[szerkesztés | forrásszöveg szerkesztése]

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.).[6]

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.

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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Hegyvári Norbert: Összeg-és különbséghalmazok számossága/Additív problémák az elemi számelméletből (előadások az ELTE-n)
  2. Az Erdős-Ginzburg-Ziv-tétel egy bizonyítása Komjáth Péter honlapjáról (pdf)
  3. Zhi-Wei Sun Unification of zero-sum problems, subset sums and covers of ℤ (A nullösszeg-problémák, részhalmazösszeg-problémák és ℤ lefedései problémáinak egyesített vizsgálatáról)
  4. Hajnal Péter: Ramsey-elmélet, alap Ramsey-tétel és Ramsey-számok
  5. Noga Alon: On three zero-sum Ramsey-type problems (Három Ramsey-típusú nullösszeg-problémáról)
  6. ^ a b c R. Thangadurai ([1], [2]) Non-canonical extensions of Erdős-Ginzburg-Ziv Theorem1 (Az EGZT nem-kanonikus általánosításai])
  7. On the structure of p-zero-sum free sequences and its application to a variant of Erdős–Ginzburg–Ziv theorem (Weidong Gao, A. Panigrahi, R. Thangadurai)

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

További információk[szerkesztés | forrásszöveg szerkesztése]

Pdf dokumentumok[szerkesztés | forrásszöveg szerkesztése]