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.).

Különféle megfogalmazásai:

  • 2m-1 db egész szám között biztosan van m darab, melyek összege osztható m-mel (m>0 egész).
  • Formálisan: ∀m∈ℕ+: [(A⊆ℤ ∧ |A|=2m-1 ) ⇒ ∃S={s1,s2,…,sm}⊆A: (|S|= m ∧ m│s1+s2+…+sm)]
  • A tétel igaz nemcsak akkor, ha számhalmazokra, hanem akkor is, ha egész számokból álló sorozatokra vagy elemrendszerekre fogalmazzuk meg, azaz: „2m-1 darab nem feltétlenül különböző egész szám között van m darab nem feltétlenül különböző egész szám, melyek összege osztható m-mel”. A bizonyítások azonban néhány helyen e megfogalmazástól körülményesebbé válnak, noha módosításuk nem igényel semmi extra ismeretet vagy készséget az eredeti bizonyítások megértéséhez szükséges ismeretekhez, készségekhez képest (hacsak ide nem számítjuk az elemrendszerekre vonatkozó általánosabb ismereteket).

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.

Azaz: Tegyük fel, hogy a p,q számok olyanok, hogy 2p-1 db szám között mindig van p db p-vel osztható összegű, és 2q-1 db szám között is mindig van q darab q-val osztható összegű. Válasszunk ki tetszőleges 2pq-1 db egész számot. Ekkor lesz köztük pq darab, melyek összege pq-val osztható.

A bizonyítás azon a taktikán alapul, hogy kiválasztunk rengeteg szám-(2p-1)-est, ezek között mindig van p db p-vel osztható összegű, majd megmutatjuk, hogy olyan sok diszjunkt (egymástól független) szám-(2p-1)-est lehet kiválasztani, hogy a p-vel osztható összegű szám-p-esek száma legalább 2q-1. Ebből viszont egyszerűen következni fog a segédtétel.

Tehát: legyen A egész számok |A| = 2pq-1 elemszámú halmaza, és p,q>0.

  • Válasszuk ki az első szám-(2p-1)-est, ezek között található p darab p-vel osztható összegű szám, legyen ezek halmaza A1. Ezeket kivesszük az A-ból, a kiválasztott 2p-1-es többi elemét viszont visszatesszük (takarékosság okából). Marad az A1' := A\A1 halmaz, melynek elemszáma 2pq-1-(2p-1) = 2pq-2p.
  • Ezt az eljárást ismételjük: tehát kiválasztunk az Ak' :=A\(A1∪A2∪…∪Ak) halmazból 2p-1 számot, ezek közül kivesszük azt a p elemű Ak+1 részhalmazt, mely elemei összege osztható p-vel (a segédtétel feltevése szerint ilyen létezik), a többit visszatesszük, tehát csökkent a maradék "nagy" Ak+1' = A\(A1∪A2∪…∪Ak∪Ak+1) halmaz elemszáma p-vel, elemszáma összesen |A|-|A1∪A2∪…∪Ak∪Ak+1| = (2pq-1)-[(k+1)p].
  • Ezek szerint a k-adik lépésben a "nagy" halmaz elemszáma
Ak' = (2pq-1)-kp.

