Nulo-suma problemo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En nombroteorio, nulo-suma problemo estas la problemo trovi la plej malgrandan entjeron k tian ke ĉiu vico de eroj de G kun longo k enhavas n erojn kies sumo estas la neŭtra elemento (0), kie G estas finia komuta grupo kaj n estas donita entjero.

En 1961 Paŭlo Erdős, A. Ginzburg kaj A. Ziv pruvis la ĝeneralan rezulton por \mathbb{Z}/n\mathbb{Z} (la entjeroj mod n):

k = 2n-1.

En ĉi tiu okazo, la n egalas al amplekso de G, kvankam ĝenerale ĉi tio ne nepras.

Eksplicite ĉi tio signifas ke ĉiu multaro de 2n-1 entjeroj havas subaron de amplekso n, la sumo de kies eroj estas oblo de n (kaj do estas 0 module n). Ĉi tiu rezulto estas ĝenerale sciata kiel la EGZ teoremo laŭ ĝiaj esploristo.

Pli ĝeneralaj rezultoj ol ĉi tiu teoremo ekzistas - teoremo de Olson, konjekto de Kemnitz (pruvita de Christian Reiher en 2003), kaj la pezita EGZ teoremo (pruvita per D. J. Grynkiewicz en 2005).

Eksteraj ligiloj[redakti | redakti fonton]