Problem o sumie zerowej

0 W teorii liczb problemy o sumie zerowej to pewne rodzaje problemów kombinatorycznych dotyczących struktury skończonej grupy abelowej . Konkretnie, mając skończoną grupę abelową G i dodatnią liczbę całkowitą n , pyta się o najmniejszą wartość k taką, że każdy ciąg elementów G o rozmiarze k zawiera n wyrazów, których suma wynosi .

Klasycznym wynikiem w tym obszarze jest twierdzenie Paula Erdősa , Abrahama Ginzburga i Abrahama Ziva z 1961 roku . Udowodnili, że dla grupy liczb całkowitych modulo n , ${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z}}$

{\ Displaystyle k = 2n-1.}

Wyraźnie mówi to, że każdy multizbiór 2 n - 1 liczb całkowitych ma podzbiór o rozmiarze n , którego suma elementów jest wielokrotnością n , ale to samo nie jest prawdą w przypadku multizbiorów o rozmiarze 2 n - 2. (Rzeczywiście, niższy granica jest łatwa do zauważenia: multiset zawierający n - 1 kopii 0 i n - 1 kopii 1 nie zawiera n - podzbioru sumującego się do wielokrotności n .) Wynik ten jest znany jako twierdzenie Erdősa – Ginzburga – Ziva po swoich odkrywcach. Można to również wywnioskować z twierdzenia Cauchy'ego – Davenporta .

Istnieją bardziej ogólne wyniki niż to twierdzenie, takie jak twierdzenie Olsona, hipoteza Kemnitza (udowodnione przez Christiana Reihera w 2003 r.) I ważone twierdzenie EGZ (udowodnione przez Davida J. Grynkiewicza w 2005 r.).

Zobacz też

Geroldinger Alfred (2009). „Dodatkowa teoria grup i nieunikalne rozkłady na czynniki”. W Geroldinger, Alfred; Ruzsa, Imre Z. (red.). Kombinatoryczna teoria liczb i addytywna teoria grup . Zaawansowane kursy matematyki CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Yo; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J .; Stanchescu, Y. Z przedmową Javiera Cilleruelo, Marca Noya i Oriol Serra (koordynatorów DocCourse). Bazylea: Birkäuser. s. 1 –86. ISBN 978-3-7643-8961-1 . Zbl 1221.20045 .
Nathanson, Melvyn B. (1996). Teoria liczb addytywnych: problemy odwrotne i geometria zbiorów sum . Absolwent Teksty z matematyki . Tom. 165. Springer-Verlag . ISBN 0-387-94655-1 . Zbl 0859.11003 .

Linki zewnętrzne

„Twierdzenie Erdösa-Ginzburga-Ziva” , Encyklopedia matematyki , EMS Press , 2001 [1994]
PlanetMath Erdős, Ginzburg, Twierdzenie Ziva
Sun, Zhi-Wei , „Systemy obejmujące, sumy ograniczone, problemy o sumie zerowej i ich unifikacja”