A k-adik lépés utáni lépést akkor tudjuk végrehajtani, amíg van legalább 2p-1 elem a "nagy" (Ak') halmazban, melyeket kivehetünk, azaz amíg igaz, hogy (2pq-1)-kp ≥ 2p-1;

(Γ:)                                                       (2pq-1)-kp ≥ 2p-1;                                                      

(és akkor kell megállnunk, ha ez már nem igaz, azaz

(2pq-1)-kp < 2p-1

tehát ha ez igaz, akkor k-1 db p-est még esetleg ki lehet választani, de k-t már nem).

A fenti (Γ) egyenlőtlenséget k-ra megoldva azokat a k∈ℕ számokat keressük, melyekre igaz, hogy k-szor ismételve a fent leírt rekurzív eljárást, még ki tudtunk választani egy elem-(2p-1)-est a „nagy” halmazból. Kicsit átrendezve és megoldva:

2pq-1-(2p-1) ≥ kp
2pq-2p ≥ kp

osztva p>0-val:

2q-2 ≥ k

Tehát k-ra nézve azon természetes számok megoldások, melyek nagyobbak mint 2q-2. A szerencsénk az, hogy a 2q-2 szám ezek közt van, mert ez azt jelenti, hogy a következő, 2q-1-edik lépést végre tudjuk hajtani. Valóban, a (2q-2)-edik lépésben:

2pq-1-(2q-2)p = 2pq-1-2qp+2p = 2p-1,

és ez azt jelenti, hogy még a (2q-1)-edik 2p-1-est is ki tudjuk a "nagy" halmazból választani, így ebből meg a (2q-1)-edik p-vel osztható összegű p-est is.

Adottak tehát az Ai halmazok (0≤i≤2q-1), melyekre |Ai|=p és minden i-re, elemeik összege p-vel osztható. Jelölje ezen összegeket Si, ekkor tehát Si/p egész szám. Ezen egészek száma legalább 2q-1. Tehát van köztük q darab q-val osztható összegű. Legyen az összeg B, tehát B osztható q-val, B=qd alakú (d∈Z)! A B összeg minden tagja Si/p alakú p-tagú összeg. A B tehát q darab p-tagú összeg összege, azaz egy pq-tagú összeg, melynek minden tagja olyan tört, melynek számlálója A-beli egész, nevezője pedig p. Megszorozva B-t tagonként p-vel, olyan B'=Bp=dqp összeget kapunk, melynek pq tagja van, és minden tagja olyan tört, melynek számlálója A-beli egész, nevezője 1. Tehát ez végül is egy pq tagú összeg, melynek minden tagja A-beli. Ez tehát pq darab A-beli elem összege, ráadásul pq-val is osztható. A segédtételt igazoltuk.

Megjegyzés: ebből a segédtételből és a prímekre vonatkozó bizonyításokból az EGZT a számelmélet alaptétele segítségével látható be (ld. lentebb).

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

Jelölje, ha k∈N; \mbox{ }_{ \mathcal{P}_{k} \left( A \right)} az A halmaz k elemű részhalmazainak (kombinációinak) halmazát:

 \mathcal{P}_{k} \left( A \right) := \left\{ X \subseteq A \ \ | \ \ |X|=k \right\}  ;

e kombinációk száma (amennyiben A véges) köztudomásúlag  \mbox{ }_{ | \mathcal{P}_{k} | } \mbox{ }_{=} \ \mbox{ }_{ { |A| \choose k } } \mbox{ }_{=} \ \mbox{ }_{ \frac{|A|!}{k!(|A|-k)!} } .

Ha p prím és A⊆Z véges számhalmaz; tekintsük az

 S  =  S(A,p)  =  \sum_{ \begin{matrix} \mbox{ }_{I \subseteq A} \\ \mbox{ }_{|I|=p} \end{matrix} } \left( \sum_{ a \in I } a \right)^{p-1}  =  \sum_{I \in \mathcal{P}_{p} \left( A \right) } \left( \sum_{ a \in I } a \right)^{p-1}

összegeket.

Tegyük fel indirekte, hogy az EGZ-tétel valamely p prímre nem igaz, azaz S mindegyik tagja olyan alösszegnek a p-1-edik hatványa, mely alösszeg nem osztható p-vel (tehát valóban nincs olyan p-tagú alösszeg, mely p-vel osztható lenne). Ebből Fermat "kis" tétele segítségével következik, hogy az S összeg  \mbox{ }_{ { \mathbf{2p-1} \choose \mathbf{p} } } -vel kongruens (modulo p), ami nem osztható (nem kongruens) p-vel (modulo p); részletesebben lásd: itt. Másrészt – lényegében a polinomiális tétel segítségével – megmutatjuk, hogy az S összeg bármely p prím és A egész számhalmaz esetén valójában nem ennyi, mert mindig p-vel osztható kell hogy legyen, lásd itt. Ebből következően tehát nem igaz, hogy S nem osztható p-vel, de akkor az sem igaz, hogy az "alösszegek között nincs p-vel osztható" (mert ebből levezettük, hogy S nem osztható p-vel, ami a fentiek szerint nem igaz), ami meg pontosan azt jelenti, hogy "nem igaz az EGZT tagadása", vagyis igaz az EGZT.

Indirekt bizonyítás p∤S-re[szerkesztés | forrásszöveg szerkesztése]

Az S összeg azért nem osztható p-vel, ha egyik tagja sem, mert a tagjai p-1-edik hatványra vannak emelve, és a kis-Fermat-tétel miatt egy p prímmel nem osztható szám p-1-edik hatványa 1-gyel kongruens modulo p, és mivel annyi darab összeg van, ahányféleképp kiválaszthatjuk a 2p-1 db szám közül a p-tagú összegeket, vagyis {2p-1 \choose p} darab, ezért modulo p az S összeg kiszámolásakor is ennyi db. 1 maradékosztályt kell összeadni. Vagyis, az indirekt feltevésből az következik, hogy

 S  \equiv

 \sum_{ \begin{matrix} \mbox{ }_{I \subseteq A} \\ \mbox{ }_{|I|=p} \end{matrix} } 1  \pmod{p}  =  \sum_{ I \in \mathcal{P}_{p} \left( A \right) } 1  =  | \mathcal{P}_{p} \left( A \right) |

 =  { |A| \choose p }  =


 =  { 2p-1 \choose p }

 =  \frac{(2p-1)!}{p! \cdot (2p-1-p)!}

 =  \frac{(2p-1)!}{p! \cdot (p-1)!}  =


 =  \frac{1 \cdot 2 \cdot \cdot ... \cdot (p-1) \cdot p \cdot (p+1) \cdot ... \cdot (2p-1) }{ \left(1 \cdot 2 \cdot ... \cdot p \right) \cdot \left( 1 \cdot 2 \cdot ... \cdot (p-1) \right) }  =


 \equiv  \frac{ (p+1) \cdot (p+2) \cdot ... \cdot (2p-1) }{ 1 \cdot 2 \cdot ... \cdot (p-1) } \pmod{p}
 \not\equiv  0 \pmod{p}


Ugyanis hogy  \mbox{ }_{ F \ := \ \frac{ (p+1) \cdot (p+2) \cdot ... \cdot (2p-1) }{ 1 \cdot 2 \cdot ... \cdot (p-1) } } 0-val kongruens avagy p-vel osztható legyen, tehát F=dp alakú legyen (d∈ℤ), az F nevezőjével átszorozva, és figyelembe véve, hogy a nevező relatív prím p-hez, ez láthatóan azzal ekvivalens, hogy F számlálója legyen kongruens 0-val avagy osztható p-vel. De mivel p prím, ha osztója egy szorzatnak (F számlálójának), akkor valamelyik tényezőjének osztója kell hogy legyen. De szintén p prímtulajdonságából következik, hogy ez lehetetlen, hisz egy prím nem lehet osztója egyik 1-nél nagyobb, de nála határozottan kisebb szám sem, csak 1 és önmaga (másképp szólva is belátható ez: Wilson tétele alapján ugyanis az F F' számlálójára F' := (p+1)·(p+2)·…·(2p-1) ≡ 1·2·…·(p-1) = (p-1)! ≡ -1 mod(p), amiből szintén következik, hogy nem kongruens 0-val a számláló, és így F sem.

Direkt bizonyítás p│S-re[szerkesztés | forrásszöveg szerkesztése]

Másrészt annak belátásához, hogy S mindig osztható p-vel, felbontjuk az S zárójeleit.

Legyen az S összeg egy-egy p-1-edik hatványra emelt tagja SI, tehát ha  I \in \mathcal{P}_{p}(A) , azaz  I = \left\{ a_{1_{I}}, a_{2_{I}}, ..., a_{p_{I}} \right\} \subseteq A, akkor

 S_{I}(A,p) = S_{I} := \left( \sum_{H_{I}=1_{I}}^{p_{I}} a_{H_{I}} \right)^{p-1} .

.

(Például, ha p=3, azaz |A| = 2p-1 = 2·3-1 = 6-1 = 5; akkor az A = {a1,a2,a3,a4,a5} halmaz esetén

S= (a1+a2+a3)2+ (a1+a2+a4)2+ (a1+a2+a5)2+ (a1+a3+a4)2+ (a1+a3+a5)2+ (a1+a4+a5)2+ (a2+a3+a4)2+ (a2+a3+a5)2+ (a3+a4+a5)2

és például ekkor ha I={a1,a3,a4}, akkor  S_{I} = S_{ \left\{ a_{1}, a_{3}, a_{4} \right\} } = (a1+a3+a4)2 = a12+a32+a42 + 2(a1a3+a1a4+a3a4).

A polinomiális tételből következik – de teljes indukcióval is belátható – hogy minden SI összeg  T_{k_{1},k_{2},...,k_{p-1}} := C_{I} \left( k_{1}, k_{2}, ... , k_{p-1} \right) a_{1_{I}}^{k_{1}}a_{2_{I}}^{k_{2}}...a_{(p-1)_{I}}^{k_{p-1}} alakú tagok összege, ahol k1+k2+…+kp-1 = p-1; és ahol a  \mbox{ }_{ C_{I} \left( k_{1}, k_{2}, ..., k_{p-1} \right) } \mbox{ }_{=} \mbox{ }_{ { p-1 \choose k_{1}, k_{2}, ..., k_{p-1} } } \mbox{ }_{=} \mbox{ }_{ \frac{(p-1)!}{k_{1}! \cdot k_{2}! \cdot ... \cdot k_{p-1}! } } polinomiális együtthatók csakis a k1,k2,…,kp-1 számoktól függenek, azaz több olyan I halmaz is van, melyben szerepel egy-egy ilyen T összeg. Egy-egy T összegben, mely egy C polinomiális együttható és néhány A-beli elem olyan hatványának szorzata, mely hatványok kitevője 0 és p-1 közti természetes szám, válogassuk ki azokat az A-beli elemeket, legyen ezek halmaza p(T), melyek hatványkitevője nem nulla (ha mondjuk T = 2a12a20, akkor p(T)=a1).

Az S összeg összes olyan T tagját, mely "valójában" a C és ugyanezen p(T) elemek ugyenezeken a kitevőkön való szorzata, egybe fogjuk csoportosítani (megjegyezzük, hogy a kitevők egyezéséből már a C-k egyezése is következik, hiszen a C együtthatók csak a kitevőktől függnek). Az S összeg így mTT alakú tagok összege lesz, ahol mT annak a száma, hányszor fordul elő T az S-ben. Tekintve p(T) elemeit, ha ezek előfordulnak egy I p elemű A-beli kombinációban, akkor biztos, hogy az SI összegben meg fog jelenni a T, hiszen ez tartalmaz minden olyan T összeget, mely elemei az I-ből valók. Mivel az SI-k halmaza osztályfelbontása is S-nek, ezért ez nemcsak elegendő, hanem szükséges feltétel is. Tehát azt kell megszámolnunk, hány olyan I p elemű kombináció van, mely tartalmazza a p(T) elemeit, és megkapjuk mT-t. Ez egy kombinatorikai feladat, legyen p(T) s elemű (|p(T)| = s, egyébként 1≤s≤p-1). Mivel I jelenthet bármely p elemű A-beli kombinációt, azért ha kikötjük, hogy legyen p(T)&subs;I, úgy az f(I) = I\p(T) függvény "végigfutja" az összes A-beli |I\p(T)| = p-s -elemű kombinációt, ha az I független változó "végigfut" a p elemű és p(T)-t részhalmazként tartalmazó A-beli kombinációkon. Magyarul, azokat az I kombinációkat, melyekben szerepelnek a p(T) elemei, pontosan úgy állíthatjuk elő, hogy veszünk p-s db. p(T)-be nem eső elemet a-ból, és képezzük ezek halmazának és p(T)-nek az unióját. Tehát mT pontosan az a szám, ahányféleképp A p(T)-be nem eső elemei közül (|A\p(T)| = (2m-1)-s db. elem közül) kiválaszthatunk néhány p(T)-be nem esőt úgy, hogy összesen p.-nyien legyenek, azaz p-|p(T)| = p-s db.-ot. Tehát:

 m_{T} = {2p-s-1 \choose p-s}

Az pedig könnyen belátható, hogy mT osztható p-vel tetszőleges olyan s-re, melyre 0≤s≤p. Egyébként s itt a nem nulla hatványkitevők számát jelenti a T tagokban (s is a k kitevőktől függ csak). Ugyanis:

 m_{T}  =  {2p-s-1 \choose p-s}  =  \frac{(2p-s-1)!}{ (p-s)! \cdot (2p-s-1-[p-s])!}  =

 =  \frac{1 \cdot 2 \cdot ... \cdot (p-s) \cdot (p-s+1) \cdot ... \cdot (p-s+p-1) }{ (1 \cdot 2 \cdot ... \cdot [p-s]) \cdot (p-1)! }  =

 =  \frac{ (p-s+1) \cdot ... \cdot (p-s+p-1) }{ (p-1)! }  =

 =  \frac{ \prod_{k=1}^{p-1} p-s+k }{ (p-1)! }

Ha érvényes p|mT, azaz van olyan d egész szám, hogy érvéynes legyen mT=dp, akkor mT nevezőjével átszorozva, a számlálónak is osztója d. Ez fordítva is igaz, mert ha a számlálónak osztója p, akkor mivel mT úgy áll elő, hogy leosztjuk számlálóját p-hez relatív prím számokkal – valójában a mod(p) redukált maradékrendszerrel – az így leosztott számnak is osztója marad a p, az osztóval relatív prím számmal való egyszerűsítés nem változtat az oszthatóságon (másképp: ha a számláló kongruens 0-val mod(p), ezt a kongruenciát szabad a modulushoz relatív prím számokkal osztani, érvényes marad). Tehát p|mT ekvivalens azzal, hogy p osztója mT számlálójának, bármi is az s 1 és p-1 között. Ez igaz, mert a p-s+k ≡ 0 (mod p) kongruencia ekvivalens a k ≡ s (mod p) kongruenciával, és k végigfut az 1 és p-1 közti összes számon, tehát valamelyik k-ra kongruens lesz s-sel, hiszen rögzített s esetén s is egy 1 és p-1 közti szám. Tehát van megoldása a k ≡ s (mod p) kongruenciának minden 1 és p-1 közti s-re, azaz tetszőleges T esetén, és így p|mT minden T-re, miáltal p osztója az mTT-k összegének is, azaz S-nek. QED.


Forrás.[1]

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

Forrás.[2]

További bizonyítási lehetőségek prímekre[szerkesztés | forrásszöveg szerkesztése]

A tétel következik az ún. Cauchy–Davenport-lemmából, 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]

De levezethető az EGZT akár a véges testek elméletének egyik tételéből, a Chevalley-Warning-tételből is (ld. Melvin B. Nathanson: Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Graduate texts in mathematics; 165), Springer-Verlag, New York, 1996; 48.-51.)., említi szintén [3] ). E tétel szerint ha F véges test, rendje tehát |F| = pα, ahol p prím; akkor bármely olyan m darab egyenletből álló n-változós homogén algebrai egyenletrendszerre (melynek minden egyenletének bal oldala F fölötti n-változós polinom, jobb oldala a test 0 nulleleme, és n,m∈ℕ+ pozitív egész számok); teljesül, hogy a polinomok fokszámának összege kisebb legyen mint n (a változók száma), akkor ha N∈ℕ; jelöli eme egyenletrendszer (Fn-beli) megoldásainak számát, úgy p|N (és emiatt, N≠1) (így, ha létezik megoldás, azaz ha a polinomoknak van közös gyöke, akkor van egy másik is).[4]

A tétel következik a segédtételből[szerkesztés | forrásszöveg szerkesztése]

  • m = 0-ra az EGZT azt állítaná, hogy -1 darab egész szám között van 0 darab 0-val osztható. Ezt az esetet, értelmetlensége miatt, kizártuk az m>0 feltétellel.
  • m = 1-re azt állítja, hogy 1 darab egész szám közt van 1 darab, melynek összege osztható 1-gyel. Ez bármely fenti bizonyítástól függetlenül igaz, mert 1 bármely egész számnak osztója.

Prímekre fentebb többféle módon igazoltuk az EGZT-t. Marad tehát az a kérdés, hogy igaz-e összetett számokra.

Viszont a segédtételből következően ez is igaz. Ugyanis bármely összetett szám a számelmélet alaptétele alapján az m = p1p2…ph; (h>0 egész, pi ahol 1≥i≥h pedig nem feltétlenül különböző prímek) félig kanonikus alakra hozható, és h-ra vonatkozó indukcióval beláthatóan igaz az EGZT m-re is (hisz ha igaz p1-re és p2-re, igaz p1p2-re is, és ha még a p3 prímre is igaz, igaz az előző két szám szorzatára, p1p2p3-ra is … és így tovább).

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, amenyben 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” [5] ;.[6]

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

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

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

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. ^ a b 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. Zhi-Wei Sun On zero-sum problems (A Nullösszeg-problémákról)
  5. Hajnal Péter: Ramsey-elmélet, alap Ramsey-tétel és Ramsey-számok
  6. Noga Alon: On three zero-sum Ramsey-type problems (Három Ramsey-típusú nullösszeg-problémáról)
  7. ^ a b c R. Thangadurai ([1], [2]) Non-canonical extensions of Erdős-Ginzburg-Ziv Theorem1 (Az EGZT nem-kanonikus általánosításai])
  8. 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]